混合自适应粒子群工作流调度优化算法

doi:10.11772/j.issn.1001-9081.2022010001

《计算机应用》唯一官方网站 ›› 2023, Vol. 43 ›› Issue (2): 474-483.DOI: 10.11772/j.issn.1001-9081.2022010001

• 先进计算 • 上一篇

混合自适应粒子群工作流调度优化算法

马学森¹^,²(), 许雪梅¹^,², 蒋功辉¹^,², 乔焰¹^,², 周天保¹^,²

^1.合肥工业大学计算机与信息学院，合肥 230601
^2.安全关键工业测控技术教育部工程研究中心（合肥工业大学），合肥 230009

收稿日期:2022-01-05 修回日期:2022-03-17 接受日期:2022-03-21 发布日期:2023-02-08 出版日期:2023-02-10
通讯作者: 马学森
作者简介:许雪梅（1998—），女，安徽合肥人，硕士研究生，主要研究方向：云计算、移动边缘计算
蒋功辉（1998—），男，江西吉安人，硕士研究生，主要研究方向：网络流量预测、数据挖掘
乔焰（1984—），女，山东聊城人，副教授，博士，主要研究方向：云计算数据中心网络管理、计算机网络管理
周天保（1998—），男，湖北黄石人，硕士研究生，主要研究方向：云计算、深度学习。
基金资助:
国家重点研发计划项目(2020YFC1512601)

Hybrid adaptive particle swarm optimization algorithm for workflow scheduling

Xuesen MA¹^,²(), Xuemei XU¹^,², Gonghui JIANG¹^,², Yan QIAO¹^,², Tianbao ZHOU¹^,²

^1.School of Computer Science and Information Engineering，Hefei University of Technology，Hefei Anhui 230601，China
^2.Engineering Research Center of Safety Critical Industrial Measurement and Control Technology，Ministry of Education （Hefei University of Technology），Hefei Anhui 230009，China

Received:2022-01-05 Revised:2022-03-17 Accepted:2022-03-21 Online:2023-02-08 Published:2023-02-10
Contact: Xuesen MA
About author:XU Xuemei， born in 1998， M. S. candidate. Her research interests include cloud computing， mobile edge computing.
JIANG Gonghui， born in 1998， M. S. candidate. His research interests include network traffic prediction， data mining.
QIAO Yan， born in 1984， Ph. D.， associate professor. Her research interests include cloud computing data center network management， computer network management.
ZHOU Tianbao， born in 1998， M. S. candidate. His research interests include cloud computing， deep learning.
Supported by:
National Key Research and Development Program of China(2020YFC1512601)

摘要/Abstract

摘要：

针对具有截止期的云工作流完成时间与执行成本冲突的问题，提出一种混合自适应粒子群工作流调度优化算法（HAPSO）。首先，基于截止期建立有向无环图（DAG）云工作流调度模型；然后，通过范数理想点与自适应权重的结合，将DAG调度模型转化为权衡DAG完成时间和执行成本的多目标优化问题；最后，在粒子群优化（PSO）算法的基础上引入自适应惯性权重、自适应学习因子、花朵授粉算法的概率切换机制、萤火虫算法（FA）和粒子越界处理方法，从而平衡粒子群的全局搜索与局部搜索能力，进而求解DAG完成时间与执行成本的目标优化问题。实验中对比分析了PSO、惯性权重粒子群算法（WPSO）、蚁群算法（ACO）和HAPSO的优化结果。实验结果表明，HAPSO在权衡工作流（30~300任务数）完成时间与执行成本的多目标函数值上降低了40.9%~81.1%，HAPSO在工作流截止期约束下有效权衡了完成时间与执行成本。此外，HAPSO在减少完成时间或降低执行成本的单目标上也有较好的效果，验证了HAPSO的普适性。

关键词: 云工作流, 调度, 截止期, 自适应权重, 粒子群优化算法, 目标优化

Abstract:

