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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

On the Inapproximability of Two-machine Open Shop Scheduling with Exact Delays

  • Shunzhang Lu,
  • An Zhang,
  • Mengyuan Hu,
  • Yong Chen,
  • Guangting Chen

摘要

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.