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.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">></ETX>