Theory of Computing
-------------------
Title : Online Scheduling to Minimize Maximum Response Time and Maximum Delay Factor
Authors : Chandra Chekuri, Sungjin Im, and Benjamin Moseley
Volume : 8
Number : 7
Pages : 165-195
URL : http://www.theoryofcomputing.org/articles/v008a007
Abstract
--------
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(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 >= 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.