Approximability of Flow Shop Scheduling
(Extended Abstract)
Leslie A. Hall
Abstract
Shop scheduling problems are notorious for their intractability, both in
theory and practice. In this paper,
we demonstrate the existence of a polynomial
approximation scheme for the flow shop scheduling problem with an arbitrary fixed
number of machines. For the three common shop models (open, flow, and job),
this result is the only known approximation scheme. Since none of the three
models can be approximated arbitrarily closely in the general case (unless $P=NP$),
the result demonstrates the approximability gap between the models in which
the number of machines is fixed, and those in which it is part of the
input of the instance.
The result can be extended to
flow shops with job release dates and delivery times.
We also describe a related polynomial approximation scheme for the problem
of scheduling an open shop with a single bottleneck machine and an arbitrary
number of non-bottleneck machines.
Research supported by NSF grant DMI-9496153.
For a postscript copy of this extended abstract, please send email to
lah@jhu.edu.