机器带故障的三台机排序问题的两个近似算法

Two approximation algorithms for three parallel machines scheduling with machine disruptions

机器带故障的m台机的目标函数为最小化误工工件数的排序问题,在m≥2时是NP(nondeterministic polynomial)困难的问题,对m=3,当工件转移时间t=0和t≠0两种情况,提出了P3丨D=∞,t1=t2=0丨n-∑u′ij和P3丨D=∞,t1≠t2丨n-∑u′ij的近似算法,以及对应的渐进性能比,且证明了其界是紧的。

We discuss the problem of m parallel machines scheduling with disruptions with the objective of minimizing the sum of unit penalties.If m≥2,the problem is NP-hard.When m=3and transfer time is t=0and t≠0,two approximation algorithms are proposed for the problems of P3 D = ∞,t1=t2 =0n-∑u′ijand P3 D = ∞,t1 ≠t2n-∑u′ijrespectively.And the paper proves that the upper bound is tight respectively.