# Research on Optimization Strategy of Task Scheduling Software Based on Genetic Algorithm in Cloud Computing Environment

Authors: Zhuoyuan Yu
Journal: Wireless Communications and Mobile Computing
 (2022)

---

## Abstract

In order to improve the task scheduling strategy, a method based on genetic algorithm in cloud computing environment was proposed. First, the independent task scheduling algorithm and associated task scheduling algorithm commonly used in cloud computing are studied and compared, respectively, and their application characteristics, advantages, and disadvantages are analyzed in detail. Second, an independent task scheduling strategy based on multipopulation genetic algorithm is proposed for independent task scheduling in cloud environment, considering the scheduling time, scheduling cost, and system resource utilization of task set. The implementation steps of the algorithm are given in detail. Finally, the simulation experiment is carried out on Cloud Sim platform. The experimental results show that computing resourceM is 10, subtask N is 2000, population size S is 80, and ETC matrix and RCU array are randomly generated by the system. As the number of iterations increases, the scheduling scheme formed by MCGA and CGA is more obvious and close to the subtask execution cost optimization. Finally, the optimized scheme is basically formed. However, the scheduling scheme formed by TGA has no obvious optimization effect on the subtask execution cost. It is proved that the algorithm proposed in this paper can effectively optimize the task scheduling efficiency and improve the utilization of cloud computing resources at the same time, providing a feasible idea and method for task scheduling in the cloud computing environment.


---

## Body

## 1. Introduction

Since the beginning of the 21st century, the network technology has undergone tremendous changes, and the development of information and service industry has become increasingly mature. The Internet age was born as people grew dissatisfied with the weak processing power of mainframe computing and personal computers and wanted to connect as many computers as possible. Under the computing model of the internet, the application programs are deployed centrally, and the operation management of the system is simplified [1]. More importantly, a variety of pure services and software as a service (SAAS) are beginning to emerge and gain acceptance. It was the emergence of software as a service that unveiled the mystery of cloud computing [2]. Virtualization technology is playing an increasingly important role in cloud computing applications. It can integrate network devices, storage servers, computer clusters, and a large number of applications in different locations and regions into a collaborative resource pool. This mature application facilitates users to provide efficient performance, simple mode, easy to expand, stable, and reliable computing and storage services. For the user of cloud computing system, he does not need to know where the resources he uses come from but only needs a simple link and a client-side way to buy the cloud computing resources or cloud computing service information he wants according to his own needs [3]. Users use this information based on the amount of use, according to the need to pay (Figure 1).Figure 1
Cloud computing task scheduling model.


## 2. Literature Review

Cloud computing has a lot in common with grid computing. Many scholars have tried to explore the feasibility of resource scheduling in cloud environment by using resource scheduling algorithms in grid environment [4]. For resource scheduling in distributed environment such as grid, many scholars at home and abroad have done a lot of research and proposed a lot of resource scheduling strategies and algorithms. The essence of resource scheduling is to allocate tasks to appropriate resources so that the task completion time is as little as possible, and the resource utilization is as high as possible on the premise of meeting the QoS requirements of users [5]. The min-min algorithm calculates the minimum completion time of each task and then selects the resource with the minimum time from all the resources with the minimum completion time to match it with the task. After the max-min algorithm obtains the minimum completion time of each task, the resource with the largest minimum completion time is selected from the resources, and then the task is matched with computing resources [5]. Sreenu and Sreelatha introduced a grid computing task scheduling algorithm based on genetic algorithm, whose purpose is to improve resource utilization and throughput as much as possible [6, 7]. Elaziz et al.’s cloud computing scheduling strategy is proposed based on MPSO algorithm, in view of the cloud computing service cluster resource scheduling and load balancing optimization problem, the dynamic variation particle group collaboration and reverse flight thought are introduced into the particle swarm optimization algorithm, so as to control the global search and local search, try to avoid falling into local optimum (Figure 2) [8]. Huang et al., in view of the shortcomings of genetic algorithm, proposed an improved algorithm to optimize scheduling and considered using the genetic algorithm with double fitness function to find the nodes where the average time and total time of task scheduling were smaller [9]. Based on this, this paper proposes a method based on genetic algorithm in cloud computing environment. First, independent task scheduling algorithms and associated task scheduling algorithms commonly used in cloud computing are studied and compared, respectively. Second, an independent task scheduling strategy based on multipopulation genetic algorithm is proposed for independent task scheduling in cloud environment, considering the scheduling time, scheduling cost, and system resource utilization of task set. It is proved that the algorithm proposed in this paper can effectively optimize the task scheduling efficiency and improve the utilization of cloud computing resources at the same time, providing a feasible idea and method for task scheduling in the cloud computing environment.Figure 2
Cloud computing scheduling framework based on MPSO algorithm.


