针对数据中心规模和任务需求不断增加带来的服务效率降低等问题，提出了一种负载均衡多群落粒子群优化任务调度方法。通过改进的适应度函数对任务的最大完工时间和各机器完工时间方差进行组合优化以提升集群的负载均衡性；利用新的自适应惯性权重函数改进粒子搜索效率，提升算法收敛速率；采取新的粒子初始化方法提高初始解的质量和多样性，并利用多群落粒子协同搜索使得最终结果更加接近最优解。在阿里巴巴数据中心的公开数据集上对算法性能进行了验证和对比，实验结果表明，该方法能够提高数据中心在多样化供应链环境下的任务调度效率。
In order to deal with the problems of low service efficiency brought by the increasing scale of datacenters and task demands, a load balancing multi-swarm PSO task scheduling approach is proposed. Through the improved fitness function, the maximum completion time of the task and the variance of the completion time among machines are optimized to improve the cluster’s load balance. A novel adaptive inertia weights method is designed to enhance particle search efficiency and algorithm convergence speed. Meanwhile, a new particle initialization method is adopted to improve the quality and diversity of the initial solution. Multi-swarm particle collaborative search is further used to bring the final result closer to the optimal solution. The performance of the proposed algorithm is verified and compared with others based on the public dataset of Alibaba datacenter. The experimental results show that the method can improve task scheduling efficiency of datacenters in diversified supply chain environments.
[1] Bouhannana F, Elkorchi A. Trade-offs among lean, green and agile concepts in supply chain management: literature review [C]//2020 IEEE 13th International Colloquium of Logistics and Supply Chain Management (LOGISTIQUA). IEEE, 2020: 1-5.
[2] 靳紫薇, 郭会明, 焦函. 云边环境下的任务调度算法研究综述[J]. 现代计算机, 2022, 28(4): 38-44. Jin Z W, Guo H M, Jiao H. A survey of task scheduling algorithms in cloud-edge environments [J]. Modern Computer, 2022, 28(4): 38-44. (in Chinese)
[3] Li B, Chen R S, Liu C Y. Using intelligent technology and real-time feedback algorithm to improve manufacturing process in IoT semiconductor industry [J]. The Journal of Supercomputing, 2021, 77(5): 4639-4658.
[4] 吴誉兰, 黄卫. 基于资源延迟感知的云计算实时任务调度仿真[J]. 计算机仿真, 2021, 38(9): 490- 494. Wu Y L, Huang W. Simulation of real-time task scheduling in cloud computing based on resource delay awareness [J]. Computer Simulation, 2021, 38(9): 490-494. (in Chinese)
[5] Liu Q, Mo R, Xu X, et al. Multi-objective resource allocation in mobile edge computing using PAES for Internet of things [J]. Wireless Networks, 2020: 1-13.
[6] Kumar M, Sharma S C, Goel A, et al. A comprehensive survey for scheduling techniques in cloud computing [J]. Journal of Network and Computer Applications, 2019, 143: 1-33.
[7] 田倬璟, 黄震春, 张益农. 云计算环境任务调度方法研究综述[J]. 计算机工程与应用, 2021, 57(2): 1-11. Tian Z J, Huang Z C, Zhang Y N. A survey of research on task scheduling methods in cloud computing environments [J]. Computer Engineering and Applications, 2021, 57(2): 1-11. (in Chinese)
[8] Shan H, Li Y, Shi J. Influence of supply chain collaborative innovation on sustainable development of supply chain: a study on Chinese enterprises [J]. Sustainability, 2020, 12(7): 2978.
[9] Sangari M S, Mashatan A. A data-driven, comparative review of the academic literature and news media on blockchain-enabled supply chain management: trends, gaps, and research needs [J]. Computers in Industry, 2022, 143: 103769.
[10] Ujazdowski T, Piotrowski R. Task scheduling-review of algorithms and analysis of potential use in a biological wastewater treatment plant [J]. IEEE Access, 2022, 10: 45230-45240.
[11] 许小龙, 方子介, 齐连永. 车联网边缘计算环境下基于深度强化学习的分布式服务卸载方法[J]. 计算机学报, 2021, 44(12): 2382-2405. Xu X L, Fang Z J, Qi L Y. Distributed service offloading method based on deep reinforcement learning in the edge computing environment of the Internet of vehicles [J]. Chinese Journal of Computers, 2021, 44(12): 2382-2405. (in Chinese)
[12] Mahmud S, Abbasi A, Chakrabortty R K, et al. A self-adaptive hyper-heuristic based multi-objective optimization approach for integrated supply chain scheduling problems [J]. Knowledge-Based Systems, 2022: 109190.
[13] Gao C, Lee V C S, Li K. D-SRTF: distributed shortest remaining time first scheduling for data center networks [J]. IEEE Transactions on Cloud Computing, 2018, 9(2): 562-575.
[14] Ajayi O, Oladeji F, Uwadia C, et al. Scheduling cloud workloads using carry-on weighted round robin [C]//International Conference on e-Infrastructure and e-Services for Developing Countries. Cham: Springer, 2017: 60-71.
[15] Shirvani M H, Talouki R N. A novel hybrid heuristic-based list scheduling algorithm in heterogeneous cloud computing environment for makespan optimization [J]. Parallel Computing, 2021, 108: 102828.
[16] Wu D. Cloud computing task scheduling policy based on improved particle swarm optimization [C]//2018 International Conference on Virtual Reality and Intelligent Systems (ICVRIS). IEEE, 2018: 99-101.
[17] Alsaidy S A, Abbood A D, Sahib M A. Heuristic initialization of PSO task scheduling algorithm in cloud computing [J]. Journal of King Saud University-Computer and Information Sciences, 2022, 34(6): 2370-2382.
[18] Dubey K, Sharma S C. A novel multi-objective CR-PSO task scheduling algorithm with deadline constraint in cloud computing [J]. Sustainable Computing: Informatics and Systems, 2021, 32: 100605
[19] Meziani N, Boudhar M, Oulamara A. PSO and simulated annealing for the two-machine flowshop scheduling problem with coupled-operations [J]. European Journal of Industrial Engineering, 2018, 12(1): 43-66.
[20] Liu S, Liu W, Huang F, et al. Multi-target allocation strategy based on adaptive SA-PSO algorithm [J]. The Aeronautical Journal, 2022: 1-13.
[21] Wang Z, Tian J, Feng K. Optimal allocation of regional water resources based on simulated annealing particle swarm optimization algorithm [J]. Energy Reports, 2022, 8: 9119-9126.
[22] Jiang C, Han G, Lin J, et al. Characteristics of co-allocated online services and batch jobs in internet data centers: a case study from Alibaba cloud [J]. IEEE Access, 2019, 7: 22495-22508.
[23] Guo J, Chang Z, Wang S, et al. Who limits the resource efficiency of my datacenter: an analysis of Alibaba datacenter traces [C]//Proceedings of the International Symposium on Quality of Service. 2019: 1-10.
[24] Wu H, Zhang W, Xu Y, et al. Aladdin: optimized maximum flow management for shared production clusters [C]//2019 IEEE International Parallel and Distributed Processing Symposium (IPDPS). IEEE, 2019: 696-707.
