Zurück zu den Preprints des Jahres 1995


A polynomial approximation scheme for problem $F2/r_j/C_{max}$

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
large n.

scheduling, two-machine flow shop, polynomial approximation scheme, dynamic programming

This paper was published in:
Operations Research Letters, Vol. 20, 1997, 75 - 79.