## 3. Cloud Computing Task Scheduling

### 3.1. Description of Task Scheduling Problems in Cloud Computing Environment

Currently, most cloud computing environments adopt the Map/Reduce programming model proposed by Google. This programming pattern is divided into two stages: Map (mapping) and Reduce (reduction) [10]. Through these two stages, a large task in the task set is decomposed into several smaller tasks, which are then assigned to several virtual resource nodes such as for execution, and finally, the running results are returned. How to dispatch the decomposed tasks reasonably without changing the service level agreement (SLA), on the one hand, these tasks can meet the basic QoS requirements of users, including resource utilization rate, quality of service, completion time, economic benefit, and other indicators; on the other hand, the time span of task execution should be shortened accordingly [11]. Finally, it is critical to increase the resource utilization of cloud computing platform as much as possible.To clarify the scheduling problem in the cloud computing environment, the task scheduling problem in the cloud computing environment can be described as follows: in the cloud computing environment,n independent subtasks are assigned to M VM nodes for execution [12]. Where task set T=subtask1,subtask2,subtask3,⋯,subtaskn and VM resource node VM=vm1,vm2,⋯,vmm,subtaskjj=1,2,⋯,n represent the JTH task, and VMii=1,2,⋯,m represent the ith VM resource. The allocation relationship between task set T and virtual resource nodes can be expressed by sparse matrix δ:
(1)δ=subtusk1,2,⋯,nVM1,2,⋯,m.Cloud computing uses virtualization technology to virtualize VMS of different types and performance from nodes and schedule VM resources to perform user tasks. This step is transparent to the user, who feels like he or she is monopolizing a machine [13].The total working time of VMpi is the sum of the time required by VM pi to complete all tasks assigned to VM pi, denoted as sumTimepi, and vx refers to pi task assigned to VM pi. For the task request set submitted by users, multiple VMS in the data center process the task set in parallel. Therefore, M VMS is parallel on the time axis. The totalTime spent on processing the task set is the maximum working time of all VMS, denoted as totalTime.
(2)sumTimepi=∑vx∈VETCi,x,(3)totalTime=maxi=1MsumTimepi.When taking the optimal time span and cost control as the optimization objective, task scheduling needs to reasonably configure the task set in view of the fact that tasks are independent from each other, and at the same time ensure a low task completion time and execution cost [14].


### 3.2. Cloud Computing Task Scheduling Optimization

