Inapproximability results for no-wait job shop scheduling

Inapproximability results for no-wait job shop scheduling

0.00 Avg rating0 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:
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.