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

机器带故障的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的近似算法,以及对应的渐进性能比,且证明了其界是紧的。