Approximation schemes for constrained scheduling problems

Publisher Website
Google Scholar
Abstract
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.<>