叶赛英,徐弼军

(浙江科技学院 理学院，杭州 310023)



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

叶赛英,徐弼军

(浙江科技学院 理学院，杭州 310023)

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

关键词:排序；性能比；最小化误工工件数；机器带故障中断；近似算法

在经典的平行机排序问题中，通常要求多台机器性能完全相同，给定一个任意的等待加工的工件集，在满足特定的约束条件下，求解一个排序，使给定的某个目标函数最优。单台机下的误工工件数最小化的问题是有最优算法的，按照Moore 算法可以得到问题的最优解[1-2]。如果考虑两台平行机，由于意外或不可抗力导致其中一台机器发生故障中断，那么，在该机器上加工的工件只能转移到另外一台正常工作的机器上去加工[3]，在目标函数为最小化误工工件数要求下，该问题是NP(nondeterministic polynomial)困难的[4],文献[5-7]给出了不同情况下两台机带故障的近似算法。由于两台机问题是NP困难的，从而三台机问题也是NP困难的[8]，本研究讨论三台机带故障中断下，目标函数为误工工件数最小化的问题。

1问题的提出

现有三台相同的机器，将三台机器上正在加工的工件集设为：

I={J11,J12,…,J1n1;J21,J22,…,J2n2;J31,J32,…,J3n3}，

其中，Jij为中断前计划在机器Mi上加工的第j个工件，加工时间为pij，n1+n2+n3=n。设机器Mi在初始的0时刻发生故障中断，且中断的持续时间很长，在该机器上未完工的工件不可能等待机器恢复正常后再加工，不妨设中断时长D=∞，构造0—1变量