Approximation schemes for constrained scheduling problems

Several constrained scheduling problems are considered. The first polynomial approximation schemes for the problem of minimizing maximum completion time in a two-machine flow shop with release dates and for the problem of minimizing maximum lateness for the single and parallel-machine problem with release dates are described. All of these algorithms are based upon the notion of an outline, a set of information with which it is possible to compute, with relatively simple procedures and in polynomial time, an optimal or near-optimal solution to the problem instance under consideration. Two related precedence-constrained scheduling problems are discussed, and new approximation results are presented