95-01
A polynomial approximation scheme for problem $F2/r_j/C_{max}$
Preprint series: 95-01, Preprints
The paper is published: Operations Research Letters, Vol. 20, 1997, 75 - 79.
Abstract: We present a polynomial (1 + ffl)-approximation scheme for the stronglyNP -hard problem of scheduling n jobs in a two-machine flow-shop subjectto release dates. This scheme is based on a dynamic programming approachapplied to a problem with rounded release dates and processing times. Incomparison with the known Hall\'s polynomial approximation scheme, ourscheme has a better time complexity estimation for small ffl and sufficientlylarge n.
Keywords: scheduling, two-machine flow shop, polynomial approximation scheme, dynamic programming
The author(s) agree, that this abstract may be stored asfull text and distributed as such by abstracting services.