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

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]. 《计算机应用》唯一官方网站, 2022, 42(2): 599-605.
[2]	罗明宇, 骆晓萌, 朱文敏, 张磊, 范秀敏. 船舶狭小空间虚拟人维修姿态建模技术[J]. 计算机应用, 2021, 41(8): 2466-2472.
[3]	张闻强, 邢征, 杨卫东. 基于多区域采样策略的混合粒子群优化求解多目标柔性作业车间调度问题[J]. 计算机应用, 2021, 41(8): 2249-2257.
[4]	张祥飞, 鲁宇明, 张平生. 基于协同进化的约束多目标优化算法[J]. 计算机应用, 2021, 41(7): 2012-2018.
[5]	陈家豪, 殷新春. 基于云雾计算的可追踪可撤销密文策略属性基加密方案[J]. 计算机应用, 2021, 41(6): 1611-1620.
[6]	葛丽娜, 胡雨谷, 张桂芬, 陈园园. 云计算环境基于客体属性匹配的逆向混合访问控制方案[J]. 计算机应用, 2021, 41(6): 1604-1610.
[7]	杨翎, 姜春茂. 基于三支决策的虚拟机节能迁移策略[J]. 计算机应用, 2021, 41(4): 990-998.
[8]	马晓航, 廖灵霞, 李智, 秦斌, 赵涵捷. 基于动态混合超时的软件定义网络多目标优化[J]. 《计算机应用》唯一官方网站, 2021, 41(12): 3658-3665.
[9]	乔钢柱, 王瑞, 孙超利. 基于分解的高维多目标改进进化算法[J]. 《计算机应用》唯一官方网站, 2021, 41(11): 3097-3103.
[10]	平凡, 汤小春, 潘彦宇, 李战怀. 不规则任务在图形处理器集群上的调度策略[J]. 《计算机应用》唯一官方网站, 2021, 41(11): 3295-3301.
[11]	孙晓玲, 杨光, 沈焱萍, 杨秋格, 陈涛. 基于可拆分倒排索引的可搜索加密方案[J]. 《计算机应用》唯一官方网站, 2021, 41(11): 3288-3294.
[12]	董海, 吴瑶, 齐新娜. 基于改进鲸鱼优化算法的血液供应链网络多目标鲁棒优化设计[J]. 计算机应用, 2021, 41(10): 3063-3069.
[13]	童林, 官铮. 改进鲸鱼优化支持向量机的交通流量模糊粒化预测[J]. 计算机应用, 2021, 41(10): 2919-2927.
[14]	陆荣秀, 陈明明, 杨辉, 朱建勇. 基于溶液图像时序特征的元素组分含量动态监测系统[J]. 计算机应用, 2021, 41(10): 3075-3081.
[15]	李二超, 李康伟. 基于最小距离和聚合策略的分解多目标进化算法[J]. 计算机应用, 2021, 41(1): 22-28.

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

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