95-01

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

by Kovalyov, M.Y.; Werner, F.

 

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.

Letzte Änderung: 01.03.2018 - Ansprechpartner: Webmaster