An Efficient Task Scheduling Algorithm Based on Particle Swarm Optimization with Self-Learning Strategy and Neighbor Heuristic Mechanism on the Cloud

Lili Fan ； Minggang Dong ； Chao Jing

《電腦學刊》 31卷2期 (2020/04) Pp. 180-196

https://doi.org/10.3966/199115992020043102016

摘要

Task scheduling plays an important role for improving the efficiency of cloud. However, due to the features and complex scenarios of the cloud, traditional scheduling approaches face with three challenges: robust model, local optima and slow convergence. Therefore, in this paper, we firstly established a robust cloud task scheduling model, which takes heterogeneity, deadline, overheads of transmission and the cost into account. Then, we proposed a particle swarm optimization scheduling algorithm with the self-learning strategy and the neighbor heuristic mechanism. The self-learning strategy is adopted to improve the diversity of population and the neighbor heuristic mechanism can accelerate the convergence speed. In addition, a greedy policy was designed and applied to quickly improve the quality of the initial solutions. In this way, the proposed algorithm has a fast speed of convergence and can avoid trapping into the local optimum. Lastly, we conducted simulations on CloudSim platform. Both on small-scale and large-scale scheduling problems, the proposed scheduling approach outperforms other well-known representative scheduling algorithms in terms of makespan, users' expense and waiting time.

關鍵字

cloud computing ； neighbor heuristic ； particle swarm optimization ； self-learning ； task scheduling