基于CSA和PSO的多目标优化任务调度算法

王丽娟; 吴锋

doi:10.13718/j.cnki.xsxb.2021.03.005

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名

姓名不能为空！

邮箱

邮箱不能为空！非法的邮箱地址。

手机号码

电话不能为空！

请输入有效手机号!

标题

标题不能为空！

留言内容

内容不能为空！

验证码

验证码不能为空！

验证码错误！

基于CSA和PSO的多目标优化任务调度算法

1.
焦作师范高等专科学校信息工程学院，河南焦作 454000

2.
信阳农林学院信息工程学院，河南信阳 464006

详细信息

作者简介:
王丽娟, 硕士, 讲师, 主要从事计算机应用技术研究 .

中图分类号: TP391

Multi Objective Optimization Task Scheduling Algorithm Based on CSA and PSO

1.
School of Information Engineering, Jiaozuo Normal College, Jiaozuo Henan 454000, China

2.
School of Information Engineering, Xinyang Agriculture and Forestry University, Xinyang Henan 464006, China

摘要: 针对现有云计算环境中任务调度算法资源利用率低、完成时间长和调度成本高的问题, 提出一种基于布谷鸟搜索算法(Cuckoo Search Algorithm, CSA)和粒子群优化(Particle Swarm Optimization, PSO)混合的多目标优化任务调度策略.该策略以完成时间、成本以及最后期限违反率为目标函数, 将布谷鸟搜索算法和粒子群优化有效地组合来执行智能优化任务调度问题, 避免调度过程中出现局部最优现象.实验结果表明: 相对于其他启发式调度算法, 本文提出的方法明显具有优势, 可以最大程度地降低完成时间、调度成本和最后期限违反率.

Abstract: Aiming at the problems of low resource utilization, long makespan and high scheduling cost of task scheduling algorithms in existing cloud computing environments, a multi-objective optimization task scheduling strategy based on Cuckoo Search Algorithm(CSA) and Particle Swarm Optimization(PSO)has been proposed.According tothe strategy, the cuckoo search algorithm and the particle swarm optimization are combinedto perform the intelligent optimization task scheduling problem with the makespan, cost and deadline violation rate as the objective function, and to avoid the local optimal phenomenon in the scheduling process. The experimental results show that compared with other heuristic scheduling algorithms, the proposed method has obvious advantages, which can minimize the completion time, scheduling cost and deadline violation rate.

Key words:

算法1：CSA和PSO混合调度算法

步骤1：生成初始化种群2N；

步骤2：随机将种群分为2组，分别为CSA群和PSO群，每组N个个体；

步骤3：目标函数F(x)初始化，利用式(8)评估适应度值；

步骤4：重复步骤4到6，直到就绪任务(K)小于最大任务数；

步骤5：对于每个任务(T)，使用CSA寻找新解；

步骤6：对于每个任务(T)，使用PSO寻找新解；

步骤7：利用下列公式寻找两种算法的混合解

$z_{i}^{d}(k+1)=s \times x_{i}(k+1)+(1-s) \times y_{i}^{d}(k+1) ;$

步骤8：if (z(k+1) < f(z(x))) then

用当前解替换i的解；

步骤9：在2N中选择任何资源R；

如果基于平台的资源R的执行时间较长，则淘汰资源R并在N中另选一个资源；

步骤10：更新 $x_{i}^{d}(k+1)=y_{i}^{d}(k+1)=z_{i}^{d}(k+1)$、p_i和p_g；

步骤11：保留并排序最优解；

步骤12：结束.

基于CSA和PSO的多目标优化任务调度算法

作者简介: 王丽娟, 硕士, 讲师, 主要从事计算机应用技术研究
1. 焦作师范高等专科学校信息工程学院，河南焦作 454000

2. 信阳农林学院信息工程学院，河南信阳 464006

收稿日期: 2020-02-09

关键词:

Multi Objective Optimization Task Scheduling Algorithm Based on CSA and PSO

¹,

1. 焦作师范高等专科学校信息工程学院，河南焦作 454000

2. 信阳农林学院信息工程学院，河南信阳 464006

Received Date: 2020-02-09

Keywords:

全文HTML

