A polynomial approximation scheme for problem F 2/rj /Cmax

We present a polynomial approximation scheme {Hϵ} 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 Hall's polynomial approximation scheme, our scheme has a better time complexity estimation for small ϵ and sufficiently large n.