A novel hybrid model for task scheduling based on particle swarm optimization and genetic algorithms

Karishma; Harendra Kumar; Karishma; Harendra Kumar

doi:10.3934/mine.2024023

Mathematics in Engineering

2024, Volume 6, Issue 4: 559-606. doi: 10.3934/mine.2024023

Previous Article Next Article

Research article

A novel hybrid model for task scheduling based on particle swarm optimization and genetic algorithms

Karishma ,
Harendra Kumar ^,

Department of Mathematics and Statistics, Gurukula Kangri (Deemed to be University) Haridwar, Uttarakhand 249404, India

Received: 03 February 2024 Revised: 25 June 2024 Accepted: 31 July 2024 Published: 08 August 2024

Distributed real time system has developed into an outstanding computing platform for parallel, high-efficiency applications. A real time system is a kind of planning where tasks must be completed with accurate results within a predetermined amount of time. It is well known that obtaining an optimal assignment of tasks for more than three processors is an NP-hard problem. This article examines the issue of assigning tasks to processors in heterogeneous distributed systems with a view to reduce cost and response time of the system while maximizing system reliability. The proposed method is carried out in two phases, Phase Ⅰ provides a hybrid HPSOGAK, that is an integration of particle swarm optimization (PSO), genetic algorithm (GA), and k-means technique while Phase Ⅱ is based on GA. By updating cluster centroids with PSO and GA and then using them like initial centroids for the k-means algorithm to generate the task-clusters, HPSOGAK produces 'm' clusters of 'r' tasks, and then their assignment onto the appropriate processor is done by using GA. The performance of GA has been improved in this article by introducing new crossover and mutation operators, and the functionality of traditional PSO has been enhanced by combining it with GA. Numerous examples from various research articles are employed to evaluate the efficiency of the proposed technique, and the numerical results are contrasted with well-known existing models. The proposed method enhances PIR values by 22.64%, efficiency by 6.93%, and response times by 23.8 on average. The experimental results demonstrate that the suggested method outperforms all comparable approaches, leading to the achievement of superior results. The developed mechanism is acceptable for an erratic number of tasks and processors with both types of fuzzy and crisp time.

Keywords:

Citation: Karishma, Harendra Kumar. A novel hybrid model for task scheduling based on particle swarm optimization and genetic algorithms[J]. Mathematics in Engineering, 2024, 6(4): 559-606. doi: 10.3934/mine.2024023

Related Papers:

[1]	Jorge E. Macías-Díaz, Anastasios Bountis, Helen Christodoulidi . Energy transmission in Hamiltonian systems of globally interacting particles with Klein-Gordon on-site potentials. Mathematics in Engineering, 2019, 1(2): 343-358. doi: 10.3934/mine.2019.2.343
[2]	Andrea Manzoni, Alfio Quarteroni, Sandro Salsa . A saddle point approach to an optimal boundary control problem for steady Navier-Stokes equations. Mathematics in Engineering, 2019, 1(2): 252-280. doi: 10.3934/mine.2019.2.252
[3]	Boubacar Fall, Filippo Santambrogio, Diaraf Seck . Shape derivative for obstacles in crowd motion. Mathematics in Engineering, 2022, 4(2): 1-16. doi: 10.3934/mine.2022012
[4]	Matteo Lapucci, Davide Pucci . Mixed-integer quadratic programming reformulations of multi-task learning models. Mathematics in Engineering, 2023, 5(1): 1-16. doi: 10.3934/mine.2023020
[5]	Mario Pulvirenti . On the particle approximation to stationary solutions of the Boltzmann equation. Mathematics in Engineering, 2019, 1(4): 699-714. doi: 10.3934/mine.2019.4.699
[6]	Lorenzo Pistone, Sergio Chibbaro, Miguel D. Bustamante, Yuri V. Lvov, Miguel Onorato . Universal route to thermalization in weakly-nonlinear one-dimensional chains. Mathematics in Engineering, 2019, 1(4): 672-698. doi: 10.3934/mine.2019.4.672
[7]	Martina Teruzzi, Nicola Demo, Gianluigi Rozza . A graph-based framework for complex system simulating and diagnosis with automatic reconfiguration. Mathematics in Engineering, 2024, 6(1): 28-44. doi: 10.3934/mine.2024002
[8]	Alberto Bressan, Yucong Huang . Globally optimal departure rates for several groups of drivers. Mathematics in Engineering, 2019, 1(3): 583-613. doi: 10.3934/mine.2019.3.583
[9]	Stefania Fresca, Federico Fatone, Andrea Manzoni . Long-time prediction of nonlinear parametrized dynamical systems by deep learning-based reduced order models. Mathematics in Engineering, 2023, 5(6): 1-36. doi: 10.3934/mine.2023096
[10]	Diogo Gomes, Julian Gutierrez, Ricardo Ribeiro . A mean field game price model with noise. Mathematics in Engineering, 2021, 3(4): 1-14. doi: 10.3934/mine.2021028

Abstract

Abbreviations:

Indices	$i, j$	Task index, $\; i, j = 1, 2, ..., r$
Indices	$k, l$	Processor index/Clustering index, $k, l = 1, 2, ..., m$
Parameters	$T = \left\{ {{t_i}:\; i = 1, 2, ..., r} \right\}$	Set of r number of tasks
	$P = \left\{ {{p_k}:\; k = 1, 2, ..., m} \right\}$	Set of m number of processors
	${\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{e} _{i, k}}$	${\text{Fuzzy }}{E_T}{\text{ of }}{i^{th}}{\text{ task on }}{k^{th}}{\text{ processor }}$
	$F{E_T}M = \left[{{{\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{e} }_{i, k}}} \right]$	${\text{Fuzzy }}{E_T}{\text{ matrix}}$
	${\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{c} _{i, j}}$	${\text{Fuzzy }}IT{C_T}{\text{ between tasks }}{t_i}{\text{ and }}{t_j}\; \;$
	$FIT{C_T}M = \left[{{{\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{c} }_{i, j}}} \right]$	${\text{Fuzzy }}IT{C_T}{\text{ matrix }}$
	${e_{i, k}}$	${\text{Crisp }}{E_T}{\text{ of task }}{t_i}{\text{ on }}{p_k}{\text{ processor }}$
	${E_T}M = \left[{{e_{i, k}}} \right]$	${E_T}{\text{ matrix}}$
	${c_{i, j}}$	${\text{Crisp }}IT{C_T}{\text{ between tasks }}{t_i}{\text{ and }}{t_j}\; \;$
	$IT{C_T}M = \left[{{c_{i, j}}} \right]$	$IT{C_T}{\text{ matrix }}$
	$N{E_T}M = \left[{e_{i, k}^{\hat n}} \right]$	${\text{New crisp }}{E_T}{\text{ matrix}}$
	$NIT{C_T}M = \left[{c_{i, j}^{\hat n}} \right]$	${\text{New crisp }}IT{C_T}{\text{ matrix }}$
	${R_k}$	Reliability of processor ${p_k}$
	${R_{kl}}$	Reliability of kl communication link
	${\lambda _k}$	Failure rate of processor ${p_k}$
	${\mu _{kl}}$	Failure rate of kl connecting path
	$c{l_k}$	${k^{th}}$ task cluster
	$C{d_k}$	${k^{th}}$ cluster centroid
	${V_k}\left(t \right)$	Velocity of ${k^{th}}$ particle
	${P_k}\left(t \right)$	Local best fitness of ${k^{th}}$ particle
	${G_k}\left(t \right)$	Globally best fitness of ${k^{th}}$ particle
	${g_{Cd}}$	Fitness value of a particle in PSO