The urgent need for data processing power and the booming development of the Internet directly gave birth to cloud computing. As a business computing model, cloud computing provides computing power and other services to users as commodities through the Internet, so that users can obtain computing power, storage, and bandwidth on demand, and then pay according to the set pricing model [15]. In the cloud computing environment, a large number of heterogeneous resources are centralized to form a virtual resource set. This resource aggregation method eliminates the differences between software and hardware of heterogeneous servers by virtue of virtualization technology and virtualizes computing resources into virtual resource pools that can be arbitrarily combined and allocated according to user requirements. The size of the pool can be dynamically expanded according to the changes of applications and user scale [16]. In addition, the resource pool can obtain certain autonomy through software, enabling it to self-maintain and manage virtual computing resources without human participation. These resource pools are also called “clouds” because of their large scale, no specific form, and flexible dynamic expansion. This management mode of cloud computing greatly improves the utilization of resources and reduces the cost of cloud data center operation and management, thus attracting wide attention [17].The task scheduling problem in cloud computing environment is a problem. Based on the particularity of cloud environment, this chapter designs a scheduling system framework in cloud computing environment. The overall architecture of task scheduling in the cloud computing environment consists of users, datacenters, and cloud information services. The overall framework of task scheduling in the cloud computing environment is shown in Figure3.Figure 3
Overall frame diagram of task scheduling in cloud computing environment.According to the above scheduling framework diagram, some terms in the scheduling framework are explained below:(1)
Users. As the name suggests, it refers to people who use cloud services(2)
Task Set. A collection of all tasks submitted by the user(3)
Task Queue. Is a critical step to complete a specific operation that controls the behavior of a task at run time [18]The time span of scheduling is the most intuitive criterion to measure the performance of scheduling algorithm and is the primary function to be considered when designing and implementing scheduling algorithm. On the basis of ensuring a reasonable scheduling length, the scheduling cost of the task set can be appropriately controlled to improve the economics of task scheduling [19]. Considering the actual application requirements, this paper tries to comprehensively consider the optimal scheduling length and cost control of the task set by means of weighting and takes the load of virtual machines as the evaluation and screening basis of the scheduling scheme, so as to ensure the load balance of the system to a certain extent. As it overlapped with the selected optimization objective and the requirements were slightly complex, this paper did not consider the QoS optimization objective [20, 21].


### 3.3. Algorithm Implementation

