# Genetic Algorithm-Based Task Scheduling in Cloud Computing Using MapReduce Framework

Authors: Zhihao Peng; Poria Pirozmand; Masoumeh Motevalli; Ali Esmaeili
Journal: Mathematical Problems in Engineering
 (2022)

---

## Abstract

Task scheduling is an essential component of any distributed system because it routes tasks to appropriate resources for execution, such as grids, clouds, and peer-to-peer networks. Common scheduling algorithms include downsides, such as high temporal complexity, non-simultaneous processing of input tasks, and longer program execution times. Exploration-based scheduling algorithms prioritize tasks using a variety of methods, resulting in long execution times on heterogeneous distributed computing systems. As a result, task prioritization becomes a bottleneck in such systems. It is appropriate to prioritize tasks with the shortest execution time using faster algorithms. The genetic algorithm (GA) is one of the evolutionary approaches used to solve complex problems quickly. This paper proposes a parallel GA with a MapReduce architecture for scheduling jobs on cloud computing with various priority queues. The fundamental aim of this study is to employ a MapReduce architecture to minimize the total execution time of the task scheduling process in the cloud computing environment. The proposed method accomplishes task scheduling in two stages: first, the GA was used in conjunction with heuristic techniques to assign tasks to processors, and then the GA was used in conjunction with the MapReduce framework to assign jobs to processors. In our experiments, we consider heterogeneous resources that differ in their ability to execute various tasks, as well as running a job on different resources with varying execution durations. The results show that the proposed method outperforms other algorithms such as particle swarm optimization, whale optimization algorithm, moth-flame optimization, and intelligent water drops.


---

## Body

## 1. Introduction

One kind ofdistributed computing system is heterogeneous, in which several processors are used to do the same work [1]. In cloud computing, task scheduling is separated into a series of lower priority tasks for processing [2]. These sub-tasks exhibit precedence constraints in the sense that the outcome of previous tasks is required before executing the current sub-task [3]. It may lower the task completion time by breaking a computer work into sub-tasks and executing them on numerous processors. As a result, the goal of this study is to arrange sub-tasks on a variety of available processors in order to minimize task completion time without breaching precedence requirements [4].The development of task scheduling algorithms that distribute sub-tasks of a program to processors is a challenge in cloud systems. Despite recent improvements in the area of task scheduling, this problem remains a significant challenge in heterogeneous computing settings[5, 6].Reduced execution time of the scheduling algorithm remains an essential problem due to the rise in the quantity of data in the cloud environment. As a result, several techniques for reducing task completion time by parallelizing sub-tasks and honoring their precedence connections have been proposed. A directed acyclic graph, which consists of vertices that represent tasks and directed edges that indicate task dependency, is often used to depict precedence relationships. It is acceptable and expressive to deliver programs with a vast and varied volume using directed acyclic graphs [7, 8]. On the other hand, the Hadoop system enables task execution in a shared data center [9]. MapReduce is an excellent Hadoop technique for processing massive data in cloud computing that runs instructions and programs in parallel utilizing processors or computers [10]. In a distributed setting, this programming paradigm enables the creation of parallel and distributed processing on a huge number of data [11]. This framework is provided with several methodologies and applications in various disciplines, such as algorithms with high time complexity in huge data, which decreases algorithm execution time by enhancing parallel processing [12]. As a result, this article discusses how to schedule priority jobs on directed acyclic networks using the genetic algorithm (GA) and the MapReduce framework. The proposed method accomplishes task scheduling in two stages: the GA was used in conjunction with heuristic techniques to allocate tasks to processors in the first stage, and the GA was used in conjunction with the MapReduce framework to assign jobs to processors in the second stage.In essence, the following are the article’s objectives:(i)
Creating a new combination of GA with MapReduce framework to assign jobs to processors.(ii)
Using the MapReduce architecture for scheduling in heterogeneous cloud environments.(iii)
Reducing the overall program execution time.(iv)
Accelerating the convergence of solutions and avoiding premature convergence.The remainder of the paper is structured as follows. Section2 examines various essential strategies for work scheduling in cloud computing. The overall structure and recommended approach are presented in Section 3 utilizing the MapReduce framework. Section 4 analyzes the acquired findings and compares the proposed approach to other algorithms. Section 5 concludes with the conclusion and future works.


## 2. Literature Review

