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

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

Abstract

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

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.

Figures/Tables 8

References 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.

Metrics

Recommended 0

No Suggested Reading articles found!

问题规模		算法
问题规模	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

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

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 8

References 19

Related Articles 7

Metrics

Recommended 0

[1]	Liming PU,Shuxin LIU,Ruihao DING,Kai WANG. Heterogeneous executor scheduling algorithm for mimic cloud service [J]. Journal on Communications, 2020, 41(3): 17-24.
[2]	Da ZHANG,Jinong WANG,Hu JI,Hao JI,Yunfeng ZHAO. Research and application of micropower safety monitoring IoT system for mine [J]. Journal on Communications, 2020, 41(2): 44-57.
[3]	Shunfu JIN, Haixing WU, Tiantian HUO, Wenjuan ZHAO. On the performance optimization for the cloud architecture with sleep-mode and registration service [J]. Journal on Communications, 2019, 40(10): 127-136.
[4]	Bing LIN,Wenzhong GUO,Guolong CHEN. Scheduling strategy for science workflow with deadline constraint on multi-cloud [J]. Journal on Communications, 2018, 39(1): 56-69.
[5]	Zhou LI,Cong TANG,Jian-bin HU,Zhong CHEN. Vulnerabilities scoring approach for cloud SaaS [J]. Journal on Communications, 2016, 37(8): 157-166.
[6]	Xian-qing WANG,Chang-qin HUANG,UOXuan LUO,Rui-hua NIE,Yong TANG,Xiao-yong MEI. Determining substitutability of cloud services supported by semantically extended type theory [J]. Journal on Communications, 2016, 37(2): 20-31.
[7]	Zhen-dong WU,Dian-xi SHI,Bo DING,Huai-min WANG. Research in mobile cloud service framework based on contexts integrated situation [J]. Journal on Communications, 2011, 32(9A): 96-101.