We first address scheduling problems
with hard job deadlines. Then we consider the minimization of response
times and other objectives.
In general, two scenarios are of
interest. In the offline setting, all jobs
to be processed are known in advance.
In the online setting, jobs arrive over
time, and an algorithm, at any time,
has to make scheduling decisions
without knowledge of any future jobs.
Online strategies are evaluated again
using competitive analysis. Online
algorithm ALG is c-competitive if, for
every input, the objective function
value (typically the energy consumption) of ALG is within c times the value
of an optimal solution.
scheduling with Deadlines
In a seminal paper, initiating the algorithmic study of speed scaling, Yao et
al. 40 investigated a scheduling problem
with strict job deadlines. At this point,
this framework is by far the most extensively studied algorithmic speed scaling problem.
Consider n jobs J1,…,Jn that have
to be processed on a variable-speed
processor. Each job Ji is specified by a
release time ri, a deadline di, and a pro-
cessing volume wi. The release time
and the deadline mark the time inter-
val in which the job must be executed.
The processing volume is the amount
of work that must be done to complete
the job. Intuitively, the processing vol-
ume can be viewed as the number of
CPU cycles necessary to finish the job.
The processing time of a job depends
on the speed. If Ji is executed at con-
stant speed s, it takes wi /s time units to
complete the job. Preemption of jobs
is allowed, that is, the processing of a
job may be suspended and resumed
later. The goal is to construct a feasible
schedule minimizing the total energy
consumption.
Algorithm YDS repeatedly determines the interval I of maximum density. In such an interval I, the algorithm
schedules the jobs of SI at speed DI
using the Earliest Deadline First (EDF)
policy. This well-known policy always
executes the job having the earliest
deadline, among the available unfinished jobs. After this assignment, YDS
removes set SI as well as time interval
I from the problem instance. More
specifically, for any unscheduled job Ji
whose deadline is in the interval I, the
new deadline is set to the beginning of
I because the time window I is not available anymore for the processing of Ji.
Formally, for any Ji with di Î I, the new
deadline time is set to di := t. Similarly,
for any unscheduled Ji whose release
time is in I, the new release time is set
to the end of I. Again, formally for any
Ji with ri Î I, the new release time is
ri := t¢. Time interval I is discarded. This
process repeats until there are no more
unscheduled jobs. We give a summary
of the algorithm in pseudocode.
algorithm Yds: Initially J := {J1, …,
Jn}. While J ¹ ⵁ, execute the following
two steps. ( 1) Determine the interval I
of maximum density. In I, process the
jobs of SI at speed DI according to EDF.
( 2) Set J := JSI. Remove I from the
time horizon and update the release
times and deadlines of unscheduled
jobs accordingly.
Figure 2 depicts the schedule constructed by YDS on an input instance
with five jobs. Jobs are represented by
colored rectangles, each job having a
different color. The rectangle heights
correpond to the speeds at which the
jobs are processed. Time is drawn on
figure 2. an input instance with five jobs specified as Ji = (ri, di, wi). Blue J1 = (0, 25, 9); red J2 = ( 3, 8, 7); orange J3 = ( 5, 7, 4);
dark green J4 = ( 13, 20, 4); light green J5 = ( 15, 18, 3).
Speed
0
0.00
0.25
0.50
0.75
1.00
1. 25
1. 50
1. 75
2.00
2. 25
2. 50
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