This section discusses approaches for task scheduling as well as the benefits and drawbacks of different methods. This study also describes the fundamental concept of the suggested scheduling approach after examining the current methods. The main issue of this paper is the multiobjective aspect of job scheduling in cloud computing. Among the different scheduling concerns, one of the NP-hard optimization problems is scheduling the machine with parallel processors.Two list-based scheduling methods, heterogeneous earliest-finish-time (HEFT) and critical-path-on-a-processor (CPOP), have been introduced in [13] in order to concurrently meet the two objectives of high efficiency and quick scheduling. To lower the quickest start time, the HEFT algorithm picks a task with the upward rank at each stage and assigns it to processors using the insertion-based technique. The CPOP algorithm, on the other hand, prioritizes by aggregating upward and downward rank into tasks. Another difference between the two algorithms is in the assignment of the processor to the tasks, with the CPOP method executing the critical path tasks on the processors, hence minimizing the execution time of all critical path tasks. Shabestari et al. [14] proposed an ant colony method (ACO)-based scheduling algorithm. The goal of this scheduler is to reduce the workflow time of the group of tasks while also reducing the maximum completion time of the complete job. This technique enables more agile work while decreasing completion time. The results of the evaluation also revealed that the ACO algorithm outperforms the random and best-effort methods. Liu [15] created an ant colony algorithm-based adaptive work scheduling system for cloud computing. Pheromones may now be updated dynamically in response to changes in the environment to the polymorphic ant colony algorithm to increase the algorithm’s convergence speed and successfully prevent the formation of local optimum solutions. Based on the tasks supplied by users, the enhanced algorithm tries to develop a distribution plan with a quicker execution time, reduced cost, and balanced load rate. Their experiment results demonstrate that the modified adaptive ant colony algorithm can rapidly discover the ideal solution to the cloud computing resource scheduling issue, shorten job completion time, minimize execution cost, and keep the overall cloud system center load balanced.For handling multi-objective task scheduling in cloud computing, Manikandan et al. [16] offered a unique hybrid whale optimization algorithm-based MBA algorithm. The multi-objective behavior of the hybrid WOA-based MBA algorithm reduces the makespan by optimizing resource consumption. By using the mutation operator from the bees algorithm, the output of the random double adaptive whale optimization algorithm (RDWOA) may be made to be of higher quality. The performance of the algorithm is analyzed and compared to that of other algorithms that make use of the CloudSim tool kit platform for various criteria like the amount of time it takes to finish, the amount of money it costs to compute, and so on. The study reveals that the suggested method is superior to other algorithms in terms of performance metrics such as computational cost, execution time, makespan, and resource consumption. These metrics were evaluated in relation to the findings obtained. To schedule a set of user tasks on a set of VMs, Imenea et al. [17] presented a third-generation multi-objective optimization method for the first time to our knowledge called non-dominated sorting genetic algorithm (NSGA-III). The method is used in the cloud to minimize the runtime (TE), power consumption (CE), and cost. Manikandan et al. [18] suggested a system that uses fuzzy C-means clustering hybrid algorithms for job scheduling and fish swarm optimization for optimal resource allocation to minimize cost, energy, and resource use. Shukri et al. [19] suggested an enhanced version of the multi-verse optimizer (EMVO) as a better job scheduler in this field. In terms of minimizing makespan time and boosting resource usage, the findings reveal that EMVO outperforms both MVO and PSO algorithms.The task scheduling and resource provisioning challenges have become an appealing paradigm in the cloud sector, owing to the rising demand for services offered by VMs that are organized by actual servers owned by cloud service providers’ data centers (CSPs). In [20], the authors suggested a novel model based on a multi-agent system for task scheduling and resource provisioning that uses deep reinforcement learning to reduce energy costs. A quantile regression deep Q network method delivers the best policy and long-term choices. A series of tests demonstrate the efficacy of the suggested scheduling strategy as well as the performance of the proposed job allocation mechanism. In [21], the ant particle swarm genetic algorithm is presented as a mix of PSO-ACO-GA for work scheduling on cloud computing VMs. Here, PSO and GA will iterate to determine the job based on fitness value, and ACO will distribute the work to particular VMs. This article improves on characteristics such as CPU usage, execution time, and makespan.Mangalampalli et al. [22] used the cat swarm optimization (CSO) algorithm to solve task scheduling in cloud computing. The presented algorithm considers lifetime, migration time, energy consumption, and the total cost of power in data centers. Tasks are scheduled in the proposed algorithm by calculating task priorities at the task level and calculating VM priorities at the VM level to plan the appropriate mapping of tasks on virtual machines.Amer et al. [23] used the modified Harris hawks optimizer (HHO) algorithm to solve the multi-objective scheduling problem. To improve the quality of the standard HHO algorithm’s discovery phase, a scientific smart method called elite opposition-based learning is used. Furthermore, the minimum completion time algorithm is used as the first phase to obtain a determined initial solution rather than a random solution at each run time, avoiding local optimization and improving the quality of service in terms of program length minimization. Furthermore, the minimum completion time algorithm is used as the first phase to obtain a determined initial solution rather than a random solution at each run time, avoiding local optimization and improving service quality by minimizing program length to cover implementation costs while maintaining service quality.


## 3. The Proposed Algorithm

As mentioned earlier, the suggested approach accomplishes task scheduling in two stages: in the first stage, the GA was used in conjunction with heuristic techniques to allocate tasks to processors, and in the second stage, the GA was used in conjunction with the MapReduce framework to assign jobs to processors. The problem variables are described initially in this part, followed by procedures to construct GA for combining cloud services.


### 3.1. Initial Definitions