Aiming at the conflict between the makespan and execution cost of cloud workflows with deadlines， a Hybrid Adaptive Particle Swarm Optimization algorithm for workflow scheduling （HAPSO） was proposed. Firstly， a Directed Acyclic Graph （DAG） cloud workflow scheduling model was established based on deadlines. Secondly， through the combination of norm ideal points and adaptive weights， the DAG scheduling model was transformed into a multi-objective optimization problem that weighs DAG makespan and execution cost. Finally， based on Particle Swarm Optimization （PSO） algorithm， the adaptive inertia weight， the adaptive learning factors， the probability switching mechanism of flower pollination algorithm， Firefly Algorithm （FA） and the particle out-of-bound processing method were added to balance the global search ability and the local search ability of the particle swarm， and then to solve the objective optimization problem of DAG makespan and execution cost. The optimization results of PSO， Weight Particle Swarm Optimization （WPSO）， Ant Colony Optimization （ACO） and HAPSO were compared and analyzed in the experiment. Experimental results show that HAPSO reduces the multi-objective function value by 40.9% to 81.1% that weighs the makespan and execution cost of workflow （30~300 tasks）， and HAPSO effectively weighs the makespan and execution cost with the constraints of workflow deadlines. In addition， HAPSO also has a good effect on the single objective of reducing the makespan or execution cost， which verifies the universality of HAPSO.

Key words: cloud workflow, scheduling, deadline, adaptive weight, Particle Swarm Optimization (PSO) algorithm, objective optimization

中图分类号:

TP391.9

马学森, 许雪梅, 蒋功辉, 乔焰, 周天保. 混合自适应粒子群工作流调度优化算法[J]. 计算机应用, 2023, 43(2): 474-483.

Xuesen MA, Xuemei XU, Gonghui JIANG, Yan QIAO, Tianbao ZHOU. Hybrid adaptive particle swarm optimization algorithm for workflow scheduling[J]. Journal of Computer Applications, 2023, 43(2): 474-483.

图/表 13

图1 DAG云工作流调度模型的架构

Fig. 1 Architecture of DAG cloud workflow scheduling model

表1 粒子编码

Tab. 1 Particle coding

任务	位置	虚拟机编号	任务	位置	虚拟机编号
t₁	2.4	2	t₄	6.7	2
t₂	7.1	3	t₅	3.5	3
t₃	5.3	1	t₆	4.2	0

图2 粒子位置更新示意图

Fig. 2 Schematic diagram of updating particle position

表2 云仿真器参数设置

Tab. 2 Parameter setting of cloud simulator

实体类型	参数	值
任务	指令长度	5 000~15 000
任务	任务总数	30~300
虚拟机	虚拟机总数	15
	处理速度/MIPS	50~2 000
	带宽/（Mb·s^-1）	500~1 000
	执行单位成本	0.34~0.7
	传输单位成本	0.3
	CPU核心数	1~5
数据中心	数据中心数	2
数据中心	主机数	4

表3 算法参数设置

Tab. 3 Parameter setting of algorithms

算法	参数名	参数值
HAPSO	惯性因子	w_max=0.9， w_min=0.5
HAPSO	学习因子	c₁，c₂∈［0.5， 2.5］
WPSO	惯性因子	w_max=0.9， w_min=0.5
WPSO	学习因子	c₁=c₂=2.0
PSO	惯性因子	w=0.9
PSO	学习因子	c₁=c₂=2.0
ACO	信息素浓度重要程度	α=0.3
	启发因子重要程度	β=1.0
	信息素挥发因子	ρ=0.4

表4 算法收敛性对比

Tab. 4 Comparison of convergence among algorithms

算法	初始值	寻优结果	收敛迭代次数
HAPSO	0.035 21	0.000 02	26
WPSO	75.904 90	5.932 38	35
PSO	86.800 86	13.678 17	130
ACO	1.412 11	0.000 75	127

图3 四种算法的迭代效果对比

Fig. 3 Comparison of iterative effects of four algorithms

