This paper presents several online scheduling algorithms for two related performance metrics, namely maximum response time and maximum delay-factor, and also their weighted versions. The delay factor metric is new (introduced in Chang et al. (SODA'08)), while special cases of maximum weighted response time have been considered before. We study both the standard scheduling model where each arriving job requires its own processing, as well as the broadcast scheduling model where multiple requests/jobs can be simultaneously satisfied.

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.