The suggested approach employs a collection of heterogeneousP processors linked by a high-speed network. The issue of task scheduling is mapped on a directed graph G(V, E) in this method. So, V represents the program’s sub-tasks, and E represents the graph edges that specify the dependencies between the sub-tasks. Each sub-task in the graph can only be executed on a single processor. The amount of communication cost between the two sub-tasks is represented by edge values, and the average computational cost of each sub-task in the processors is measured on each node. The example described in this study is shown in Figure 1.Figure 1
A directed graph that does not rotate and has ten sub-tasks [5].Table1 lists the symbols used in this paper’s equations and algorithms.Table 1
Symbols used in the proposed method.
SymbolDescriptiontiith sub-task in a graphpkKih processor in the systemESet of edges in a graphTThe following set of tasks in the graphPSet of processors in the systemTentrySub-task input in a graphTexitSub-output task in a graphSucc(ti)The set of delays below the tasktiPred(ti)A set of sub-taskstiWti¯The average computational cost below tasktiWti,PkComputational cost below taskti on the processorCti,tjThe amount of communication cost between the tasks ofti and tjrankbtiUpward rank of sub-tasktirankttiDownward ranking of sub-tasktiRankb +t(ti)Add a task to the sub-taskti in the rankESTti,PkThe earliest start time sub-taskti on a processorEFTti,PkThe earliest end time sub-taskti on a processorASTti,PkActual start time sub-taskti on a processorAFTti,PkActual end time sub-taskti on a processorAvail {k}Idle time and availability of pk processorPopPopulationPopSizePopulation sizeChSizeChromosome sizeThe communication cost between two linked sub-tasks is zero if they are scheduled on the same processor. The start and end nodes in the graph represent the beginning and end of the program, respectively. The utilization model of the proposed method is unrelated, which implies that one processor may perform some activities in less time and others in more time, as shown in Table2. Furthermore, all previous sub-tasks must be scheduled and completed before commencing to execute a sub-task.Table 2
An example of sub-task computational expenses on processors.
TaskP0P1P2ω¯t089109t19101110t2106119t31281612t425181720t513101613t67121712t717101213t81281311t913101312Following the creation of the initial population, each chromosome is evaluated and ranked based on total execution time; this ranking is referred to as the suitability value of each chromosome. In the ranking, the HEFT processor allocation algorithm is employed. The fusion process is then initiated by choosing and merging several chromosomes. The parallelism procedure is performed on the chromosomes after the fusion step. The proposed method is executed until the termination condition is satisfied. In the next portion of this research, the details of each step of the suggested algorithm and accompanying pseudocodes will be discussed.


### 3.2. Initial Population Quantification

Making a chromosome through encoding is the first stage in populating the population. The suggested algorithm’s chromosomal structure contains a gene that provides a solution to the task scheduling issue. A chromosome’s structure is a permutation of natural numbers from0 to n1, which shows the order of priority of jobs in a non-rotating directed graph. Furthermore, the topological arrangement of tasks on the chromosome must be valid. The proposed method places the starting job at the very first position on the chromosome and the job at the very end of the chromosome, known as the end node. The additional jobs are located on the chromosome in locations that do not contradict task precedence. All sub-tasks in the graph must be planned for scheduling to be feasible.ThePopSize symbol represents the proposed algorithm’s starting population size, which is four times the number of jobs in the network (4n). The algorithm’s population size remains fixed until the conclusion of the algorithm. This means the population size does not fluctuate throughout the creation of new generations. In the proposed algorithm, three exploratory ranking policies called upward rank (equation (1)), downward rank (equation (2)), and a combination of these two methods with level ranking (equation (3)) have been used to quantify the first three chromosomes of a population in order to have good seeding in the initial population quantification. It is shown in Table 3 using three policies, with random permutations determining the priority of the remaining chromosomes. Because their priorities are invalid, randomly generated chromosomes are arranged from left to right to ensure that priority constraints are not broken. The first population creation process is depicted in Algorithm 1.(1)rankbti=Wti¯+maxtj∈SUCCtiCti,tj+rankbtj.Table 3
An example of task priorities in a cloud environment.
Sub-task (ti)RankbRanktRankb +tLevelT012901230T181241051T278231011T3100171171T499301291T560501102T667521192T735751103T842771193T9121071194In (1), Wti the average computational cost of task ti, Cti,tj the amount of communication cost between tasks ti and tj and rankbtj the upward rank is the sub-task ti.(2)ranktti=maxtj∈SUCCtirankttj+Wtj+Cti,tj.In (2), rankttj is the downward rank is the sub-task ti.(3)Levelti=0,ifti=tentry;maxtj∈predtjLeveltj+1,otherwise.In equation (3), Leveltj is the precedence sub-task of ti.Algorithm 1: Creation of the initial population.
Applying three different heuristic ranking strategies on the first three of the chromosomes.fori from 3 to PopSize-1 doforj from 0 to ChSize-1 doproduce at random a gene with the parametersj∈0,ChSize−1 that has not beengenerated in previous genes.In order to maintain a topological order that is reliable, transfer chromosomei from itscurrent position on the left to its new position on the right in the queue.end forend for