Darwin’s theory of biological evolution is the ideological source of genetic algorithm, and the principle of the algorithm is to follow the “survival of the fittest” and “superior slightly out.” Genetic algorithm is a simulation of an artificial population evolution process, and through the selection, hybridization, and variation mechanisms, the population after several generations always reaches the optimal (or nearly optimal) state [22]. The overall flow of the algorithm is shown in Figure 4.Figure 4
Flowchart of genetic algorithm.As can be seen from Figure1, the algorithm can be roughly divided into encoding and decoding, calculation of fitness value, selection, crossover, mutation, and other major steps. The following is a detailed description of each step.
(1)
Encoding and decodingThe encoding problem is the first problem to be solved by the heritage algorithm. Usually, real coding and binary coding are used in two ways, each of which has its own advantages. The advantages of binary coding are high stability, large population diversity, but the storage space is large, and decoding process is difficult to understand. The real code is easy to understand and there is no decoding process, using real numbers to represent the gene is more convenient and concise [23]. In this paper, real-number coding is adopted for chromosome coding. The number of subtasks is the length of the chromosome, and the number of computing resources occupied by subtasks is represented by the value of each gene in the chromosome, as shown in Figure 2.Combined with Figure5, it can be seen that N tasks are scheduled to M computing resources, and the number of these N tasks is T1,T2,⋯,Ti,⋯TN;. M computing resources are numbered R1,R2,⋯,RM. In this case, the number of tasks N is much larger than the number of resources M. An example is given in Figure 5. The chromosome length is the number of tasks N, and these N tasks correspond to different computing resources. Then, the chromosome decoding is shown in the dotted box in Figure 5.
(4)R:T1,Ti+1,⋯,R2:T2,Ti+2,⋯,R3:T3,Ti+3,⋯.Figure 5
Task scheduling chromosome coding.Through the decoded sequence of chromosome,ETCi,j matrix, and RCUj sequence, the time and cost required for each computing resource to perform all subtasks on the resource (M) can be calculated:
(5)TimeM=∑i=1TotalETCi,M,(6)CostM=RCUM×TimeM.Then, the total time function and total cost function of the resource scheduling scheme formed by this chromosome coding to complete all tasks are(7)Timetotal=maxj=1M∑i=1TotalETCi,M,(8)Costtotal=∑j=1MRCUM×TimeM.(2)
Selection of fitness functionTraditional genetic algorithm takes a single target for the design of fitness function, such as most of the function optimization problem can be seen as the maximum or minimum value of form, but in the cloud resource environment resource scheduling problem, the cloud resource providers and users pay attention to the content of the different, and the selection of fitness function is different. In this paper, multiobjective optimization-oriented cloud resource scheduling is studied [24]. Four objectives, namely, completion time, cost, CPU utilization, and memory utilization, are selected to quantify the satisfaction degree of resource scheduling. In resource allocation and scheduling, consider the overall load of resource clusters. Resource cluster K contains M computing resources. The cluster load includes CPU load, memory load, and network load.Set the CPU load of resource clusterK at time T to ldcpukt. The calculation formula is as follows:
(9)ldcpukt=1N∑j=1N∑i=1ncpuusedkitm∑i=1ncpuki.Let the memory load of application clusterK at time T be ldmemkt, and the calculation formula is as follows:
(10)ldmemkt=1N∑j=1N∑i=1nmemusedkitm∑i=1nmemki.Let the network load of application clusterK at time T be ldnetkt:
(11)ldnetkt=1N∑j=1N∑i=1nnetusedkitm∑i=1nnetki,whereN indicates the number of times that monitoring data is collected within Δt time. cpuki,memki,netki indicate the CPU, memory, and network capacity of the I the computing resource of cluster K. cpuusedkitm,memusedkitm,netusedkitm indicate the CPU usage, memory usage, and network usage of the I the computing resource in cluster K at the time of TM monitoring [25]. Because we can conclude that the lower the total running time and total cost of all tasks is, the better, and the cluster CPU, memory, and bandwidth utilization are best maximized. Therefore, we give the fitness function of resource scheduling as follows:
(12)f=−ω1Timetotal−ω2Costtotal+ω3ldcpu+ω4ldmem+ω5ldnet.In the formula,Timetotal represents the total running time of the task, Costtotal represents the total running cost of the task, ldcpu represents the CPU utilization, ldmem represents the memory utilization, and ldnet represents the bandwidth utilization. ω1,ω2,ω3,ω4,ω5 represent the weight coefficient, and 0≤ωi≤1,∑i=15ωi=1.
(3)
Cross operationsIn order to ensure and enhance the global search ability of genetic algorithm, it is necessary to conduct crossover operation between two individuals in the population, that is, exchange the gene positions and values of two individuals. Set the crossover probability ascorss_rate, and adopt formulas (10) and (11) for adaptive adjustment of the crossover probability.
(13)corss_rate=k1fmax−f′fmax−f¯,f′≥f¯,(14)corss_rate=k2,f′≥f¯.In the equation,corss_rate represents the crossover probability, fmax represents the maximum fitness value of the population, f′ represents the larger fitness value of the two individuals to be crossed, and f¯ represents the average fitness value of the generation population. k1,k2 are the coefficient between 0 and 1. When the fitness function value is large, the crossover probability should be small, which can not only prevent individuals with large fitness from being destroyed but also speed up population convergence. However, when the fitness function value is small, the crossover probability should be higher, so that new individuals can be recombined. Therefore, k1=0.32,k2=0.75 is set in this paper. At the same time, this paper adopts the way of two-point crossover to carry on the chromosome body crossover operation, and the intersection point is randomly selected.
(4)
Mutation operationMutation operation is carried out on a single individual, which can improve the local search ability of genetic algorithm, maintain the diversity of population, and prevent the phenomenon of early maturity. Let the mutation probabilitymutate_rate, which is adaptive adjusted by the following formula.
(15)mutate_rate=k3fmax−f′fmax−f¯,f′≥f¯,(16)mutate_rate=k4,f′≥f¯.In the formula,mutate_rate represents the mutation probability, fmax represents the maximum fitness value of the population, f represents the fitness value of the individual to be changed, and f represents the average fitness value of the generation population. k3,k4 are the coefficient between 0 and 1, and the probability of variation is generally between 0.0001 and 0.1. Therefore, k3=0.08,k4=0.05 are set in this paper.
(5)
Convergence conditionsThe standard deviation of the fitness function value of the optimal span is adopted to judge the termination condition, as shown in formula (15):
(17)∑i=1Sfi−f¯2S<ξ;ξ∈0,1,whereS represents the population size, fi represents the fitness value of the ith individual of the population of this generation, f¯ represents the average fitness value of the population of this generation, and ξ represents the convergence threshold. In this paper, ξ=0.1 is taken to mean that the algorithm iteration is terminated when the standard deviation is less than 0.1, and the genetic evolution of the population continues if this condition is not met.