云环境是指能够从动态虚拟化的资源池中向用户提供计算能力、存储能力或者虚拟机服务的互联网大数据环境^[1]. 云提供的服务可以分为软件即服务(SaaS)、平台即服务(PaaS)和基础设施即服务(IaaS). 用户可以利用这些服务访问虚拟资源，但必须以“按次付费”模式为云服务付费. 近年来，随着云的应用和推广，分散的云数据中心可以提供更多高质量和可靠的服务. 在使用云服务时，由于用户在物理资源使用方面直接依赖于云服务，因此优化任务调度成为一种必要条件^[2-3].

云环境中的任务调度策略是指通过算法为用户任务提供更合理的资源分配方案，在最短的完成时间内实现资源优化、负载均衡等目标^[4]. 目前，许多云计算任务调度模型通过引入启发式优化算法来解决任务调度的非确定多项式(Nondeterministic Polynomial, NP)完全问题^[5-6]. 文献[7]提出一种基于布谷鸟搜索的任务调度方法，该方法在可用的虚拟机之间有效地分配任务，并保持总体响应时间最小，使计算资源得到最佳的利用. 文献[8]为提高云计算任务调度效率，提出一种新的云计算任务调度算法，该算法以等待时间、资源负载均衡程度及任务完成所耗费用为目标函数，利用改进的分数阶达尔文粒子群算法自适应搜索最优解. 文献[9]结合负载利用率、能耗、迁移成本和迁移时间，提出一种新的多目标函数，并且将遗传算法和灰狼优化算法相结合对该目标函数进行优化，有效地改善了任务调度. 文献[10]提出一种基于布谷鸟搜索算法和反向学习算法的多目标任务调度策略，该策略采用完成时间和成本作为优化问题的重要约束条件来求解任务调度的NP完全问题，实现高性能、低成本的资源动态分配目标. 文献[11]提出一种混合粒子群算法和爬山算法对任务调度完成时间进行优化，提高了云计算异构环境中的服务效率.

当综合考虑性能、成本和最后期限违反率时，上述文献并未提供接近最佳的结果. 针对这一问题，本文提出一种基于布谷鸟搜索和粒子群优化算法的任务调度策略，该策略将CSA和PSO两种算法混合在一起，混合算法既利用CSA算法的搜索随机性，扩大算法的搜索范围，又可以利用PSO算法的优势提高算法的收敛性，从而克服PSO算法陷入局部最优和CSA算法收敛速度慢的缺点，可以更有效地优化任务和资源，实现相应虚拟机(Virtual Machine, VM)之间最小的完成时间和成本.

1. 相关背景

1.1. 布谷鸟搜索算法

布谷鸟搜索算法(Cuckoo Search Algorithm, CSA)^[12]是在2010年提出的一种生物启发式智能优化算法，该算法结构简单，易于实现，而且可以与其他优化算法结合，获得性能更佳的混合算法. CSA参考了自然界中布谷鸟的寄宿繁衍行为和果蝇的莱维飞行行为，可以为连续优化问题快速有效地寻找到最优解. 该算法全局搜索能力较强，但容易陷入局部最优.

布谷鸟搜索算法存在3个基本假设：①每只布谷鸟一次仅产一个卵，并随机选择一个寄生巢；②在随机选择的一组寄生巢中，最好的巢将会保留到下一代；③可利用寄生巢数量固定，宿主鸟发现外来卵的概率为P_a∈[0, 1]. 被发现后布谷鸟选择丢弃卵或者更换新巢.

布谷鸟卵寄生的巢即为空间的一个解，寄生巢位置的好坏代表解的适应度值，布谷鸟寻找寄生巢的过程就是算法搜索和优化的过程. 布谷鸟寻找寄生巢以及位置x更新的公式被定义为

其中，i=1, 2, …, n, α为步长控制量，Levy为莱维飞行搜索，服从Levy分布式

1.2. 粒子群优化算法

粒子群优化(PSO)^[13]算法是在1995年提出的一种基于群体智能的全局随机搜索算法. 在PSO中，每个优化问题的潜在解都是搜索空间中的一个粒子，所有粒子都有一个被优化的函数决定的适应度值，每个粒子的飞行速度还决定其飞行的方向和距离，粒子群追随当前的最优粒子在解空间中搜索..