### 3.3. Assigning Sub-Tasks to Processors

Each chromosome in the initial population must have a legitimate order of precedence, i.e., the precedence restrictions on the chromosome must not be violated. The suggested approach for work assignment processors has been subjected to the HEFT processor allocation policy [10]. In this procedure, the sub-task with the greatest priority is chosen from the chromosome’s sub-tasks and given to processors with the shortest execution time compared to other processors. An insert-based scheduling strategy is used in this processor allocation approach. This approach is discussed in the next section. The earliest start time is the ti task on the pk processor. ESTti,pk is symbolized and obtained from(4)ESTti,pk=maxAFTtj+Cti,tjtj∈predtimax.The moment when the actual taskti began running on processor pk with ASTti,pk is symbolized and obtained from(5)ASTti,pk=maxASTti,pk,Availpk,where Avail (pk) is the time when the pk processor is idle and ready to execute tasks. Earliest finish time of sub-task ti on processor pk with EFTti,pk is symbolized and calculated from(6)EFTti,pk=Wti,pk+ESTti,pk,here, Wti,pk is defined as the amount of computing effort required to complete task ti on processor pk which is actually the real-time finish of sub-task ti on processor pk with AFTti,pk.It is shown and obtained from(7)AFTti,pk=E1≤l≤pminFTti,pl,which pk in the above equation is the fittest processor for the sub-task ti. The pseudocode for assigning tasks to processors is explained in Algorithm 2.Algorithm 2: Sub-task allocation to processors.
Push sub-task to priority queuewhile not empty (priority queue)Popti (first sub-task) From priority queuefor each processor pkdoinsertion-based HEFT scheduling policy (AFTti,pk)assignti to the processor pkend forend whileReturn makespan =  AFTtexit


### 3.4. Fitness Function

The degree of fitness of chromosomes is critical in determining which chromosomes to carry on to the next generation. The real finish time of the final sub-task in the directed graph is without rounds; or in other words, the graph’s output node equals the program’s execution time. (8) yields the execution time of the whole program, which is the same as the appropriateness of chromosome i.(8)makespani=maxAFTtexit.A low fitness signifies a short overall execution time. As a result, the poorest and best chromosomes in the population have the greatest and lowest fitness rates, respectively.


### 3.5. Crossover

Crossover is a key operator in GAs for modifying population chromosomes [8]. In GAs, the crossover operator also contributes to population evolution. To create a new generation of chromosomes, the operator unites more than one chromosome. Some qualities are inherited from the first parent, while others are inherited from the second parent. Algorithm 3 describes the crossover operation in details.Algorithm 3: Crossover operation.
Input: Two parents from the existing populationOutput: Two offspringSelect at random an appropriate crossing pointiSeparate the chromosomes of the father and mother into left and right parts.Create a new offspring, specifically a sonTransfer the father’s left chromosomal segment to the son’s left chromosome segment.Copy genes from the mother’s chromosome that do not occur in the father’s left chromosome segment to the rightchromosome segment of the son.Produce a new offspring, specifically a daughterTransfer the mother’s left chromosomal segment to the daughter’s left chromosome segment.Copy genes from the father’s chromosome that do not occur on the mother’s left chromosome to the daughter’s rightchromosome.Return (Two selected offspring)The single-point operator is simplified to a MapReduce framework in Algorithm4, with each combined action allocated to a mapping.Algorithm 4: Crossover mapper.
Input: MappersOutput: New MappersFor each Mapper do Algorithm 5 (A chromosome Ti that has been picked at random)Execute the MapReduce task managerRecord the result asM blocksTransfer the outcome to the shuffle step.The best person should be written to the global file in DFS if all individuals have been processedsuccessfullyReturn (New Mappers)


### 3.6. Mutation

GA mutations are employed to preserve population variability by altering chromosomes. Following the use of the combination operator, several chromosomes are modified using the mutation operator to prevent local optimum convergence and to produce variety in the population. Two more genes are designated for mutation procedures. Algorithm5 describes the suggested algorithm’s mutation operation.Algorithm 5: Mutation operation.
Input: A chromosome Ti that has been picked at random.Output: A new chromosome is being created.Line 1: fromSucc (i)select the first successor TjIn the interval [i+1, j-1] Choose a gene Tk randomlyfor all Tl member Pred (k)ifl < i thenswapped (Ti,Tk) to create a new generation.Return the new offspringelseGo to Line 1end ifend forIn Algorithm6, mutation operators are condensed to combine with the MapReduce architecture.Algorithm 6: Mutation reduce.
(1)
Give each Reducer the result of Algorithm 6.(2)
Activate the MapReduce task manager.(3)
Begin the process of calculating.(4)
Incorporate the findings into M-sized blocks.(5)
Verify that the termination condition has been met.(6)
if all individuals are properly processed then Write (best individual, DFS).(7)
The result should be sent to the cluster.


### 3.7. Selection

