关于延误时间的平行机排序问题的复杂性

The Complexity of the Parallel Machine Scheduling about Tardiness

研究了当目标函数和延误时间有关时 ,带两个服务器的 3台平行机排序问题的复杂性。首先证明了 P3 ,S2 /si=1 /Lmax是强 NP-难的 ,然后证明了另两个问题 P3 ,S2 /pi=1 /Lmax和 P3 ,S2 /si=1 ,di=d/Lmax都是

In this paper, the complexity of the parallel machine scheduling with two servers was studied. It is proved that the P3,S2/s_i=1/L_ max problem is strong NP-hard. Then it is also proved that the other two problems P3,S2/p_i=1/L_ max and P3,S2/s_i=1,d_i=d/L_ max are NP-hard.