Journal of Computer Applications ›› 2023, Vol. 43 ›› Issue (2): 474-483.DOI: 10.11772/j.issn.1001-9081.2022010001
• Advanced computing • Previous Articles
Xuesen MA1,2(), Xuemei XU1,2, Gonghui JIANG1,2, Yan QIAO1,2, Tianbao ZHOU1,2
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.Supported by:
马学森1,2(), 许雪梅1,2, 蒋功辉1,2, 乔焰1,2, 周天保1,2
通讯作者:
马学森
作者简介:
许雪梅(1998—),女,安徽合肥人,硕士研究生,主要研究方向:云计算、移动边缘计算基金资助:
CLC Number:
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.
马学森, 许雪梅, 蒋功辉, 乔焰, 周天保. 混合自适应粒子群工作流调度优化算法[J]. 《计算机应用》唯一官方网站, 2023, 43(2): 474-483.
Add to citation manager EndNote|Ris|BibTeX
URL: http://www.joca.cn/EN/10.11772/j.issn.1001-9081.2022010001
任务 | 位置 | 虚拟机编号 | 任务 | 位置 | 虚拟机编号 |
---|---|---|---|---|---|
t1 | 2.4 | 2 | t4 | 6.7 | 2 |
t2 | 7.1 | 3 | t5 | 3.5 | 3 |
t3 | 5.3 | 1 | t6 | 4.2 | 0 |
Tab. 1 Particle coding
任务 | 位置 | 虚拟机编号 | 任务 | 位置 | 虚拟机编号 |
---|---|---|---|---|---|
t1 | 2.4 | 2 | t4 | 6.7 | 2 |
t2 | 7.1 | 3 | t5 | 3.5 | 3 |
t3 | 5.3 | 1 | t6 | 4.2 | 0 |
实体类型 | 参数 | 值 |
---|---|---|
任务 | 指令长度 | 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 |
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 |
算法 | 参数名 | 参数值 |
---|---|---|
HAPSO | 惯性因子 | wmax=0.9, wmin=0.5 |
学习因子 | c1,c2∈[0.5, 2.5] | |
WPSO | 惯性因子 | wmax=0.9, wmin=0.5 |
学习因子 | c1=c2=2.0 | |
PSO | 惯性因子 | w=0.9 |
学习因子 | c1=c2=2.0 | |
ACO | 信息素浓度重要程度 | α=0.3 |
启发因子重要程度 | β=1.0 | |
信息素挥发因子 | ρ=0.4 |
Tab. 3 Parameter setting of algorithms
算法 | 参数名 | 参数值 |
---|---|---|
HAPSO | 惯性因子 | wmax=0.9, wmin=0.5 |
学习因子 | c1,c2∈[0.5, 2.5] | |
WPSO | 惯性因子 | wmax=0.9, wmin=0.5 |
学习因子 | c1=c2=2.0 | |
PSO | 惯性因子 | w=0.9 |
学习因子 | c1=c2=2.0 | |
ACO | 信息素浓度重要程度 | α=0.3 |
启发因子重要程度 | β=1.0 | |
信息素挥发因子 | ρ=0.4 |
算法 | 初始值 | 寻优结果 | 收敛迭代次数 |
---|---|---|---|
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 |
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 |
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] | Lei ZHONG, Yunsheng ZHOU, Dunhui YU, Haibo CUI. Reviewer recommendation algorithm based on affinity and research direction coverage [J]. Journal of Computer Applications, 2023, 43(2): 430-436. |
[2] | Feng XIANG, Zhongzhi LI, Xi XIONG, Binyong LI. Inverse distance weight interpolation algorithm based on particle swarm local optimization [J]. Journal of Computer Applications, 2023, 43(2): 385-390. |
[3] | Xingjia LI, Qiuhui YANG, Mei HONG, Chunxia PAN, Ruihang LIU. Test case prioritization approach based on historical data and multi-objective optimization [J]. Journal of Computer Applications, 2023, 43(1): 221-226. |
[4] | Yanfang MA, Wen ZHANG, Zongmin LI, Fang YAN, Lingyun GUO. Two-echelon location-routing model and algorithm for waste recycling considering obnoxious effect [J]. Journal of Computer Applications, 2023, 43(1): 289-298. |
[5] | Renbiao WU, Zhenchi ZHANG, Yunfei JIA, Han QIAO. Adaptive scheduling strategy based on deadline under cloud platform [J]. Journal of Computer Applications, 2023, 43(1): 176-184. |
[6] | Songyan JIANG, Xiaojuan LIAO, Guangzhu CHEN. Optimal task scheduling method based on satisfiability modulo theory for multiple processors with communication delay [J]. Journal of Computer Applications, 2023, 43(1): 185-191. |
[7] | Hongchao YAN, Wei TANG, Bin YAO. Hybrid bird swarm algorithm for solving permutation flowshop scheduling problem [J]. Journal of Computer Applications, 2022, 42(9): 2952-2959. |
[8] | Yidi WANG, Zhiwei LI, Wenxin ZHANG, Tieke LI, Bailin WANG. Estimation of distribution algorithm for hot rolling rescheduling with order disturbance [J]. Journal of Computer Applications, 2022, 42(8): 2628-2636. |
[9] | Kuineng CHEN, Xiaofang YUAN. Multi-objective hybrid evolutionary algorithm for solving open-shop scheduling problem with controllable processing time [J]. Journal of Computer Applications, 2022, 42(8): 2617-2627. |
[10] | Houming FAN, Shuang MU, Lijun YUE. Collaborative optimization of automated guided vehicle scheduling and path planning considering conflict and congestion [J]. Journal of Computer Applications, 2022, 42(7): 2281-2291. |
[11] | Xiangyu ZHANG, Yang YANG, Guohui FENG, Chuan QIN. Reversible data hiding in encrypted image based on multi-objective optimization [J]. Journal of Computer Applications, 2022, 42(6): 1716-1723. |
[12] | Hongliang LI, Nong ZHANG, Ting SUN, Xiang LI. Performance interference analysis and prediction for distributed machine learning jobs [J]. Journal of Computer Applications, 2022, 42(6): 1649-1655. |
[13] | Weikang ZHANG, Sheng LIU, Qian HUANG, Yuxin GUO. Equilibrium optimizer considering distance factor and elite evolutionary strategy [J]. Journal of Computer Applications, 2022, 42(6): 1844-1851. |
[14] | Jinquan ZHANG, Shouwei XU, Xincheng LI, Chongyang WANG, Jingzhi XU. Cloud computing task scheduling based on orthogonal adaptive whale optimization [J]. Journal of Computer Applications, 2022, 42(5): 1516-1523. |
[15] | Bing GAO, Ya ZHENG, Jing QIN, Qijie ZOU, Zumin WANG. Network intrusion detection algorithm based on sparrow search algorithm and improved particle swarm optimization algorithm [J]. Journal of Computer Applications, 2022, 42(4): 1201-1206. |
Viewed | ||||||
Full text |
|
|||||
Abstract |
|
|||||