In the suggested approach, the technique of picking a roulette wheel with random acceptance is utilized to choose several chromosomes for the local search algorithm (LSA) [16]. It has a temporal complexity of O in this manner (1). This method consists of two major steps. In the first step, a chromosome is selected at random from the population. The probability (1/n) of selection is used. The next step is to analyze the chromosome fitness value and to find if the locally selected chromosome is one of the elites of the population. Otherwise, the selected chromosome is not accepted and the process is repeated. Algorithm 7 provides the pseudocode for selecting a roulette wheel with random acceptance.Algorithm 7: Stochastic acceptance for roulette wheel selection.
Input: A chromosome.Output: A new chromosomeGenerateR∈0,PopSize−1 a random numberifmake span R/makespanmin==1thenreturnchoromosomeR;end ifwhile (founding one of the fitness solutions)


### 3.8. Termination Conditions

The primary distinction between natural evolution and the issue in natural evolution is that species in nature do not tend to end, but in order to solve a problem within the stipulated budget, the process must be halted [17]. There are popular ways for testing the termination condition of algorithms, such as limiting the cost of fitness evaluation function or computer clock time, or monitoring diversity and terminating it when population diversity diminishes [14]. The termination condition in the proposed method happens when all of the chromosomes, or solutions, converge to the same degree of fit.


## 3.1. Initial Definitions

The suggested approach employs a collection of heterogeneousP processors linked by a high-speed network. The issue of task scheduling is mapped on a directed graph G(V, E) in this method. So, V represents the program’s sub-tasks, and E represents the graph edges that specify the dependencies between the sub-tasks. Each sub-task in the graph can only be executed on a single processor. The amount of communication cost between the two sub-tasks is represented by edge values, and the average computational cost of each sub-task in the processors is measured on each node. The example described in this study is shown in Figure 1.Figure 1
A directed graph that does not rotate and has ten sub-tasks [5].Table1 lists the symbols used in this paper’s equations and algorithms.Table 1
Symbols used in the proposed method.
SymbolDescriptiontiith sub-task in a graphpkKih processor in the systemESet of edges in a graphTThe following set of tasks in the graphPSet of processors in the systemTentrySub-task input in a graphTexitSub-output task in a graphSucc(ti)The set of delays below the tasktiPred(ti)A set of sub-taskstiWti¯The average computational cost below tasktiWti,PkComputational cost below taskti on the processorCti,tjThe amount of communication cost between the tasks ofti and tjrankbtiUpward rank of sub-tasktirankttiDownward ranking of sub-tasktiRankb +t(ti)Add a task to the sub-taskti in the rankESTti,PkThe earliest start time sub-taskti on a processorEFTti,PkThe earliest end time sub-taskti on a processorASTti,PkActual start time sub-taskti on a processorAFTti,PkActual end time sub-taskti on a processorAvail {k}Idle time and availability of pk processorPopPopulationPopSizePopulation sizeChSizeChromosome sizeThe communication cost between two linked sub-tasks is zero if they are scheduled on the same processor. The start and end nodes in the graph represent the beginning and end of the program, respectively. The utilization model of the proposed method is unrelated, which implies that one processor may perform some activities in less time and others in more time, as shown in Table2. Furthermore, all previous sub-tasks must be scheduled and completed before commencing to execute a sub-task.Table 2
An example of sub-task computational expenses on processors.
TaskP0P1P2ω¯t089109t19101110t2106119t31281612t425181720t513101613t67121712t717101213t81281311t913101312Following the creation of the initial population, each chromosome is evaluated and ranked based on total execution time; this ranking is referred to as the suitability value of each chromosome. In the ranking, the HEFT processor allocation algorithm is employed. The fusion process is then initiated by choosing and merging several chromosomes. The parallelism procedure is performed on the chromosomes after the fusion step. The proposed method is executed until the termination condition is satisfied. In the next portion of this research, the details of each step of the suggested algorithm and accompanying pseudocodes will be discussed.


## 3.2. Initial Population Quantification

