多云环境下带截止日期约束的科学工作流调度策略

林兵; 郭文忠; 陈国龙

doi:10.11959/j.issn.1000-436x.2018006

您当前的位置：

首页 >

文章列表页 >

多云环境下带截止日期约束的科学工作流调度策略

学术论文 | 更新时间：2024-06-05

- 多云环境下带截止日期约束的科学工作流调度策略
- Scheduling strategy for science workflow with deadline constraint on multi-cloud
- 通信学报 2018年39卷第1期页码：56-69
- 作者机构：
  
  1. 福建师范大学物理与能源学院，福建福州 350117
  2. 福建省网络计算与智能信息处理重点实验室（福州大学），福建福州 350116
  3. 空间数据挖掘与信息共享教育部重点实验室，福建福州 350003
  4. 福州大学数学与计算机科学学院，福建福州 350116
- 作者简介：
  
  [ "林兵（1986-），男，福建福清人，博士，福建师范大学讲师，主要研究方向为云计算技术、计算智能及其应用。" ]
  [ "郭文忠（1979-），男，福建泉港人，博士，福州大学教授、博士生导师，主要研究方向为计算智能及其应用。" ]
  [ "陈国龙（1965-），男，福建莆田人，博士，福州大学教授、博士生导师，主要研究方向为人工智能、网络安全。" ]
- 基金信息：
  
  国家重点研发计划基金资助项目(2017YFB1002000);国家自然科学基金资助项目(61672159);福建省科技创新平台计划基金资助项目(2009J1007);福建省科技创新平台计划基金资助项目(2014H2005);海峡政务大数据应用省级协同创新中心基金资助项目
- DOI：10.11959/j.issn.1000-436x.2018006
  中图分类号： TP338
- 网络出版日期：2018-01，
  
  纸质出版日期：2018-01-25
- 稿件说明：
移动端阅览
林兵, 郭文忠, 陈国龙. 多云环境下带截止日期约束的科学工作流调度策略[J]. 通信学报, 2018,39(1):56-69.

Bing LIN, Wenzhong GUO, Guolong CHEN. Scheduling strategy for science workflow with deadline constraint on multi-cloud[J]. Journal on communications, 2018, 39(1): 56-69.
林兵, 郭文忠, 陈国龙. 多云环境下带截止日期约束的科学工作流调度策略[J]. 通信学报, 2018,39(1):56-69. DOI： 10.11959/j.issn.1000-436x.2018006.

Bing LIN, Wenzhong GUO, Guolong CHEN. Scheduling strategy for science workflow with deadline constraint on multi-cloud[J]. Journal on communications, 2018, 39(1): 56-69. DOI： 10.11959/j.issn.1000-436x.2018006.

摘要

针对多云环境下带截止日期约束的科学工作流调度问题，提出一种基于遗传算法操作的自适应离散粒子群优化算法（ADPSOGA），目的是在尽可能满足工作流截止日期前提下，减少其执行代价。该方法考虑多云之间的通信代价、虚拟机的启动和关闭时间以及多云之间不同的带宽通信波动；为了避免传统粒子群优化算法（PSO

particle swarm optimization）存在的过早收敛问题，引入遗传算法的随机两点交叉操作和随机单点变异操作，有效提高种群进化过程中的多样性；在充分考虑数据通信代价和任务计算代价的情况下，设计一种基于工作流截止日期约束的代价驱动调度策略。实验结果表明，ADPSOGA在波动因素存在情况下，对工作流截止日期满足和执行代价控制方面具有良好的性能表现。

Abstract

In view of the deadline-constrained scientific workflow scheduling on multi-cloud

an adaptive discrete particle swarm optimization with genetic algorithm (ADPSOGA) was proposed

which aimed to minimize the execution cost of workflow while meeting its deadline constrains.Firstly

the data transfer cost

the shutdown and boot time of virtual machines

and the bandwidth fluctuations among different cloud providers were considered by this method.Secondly

in order to avoid the premature convergence of traditional particle swarm optimization (PSO)

the randomly two-point crossover operator and randomly one-point mutation operator of the genetic algorithm (GA) was introduced.It could effectively improve the diversity of the population in the process of evolution.Finally

a cost-driven strategy for the deadline-constrained workflow was designed.It both considered the data transfer cost and the computing cost.Experimental results show that the ADPSOGA has better performance in terms of deadline and cost reducing in the fluctuant environment.

关键词

Keywords

references

RODRIGUEZ M A , BUYYA R . Deadline based resource provisioning and scheduling algorithm for scientific workflows on clouds [J ] . IEEE Transactions on Cloud Computing , 2014 , 2 ( 2 ): 222 - 235 .

FARD H M , PRODAN R , FAHRINGER T . A truthful dynamic workflow scheduling mechanism for commercial multicloud environments [J ] . IEEE Transactions on Parallel ＆ Distributed Systems , 2013 , 24 ( 6 ): 1203 - 1212 .

MALAWSKI M , JUVE G , DEELMAN E , et al . Cost-and deadline-constrained provisioning for scientific workflow ensembles in IaaS clouds [C ] // International Conference for High Performance Computing,Networking,Storage and Analysis . 2012 : 1 - 11 .

MASDARI M , SALEHI F , JALALI M , et al . A survey of PSO-based scheduling algorithms in cloud computing [J ] . Journal of Network ＆Systems Management , 2017 , 25 ( 1 ): 1 - 37 .

WU Z , NI Z , GU L , et al . A revised discrete particle swarm optimization for cloud workflow scheduling [C ] // International Conference on Computational Intelligence and Security , 2010 : 184 - 188 .

