The ACO Seminar (2013–2014)

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² log(m)). The key is to carefully combine two algorithms that solve two important subclasses of the problem. It remains as an open problem whether there is a constant c such that cm suffice in the online setting. This is joint work with Lin Chen and Nicole Megow.