Volume 8 (2012) Article 7 pp. 165-195
Special Issue in Honor of Rajeev Motwani
Online Scheduling to Minimize Maximum Response Time and Maximum Delay Factor
Motivated by strong lower bounds, we consider the resource augmentation model introduced in Kalyanasundaram and Pruhs (JACM'95) where the algorithm is given a machine with faster speed than the adversary. We give scalable algorithms; that is, algorithms that when given $(1+\epsilon)$-speed are $O(\mbox{poly}(1/\epsilon))$-competitive for any fixed $\epsilon > 0$. Our main contributions are for broadcast scheduling. Along the way we also show that the FIFO (first-in-first-out) algorithm is $2$-competitive for broadcast scheduling even when pages have non-uniform sizes. We complement our algorithmic results by showing that a natural greedy algorithm modeled after LWF (Longest-Wait-First) is, for any $s \ge 1$, not constant competitive for minimizing maximum delay factor when given an $s$-speed machine. The lower bound holds even in the restricted setting of standard scheduling of jobs with uniform size, and demonstrates the importance of the trade-off made in our algorithms.