基于正交自适应鲸鱼优化的云计算任务调度

doi:10.11772/j.issn.1001-9081.2021050806

《计算机应用》唯一官方网站 ›› 2022, Vol. 42 ›› Issue (5): 1516-1523.DOI: 10.11772/j.issn.1001-9081.2021050806

基于正交自适应鲸鱼优化的云计算任务调度

张金泉¹, 徐寿伟¹, 李信诚¹, 王重洋¹, 徐景芝²()

^1.山东科技大学计算机科学与工程学院，山东青岛 266590
^2.山东科技大学科技产业管理处，山东青岛 266590

收稿日期:2021-05-17 修回日期:2021-09-15 接受日期:2021-09-16 发布日期:2022-03-08 出版日期:2022-05-10
通讯作者: 徐景芝
作者简介:张金泉（1972—），男，四川南充人，副教授，博士，CCF会员，主要研究方向：云计算、大数据分析与处理、隐私保护
徐寿伟（1996—），男，山东烟台人，硕士研究生，CCF会员，主要研究方向：云计算、边缘计算、任务调度
李信诚（1997—），男，山东泰安人，硕士研究生，CCF会员，主要研究方向：云计算、边缘计算、任务调度
王重洋（1996—），男，山东潍坊人，硕士研究生，CCF会员，主要研究方向：云计算、隐私保护
徐景芝（1973—），女，山东济南人，讲师，硕士，主要研究方向：云计算、大数据分析与处理。 skd306@163.com
基金资助:
教育部人文社科基金资助项目(20YJAZH078);同济大学嵌入式系统与服务计算教育部重点实验室开放课题(ESSCKF 2019?06)

Cloud computing task scheduling based on orthogonal adaptive whale optimization

Jinquan ZHANG¹, Shouwei XU¹, Xincheng LI¹, Chongyang WANG¹, Jingzhi XU²()

^1.College of Computer Science and Engineering，Shandong University of Science and Technology，Qingdao Shandong 266590，China
^2.Science and Technology Industry Management Office，Shandong University of Science and Technology，Qingdao Shandong 266590，China

Received:2021-05-17 Revised:2021-09-15 Accepted:2021-09-16 Online:2022-03-08 Published:2022-05-10
Contact: Jingzhi XU
About author:ZHANG Jinquan， born in 1972，Ph. D.，associate professor. Hisresearch interests include cloud computing， big data analysis and processing，privacy protection.
XU Shouwei， born in 1996，M. S. candidate. His research interestsinclude cloud computing，edge computing，task scheduling.
LI Xincheng， born in 1997，M. S. candidate. His research interestsinclude cloud computing，edge computing，task scheduling.
WANG Chongyang， born in 1996，M. S. candidate. His researchinterests include cloud computing，privacy protection.
XU Jingzhi， born in 1973，M. S.，lecturer. Her research interestsinclude cloud computing，big data analysis and processing.
Supported by:
Humanity and Social Science Fund of Ministry of Education(20YJAZH078);Open Project of Key Laboratory of Embedded System and Service Computing, Ministry of Education （Tongji University）（ESSCKF 2019-06, ESSCKF 2019-08）

摘要/Abstract

摘要：

针对任务调度中存在的任务完成时间长、系统执行任务成本高且系统负载不均衡等问题，提出了一种基于正交自适应鲸鱼优化算法（OAWOA）的云计算任务调度方法。首先，将正交试验设计（OED）应用于种群初始化和全局搜索阶段，以提升和维持种群的多样性，避免算法过早陷入局部收敛状态；然后，利用自适应指数递减因子和双向搜索机制，来进一步加强算法的全局搜索能力；最后，对适应度函数进行优化，从而使算法实现多目标优化。通过仿真实验将所提的算法与鲸鱼优化算法（WOA）、粒子群优化（PSO）算法、蝙蝠算法（BA）以及其他两种改进的WOA进行比较。实验结果表明，在任务规模为50和500时所提算法都取得了更好的收敛效果，并且得到的系统执行任务的总时间和总成本均低于其他几种算法，同时负载均衡度仅低于BA。可见，所提算法在降低系统执行任务的总时间和总成本以及提高系统负载均衡方面均表现出了显著的优势。

关键词: 云计算, 任务调度, 鲸鱼优化算法, 正交试验设计, 多目标优化

Abstract:

