改进多目标进化算法的云工作流调度

doi:10.19665/j.issn1001-2400.2019.01.021

摘要/Abstract

摘要：

针对云计算和云存储资源复杂变化的定价机制给云工作流调度带来了极大的挑战问题,建立了考虑定价机制的多目标云工作流调度模型。针对云工作流调度问题的特点,设计了一种实数编码机制,使得现有的基于实数编码的交叉算子能够直接用于求解云工作流调度问题,从而避免了现有组合优化方法需要进行解的可行性修正的问题。进一步在MOEA/D算法框架下,设计了一种启发式局部搜索策略,提出了一种新的进化多目标云工作流调度算法。仿真试验结果表明,与目前主流的进化多目标优化算法相比,该算法在求得帕累托最优解集的宽广性和均匀性上具有明显的优势,且算法稳定性更好。该方法对于云平台资源利用率的提升具有重要的应用价值。

关键词: 工作流调度, 云计算, 进化多目标优化算法, 局部搜索

Abstract:

The complex and dynamic pricing mechanism raises big challenges to the workflow scheduling on the cloud platform. Considering the prices of the virtualized computing and storage resources, a multi-objective optimization model is developed for the workflow running on a cloud platform. Based on the character of the target problem, a real-coding mechanism is developed for the workflow scheduling problem, so that the crossover operators in a real-coded evolutionary based optimizer can be conveniently employed and the solution repairing step in combinatorial optimization algorithms can be skipped. Following the algorithm framework of the MOEA/D, a local search strategy is designed, and a new multi-objective workflow scheduling algorithm is proposed. Experimental studies have illustrated that the proposed algorithm can obtain Pareto optimal solution sets with better coverage and uniformity than the compared algorithms, which will contribute to improving the utilization of the resources on the cloud platform.

Key words: workflow scheduling, cloud computing, evolutionary multi-objective optimization algorithm, local search

中图分类号:

TP301.6

王燕. 改进多目标进化算法的云工作流调度[J]. 西安电子科技大学学报, 2019, 46(1): 130-136.

WANG Yan. Enhanced multi-objective evolutionary algorithm for workflow scheduling on the cloud platform[J]. Journal of Xidian University, 2019, 46(1): 130-136.

图/表 5

图1

图2

表1

图3

表2

参考文献 20

