带准备时间和截止期约束的云服务工作流调度算法

沈虹; 李小平

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

您当前的位置：

首页 >

文章列表页 >

带准备时间和截止期约束的云服务工作流调度算法

学术通信 | 更新时间：2024-06-05

- 带准备时间和截止期约束的云服务工作流调度算法
- Algorithm for the cloud service workflow scheduling with setup time and deadline constraints
- 通信学报 2015年36卷第6期页码：183-192
- 作者机构：
  
  1. 东南大学计算机科学与工程学院，江苏南京210096
  2. 南京审计学院金审学院，江苏南京210029
- 作者简介：
  
  [ "沈虹（1981-），女，江苏启东人，东南大学博士生，南京审计学院讲师，主要研究方向为项目调度、服务计算。" ]
  [ "李小平（1970-），男，重庆人，博士，东南大学教授、博士生导师，主要研究方向为机器调度、项目调度、服务计算。" ]
- 基金信息：
  
  国家自然科学基金资助项目(61272377);教育部高等学校博士学科点专项科研基金资助项目(20120092110027)
- DOI：10.11959/j.issn.1000-436x.2015125
  中图分类号： TP393
- 网络出版日期：2015-06，
  
  纸质出版日期：2015-06-25
- 稿件说明：
移动端阅览
沈虹, 李小平. 带准备时间和截止期约束的云服务工作流调度算法[J]. 通信学报, 2015,36(6):183-192.

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.
沈虹, 李小平. 带准备时间和截止期约束的云服务工作流调度算法[J]. 通信学报, 2015,36(6):183-192. DOI： 10.11959/j.issn.1000-436x.2015125.

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 .

浏览量

717

下载量

CSCD

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

提交

工具集

关联资源

基于Wi-Fi指纹且计算外包的室内定位隐私保护方案

矿山微功耗安全监测物联网系统的研究与应用

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

面向SaaS云平台的安全漏洞评分方法研究

基于语义扩展类型论的云服务替换性判定研究