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

doi:10.19665/j.issn1001-2400.2019.01.021

Abstract

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

CLC Number:

TP301.6

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

Figures/Tables 5

References 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)

Enhanced multi-objective evolutionary algorithm for workflow scheduling on the cloud platform

RichHTML

PDF (PC)

Like

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 5

References 20

Related Articles 13

Metrics

Comments

Recommended 10

[1]	LI Huadong,ZHANG Xueliang,WANG Xiaolei,LIU Hui,WANG Pengcheng,DU Junzhao. Multi-node cooperative game load balancing strategy in the Kubernetes cluster [J]. Journal of Xidian University, 2021, 48(6): 16-22.
[2]	LOU Ao,YAO Minli,JIA Weimin,YUAN Ding. Tent chaos and variable neighborhood local search optimized GSA [J]. Journal of Xidian University, 2019, 46(5): 120-127.
[3]	HAN Kun;ZHANG Hailin;XIN Dan;WU Bo;KANG Yuanji. Design method of an identity-based fully homomorphic encryption library [J]. Journal of Xidian University, 2017, 44(4): 56-61.
[4]	JING Weipeng;HUO Shuaiqi;CHEN Guangsheng;LIU Yaqiu. Novel mixed-criticality reliability scheduling strategy and schedulability test [J]. Journal of Xidian University, 2016, 43(6): 158-163.
[5]	HUANG Chunshui;REN Yanli;CAI Jianxing. Verifiable outsourcing scheme for batch modular exponentiations [J]. Journal of Xidian University, 2016, 43(4): 135-140.
[6]	JING Weipeng;WU Zhibo;LIU Hongwei;SHU Yanjun. Multiple DAGs dynamic workflow reliability scheduling algorithm in a cloud computing system [J]. Journal of Xidian University, 2016, 43(2): 83-88.
[7]	LIU Xing;YUAN Chaowei;YANG Zhen;LI Zhenjun. Services promote Lyapunov-based strategy in mobile cloud computing [J]. J4, 2015, 42(6): 138-144.
[8]	JIANG Jianguo;ZHOU Jiawei;ZHENG Yingchun;WANG Tao. Adaptive bacterial foraging optimization algorithm [J]. J4, 2015, 42(1): 75-81.
[9]	LU Di;MA Jianfeng;WANG Yichuan;XI Ning;ZHANG Liumei;MENG Xianjia. Enhanced fairness-based multi-resource allocation algorithm for cloud computing [J]. J4, 2014, 41(3): 162-168.
[10]	WANG Yichuan;MA Jianfeng;LU Di;ZHANG Liumei;MENG Xianjia. Cloud droplets freezing attack in cloud computing [J]. J4, 2014, 41(3): 116-122.
[11]	ZHU Xudong;LI Hui;GUO Zhen. Privacy-preserving query over the encrypted image in cloud computing [J]. J4, 2014, 41(2): 151-158.
[12]	TONG Fei;WANG Jun;LI Hongwei. Novel passive radar location algorithm based on Memetic optimization by using the bearing-and-Doppler frequency [J]. J4, 2012, 39(4): 46-51+102.
[13]	HAN Li-xia1;WANG Yu-ping2. Novel genetic algorithm for the graph coloring problem [J]. J4, 2008, 35(2): 309-313.