Article ID: | iaor20051757 |
Country: | Netherlands |
Volume: | 33 |
Issue: | 3 |
Start Page Number: | 255 |
End Page Number: | 262 |
Publication Date: | May 2005 |
Journal: | Operations Research Letters |
Authors: | Strusevich V.A., Billaut J.-C., Bouquard J.-L., Kubzin M.A. |
Keywords: | combinatorial analysis |
In this paper we provide a fairly complete complexity classification of various versions of the two-machine permutation flow shop scheduling problem to minimize the makespan in which some of the jobs have to be processed with no-wait in process. For some version, we offer a fully polynomial-time approximation scheme and a