A polynomial time approximation scheme for the two-stage multiprocessor flow shop problem

AbstractIn this paper we investigate the two-stage multiprocessor flow shop scheduling problem F2(P)|·|Cmax, where the numbers m1 and m2 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). An extension of our algorithm yields an approximation scheme for the closely related two-stage multiprocessor job shop problem