Making a chromosome through encoding is the first stage in populating the population. The suggested algorithm’s chromosomal structure contains a gene that provides a solution to the task scheduling issue. A chromosome’s structure is a permutation of natural numbers from0 to n1, which shows the order of priority of jobs in a non-rotating directed graph. Furthermore, the topological arrangement of tasks on the chromosome must be valid. The proposed method places the starting job at the very first position on the chromosome and the job at the very end of the chromosome, known as the end node. The additional jobs are located on the chromosome in locations that do not contradict task precedence. All sub-tasks in the graph must be planned for scheduling to be feasible.ThePopSize symbol represents the proposed algorithm’s starting population size, which is four times the number of jobs in the network (4n). The algorithm’s population size remains fixed until the conclusion of the algorithm. This means the population size does not fluctuate throughout the creation of new generations. In the proposed algorithm, three exploratory ranking policies called upward rank (equation (1)), downward rank (equation (2)), and a combination of these two methods with level ranking (equation (3)) have been used to quantify the first three chromosomes of a population in order to have good seeding in the initial population quantification. It is shown in Table 3 using three policies, with random permutations determining the priority of the remaining chromosomes. Because their priorities are invalid, randomly generated chromosomes are arranged from left to right to ensure that priority constraints are not broken. The first population creation process is depicted in Algorithm 1.(1)rankbti=Wti¯+maxtj∈SUCCtiCti,tj+rankbtj.Table 3
An example of task priorities in a cloud environment.
Sub-task (ti)RankbRanktRankb +tLevelT012901230T181241051T278231011T3100171171T499301291T560501102T667521192T735751103T842771193T9121071194In (1), Wti the average computational cost of task ti, Cti,tj the amount of communication cost between tasks ti and tj and rankbtj the upward rank is the sub-task ti.(2)ranktti=maxtj∈SUCCtirankttj+Wtj+Cti,tj.In (2), rankttj is the downward rank is the sub-task ti.(3)Levelti=0,ifti=tentry;maxtj∈predtjLeveltj+1,otherwise.In equation (3), Leveltj is the precedence sub-task of ti.Algorithm 1: Creation of the initial population.
Applying three different heuristic ranking strategies on the first three of the chromosomes.fori from 3 to PopSize-1 doforj from 0 to ChSize-1 doproduce at random a gene with the parametersj∈0,ChSize−1 that has not beengenerated in previous genes.In order to maintain a topological order that is reliable, transfer chromosomei from itscurrent position on the left to its new position on the right in the queue.end forend for


## 3.3. Assigning Sub-Tasks to Processors

Each chromosome in the initial population must have a legitimate order of precedence, i.e., the precedence restrictions on the chromosome must not be violated. The suggested approach for work assignment processors has been subjected to the HEFT processor allocation policy [10]. In this procedure, the sub-task with the greatest priority is chosen from the chromosome’s sub-tasks and given to processors with the shortest execution time compared to other processors. An insert-based scheduling strategy is used in this processor allocation approach. This approach is discussed in the next section. The earliest start time is the ti task on the pk processor. ESTti,pk is symbolized and obtained from(4)ESTti,pk=maxAFTtj+Cti,tjtj∈predtimax.The moment when the actual taskti began running on processor pk with ASTti,pk is symbolized and obtained from(5)ASTti,pk=maxASTti,pk,Availpk,where Avail (pk) is the time when the pk processor is idle and ready to execute tasks. Earliest finish time of sub-task ti on processor pk with EFTti,pk is symbolized and calculated from(6)EFTti,pk=Wti,pk+ESTti,pk,here, Wti,pk is defined as the amount of computing effort required to complete task ti on processor pk which is actually the real-time finish of sub-task ti on processor pk with AFTti,pk.It is shown and obtained from(7)AFTti,pk=E1≤l≤pminFTti,pl,which pk in the above equation is the fittest processor for the sub-task ti. The pseudocode for assigning tasks to processors is explained in Algorithm 2.Algorithm 2: Sub-task allocation to processors.
Push sub-task to priority queuewhile not empty (priority queue)Popti (first sub-task) From priority queuefor each processor pkdoinsertion-based HEFT scheduling policy (AFTti,pk)assignti to the processor pkend forend whileReturn makespan =  AFTtexit


## 3.4. Fitness Function

The degree of fitness of chromosomes is critical in determining which chromosomes to carry on to the next generation. The real finish time of the final sub-task in the directed graph is without rounds; or in other words, the graph’s output node equals the program’s execution time. (8) yields the execution time of the whole program, which is the same as the appropriateness of chromosome i.(8)makespani=maxAFTtexit.A low fitness signifies a short overall execution time. As a result, the poorest and best chromosomes in the population have the greatest and lowest fitness rates, respectively.


## 3.5. Crossover

Crossover is a key operator in GAs for modifying population chromosomes [8]. In GAs, the crossover operator also contributes to population evolution. To create a new generation of chromosomes, the operator unites more than one chromosome. Some qualities are inherited from the first parent, while others are inherited from the second parent. Algorithm 3 describes the crossover operation in details.Algorithm 3: Crossover operation.
Input: Two parents from the existing populationOutput: Two offspringSelect at random an appropriate crossing pointiSeparate the chromosomes of the father and mother into left and right parts.Create a new offspring, specifically a sonTransfer the father’s left chromosomal segment to the son’s left chromosome segment.Copy genes from the mother’s chromosome that do not occur in the father’s left chromosome segment to the rightchromosome segment of the son.Produce a new offspring, specifically a daughterTransfer the mother’s left chromosomal segment to the daughter’s left chromosome segment.Copy genes from the father’s chromosome that do not occur on the mother’s left chromosome to the daughter’s rightchromosome.Return (Two selected offspring)The single-point operator is simplified to a MapReduce framework in Algorithm4, with each combined action allocated to a mapping.Algorithm 4: Crossover mapper.
Input: MappersOutput: New MappersFor each Mapper do Algorithm 5 (A chromosome Ti that has been picked at random)Execute the MapReduce task managerRecord the result asM blocksTransfer the outcome to the shuffle step.The best person should be written to the global file in DFS if all individuals have been processedsuccessfullyReturn (New Mappers)


