by Kovalyov, M.Y., Werner, F..
Series: 1995-01, Preprints
We present a polynomial (1 + ffl)-approximation scheme for the strongly
NP -hard problem of scheduling n jobs in a two-machine flow-shop subject
to release dates. This scheme is based on a dynamic programming approach
applied to a problem with rounded release dates and processing times. In
comparison with the known Hall's polynomial approximation scheme, our
scheme has a better time complexity estimation for small ffl and sufficiently
scheduling, two-machine flow shop, polynomial approximation scheme, dynamic programming
This paper was published in:
Operations Research Letters, Vol. 20, 1997, 75 - 79.