Abstract:

We extend the study of online algorithms for energy-efficient deadline
scheduling to the overloaded setting.  Specifically, we consider a
processor that can vary its speed between $0$ and a maximum speed $T$
to minimize its energy usage (of which the rate is roughly a cubic
function of the speed).  As the speed is upper bounded, the system may
be overloaded with jobs and no scheduling algorithms can meet the
deadlines of all jobs. An optimal schedule is expected to maximize the
throughput, and furthermore, its energy usage should be the smallest
among all schedules that achieve the maximum throughput.  In designing
a scheduling algorithm, one has to face the dilemma of selecting more
jobs and being conservative in energy usage.  Even if we ignore energy
usage, the best possible online algorithm is 4-competitive on
throughput.  On the other hand, existing work on energy-efficient
scheduling focuses on minimizing the energy to complete all jobs on a
processor with unbounded speed, giving several $O(1)$-competitive
algorithms with respect to the energy usage. We present the first
online algorithm for the more realistic setting where processor speed
is bounded and the system may be overloaded; the algorithm is
$O(1)$-competitive on both throughput and energy usage.  If the maximum
speed of the online scheduler is relaxed slightly to $(1+\epsilon)T$
for some $\epsilon > 0$, we can improve the competitive ratio on
throughput to arbitrarily close to one, while maintaining
$O(1)$-competitive on energy usage.

This is a joint work with HL Chan, WT Chan, TW Lam, LK Lee and KS Mak
and appears in SODA 2007.