多群落粒子群优化供应链数据中心任务调度

doi:10.3969/j.issn.0255-8297.2023.03.005

应用科学学报 ›› 2023, Vol. 41 ›› Issue (3): 419-430.doi: 10.3969/j.issn.0255-8297.2023.03.005

多群落粒子群优化供应链数据中心任务调度

曾磊¹, 白金明², 刘琦³

1. 南京信息工程大学计算机学院, 江苏南京 210044;
2. 南京信息工程大学应用气象学院, 江苏南京 210044;
3. 南京信息工程大学数字取证工程研究中心, 江苏南京 210044

收稿日期:2022-10-28 出版日期:2023-05-30 发布日期:2023-06-16
通信作者: 刘琦,教授,博导,研究方向为物联网、云计算与大数据。E-mail:qi.liu@nuist.edu.cn E-mail:qi.liu@nuist.edu.cn
基金资助:
国家自然科学基金 (No. 62002276, No. 41911530242, No. 41975142)；国家社科基金重大项目(No. 17ZDA092)；英国爱丁堡皇家学会和中国自然科学基金委员会联合国际项目；江苏省基础研究计划基金(No. BK20191398)资助

Multi-swarm Particle Swarm Optimization for Task Scheduling in Supply Chain Datacenter

ZENG Lei¹, BAI Jinming², LIU Qi³

1. School of Computer, Nanjing University of Information Science and Technology, Nanjing 210044, Jiangsu, China;
2. School of Applied Meteorology, Nanjing University of Information Science and Technology, Nanjing 210044, Jiangsu, China;
3. Engineering Research Center of Digital Forensics, Nanjing University of Information Science and Technology, Nanjing 210044, Jiangsu, China

Received:2022-10-28 Online:2023-05-30 Published:2023-06-16

摘要/Abstract

摘要： 针对数据中心规模和任务需求不断增加带来的服务效率降低等问题，提出了一种负载均衡多群落粒子群优化任务调度方法。通过改进的适应度函数对任务的最大完工时间和各机器完工时间方差进行组合优化以提升集群的负载均衡性；利用新的自适应惯性权重函数改进粒子搜索效率，提升算法收敛速率；采取新的粒子初始化方法提高初始解的质量和多样性，并利用多群落粒子协同搜索使得最终结果更加接近最优解。在阿里巴巴数据中心的公开数据集上对算法性能进行了验证和对比，实验结果表明，该方法能够提高数据中心在多样化供应链环境下的任务调度效率。

关键词: 粒子群优化, 供应链管理, 数据中心, 任务调度, 负载均衡

Abstract: 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.

Key words: particle swarm optimization, supply chain management, datacenter, task scheduling, load balancing

中图分类号:

TP393.09

曾磊, 白金明, 刘琦. 多群落粒子群优化供应链数据中心任务调度[J]. 应用科学学报, 2023, 41(3): 419-430.

ZENG Lei, BAI Jinming, LIU Qi. Multi-swarm Particle Swarm Optimization for Task Scheduling in Supply Chain Datacenter[J]. Journal of Applied Sciences, 2023, 41(3): 419-430.

参考文献

[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.

多群落粒子群优化供应链数据中心任务调度

Multi-swarm Particle Swarm Optimization for Task Scheduling in Supply Chain Datacenter

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

[1]	李晗, 孟顺梅, 蔡志成. 基于博弈论和粒子群优化的移动边缘计算任务卸载方法[J]. 应用科学学报, 2023, 41(3): 405-418.
[2]	邹倩颖, 陈晖阳, 李永生, 胡力雯, 王小芳. 粒子群优化的深海图像暗边缘检测优化算法[J]. 应用科学学报, 2023, 41(1): 153-169.
[3]	仇宾, 孙曼曼, 崔素丽. 基于剪枝优化的多变邻域节能调度算法[J]. 应用科学学报, 2022, 40(2): 349-360.
[4]	范君, 李茹, 张祎航. 一种适用于车联云任务调度的轻量级区块链架构[J]. 应用科学学报, 2021, 39(1): 99-108.
[5]	陈俊, 李娅, 张芥. 基于虚拟机的数据中心能耗测量[J]. 应用科学学报, 2020, 38(3): 488-495.
[6]	杨亚南, 李一鸣, 聂力海, 张宁, 赵来平. 跨地域分布数据中心高成本效益的任务调度[J]. 应用科学学报, 2019, 37(6): 859-874.
[7]	王光艳, 耿艳香, 陈雷. 改进粒子群算法在水下盲语音分离中的应用研究[J]. 应用科学学报, 2018, 36(4): 589-600.
[8]	姜长泓, 张永恒, 王盛慧. 基于改进粒子群优化算法的PID控制器参数优化[J]. 应用科学学报, 2017, 35(5): 667-674.
[9]	董莉, 宋晓勤, 韩杰. 基于遗传粒子群优化的认知OFDM网络资源分配算法[J]. 应用科学学报, 2017, 35(3): 288-298.
[10]	邵静珠，董育宁. 基于智能天线的一种自适应小基站架构[J]. 应用科学学报, 2015, 33(4): 351-366.
[11]	杨洪涛，耿金华，丁小瑞，喻曹丰，禹斌. 数控机床力-几何误差的PSO-SVM建模[J]. 应用科学学报, 2014, 32(3): 325-330.
[12]	刘立昕，卞红雨. 用于水下目标跟踪的多特征融合PSOPF 算法[J]. 应用科学学报, 2013, 31(6): 564-568.
[13]	唐良瑞1，杨筝1，赵琳2. 有效均衡异构无线网络负载的接入选择[J]. 应用科学学报, 2013, 31(5): 441-447.
[14]	张树银，郭英，齐子森，苏令华. 共形阵列LFM信号DOA和极化参数的联合估计[J]. 应用科学学报, 2013, 31(3): 252-258.
[15]	陈志敏，薄煜明，吴盘龙，宋公飞，段文勇. 一种新型自适应粒子群优化粒子滤波算法及应用[J]. 应用科学学报, 2013, 31(3): 285-293.