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

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

摘要/Abstract

摘要：

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

沈虹,李小平. 带准备时间和截止期约束的云服务工作流调度算法[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.

图/表 8

图1

图2

图3

图4

图5

图6

图7

表1

参考文献 19

[1]	林闯, 苏文博, 孟坤等 . 云计算安全:架构、机制与模型评价[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.
[2]	CHARD K , BUBENDORFER K . High performance resource allocation strategies forcomputational economies[J]. IEEE Transactions on Parallel and Distributed Systems, 2013,24(1): 72-84.
[3]	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.
[4]	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.
[5]	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.
[6]	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.
[7]	苑迎春, 李小平, 王茜 . 基于逆向分层的网格工作流调度算法[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.
[8]	苑迎春, 李小平, 王茜 . 基于串归约的网格工作流费用优化方法[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.
[9]	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.
[10]	张晓东, 李小平, 王茜等 . 服务工作流的混合粒子群调度算法[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.
[11]	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.
[12]	YU J , BUYYA R . Scheduling scientific workflow applications with deadline and budget constraints using genetic algorithms[J]. Scientific Programming, 2006,14(3): 217-230.
[13]	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.
[14]	ABRISHAMI S , NAGHIBZADEH M , EPEMA D . Deadline constrained workflow scheduling algorithms for IAAS clouds[J]. Future Generation Computer Systems, 2013,29(1): 158-169.
[15]	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.
[16]	LARRAANAGA P , LOZANO J A . Estimation of Distribution Algorithms:a New Tool for Evolutionary Computation[M]. Boston: Kluwer PressPress, 2002.
[17]	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.
[18]	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.
[19]	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.

问题规模		算法
问题规模	PSO	HEDA-1	HEDA-2
30	0.02 s	0.10 s	0.11 s
60	0.18 s	0.32 s	0.36 s
90	0.45 s	0.73 s	0.82 s
120	0.75 s	1.39 s	1.55 s
150	1.71 s	2.28 s	2.56 s
180	2.76 s	3.57 s	3.87 s
210	4.06 s	5.18 s	5.81 s
240	5.86 s	7.32 s	7.88 s
270	8.17 s	10.02 s	10.80 s
300	11.21 s	14.67 s	15.44 s