On the Inapproximability of Two-machine Open Shop Scheduling with Exact Delays
摘要
In two-machine open shop scheduling with exact delays, each job consists of two operations with an arbitrary process order, provided that the second operation must start exactly a certain time after the first operation is completed. It is known that the problem of minimizing makespan cannot be approximated in polynomial time to within a factor of \(2-\epsilon \) for any \(\epsilon >0\) , unless \(P=NP\) . In this paper, we show that similar inapproximability results hold even if all delays are equal. Specifically, it is shown that the problem with equal exact delays cannot be approximated within \(\frac{4}{3}-\epsilon \) unless \(P=NP\) , and even if each job has equal-length operations, it is NP-hard to approximate the problem to within \(\frac{5}{4}-\epsilon \) . When there exist single-operation jobs, we show that the problem cannot be approximated within \(\frac{7}{6}-\epsilon \) unless \(P=NP\) . On the positive side, we first observe that the \(O(n\log n)\) -time exact algorithm for the flow shop problem behaves as a 2-approximation algorithm for the open shop problem, and then we present an improved \(\frac{5}{3}\) -approximation algorithm for the case with equal-length operations for each job.