m台机器上流水作业时间表问题的复杂性及一种新的启发式算法(英)

研究流水作业时间表问题,在具有延迟时间的条件下证明该问题是强NP-困难的。给出一种新的启发式算法,并证明该算法的最坏性能比是(m+1)/2,且上界是紧的。