Aiming at the problems such as long task completion time， high task execution cost and unbalanced system load in task scheduling， a new cloud computing task scheduling method based on Orthogonal Adaptive Whale Optimization Algorithm （OAWOA） was proposed. Firstly， the Orthogonal Experimental Design （OED） was applied to the population initialization and global search stages to improve and maintain the population diversity， avoid the algorithm from falling into local convergence too early. Then， the adaptive exponential decline factor and bidirectional search mechanism were used to further strengthen the global search ability of the algorithm. Finally， the fitness function was optimized to enable the algorithm to achieve multi-objective optimization. Through the simulation experiments， the proposed algorithm was compared with Whale Optimization Algorithm （WOA）， Particle Swarm Optimization （PSO） algorithm， Bat Algorithm （BA） and two other improved WOAs. Experimental results show that， when the task scale is 50 and 500， the proposed algorithm achieves better convergence effect， has the total time and total cost of the obtained system executing tasks lower than those of other algorithms， and has the load balancing degree only lower than that of BA. In conclusion， the proposed algorithm shows significant advantages in reducing the total time and cost of system executing tasks and improving the system load balancing.

Key words: cloud computing, task scheduling, Whale Optimization Algorithm (WOA), Orthogonal Experimental Design (OED), multi-objective optimization

中图分类号:

TP399

张金泉, 徐寿伟, 李信诚, 王重洋, 徐景芝. 基于正交自适应鲸鱼优化的云计算任务调度[J]. 计算机应用, 2022, 42(5): 1516-1523.

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.

图/表 8

表1 L8(27)正交表

Tab. 1 L8(27) orthogonal table

试验号	1	2	3	4	5	6	7
1	1	1	1	1	1	1	1
2	1	1	1	2	2	2	2
3	1	2	2	1	1	2	2
4	1	2	2	2	2	1	1
5	2	1	2	1	2	1	2
6	2	1	2	2	1	2	1
7	2	2	1	1	2	2	1
8	2	2	1	2	1	1	2

图1 基于OAWOA的云计算任务调度流程

Fig. 1 Flow chart of cloud computing task scheduling based on OAWOA

表2 虚拟机信息

Tab. 2 Virtual machine information

VM分组	VM编号	VM性能/MIPS	每秒VM定价/元
低性能	0~4	1 000	0.03
中性能	5~9	2 000	0.05
高性能	10~14	4 000	0.09

表3 任务规模为50和500时适应度函数的最优值

Tab. 3 Optimal values of fitness function when task scale is 50 and 500

任务规模	算法
任务规模	WOA	PSO	BA	WOAmM	IWOA	OAWOA
50	0.161	0.195	0.161	0.158	0.160	0.149
500	0.174	0.198	0.251	0.164	0.165	0.157

图2 任务规模为50时不同算法的收敛情况

Fig. 2 Convergence of different algorithms when task scale is 50

图3 任务规模为50时各个指标的优化情况

Fig. 3 Optimization of each index when task scale is 50

图4 任务规模为500时不同算法的收敛情况

Fig. 4 Convergence of different algorithms when task scale is 500

图5 任务规模为500时各个指标的优化情况

Fig. 5 Optimization of each index when task scale is 500

参考文献 20

1	王冠宇，王庆生，赵腾.混合蛙跳算法在云计算资源调度的策略改进［J］.科学技术与工程，2018，18（4）：297-303. 10.3969/j.issn.1671-1815.2018.04.047
	WANG G Y， WANG Q S， ZHAO T. The improved strategy of shuffled frog leaping algorithm in the resource scheduling of cloud computing ［J］. Science Technology and Engineering， 2018， 18（4）： 297-303. 10.3969/j.issn.1671-1815.2018.04.047