[1]	KAVIS M J. 让云落地:云计算服务模式(SaaS、PaaS和IaaS)设计决策[M]. 陈志伟,译. 北京: 电子工业出版社, 2016.
[2]	SMANCHAT S, VIRIYAPANT K . Taxonomies of Workflow Scheduling Problem and Techniques in the Cloud[J]. Future Generation Computer Systems, 2015,52:1-12. doi: 10.1016/j.future.2015.04.019
[3]	ATKINSON M, GESING S, MONTAGNAT J , et al. Scientific Workflows: Past, Present and Future[J]. Future Generation Computer Systems, 2017,75:216-227. doi: 10.1016/j.future.2017.05.041
[4]	DEB K, SINDHYA K, HAKANEN J. Multi-objective Optimization, in Decision Sciences: Theory and Practice[M]. Boca Raton: CRC Press, 2016: 145-184.
[5]	TOPCUOGLU H, HARIRI S, WU M . Performance-effective and Low-complexity Task Scheduling for Hetero-geneous Computing[J]. IEEE Transactions on Parallel and Distributed Systems, 2002,13(3):260-274. doi: 10.1109/71.993206
[6]	SIH G C, LEE E A . A Compile-time Scheduling Heuristic for Interconnection-constrained Heterogeneous Processor Architectures[J]. IEEE Transactions on Parallel and Distributed Systems, 1993,4(2):175-187. doi: 10.1109/71.207593
[7]	KWOK Y K, AHMAD I . Dynamic Critical-path Scheduling: an Effective Technique for Allocating Task Graphs to Multiprocessors[J]. IEEE Transactions on Parallel and Distributed Systems, 1996,7(5):506-521. doi: 10.1109/71.503776
[8]	ARABNEJAD H, BARBOSA J G . List Scheduling Algorithm for Heterogeneous Systems by an Optimistic Cost Table[J]. IEEE Transactions on Parallel and Distributed Systems, 2014,25(3):682-694. doi: 10.1109/TPDS.2013.57
[9]	LEE Y C, HAN H, ZOMAYA A Y , et al. Resource-efficient Workflow Scheduling in Clouds[J]. Knowledge-Based Systems, 2015,80:153-162. doi: 10.1016/j.knosys.2015.02.012
[10]	DUAN R, PRODAN R, LI X . Multi-objective Game Theoretic Scheduling of Bag-of-tasks Workflows on Hybrid Clouds[J]. IEEE Transactions on Cloud Computing, 2014,2(1):29-42. doi: 10.1109/TCC.2014.2303077
[11]	YE X, LIU S H, YIN Y L , et al. User-oriented Many-objective Cloud Workflow Scheduling Based on an Improved Knee Point Driven Evolutionary Algorithm[J]. Knowledge-Based Systems, 2017,137:113-124.
[12]	LI L M, WANG Y L, TRAUTMANN H , et al. Multiobjective Evolutionary Algorithms Based on Target Region Preferences[J]. Swarm and Evolutionary Computation, 2018,40:196-215. doi: 10.1016/j.swevo.2018.02.006
[13]	DEB K, AGRAWAL S, PRATAP A , et al. A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II[J]. IEEE Transactions on Evolutionary Computation, 2002,6(2):182-197. doi: 10.1109/4235.996017
[14]	DENYSIUK R, GASPAR-CUNHA A . Multiobjective Evolutionary Algorithm Based on Vector Angle Neighborhood[J]. Swarm and Evolutionary Computation, 2017,37:45-57. doi: 10.1016/j.swevo.2017.05.005
[15]	BEUME N, NAUJOKS B, EMMERICH M . SMS-EMOA: Multiobjective Selection Based on Dominated Hypervolume[J]. European Journal of Operational Research, 2007,181:1653-1669. doi: 10.1016/j.ejor.2006.08.008
[16]	ZAPOTECAS-MARTíNEZ S, LóPEZ-JAIMES A, GARCíA-NáJERA A . LIBEA: a Lebesgue Indicator-based Evolutionary Algorithm for Multi-objective Optimization[J/OL].[2018-05-16]. DOI: 10.1016/j.swevo.2018.05.004.
[17]	ZHANG Q F, LI H . MOEA/D: a Multiobjective Evolutionary Algorithm Based on Decomposition[J]. IEEE Transactions on Evolutionary Computation, 2007,11(6):712-731. doi: 10.1109/TEVC.2007.892759
[18]	TRIVEDI A, SRINIVASAN D, SANYAL K , et al. A Survey of Multiobjective Evolutionary Algorithms Based on Decomposition[J]. IEEE Transactions on Evolutionary Computation, 2017,21(3):440-462. doi: 10.1109/TEVC.2016.2608507
[19]	BHARATHI S, CHERVENAK A, DEELMAN E, et al. Characterization of Scientific Workflows [C]//Proceedings of the Third Workshop on 2008 Workflows in Support of Large-scale Science. Piscataway: IEEE, 2008: 1-10.
[20]	ZITZLER E, THIELE L . Multiobjective Evolutionary Algorithms: a Comparative Case Study and the Strength Pareto Approach[J]. IEEE Transactions on Evolutionary Computation, 1999,3(4):257-271. doi: 10.1109/4235.797969

工作流	任务个数	任务之间依赖个数	任务平均数据大小/MB	任务平均执行时间/s
Inspiral-50	50	198	9.16	226.19
Montage-50	50	206	3.36	9.78
CyberShake-100	100	380	849.60	31.53
Epigenomics-100	100	322	395.10	3 954.90

工作流问题实例	对比算法
工作流问题实例	EADLS	MOEA/D	NSGA-II
Inspiral-50	124 702.392 8 (145.697 5)	123 331.025 6 (1 134.857 9)	123 418.972 0 (1 048.300 7)
Montage-50	144.673 8 (0.054 4)	143.361 7 (0.062 2)	144.030 8 (0.048 7)
CyberShake-100	4 474.894 2 (31.069 4)	4 407.043 1 (47.024 6)	4 427.957 6 (43.270 8)
Epigenomics-100	113 946 497.541 4 (118 335.068 3)	113 351 862.043 0 (166 740.277 1)	113 036 079.242 0 (419 149.909 1)