Multi Objective Optimization Task Scheduling Algorithm Based on CSA and PSO

WANG Li-juan; WU Feng

doi:10.13718/j.cnki.xsxb.2021.03.005

2021 Volume 46 Issue 3

Article Contents

Previous Article Next Article

WANG Li-juan, WU Feng. Multi Objective Optimization Task Scheduling Algorithm Based on CSA and PSO[J]. Journal of Southwest China Normal University(Natural Science Edition), 2021, 46(3): 27-32. doi: 10.13718/j.cnki.xsxb.2021.03.005

Citation:

WANG Li-juan, WU Feng. Multi Objective Optimization Task Scheduling Algorithm Based on CSA and PSO[J]. Journal of Southwest China Normal University(Natural Science Edition), 2021, 46(3): 27-32. doi: 10.13718/j.cnki.xsxb.2021.03.005

Multi Objective Optimization Task Scheduling Algorithm Based on CSA and PSO

WANG Li-juan¹,
WU Feng²

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

More Information

Received Date: 09/02/2020
Available Online: 20/03/2021
MSC: TP391

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.
- cloud computing,
- task scheduling,
- multi-objective optimization,
- cuckoo search,
- particle swarm optimization

References

[1]	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. Google Scholar
[2]	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. Google Scholar
[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 CrossRef Google Scholar
[4]	徐健锐, 朱会娟. 云计算环境中面向DAG任务的多目标调度算法[J]. 计算机应用研究, 2019, 36(1): 31-36. Google Scholar
[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 CrossRef Google Scholar
[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 CrossRef Google Scholar
[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. Google Scholar
[8]	侯欢欢. 自适应动态调整粒子群的云计算任务调度[J]. 计算机应用与软件, 2019, 36(9): 46-51, 116. Google Scholar
[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 CrossRef Google Scholar
[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 CrossRef Google Scholar
[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 CrossRef Google Scholar
[12]	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. Google Scholar
[13]	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. Google Scholar
[14]	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. Google Scholar
[15]	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. Google Scholar
[16]	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. Google Scholar

Access History

通讯作者: 陈斌, bchen63@163.com

1.
沈阳化工大学材料科学与工程学院沈阳 110142

Figures(6) / Tables(1)

Export Citation

PDF

XML

Article Metrics

Article views(1681) PDF downloads(190) Cited by(0)

Access History

Other Articles By Authors

on this site
- WANG Li-juan
- WU Feng
on Google Scholar
- WANG Li-juan
- WU Feng

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. 结语

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

Figure (6) Table (1) Reference (16)

Name
	Name cannot be empty!
E-mail
	Mailbox cannot be empty! Mailbox cannot be empty!
Telephone
	Mobile number cannot be empty! Please enter a valid mobile number!
Title

Content
Verification Code

Message Board

Multi Objective Optimization Task Scheduling Algorithm Based on CSA and PSO