## 3.1. Description of Task Scheduling Problems in Cloud Computing Environment

Currently, most cloud computing environments adopt the Map/Reduce programming model proposed by Google. This programming pattern is divided into two stages: Map (mapping) and Reduce (reduction) [10]. Through these two stages, a large task in the task set is decomposed into several smaller tasks, which are then assigned to several virtual resource nodes such as for execution, and finally, the running results are returned. How to dispatch the decomposed tasks reasonably without changing the service level agreement (SLA), on the one hand, these tasks can meet the basic QoS requirements of users, including resource utilization rate, quality of service, completion time, economic benefit, and other indicators; on the other hand, the time span of task execution should be shortened accordingly [11]. Finally, it is critical to increase the resource utilization of cloud computing platform as much as possible.To clarify the scheduling problem in the cloud computing environment, the task scheduling problem in the cloud computing environment can be described as follows: in the cloud computing environment,n independent subtasks are assigned to M VM nodes for execution [12]. Where task set T=subtask1,subtask2,subtask3,⋯,subtaskn and VM resource node VM=vm1,vm2,⋯,vmm,subtaskjj=1,2,⋯,n represent the JTH task, and VMii=1,2,⋯,m represent the ith VM resource. The allocation relationship between task set T and virtual resource nodes can be expressed by sparse matrix δ:
(1)δ=subtusk1,2,⋯,nVM1,2,⋯,m.Cloud computing uses virtualization technology to virtualize VMS of different types and performance from nodes and schedule VM resources to perform user tasks. This step is transparent to the user, who feels like he or she is monopolizing a machine [13].The total working time of VMpi is the sum of the time required by VM pi to complete all tasks assigned to VM pi, denoted as sumTimepi, and vx refers to pi task assigned to VM pi. For the task request set submitted by users, multiple VMS in the data center process the task set in parallel. Therefore, M VMS is parallel on the time axis. The totalTime spent on processing the task set is the maximum working time of all VMS, denoted as totalTime.
(2)sumTimepi=∑vx∈VETCi,x,(3)totalTime=maxi=1MsumTimepi.When taking the optimal time span and cost control as the optimization objective, task scheduling needs to reasonably configure the task set in view of the fact that tasks are independent from each other, and at the same time ensure a low task completion time and execution cost [14].


## 3.2. Cloud Computing Task Scheduling Optimization

The urgent need for data processing power and the booming development of the Internet directly gave birth to cloud computing. As a business computing model, cloud computing provides computing power and other services to users as commodities through the Internet, so that users can obtain computing power, storage, and bandwidth on demand, and then pay according to the set pricing model [15]. In the cloud computing environment, a large number of heterogeneous resources are centralized to form a virtual resource set. This resource aggregation method eliminates the differences between software and hardware of heterogeneous servers by virtue of virtualization technology and virtualizes computing resources into virtual resource pools that can be arbitrarily combined and allocated according to user requirements. The size of the pool can be dynamically expanded according to the changes of applications and user scale [16]. In addition, the resource pool can obtain certain autonomy through software, enabling it to self-maintain and manage virtual computing resources without human participation. These resource pools are also called “clouds” because of their large scale, no specific form, and flexible dynamic expansion. This management mode of cloud computing greatly improves the utilization of resources and reduces the cost of cloud data center operation and management, thus attracting wide attention [17].The task scheduling problem in cloud computing environment is a problem. Based on the particularity of cloud environment, this chapter designs a scheduling system framework in cloud computing environment. The overall architecture of task scheduling in the cloud computing environment consists of users, datacenters, and cloud information services. The overall framework of task scheduling in the cloud computing environment is shown in Figure3.Figure 3
Overall frame diagram of task scheduling in cloud computing environment.According to the above scheduling framework diagram, some terms in the scheduling framework are explained below:(1)
Users. As the name suggests, it refers to people who use cloud services(2)
Task Set. A collection of all tasks submitted by the user(3)
Task Queue. Is a critical step to complete a specific operation that controls the behavior of a task at run time [18]The time span of scheduling is the most intuitive criterion to measure the performance of scheduling algorithm and is the primary function to be considered when designing and implementing scheduling algorithm. On the basis of ensuring a reasonable scheduling length, the scheduling cost of the task set can be appropriately controlled to improve the economics of task scheduling [19]. Considering the actual application requirements, this paper tries to comprehensively consider the optimal scheduling length and cost control of the task set by means of weighting and takes the load of virtual machines as the evaluation and screening basis of the scheduling scheme, so as to ensure the load balance of the system to a certain extent. As it overlapped with the selected optimization objective and the requirements were slightly complex, this paper did not consider the QoS optimization objective [20, 21].


