基于逆向分层的网格工作流调度算法

有向无环图DAG(Directed Acrylic Graph)描述的工作流时间费用优化问题是计算网格下一个基本的且难以求解的问题.通过分析DAG图中活动的并行和同步完成特征,采取由后向前方法将活动逆向分层(BottomLevel,BL),将工作流截止期转化为层截止时间,提出截止期约束的逆向分层费用优化算法DBL(Deadline BottomLevel).算法中同层活动的开始时间不同于DTL(Deadline Top Level)算法中设置相同的策略,而是分别由其前驱活动确定,时间浮差被平均分配到各分层,以尽量增大活动的费用优化区间.通过大量模拟实验将DBL和MCP(mini mumCritical Path)、DTL两算法比较,结果表明DTL将MCP的平均费用降低15.62%,而DBL将MCP的平均费用降低24.74%.最后讨论了截止期和分组参数对算法性能的影响.

Bottom Level Based Heuristic for Workflow Scheduling in Grids

Efficient scheduling of workflow applications represented by DAG(Directed Acyclic Graph)with the objective of time-cost optimization is fundamental and intractable in computational Grid.By analyzing parallel and synchronization properties of DAG,all tasks are divided into BL(Bottom Level)groups using a backward method.The workflow deadline can be transformed into the time intervals of all tasks based on BL groups,a bottom leveling based algorithm called DBL(Deadline Bottom Level)is proposed.In DBL,the starting time of a task in each group is determined by the maximum finish time among those of its predecessors rather than the finish time of its parent group,which is adopted by DTL(Deadline Top Level).The total time float is allocated equally to each group,which manage to enlarge the cost optimization intervals of all tasks.By comparing DBL with DTL and MCP(Minimum Critical Path),which is a cost optimization method based on the minimum critical path,experimental results show that DBL can save 24.74% average cost of MCP and DTL can only do 15.62%.In other words,DBL outperforms both DTL and MCP.As well,parameters affecting algorithms(such as leveling parameters,deadlines)are analyzed by experiments.