图4 四种算法的权衡最小值f对比

Fig. 4 Comparison of trade-off minimum values f of four algorithms

图5 四种算法在不同工作流上的完成时间和截止期对比

Fig. 5 Comparison of makespans and deadlines for different workflows of four algorithms

图6 DAG完成时间对比（10~90任务数）

Fig. 6 Comparison of DAG makespan （10~90 tasks）

图7 DAG完成时间对比（210~290任务数）

Fig. 7 Comparison of DAG makespan （210~290 tasks）

图8 DAG执行成本对比（10~90任务数）

Fig. 8 Comparison of DAG execution cost （10~90 tasks）

图9 DAG执行成本对比（210~290任务数）

Fig. 9 Comparison of DAG execution cost （210~290 tasks）

参考文献 30

1	LIU X F， ZHAN Z H， DENG J D， et al. An energy efficient ant colony system for virtual machine placement in cloud computing ［J］. IEEE Transactions on Evolutionary Computation， 2018， 22（1）： 113-128. 10.1109/TEVC.2016.2623803
2	ISMAYILOV G， TOPCUOGLU H R. Neural network based multi-objective evolutionary algorithm for dynamic workflow scheduling in cloud computing ［J］. Future Generation Computer Systems， 2020， 102： 307-322. 10.1016/j.future.2019.08.012
3	TAGHINEZHAD-NIAR A， PASHAZADEH S， TAHERI J. Workflow scheduling of scientific workflows under simultaneous deadline and budget constraints ［J］. Cluster Computing， 2021， 24（4）：3449-3467. 10.1007/s10586-021-03314-3
4	MOHAMMADZADEH A， MASDARI M， GHAREHCHOPOGH F S. Energy and cost-aware workflow scheduling in cloud computing data centers using a multi-objective optimization algorithm ［J］. Journal of Network and Systems Management， 2021， 29（3）： No.31. 10.1007/s10922-021-09599-4
5	李启锐，彭心怡. 基于深度强化学习的云作业调度及仿真研究［J］. 系统仿真学报， 2022， 34（2）：258-268. 10.16182/j.issn1004731x.joss.21-0337
	LI Q R， PENG X Y. Job scheduling and simulation in cloud based on deep reinforcement learning［J］. Journal of System Simulation， 2022， 34（2）：258-268. 10.16182/j.issn1004731x.joss.21-0337
6	HAN P C， DU C L， CHEN J C， et al. Cost and makespan scheduling of workflows in clouds using list multi-objective optimization technique［J］. Journal of Systems Architecture， 2021， 112： No.101837. 10.1016/j.sysarc.2020.101837
7	ALKAYAL E S， JENNINGS N R， ABULKHAIR M F. Efficient task scheduling multi-objective particle swarm optimization in cloud computing［C］// Proceedings of the IEEE 41st Conference on Local Computer Networks Workshops. Piscataway： IEEE， 2016： 17-24. 10.1109/lcn.2016.024
8	童钊，邓小妹，陈洪剑，等. 云环境下基于强化学习的多目标任务调度算法［J］. 小型微型计算机系统， 2020， 41（02）： 285-290. 10.3969/j.issn.1000-1220.2020.02.010
	TONG Z， DENG X M， CHEN H J， et al. Multi-objective task scheduling algorithm based on reinforcement learning in cloud environments［J］. Journal of Chinese Computer Systems， 2020， 41（2）： 285-290. 10.3969/j.issn.1000-1220.2020.02.010
9	CHAKRAVARTHI K K， SHYAMALA L， VAIDEHI V. Cost-effective workflow scheduling approach on cloud under deadline constraint using firefly algorithm［J］. Applied Intelligence， 2021， 51（3）： 1629-1644. 10.1007/s10489-020-01875-1
10	GUO P Z， XUE Z. An adaptive PSO-based real-time workflow scheduling algorithm in cloud systems［C］// Proceedings of the 17th IEEE International Conference on Communication Technology. Piscataway： IEEE， 2017： 1932-1936. 10.1109/icct.2017.8359966
11	JIA Y H， CHEN W N， YUAN H Q， et al. An intelligent cloud workflow scheduling system with time estimation and adaptive ant colony optimization［J］. IEEE Transactions on Systems， Man， and Cybernetics： Systems， 2021， 51（1）：634-649. 10.1109/tsmc.2018.2881018
12	董明刚，范培，闭玉申，等. 面向虚拟化云数据中心的工作流联合调度算法研究［J］. 小型微型计算机系统， 2021， 42（6）：1152-1157. 10.3969/j.issn.1000-1220.2021.06.005
	DONG M G， FAN P， BI Y S， et al. Research on joint workflows scheduling algorithm for virtualized cloud data centers［J］. Journal of Chinese Computer Systems， 2021， 42（6）： 1152-1157. 10.3969/j.issn.1000-1220.2021.06.005
13	孙长亚，王向文. 基于MGA-PSO的云计算多目标任务调度［J］. 计算机应用与软件， 2021， 38（6）：212-218. 10.3969/j.issn.1000-386x.2021.06.034
	SUN C Y， WANG X W. Multi-objective task scheduling of cloud computing based on MGA-PSO［J］. Computer Applications and Software， 2021， 38（6）： 212-218. 10.3969/j.issn.1000-386x.2021.06.034
14	方伯芃，孙林夫. 面向QoS与成本感知的云工作流调度优化［J］. 计算机集成制造系统， 2018， 24（2）：331-348. 10.13196/j.cims.2018.01.006
	FANG B P， SUN L F. Cloud workflow scheduling optimization oriented to QoS and cost-awareness［J］. Computer Integrated Manufacturing Systems， 2018， 24（2）： 331-348. 10.13196/j.cims.2018.01.006
15	REHMAN A， JAVED K， BABRI H A， et al. Selection of the most relevant terms based on a max-min ratio metric for text classification［J］. Expert Systems with Applications， 2018， 114： 78-96. 10.1016/j.eswa.2018.07.028
16	TOPCUOGLU H， HARIRI S， WU M Y. Performance-effective and low-complexity task scheduling for heterogeneous computing［J］. IEEE Transactions on Parallel and Distributed Systems， 2002， 13（3）： 260-274. 10.1109/71.993206
17	VISHNU B A， JEVITHA K P. Prediction of cross-site scripting attack using machine learning algorithms［C］// Proceedings of the 2014 International Conference on Interdisciplinary Advances in Applied Computing. New York： ACM， 2014： No.55. 10.1145/2660859.2660969
18	孙敏，叶侨楠，陈中雄. 云环境下方差定向变异遗传算法的任务调度［J］. 计算机应用， 2019， 39（11）：3328-3332. 10.11772/j.issn.1001-9081.2019040635
	SUN M， YE Q N， CHEN Z X. Task scheduling of variance-directional variation genetic algorithm in cloud environment［J］. Journal of Computer Applications， 2019， 39（11）：3328-3332. 10.11772/j.issn.1001-9081.2019040635
19	罗斌，于波. 移动边缘计算中基于粒子群优化的计算卸载策略［J］. 计算机应用， 2020， 40（8）：2293-2298. 10.11772/j.issn.1001-9081.2019122200
	LUO B， YU B. Computation offloading strategy based on particle swarm optimization in mobile edge computing［J］. Journal of Computer Applications， 2020， 40（8）： 2293-2298. 10.11772/j.issn.1001-9081.2019122200
20	张晓丽. 自适应CPSO算法在云计算任务调度中的应用［J］. 计算机技术与发展， 2016， 26（8）：161-165. 10.3969/j.issn.1673-629X.2016.08.034
	ZHANG X L. Application of self-adaptive chaos particle swarm optimization in task scheduling for cloud computing［J］. Computer Technology and Development， 2016， 26（8）： 161-165. 10.3969/j.issn.1673-629X.2016.08.034
