Journal of Computer Applications ›› 2023, Vol. 43 ›› Issue (2): 474-483.DOI: 10.11772/j.issn.1001-9081.2022010001
Special Issue: 先进计算
• Advanced computing • Previous Articles Next 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: https://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] | Peigen GAO, Bin SUO. Experimental design and staged PSO-Kriging modeling based on weighted hesitant fuzzy set [J]. Journal of Computer Applications, 2024, 44(7): 2144-2150. |
[2] | Yan LI, Dazhi PAN, Siqing ZHENG. Improved adaptive large neighborhood search algorithm for multi-depot vehicle routing problem with time window [J]. Journal of Computer Applications, 2024, 44(6): 1897-1904. |
[3] | Wanting ZHANG, Wenli DU, Wei DU. Multi-timescale cooperative evolutionary algorithm for large-scale crude oil scheduling [J]. Journal of Computer Applications, 2024, 44(5): 1355-1363. |
[4] | Tao JIANG, Zhenyu LIANG, Ran CHENG, Yaochu JIN. GPU-accelerated evolutionary optimization of multi-objective flow shop scheduling problems [J]. Journal of Computer Applications, 2024, 44(5): 1364-1371. |
[5] | Kaiwen ZHAO, Peng WANG, Xiangrong TONG. Two-stage search-based constrained evolutionary multitasking optimization algorithm [J]. Journal of Computer Applications, 2024, 44(5): 1415-1422. |
[6] | Xiaofang LIU, Jun ZHANG. Probability-driven dynamic multiobjective evolutionary optimization for multi-agent cooperative scheduling [J]. Journal of Computer Applications, 2024, 44(5): 1372-1377. |
[7] | Lin GAO, Yu ZHOU, Tak Wu KWONG. Evolutionary bi-level adaptive local feature selection [J]. Journal of Computer Applications, 2024, 44(5): 1408-1414. |
[8] | Ye TIAN, Jinjin CHEN, Xingyi ZHANG. Hybrid optimizer combining evolutionary computation and gradient descent for constrained multi-objective optimization [J]. Journal of Computer Applications, 2024, 44(5): 1386-1392. |
[9] | Xin LI, Liyong BAO, Hongwei DING, Zheng GUAN. MAC layer scheduling strategy of roadside units based on MEC server priority service [J]. Journal of Computer Applications, 2024, 44(4): 1227-1235. |
[10] | Xiuxi WEI, Maosong PENG, Huajuan HUANG. Node coverage optimization of wireless sensor network based on multi-strategy improved butterfly optimization algorithm [J]. Journal of Computer Applications, 2024, 44(4): 1009-1017. |
[11] | Jianqiang LI, Zhou HE. Hybrid NSGA-Ⅱ for vehicle routing problem with multi-trip pickup and delivery [J]. Journal of Computer Applications, 2024, 44(4): 1187-1194. |
[12] | Xiaoxin DU, Wei ZHOU, Hao WANG, Tianru HAO, Zhenfei WANG, Mei JIN, Jianfei ZHANG. Survey of subgroup optimization strategies for intelligent algorithms [J]. Journal of Computer Applications, 2024, 44(3): 819-830. |
[13] | Yongjian MA, Xuhua SHI, Peiyao WANG. Constrained multi-objective evolutionary algorithm based on two-stage search and dynamic resource allocation [J]. Journal of Computer Applications, 2024, 44(1): 269-277. |
[14] | Shaofa SHANG, Lin JIANG, Yuancheng LI, Yun ZHU. Adaptive partitioning and scheduling method of convolutional neural network inference model on heterogeneous platforms [J]. Journal of Computer Applications, 2023, 43(9): 2828-2835. |
[15] | Yun OU, Kaiqing ZHOU, Pengfei YIN, Xuewei LIU. Improved grey wolf optimizer algorithm based on dual convergence factor strategy [J]. Journal of Computer Applications, 2023, 43(9): 2679-2685. |
Viewed | ||||||
Full text |
|
|||||
Abstract |
|
|||||