Inapproximability results for no-wait job shop scheduling

0.00 Avg rating—0 Votes

Article ID:	iaor2005930
Country:	Netherlands
Volume:	32
Issue:	4
Start Page Number:	320
End Page Number:	325
Publication Date:	Jul 2004
Journal:	Operations Research Letters
Authors:	Woeginger Gerhard J.
Keywords:	combinatorial analysis

Abstract:

We investigate the approximability of the no-wait job shop scheduling problem under the makespan criterion. We show that this problem is APX-hard (i) for the case of two machines with at most five operations per job, and (ii) for the case of three machines with at most three operations per job. Hence, these problems do not possess a polynomial time approximation scheme, unless 𝒫 = NP.

Reviews

Required fields are marked *. Your email address will not be published.