A polynomial approximation scheme for a constrained flow-shop scheduling problem

The paper presents a polynomial approximation scheme for a two-machine flow shop scheduling problem with the additional constraint that each job has a release date, when it first becomes available for processing. This is one of the first such results for multiple-task scheduling problems; previously, the best approximation result for this problem was an algorithm guaranteed to deliver a schedule of length at most 5/3 times the optimal length. The present (1+∈)-approximation algorithm is intuitively appealing because it is based on Johnson’s algorithm, an optimization algorithm for the problem without release dates.