A polynomial time approximation scheme for the two-stage multiprocessor flow shop problem
In this paper we investigate the two-stage multiprocessor flow shop scheduling problem F2(P)\ . \C-max, where the numbers m(1) and m(2) of machines available in the two stages are part of the input. We demonstrate the existence of a polynomial time approximation scheme for this problem. This result solves the simplest case of an open problem that has been posed by Leslie Hall in a recent paper (Hall, 1995). hn extension of our algorithm yields an approximation scheme for the closely related two-stage multiprocessor job shop problem. (C) 2000 Elsevier Science B.V. All rights reserved.
polynomial time approximation scheme flow shop scheduling job shop worst-case analysis approximation algorithm