Segment Level Based Heuristic for Workflow Cost-time Optimization in Grids
-
摘要: 针对有向无环图(directed acrylic graph,DAG)表示的截止期约束下的网格工作流费用优化问题,提出启发式分段(segment level,SL)费用优化算法.通过分析DAG图中活动的并行和同步特征,算法对活动进行分段,时间浮差按比例分配到各段,段内的费用优化采用动态规划的求解策略实现.通过将工作流截止期转换为段截止时间,扩大了活动的费用优化区间,通过大量模拟实验将SL算法和MCP (minimum critical path)、DTL (deadline top level)、DBL (deadline bottom level)算法比较,证明了SL算法的有效性.Abstract: Workflow scheduling with the objective of time-cost optimization is a fundamental problem in grids and generally the problem is NP-hard.In this paper,a novel heuristics called SL (Segment Level) for workflows represented by DAG (Directed Acyclic Graph) is proposed.Considering the parallel and synchronization properties,the workflow application is divided into segments,and the workflow deadline is transformed into the time intervals and appointed to different segments.The floating time is prorated to each segment to enlarge cost-time duration,and a dynamic programming method is implemented to optimize cost for each segment.By comparing SL with MCP (Minimum Critical Path),DTL (Deadline Top Level),DBL (Deadline Bottom Level),the heuristics' efficiency is verified by experimental results.
-
Keywords:
- grid workflow /
- directed acrylic graph /
- heuristics /
- segment level
-
-
[1] FOSTER I,KESSELMAN C.The grid:blueprint for a new computing infrastructure[M].2nd ed.San Francisco:MorganKaufmann Publishers,2003:5-7.
[2] FOSTER I,KESSELMAN C.Grid service for distributed system integration[J].IEEE Computer,2002,35(6):37-46.
[3] ZENG L Z,BENATALLAH B,NGU A H H,et al.QoS-aware middleware for Web services composition[J].IEEE Trans onSoftware Engineering,2004,30(5):311-327.
[4] BLYTHE J,JAIN S,DEELMAN E,et al.Task scheduling strategies for workflow-based applications in grids[C]∥Proceedingsof the IEEE International Symposium on Cluster Computing and Grid.Cardiff,Wales,UK:IEEE Computer Society,2005(2):759-767.
[5] GERASOULIS A,YANG T.A comparison of clustering heuristics for scheduling directed acyclic graphs of multiprocessors[J].Journal of Parallel and Distributed Computing,1992,16(4):276-291.
[6] KWOK Y K,AMAD I.Dynamic critical-path scheduling:an effective technique for allocating task graphs to multiprocessors[J].IEEE Transactions on Parallel and Distributed Systems,1996,7(5):506-521.
[7] DEMEULEMEESTER E,HERROELEN W,ELMAGHRABY S E.Optimal procedures for the discrete time/cost trade-offproblem in project networks[J].European Journal of Operational Research,1996,88(1):50-68.
[8] 林剑柠,吴慧中.基于遗传算法的网格资源调度算法[J].计算机研究与发展,2004,41(12):2190-2194.LIN Jian-ning,WU Hui-zhong.Scheduling in grid computing environment based on genetic algorithm[J].Journal of ComputerResearch and Development,2004,41(12):2190-2194.(in Chinese) [9] JIA Yu,BUYYA R.Scheduling scientific workflow applications with deadline and budget constraints using genetic algorithms[J].Scientific Programming,2006,14(3/4):217-230.
[10] 金海,陈汉华,吕志鹏,等.CGSP作业管理其合成服务的QoS优化模型及求解[J].计算机学报,2005,28(4):578-588.JIN Hai,CHEN Han-hua,LZhi-peng,et al.QoS optimizing model and solving for composite service in CGSP job manager[J].Chinese Journal of Computers,2005,28(4):578-588.(in Chinese) [11] 于明远,朱艺华,梁荣华.基于混合微粒群算法的网格服务工作流调度[J].华中科技大学学报:自然科学版,2008,36(4):45-47.YU Ming-yuan,ZHU Yi-hua,LIANG Rong-hua.A grid service-workflow schedule using hybrid particle swarm[J].Journal ofHuazhong University of Science and Technology:Natural Science Edition,2008,36(4):45-47.(in Chinese) [12] JIA Yu,BUYYA R,CHEN Khong-tham.Cost-based scheduling of workflow applications on utility grids[C]∥The 1st IEEEInt'l Conf on e-Science and Grid Computing.Melbourne,Australia:IEEE Press,2005:140-147.
[13] 苑迎春,李小平,王茜,等.基于逆向分层的网格工作流调度算法[J].计算机学报,2008,31(2):282-290.YUAN Ying-chun,LI Xiao-ping,WANG Qian,et al.Bottom level based heuristic for workflow scheduling in grids[J].Chinese Journal of Computers,2008,31(2):282-290.(in Chinese)
计量
- 文章访问数: 7
- HTML全文浏览量: 1
- PDF下载量: 4
下载:
