通信学报 ›› 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

[1] 鲜永菊,董灿,张祖凡,吴东伟. LTE-A载波聚合下的载波切换分析[J]. 电信科学, 2009, 25(12): 46 -50 .
[2] 牛德华,马建峰,马卓,李辰楠,王蕾. 基于属性的安全增强云存储访问控制方案[J]. 通信学报, 2013, 34(Z1): 37 -284 .
[3] 刘 龙,宋琦军,赵太飞,元向辉. 基于运动矢量时-空特性的快速运动估计算法研究[J]. 通信学报, 2013, 34(1): 14 -127 .
[4] 王亚石,闵丽娟,周严. OSS/BSS一体化及其与ITSM的融合[J]. 电信科学, 2014, 30(6): 17 -23 .
[5] 葛仕明,程义民,曾 丹. 基于边缘方向投影的图像块修复方法[J]. 通信学报, 2008, 29(1): 5 -38 .
[6] 龚声蓉,郭 丽,韩 军,崔志明,刘 全. 基于全局运动补偿编码的AVS编码器设计[J]. 通信学报, 2007, 28(10): 16 -108 .
[7] 刘月平,姜秋喜,毕大平,崔 瑞. 网络雷达对Rician目标检测性能分析[J]. 通信学报, 2011, 32(10): 3 -26 .
[8] 干 楠,龚声蓉,王朝晖,刘纯平,刘 全. 基于张量投票的空域错误隐藏算法[J]. 通信学报, 2011, 32(10): 16 -134 .
[9] 郎非1,王保云1,2,邓志祥1. 基于分离信源信道码的相关信源在有噪广播信道下的可靠和安全传输[J]. 通信学报, 2013, 34(10): 3 -27 .
[10] 张红旗,韩崇砚. 支持分布式身份联盟的单点登录机制[J]. 通信学报, 2011, 32(11A): 22 -162 .