|Abstract of Paper|
Approximation Schemes for the Min-Max Starting Time Problem
by Leah Epstein and Tamir Tassa
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.