Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
10524100 | Operations Research Letters | 2005 | 8 Pages |
Abstract
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 43-approximation algorithm.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
J.-L. Bouquard, J.-C. Billaut, M.A. Kubzin, V.A. Strusevich,