ABRISHAMI S , NAGHIBZADEH M , EPEMA D H J . Deadline-constrained workflow scheduling algorithms for infrastructure as a service clouds [J ] . Future Generation Computer Systems , 2013 , 29 ( 1 ): 158 - 169 .

MATTOSO M , DIAS J,OCAÑA K A C S , et al . Dynamic steering of HPC scientific workflows:a survey [J ] . Future Generation Computer Systems , 2015 , 46 ( C ): 100 - 113 .

ZENG L , VEERAVALLI B , ZOMAYA A Y . An integrated task computation and data management scheduling strategy for workflow applications in cloud environments [J ] . Journal of Network ＆ Computer Applications , 2015 , 50 ( C ): 39 - 48 .

CHEN W N , ZHANG J . An ant colony optimization approach to a Grid workflow scheduling problem with various QoS requirements [J ] . IEEE Transactions on Systems Man ＆ Cybernetics Part C , 2008 , 39 ( 1 ): 29 - 43 .

CAO H , JIN H , WU X , et al . DAGMap:efficient and dependable scheduling of DAG workflow job in grid [J ] . The Journal of Supercomputing , 2010 , 51 ( 2 ): 201 - 223 .

HIGASHINO W A , CAPRETZ M A M , TOLEDO M B F D , et al . A hybrid particle swarm optimization-genetic algorithm applied to grid scheduling [J ] . International Journal of Grid ＆ Utility Computing , 2016 , 7 ( 2 ): 113 - 129 .

苑迎春 , 李小平 , 王茜 , 等 . 基于逆向分层的网格工作流调度算法 [J ] . 计算机学报 , 2008 , 31 ( 2 ): 282 - 290 .

YUAN Y C , LI X P , WANG Q , et al . Bottom level based heuristic for workflow scheduling in grids [J ] . Chinese Journal of Computers , 2008 , 31 ( 2 ): 282 - 290 .

ABRISHAMI S , NAGHIBZADEH M , EPEMA D H J . Cost-driven scheduling of grid workflows using partial critical paths [J ] . IEEE Transactions on Parallel ＆ Distributed Systems , 2012 , 23 ( 8 ): 1400 - 1414 .

KHAJEMOHAMMADI H , FANIAN A , GULLIVER T A . Fast workflow scheduling for grid computing based on a multi-objective genetic algorithm [C ] // Communications,Computers and Signal Processing . 2013 : 96 - 101 .

沈虹 , 李小平 . 带准备时间和截止期约束的云服务工作流调度算法 [J ] . 通信学报 , 2015 , 36 ( 6 ): 183 - 192 .

SHEN H , LI X P . Algorithm for the cloud service workflow scheduling with setup time and deadline constraints [J ] . Journal on Communica-tions , 2015 , 36 ( 6 ): 183 - 192 .

肖鹏 , 胡志刚 , 屈喜龙 . 面向数据密集型工作流的能耗感知调度策略 [J ] . 通信学报 , 2015 , 36 ( 1 ): 149 - 158 .

XIAO P , HU Z G , QU X L . Energy-aware scheduling policy for da-ta-intensive workflow [J ] . Journal on Communications , 2015 , 36 ( 1 ): 149 - 158 .

MAO M , HUMPHREY M . Auto-scaling to minimize cost and meet application deadlines in cloud workflows [C ] // High Performance Computing,Networking,Storage and Analysis . 2011 : 1 - 12 .

PANDEY S , WU L , GURU S M , et al . A particle swarm optimization-based heuristic for scheduling workflow applications in cloud computing environments [C ] // IEEE International Conference on Advanced Information Networking and Applications . 2010 : 400 - 407 .

KEAHEY K , TSUGAWA M , MATSUNAGA A , et al . Sky computing [J ] . IEEE Internet Computing , 2009 , 13 ( 5 ): 43 - 51 .

LIN B , GUO W , XIONG N , et al . A pretreatment workflow scheduling approach for big data applications in multicloud environments [J ] . IEEE Transactions on Network ＆ Service Management , 2016 , 13 ( 3 ): 581 - 594 .

WOO S S , MIRKOVIC J . Optimal application allocation on multiple public clouds [J ] . Computer Networks , 2014 , 68 ( 11 ): 138 - 148 .

KENNEDY J , EBERHART R . Particle swarm optimization [C ] // IEEE International Conference on Neural Networks . 2002 : 1942 - 1948 .

SU J S , GUO W Z , YU C L , et al . Fault-tolerance clustering algorithm with load-balance aware in wireless sensor network [J ] . Chinese Journal of Computers , 2014 , 37 ( 2 ): 445 - 456 .

SHI Y , EBERHART R . A modified particle swarm optimizer [C ] // IEEE World Congress on Computational Intelligence . 1998 : 69 - 73 .

BHARATHI S , CHERVENAK A , DEELMAN E , et al . Characterization of scientific workflows [C ] // Workflows in Support of Large-Scale Science . 2008 : 1 - 10 .

TOPCUOGLU H , HARIRI S , WU M Y . Performance-effective and low-complexity task scheduling for heterogeneous computing [J ] . IEEE Transactions on Parallel ＆ Distributed Systems , 2002 , 13 ( 3 ): 260 - 274 .

浏览量

1242

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

云环境下协同作业的密码服务优化调度算法

M-RSF：面向Unikernel的一种多级反馈队列任务调度机制

基于强化学习的在线离线混部云环境下的调度框架

云计算中基于时间和隐私保护的可撤销可追踪的数据共享方案

公有云中身份基多源IoT终端数据PDP方案