2	ALDOSSARY M. A review of dynamic resource management in cloud computing environments ［J］. Computer Systems Science and Engineering， 2021， 36（3）： 461-476. 10.32604/csse.2021.014975
3	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. 10.1016/j.jnca.2019.06.006
4	HU H Y， LI Z J， HU H， et al. Multi-objective scheduling for scientific workflow in multicloud environment ［J］. Journal of Network and Computer Applications， 2018， 114： 108-122. 10.1016/j.jnca.2018.03.028
5	ZHANG G H， ODBAL， ABNOOSIAN K. Scheduling mechanisms in the cloud environment： a methodological analysis ［J］. Kybernetes， 2020， 49（12）： 2977-2992. 10.1108/k-09-2019-0629
6	ARORA M， KUMAR V， DAVE M. Task scheduling in cloud infrastructure using optimization technique genetic algorithm ［C］// Proceedings of the 2020 4th World Conference on Smart Trends in Systems， Security and Sustainability. Piscataway： IEEE， 2020： 788-793. 10.1109/worlds450073.2020.9210303
7	KENNEDY J， EBERHART R. Particle swarm optimization ［C］// Proceedings of the 1995 International Conference on Neural Networks. Piscataway： IEEE， 1995： 1942-1948. 10.1109/icnn.1995.488968
8	DORIGO M， MANIEZZO V， COLORNI A. Ant system： optimization by a colony of cooperating agents ［J］. IEEE Transactions on Systems， Man， and Cybernetics， Part B （Cybernetics）， 1996， 26（1）： 29-41. 10.1109/3477.484436
9	SANAJ M S， PRATHAP P M JOE. Nature inspired Chaotic Squirrel Search Algorithm （CSSA） for multi objective task scheduling in an IAAS cloud computing atmosphere ［J］. Engineering Science and Technology， an International Journal， 2020， 23（4）： 891-902. 10.1016/j.jestch.2019.11.002
10	VELLIANGIRI S， KARTHIKEYAN P， ARUL XAVIER V M， et al. Hybrid electro search with genetic algorithm for task scheduling in cloud computing ［J］. Ain Shams Engineering Journal， 2021， 12（1）： 631-639. 10.1016/j.asej.2020.07.003
11	NATESAN G， CHOKKALINGAM A. An improved grey wolf optimization algorithm based task scheduling in cloud computing environment ［J］. The International Arab Journal of Information Technology， 2020， 17（1）： 73-81. 10.34028/iajit/17/1/9
12	MIRJALILI S， LEWIS A. The whale optimization algorithm ［J］. Advances in Engineering Software， 2016， 95： 51-67. 10.1016/j.advengsoft.2016.01.008
13	XU Z Z， HU Z Y， HEIDARI A A， et al. Orthogonally-designed adapted grasshopper optimization： a comprehensive analysis ［J］. Expert Systems with Applications， 2020， 150： Article No.113282. 10.1016/j.eswa.2020.113282
14	SREENU K， SREELATHA M. W-Scheduler： whale optimization for task scheduling in cloud computing ［J］. Cluster Computing， 2019， 22（S1）： 1087-1098. 10.1007/s10586-017-1055-5
15	CHEN X， CHENG L， LIU C， et al. A WOA-based optimization approach for task scheduling in cloud computing systems ［J］. IEEE Systems Journal， 2020， 14（3）： 3117-3128. 10.1109/jsyst.2019.2960088
16	閤大海，李元香，祝婕.基于正交设计的反向学习差分进化算法［J］.华中科技大学学报（自然科学版），2017，45（5）：23-27，44.
	XIA D H， LI Y X， ZHU J. Differential evolution algorithm using orthogonal design opposition-based learning ［J］. Journal of Huazhong University of Science and Technology （Natural Science Edition）， 2017， 45（5）： 23-27， 44.
17	郝晓弘，宋吉祥，周强，等.混合策略改进的鲸鱼优化算法［J］.计算机应用研究，2020，37（12）：3622-3626，3655.
	HAO X H， SONG J X， ZHOU Q， et al. Improved whale optimization algorithm based on hybrid strategy ［J］. Application Research of Computers， 2020， 37（12）： 3622-3626， 3655.
18	YANG X S， HOSSEIN GANDOMI A. Bat algorithm： a novel approach for global engineering optimization ［J］. Engineering Computations， 2012， 29（5）： 464-483. 10.1108/02644401211235834
19	CHAKRABORTY S， SAHA A K， SHARMA S， et al. A novel enhanced whale optimization algorithm for global optimization ［J］. Computers and Industrial Engineering， 2021， 153： Article No.107086. 10.1016/j.cie.2020.107086
20	武泽权，牟永敏.一种改进的鲸鱼优化算法［J］.计算机应用研究，2020，37（12）：3618-3621.
	WU Z Q， MU Y M. Improved whale optimization algorithm ［J］. Application Research of Computers， 2020， 37（12）： 3618-3621.

