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

Improving Bottom Level Based Heuristic for Workflow Scheduling in Grids

通过对逆向分层DBL（Deadline Bottom level BL）算法的分析与研究,发现当截止期（δn）大于BLmin的情况下,其对逆向分层浮差（Tws）分配上有不足之处。为此该文提出了一种改进算法DBL-LC（DeadlineBottomlevel-lowercost）。改进算法使得对逆向分层浮差（Tws）的使用更加充分,减少了流时间碎片。实验证明,在相同的截止期下DBL-LC执行费用比DBL算法平均降低了14.52%。

By analyzing DBL （Deadline Bottom Level） algorithm,there is unreasonable problem in allocating Tws when δnBLmin. Regarding this problem,a improving algorithm called DBL-LC （deadline bottom level-lower cost） algorithm is proposed. Improving algorithm makes good use of Tws and reduces shattering time of workflow. Experimental results show that at same workflow deadline,comparing DBL algorithm,DBL-LC algorithm averagely save 14.52% cost.