the horizontal axis. In the first iteration
YDS identifies I1 = [ 3, 8] as interval of
maximum density, along with set SI1 =
{ J2, J3}. In I1, the red job J2 is preempted
at time 5 to give preference to the
orange job J3 having an earlier deadline. In the second iteration I2 = [ 13,
20] is the maximum density interval.
The dark green and light green jobs are
scheduled; preemption is again used
once. In the third iteration, the remaining job J3 is scheduled in the available
time slots.
Obviously, when identifying intervals of maximum density, YDS only has
to consider intervals whose boundaries are equal to the release times
and deadlines of the jobs. A straightforward implementation of the algorithm has a running time of O(n3). Li
et al. 34 showed that the time can be
reduced to O(n2 log n). Further improvements are possible if the job execution
intervals form a tree structure. 33
Yao et al. 40 also devised two elegant
online algorithms, called Average Rate
and Optimal Available. Whenever a new
job Ji arrives at time ri, its deadline di
and processing volume wi are known.
For any incoming job Ji, Average Rate
considers the density di = wi/(di − ri),
which is the minimum average speed
necessary to complete the job in time
if no other jobs were present. At any
time t, the speed s(t) is set to the accumulated density of jobs active at time t.
A job Ji is active at time t if it is available
for processing at that time, such as, if
t Î [ri, di]. Available jobs are scheduled
according to the EDF policy.
algorithm Average Rate: At any time
t, use a speed of .
Available unfinished jobs are scheduled using EDF.
Yao et al. 40 analyzed Average Rate
and proved that the competitive ratio is
upper bounded by 2a−1aa, for any a ³ 2.
Bansal et al. 6 showed that the analysis
is essentially tight by providing a nearly
matching lower bound.
The second strategy Optimal Available
is computationally more expensive than
Average Rate. It always computes an optimal schedule for the currently available
workload. A recomputation is necessary
whenever a new job arrives. A new optimal schedule for the future time horizon
can be constructed using YDS.
algorithm Optimal Available: Whenever a new job arrives, compute an
optimal schedule for the currently
available unfinished jobs.
Bansal et al. 9 gave a comprehensive analysis of the above algorithm
and proved that the competitive
ratio is exactly aa. Hence, in terms of
competitiveness, Optimal Available
is better than Average Rate. Bansal
et al. 9 also presented a new online
algorithm, called BKP according to
the initials of the authors, which
can be viewed as approximating the
optimal speeds of YDS in an online
manner. Again, the algorithm considers interval densities. For times
t, t1, and t2 with t1 < t £ t2, let w(t, t1,
t2) be the total processing volume of
jobs that have arrived by time t, have
a release time of at least t1 and a deadline of at most t2. Then, intuitively,
maxt1,t2 w(t, t1, t2)/(t2 − t1) is an estimate
of the speed used by YDS, based on the
knowledge of jobs that have arrived by
time t. The new algorithm BKP approximates this speed by considering specific time windows [et − (e − 1)t¢, t¢], for
t¢ > t, of length e(t¢ − t). The corresponding necessary speed is then multiplied
by a factor of e.
algorithm BKP: At any time t use a
speed of e . s(t), where
Available unfinished jobs are processed using EDF.
Bansal et al. 9 proved that BKP achieves a competitive ratio of ,
which is better than the competitiveness of Optimal Available for large values of a.
All the above online algorithms
attain constant competitive ratios
that depend on a and no other problem parameter. The dependence on
a is exponential. For small values of
a, which occur in practice, the competitive ratios are reasonably small. A
result by Bansal et al. 9 implies that the
exponential dependence on a is inherent to the problem. Any randomized
online algorithm has a competitiveness of at least W( (4/3)a).
refinements—Bounded speed: The
problem setting considered so far
assumes a continuous, unbounded
spectrum of speeds. However, in practice only a finite set of discrete speed
levels s1 < s2 < ... < sd is available. The
offline algorithm YDS can be adapted
easily to handle feasible job instances,
such as, inputs for which feasible
schedules exist using the restricted
set of speeds. Note that feasibility can
be checked easily by always using the
maximum speed sd and scheduling
available jobs according to the EDF policy. Given a feasible job instance, the
modification of YDS is as follows. We
first construct the schedule according
to YDS. For each identified interval I of
maximum density, we approximate the
desired speed DI by the two adjacent
speed levels sk and sk+ 1, such that sk < DI
< sk+ 1. Speed sk+ 1 is used first for some
d time units and sk is used for the last
|I| − d time units in I, where d is chosen
such that the total work completed in I
is equal to the original amount of |I|DI.
An algorithm with an improved running time of O(dn log n) was presented
by Li and Yao. 35
If the given job instance is not feasible, the situation is more delicate.
In this case it is impossible to complete all the jobs. The goal is to design
algorithms that achieve good
throughput, which is the total processing
volume of jobs finished by their deadline, and at the same time optimize
energy consumption. Papers7, 17
present algorithms that even work online.
At any time the strategies maintain a
pool of jobs they intend to complete.
Newly arriving jobs may be admitted
to this pool. If the pool contains too
large a processing volume, jobs are
expelled such that the throughput
is not diminished significantly. The
algorithm by Bansal et al. 7 is 4-com-
petitive in terms of throughput and
constant competitive with respect to
energy consumption.
Temperature minimization: High
processor speeds lead to high temperatures, which impair a processor’s
reliability and lifetime. Bansal et al. 9
consider the minimization of the maximum temperature that arises during
processing. They assume that cooling
follows Newton’s Law, which states
that the rate of cooling of a body is
proportional to the difference in temperature between the body and the
environment. Bansal et al. 9 show that
algorithms YDS and BKP have favorable
properties. For any jobs sequence, the
maximum temperature is within a constant factor of the minimum possible