## 3.6. Mutation

GA mutations are employed to preserve population variability by altering chromosomes. Following the use of the combination operator, several chromosomes are modified using the mutation operator to prevent local optimum convergence and to produce variety in the population. Two more genes are designated for mutation procedures. Algorithm5 describes the suggested algorithm’s mutation operation.Algorithm 5: Mutation operation.
Input: A chromosome Ti that has been picked at random.Output: A new chromosome is being created.Line 1: fromSucc (i)select the first successor TjIn the interval [i+1, j-1] Choose a gene Tk randomlyfor all Tl member Pred (k)ifl < i thenswapped (Ti,Tk) to create a new generation.Return the new offspringelseGo to Line 1end ifend forIn Algorithm6, mutation operators are condensed to combine with the MapReduce architecture.Algorithm 6: Mutation reduce.
(1)
Give each Reducer the result of Algorithm 6.(2)
Activate the MapReduce task manager.(3)
Begin the process of calculating.(4)
Incorporate the findings into M-sized blocks.(5)
Verify that the termination condition has been met.(6)
if all individuals are properly processed then Write (best individual, DFS).(7)
The result should be sent to the cluster.


## 3.7. Selection

In the suggested approach, the technique of picking a roulette wheel with random acceptance is utilized to choose several chromosomes for the local search algorithm (LSA) [16]. It has a temporal complexity of O in this manner (1). This method consists of two major steps. In the first step, a chromosome is selected at random from the population. The probability (1/n) of selection is used. The next step is to analyze the chromosome fitness value and to find if the locally selected chromosome is one of the elites of the population. Otherwise, the selected chromosome is not accepted and the process is repeated. Algorithm 7 provides the pseudocode for selecting a roulette wheel with random acceptance.Algorithm 7: Stochastic acceptance for roulette wheel selection.
Input: A chromosome.Output: A new chromosomeGenerateR∈0,PopSize−1 a random numberifmake span R/makespanmin==1thenreturnchoromosomeR;end ifwhile (founding one of the fitness solutions)


## 3.8. Termination Conditions

The primary distinction between natural evolution and the issue in natural evolution is that species in nature do not tend to end, but in order to solve a problem within the stipulated budget, the process must be halted [17]. There are popular ways for testing the termination condition of algorithms, such as limiting the cost of fitness evaluation function or computer clock time, or monitoring diversity and terminating it when population diversity diminishes [14]. The termination condition in the proposed method happens when all of the chromosomes, or solutions, converge to the same degree of fit.


## 4. Simulation Results