PSO初始化为一群随机粒子，然后通过迭代找到最优解. 在每一次迭代中，粒子通过跟踪粒子本身所找到的最优解p_i和整个种群目前找到的最优解p_g两个极值来更新自己的位置和速度. 假设在d维的目标搜索空间中，粒子群包含有N个粒子，则第i个粒子在k+1时刻的速度和位置可以根据k时刻的速度 $v_{i}^{d}(k)$和位置 $y_{i}^{d}(k)$更新为

其中，i=1, 2, …, N, d=1, 2, …, D, ω为惯性权重，c₁, c₂表示学习因子，r₁, r₂∈[0, 1]是随机数，α为约束因子，用来控制速度的权重.

2. 基于CSA和PSO的多目标任务调度算法

任务调度的主要目标是有效地将任务分配给云服务提供商的相应虚拟机(VM), 并使得目标函数最小化. 为了改善和优化调度性能和成本，提高云环境下的资源利用效率，本文提出一种多目标函数混合任务调度算法，通过引入布谷鸟搜索和粒子群优化算法对目标问题进行优化. 许多用户将任务提交到任务管理器，任务管理器的作用是接受任务和管理任务. 同时，任务管理器通过预算、成本、内存和最后期限提交任务至调度程序. 任务由调度程序进行调度和映射到全局资源管理器. 全局资源管理器全局控制资源，监视资源上的持续时间任务和计算资源成本. 整个过程在云中完成，该云允许存在各种物理节点和虚拟机.

在云计算中调度算法的效率取决于性能和预算成本. 在定义任务、资源和成本的基础上，提出一种多目标优化调度模型，以优化云中的调度. 提出的优化模型将K个任务调度到N个资源上，从而达到优化的目的. 除了优化，还考虑了最后期限和预算成本的约束条件. 假定每个任务的执行都必须在单个VM中完成.

在当前云计算中，存在N个资源R={R₁, R₂, …R_N}和K个任务T={T₁, T₂, …, T_K}. 云上的每个资源由中央处理器(CPU)和内存来定义R_j=(C_j; M_j), 用户提交的任务定义为T_i=(C_i; M_i; DL_i; B_i), 其中C, M分别表示CPU和内存利用率，DL表示任务的最后期限，B表示用户预算成本. 多目标优化问题可以描述为

其中，目标函数的性能由MakSpan(x)表示，x表示可行的解决方案. Budget(x)定义预算成本和对应成本的资源(CPU和内存). 式(7)和式(8)给出了用户预算与资源成本模型中资源成本之间的关系. 根据资源定义，通过将资源成本划分为CPU和内存来使用资源成本模型. 式(9)、式(10)定义了CPU和内存的成本

其中，C^base表示资源利用率最低时的基本成本，M^base表示内存空间为1 GB时的基本成本，t_ij表示任务T_i在资源R_j运行的时间，C^Tran, M^Tran分别表示与成本相关的CPU传输和内存传输.

式(11)和式(12)表示从成本函数获得的CPU和内存的成本模型

通过求解多目标优化问题可以获得最佳解决方案，本文提出的多目标函数混合任务调度算法具体步骤由算法1给出.

4. 结语

本文提出一种基于布谷鸟搜索和粒子群优化算法的多目标优化任务调度方法，用于解决现有云计算环境中任务调度算法在完成时间、成本和最后期限违反率等方面表现不佳的问题. 该方法通过将布谷鸟搜索和粒子群优化两种启发式智能优化算法结合在一起，有效地提高了任务调度过程中的资源利用率，降低了任务的完成时间、成本和最后期限违反率. 相对于其他任务调度优化算法，本文提出的策略具有更佳的性能.

参考文献 (16)

