关于工件组的两机自由作业时间表问题

Scheduling Groups of Jobs in Two-machine Open Shop

讨论关于工件组的两机自由作业时间表的加工全长问题。无论是对于成组加工情形还是分组情形 ,该问题都可以被证明是 NP困难的。对于成组加工的情形 ,设计了一个性能比为 5/4的近似算法 ,该算法生成的时间表作为分组情形的解 ,性能比仍能保持为 5/4。此外 ,还讨论了如何最优地求解只有一个工件组的情形。

This paper is concerned with the makespan problem of scheduling groups of jobs in two machine open shop. The problem is known as NP hard no matter whether group sub lotting is admissible or not. We obtain an approximation algorithm which generates a GT schedule (in which no group is split) with the worst case performance ratio 5/4, even when the GT schedule is used as a solution to the group sub lotting case. Besides, we give a polynomial algorithm to solve the one group case to optimality.