The suggested technique of the study, including job scheduling cloud computing utilizing GA, is evaluated in this paper using the Matlab software R2016b v9.1 × .64 and executed on a computer system with an Intel® CoreTM2 Duo E4500 processor and 2 GB RAM.This study considers heterogeneous resources, which vary in their capacity to execute various tasks, and executing a job on different resources might result in varied execution durations. In the equivalent graph, communication cost or edge cost refers to the time spent transferring the outcome of one job to another.Two graphs,G1n×n for the communication cost between tasks and G2n×m for the computing cost of each task, are required to construct each random DAG, where n is the number of tasks and m is the number of available resources. The computation cost is created at random between 5 and 20, while the communication cost is generated at random between 1 and 10 every millisecond unit. In the experiments, the following algorithm parameters are set. The starting population size is 50, the maximum number of iterations is 120, the inertia weight is 0.7, and C1 and C2 are equal to 2. The test phase was divided into three phases, each with 50 graphs and no different activities (20, 40, 60).In addition to the PSO and IWD algorithms, the results of the proposed method are compared against the results of the well-known WOA and MFO algorithms. The identical method was utilized for all five of the abovementioned test conditions.Figures2–4 depict graphs with 20 tasks, 50 graphs with 40 tasks, and 50 graphs with 60 tasks. All algorithms have the same set of parameters. In addition, the maximum number of iterations in each of the five algorithms is set at 120.Figure 2
The algorithms’ convergence speed is determined by running them on 50 graphs with 20 tasks.Figure 3
The convergence speed achieved from the methods’ implementation on 50 graphs with 40 tasks.Figure 4
The algorithms’ convergence speed is determined by running them on 50 graphs with 60 tasks.In these graphs, the number of iterations required for the algorithm to reach the optimum solution is referred to as the convergence step. When the number of tasks equals 20, the PSO algorithm’s convergence step is changed in the interval (63-81), the IWD algorithm’s in the interval (63-80), the WOA algorithm’s in the interval (58-72), the MFO algorithm’s in the interval (72-82), and the GA algorithm’s in the interval (53-63). Furthermore, MFO has had the poorest average outcomes. The GA’s advantage is also evident in all iterations.When the number of tasks reaches 40, the convergence step in the PSO algorithm shifts to the interval (85-103), the IWD method shifts to the interval (85-100), the WOA algorithm shifts to the interval (85-100), the MFO algorithm shifts to the interval (96-108) and the GA algorithm shifts to the interval (77-97). Again, as seen in the graph, MFO has produced the poorest outcomes in this circumstance. The results of the algorithms in the second scenario are closer than the results of the algorithms in the other two cases. IWD and WOA outcomes are closely related, and in 16 instances, they are identical. The IWD algorithm produced the best results in 21% of instances, the GA method in 72%, and the WOA algorithm in 7% of cases.Furthermore, when the number of tasks reaches 60, the PSO algorithm’s convergence step shifts to (90-105), the IWD algorithm shifts to (95-105), the WOA method shifts to (81-101), the MFO algorithm shifts to (96-109), and the GA algorithm shifts to (71-102). As the number of tasks rises, WOA outcomes approach GA, and PSO results approach IWD. MFO had the poorest average performance in the third scenario, as in the previous situations. WOA performed better in 26% of the instances, whereas GA performed best in the remaining situations. Table4 displays the best, average, worst, and standard deviation of convergence speed values. Figures 5–7 illustrate the results of implementing the proposed method and comparing algorithms on 50 graphs with a varying number of jobs. All algorithms have the same set of parameters. In addition, the maximum number of repeats in all three situations is 120. After 120 repetitions, the values of makespan are recorded and reported in Table 4.Table 4
The best, average, worst, and standard deviation of convergence speed results.
Test scenarioAlgorithmBestMediumWorstStandard deviationFirst scenarioIWD6374807.23PSO6378816.58GA5357634.08WOA5868726.21MFO7280824.76Second scenarioIWD85941006.24PSO85981038.04GA70889711.61WOA85941006.24MFO961041085.16Third scenarioIWD951031054.76PSO90961056.24GA718410211.90WOA819910110.64MFO961041095.44Figure 5
Makespan results from running the algorithms on 50 graphs with 20 tasks.Figure 6
Makespan is determined by running the algorithms on 50 graphs with 40 tasks.Figure 7
Makespan results from running the algorithms on 50 graphs with 60 tasks.As illustrated in the diagram, the PSO and IWD outcomes in the first scenario are quite near to each other. The MFO algorithm had the poorest performance, whereas GA had the highest performance in 86% of situations.In the second scenario, PSO degrades the most and is worse than MFO in 13 occurrences. Similar to the previous example, GA had the greatest performance; however, it performed lower than WOA on 10 occasions.In the third scenario, the IWD outcomes of two GA and WOA algorithms became closer and even outperformed each other in five instances. However, GA continues to outperform in 67% of situations. As illustrated in Figures5–7, the overall tendency is that as the number of tasks rises, makespan increases, PSO performance declines, and IWD performance improves. In addition, Table 5 displays the best, average, worst, and standard deviation outcomes of makespan.Table 5
The best, average, worst, and standard deviation results of makespan.
Test scenarioAlgorithmBestMediumWorstStandard deviationFirst scenarioIWD2802963019.86PSO28029830310.78GA2512562708.59WOA2602812908.22MFO2993103167.25Second scenarioIWD2823023068.96PSO2993093167.04GA2732802886.13WOA2722782913.87MFO3063133164.39Third scenarioIWD2822963008.40PSO3003123167.30GA2812882955.71WOA28128930141.12MFO30031932411.34Bold numbers represent the best results achieved.As demonstrated in this section, the GA algorithm solved the problem better than the other four algorithms and was able to compete with them. In the first and third scenarios, the GA algorithm outperformed the compared algorithms, and only in the second scenario did the WOA algorithm outperform the GA algorithm by one unit. This proves the GA algorithm’s stability and convergence.


## 5. Conclusion and Future Works

Scheduling is a critical topic in distributed computing systems, and several scheduling techniques have been suggested. This research presents a parallel GA for static tasks in cloud computing systems utilizing a MapReduce framework. This method was created by merging genetic algorithms with the HEFT algorithm, which is used to allocate sub-tasks to processors. The proposed method accomplishes task scheduling in two stages: first, the GA was used in conjunction with heuristic techniques to assign tasks to processors, and then the GA was used in conjunction with the MapReduce framework to assign jobs to processors. In our experiments, we consider heterogeneous resources that differ in their ability to execute various tasks, as well as running a job on different resources with varying execution durations. The results show that the proposed method outperforms other algorithms such as PSO, WOA, MFO, and IWD.One disadvantage of this strategy is that the graphs’ computational and communication costs are chosen at random from a range. MapReduce, on the other hand, is low-level programming that necessitates a significant amount of code in order to obtain the mapping and reduction functions. As a result, future research on the proposed technique could be based on real-world graphs like the fast Fourier transform (FFT), molecular dynamics code, and so on. In the mapping and communication stage segment of Google’s MapReduce approach, there is a brief overlap. Unfortunately, this overlap in MapReduce software, which has a longer communication phase than the mapping phase, does not affect reaction time. If it is possible to provide solutions that can overlap the massive stages of communication and reduction in such software, the necessary time of program execution may be reduced while simultaneously maximizing the available resources.



---

*Source: 4290382-2022-09-30.xml*