| 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