Algorithm for the cloud service workflow scheduling with setup time and deadline constraints

Hong SHEN; Xiao-ping LI

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

您当前的位置：

首页 >

文章列表页 >

Algorithm for the cloud service workflow scheduling with setup time and deadline constraints

Academic communication | 更新时间：2024-06-05

- Algorithm for the cloud service workflow scheduling with setup time and deadline constraints
- Journal on Communications Vol. 36, Issue 6, Pages: 183-192(2015)
- 作者机构：
  
  1. 东南大学计算机科学与工程学院，江苏南京210096
  2. 南京审计学院金审学院，江苏南京210029
- 作者简介：
- 基金信息：
  
  The National Natural Science Foundation of China(61272377);The Research Fund for the Doctoral Program of Higher Education of China(20120092110027)
- DOI：10.11959/j.issn.1000-436x.2015125
  CLC： TP393
- Online First：2015-06，
  
  Published：25 June 2015
- 稿件说明：
移动端阅览
Hong SHEN, Xiao-ping LI. Algorithm for the cloud service workflow scheduling with setup time and deadline constraints[J]. Journal on Communications, 2015, 36(6): 183-192.
DOI：

Hong SHEN, Xiao-ping LI. Algorithm for the cloud service workflow scheduling with setup time and deadline constraints[J]. Journal on Communications, 2015, 36(6): 183-192. DOI： 10.11959/j.issn.1000-436x.2015125.

摘要

带准备时间和截止期约束的云服务工作流费用优化是一个新的云计算资源优化分配问题。分析该NP-hard问题特征，建立相应的整数规划数学模型。构建有效的变量取值概率模型和更新机制，提出高质量初始群体的启发式生成方法；提出混合的分布估计算法（HEDA），引入个体向全局最优解学习的策略，提高算法的全局搜索和局部优化能力。模拟实验结果表明此提出的方法在合理的CPU时间内可有效减少工作流费用。

Abstract

Cost minimization with deadline constraints and setup time is a new resource allocation optimization problem in cloud computing.An integer programming model is constructed for this NP-hard problem.A novel probability model and updating mechanism is suggested for sampling the solution space.A heuristic method is investigated for generating good initial population.A hybrid estimation of distribution algorithm (HEDA) is proposed for the considered problem.The global best solution is adopted to balance the diversification and intensification of HEDA.Experimental results show that the proposed method is effective to optimize the workflow running cost within reasonable CPU time.

关键词

Keywords

references

林闯 , 苏文博 , 孟坤等 . 云计算安全:架构、机制与模型评价 [J ] . 计算机学报 , 2013 , 36 ( 9 ): 1765 - 1784 .

LIN C , SU WB , MENG K , et al . Cloud computing security:architecture,mechanism and modeling [J ] . Chinese Journal of Computers , 2013 , 36 ( 9 ): 1765 - 1784 .

CHARD K , BUBENDORFER K . High performance resource allocation strategies forcomputational economies [J ] . IEEE Transactions on Parallel and Distributed Systems , 2013 , 24 ( 1 ): 72 - 84 .

DE P , DUNNE E , GHOSH J , et al . Complexity of the discrete time-cost tradeoff problem for project networks [J ] . Operations Research , 1997 , 45 ( 2 ): 302 - 306 .

DE P , DUNNE E , GHOSH J , et al . The discrete time-cost tradeoff problem revisited [J ] . European Journal of Operational Research , 1995 , 81 ( 2 ): 225 - 238 .

YU J , BUYYA R , THAM C . Cost-based scheduling of workflow applications on utility grids [A ] . Proceedings of 1st International Conference on e-Science and Grid Computing [C ] . 2005 . 140 - 147 .

YUAN Y C , LI X P , WANG Q , et al . Deadline division-based heuristic for cost optimization in workflow scheduling [J ] . Information Sciences , 2009 , 179 ( 15 ): 2562 - 2575 .

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

YUAN YC , LI XP , WANG Q . Bottom level based heuristic for workflow scheduling in grids [J ] . Chinese Journal of Computers , 2008 , 31 ( 2 ): 282 - 290 .

苑迎春 , 李小平 , 王茜 . 基于串归约的网格工作流费用优化方法 [J ] . 计算机研究与发展 , 2008 , 45 ( 2 ): 246 - 253 .

YUAN YC,LIXP , WANG Q . Cost optimization heuristic for grid workflows scheduling based on serial reduction [J ] . Chinese Journal of Computer Research and Development , 2008 , 45 ( 2 ): 246 - 253 .

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

张晓东 , 李小平 , 王茜等 . 服务工作流的混合粒子群调度算法 [J ] . 通信学报 , 2008 , 29 ( 8 ): 87 - 93 .

ZHANG XD , LI XP , WANG Q , et al . Hybrid particle swarm optimization algorithm for cost minimization in service-workflows with due dates [J ] . Journal on Communications , 2008 , 29 ( 8 ): 87 - 93 .

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,and Cybernetics,Part C:Applications and Reviews , 2009 , 39 ( 1 ): 29 - 43 .

YU J , BUYYA R . Scheduling scientific workflow applications with deadline and budget constraints using genetic algorithms [J ] . Scientific Programming , 2006 , 14 ( 3 ): 217 - 230 .

CAI Z C , LI X P , GUPTA J N D . Critical path-based iterative heuristic for workflow scheduling in utility and cloud computing [A ] . Proceedings of 11th International Conference on Service-Oriented Computing [C ] . 2013 . 207 - 221 .

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

VAN DEN BOSSCHE R , VANMECHELEN K , BROECKHOVE J . Cost optimal scheduling in hybrid IAAS clouds for deadline constrained workloads [A ] . Proceedings of IEEE 3rd International Conference on Cloud Computing [C ] . 2010 . 228 - 235 .

LARRAANAGA P , LOZANO J A . Estimation of Distribution Algorithms:a New Tool for Evolutionary Computation [M ] . Boston : Kluwer PressPress , 2002 .

WANG L , FANG C . An effective estimation of distribution algorithm for the multi-mode resource-constrained project scheduling problem [J ] . Computers & Operations Research , 2012 , 39 ( 2 ): 449 - 460 .

DEMEULEMEESTER E , VANHOUCKE M , HERROELEN W . Rangen:A random network generator for activity-on-the-node networks [J ] . Journal of Scheduling , 2003 , 6 ( 1 ): 17 - 38 .

AKKAN C , DREXL A , KIMMS A . Network decomposition based benchmark results for the discrete time–cost tradeoff problem [J ] . European Journal of Operational Research , 2005 , 165 ( 2 ): 339 - 358 .

Views

956

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Privacy-preserving indoor localization scheme based on Wi-Fi fingerprint with outsourced computing

Research and application of micropower safety monitoring IoT system for mine

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

Vulnerabilities scoring approach for cloud SaaS

Determining substitutability of cloud services supported by semantically extended type theory

Related Author

Sirui ZHANG

Qiuxia ZHAO

Xiaokun ZHENG

Jin CAO

Yinghui ZHANG

Yunfeng ZHAO

Hao JI

Hu JI

Related Institution

School of Cyberspace Security, Xi’an University of Posts ＆Telecommunications

The College of Computer, Qinghai Normal University

School of Cyber Engineering, Xidian University

BGRIMM Technology Group

Beijing General Research Institute of Mining and Metallurgy Technology

AI问答

⁰