计算机科学 ›› 2018, Vol. 45 ›› Issue (5): 31-37.doi: 10.11896/j.issn.1002-137X.2018.05.005

• 网络与通信 • 上一篇    下一篇

多目标最优化云工作流调度进化遗传算法

王国豪,李庆华,刘安丰   

  1. 丽水学院工学院 浙江 丽水323000,丽水学院工学院 浙江 丽水323000,中南大学信息科学与工程学院 长沙410083
  • 出版日期:2018-05-15 发布日期:2018-07-25
  • 基金资助:
    本文受浙江省教育厅科研备案项目(Y201534160),浙江省公益性应用研究计划项目(2016C31G2260015)资助

Evoluation Genetic Algorithm of Multi-objective Optimization Scheduling on Cloud Workflow

WANG Guo-hao, LI Qing-hua and LIU An-feng   

  • Online:2018-05-15 Published:2018-07-25

摘要: 为了实现云环境中科学工作流调度的执行跨度和执行代价的同步优化,提出了一种多目标最优化进化遗传调度算法MOEGA。该算法以进化遗传为基础,定义了任务与虚拟机映射、虚拟机与主机部署间的编码机制,设计了满足多目标优化的适应度函数。同时,为了满足种群的多样性,在调度方案中引入了交叉与变异操作,并使用启发式方法进行种群初始化。通过4种现实科学工作流的仿真实验,将其与同类型算法进行了性能比较。结果表明,MOEGA算法不仅可以满足工作流截止时间约束,而且在降低任务执行跨度与执行代价的综合性能方面也优于其他算法。

关键词: 云计算,遗传算法,工作流调度,多目标优化,适应度函数

Abstract: To implement the synchronous optimization of makespan and execution cost of scientific workflow scheduling in cloud environment,this paper proposed a multi-objective optimization evoluation genetic scheduling algorithm named MOEGA.Based on evoluation genetics,MOEGA defines the encoding mechanism of the mapping between tasks and virtual machines,virtual machines and hosts placement,and designs the fitness function satisfying multi-objective optimization.Meanwhile,for meeting the diversity of population,the crossover operation and mutation operation are introduced into the scheduling scheme,and the heuristics is used to initialize the population.Through the experimental tests of four types of scientific workflow in reality,its performance was compared with the same types of algorithms.The results show that MOEGA not only can meet the deadline constraint of workflow,but also outperforms other algorithms in overall performance of reducing the execution makespan and execution cost.

Key words: Cloud computing,Genetic algorithm,Workflow scheduling,Multi-objective optimization,Fitness function

[1] VOCKLER J S,JUVE G,DEELMAN E,et al.Experiencesusing cloud computing for a scientific workflow application[C]∥Proceedings of the 2nd International Workshop on Scientific Cloud Computing.USA:ACM Press,2011:15-24.
[2] LIU L,ZHANG M,LIN Y,et al.A survey on workflow mana-gement and scheduling in cloud computing[C]∥14th IEEE/ACM International Symposium on Cluster,Cloud and Grid Computing.USA:IEEE Press,2014:837-846.
[3] RODRIGUEZ M,BUYYA R.Deadline based resource provisioning and scheduling algorithm for scientific workflows on clouds[J].IEEE Transactions Cloud Computing,2014,2(2):222-235.
[4] ARABNEJAD H,BARBOSA J G.A budget constrained scheduling algorithm for workflow applications[J].Journal of Grid Computing,2014,2(14):1-15.
[5] TOPCUOGLU H,HARIRI S,WU M Y.Performance-effective and low-complexity task scheduling for heterogeneous computing[J].IEEE Transactions Parallel Distributed Systems,2012,3(3):260-274.
[6] ZHENG W,SAKLEEARIOU R.Budget-deadline constrainedworkflow planning for admission control[J].Journal of Grid Computing,2013,1(4):633-651.
[7] YANG Y L,PENG X G,HUANG M X,et al.Cloud workflow scheduling based on discrete particle swarm optimization[J].Application Research of Computers,2014,1(12):3677-3681.(in Chinese) 杨玉丽,彭新光,黄名选,等.基于离散粒子群优化的云工作流调度[J].计算机应用研究,2014,1(12):3677-3681.
[8] SU S,LI J,HUANG Q,et al.Cost-efficient task scheduling for executing large programs in the cloud[J].Parallel Computing,2013,9(4):177-188.
[9] GARG R,SINGH A.Multi-objective Workflow Grid Scheduling Based on Discrete Particle Swarm Optimization[M]∥Swarm,Evolutionary,and Memetic Computing.Springer Berlin Heidelberg,2011:183-190.
[10] GARG R,SINGH A K.Multi-objective workflow grid scheduling using ε-fuzzy dominance sort based discrete particle swarm optimization[J].Journal of Supercomputing,2014,8(2):709-732.
[11] ZHANG F,CAO J,HWANG K,et al.Ordinal Optimized Scheduling of Scientific Workflows in Elastic Compute Clouds[C]∥IEEE Third International Conference on Cloud Computing Technology and Science.IEEE Computer Society,2011:9-17.
[12] LI K W,ZHANG G X,ZHU Z M.A decomposition-based multi-objective workflow scheduling algorithm in cloud computing[J].Computer Engineering & Science,2016,8(8):1588-1594.(in Chinese) 李克武,张功萱,朱昭萌.云环境中基于分解的多目标工作流调度算法[J].计算机工程与科学,2016,8(8):1588-1594.
[13] CHEN W,DEELMAN E.WorkflowSim:a toolkit for simulating scientific workflows in distributed environments[C]∥IEEE 8th International Conference on E-Science (e-Science).USA:IEEE Press,2012:1-8.
[14] JUVE G,CHERVENAK A,DEELMAN E,et al.Characterizing and profiling scientific workflows[J].Future Generation Computer System,2013,9(3):682-692.

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] 编辑部. 新网站开通,欢迎大家订阅![J]. 计算机科学, 2018, 1(1): 1 .
[2] 雷丽晖,王静. 可能性测度下的LTL模型检测并行化研究[J]. 计算机科学, 2018, 45(4): 71 -75 .
[3] 孙启,金燕,何琨,徐凌轩. 用于求解混合车辆路径问题的混合进化算法[J]. 计算机科学, 2018, 45(4): 76 -82 .
[4] 张佳男,肖鸣宇. 带权混合支配问题的近似算法研究[J]. 计算机科学, 2018, 45(4): 83 -88 .
[5] 伍建辉,黄中祥,李武,吴健辉,彭鑫,张生. 城市道路建设时序决策的鲁棒优化[J]. 计算机科学, 2018, 45(4): 89 -93 .
[6] 史雯隽,武继刚,罗裕春. 针对移动云计算任务迁移的快速高效调度算法[J]. 计算机科学, 2018, 45(4): 94 -99 .
[7] 周燕萍,业巧林. 基于L1-范数距离的最小二乘对支持向量机[J]. 计算机科学, 2018, 45(4): 100 -105 .
[8] 刘博艺,唐湘滟,程杰仁. 基于多生长时期模板匹配的玉米螟识别方法[J]. 计算机科学, 2018, 45(4): 106 -111 .
[9] 耿海军,施新刚,王之梁,尹霞,尹少平. 基于有向无环图的互联网域内节能路由算法[J]. 计算机科学, 2018, 45(4): 112 -116 .
[10] 崔琼,李建华,王宏,南明莉. 基于节点修复的网络化指挥信息系统弹性分析模型[J]. 计算机科学, 2018, 45(4): 117 -121 .