需要安装时间的两台多功能机排序问题的计算复杂性

The Computational Complexities of Two Multi-purpose Machines Scheduling Problem with Setup Times

提出需要安装时间的多功能机排序问题,一般情况下,这是NP-困难的;主要研究只有两台机器时一些特殊情况下的计算复杂性.根据加工集合为机器全集的工件组数的不同,分别给出多项式时间算法和分枝定界算法.对各工件组的工件数和加工时间都相等的情况,给出一个多项式时间的最优算法-奇偶算法,从而证明此问题是多项式时间可解的.

This paper proposes multi-purpose machine scheduling problems with setup times. Generally, they are NP-hard. We mainly study the computational com- plexities of several special cases on two machines. Polynomial algorithm and branch and bound algorithms are given for different number of job groups whose processing set con- tain both machines. For the case that all the job groups have the same number of jobs and equal processing times, we give a polynomial time optimal algorithm-parity algorithm, and thereby prove that the problem is polynomial.