Speed is as powerful as clairvoyance.
We introduce resource augmentation as a method for analyzing online scheduling problems. In resource augmentation analysis the on-line scheduler is given more resources, say faster processors or more processors, than the adversary. We apply this analysis to two well-known on-line scheduling problems, the classic uniprocessor CPU scheduling problem 1 |ri, pmtn|&Sgr; Fi, and the best-effort firm real-time scheduling problem 1|ri, pmtn| &Sgr; wi( 1- Ui). It is known that there are no constant competitive nonclairvoyant on-line algorithms for these problems. We show that there are simple on-line scheduling algorithms for    these problems that are constant competitive if the online scheduler is equipped with a slightly faster processor than the adversary. Thus, a moderate increase in processor speed effectively gives the on-line scheduler the power of clairvoyance. Furthermore, the on-line scheduler can be constant competitive on all inputs that are not closely correlated with processor speed. We also show that the performance of an on-line scheduler is best-effort real time scheduling can be significantly improved if the system is designed in such a way that the laxity of every job is proportional to its length.
Introduction
We consider several well known nonclairvoyant
scheduling problems, including the problem of minimizing
the average response time [13, 15], and best-effort
firm real-time scheduling [1, 2, 3, 4, 8, 11, 12, 18].
(We postpone formally defining these problems until
the next section.) In nonclairvoyant scheduling some
relevant information, e.g. when jobs will arrive in the
future, is not available to the scheduling algorithm A.
The standard way to measure the adverse effect of this
lack of knowledge is the competitive ratio:
I
Opt(I)
where A(I) denotes the cost of the schedule produced
by the online algorithm A on input I, and Opt(I) denotes
the cost of the optimal schedule. The competi-
Supported in part by NSF under grant CCR-9202158.
kalyan@cs.pitt.edu, http://www.cs.pitt.edu/-kalyan
y Supported in part by NSF under grant CCR-9209283.
tive ratio for a problem is then
min
A
I
Opt(I)
where the min is over all online algorithms. The standard
way to interpret the competitive ratio is as the
payoff to a game played between an online algorithm
and an all-powerful malevolent adversary that specifies
the input I.
One of the primary goals of any analysis is to identify
what works well in practice. Competitive analysis
has been criticized because it often yields ratios that
are unrealistically high for "normal" inputs and as a
result it can fail to identify the class of online algorithms
that work well. The scheduling problems that
we consider are good examples of this phenomenon
in that their competitive ratios are unbounded, while
there are simple nonclairvoyant algorithms that perform
reasonably well in practice. We explain this phenomenon
by adopting what we call the weak adversary
model, which assumes that the speed of the processor
used by the nonclairvoyant scheduler is (1
the speed of the processor used by the clairvoyant ad-
versary, where ffl ? 0. We define the ffl-weak competitive
ratio of a problem to be:
min
A
I
where the subscripts denote the speed of the processor
used by the corresponding algorithm.
The original motivation for the standard competitive
ratio was to use the divergence of the online al-
gorithm's output from optimal as a measure of the
adverse effect of nonclairvoyance. Not only does the
ffl-weak competitive ratio give us another measure, but
also suggests a practical way to combat the adverse
effect of nonclairvoyance. If a problem has a small ffl-
competitive ratio for some moderate ffl then this
means that a moderate increase in processor speed will
effectively buy the power of clairvoyance. Therefore,
the weak adversary model gives the system designer
a practical way, increasing the speed of the processor,
to improve the performance of the system.
On "normal" inputs, one would intuitively expect
that the offline performance of the system would not
degrade drastically if the speed of the processor is increased
slightly. If an algorithm has a bounded ffl-
competitive ratio then it has a bounded competitive
ratio for all inputs I where Opt 1 (I)=Opt1+ffl (I) is
bounded. Thus an algorithm with a bounded ffl-weak
competitive ratio has a bounded competitive ratio for
all inputs that fall under this formulation of "normal".
We give algorithms for these scheduling problems
that have ffl-weak competitive ratios that are solely a
function of ffl, and not the input I. Furthermore, as
ffl increases the ffl-weak competitive ratios quickly approach
one.
Previous and Current Results
Our generic scheduling problem consists of a collection
Jng of independent jobs to be run
on a single processor. (While these results extend to
the multiprocessor setting, we restrict our attention
to a single processor for simplicity. ) Each job J i has
a release time r i and a length x i . J i can not be run
before time r i . The time required to complete J i is x i
divided by the speed of the processor. We assume that
the online/nonclairvoyant scheduler is not aware of J i
. We consider only preemptive scheduling,
that is, a job can always be restarted from the point of
last execution. We assume that such context switches
require no time.
The problem of minimizing the average response
time of the jobs is a well known and widely studied
problem in operating system scheduling (see for example
[7, 14]). We assume that the nonclairvoyant
scheduler does not learn x i at time r i , and more gen-
erally, can not deduce x i until it has run J i to com-
pletion. The completion time c i of a job J i is the time
at which J i has been allocated enough time to finish
execution. Similarly, the response time is w
and the idle time for a speed s processor is w
For the problem of minimizing the average response
the deterministic competitive ratio
is \Omega\Gamma n 1=3 ), and the randomized competitive ratio is
n) [15]. It can easily be shown that any algorithm
that doesn't unnecessarily idle the processors
has a competitive ratio of O(n). Surprisingly, this is
the best known upper bound on the competitive ra-
tio, even allowing randomization. The competitive ratio
for the commonly used Round Robin algorithm is
In section 3, we first consider the queue size as a
function of time. Define QA (t; s) as the set of jobs that
have been released before time t, but have not been
finished by algorithm A by time t assuming that A is
using a speed s processor. We show that for every non-
clairvoyant scheduling algorithm A there is an input
I and a time t such that jQA (t; 1)j=jQ Opt (t;
set cardinality. We then give an on-line
algorithm Balance, B for short, that guarantees
that at all times that jQB (t; 1
ffl jQOpt (t; 1)j.
This implies that Balance has an ffl-weak competitive
ratio of 1
ffl for the problem of minimizing the
average response time. In contrast, we show that the
ffl-weak competitive ratio of Round Robin is \Omega\Gamma n 1\Gammaffl ),
1. We then assume that the nonclairvoy-
ant scheduler is equipped with a unit speed processor
and an ffl speed processor, instead of a (1+ffl) speed pro-
cessor. (Here we are assuming ffl ! 1.) In this case we
give a nonclairvoyant scheduling algorithm Balance2
with average response time at most 1+ 1
ffl times the average
response time of the adversary. This means that
a nonclairvoyant scheduler with a supercomputer and
an old 386 PC can be constant competitive against a
clairvoyant scheduler with only a supercomputer. Fi-
nally, we demonstrate that Balance is fair every job
it sees by proving that the maximum idle time of Balance
is quite comparable to that of offline.
In best-effort firm real-time scheduling each job J i
now has a deadline d i , and a benefit b i , in addition
to a release time and an execution time. It is also
useful to define the value density of a job J i to be
and the laxity of J i for a speed s processor
to be d which is the maximum amount
J i can be delayed if it is to be completed. Since real-time
systems are embedded systems, the scheduler is
generally aware in advance of the jobs that it may re-
ceive. Thus, the standard assumption is that at time
r i the scheduler learns of x i , d i , and b i . If J i is finished
by time d i then the algorithm receives a benefit
of b i , otherwise no benefit is gained from this job. The
goal of the scheduler is to maximize the total benefit
of the jobs that it completes. Since this is a maximization
problem, the competitive ratio definitions in
the introduction have to be modified by inverting the
ratios. So for example, the competitive ratio for this
problem is then
min A
I
Opt(I)
The deterministic competitive ratio for this problem
is \Theta(\Phi) [3, 4, 11, 18], and the randomized competitive
ratio is \Theta(min(log \Phi; log \Delta)) [8, 12], where the
importance ratio \Phi is the ratio of the maximum value
density of a job to the minimum value density of a
job, and \Delta is the ratio of the length of the longest
job to the length of the shortest job. The competitive
ratio is unbounded even in the special case that each
In section 4, we first assume that both the nonclair-
voyant scheduler and the adversary have unit speed
processors, and that the laxity of each job J i is at
least fflx i . An upper bound on the standard competitive
ratio, under this laxity assumption, will also upper
bound the ffl-weak competitive ratio since any job
J i that doesn't have laxity at least fflx i for a (1
speed processor can't be finished by a unit speed pro-
cessor. This formulation also has the added advantage
of showing the effect of laxity. Under these laxity as-
sumptions, we give an algorithm Slacker that has
a competitive ratio that is only a function of ffl, and
approaches three as ffl increases. These results show
that if a real-time system is designed so that every job
has laxity that is a reasonable fraction of the execution
time of that job, then the resulting competitive ratio is
reasonably small. The effect of laxity on the competitive
ratio in the special case of
in [1, 6]. We then show that the ffl-weak competitive
ratio for Slacker approaches one as ffl increases.
The weak adversary model, comparing an online algorithm
against a less powerful but more knowledgeable
adversary, has been considered before in query-response
problems such as the k-server problem and
its special cases (e.g. [17, 19]), and online weighted
matching [9]. In each case the adversary is handicapped
by having fewer servers. One can argue that
the weak competitive ratio is essentially what is called
the comparative ratio in [10]. However, the results
in [10] are really of a different flavor in that they are
primarily concerned with the effect of partial clairvoy-
ance. Other methods have been suggested to address
the limitations of competitive analysis. These methods
include restricting the input distribution to satisfy
some special properties (e.g. [10, 16]), and comparing
the cost of a solution produced by an online algorithm
on input I to the worst-case optimal cost of any input
of the same size as I [5].
3 Average Response Time
The following well known lemma explains why we
first consider the queue size.
Lemma 3.1 For any scheduling algorithm A with
a speed s processor, the total response time is
Lemma 3.2 For every nonclairvoyant scheduling algorithm
A there is an input I and a time t such that
Proof
jobs arrive at time t 0 . One job arrives
at time t 1. The adversary sets the jobs
lengths so that online hasn't finished any jobs by time
t . One can show that if the adversary always runs
the shorter job, then it will always have at most two
active jobs. The key point to note is that at time t i ,
the sum S of the remaining unfinished lengths
of the two jobs that the adversary has in its queue
satisfies
We now give an online algorithm Balance that
guarantees that its queue size is not too much more
than optimal under the weak adversary scenario.
Algorithm Balance : For any job J i and time t we
define to be the amount of time that Balance
has executed J i before time t. At all times t, Balance
splits the processing time equally among all jobs J i
that have minimum
Our analysis of Balance is based on the following
lemma.
Lemma 3.3 Let B be the algorithm Balance. At any
point t in time, jQB (t; 1
ffl jQOpt (t; 1)j.
The proof of this lemma follows from the ensuing
chain of reasoning. Let UB be the set of jobs
unfinished by Balance, and UA be the set of jobs
unfinished by the adversary at time t mentioned in
Lemma 3.3. Intuitively, the adversary can use time
that Balance spent on jobs in UA to finish jobs in
UB \GammaU A . We need to show that the weak adversary assumption
means that in order to borrow enough time
to finish jobs in UB \Gamma UA it must be the case that
UA is reasonably large. We say that a job J i can
immediately borrow from another job J j , denoted by
Balance ran J j at some time t 0 satisfying
then at time t 0 the adversary could have been executing
Balance was executing J j . The borrow
relation, denoted J i

is the transitive closure
of the immediately borrow relation. We define

g. Intuitively, if the adversary
transfers some time from a J j 2 UA to a J
then
Lemma 3.4 Let J i be a job that Balance saw but
did not complete by time t. For any job J
Proof Suppose there is a job J
that . If there are many such jobs J j ,
then select the one that can be reached from J i by
a shortest path P in the directed unweighted graph
induced by the relation immediately borrow. Let J k
be the job in P immediately before J j . So J k /- J j .
By the definition of P ,
x be the last time that J j was run before time t. Then
notice that it must be the case c k ? x or J k would not
be J j 's predecessor in P . Hence,
By the definition of Balance, if J k /- J j , then k
. Hence, we
deduce We reach a contradiction since
pg. Since the adversary
completes jobs in UB \GammaU A , the total time spent by
Balance on jobs in UA must be at least
We partition the time that Balance spent on jobs in
such that the cumulative
time in the ith class is at least ffl . Note that T i
could be a collection of time intervals. We call a partition
good if there is no job X 2 UA such that some
portion of time spent by Balance on X is included
in T i and kXk t ?kJ i k t .
Lemma 3.5 There always exists a good partition.
Proof be the
earliest release time of a job in B(X). Let UB \Gamma
where the indexing is such that
j. By the definition of
the relation immediately borrow, it must be the case
that any job executed by Balance during the time
interval [t(J i ); t] must be a member of B(J i ). Also,
observe that for each i in the range 1
must run and finish jobs in B(J i during
the interval [t(J i ); t]. Therefore, for each 1 - i - p, it
must be the case that the cumulative amount of time
spent by Balance to jobs in B(J must be at
least
Observe that if consequently
by induction on i, time
spent on jobs in UA by Balance can be distributed
to jobs in UB \Gamma UA such that for each job J
gets ffl units of time from jobs in B(J i )"U A . The
result follows since, by lemma 3.4, kXk t -kJ i k t for any
The proof of the lemma 3.5 intuitively suggests
that, if the adversary is going to finish a job
needs to raise ffl k J i k t units
of times from jobs J 3.4 we
know that This suggests that we analyze
the following problem to get lower bound on number
of jobs in UB .
The Politician Problem: There are n politicians
trying to raise money from m contributors. The ith
politician must raise fflS i dollars, and the j contributor
has C j dollars to contribute. The election rule
says that the jth contributor can contribute to the
ith politician only if C j - S i . A politician can raise
money from many contributors and a contributor can
give money to several politicians.
Lemma 3.6 If there is a solution for the above Politicians
Problem then ffln - m.
Proof be the contribution from
the the j contributor to the i politician. Since
is the fraction of fflS i that the ith politician
got from the j contributor, and since every politician
is successful, it is the case that,
Now by the election rule,
Here
is the fraction of C j that the j contributor
gave to the ith politician.
Proof Applying the lemma 3.5
we know that for each job J must
find ffl units of times from jobs J
By lemma 3.4 . Now applying lemma 3.6
to this case, we get jUA j
The following theorem then follows by lemma 3.1.
Theorem 3.1 The ffl-weak competitive ratio of Balance
with respect to average response time is at most
ffl .
We now show that the commonly used algorithm
Round Robin [7, 14] does not have a constant ffl-weak
competitive ratio for small ffl. Round Robin splits the
processing time evenly among all unfinished jobs.
Lemma 3.7 For the problem of minimizing the average
response time, the ffl-weak competitive ratio of Round
Robin is
Proof We divide time into stages. Let the ith
stage, start at time t i . We let t
ffl. There are two jobs of length (1+ ffl) released
at time t 0 , and one job is released at each time t i ,
length s(i) that is exactly the same length
as Round Robin has left on each of the previous jobs.
To guarantee that the adversary can finish the job
released at time t i by time t
We then get the recurrence
Expanding this we get The total response
time for the adversary is then \Theta(
which is \Theta(1). The total response time for Round
Robin is then \Theta(
The following theorem shows that Balance does
not overly delay any job to improve the performance
of average response time.
Theorem 3.2 The ffl-weak competitive ratio of Balance
with respect to maximum idle time is 1
ffl .
Proof t be the time at which Balance
completed a job J i for which the idle time is maxi-
mum. By shortening other unfinished jobs, let us assume
that Balance completed all jobs by time t. Let
be the idle time experienced by
using Balance. By lemma 3.4, the amount
of time spent by Balance on any job during (r
is at most . Due to the difference in speed, it
must be the case that the adversary finished a job J j
at time (1 ffl)t. If Balance did not run J j during
d. On the other hand if Balance
ran J j during (r
Therefore, t is at most t \Gamma d. Notice that J j must
have arrived on or before t\Gamma . Therefore, the idle
time incurred by the adversary for J j must be at least
We now assume that the nonclairvoyant scheduler
equipped with a unit speed processor and an ffl speed
processor can be almost as competitive as if it was
equipped with a (1 speed processor. Here we are
assuming ffl ! 1. We further assume for simplicity that
1=ffl is an integer.
Algorithm Balance2 : Run the job J i that has
been run the least on the unit speed processor. Run
the job, other than J i , that has been run the least on
the ffl speed processor.
The analysis of Balance2 follows the same line as
the analysis of Balance. We modify the definition
of immediately borrow in the following way. A job J i
can immediately borrow time from another job J j if at
running J j while either, Balance2 was not running
running J i on a processor that is slower than
the processor that J j was being run on. We define UA ,
UB , borrow, and B(J i ) as before. We define to be
the initial length of J i that has been executed before
time t by Balance2.
Lemma 3.8 Let J i be a job that Balance saw but
did not complete by time t. For any job J
The Modified Politicians Problem: There are n
politicians and m original contributors. Let S 1 -
must
refund at least fflS i+1 dollars to the contributors. The
jth contributor requires C j dollars in refunds. The
election rule says that the ith politician can refund
money to the jth contributor only if C j - S i .
Lemma 3.9 If there is a solution for this modified politicians
problem then m - ffl(n \Gamma 1).
Proof Assume without loss of generality that
Assume that S i 1
refunds to C j1 and
refunds to C j2 , with
such a situation a swap. By transitivity we can have
refund to C j2 and S i 2
refund to C j1 . It is easy to
see that we can assume without loss of generality that
there is a solution to the modified politician problem
without any swaps. Let us multiply the refund of each
politician by a factor of 1=ffl. Simultaneously, we also
increase the pool of potential contributors by a factor
of 1=ffl by replacing each original contributor by
1=ffl identical contributors. By repeating the previous
assignment 1=ffl times, the politicians can still be successful
in refunding the money.
We prove by induction that for any i, 1
there are at least i contributors among the m=ffl contributors
that get refunds from politicians 1 through
i, and those i contributors will not get refunds from
other politicians. Assume
gets all of its refunds from the first politician by
the no swapping assumption. Otherwise, if
then C 1 cannot accept refunds from politicians
Now assuming that the hypothesis holds for
show that the hypothesis also holds for i. By the induction
hypothesis, contributors 1 through
get a refund from the ith politician. Let C ff(i) be
the highest contributor that got a refund from the ith
politician. If C ff(i) ? S i+1 , then C ff(i) cannot get a
refund from politicians On the other hand,
if C ff(i) - S i+1 then the i contributor gets all of its
refund from the i politician by the no swapping assumption

Lemma 3.10 Let B be the algorithm Balance2. At
any point t in time, jQB (t; 1+
ffl jQOpt (t; 1)j.
Proof Once again we are going to reduce to
the modified politicians problem, where the members
of UA are the contributors, and the members of UB \Gamma
UA are the politicians. Let UB \Gamma
j. So the jobs are ordered
by increasing order of release times. Since at least two
jobs are unfinished during the time interval (r
it must be the case that Balance2 was running both
processors throughout this period.
assume that Balance2 was running
two jobs J a and J b at a time t 0 between time r ff(i) and
t. Then we claim J a g. If
neither J a or J b is J ff(i\Gamma1) then both are in B(J ff(i\Gamma1) )
by definition. Otherwise if say J
are all being executed in round robin
fashion, and the claim once again follows. Notice that
Assume that the length of each job J ff(i)
is exactly . This is the best case for the adver-
sary. Then Balance2 and the adversary executed the
same length of each job in (UB \Gamma UA
Hence, the extra ffl(t \Gamma r ff(2) ) work (the refunds) done
by Balance2 must go to jobs in UA . Consider how
this might be distributed. For each
must be the case that the extra work must during the
period (r must be distributed to jobs in
We think of J ff(i\Gamma1) as giving this
refund to jobs in B(J ff(i\Gamma1) . The election rule is
satisfied by lemma 3.8. We now apply the modified
politicians lemma, and the rest of the argument is as
before.
Theorem 3.3 The average response time for Bal-
ance2, with a unit speed processor and an ffl ! 1 speed
processor, is at most 1
ffl times the average response
time of an adversary given only a unit speed processor.
Proof This theorem follows by applying
lemma 3.10 and noting that the adversary must be
running some jobs for a duration of ffl' even after Balance
completed all jobs at time '.
4 Real-time Scheduling
Before describing the algorithm Slacker we need
to introduce some definitions and notation. Recall
that we first assume that both the nonclairvoyant
scheduler and the clairvoyant adversary have unit
speed processors, and that the laxity of each job J i is
at least fflx i . For notational convenience, let
A job J i is viable at time t for a scheduling algorithm
A if A can finish J i before d i , that is, if A has run J i
for at least x units of time. Define the slack
of a job J i at time t by s i t. A job is
fresh at time t if s Otherwise, we say
the job is stale at time t. Let c ?
constant that we define later. Define the density class
of a job J i to be blog c v i c. Assuming that we normalize
so that the smallest value density is one, the density
classes then range from 0 to blog c \Phic. If X is a set of
jobs then let kXk=
denote the total benefit
of jobs in X. Let Opt be the set of jobs finished by
the adversary.
Algorithm Slacker: At time r i Slacker switches
to J i if and only if J i is in a higher density class than
the job J j that Slacker is currently running. If this
happens, J j is saved as the representative job for density
class blog c v j c. If Slacker finishes a job J i at
time t, then let ff be the largest integer such that there
is currently a fresh job in density class ff or a viable
representative job in class ff. If there is a viable representative
job J i in density class ff then Slacker
resumes execution of J i . Otherwise, Slacker starts
executing an arbitrary fresh job in density class ff.
Let S be the set of jobs completed by Slacker,
and R the set of jobs run by Slacker. S may be
a proper subset of R since Slacker may not finish
every job that it started.
Lemma 4.1 Let J i be an arbitrary representative
job in density class ff that Slacker did not com-
plete. Then for a period of at least d
units of time between r i and d i Slacker was running
a job in density class ff
Lemma 4.2 Assuming the density of each job is an integral
power of c,
Proof We imagine that each job J i 2 R has
an account associated with it. The account for a job
initially starts with b i points. All other accounts
start with zero points. We redistribute points
from accounts of jobs in S to accounts of jobs in R \Gamma S.
The argument is by reverse induction on the density
classes. First note that Slacker finishes every job in
density class blog c \Phic that it begins. Assume we now
are considering jobs in density class ff. Let J i
be a job that was the representative job for density
class ff between time t 1 and t 2 . If Slacker ran a
job J j in density class fi ? ff for t units of time between
are transferred
from J j 's account to J i 's account. By lemma 4.1, J i
borrowed for a total time of at least ffi x i , and hence
borrowed at least c ff x i points. Thus the account for
now contains at least b i points.
We now need to examine how much the account of
a job J i in density class ff can be depleted by jobs in
lower density classes. The representative jobs in density
class ff take at most c fi x i =ffi points from the
account of J i . Hence, the number of points remaining
in the account for J i is at least
Lemma 4.3 Assuming the density of each job is an integral
power of c, kOptk- 1+3ffi
Proof Assume that if the adversary ran a job
with density c ff for t units of time, we credit the adversary
with points regardless of whether it finished
the job or not. Define a job to be dense if it has density
c ff or greater. We then show that the total amount of
time the adversary spent running dense jobs is at most
times the time that Slacker was running
dense jobs. We divide time up in the following way.
Let oe 0 be the first point of time where Slacker starts
running a dense job. Let - i , i - 0, be the first point of
time after oe i where Slacker is not running a dense
job. Let oe i , i - 1, be the first point in time after
after - i\Gamma1 that Slacker begins running a dense job.
Note that no dense job can arrive between any - i and
oe i+1 . Consider the longest dense job J j that arrived
between a oe i and a - i , and that Slacker did not run.
Then J i had to have been stale at time - i . Hence,
. This means
that the time that the adversary is running dense jobs
that Slacker didn't run is at most 1+2ffi
times the
time that Slacker was running dense jobs. We must
add one to this ratio for the jobs that both the adversary
and Slacker ran. The lemma then follows by
reverse induction on ff.
Theorem 4.1 Under the assumption that every job J i
has laxity at least fflx the competitive ratio of
Slacker is at most
Proof applying lemma 4.2
and lemma 4.3, and by removing the condition that
the density of a job is an integral power of c.
One can verify that by letting
, we get
a bounded competitive ratio for all ffi ? 0, and that
the competitive ratio goes to three as ffi increases. If
we go back to assuming that Slacker has a (1
speed processor, we can show that the ffl-weak competitive
ratio approaches one by modifying lemma 4.3
as follows. The proof is very similar to the proof of
lemma 4.3.
Lemma 4.4 Assuming the density of each job is an integral
power of c, and that Slacker has a (1 speed
processor,
5 Conclusion
We believe that the weak adversary model will be
useful in identifying online algorithms that work well
in practice for other types of problems. It is important
that the weakening of the adversary should be
done in such a way that the corresponding strengthening
of online algorithm can be achieved in practice.
It is worth mentioning that for the problems considered
in this paper, increasing the speed of the online
processor is not the only way to weaken the adver-
sary. For example, in the case of real-time scheduling,
it suffices to design the real-time system in such a way
that the laxity condition is satisfied.
Finally, we would like to mention that the weak
adversary model has been used recently to show that
the natural greedy algorithm, which works reasonably
well in practice, is almost optimal for online weighted
matching [9]. Traditional competitive analysis shows a
bound of \Theta(2 m ) whereas the weak adversary analysis
yields a bound of \Theta(log m) where m is the size of the
graph.

Acknowledgements

: The second author would like
to thank Daniel Mosse, Rege Colwell, Richard Su-
choza, and Dimitri Zorine for many helpful discussions
on real-time scheduling.



--R

"On improved performance guarantees through the use of slack times,"
"On-line scheduling to maximize task completions"
"On the competitiveness of on-line real-time task scheduling"
"On-line scheduling in the presence of overload"
"A new measure for the study of on-line algorithms"
"On-line real-time scheduling with laxities,"
Operating System Concepts
"Fault- tolerant real-time scheduling"
"The on-line transportation problem"
"Beyond competitive analysis,"
"D over :An optimal on-line scheduling algorithm for overloaded real-time systems"
"MOCA: a multiprocessor on-line competitive algorithm for real-time system scheduling,"

Operating Systems: Concepts and Designs
"Non- clairvoyant scheduling"
"A statistical adversary for on-line algorithms"
"Amortized efficiency of list update and paging rules"
"On-line scheduling of jobs with fixed start and end time"
"The k-server dual and loose competitiveness for paging,"
--TR
Amortized efficiency of list update and paging rules
Operating system concepts (3rd ed.)
On-line scheduling in the presence of overload
Operating systems: concepts and design
On the competitiveness of on-line real-time task scheduling
MOCA
On-line scheduling of jobs with fixed start and end times
Nonclairvoyant scheduling
Approximation algorithms for scheduling
Optimal time-critical scheduling via resource augmentation (extended abstract)
The art of computer programming, volume 1 (3rd ed.)
Scheduling for Overload in Real-Time Systems
Online computation and competitive analysis
Scheduling in the dark
Page replacement for general caching problems
Trade-offs between speed and processor in hard-deadline scheduling
Scheduling Algorithms
Speed is More Powerful than Claivoyance
Competitive Analysis of the Round Robin Algorithm
On-line Scheduling
The Online Transportation Problem
Fault-Tolerant Real-Time Scheduling
Maximizing Job Completions Online
Minimizing flow time nonclairvoyantly
Jitter Control in QoS Networks

--CTR
Mohamed Eid Hussein , Uwe Schwiegelshohn, Utilization of nonclairvoyant online schedules, Theoretical Computer Science, v.362 n.1, p.238-247, 11 October 2006
Jae-Hoon Kim , Kyung-Yong Chwa, Online deadline scheduling on faster machines, Information Processing Letters, v.85 n.1, p.31-37, January
Leah Epstein , Rob van Stee, Optimal on-line flow time with resource augmentation, Discrete Applied Mathematics, v.154 n.4, p.611-621, 15 March 2006
Marek Chrobak , Leah Epstein , John Noga , Ji Sgall , Rob van Stee , Tom Tich , Nodari Vakhania, Preemptive scheduling in overloaded systems, Journal of Computer and System Sciences, v.67 n.1, p.183-197, August
Thomas Erlebach , Alexander Hall, NP-hardness of broadcast scheduling and inapproximability of single-source unsplittable min-cost flow, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.194-202, January 06-08, 2002, San Francisco, California
Thomas Erlebach , Alexander Hall, NP-Hardness of Broadcast Scheduling and Inapproximability of Single-Source Unsplittable Min-Cost Flow, Journal of Scheduling, v.7 n.3, p.223-241, May-June 2004
Ho-Leung Chan , Tak-Wah Lam , Kar-Keung To, Non-migratory online deadline scheduling on multiprocessors, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
Luca Becchetti , Stefano Leonardi , Alberto Marchetti-Spaccamela , Kirk Pruhs, Semi-clairvoyant scheduling, Theoretical Computer Science, v.324 n.2-3, p.325-335, 20 September 2004
Francis Y. L. Chin , Stanley P. Y. Fung, Improved competitive algorithms for online scheduling with partial job values, Theoretical Computer Science, v.325 n.3, p.467-478, 6 October 2004
Jae-Hoon Kim , Kyung-Yong Chwa, Non-clairvoyant scheduling for weighted flow time, Information Processing Letters, v.87 n.1, p.31-37, July
Guido Schfer , Naveen Sivadasan, Topology matters: smoothed competitiveness of metrical task systems, Theoretical Computer Science, v.341 n.1, p.216-246, 5 September 2005
Jason McCullough , Eric Torng, SRPT optimally utilizes faster machines to minimize flow time, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
Bala Kalyanasundaram , Kirk R. Pruhs, Maximizing job completions online, Journal of Algorithms, v.49 n.1, p.63-85, 1 October
Jeff Edmonds , Kirk Pruhs, Broadcast scheduling: when fairness is fine, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.421-430, January 06-08, 2002, San Francisco, California
N. Bansal , K. Dhamdhere, Minimizing weighted flow time, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
Bala Kalyanasundaram , Kirk R. Pruhs, Minimizing flow time nonclairvoyantly, Journal of the ACM (JACM), v.50 n.4, p.551-567, July
Chiu-Yuen Koo , Tak-Wah Lam , Tsuen-Wan Ngan , Kunihiko Sadakane , Kar-Keung To, On-line scheduling with tight deadlines, Theoretical Computer Science, v.295 n.1-3, p.251-261, 24 February
Anupam Gupta , Bruce M. Maggs , Florian Oprea , Michael K. Reiter, Quorum placement in networks to minimize access delays, Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, July 17-20, 2005, Las Vegas, NV, USA
Chiu-Yuen Koo , Tak-Wah Lam , Tsuen-Wan Ngan , Kar-Keung To, Competitive deadline scheduling via additional or faster processors, Journal of Scheduling, v.6 n.2, p.213-223, March/April
Tak-Wah Lam , Tsuen-Wan Johnny Ngan , Kar-Keung To, Performance guarantee for EDF under overload, Journal of Algorithms, v.52 n.2, p.193-206, August 2004
Chiu-Yuen Koo , Tak-Wah Lam , Tsuen-Wan Ngan , Kar-Keung To, Extra processors versus future information in optimal deadline scheduling, Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures, August 10-13, 2002, Winnipeg, Manitoba, Canada
Jeff Edmonds , Kirk Pruhs, A maiden analysis of Longest Wait First, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
Michael H. Goldwasser, Patience is a virtue: the effect of slack on competitiveness for admission control, Journal of Scheduling, v.6 n.2, p.183-211, March/April
C. Greg Plaxton , Yu Sun , Mitul Tiwari , Harrick Vin, Reconfigurable resource scheduling, Proceedings of the eighteenth annual ACM symposium on Parallelism in algorithms and architectures, July 30-August 02, 2006, Cambridge, Massachusetts, USA
Ryan Porter, Mechanism design for online real-time scheduling, Proceedings of the 5th ACM conference on Electronic commerce, May 17-20, 2004, New York, NY, USA
Jeff Edmonds , Suprakash Datta , Patrick Dymond, TCP is competitive against a limited adversary, Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, June 07-09, 2003, San Diego, California, USA
Jeff Edmonds , Kirk Pruhs, A maiden analysis of longest wait first, ACM Transactions on Algorithms (TALG), v.1 n.1, p.14-32, July 2005
Kirk Pruhs, Competitive online scheduling for server systems, ACM SIGMETRICS Performance Evaluation Review, v.34 n.4, March 2007
Wun-Tat Chan , Tak-Wah Lam , Kin-Shing Liu , Prudence W. H. Wong, New resource augmentation analysis of the total stretch of SRPT and SJF in multiprocessor scheduling, Theoretical Computer Science, v.359 n.1, p.430-439, 14 August 2006
Chandra Chekuri , Ashish Goel , Sanjeev Khanna , Amit Kumar, Multi-processor scheduling to minimize flow time with  resource augmentation, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA
Ho-Leung Chan , Tak-Wah Lam , Kin-Shing Liu, Extra unit-speed machines are almost as powerful as speedy machines for competitive flow time scheduling, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.334-343, January 22-26, 2006, Miami, Florida
Joan Boyar , Lene M. Favrholdt , Kim S. Larsen, The relative worst order ratio applied to paging, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
Nikhil Bansal , Kirk Pruhs, Server scheduling in the Lp norm: a rising tide lifts all boat, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
Joan Boyar , Lene M. Favrholdt , Kim S. Larsen, The relative worst-order ratio applied to paging, Journal of Computer and System Sciences, v.73 n.5, p.818-843, August, 2007
Sandy Irani , Kirk R. Pruhs, Algorithmic problems in power management, ACM SIGACT News, v.36 n.2, June 2005
Roughgarden , va Tardos, How bad is selfish routing?, Journal of the ACM (JACM), v.49 n.2, p.236-259, March 2002
resource augmentation;multi-level feedback scheduling;scheduling