Abstract of Paper

Approximation Schemes for the Min-Max Starting Time Problem
by Leah Epstein and Tamir Tassa

Abstract:

We consider the off-line scheduling problem of minimizing the maximal
starting time. Given a sequence of n jobs, they have to be assigned to m
identical machines so that if the jobs assigned to a certain machine are
processed according to their order, the first time in which all jobs have
already started their processing is minimized. Our main result is a
polynomial time approximation scheme for this problem in the case where m is
considered as part of the input. As the input to this problem is a sequence
of jobs, rather than a set of jobs where the order is insignificant, we
present techniques that are designed to handle ordering constraints. Those
techniques are combined with common techniques of assignment problems in
order to yield a polynomial time approximation scheme.