Scheduling strategy for science workflow with deadline constraint on multi-cloud

Bing LIN; Wenzhong GUO; Guolong CHEN

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

您当前的位置：

首页 >

文章列表页 >

Scheduling strategy for science workflow with deadline constraint on multi-cloud

Papers | 更新时间：2024-06-05

- Scheduling strategy for science workflow with deadline constraint on multi-cloud
- Journal on Communications Vol. 39, Issue 1, Pages: 56-69(2018)
- 作者机构：
  
  1. 福建师范大学物理与能源学院，福建福州 350117
  2. 福建省网络计算与智能信息处理重点实验室（福州大学），福建福州 350116
  3. 空间数据挖掘与信息共享教育部重点实验室，福建福州 350003
  4. 福州大学数学与计算机科学学院，福建福州 350116
- 作者简介：
- 基金信息：
  
  The National Key R＆D Program of China(2017YFB1002000);The National Natural Science Foundation of China(61672159);The Key Project of Chinese Ministry of Education(2009J1007);The Technology Innovation Platform Project of Fujian Province(2014H2005);The Foundation of The Fujian Collaborative Innovation Center for Big Data Application in Governments
- DOI：10.11959/j.issn.1000-436x.2018006
  CLC： TP338
- Online First：2018-01，
  
  Published：25 January 2018
- 稿件说明：
移动端阅览
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：

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 .

Views

1502

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Cryptographic service optimization scheduling algorithm for collaborative jobs in cloud environment

M-RSF: a multilevel feedback queue task scheduling mechanism for Unikernel

Scheduling framework based on reinforcement learning in online-offline colocated cloud environment

Time-based and privacy protection revocable and traceable data sharing scheme in cloud computing

Identity-based provable data possession scheme for multi-source IoT terminal data in public cloud

Related Author

CAO Xiaogang

LI Fenghua

GENG Kui

LI Zifu

KOU Wenlong

DONG Bonan

YANG Qiusong

LI Mingshu

Related Institution

Institute of Information Engineering, Chinese Academy of Sciences

School of Cyber Security, University of Chinese Academy of Sciences

Key Laboratory of Cyberspace Security Defense

University of Chinese Academy of Sciences

National Engineering Research Center for Fundamental Software, Institute of Software Chinese Academy of Sciences

AI问答

⁰