## 3.3. Algorithm Implementation

Darwin’s theory of biological evolution is the ideological source of genetic algorithm, and the principle of the algorithm is to follow the “survival of the fittest” and “superior slightly out.” Genetic algorithm is a simulation of an artificial population evolution process, and through the selection, hybridization, and variation mechanisms, the population after several generations always reaches the optimal (or nearly optimal) state [22]. The overall flow of the algorithm is shown in Figure 4.Figure 4
Flowchart of genetic algorithm.As can be seen from Figure1, the algorithm can be roughly divided into encoding and decoding, calculation of fitness value, selection, crossover, mutation, and other major steps. The following is a detailed description of each step.
(1)
Encoding and decodingThe encoding problem is the first problem to be solved by the heritage algorithm. Usually, real coding and binary coding are used in two ways, each of which has its own advantages. The advantages of binary coding are high stability, large population diversity, but the storage space is large, and decoding process is difficult to understand. The real code is easy to understand and there is no decoding process, using real numbers to represent the gene is more convenient and concise [23]. In this paper, real-number coding is adopted for chromosome coding. The number of subtasks is the length of the chromosome, and the number of computing resources occupied by subtasks is represented by the value of each gene in the chromosome, as shown in Figure 2.Combined with Figure5, it can be seen that N tasks are scheduled to M computing resources, and the number of these N tasks is T1,T2,⋯,Ti,⋯TN;. M computing resources are numbered R1,R2,⋯,RM. In this case, the number of tasks N is much larger than the number of resources M. An example is given in Figure 5. The chromosome length is the number of tasks N, and these N tasks correspond to different computing resources. Then, the chromosome decoding is shown in the dotted box in Figure 5.
(4)R:T1,Ti+1,⋯,R2:T2,Ti+2,⋯,R3:T3,Ti+3,⋯.Figure 5
Task scheduling chromosome coding.Through the decoded sequence of chromosome,ETCi,j matrix, and RCUj sequence, the time and cost required for each computing resource to perform all subtasks on the resource (M) can be calculated:
(5)TimeM=∑i=1TotalETCi,M,(6)CostM=RCUM×TimeM.Then, the total time function and total cost function of the resource scheduling scheme formed by this chromosome coding to complete all tasks are(7)Timetotal=maxj=1M∑i=1TotalETCi,M,(8)Costtotal=∑j=1MRCUM×TimeM.(2)
Selection of fitness functionTraditional genetic algorithm takes a single target for the design of fitness function, such as most of the function optimization problem can be seen as the maximum or minimum value of form, but in the cloud resource environment resource scheduling problem, the cloud resource providers and users pay attention to the content of the different, and the selection of fitness function is different. In this paper, multiobjective optimization-oriented cloud resource scheduling is studied [24]. Four objectives, namely, completion time, cost, CPU utilization, and memory utilization, are selected to quantify the satisfaction degree of resource scheduling. In resource allocation and scheduling, consider the overall load of resource clusters. Resource cluster K contains M computing resources. The cluster load includes CPU load, memory load, and network load.Set the CPU load of resource clusterK at time T to ldcpukt. The calculation formula is as follows:
(9)ldcpukt=1N∑j=1N∑i=1ncpuusedkitm∑i=1ncpuki.Let the memory load of application clusterK at time T be ldmemkt, and the calculation formula is as follows:
(10)ldmemkt=1N∑j=1N∑i=1nmemusedkitm∑i=1nmemki.Let the network load of application clusterK at time T be ldnetkt:
(11)ldnetkt=1N∑j=1N∑i=1nnetusedkitm∑i=1nnetki,whereN indicates the number of times that monitoring data is collected within Δt time. cpuki,memki,netki indicate the CPU, memory, and network capacity of the I the computing resource of cluster K. cpuusedkitm,memusedkitm,netusedkitm indicate the CPU usage, memory usage, and network usage of the I the computing resource in cluster K at the time of TM monitoring [25]. Because we can conclude that the lower the total running time and total cost of all tasks is, the better, and the cluster CPU, memory, and bandwidth utilization are best maximized. Therefore, we give the fitness function of resource scheduling as follows:
(12)f=−ω1Timetotal−ω2Costtotal+ω3ldcpu+ω4ldmem+ω5ldnet.In the formula,Timetotal represents the total running time of the task, Costtotal represents the total running cost of the task, ldcpu represents the CPU utilization, ldmem represents the memory utilization, and ldnet represents the bandwidth utilization. ω1,ω2,ω3,ω4,ω5 represent the weight coefficient, and 0≤ωi≤1,∑i=15ωi=1.
(3)
Cross operationsIn order to ensure and enhance the global search ability of genetic algorithm, it is necessary to conduct crossover operation between two individuals in the population, that is, exchange the gene positions and values of two individuals. Set the crossover probability ascorss_rate, and adopt formulas (10) and (11) for adaptive adjustment of the crossover probability.
(13)corss_rate=k1fmax−f′fmax−f¯,f′≥f¯,(14)corss_rate=k2,f′≥f¯.In the equation,corss_rate represents the crossover probability, fmax represents the maximum fitness value of the population, f′ represents the larger fitness value of the two individuals to be crossed, and f¯ represents the average fitness value of the generation population. k1,k2 are the coefficient between 0 and 1. When the fitness function value is large, the crossover probability should be small, which can not only prevent individuals with large fitness from being destroyed but also speed up population convergence. However, when the fitness function value is small, the crossover probability should be higher, so that new individuals can be recombined. Therefore, k1=0.32,k2=0.75 is set in this paper. At the same time, this paper adopts the way of two-point crossover to carry on the chromosome body crossover operation, and the intersection point is randomly selected.
(4)
Mutation operationMutation operation is carried out on a single individual, which can improve the local search ability of genetic algorithm, maintain the diversity of population, and prevent the phenomenon of early maturity. Let the mutation probabilitymutate_rate, which is adaptive adjusted by the following formula.
(15)mutate_rate=k3fmax−f′fmax−f¯,f′≥f¯,(16)mutate_rate=k4,f′≥f¯.In the formula,mutate_rate represents the mutation probability, fmax represents the maximum fitness value of the population, f represents the fitness value of the individual to be changed, and f represents the average fitness value of the generation population. k3,k4 are the coefficient between 0 and 1, and the probability of variation is generally between 0.0001 and 0.1. Therefore, k3=0.08,k4=0.05 are set in this paper.
(5)
Convergence conditionsThe standard deviation of the fitness function value of the optimal span is adopted to judge the termination condition, as shown in formula (15):
(17)∑i=1Sfi−f¯2S<ξ;ξ∈0,1,whereS represents the population size, fi represents the fitness value of the ith individual of the population of this generation, f¯ represents the average fitness value of the population of this generation, and ξ represents the convergence threshold. In this paper, ξ=0.1 is taken to mean that the algorithm iteration is terminated when the standard deviation is less than 0.1, and the genetic evolution of the population continues if this condition is not met.