Decision variables	${x_{i, k}}$	$\left\{ \begin{array}{l} 1, \; \; if\; {t_i}\; task\; is\; allocated\; to\; {p_k}\; processor \hfill \\ 0, \; \; otherwise \hfill \\ \end{array} \right.$
	${d_{k, l}}$	Inter-processor distance with unit data transfer where ${d_{k, l}}$ = 0 if k = l.
	${u_{i, k}}$	$\left\{ \begin{array}{l} 1, \; \; if\; {t_i}\; task\; does\; belong\; to\; cluster\; c{l_k}\; \hfill \\ 0, \; \; otherwise \hfill \\ \end{array} \right.$

1. Introduction

Distributed real time system (DRTS) comprises a set of geographically distributed varied-pace heterogeneous processors that are interconnected to each other via fast communication networks. It has become a spectacular stage for computing high efficiency parallel applications. Parallel applications can be split into multiple tasks and executed simultaneously on different processors in the system. To make optimal use of this system, the key challenge lies in generating a task assignment model that assigns each task to the most appropriate processor for parallel execution. Authors Mall ^[1] and Jin and Tan ^[2] did explain that tasks in distributed system are performed in two ways, a hard real time system, and a soft real time system. Jobs are created and outcomes are generated without any time delay in hard real time system. For example, missile system, satellite system etc. (there should not be time lag). Whereas the soft real time system does not have any time limit to deliver the result or within a fixed pre-defined time. For example, web searching. Singh et al. ^[3] mentioned that according to the complexity of the distributed environment we need of system where multiple systems are connected and work together to optimize the goal. Typically, throughput processor usage, tasks waiting time etc., are the execution scales for the task assignment problem. In the system, if scheduling is not executed carefully, processors may take their maximum time to run the calculations. DNS (domain name system) is a simple example of DRTS that is used in a network to translate the domain name to IP address and internet ^[3]. The utilization of distributed system and multiprocessors is becoming very successful in real time applications. And the reason behind this is to provide the fault tolerance feature and lightning response time to the system and prices of these systems. Real time tasks' assignment in distributed environment subsists of two sub-problems: primarily partition of a set of tasks and secondary assignment of tasks to the worthy processor. Based on the time when scheduling decisions are made, there are two classes of assignment policies in DRTS, namely static and dynamic. By the static assignment of the task the permanent allocation of the task can be achieved whereas, in the dynamic assignment, the task is allotted at the time of node arrival or while the task is running. In order to acquire a simple and quick method, it is required to use approximations that yield the nearest optimum performance in a feasible amount of time. In the present work, the analysis focuses on static task assignment within a heterogeneous environment that provides diverse designing capabilities. This allocation technique can be utilized for a large set of real time applications that are able to plan a method which allows deterministic execution. Since static method does not have run time overhead and can be created applying very complex algorithmic process, it is far better than dynamic method.

As compared to centralized systems, DRTS is way more intricate. Excessive complexity can increase the likelihood of system failures. Task allocation technique and reliability play a key role in the efficient utilization of such multiprocessing system. Reliability of the system can be defined as the possibility of execution of a task having each component in working condition. The intricacy of the assignment issue in DRTS is heightened by various factors, such as the variability in task execution time, the discriminative nature of tasks, inter-dependency among tasks, and the challenge of load balancing. Various articles are assigned with the fundamental objective of reducing the total amount of communication and execution time being one of the performance parameters. In order to decrease operational costs, increase capacity, and optimize resource utilization in data centres, Jeyakrishnan and Sengottuvelan ^[4] developed the BSO algorithm for resource allocation and load balancing. The CSS task scheduling technique was developed by Xavier and Annadurai ^[5] to avoid local convergence and find the most optimal VM for tasks. This technique optimized the overall computing cost while increasing the throughput of the cloud system and there has been presented a task scheduling paradigm by Huang et al. ^[6] for task-VM mapping using several discrete PSO algorithm variations in cloud environment. By taking inspiration from the way crocodiles hunt, Abualigah et al. ^[7] developed the Reptile Search Algorithm (RSA), a brand-new meta-heuristic optimizer. The primary goal of RSA was to discover strong search techniques that can deliver higher-quality resolutions to challenging real-world issues.

In the presented article, a novel technique based on PSO-GA has been set up to solve the tasks allotment issue in a heterogeneous static environment. The GA framework can effectively deliver promising results in a broad and complex solution space, making it well suited for the scheduling issue. On the other hand, the PSO algorithm boasts easy implementation and impressive global search capabilities. Despite these advantages, the original PSO encounters limitations due to its slower convergence rate, making it unsuitable for directly tackling assignment issues. Therefore, this article has been hybridized with genetic operators to prevent the shortcomings of PSO. To reach an ideal solution and prevent early convergence, the GA employs continuous iteration. The process of convergence is iterated until it is accomplished. In current technique, the convergence of GA has been improved by presenting new genetic operations and population initialization method. Two phases are addressed in the generated approach. In the first phase a hybrid algorithm HPSOGAK, union of particle swarm optimization (PSO), genetic algorithm (GA) and k-means clustering approach has been induced. The HPSOGAK algorithm is used for the formation of clusters of tasks such that exceedingly communicated tasks assembled together in order to decrease inter-task communication time ( $IT{C_T}$ ). In the second phase, GA is employed to assign task-clusters to processors efficiently, aiming to minimize execution time ( ${E_T}$ ). The vital assists of the proposed technique in a distributed heterogeneous system are outlined below:

● Proposing a new task allocation model in distributed environment that takes into consideration the execution costs of tasks assigned to processors as well as the communication cost between tasks.

● In the context of task allocation onto worthy processors, PSO and GA based algorithms are presented.

● To improve the performance of GA, new crossover and mutation approaches are introduced.

● Proposed algorithm's performance is evaluated through studies based on assessment criteria like as response time, cost of the system, system reliability, performance improvement ratio (PIR %), efficiency, and resource utilization. It consistently delivers superior outcomes in these assessments.

● Analyze the run-time complexity of the proposed method.

The remainder of this article is organized as follows: The work related to this area is presented in Section 2. The definitions and terminology that will be used throughout the work are discussed in Section 3. The model of task allocation problem is explained in Section 4 and Section 5 provides more information on the proposed model's methodology. Four examples, two crisp and two fuzzy are solved in Section 6 by the proposed technique and Section 7 shows the compare of functioning of the suggested model to other existing techniques. Conclusion and recommendations for further research on this task allocation problem are provided in Section 8 and notations used throughout the paper are defined in the nomenclature section.

2. Related work

DRTS provides accurate results in both logical and temporal aspects, distinguishing itself from other types of systems. It can be roughly divided into three areas: environment, controller, and controlled object. In this process, input is received by the controller from the environment, and as an output, it provides information to the controlled object. In DRTS, task allotment is an essential phase. The primary objective of real time system is to establish an allocation model that ensures meeting all deadlines while considering execution time. Over the years, a comprehensive study of task assignment in a multiprocessing environment has led to the development of many efficient scheduling mechanisms for distributed system. Authors Davis and Burns ^[8] and Zhang et al. ^[9] came up with their work on a multiprocessing system. Casanova et al. ^[10] did mention that task allotment issue belongs to the category of NP- complete problem which includes the number of tasks and each task executes on the single processor and communicates with other tasks. In the proposed article, to resolve the task allotment complication, three algorithms namely PSO, GA and k-means clustering technique are integrated together. PSO and GA both are driven by procedures happening in nature. Inspired by the movements of bird flocks and schooling fish, Kennedy and Eberhart ^[11] developed a PSO technique. The particles of this computational technique have two characteristics, velocity, and position. On the basis of these two characteristics personal best and global best positions of particle of PSO are determined. Like PSO, GA ^[12] is one more familiar optimization technique. It is a metaheuristic approach originated by Charles Darwin's theory of "survival of the fittest". This technique refers to the natural election process, in which the most eligible individuals are elected for breeding in order to generate the succeeding generation of offspring. Clustering is a process where a group of data is assigned into smaller groups while considering that the objects in the same groups are more familiar than those in other groups. It is a heuristic approach, used to identify groups of similar objects in datasets with two or more variable quantities. It can be classified into two types viz. soft clustering and hard clustering. K-means clustering technique is a popular hard clustering technique where k determines how many predetermined clusters must be formed during the procedure. The task is an event which dictates the course of action and when task occurs, processing and responding done by the system accordingly. Periodic tasks, aperiodic tasks and sporadic tasks are the three categories of tasks. In a distributed environment, task assignment system is one of the elemental and exacting problems. This system plays a key role in using the resources efficiently in an economic way. Actually, allotment of tasks onto proper processors is the arrangement of tasks in such manner that several efficient constraints like system cost (CS), system reliability (RS), response time (RT) etc. are optimized. There are essentially several algorithms to achieve optimization; these algorithms are categorized into two types: dynamic and static priority algorithms. In dynamic priority model, the preference changes dynamically while in static priority model preference assigned to static nature. This article focuses on static prioritization. The solution for the task allotment issue is given by various researchers in their articles by using different techniques. Some of them evolved well organized task scheduling algorithms using heuristic approaches and meta heuristic approaches. The detail study of various techniques that are used to solve the assignment issues have shown in the Table 1.

Table 1. Study of research articles generated by various authors.

S. No.	Researchers	Core technique	Highlights	Evaluation criteria	Nature of scheduling
1	Wu et al. ^[13]	Clustering approach	Market- situated hierarchical allocation policy in cloud workflow systems	Makespan, Cost, CPU time, cloud computing, workflow scheduling,	Static
2	Naderam et al. ^[14]	Heuristic approach	Heuristic approach on the basis of matching	Clustering, task assignment, Lagrangian relaxation,	Dynamic
3	Wang et al. ^[15]	Clustering approach	Developed a model to abate energy utilization of tasks execution	Green computing, cluster computing, schedule	Static
4	Tripathy et al. ^[16]	Directed search optimization	Three novel algorithms, for scheduling, were presented	Assignment, Cost, Service, neural network, makespan	Dynamic
5	Xiao et al. ^[17]	Hybrid fog computing/SDN VANET	Task allocation method to improve reliability within delay constraint	Reliability, node processing capacity, communication bandwidth	Static
6	Neamatollahi et al. ^[18]	HCSP clustering	To reduce the clustering energy value proposed HCSP algorithm	Network lifetime, cluster, energy, wireless sensor network, cost	Static
7	Kumar et al. ^[19]	k-means clustering method	Allocation method to optimize the cost and reliability	Reliability, execution cost, time, cluster	Static
8	Dao et al. ^[20]	Bat algorithm	BA is subjected to parallel processing, and a PBA communication approach is suggested to address JSSP	Makespan, flowtime, tardiness, weighted earliness	Dynamic
9	Kumar and Tyagi ^[21]	Clustering approach	k-means and fuzzy c-means algorithms were taken	Communication cost, execution cost, time	Static
10	Heidari et al. ^[22]	HHO	Developed the Harris Hawks Optimizer, a unique optimization method inspired by nature	Optimization, scalability	-
11	Alkhateeb and Abed-alguni ^[23]	Hybrid CS-SA	Developed a hybrid model combining CS and SA to enhance the results produced by CS.	Standard deviation, benchmark functions	Dynamic
12	Tirkolaee et al. ^[24]	Hybrid SAAFSA	Authors presented a high-performance decision-making for FSS issues in line with total cost and energy consumption reduction to enhance the productivity	Completion time, cost, energy consumption, sensitivity analysis	Static
13	Kanemitsu et al. ^[25]	Clustering approach	An algorithm was proposed to minimize the schedule length of heterogeneous processors	Efficiency, SLR, CCR	Static
14	Mishra and Majhi ^[26]	Bird swarm optimization	Introduced a load balancing technique that distributes loads among virtual machines fairly	Load balancing, makespan, task scheduling	Dynamic
15	Alawad and Abed-alguni ^[27]	DJaya	To solve the PFSSP, suggested a novel approach called Discrete Jaya with Refraction Learning	Reliability, makespan, ARD	Dynamic
16	Haris and Zubair ^[28]	MMHHO	A new, effective hybrid optimization technique called MMHHO was designed to enhance load balancing in the cloud network	Cost, response time, load balancing	Dynamic

| Show Table

DownLoad: CSV

The meta heuristic techniques GA and PSO are based on the principles of biological evolution and swarms, respectively. These algorithms have been applied to address optimization problems across various domains, such as remote monitoring systems, energy-storage optimization, industrial engineering, and more. There have been numerous attempts to use these metaheuristic algorithms to solve a tasks allocation problem under various assumptions and limitations. Such as, in ^[29], the authors proposed a hybrid PSOGA model to enhance task scheduling in cloud computing, utilizing GA to refine solutions within PSO through genetic operations. However, a significant drawback of this approach was that GA tends to be slow and computationally intensive, due to the evaluation of many functions and the slow convergence of its operators. Unlike PSOGA, which relies on single-point crossover, the proposed method employs novel crossover and mutation techniques, to ensure a more diverse set of offspring. Additionally, a dynamic inertia weight balances local and global search components of PSO. This approach synergizes PSO and GA strengths, achieving faster convergence and superior optimization results. Table 2 includes an overview of some task scheduling approaches that comprise PSO, GA, and hybridization of these with other meta-heuristic or heuristic techniques, along with a list of all the salient characteristics.

Table 2. Study of research publications authored by various researchers using PSO and GA.

S. No.	Researchers	Core technique	Highlights	Evaluation criteria	Nature of scheduling
1	Agarwal and Srivastava ^[29]	PSOGA	Makespan time was considered	Makespan, PIR	Static
2	Kang et al. ^[30]	Hybrid PSO	Approached an assignment algorithm on heterogeneous distributed environment	Task schedules, execution time, CER, DWR	Static
3	Samal et al. ^[31]	GA	GA based assignment result in multiprocessor environment	Fault-tolerance, scheduling, primary- backup	Static
4	Raju et al. ^[32]	PSO	Optimized tasks allocation strategy to reduce execution time	Deadline violation, resource allocation, waiting time, turnaround time	Static
5	Mutingi and Mbohwa ^[33]	GA	An approach to tackle the complications of supplier selection from a vaguely multi-criteria perspective	Price, lead time, quality	Static
6	Zhou et al. ^[34]	PSO	Modified PSO to control the local optimum	Inertia weight, cloud computing, CPU time, memory, allocation	Dynamic
7	Luan et al. ^[35]	Hybrid GA and ACO	Demonstrated a hybrid model to solve supplier selection issue	Supplier election, fitness value	Static
8	Tang et al. ^[36]	GA-ACO	The GAPACO algorithm was designed to save time and cost	Makespan, execution time, cost	Static
9	Mapetu et al. ^[37]	PSO	PSO based technique for load balancing	Makespan, time	Static
10	Kumar et al. ^[38]	Hybrid GA	Scheduling of tasks based on hybrid model	Scheduling, execution cost, time	Static
11	Kumar and Tyagi ^[39]	Hybrid GA, B&B	Hybrid model to reduce the system cost and time	Assignment, cost, communication time, reliability	Static
12	Devi and Garg ^[40]	Hybrid PSO	A hybrid model was developed to address the problem of redundant allocation	CPU time, reliability,	Static
13	Agarwal and Srivastava ^[41]	OPSO	To evade premature convergence, combined opposition-based learning technique with PSO	Makespan, scheduling, opposite number, PIR	Dynamic
14	Zhang et al. ^[42]	Hybrid GA	To resolve the QAP, the hybrid algorithm EGATS was devised.	CPU time, reliability,	Static
15	Chauhan et al. ^[43]	Hybrid GA	An approach to maximize the reliability of the system	Reliability, system time, execution cost	Static
16	Amirteimoori et al. ^[44]	PSO-GA	To simultaneously schedule tasks and transporters in a flow shop system, a MILP model was proposed.	Efficiency, time	Dynamic
17	Karishma and Kumar ^[45]	PSO	Authors developed a model to optimize flowtime, cost and time	Cost, Execution time, Flowtime	Static
18	Proposed technique	HPSOGAK	Algorithms based on PSO-GA are discussed to improve the system's reliability and reduce response time and cost.	Response time, cost, reliability, efficiency, resource utilization	Static

| Show Table

DownLoad: CSV

Here, we are going to discuss some of the works done by the authors aimed at maximizing reliability without repetition. Reliability, a crucial factor to raise the system's performance, is used for examining fault-tolerant designs under significant unpredictability. If the program is carefully allocated to suitable processors, while considering the probability of failure for both communication lines and processors, a distributed system can achieve enhanced reliability in executing a program. Processor outages and communication errors have an impact on system reliability and user service quality. To raise the distributed system's reliability, Attiya and Hamam ^[46] approached a simulated annealing model in a heterogeneous environment and compared it to the B&B technique. Minghua et al. ^[47] came up with a model which gives the approximation for the upper and lower boundary of RAND 5 with a single run of the model. Authors Kang et al. ^[48] suggested HBMO algorithm, the power combination of simulated annealing and GA, to increase the distributed system's reliability. Other than these researchers Donight et al. ^[49] determined a novel method for fuzzy reliability that uses the beta type distribution as the membership function. In intelligent transportation systems, Noori and Jenab ^[50] established a model for rail vehicles with speed sensors on the basis of fuzzy reliability. Authors addressed a clustering based mathematical approach to get system's optimal reliability and cost by assigning tasks to the processors ^[19].

Although the use of a multiprocessor was expected to offer suitable solutions for the problem of task scheduling in DRTS, doing so caused several challenges. When a failure occurs in DRTS, we expect it to be noticed right away, and the distributed operation reverts to the previous checkpoint it had reached. Due to some such failures in system, uncertain results can be obtained. To rescue from this some authors had been dealing with the algorithms for the vague computation in which some of them got their best result and some got failed. Table 3 describes work of such authors with their drawbacks.

Table 3. The summary of existing literature regarding to their drawbacks.

S. No.	Literature	Existing environment	Drawback of existing environment
1	Cederholm and Petterson ^[51]	The goal of this study was to develop an algorithm for scheduling a collection of tasks in a multiprocessor environment	This research did not provide an outlook as per increasing the number of processors and the size of system
2	Jie et al. ^[52]	The authors focused on fixed and hard real-time scheduling in uniprocessor and multiprocessor systems	This work did not provide a distributed, soft real-time, dynamic, or heterogeneous assignment algorithm
3	Singh et al. ^[3]	Authors work presented a basic viewpoint on model PDS, CDS and RMA. This study had provided a tool that is created using the C programming language to accomplish job scheduling and energy consumption	This study did not include any suggestions for dealing with the genuine deadline or other assignment techniques
4	Li and Cheng ^[53]	This study had proposed a strategy for dealing with the few classes of real-time allotment problem and many optional ways in light of the RRP model, as well as achieving task scheduling transparency on the basis of conventional partitions	The transformation methods for the following aspects were not provided in this work. Non-preemptive policies, soft real-time policies, and dynamic job priorities
5	Narale and Butey ^[54]	Through the use of the Throttled load balancing technique, this study suggested a method to decrease data centre processing time and transfer cost	If the number of VMs rises, the response time and cost would as well
6	Adhikari et al. ^[55]	To achieve the best resource clustering, a load balancing technique that relies on the Bat-algorithm had been presented. Reduced degree of unbalance, better load balancing, and minimize makespan and cost	Homogeneous environment, lower scalability, unique task
7	Li and Wu ^[56]	To minimize task execution time and enhance system resource utilization, an ACO-based algorithm was developed. Maximize load balancing, maximal scalability	The presented technique was less reliable, having a longer response time and lower quality of service
8	Shao et al. ^[57]	The flow-shop scheduling problem (DBFSP) was examined in this article in order to reduce the maximum completion time	RPD and makespan performance could be improved
9	Hosseinioun et al. ^[58]	In this work, a method for conserving energy was introduced using the DVFS approach	The static energy was not taken into account in this model
10	Negi et al. ^[59]	The suggested PLB model takes into account makespan time, task starvation, multi-queuing model, resource mapping, and optimum performance	It did not take into account reallocating resources in a dynamic environment
11	Princess and Radhamani ^[60]	With an efficiency of 97%, hybrid Harris Hawk optimizing technique was developed	It did not offer a better degree of imbalance

| Show Table

DownLoad: CSV

3. Definitions and terminology

Appropriate task arranging onto relevant processors can enhance reliability of the system. Various performance specifications impact scheduling strategies. The ${\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{e} _{i, k}}$ , where $1 \leqslant i \leqslant r, \; 1 \leqslant k \leqslant m$ , is determined by the task's efficiency and the processor's attributes. If tasks ${t_i}{\text{ and }}{t_j}$ are on separate processors, ${\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{c} _{i, j}}$ symbolizes the fuzzy communication time between them. Under this report, it is assumed that data exist about ${\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{e} _{i, k}}$ and ${\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{c} _{i, j}}$ times, and these times are demonstrated as $F{E_T}M$ and $FIT{C_T}M$ in the form of matrix respectively and by the process of defuzzification $F{E_T}M$ and $FIT{C_T}M$ are renewed into crisp matrix.

3.1. Defuzzification

Robust's ranking approach has been used in this present work to defuzzify the $F{E_T}$ and $FIT{C_T}$ . If $\left({a_\alpha ^L, a_\alpha ^U} \right)$ represents the $\alpha$ -cut for fuzzy (triangular/trapezoidal) communication/execution time, then the defuzzification is performed as:

${e_{i, k}} = \;R\left( {{{\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{e} }_{i, k}}} \right){\text{ = }}\frac{{\text{1}}}{{\text{2}}}\int\limits_0^1 {\left( {a_\alpha ^L, a_\alpha ^U} \right)} d\alpha$

${c_{i, j}} = \;R\left( {{{\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{c} }_{i, j}}} \right){\text{ = }}\frac{{\text{1}}}{{\text{2}}}\int\limits_0^1 {\left( {a_\alpha ^L, a_\alpha ^U} \right)} d\alpha .$

(1)

After defuzzification, crisp values of communication time are stored in $IT{C_T}M = \left[{{c_{i, j}}} \right]$ matrix and values of execution time are stored in ${E_T}M = \left[{{e_{i, k}}} \right]$ matrix.

Moreover, the following are some key terms that will be used all across the article:

3.2. Communication time (C_T)

If the tasks are on multiple processors, then the total amount of time which needed to transmit data among tasks ${t_i}$ and ${t_j}$ is known as communication time. $TIT{C_T}$ may be prescribed as:

$TIT{C_T}=\sum\limits_{i, j = 1}^r {\sum\limits_{\substack{k=1 \\ k \neq l}}^m {\left( {{d_{k, l}} \cdot {{\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{c} }_{i, j}}} \right)} } \cdot {x_{j, l}} \cdot {x_{i, k}} ,$

(2)

where, the inter-processor distance ${d_{k, l}}$ represents the communication time per unit of data transferred between processor ${p_k}$ and processor ${p_l}$ . In scenarios where tasks ${t_i}$ and ${t_j}$ are assigned to different processors, the communication time is calculated as $\left({{d_{k, l}} \cdot {{\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{c} }_{i, j}}} \right)$ , where ${d_{k, l}}$ = 0 if k = l ^[39]. Therefore, under this approximation, the communication time for tasks on different processors corresponds directly to the amount of data exchanged between them.

3.3. Execution time (E_T)

The execution time is the time of executing so every task ${t_i}$ on processor ${p_k}$ . Total execution time $\left({T{E_T}} \right)$ is calculated as:

$T{E_T}{\text{ = }}\sum\limits_{i = 1}^r {{x_{i, k}}} \cdot {\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{e} _{i, k}} .$

(3)

3.4. System cost (CS)

In terms of time units, cost of the system is the total sum of execution and communication times. It can be determined as:

$CS\; = \;\sum\limits_{i, j = 1}^r {\sum\limits_{\substack{k=1 \\ k \neq l}}^m {\left( {{d_{k, l}} \cdot {{\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{c} }_{i, j}}} \right)} } \cdot {x_{j, l}} \cdot {x_{i, k}} + \;\sum\limits_{i = 1}^r {\sum\limits_{k = 1}^m {{x_{i, k}} \cdot {{\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{e} }_{i, k}}} } .$

(4)

3.5. Response time (RT)

The amount of computation to be performed by each processor determines the RT. Response time is inversely proportional to stability of the system. It can be calculated by using the following:

$RT\; = \mathop {\max }\limits_{1 \leqslant k \leqslant m} \left\{ {\sum\limits_{i, j = 1}^r {\sum\limits_{\substack{k=1 \\ k \neq l}}^m {\left( {{d_{k, l}} \cdot {{\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{c} }_{i, j}}} \right)} } \cdot {x_{j, l}} \cdot {x_{i, k}} + \;\sum\limits_{i = 1}^r {{x_{i, k}}} \cdot {{\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{e} }_{i, k}}} \right\} .$

(5)

3.6. System reliability (RS)

The probability that each engaged component will be operational during the execution process is referred to as RS. The stability of a system is improved by having a reliable system. The following equation is used to determine the RS:

$RS\; = \;\left[ {\prod\limits_{k = 1}^m {{R_k}} } \right] \cdot \left[ {\prod\limits_{\substack{k=1 \\ k \neq l}}^m {{R_{k, l}}} } \right] ,$

(6)

where ${R_k}$ and ${R_{k, l}}$ are the processor ${p_k}$ reliability and the kl link reliability, respectively. In a given time interval, let's call it t, processor ${p_k}$ reliability pursues a Poisson distribution,

${R_k}{\text{ = }}{e^{ - \int_0^t {{\lambda _k}\left( t \right)dt} }}$

where ${\lambda _k}$ remains constant all across the procedure. In terms of ${E_T}$ , in which task ${t_i}$ is assigned to ${p_k}$ processor, reliability of ${p_k}$ can be computed as

${R_k}{\text{ = }}{e^{ - {\lambda _k} \cdot \sum\limits_{i = 1}^r {{x_{i, k}} \cdot {{\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{e} }_{i, k}}} }} .$

Correspondingly, in a specified interval of time t, the reliability of the kl path is ${e^{ - {\mu _{k, l}}t}}$ and in terms of communication time the reliability between kl paths is given by

${R_{k, l}}{\text{ = }}{e^{ - {\mu _{k, l}} \cdot \sum\limits_{i, j = 1}^r {\sum\limits_{\substack{k=1 \\ k \neq l}}^m {\;\left( {{d_{k, l}} \cdot {{\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{c} }_{i, j}}} \right) \cdot {x_{j, l}} \cdot {x_{i, k}}} } }} .$

3.7. Performance improvement ratio (PIR%)

Term PIR refers to the ability of a suggested algorithm, determined by the decrease in execution time. It is one of the essential parameters that ascertain the effectiveness of the proposed algorithm. It can be computed as per Eq (7), as follows:

$PIR\;\% = \;\frac{{R{T_i} - R{T_{proposed}}}}{{R{T_i}}} \times 100 ,$

(7)

where $R{T_{proposed}}$ and $R{T_i}$ represent the obtained RT for the proposed and ${i^{th}}$ algorithm, respectively.

4. Model of tasks allocation problem

DRTS comprises a diverse set of heterogeneous processing units interconnected via advanced networks. These processing units and communication networks may possess different resource capabilities and varying levels of bandwidth utilization. This model can perform all functions simultaneously and communicate at any point during the program's execution. The following assumptions are employed to generate a model for solving the task allocation problem.

● In a real time structure, for every processor has a varying processing capability.

● On various processors, a task's execution time may vary.

● The allocated task persists on the processor while the program is executing.

● RS, RT, and CS are determined by the times of communication and execution.

● Heterogeneous processors are used in this DRTS paradigm. Consequently, the processors may be restricted by different memory and compute units and they have varying failure rates and processing times. Additionally, the communication links' failure rates may vary.

● While executing, a module consumes a certain amount of its designated processor's compute resources. It is possible for two modules that are running on different processors to communicate and incur a certain amount of intermodule communication time in terms of data quantity.

In this article, task allocation issue is preferred and timing-constrained tasks are placed on processors in a way that optimises RS, CS and RT under the following conditions:

● In DRTS all the tasks are non-preemptive.

● In a certain amount of time each and every processor execute single task.

The object of the task assignment problem in DRTS, where ${E_T}M$ and $IT{C_T}M$ are assumed to be given, is to minimize the RT and maximize the RS. The task allocation problem addressed with system resource constraints is as follows:

$\min RT\; = \mathop {\max }\limits_{1 \leqslant k \leqslant m} \left\{ {\sum\limits_{i, j = 1}^r {\sum\limits_{\substack{k=1 \\ k \neq l}}^m {\left( {{d_{k, l}} \cdot {{\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{c} }_{i, j}}} \right)} } \cdot {x_{j, l}} \cdot {x_{i, k}} + \;\sum\limits_{i = 1}^r {{x_{i, k}}} \cdot {{\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{e} }_{i, k}}} \right\} .$

Such that,

$\sum\limits_{l = 1}^m {{x_{j, l}}} = 1\;\forall j,$

(8)

${x_{j, l}} \in \left\{ {0, 1} \right\}\forall j, l .$

(9)

Each and every module must be allotted to precisely single processor, according to constraint (8) and ${x_{j, l}}$ must be binary variables, according to constraint (9). With a quadratic objective function, the aforementioned formulation is an NP-hard 0–1 programming problem.

5. The proposed method

This section elucidates the developed method for addressing the task scheduling problem, aiming to minimize CS and RT while maximizing RS. This paper introduces a novel scheduling method developed through the integration of a PSO-based swarm technique with GA and k-means techniques. In recent decades, GA and PSO have been widely utilized in a number of scientific domains. The study of computing systems motivated by collective intelligence is known as swarm intelligence. Large numbers of homogeneous agents in the environment work together to form collective intelligence. That includes the examples of flocks of birds, fish schooling, and ant colonies. Swarm intelligence can be used to find the best solutions for the issues like task scheduling. PSO is used in this paper because it is the best strategy for all size problems. An approximate solution to an optimization or search problem can be found using the GA search approach. Since GA considers all potential solutions, it takes longer to find a solution to any given problem. The procedure of selecting which task should be carried out at each moment in time is called task scheduling. The assignment algorithm prioritizes each active task at runtime and allots the highest priority task to the processor. In the present study task-clusters are formed using hybrid particle swarm optimization genetic algorithm k-means (HPSOGAK) and their assignment onto appropriate processor is done by using genetic algorithm. The main drawback of the traditional PSO algorithm is to establish a balance between local and global search, which leads to local best or optima in large number of optimization issues. Additionally, the standard PSO algorithm suffers from slow convergence rates, rendering it unsuitable for directly addressing assignment problems. Numerous attempts have been made to mitigate these issues, as detailed in Section 2. As an illustration, the approach in ^[30], devised a hybrid PSO-based method for task scheduling in heterogeneous systems, faced restrictions on operators' actions, potentially made parts of the search space unreachable. The motivation behind developing the proposed HPSOGAK approach is to overcome the drawbacks and limitations associated with the standard PSO algorithm. This work combines PSO and GA techniques to enhance the capabilities of conventional PSO, with the goal of effectively tackling the crucial task scheduling problem in heterogeneous computing systems. By combining the exploration capabilities of PSO with the refinement strengths of GA, the proposed hybrid method effectively balances the search process, leading to improved optimization results. Even though, using only genetic operators to determine the optimal solution is difficult. Therefore, the convergence rate of GA is improved by providing new population initialization, encoding and genetic operations. This article introduces new crossover and mutation techniques that help GA function better. In addition to initializing particles with HPSOGAK, a global-local best inertia weight is used to balance the local and global search components of the standard PSO algorithm. In the hybrid HPSOGAK algorithm, k-means clustering technique is implemented to produce a finite number of task-clusters as the conception of k-means is quite straightforward and comfortable to accomplish. The fundamental disadvantage of the k-means clustering method is that it may produce vacant clusters. Hence, PSO-GA approach is employed to address this shortcoming. After using the PSO-GA approach, non-empty clusters of tasks are obtained within a low number of iterations of k-means. Now, the fundamental characteristics of PSO and GA are as follows.

5.1. Particle swarm optimization

In an effort to address issues related to optimization, Kennedy and Eberhart ^[11] introduced the basic version of PSO. It is a meta-heuristic optimizing technique that draws inspiration from animal social behavior and information-sharing strategies, such as that of soaring birds and fish schooling. A particle swarm is a gathering of particles that can all move around in the problem space and be drawn to advantageous locations. Each and every particle of PSO in a population has two characteristics, velocity and position. On the basis of these two factors all the particles look for their food in that available search space. Influenced by the natural phenomena of schooling and flocking, PSO particles are distinguished not only by their position but also by a velocity that allows them to move within the search space. Each and every particle in PSO represents a location in the specified search space and a potential answer to the problem. Its goal is to optimize the problem-dependent fitness function, a function that provides each particle of the population a specific value demonstrating the superiority of the g best and p best in the solution. Centroids of task-clusters are represented as swarm particles in the present article, and the following Eq (10) can be used to get the fitness value for each particle.

${g_{Cd}} = \max \left( {\frac{1}{{1 + \sum\limits_{i = 1}^r {\left( {\sum\limits_{j = 1}^r {{{\left( {\left\| {c_{i, j}^{\hat n} - c{d_{k, j}}} \right\|} \right)}^2}} } \right)} }}} \right), {\text{ }}k = 1, 2, ...m$

(10)

where, $\left({c_{i, j}^{\hat n}} \right)$ represents the element of the matrix $NIT{C_T}M$ and for the centroid of the ${k^{th}}$ cluster $C{d_k}$ ; $C{d_k} = \left({c{d_{k, 1}}, c{d_{k, 2}}, ..., c{d_{k, r}}} \right)$ .

In the search space each particle's position is influenced by both its best position (p best) and the position of the next best particle (g best). All the particles migrate to the ideal solution, updating their p best and g best results. All of these particles have now reached their destination in the best possible manner. Each bird in this process is viewed as a distinct particle. Therefore, each and every particle has its own position and velocity. PSO is an iterative procedure in which each particle modifies its position and velocity in accordance with its prior experience as well as that of its neighbors. Determine the p best and g best for upgrading every particle's velocity and position i.e., cluster centroids based on its fitness values by the Eqs (11) and (12) respectively.

${V_k}\left( {t + 1} \right) = \omega \times {V_k}\left( t \right) + {\eta _1} \times {\phi _1} \times \left( {{P_k}\left( t \right) - C{d_k}\left( t \right)} \right) + {\eta _2} \times {\phi _2} \times \left( {{G_k}\left( t \right) - C{d_k}\left( t \right)} \right)$

(11)

where, $\omega$ stands for the inertia weight and the values of cognitive constant ${\eta _1}$ and social constant ${\eta _2}$ typically fall between [0, 2]. ${\phi _1}$ , ${\phi _2}$ are two random numbers, have values in the range from [0, 1]. The inertia component is the first, cognitive component is the second, and social component is the third component in the velocity upgrade calculation in Eq (11). Here, an algorithm's two successive iterations are represented by (t) and (t+1).

$C{d_k}\left( {t + 1} \right) = C{d_k}\left( t \right) + {V_k}\left( {t + 1} \right) .$

(12)

The three components that make up the velocity vector, which controls how a particle moves through a given search space, are as follows: momentum, also known as inertia, keeps a particle from abruptly changing direction; cognitive component, that is accountable for the trend to return the particles to their previous foremost position; and social component, which assists a particle in moving through the swarm's best position. These factors influence how the velocity of the ${k^{th}}$ particle updates according to Eq (11). The iterative procedure described in Eqs (11) and (12) will continue until the halting condition is satisfied.

The graphic depiction of the PSO is shown in Figure 1. The particle changes direction with each iteration, and often, the new path is optimal. This decision is based on both the individual's personal best position and the global best position.

Figure 1. Graphical presentation of PSO.

Input:	Select two distinct parents ${A^{\left(t \right)}}$ and ${B^{\left(t \right)}}$ of dimension m from parent pool
Output:	Two distinct offspring ${C^{\left({t + 1} \right)}}$ and ${D^{\left({t + 1} \right)}}$
	# Create offspring ${C^{\left({t + 1} \right)}}$ and ${D^{\left({t + 1} \right)}}$ respectively as follows:
	# For offspring ${C^{\left({t + 1} \right)}}$ , ${C^{\left({t + 1} \right)}}$ = Reverse $\left({\mathop C\nolimits^{'\left({t + 1} \right)} } \right)$
1:	While $\left({k \leqslant m} \right)$
2:	{
3:		if (k = =1)
4:		{
5:				$C_1^{'\left({t + 1} \right)} = = B_1^t$
6:		}
7:		if $\left({1 < k \leqslant m} \right)$
8:		{
9:				$x_k^t$ = (image ( $C_{^{k - 1}}^{'(t + 1)}$ )) IN ${B^{\left(t \right)}}$
10:				$y_k^t$ = (image ( $x_k^t$ )) IN ${A^{\left(t \right)}}$
11:				if (( $y_k^t$ IN ${C^{'\left({t + 1} \right)}}$ ) = True)
12:				{
13:						$C_{^k}^{'(t + 1)}$ = min $\left({{B^{\left(t \right)}} - {C^{'\left({t + 1} \right)}}} \right)$
14:				}
15:				else
16:				{
17:						$C_{^k}^{'(t + 1)}$ = $y_k^t$
18:				}
19:			}
20:	}
21:	${C^{\left({t + 1} \right)}}$ = Reverse $\left({{C^{'\left({t + 1} \right)}}} \right)$
22:	# For offspring ${D^{\left({t + 1} \right)}}$
23:	While $\left({k \leqslant m} \right)$ do
24:	{
25:				if (k = 1)
26:				{
27:							$D_1^{\left({t + 1} \right)} = = A_1^t$
28:				}
29:				if $\left({1 < k \leqslant m} \right)$
30:				{
31:								$w_k^t$ = (image ( $D_{^{k - 1}}^{(t + 1)}$ )) IN ${A^{\left(t \right)}}$
31:								$v_k^t$ = (image ( $w_k^t$ )) IN ${B^{\left(t \right)}}$
32:								if (( $v_k^t$ IN ${D^{\left({t + 1} \right)}}$ ) = True)
33:								{
34:									$D_{^k}^{(t + 1)}$ = min $\left({{A^{\left(t \right)}} - {D^{\left({t + 1} \right)}}} \right)$
35:								}
36:								else
37:								{
38:									$D_{^k}^{(t + 1)}$ = $v_k^t$
39:								}
40:							}
41:					}

Input:	Select an offspring chromosome ${C^{\left({t + 1} \right)}}$ of dimension m
Output:	A mutated offspring ${E^{\left({t + 1} \right)}}$
	# Create mutated offspring ${E^{\left({t + 1} \right)}}$ as follows:
1:	Select two random cut-points over ${C^{\left({t + 1} \right)}}$ say, cut-point1 and cut-point2 respectively
2:	$x = {C^{\left({t + 1} \right)}}$ (cut-point1 to cut-point2)
3:	$x'$ = Shuffle $\left({x'} \right)$
4:	Place $x'$ in ${C^{\left({t + 1} \right)}}$ between cut-point1 and cut-point2
5:	While ( $k \leqslant m$ )
6:	{
7:	if (k = =1)
8:	{
9:		$E_1^{\prime(t+1)}=\min \left(x^{\prime}\right)$
10:	}
11:	if $\left({1 < k \leqslant m} \right)$
12:	{
13:		$y^{\prime(t+1)}=\left(\operatorname{image}\left(E_{k-1}^{'(t+1)}\right)\right) \operatorname{IN}\; C^{(t+1)}$
14:		if (( ${y^{'\left({t + 1} \right)}}$ IN ${E^{'\left({t + 1} \right)}}$ ) = True)
15:		{
16:			$E_k^{'\left({t + 1} \right)}$ = image ( ${y^{'\left({t + 1} \right)}}$ )
17:		else
18:		{
19:			$E_k^{'\left({t + 1} \right)}$ = ${y^{'\left({t + 1} \right)}}$
20:	}
21:	}
22:	Reshuffle the bits of $E_k^{'\left({t + 1} \right)}$ to their original position from Step 2 to get mutated offspring ${E^{\left({t + 1} \right)}}$

1:		Initialize $r, m, \omega, {\eta _1}, {\eta _2}, {\phi _1}, {\phi _2}, FIT{C_T}M$
2:		Defuzzification of $FIT{C_T}M = \left[{{{\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{c} }_{i, j}}} \right]$ into crisp $IT{C_T}M = \left[{{c_{i, j}}} \right]$ through using Robust's ranking approach
3:				for $0 \leqslant i \leqslant j \leqslant r$ do
4:						{
5:							$NIT{C_T}M = \left[{c_{i, j}^{\hat n}} \right] = \left\{ \begin{array}{l} \mathop {\max }\limits_i \mathop {\max }\limits_j {c_{i, j}} - {c_{i, j}}{\text{, if }}i \ne j \hfill \\ {\text{ 0, otherwise}} \hfill \\ \end{array} \right.$
6:						}
7:				end for
8:		Generate 'm' number of task-clusters of 'r' tasks randomly named as $\left\{ {c{l_1}, c{l_2}, ...c{l_m}} \right\}$
9:				for ${k^{th}}{\text{ cluster }}\left({1 \leqslant k \leqslant m} \right)$ do
10:					{
11:							Calculate the initial $C{d_k}$ for PSO-GA as follows: $C{d_k} = \frac{1}{{{n_k}}}\sum\limits_{i, j = 1}^r {c_{i, j}^{\hat n}.\; {u_{i, k}}}$
12:						}
13:				end for
14:		t = 0
15:		for $\left({1 \leqslant k \leqslant m} \right)$ do
16:						{
17:						Initialize ${V_k}\left(t \right)$ and $C{d_k}\left(t \right)$
18:						${P_k}\left(t \right)$ = $C{d_k}\left(t \right)$
19:						}
20:		end for
21:		Formation of new centroids using PSO-GA technique
22:					if (PSO-GA stopping criteria = false) do
23:					for ${k^{th}}{\text{ particle }}\left({1 \leqslant k \leqslant m} \right)$ do
24:							{
25:									Evaluate the fitness value ${g_{Cd}}$ of each particle by using Eq (10)
26:									Determine the p best for each particle based on its fitness value
27:									Implement the crossover operator to update p best
28:									Implement the mutation operator to update p best
29:									Determine the g best based on its fitness value
30:									Implement the mutation operator to update g best
31:									Update ${V_k}\left({t + 1} \right)$ by using Eq (11)
32:									Update $C{d_k}\left({t + 1} \right)$ by using Eq (12)
33:								}
34:						end for
35:				end if
36:		Assign the centroids obtained in Step 32 as the initial centroids for the k-means algorithm
37:		Repeat
	(a)			for ( $1 \leqslant i \leqslant r\; and\; 1 \leqslant k \leqslant m$ ) do
						{
								Distance ${\hat d_{ik}}$ between task ${t_i}$ and the cluster centre $C{d_k}$ ${\hat d_{ik}}{\text{ = }}\sqrt {\sum\limits_{j = 1}^r {{{\left({c_{i, j}^{\hat n} - c{d_{k, j}}} \right)}^2}} }$
						}
				end for
	(b)	Create new task-clusters by allocating each task to its closest cluster centroid
		# Update novel clusters as follows
	(c)		for $\left({1 \leqslant k \leqslant m} \right)$ do
					{
							$C{d_k} = \frac{1}{{{n_k}}}\sum\limits_{i, j = 1}^r {c_{i, j}^{\hat n}.\; {u_{i, k}}}$
						}
				end for
	(d)	Apply 37 (a), (b) steps and encore the process until the stopping criteria are met
38:		end

1:	Input $F{E_T}M = \left[{{{\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{e} }_{i, k}}} \right]$
2:	Defuzzification of $F{E_T}M = \left[{{{\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{e} }_{i, k}}} \right]$ into crisp ${E_T}M = \left[{{e_{i, k}}} \right]$ through using Robust's ranking approach
3:	Modify ${E_T}M = \left[{{e_{i, k}}} \right]$ into $N{E_T}M = \left[{e_{i, k}^{\hat n}} \right]$ by fusing the rows based on the cluster acquired from Algorithm 3
4:	To produce the initial population, encode 'm' chromosomes
5:	Start
6:		Size of population = m
7:		for k = 1 to size of population 'm'
8:		chromosome $c{h_k}$ = select in random order
9:	end
10:	Through using the following formula, compute the fitness value of each chromosome in the population: ${f_{fet}} = {\text{ 1/}}\left\{ {\varepsilon + \sum\limits_{i = 1}^r {\sum\limits_{k = 1}^m {{x_{i, k}}.\; {{\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{e} }_{i, k}}} } } \right\}$
11:	Assess the probability of each chromosome in the population through using following formula: $P_{rob}^i = \; 1 - \left\{ {\frac{{{f_{fet}}\left({chromosome\_i} \right)}}{{\sum\limits_{i = 1}^m {\left({{f_{fet}}\left({chromosome\_i} \right)} \right)} - {f_{fet}}\left({chromosome\_i} \right) + 1}}} \right\}$
12:	New population to be produced-
13:	For the new population, select the chromosome having high probability
14:	Select the chromosomes with the least probability and apply the proposed crossover operator to them
15:	Implement the proposed mutation operator
16:	If the prerequisites for stopping are met, stop; otherwise go to Step 10
17:	Applying Eqs (4) – (6) to determine CS, RT, and RS respectively.
18:	End

System parameters	Values
Inertia weight $\omega$	0.4–0.9
${\phi _1}\, and\, {\phi _2}$	[0, 1]
${\eta _1}\, and\, {\eta _2}$	1.49
Failure rate of processor, ${\lambda _k}$	[0.0002-0.00012]
Failure rate of kl communicating path, $\, {\mu _{k, l}}$	[0.0005-0.00015]
Maximum iteration of GA	50
Crossover probability	0.8
Mutation probability	0.1
Maximum iteration of PSO	100

Example	Reference	Used Technique	Tasks Assignment	RS	CS	RT	Resource Utilization (%)
1	Djigal et al. ^[63]	List based scheduling algorithm	{t₁, t₂, t₃, t₇}→p₁ {t₄, t₆, t₈, t₁₀}→p₂ {t₅, t₉}→p₃	-	304	181	75.32
	Proposed model	Hybrid PSO	{t₈, t₁₀}→p₁ {t₂, t₅, t₉}→p₃ {t₁, t₃, t₄, t₆, t₇}→p₂	0.98074	275	162	79.39
2	Kumar et al. ^[64]	Heuristic approach	{t₁, t₄}→p₁ {t₅}→p₂ {t₂, t₃}→p₃	0.97096	(145,240,360)	(110,175,250)	68.06
2	Proposed model	Hybrid PSO	{t₁}→p₂ {t₂, t₃, t₅}→p₁ {t₄}→p₃	0.98780	(145,230,320)	(95,165,240)	74.35
3	Sharma et al. ^[65]	Clustering approach	{t₄, t₅}→p₁ {t₂, t₃}→p₂ {t₁}→p₃	0.9956	123	97	77.89
	Proposed model	Hybrid PSO	{t₃, t₄, t₅}→p₂ {t₁}→p₁ {t₂}→p₃	0.9979	81	68	81.34
4	Chauhan et al. ^[43]	Hybrid GA	{t₁, t₈}→p₁ {t₄, t₉}→p₂ {t₂, t₅}→p₃ {t₆, t₇}→p₄ {t₃}→p₅	(0.9349, 0.9506, 0.9693)	(403.8,634.8,965.8)	(32, 53, 78)	51.29
	Proposed model	Hybrid PSO	{t₃}→p₅ {t₄, t₉}→p₂ {t₁, t₈}→p₁ {t₂, t₅}→p₃ {t₆, t₇}→p₄	(0.9349, 0.9506, 0.9693)	(403.8,634.8,965.8)	(32, 53, 78)	51.29

S. No.	References	Size of the model (r, m)	Technique used	By reference technique		By proposed technique
S. No.	References	Size of the model (r, m)	Technique used	CS	RT	CS	RT
1	Dai and Zhang ^[69]	(10, 3)	Heuristic approach	218	147	199	126
2	Yadav et al. ^[70]	(4, 4)	Heuristic approach	29	27	23	21
3	Kumar et al. ^[64]	(5, 3)	Heuristic approach	246.25	177.5	231.25	166.25
4	Attiya and Hamam ^[46]	(6, 4)	Simulated annealing approach	145	51	60	21
5	Sharma et al. ^[65]	(5, 3)	Clustering approach	123	97	81	68
6	Daoud and Kharma ^[71]	(5, 2)	List based scheduling algorithm	36	27	33	18
7	Topcuoglu et al. ^[68]	(10, 3)	List based scheduling algorithm	230	172	203	128
8	Ilavarasan et al. ^[66]	(10, 3)	HPS approach	236	131	203	128
9	Khandelwal ^[72]	(8, 3)	Clustering approach	122	58	76	46
10	Govil and Kumar ^[73]	(10, 4)	Heuristic approach	163	89	154	77
11	Yadav et al. ^[74]	(9, 3)	Heuristic approach	2563.9	1272.6	2475.70	1181.20
12	Kafil and Ahmad ^[75]	(5, 3)	A* technique	65	28	62	28
13	Kumar and Yadav ^[76]	(8, 3)	Heuristic approach	83	54	76	46
14	Lo ^[77]	(4, 3)	Graph theoretic approach	38	30	35	30
15	Kaushal and Kumar ^[78]	(10, 4)	Heuristic approach	400	200	154	77
16	Kumar et al. ^[19]	(9, 3)	Clustering approach	1094	422	963	415
17	Koppiddakis et al. ^[79]	(3, 2)	Heuristic approach	30	24	14	13
18	Shatz et al. ^[61]	(4, 4)	Heuristic approach	33	21	23	21
19	Akbari and Rashidi ^[80]	(8, 3)	Genetic algorithm	170	111	154	88
20	Bittencourt et al. ^[81]	(9, 3)	DAG scheduling	474	347	474	336
21	Daoud and Kharma ^[71]	(11, 2)	List based scheduling algorithm	188.5	142	157	115
22	Kumar et al. ^[38]	(5, 3)	Genetic algorithm	246.25	177.5	231.25	166.25
23	Yadav et al. ^[82]	(9, 3)	Artificial neural network approach	1372	479	963	415
24	Djigal et al. ^[63]	(10, 3)	List based scheduling algorithm	304	181	275	162
25	Kumar and Tyagi ^[21]	(6, 4)	Clustering approach	84	36	60	21
26	Yadav et al. ^[83]	(8, 4)	Clustering approach	83.8	37	80.2	37
27	Ucar et al. ^[84]	(7, 3)	Heuristic approach	270	195	270	185
28	Kumar and Tyagi ^[39]	(5, 3)	Hybrid Genetic algorithm	246.25	177.5	231.25	166.25
29	Gupta and Yadav ^[85]	(9, 3)	Heuristic approach	2525	1221.9	2475.70	1181.20
30	Elsadek and Wells ^[86]	(9, 3)	Heuristic approach	1372	479	963	415

Size of the model (r, m)	B&B	GA	Clustering approach	GA-B&B	Proposed approach
(6, 4)	39.21	58.82	29.41	58.82	58.82
(10, 3)	11.56	18.16	10.20	8.16	14.28
(4, 4)	9.52	10.52	19.04	9.52	0
(9, 3)	11.69	11.89	11.27	11.69	13.36
(8, 3)	18.91	29.72	16.76	19.81	20.72
(11, 2)	1.16	4.92	2.81	1.16	19.01
(9, 3)	11.52	10.52	11.10	11.11	13.53
(10, 3)	23.46	30.81	24.41	24.41	25.58
(8, 4)	0	5.40	0	16.21	18.91
(10, 4)	62.5	70.45	67.23	67.5	61.50
(5, 3)	1.97	2.98	4.61	2.98	6.33
(7, 3)	2.05	4.87	1.02	0	5.12
(3, 2)	41.66	40.83	25	41.66	45.83
(9, 3)	2.97	3.33	2.97	3.33	3.33
(5, 2)	4.81	0	29.62	22.22	33.33

S. No.	Algorithms	Tasks	Processors	RS	CS
1	Topcuoglu et al. ^[68]	{t₃, t₇}	${p}_{1}$	0.9614	230
		{t₄, t₆, t₈}	${p}_{3}$
		{t₁, t₂, t₅, t₉, t₁₀}	${p}_{2}$
2	Kumar et al. ^[19]	{t₃, t₇, t₁₀}	${p}_{1}$	0.9629	224
		{t₄, t₈, t₉}	${p}_{2}$
		{t₁, t₂, t₅, t₆}	${p}_{3}$
3	Chauhan et al. ^[43]	{t₃, t₇, t₁₀}	${p}_{1}$	0.9629	224
		{t₄, t₈, t₉}	${p}_{2}$
		{t₁, t₂, t₅, t₆}	${p}_{3}$
4	Ilavarasan et al. ^[66]	{t₃, t₇, t₈}	${p}_{1}$	-	236
		{t₁, t₂, t₆}	${p}_{3}$
		{t₄, t₅, t₉, t₁₀}	${p}_{2}$
5	Kumar and Tyagi ^[39]	{t₄, t₈, t₉}	${p}_{2}$	0.9629	224
		{t₃, t₇, t₁₀}	${p}_{1}$
		{t₁, t₂, t₅, t₆}	${p}_{3}$
6	Proposed algorithm	{t₃, t₇, t₁₀} {t₂, t₄, t₈, t₉} {t₁, t₅, t₆}	${p}_{2}$ ${p}_{1}$ ${p}_{3}$	0.9840	203

S. No.	Tasks & Processors	GA			PSO-GA
S. No.	Tasks & Processors	RT	Efficiency	Utilization (%)	RT	Efficiency	Utilization (%)
1	(9, 3)	422	0.7867	81.37	415	0.8001	83.69
2	(6, 4)	21	0.7976	78.66	21	0.7976	78.66
3	(4, 3)	65	0.5246	-	30	0.6105	67.31
4	(6, 4)	34	0.6126	52.94	21	0.7976	78.66
5	(9, 3)	120	0.5629	-	118	0.5801	61.13
6	(8, 4)	37	0.7901	-	37	0.7901	78.38
7	(9, 3)	1181.2	0.6183	-	1181.20	0.6183	69.23
8	(4, 3)	19	0.6140	63.25	19	0.6140	63.25
9	(5, 2)	86	0.3139	-	18	0.7502	79.33
10	(10, 4)	85	0.5973	-	77	0.6421	71.77
11	(7, 3)	195	0.4708	-	185	0.5954	63.13
12	(10, 4)	65	0.7803	-	58	0.7992	81.02
13	(10, 3)	130	0.5385	55.38	128	0.5891	78.41
14	(8, 3)	78	0.7629	77.38	78	0.7629	77.38
15	(5, 3)	177.5	0.7102	-	166.25	0.7732	81.79

S. No.	Problem's size	Ranks of the algorithms
S. No.	Problem's size	B&B	GA	Clustering approach	GA-B&B	Proposed technique
1	$6 \times 4$	4	2	5	2	2
2	$10 \times 3$	3	1	4	5	2
3	$4 \times 4$	3.5	2	1	3.5	5
4	$9 \times 3$	3.5	2	5	3.5	1
5	$8 \times 3$	4	1	5	3	2
6	$11 \times 2$	4.5	2	3	4.5	1
7	$9 \times 3$	2	5	4	3	1
8	$10 \times 3$	5	1	3.5	3.5	2
9	$8 \times 4$	4.5	3	4.5	2	1
10	$10 \times 4$	4	1	3	2	5
11	$5 \times 3$	5	3.5	2	3.5	1
12	$7 \times 3$	3	2	4	5	1
13	$3 \times 2$	2.5	4	5	2.5	1
14	$9 \times 3$	3.5	2	3.5	2	2
15	$5 \times 2$	4	5	2	3	1
Sum of ranks		56	36.5	54.5	48	28
Sum of ranks squared		3136	1332.25	2970.25	2304	784
Average of ranks		3.73	2.43	3.63	3.2	1.86

Mathematics in Engineering

A novel hybrid model for task scheduling based on particle swarm optimization and genetic algorithms

Related Papers:

Abstract

Abbreviations:

1. Introduction

2. Related work

3. Definitions and terminology

3.1. Defuzzification

3.2. Communication time (CT)

3.3. Execution time (ET)

3.4. System cost (CS)

3.5. Response time (RT)

3.6. System reliability (RS)

3.7. Performance improvement ratio (PIR%)

4. Model of tasks allocation problem

5. The proposed method

5.1. Particle swarm optimization

5.2. Genetic algorithm

5.2.1. Evolution of an initial population

5.2.2. Fitness function

5.2.3. Selection

5.2.4. Crossover

5.2.5. Mutation

5.3. Stopping criteria

5.4. Developed algorithms

5.4.1. Phase Ⅰ

5.4.2. Phase Ⅱ

5.5. Performance parameter

6. Performance assessment

7. Comparison

7.1. Scenario 1

7.2. Scenario 2

7.3. Scenario 3

7.4. Scenario 4

7.5. Scenario 5

8. Conclusions

Use of AI tools declaration

Acknowledgments

Conflict of interest

References

Reader Comments

通讯作者: 陈斌, bchen63@163.com

Metrics

Figures and Tables

Other Articles By Authors

Related pages

Tools

Export File

Citation

Format

Content

Catalog

3.2. Communication time (C_T)

3.3. Execution time (E_T)