May. 7, 3:30pm, Gates 6115 (Note unusual location)

Kevin Schewior, TU Berlin

New Results on Resource Augmentation in Online Deadline Scheduling

Kevin Schewior, TU Berlin

New Results on Resource Augmentation in Online Deadline Scheduling

Abstract:

We consider preemptively scheduling jobs with release dates and hard deadlines on m parallel machines. An online algorithm is provided an instance (each job at its release date) that possesses a feasible (offline) schedule meeting all deadlines. It is known that there is no online algorithm that always produces a feasible schedule given just these m machine. Thus, resource augmentation, that is, increasing the machine speed or the number of machines, has been proposed by Phillips et al. (STOC 1997).

Regarding augmentation by speed, we give a new (now tight) lower bound of *2*-*1*/*m* on the speed required by the very natural algorithm Least
Laxity First (LLF), matching the guarantee achieved by simply prioritizing by deadlines. In this context, we open up the analysis of
instances with a fixed number of distinct release dates and show more positive results about LLF. We also note that an algorithm by Anand
et al. (ICALP 2011) does not, as claimed, only require a speed of *e*/(*e*-*1*). Thus the best provable guarantee of an algorithm to date is
the one by Lam and To (SODA 1999), namely *2*-*2*/(*m*+*1*), and the gap to their lower bound of *1.207* remains.

Finally, we give the first algorithm requiring *f*(*m*) unit-speed machines for a function *f*. In particular, we have *f*(*m*)=*O*(*m ^{2}*