[1]	刘晓芳, 张军. 概率驱动的动态多目标多智能体协同调度进化优化[J]. 《计算机应用》唯一官方网站, 2024, 44(5): 1372-1377.
[2]	高麟, 周宇, 邝得互. 进化双层自适应局部特征选择[J]. 《计算机应用》唯一官方网站, 2024, 44(5): 1408-1414.
[3]	田野, 陈津津, 张兴义. 面向约束多目标优化的进化计算与梯度下降联合优化算法[J]. 《计算机应用》唯一官方网站, 2024, 44(5): 1386-1392.
[4]	姜涛, 梁振宇, 程然, 金耀初. GPU加速的演化算法求解多目标流水车间调度问题[J]. 《计算机应用》唯一官方网站, 2024, 44(5): 1364-1371.
[5]	赵楷文, 王鹏, 童向荣. 基于双阶段搜索的约束进化多任务优化算法[J]. 《计算机应用》唯一官方网站, 2024, 44(5): 1415-1422.
[6]	李建强, 何舟. 面向多行程取送货车辆路径问题的混合NSGA-Ⅱ[J]. 《计算机应用》唯一官方网站, 2024, 44(4): 1187-1194.
[7]	马勇健, 史旭华, 王佩瑶. 基于两阶段搜索与动态资源分配的约束多目标进化算法[J]. 《计算机应用》唯一官方网站, 2024, 44(1): 269-277.
[8]	尚绍法, 蒋林, 李远成, 朱筠. 异构平台下卷积神经网络推理模型自适应划分和调度方法[J]. 《计算机应用》唯一官方网站, 2023, 43(9): 2828-2835.
[9]	徐赛娟, 裴镇宇, 林佳炜, 刘耿耿. 基于多阶段搜索的约束多目标进化算法[J]. 《计算机应用》唯一官方网站, 2023, 43(8): 2345-2351.
[10]	陆佳行, 戴华, 刘源龙, 周倩, 杨庚. 面向云环境密文排序检索的字典划分向量空间模型[J]. 《计算机应用》唯一官方网站, 2023, 43(7): 1994-2000.
[11]	孙林, 黄金旭, 徐久成. 基于邻域容差互信息和鲸鱼优化算法的非平衡数据特征选择[J]. 《计算机应用》唯一官方网站, 2023, 43(6): 1842-1854.
[12]	方和平, 刘曙光, 冉泳屹, 钟坤华. 基于深度强化学习的多数据中心一体化调度优化[J]. 《计算机应用》唯一官方网站, 2023, 43(6): 1884-1892.
[13]	金苍宏, 邵育华, 何琴芳. 基于自适应群组重排的长尾推荐模型[J]. 《计算机应用》唯一官方网站, 2023, 43(4): 1122-1128.
[14]	宁明超, 张俊勃, 陈戈. 基于面向服务架构的工业软件的任务调度算法[J]. 《计算机应用》唯一官方网站, 2023, 43(3): 885-893.
[15]	柳春锋, 李峥, 王居凤. 分布式工厂中微型制造单元多目标优化[J]. 《计算机应用》唯一官方网站, 2023, 43(12): 3824-3832.

基于正交自适应鲸鱼优化的云计算任务调度

Cloud computing task scheduling based on orthogonal adaptive whale optimization

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 8

参考文献 20

相关文章 15

编辑推荐

Metrics

试验号	1	2	3	4	5	6	7
1	1	1	1	1	1	1	1
2	1	1	1	2	2	2	2
3	1	2	2	1	1	2	2
4	1	2	2	2	2	1	1
5	2	1	2	1	2	1	2
6	2	1	2	2	1	2	1
7	2	2	1	1	2	2	1
8	2	2	1	2	1	1	2

试验号	1	2	3	4	5	6	7
1	1	1	1	1	1	1	1
2	1	1	1	2	2	2	2
3	1	2	2	1	1	2	2
4	1	2	2	2	2	1	1
5	2	1	2	1	2	1	2
6	2	1	2	2	1	2	1
7	2	2	1	1	2	2	1
8	2	2	1	2	1	1	2

试验号	1	2	3	4	5	6	7
1	1	1	1	1	1	1	1
2	1	1	1	2	2	2	2
3	1	2	2	1	1	2	2
4	1	2	2	2	2	1	1
5	2	1	2	1	2	1	2
6	2	1	2	2	1	2	1
7	2	2	1	1	2	2	1
8	2	2	1	2	1	1	2

试验号	1	2	3	4	5	6	7
1	1	1	1	1	1	1	1
2	1	1	1	2	2	2	2
3	1	2	2	1	1	2	2
4	1	2	2	2	2	1	1
5	2	1	2	1	2	1	2
6	2	1	2	2	1	2	1
7	2	2	1	1	2	2	1
8	2	2	1	2	1	1	2

试验号	1	2	3	4	5	6	7
1	1	1	1	1	1	1	1
2	1	1	1	2	2	2	2
3	1	2	2	1	1	2	2
4	1	2	2	2	2	1	1
5	2	1	2	1	2	1	2
6	2	1	2	2	1	2	1
7	2	2	1	1	2	2	1
8	2	2	1	2	1	1	2

试验号	1	2	3	4	5	6	7
1	1	1	1	1	1	1	1
2	1	1	1	2	2	2	2
3	1	2	2	1	1	2	2
4	1	2	2	2	2	1	1
5	2	1	2	1	2	1	2
6	2	1	2	2	1	2	1
7	2	2	1	1	2	2	1
8	2	2	1	2	1	1	2