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