论文部分内容阅读
讨论机器带故障中断的两台平行机排序问题，目标为极小化误工工件数，在转移时间t=0时的排序问题是问题P2｜D=∞，t=0｜∑u′ij，该文给出了相应的算法，并利用该算法，考虑了当工件转移时间t〉0时的NP难的排序问题P2｜D=∞，t≠0｜∑u′ij。该文使用对前一问题的最优序π^＊当中的工件相交换，使得增加误工工件数尽量少的方法，提出了一个差界为1的多项式时间的近似算法，并给出了证明及算法的计算复杂性。