## 4. Experimental Results and Analysis

The cloud computing simulation tool Cloud Sim was used for the experimental simulation. Under the same environment and conditions, the TGA (time constraints GA) and CGA (cost constraints GA) algorithms of MCGA proposed in this paper were compared and tested.If the fitness value of the optimal individual in the elite population can keep a certain algebraic unchanged, the algorithm can be considered as converging. At this point, the iteration terminates, and the corresponding optimal solution is output. In addition, to avoid excessive search, an upper limit is usually set on the evolutionary algebra of the algorithm, and when the iteration reaches this upper limit, the algorithm is forced to terminate. In the experiment in this section, the maximum evolution algebra of the algorithm is set as 150 generations, and the minimum preservation algebra of the optimal individual is set as 10 generations.The initial conditions of the algorithm are as follows: computing resourceM is 10, subtask N is 2000, population size S is 80, and ETC matrix and RCU array are randomly generated by the system. In this paper, the time and cost required for the execution of the total task are selected as the results for display. The experimental results are shown in Figures 6 and 7.Figure 6
Comparison of total task completion time.Figure 7
Comparison of total task completion costs.As can be seen from Figure3, at the beginning, the optimal scheduling scheme obtained by running the algorithm MCGA, TGA, and CGA in this paper has little difference in the completion time required to execute subtasks. As the number of iterations increases, the optimal subtask scheduling scheme formed by MCGA and TGA is more obvious to optimize the total time required for executing subtasks, and finally, the optimal solution is basically reached. However, the scheduling scheme formed by CGA has no obvious optimization effect.Also, it can be seen from Figure4 that, in the early stage of algorithm iteration, the scheduling scheme formed by algorithm MCGA, TGA, and CGA in this paper has almost the same cost for performing subtasks. However, with the increase of the number of iterations, the scheduling scheme formed by MCGA and CGA is more obvious and close to the optimization of subtask execution cost, and finally, the optimal scheme is basically formed. However, the scheduling scheme formed by TGA has no obvious optimization effect on the execution cost of subtasks. Through comparison, it can be seen that the improved genetic algorithm proposed in this paper considers time, cost, and other factors at the same time, so that the cloud resource scheduling has a good effect in terms of time and cost constraints and can meet the needs of cloud resource providers and users [26].In this paper, the cloud computing environment is simulated by Matlab. In order to verify the effectiveness of the algorithm proposed in this paper in large-scale graph task scheduling, the comparison experiment between CETS and other algorithms is given in this section. Related parameter settings of the experiment, where represents the population number set in the multipopulation algorithm, CVz/MIC bar and M/RAD are randomly generated by the system. If the fitness value of the optimal individual in the elite population remains unchanged for 10 generations, the algorithm can be considered to have converged and terminated accordingly. In addition, the algorithm will be forced to terminate if the iteration reaches 150 generations.