[1]	doi: http://www.sciencedirect.com/science/article/pii/S004579061731073X KUMAR M, SHARMA S C. Deadline Constrained Based Dynamic Load Balancing Algorithm with Elasticity in Cloud Environment[J]. Computers & Electrical Engineering, 2018, 69: 395-411.
[2]	doi: http://www.researchgate.net/publication/321496078_Task_Scheduling_in_Cloud_Computing_using_Lion_Optimization_Algorithm ALMEZEINI N, HAFEZ A. Task Scheduling in Cloud Computing Using Lion Optimization Algorithm[J]. International Journal of Advanced Computer Science and Applications, 2017, 8(11): 77-83.
[3]	LIN W W, WANG W Q, WU W T, et al. A Heuristic Task Scheduling Algorithm Based on Server Power Efficiency Model in Cloud Environments[J]. Sustainable Computing: Informatics and Systems, 2018, 20: 56-65. doi: 10.1016/j.suscom.2017.10.007
[4]	徐健锐, 朱会娟. 云计算环境中面向DAG任务的多目标调度算法[J]. 计算机应用研究, 2019, 36(1): 31-36. doi: https://www.cnki.com.cn/Article/CJFDTOTAL-JSYJ201901008.htm
[5]	ARUNARANI A, MANJULA D, SUGUMARAN V. Task Scheduling Techniques in Cloud Computing: a Literature Survey[J]. Future Generation Computer Systems, 2019, 91: 407-415. doi: 10.1016/j.future.2018.09.014
[6]	SALEH H, NASHAAT H, SABER W, et al. IPSO Task Scheduling Algorithm for Large Scale Data in Cloud Computing Environment[J]. IEEE Access, 2019, 7: 5412-5420. doi: 10.1109/ACCESS.2018.2890067
[7]	AGARWAL M, SRIVASTAVA G M S. A Cuckoo Search Algorithm-Based Task Scheduling in Cloud Computing[M]//Advances in Computer and Computational Sciences. Singapore: Springer, 2017.
[8]	侯欢欢. 自适应动态调整粒子群的云计算任务调度[J]. 计算机应用与软件, 2019, 36(9): 46-51, 116. doi: https://www.cnki.com.cn/Article/CJFDTOTAL-JYRJ201909010.htm
[9]	GOBALAKRISHNAN N, ARUN C. A New Multi-Objective Optimal Programming Model for Task Scheduling Using Genetic Gray Wolf Optimization in Cloud Computing[J]. The Computer Journal, 2018, 61(10): 1523-1536. doi: 10.1093/comjnl/bxy009
[10]	KRISHNADOSS P, JACOB P. OCSA: Task Scheduling Algorithm in Cloud Computing Environment[J]. International Journal of Intelligent Engineering and Systems, 2018, 11(3): 271-279. doi: 10.22266/ijies2018.0630.29
[11]	DORDAIE N, NAVIMIPOUR N J. A Hybrid Particle Swarm Optimization and Hill Climbing Algorithm for Task Scheduling in the Cloud Environments[J]. ICT Express, 2018, 4(4): 199-202. doi: 10.1016/j.icte.2017.08.001
[12]	doi: http://www.researchgate.net/publication/335232316_Task_Scheduling_of_an_Improved_Cuckoo_Search_Algorithm_in_Cloud_Computing LIU W L. Task Scheduling of an Improved Cuckoo Search Algorithm in Cloud Computing[J]. International Journal of Performability Engineering, 2019, 15(7): 1965-1975.
[13]	doi: http://www.worldscientific.com/doi/abs/10.1142/S0219622018500244?src=recsys AGARWAL M, SRIVASTAVA G M S. Genetic Algorithm-Enabled Particle Swarm Optimization(PSOGA)-Based Task Scheduling in Cloud Computing Environment[J]. International Journal of Information Technology & Decision Making, 2018, 17(4): 1237-1267.
[14]	doi: http://www.ncbi.nlm.nih.gov/pubmed/28467505 MADNI S H H, ABD LATIFF M S, ABDULLAHI M, et al. Performance Comparison of Heuristic Algorithms for Task Scheduling in IaaS Cloud Computing Environment[J]. PLoS One, 2017, 12(5): 176321-176346.
[15]	doi: http://pubmedcentralcanada.ca/pmcc/articles/PMC5435234/ IDRIS H, EZUGWU A E, JUNAIDU S B, et al. An Improved Ant Colony Optimization Algorithm with Fault Tolerance for Job Scheduling in Grid Computing Systems[J]. PLoS One, 2017, 12(5): 177567-177590.
[16]	doi: http://www.sciencedirect.com/science/article/pii/S0950705119300322 Elaziz M A, Xiong S, Jayasena K P N, et al. Task scheduling in cloud computing based on hybrid moth search algorithm and differential evolution[J]. Knowledge-Based Systems, 2019, 169(1): 39-52.

留言板