21	李学俊，徐佳，王福田，等. 云工作流系统中能耗感知的任务调度算法［J］. 模式识别与人工智能， 2016， 29（9）：790-796. 10.16451/j.cnki.issn1003-6059.201609003
	LI X J， XU J， WANG F T， et al. Energy aware task scheduling algorithm in cloud workflow system［J］. Pattern Recognition and Artificial Intelligence， 2016， 29（9）： 790-796. 10.16451/j.cnki.issn1003-6059.201609003
22	王宏欣，张跃. 带截止期约束的多模态云服务工作流调度［J］. 小型微型计算机系统， 2016， 37（11）：2437-2442. 10.3969/j.issn.1000-1220.2016.11.010
	WANG H X， ZHANG Y. Scheduling method for multi-mode cloud workflows with deadlines［J］. Journal of Chinese Computer Systems， 2016， 37（11）： 2437-2442. 10.3969/j.issn.1000-1220.2016.11.010
23	冉家敏，倪志伟，彭鹏，等. 考虑空间众包工作者服务质量的任务分配策略及其萤火虫群优化算法求解［J］. 计算机应用， 2021， 41（3）： 794-802. 10.11772/j.issn.1001-9081.2020060940
	RAN J M， NI Z W， PENG P， et al. Task allocation strategy considering service quality of spatial crowdsourcing workers and its glowworm swarm optimization algorithm solution［J］. Journal of Computer Applications， 2021， 41（3）： 794-802. 10.11772/j.issn.1001-9081.2020060940
24	BEEGOM A S A， RAJASREE M S. Integer⁃PSO： a discrete PSO algorithm for task scheduling in cloud computing systems［J］. Evolutionary Intelligence， 2019， 12（2）： 227-239. 10.1007/s12065-019-00216-7
25	胡堂清，张旭秀，曹晓月. 一种动态调整惯性权重的混合粒子群算法［J］. 电光与控制， 2020， 27（6）：16-21. 10.3969/j.issn.1671-637X.2020.06.004
	HU T Q， ZHANG X X， CAO X Y. A hybrid particle swarm optimization with dynamic adjustment of inertial weight［J］. Electronics Optics and Control， 2020， 27（6）： 16-21. 10.3969/j.issn.1671-637X.2020.06.004
26	张晓莉，王秦飞，冀汶莉. 一种改进的自适应惯性权重的粒子群算法［J］. 微电子学与计算机， 2019， 36（3）：66-70.
	ZHANG X L， WANG Q F， JI W L. An improved particle swarm optimization algorithm for adaptive inertial weights［J］. Microelectronics and Computer， 2019， 36（3）： 66-70.
27	谈杰. 基于改进粒子群算法的云计算多目标任务调度问题研究［D］.合肥：合肥工业大学， 2020：20-23.
	TAN J. Research on cloud computing multi-objective task scheduling problem based on improved particle swarm algorithm［D］. Hefei： Hefei University of Technology， 2020：20-23.
28	李建平，宫耀华，卢爱平，等. 改进的粒子群算法及在数值函数优化中应用［J］. 重庆大学学报， 2017， 40（5）：95-103. 10.11835/j.issn.1000-582X.2017.05.012
	LI J P， GONG Y H， LU A P， et al. Application of improved particle swarm algorithm to numerical function optimization［J］. Journal of Chongqing University， 2017， 40（5）： 95-103. 10.11835/j.issn.1000-582X.2017.05.012
29	卞京红，贺兴时，杨新社. 基于萤火虫算法的自适应花授粉优化算法［J］. 计算机工程与应用， 2016， 52（21）：162-167， 217. 10.3778/j.issn.1002-8331.1603-0412
	BIAN J H， HE X S， YANG X S. Hybrid algorithm of firefly algorithm and self-adaptive flower pollination algorithm［J］. Computer Engineering and Applications， 2016， 52（21）：162-167， 217. 10.3778/j.issn.1002-8331.1603-0412
