通信学报 ›› 2015, Vol. 36 ›› Issue (6): 183-192.doi: 10.11959/j.issn.1000-436x.2015125

• 学术通信 • 上一篇    下一篇

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

沈虹,李小平   

  1. 1 东南大学 计算机科学与工程学院,江苏 南京210096
    2 南京审计学院 金审学院,江苏 南京210029
  • 出版日期:2015-06-25 发布日期:2017-05-11
  • 基金资助:
    国家自然科学基金资助项目;教育部高等学校博士学科点专项科研基金资助项目

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

Hong SHEN,Xiao-ping LI   

  1. 1 School of Computer Science & Engineering,Southeast University,Nanjing 210096,China
    2 Jinshen College,Nanjing Audit University,Nanjing 210029,China
  • Online:2015-06-25 Published:2017-05-11
  • Supported by:
    The National Natural Science Foundation of China;The Research Fund for the Doctoral Program of Higher Education of China

摘要:

带准备时间和截止期约束的云服务工作流费用优化是一个新的云计算资源优化分配问题。分析该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.

Key words: cloud service, workflow scheduling, estimation of distribution algorithm