## 5. Conclusion

The first level is the scheduling from task set to virtual machine set, and the other level is the scheduling from virtual machine set to physical machine set. This paper mainly studies the task scheduling on the first level. At this level, the scheduling object is a small granularity task set formed by segmentation, and the task scheduling strategy is to seek the mapping relationship between this task set and the virtual resource set available on the cloud platform. With the emergence of cloud computing, resource allocation and scheduling in cloud data centers have become an important factor determining the efficiency of cloud computing, and the cloud resource scheduling has become a hot topic of research. In this paper, on the basis of genetic algorithm, by improving the execution process of genetic algorithm, to scheduling task completion time, cost, CPU utilization, memory bandwidth utilization five goals to quantify the satisfaction of resource scheduling, forming a cloud resource scheduling research plan, and USES the Cloud Sim platform conducts a practical analysis to simulate the cloud computing environment. The experimental results show that the improved genetic algorithm in this paper has a better effect in cloud resource scheduling, achieving more reasonable task scheduling, and producing ideal task scheduling results. In the next work, the resource load balancing of dynamic task scheduling in cloud computing will be the focus of our research. Combined with cloud resource scheduling policies and algorithms under SLA constraints, a multipolicy cloud resource scheduling study will be carried out.



---

*Source: 3382273-2022-06-11.xml*