30	CALHEIROS R N， RANJAN R， BELOGLAZOV A， et al. CloudSim： a toolkit for modeling and simulation of cloud computing environments and evaluation of resource provisioning algorithms［J］. Software： Practice and Experience， 2011， 41（1）： 23-50. 10.1002/spe.995

[1]	钟磊, 周允升, 余敦辉, 崔海波. 基于亲和力与研究方向覆盖率的审稿人推荐算法[J]. 《计算机应用》唯一官方网站, 2023, 43(2): 430-436.
[2]	吴仁彪, 张振驰, 贾云飞, 乔晗. 云平台下基于截止时间的自适应调度策略[J]. 《计算机应用》唯一官方网站, 2023, 43(1): 176-184.
[3]	姜松岩, 廖晓鹃, 陈光柱. 基于可满足性模理论的多处理机通信延迟优化任务调度方法[J]. 《计算机应用》唯一官方网站, 2023, 43(1): 185-191.
[4]	李兴佳, 杨秋辉, 洪玫, 潘春霞, 刘瑞航. 基于历史数据和多目标优化的测试用例排序方法[J]. 《计算机应用》唯一官方网站, 2023, 43(1): 221-226.
[5]	马艳芳, 张文, 李宗敏, 闫芳, 郭凌云. 考虑负效应的垃圾回收两级选址‒路径模型与算法[J]. 《计算机应用》唯一官方网站, 2023, 43(1): 289-298.
[6]	闫红超, 汤伟, 姚斌. 求解置换流水车间调度问题的混合鸟群算法[J]. 《计算机应用》唯一官方网站, 2022, 42(9): 2952-2959.
[7]	陈揆能, 袁小芳. 多目标混合进化算法求解加工时间可控的开放车间调度问题[J]. 《计算机应用》唯一官方网站, 2022, 42(8): 2617-2627.
[8]	王一荻, 李志伟, 张文新, 李铁克, 王柏琳. 考虑订单扰动因素的热轧重调度分布估计算法[J]. 《计算机应用》唯一官方网站, 2022, 42(8): 2628-2636.
[9]	盖荣丽, 高守传, 李明霞. 粒子群优化算法求解最优控制点的非均匀有理B样条曲线拟合[J]. 《计算机应用》唯一官方网站, 2022, 42(7): 2177-2183.
[10]	范厚明, 牟爽, 岳丽君. 考虑冲突和拥堵的自动导引车调度与路径规划协同优化[J]. 《计算机应用》唯一官方网站, 2022, 42(7): 2281-2291.
[11]	张翔宇, 杨阳, 冯国徽, 秦川. 基于多目标优化的加密图像可逆信息隐藏[J]. 《计算机应用》唯一官方网站, 2022, 42(6): 1716-1723.
[12]	李洪亮, 张弄, 孙婷, 李想. 分布式机器学习作业性能干扰分析与预测[J]. 《计算机应用》唯一官方网站, 2022, 42(6): 1649-1655.
[13]	张伟康, 刘升, 黄倩, 郭雨鑫. 考虑距离因素与精英进化策略的平衡优化器[J]. 《计算机应用》唯一官方网站, 2022, 42(6): 1844-1851.
[14]	张金泉, 徐寿伟, 李信诚, 王重洋, 徐景芝. 基于正交自适应鲸鱼优化的云计算任务调度[J]. 《计算机应用》唯一官方网站, 2022, 42(5): 1516-1523.
[15]	高兵, 郑雅, 秦静, 邹启杰, 汪祖民. 基于麻雀搜索算法和改进粒子群优化算法的网络入侵检测算法[J]. 《计算机应用》唯一官方网站, 2022, 42(4): 1201-1206.

混合自适应粒子群工作流调度优化算法

Hybrid adaptive particle swarm optimization algorithm for workflow scheduling

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 13

参考文献 30

相关文章 15

编辑推荐

Metrics