最小化时间表长的平行机调度近似算法研究

APPROXIMATED ALGORITHM FOR IDENTICAL MACHINE SCHEDULING WITH MINIMIZED MAKESPANS

讨论机器具有固定周期维护t,目标函数为最小化时间表长的m台平行机调度问题.这是一个NP-难的问题.关于该问题主要分析了当维护时间t≤T/3时,利用经典的装箱算法FFD我们可以得到关于该问题的一个近似算法FFPTD.该算法的最坏误差界为2,最后以实例说明2为该算法的紧界.

Identical machine scheduling with periodic maintenance was considered.The objective was to minimize make-spans.It was a NP-hard problem.An approximated algorithm was proposed to solve this problem with the bins packing algorithm FFD.For the case t≤T/3,the worst-case bound was 2.An example was given to illustrate that 2 was a tight bound.