A polynomial approximation scheme for problem F2/rj/Cmax

What is it about?

We present a polynomial approximation scheme for the sytongly 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.

Featured Image