异时排序问题的算法复杂性

Complexity of Non-Simultaneously Scheduling Problem

我们将限制某些工件不能同时处理的平行机排序问题称为异时排序问题．本文我们讨论工件加工时间相同、目标为总完工时间最小的异时排序问题．我们证明了当机器台数为2时，该问题等价于图上的最大匹配问题，因此存在组合强多项式时间算法；但量当机器台数为3或者多于3时，该问题是强NP困难的．

In this paper, we consider a multiprocessor scheduling model to minimize the makespan whichrequires some jobs can not be processed simultaneously We only consider the equal execution timecase. If there are only two machines, we show that the scheduling problem is equivalent to maximummatching problem on a graph, hence can be solved in combinatorial strongly polynomial algorithm.But if there are three or more machines, we show the the scheduling problem is NP-hard in thestrong sense.