Admission control with immediate notification.
When admission control is used, an on-line scheduler chooses whether or not to complete each individual job successfully by its deadline. An important consideration is at what point in time the scheduler determines if a job request will be satisfied, and thus at what point the scheduler is able to provide notification to the job owner as to the fate of the request. In the loosest model, often seen in real-time systems, such a decision can be deferred up until the job's deadline passes. In the strictest model, more suitable for customer-based applications, a scheduler would be required to give notification at the instant that a job request arrives.Unfortunately there seems to be little existing research which explicitly studies the effect of the notification model on the performance guarantees of a scheduler. We undertake such a study by reexamining a problem from the literature. Specifically, we study the effect of the notification model on the non-preemptive scheduling of a single resource in order to maximize utilization. At first glance, it appears severely more restrictive to compare a scheduler required to give immediate notification to one which need not give any notification. Yet we are able to present alternate algorithms which provide immediate notification, while matching most of the performance guarantees which are possible by schedulers which provide no such notification. In only one case are we able to give evidence that providing immediate notification may be more difficult.
Introduction
We consider the non-preemptive scheduling of a single resource in an online setting. Job requests
arrive, with each request specifying the length of time for which the resource is needed as well as
a deadline by which the job should be completed. The scheduler is not required to complete all
job requests, yet the goal is to maximize the resource utilization. In such a setting, an important
consideration is at what point in time the scheduler determines if a job request will be satisfied,
and thus at what point the scheduler is able to provide notification to the job owner as to the fate
of the request. The natural model for notification has varied greatly between application domains.
In traditional real-time systems, for example, admission control has been used for processing
jobs with what are termed firm deadlines [16]. If a system issues a job request with a firm deadline
this job does not necessarily need to be completed, however completing the job provides no utility
if its deadline has passed. In this setting, it is quite natural to allow the scheduler to take a "wait-
and-see" approach for each request. The scheduler is allowed to defer a final decision on whether
or not to service the request up to the time when the deadline passes. From the scheduler's point
of view, this is the loosest possible model for providing notification.
Department of Mathematical and Computer Sciences, Loyola University, Chicago. Research completed while at
Princeton University, supported by DIMACS (Center for Discrete Mathematics and Theoretical Computer Science),
a National Science Foundation Science and Technology Center.
y Microsoft Corporation. Research completed while at Princeton University.
Conversely, admission control is routinely used in a wide array of customer-based applications,
where job requests are submitted by individual customers to a company which may or may not be
able to meet the requests by their given deadlines. Examples of such applications in daily life might
include photo-finishing, dry cleaning, and package delivery. The problem has been motivated on
a more industrial scale to model requests for an uninterrupted connection in a telecommunication
system, used for the transmission of text, sound, images, video or other data. Unfortunately the
loosest model for notification is inappropriate in these applications. If a customer has a job which
"absolutely, positively" must be done by a certain deadline, it is unacceptable to entrust that job
to a company that may wait until the deadline approaches before informing the customer that
the request will not be completed. In this setting, we can consider the strictest possible model
for notification. Immediately upon receiving a request, we can require that the scheduler either
promise completion of the job or else outright reject it. In this way, if a request is rejected, the
customer can still approach an alternate provider about servicing the job 1 .
Although these two views represent the extremes in modeling notification, it is possible to define
various intermediate models by specifying at what point notification is required. For example, in an
ATM network, the decision of whether to admit a request is not immediate, yet it is made during
a specific connection setup period.
Unfortunately there seems to be little existing research which explicitly studies the effect of
the notification model on the performance of a scheduler. Our goal is to undertake such a study,
starting with this particular scheduling problem.
While receiving earlier notification can only be to the advantage of a customer, providing such
notification can be nothing but a hindrance to the scheduler. Remarkably though, we are able
to give alternate algorithms which provide immediate notification while matching most of the
best possible performance bounds achieved by schedulers which provide no advanced notification
[10, 11]. There does exist one case for which we are able to give evidence that providing immediate
notification may indeed be strictly more difficult.
1.1 Definitions
Following the standard notation of Graham et al. [12], we consider a job J i to be a triple of non-negative
integers
is the arrival or release time of the job, p i
is the processing
time, and d i
is the deadline for the job's completion. Job J i
is available at time t with respect to a
schedule oe if r i  t  d has not been started in oe prior to time t. Additionally,
we say that a job J i has slack s which is the amount of time between the job's
arrival and the last possible time at which it could be started while still meeting its deadline. The
patience of a problem instance is defined as
so that every job J j
with processing
time p j has a slack s j   \Delta p j [11]. We let \Delta denote the ratio between the largest and smallest
processing times of an instance.
The gain of a schedule oe on instance I is defined equal to
our goal is to maximize
the gain. We assume that an online algorithm A has no knowledge of a job until the release time,
at which point all job parameters are known. Furthermore, we assume that the algorithm has no
a priori knowledge of the value of , however we will assume the algorithm has knowledge of the
value of \Delta. We will measure the performance of A by comparing its gain to the gain of an optimal
offline algorithm, opt, that has a priori knowledge of all jobs when creating a schedule [7, 15, 20].
We say that a (deterministic) online algorithm A is c-competitive if gain opt (I)  c \Delta gain A (I), for all
input instances I. When considering randomized online algorithms, the competitiveness compares
1 Unfortunately, the authors' experiences have too often involved companies who give the appearance of immediate
notification when accepting a request, yet later announce that the deadline will not be met.
the gain of the optimal schedule to the expected gain of a randomized algorithm. We assume that
a worst case input for an algorithm is chosen by an oblivious adversary who must choose the entire
sequence in advance [6, 19].
1.2 Our Results
Our primary results are algorithms which provide immediate notification while meeting the same
bounds on performance as previous algorithms which do not provide any type of advanced notifica-
tion. Specifically, we give algorithms providing immediate notification while matching the following
competitiveness bounds given by previous algorithms without notification [10, 11]:
ffl For the case when all job lengths are equal, we present a deterministic algorithm which
provides immediate notification. This algorithm is 2-competitive in general, and is (1+ 1
competitive where   0 is the patience of the instance.
ffl For the case when arbitrary job lengths are allowed and  ? 0 is the patience of an instance, we
present a (2+ 1
)-competitive, deterministic algorithm which provides immediate notification.
ffl For the case when arbitrary job lengths are allowed and \Delta  1 is the ratio between the largest
and smallest job lengths, we present a (4dlog 2 \Deltae)-competitive, randomized algorithm which
provides immediately notification.
The first two of the above results are matched by existing lower bounds for the setting in which
no advanced notification is required. These lower bounds trivially apply to the stricter setting of
immediately notification and thus our results are tight. The third result improves, by a constant
factor, the best known upper bound for the model with no advanced notification, and it is matched
asymptotically by an
\Omega\Gamma/17 \Delta) lower bound for that model [17].
Our secondary results concern the special case when all jobs have one of two distinct lengths.
Although this special case has limited practical importance, it appears interesting theoretically.
We are able to give some evidence that providing immediate notification may be strictly more
difficult than providing no notification. Specifically, the best current results for the randomized
competitiveness include a lower bound of 2 and an upper-bound of 4, in the model without notification
[10, 17]. We make progress towards a separation between the competitiveness in the various
notification models, giving the following results:
ffl We give a 4-competitive randomized algorithm which provides immediate notification.
ffl We give a 3-competitive randomized algorithm (without notification).
ffl We show that no randomized algorithm which provides immediate notification can be better
than 7-competitive.
Even with our improvements, we note that there is not yet an explicit separation between the
two notification models, as the gaps between upper and lower bounds overlap.
Previous Work
Although understanding the effect of the notification model for admission control seems a clear
priority, there has been very little mention of this issue in the standard literature. The only
previous work we are able to find which explicitly studies the effect of the notification model on
performance involves a system for delivering video-on-demand [4]. In contract to our results, they
show a striking difference in the competitiveness of that problem based on the exact model for
notification.
A partial explanation for the lack of previous work focusing on the notification model is that
the issue becomes moot in a non-preemptive model for which all jobs have zero slack. In such a
setting, the scheduler is implicitly required to make an immediate decision of whether to begin a
job or to reject the request.
Such is the case on the earliest work directly related to the problem we study. Lipton and
Tomkins introduce a problem referred to to as online interval scheduling, in which all jobs request
the immediate use of the resource [17]. When all job lengths are equal, a greedy online algorithm is
guaranteed to find the optimal solution. Their model implicitly assumes that a scheduler does not
have a priori knowledge of the value of \Delta. When jobs have one of two distinct lengths, the authors
provide a randomized 2-competitive algorithm and a matching lower bound. With arbitrarily many
job lengths, the authors provide a randomized O((log \Delta) 1+ffl )-competitive algorithm, and a lower
bound of !(log \Delta) for the competitiveness of any randomized online algorithm. Adapting their
constructions to our model where the value of \Delta is known results in lower bounds of
with
two distinct lengths and
\Omega\Gammad/1 \Delta) with arbitrarily many lengths.
The model of Lipton and Tomkins was later generalized by Goldman, Parwatikar and Suri to
a setting in which each job explicitly specifies a deadline of its choice [10]. As the scheduler may
have flexibility in when to start a job, the choice of notification models becomes meaningful. The
problem as defined by Goldman et al. implicitly corresponds to the setting in which no advanced
notification is provided by the scheduler. In this setting, they provide a tight upper and lower
bound of 2 for the deterministic competitiveness when all jobs have equal length. When all jobs
have one of two lengths, they give a 4-competitive randomized algorithm, as compared to the lower
bound of 2 from Lipton and Tomkins. Finally, when arbitrary job lengths are allowed, they provide
a 6(dlog 2 \Deltae +1)-competitive, randomized algorithm, matching
the\Omega\Gammae/3 \Delta) lower bound to within
a constant factor.
Goldwasser considers the same setting as Goldman et al., refining the analysis based on the
introduction of , the patience of an instance, as an additional parameter [11]. When all jobs have
equal length, Goldwasser proves that the same deterministic algorithm which Goldman et al. had
shown to be 2-competitive is really
bc+1 )-competitive. Similarly, he proves that in the case
where jobs have arbitrary lengths, a simple deterministic algorithm is (2+ 1
)-competitive. Matching
lower bounds are given for both of these results.
Scheduling a single resource is a special case of the more general problem of call control in larger
communication networks, where both admission control and routing are issues. The competitiveness
of various call control models has been studied in both the non-preemptive [1, 2] and preemptive
[3, 9] models; a more complete survey is given by Plotkin [18].
A technique of particular use in our work is given by Awerbuch, Bartal, Fiat and Ros'en in solving
some general call control problems on tree networks [2]. Though these problems do not closely relate
to the problem we study, they introduce a technique for admission control termed "Classify and
Randomly Select". Jobs are classified into groups based on the individual job parameters such that
jobs within a group are similar enough for a base algorithm to be competitive. Randomness is used
to pick one particular class a priori, and then the overall algorithm runs the base algorithm on the
selected group, while rejecting all jobs from other groups. The overall competitiveness increases
by a factor equal to the number of groups. Our results will make use of the fact that if immediate
notification can be provided by a base algorithm, then the overall "Classify and Randomly Select"
technique can provide immediate notification.
ProcessArival(J)
accept J
else if Feasible(Q [ fJg; nextidle) then
accept J
else
reject J
be the job with earliest deadline.
nextidle / current time
Give resource to J i
When J i completes
if
Order all jobs of S by non-decreasing deadline
Calculate lateststart / min 1js (d j
if t  lateststart then
return true
else
return false

Figure

1: The Greedy-Notify algorithm.
Providing Immediate Notification
A simple deterministic algorithm, denoted as Greedy, was analyzed by Goldman et al. and by
Goldwasser [10, 11]. This algorithm keeps all available jobs in a queue and whenever the resource
becomes idle, it schedules the available job with the earliest deadline. As jobs waiting in the queue
become infeasible they can be explicitly removed from the queue. Unfortunately, until this point
a customer making a job request is given no notification as to whether or not the request will
eventually be satisfied.
For this reason, we consider another natural greedy algorithm which provides immediate noti-
fication. The algorithm, Greedy-Notify, maintains a queue of accepted jobs. Whenever a new
job arrives it accepts the job if and only if it can be feasibly scheduled along with all previously
accepted jobs; otherwise it immediately rejects the job. The feasibility check is based on a classic
result of Jackson stating that, in the absence of release times, the earliest due date ordering of jobs
will produce a feasible schedule when one exists [14]. Specifically, if we are given a set S of available
jobs, ordered by non-decreasing deadlines, the jobs can be feasibly scheduled starting
at time t if and only if the following inequality is satisfied,
1js
The complete algorithm is given in Figure 1.
3.1 An efficient implementation
The algorithm presentation of Figure 1 is clear, however it is not the most efficient, as the feasibility
check requires that jobs be sorted according to deadline, and that a prefix sum of the processing
times is computed. Naively this check
time, and the overall algorithm requires
time in the worst case for an instance with n job requests. We can improve the running
time by using a better data structure for maintaining the set Q and testing feasibility.
Theorem 1 The algorithm Greedy-Notify can be implemented on an instance with n job re-
quests, such that it runs in O(log n) time per job request and O(n log n) overall time.
Proof: We will maintain the set Q ordered by non-decreasing deadlines using a red-black tree
[5, 13]. We will further augment this tree to allow us to perform a feasibility test for the jobs of
set Q given a starting time t. We make use of Theorem 15.1 of the text by Cormen, Leiserson
and Rivest which states that extra fields can be added to nodes of a red-black tree, while still
maintaining O(log n) running time for insertions and deletions, so long as the set of fields at a
given node x can be computed solely from the information at x together with the values of the
fields at the children of x [8]. In particular, each job J x
be stored at some node x in which
we maintain the following two additional fields:
the sum of the processing times for all jobs stored in the subtree rooted at node x.
latest[x] - the latest possible starting time for a feasible scheduling containing only those jobs
stored in the subtree rooted at node x.
The field total[x] is maintained as the sum of p x and the values of total[lef t[x]] and total[right[x]],
in the cases where the respective child exists. The value of latest[x] should equal the righthand side
of Equation (1), when applied to the set of nodes in the subtree rooted at x. We claim this value
can be calculated as follows,
d x
When x is a leaf, the above is simply d x \Gamma p x . In general, an individual term from Equation (1)
for a job J i
depends only on jobs in the set which have lessor or equal deadlines to that of J i
Therefore, nodes in the left subtree of x have the same contribution for the tree rooted at x as they
do for the tree rooted at lef t[x]. For x itself, the term is precisely is precisely d
Finally, the term associated with any job in the right subtree will be reduced exactly by the sum
of p x
and total[lef t[x]] because those jobs will surely have deadlines less than or equal to a job in
the right subtree. Therefore, the minimum term contributed by a node in the right subtree of x
will equal
Based on these formulas, we can conclude that jobs can be inserted into or deleted from set Q
in O(log jQj) time. Furthermore, the value of latest stored at the root represents the latest possible
starting time for a feasible schedule containing all the jobs stored in the structure. This allows the
condition nextidle)) to be tested in O(log jQj) time, by inserting J into set Q,
comparing nextidle to the value of latest[root], and deleting J from the structure, in the case that
it was infeasible.
Overall, we can be sure that each job accounts for at most one insertion into our structure, and
thus at most one deletion. Since the size of the queue can never exceed n, we get an overall running
time which is O(n log n).
3.2 Equal Length Jobs
We begin by considering the case when all jobs have the same length. This is an important special
case in its own right, for instance in ATM networks where packet sizes are all the same. In addition,
we will use an algorithm designed for equal length jobs as a base algorithm for the more general
case with multiple job lengths.
It would be convenient if we could show that the Greedy-Notify algorithm always produces
the identical schedule as the Greedy algorithm considered by earlier researchers [10, 11]. Unfortunately
this is not the case, as demonstrated by an instance with the following three jobs:
On this instance Greedy produces a schedule
consisting of J 1 followed by J 3 whereas Greedy-Notify accepts both J 1 and J 2 and rejects J 3 .
What we can prove is that in the special case where all job lengths are equal, Greedy-Notify
and Greedy always produce schedules with the same gain. Specifically, we prove that the busy periods
for the resource are exactly the same for schedules produced by the two algorithms. Therefore,
all previous upper bounds for the performance of Greedy automatically apply to Greedy-Notify
for this case.
Theorem 2 When all job lengths are equal, if Greedy begins running a job J at some time t, then
Greedy-Notify begins running a (possibly different) job at time t. Similarly, if Greedy-Notify
begins running a job J at some time t, then Greedy begins running a job at time t.
Proof: For simplicity, we assumed that both algorithms break ties lexicographically, when considering
jobs with equivalent deadlines. We let oe denote the schedule produced by the Greedy
algorithm and  the schedule produced by the Greedy-Notify algorithm. For sake of contradic-
tion, if the theorem is not true we let t be the earliest time at which one schedule starts running
a job, J , while the other schedule does not start any job. We consider two cases, depending on
whether oe starts job J at time t or  starts job J at time t.
First we consider the case where oe starts J at time t. Inductively, we prove the existence, for
any integer k  1, of a sequence of jobs fJ
g and times t
such that
ffl At time t 1 ,  is idle and oe begins job J
, for all 2  x  k,  begins job J i
and oe begins job J i x
The general framework is shown in Figure 2. As a base case, when
We have assumed that oe starts J at time t and since all jobs have equal length and t is
defined as the earliest violation of the theorem,  must remain idle at time t. For the inductive
step, we assume a sequence for value k and prove the existence for k + 1.
n:
s:

Figure

2: The first case of Theorem 2, in which oe runs J at time t.
s:
n:

Figure

3: The second case of Theorem 2, in which  runs J at time t.
We argue that job J i k
was accepted by Greedy-Notify. To do so, we demonstrate a feasible
schedule which includes J i k
together with any previously accepted jobs of . As  is idle at time
is possible to modify the schedule  so that each job J i x
is scheduled at time t x
rather than
1. The modified starting times respect the individual jobs' release times and
deadlines, as witnessed by oe. Such a modification leaves an idle spot starting at time t k
which
could be used to schedule J i k
Both jobs J i k
and J i
arrived on or before time t k
as witnessed respectively by their placement
in oe and . Both were available to oe at time t k , yet Greedy chose to run J i k
at that time based on
their deadlines. From the preceding paragraph, we know that J i k
had arrived and been accepted
by  on or before time t k and yet Greedy-Notify begins running job J i
at that time. This
could only happen if it were the case that job J i k
had run in  prior to time t k . Therefore we define
time t k+1
as the time at which job J i k
begins in . Since t
t, our assumption is that
some job must also be started precisely at that time in oe. We call this job J i k+1
, completing the
induction.
Overall, the induction shows that an arbitrarily long such sequence of unique jobs can be created,
since all times are unique. This contradicts the finiteness of a given instance, so it must be that
our assumption is flawed regarding the existence of a time t when oe starts a job J yet  idles.
For the second case in which the earliest violation involves  starting job J at time t, we give
a slightly simpler symmetric argument. Inductively, we prove the existence, for any integer k  1,
of a sequence of jobs fJ i 1
g and times t , such that
ffl At time t 1 , oe is idle and  begins job J
ffl At time t x , for all 2  x  k, oe begins job J i
and  begins job J i x
The general framework is shown in Figure 3. As a base case, when
We have assumed that  starts J at time t and since all jobs have equal length and t is
defined as the earliest violation of the theorem, oe must remain idle at time t. For the inductive
step, we assume a sequence for value k and prove the existence for k + 1.
From the inductive hypotheses, we see that both jobs J i k
and J i
arrived on or before time t k
as witnessed respectively by their placement in  and oe. Furthermore, both jobs were accepted by
Greedy-Notify and yet J i k
was chosen to run at time t k while job J i
remained in the queue.
Since Greedy chose to run J i
at time t k
, we can conclude that job J i k
must have already been
completed in oe prior to time t k . Therefore, we define time t k+1 as the time at which job J i k
begins
in oe. Since t t, our assumption is that some job must also be started precisely at that
time in . We call this job J i k+1
, completing the induction. As in the first case, such an arbitrarily
long sequence of unique jobs provides a contradiction, completing the proof.
The following two corollaries follow trivially from Theorem 2 together with the previous analysis
of Greedy given by Goldman et al. [10] and Goldwasser [11], respectively.
Corollary 3 When all jobs have the same length, Greedy-Notify is 2-competitive.
Corollary 4 When all jobs have the same length and a problem instance has a patience   0,
Greedy-Notify is
)-competitive.
3.3 Arbitrary Job Lengths
When we consider instances with arbitrary job lengths, not only is it the case that the schedules
of Greedy and Greedy-Notify may differ but the gain of the schedules may vary drastically.
Consider an instance with three jobs J +1i. The
Greedy-Notify algorithm would achieve a gain of 2, as jobs J 1 and J 2 are accepted, however job
J 3 is rejected as it is not possible to schedule all three jobs. Alternatively, the Greedy algorithm
would run job J 1 during [0; 1), and at time 1 would choose to start J 3 , achieving a gain of 1 \Delta.
Even so, we begin by considering the deterministic Greedy-Notify algorithm. Goldwasser
defines an algorithm to be a greedy-type algorithm so long as the resource is never idle while a job is
available [11]. We show that Greedy-Notify is indeed a greedy-type algorithm. If the resource is
idle, all previously accepted jobs must have already completed. If a rejected job is available at such
an idle time this contradicts the condition for rejection, as starting that job at this time provides
a feasible schedule together with all previously accepted jobs. Based on this, the following two
results follow trivially, as they were proven for any greedy-type algorithm by Goldwasser [11].
Theorem 5 When jobs have arbitrary lengths, Greedy-Notify is
)-competitive.
Lemma 6 When jobs have arbitrary lengths with \Delta equal to the ratio between the maximum and
minimum lengths, Greedy-Notify is \Delta)-competitive.
In order to design a competitive randomized algorithm, we apply Lemma 6 to provide a base
algorithm for the "Classify and Randomly Select" technique, together with the following lemma
given by Awerbuch et al. [2].
Lemma 7 If the requests can be classified into a set, P, of distinct groups, such that on each group
base algorithm is guaranteed to be c-competitive, then the "Classify and Randomly Select"
technique provides a randomized algorithm which is cjP j-competitive.
Theorem 8 When jobs have arbitrary lengths in the range [1; \Delta], we can give a randomized algorithm
with immediate notification which is (4dlog 2 \Deltae)-competitive.
Proof: We can create dlog 2 \Deltae distinct groups such that all jobs in a particular group are guaranteed
to have lengths which are within a factor of two of each other. If we run Greedy-Notify on a
set of jobs which have lengths within a factor of two of each other, Lemma 6 states that this
algorithm will be 4-competitive. Using Greedy-Notify as a base algorithm for the "Classify and
Randomly Select" technique results in a (4dlog 2 \Deltae)-competitive randomized algorithm, according
to Lemma 7. We note that because Greedy-Notify gives immediate notification and the "Classify
and Randomly Select" technique can immediately reject those jobs not in the selected class, the
resulting algorithm indeed provides immediate notification.
Note that this upper bound is actually stronger than 6(dlog 1)-competitive algorithm
provided by Goldman et al. for the case without any notification [10]. To be fair, in the case
without any notification, Goldman et al. specifically sought an algorithm which did not rely on the
"Classify and Randomly Select" technique, as this technique results in a large variance which may
be unappealing in practice. It might be desirable to develop an algorithm with notification that
does not rely on such a technique, but no such algorithm is evident.
4 The case with two distinct job lengths
We conclude by examining the randomized competitiveness of the case when all jobs have one of
two known lengths. Without loss of generality we will assume all jobs have length either 1 or \Delta ? 1,
and we will refer to these groups as small jobs and large jobs respectively.
Unlike the previous cases, we give some evidence that the immediate notification model is
strictly harder than the non-notification model for this setting. For the setting with immediate
notification, we are able to provide an upper bound of 4 on the competitiveness, and a lower bound
of 7. In the previously studied model without any notification, we improve the best known upper
bound to 3 opposite a previous lower bound of 2. Unfortunately, as these gaps overlap, we are
unable to definitively separate the competitiveness of the two settings.
4.1 With immediate notification
We first consider the case of two jobs lengths in the setting where immediate notification is required.
We provide a 4-competitive randomized algorithm, which matches the best previously known bound
for the setting with no notification. Then we provide a lower bound of 7on the competitiveness of
any randomized algorithm which provides immediate notification. This improves upon the lower
bound of 2 which is known for the setting with no notification.
Theorem 9 When jobs have one of two distinct lengths, there exists a 4-competitive, randomized
algorithm which provides immediate notification.
Proof: We again rely on the "Classify and Randomly Select" technique. This time, we create two
groups, one consisting of small jobs and one consisting of large jobs. Since each group has only
jobs of equal length, Corollary 3 guarantees that Greedy-Notify is 2-competitive when used as a
base algorithm on each group. Thus, according to Lemma 7, the "Classify and Randomly Select"
technique results in a randomized 4-competitive algorithm. As was the case with multiple length
jobs, this algorithm provides immediate notification.
Theorem 10 When jobs have one of two distinct lengths, no randomized algorithm with notification
can be c-competitive for c ! 7=3.
Proof: We fix an arbitrarily large \Delta and define the following four problem instances, shown in

Figure

4:
ffl Instance I 1 consists of J
ffl Instance I 2 consists of J
I
e
e
I 2
Figure

4: Four problem instances from proof of Theorem 10
maximum possible gain given behavior
instance gain opt A B C D
I
I
I 3
I 4

Table

1: Summary of potential gains from proof of Theorem 10
ffl Instance I 3 consists of J
ffl Instance I 4 consists of J
Given any of the above four instances, we can classify a particular execution of an algorithm into
one of exactly four disjoint behaviors:
ffl Behavior A: J 1 was accepted and began processing at time
ffl Behavior B: J 1 was accepted, but the resource remained idle at time
ffl Behavior C: J 1 was rejected and J 2 was accepted;
ffl Behavior D: both J 1 and J 2 were rejected.

Table

presents some observations based directly on the instance and behavior definitions.
Given any fixed randomized algorithm R, we can let PA the probability that the
algorithm produces behavior A when run on instance I 1 . We define similar notation for the
probabilities of all other behaviors on all four instances. Since the four behaviors constitute a
disjoint partition of all possible behaviors, we have for each 1  i  4,
At particular times, several of these instances are indistinguishable to an online algorithm, and so
we claim:
Based on this, we simplify our notation, letting
From

Table

1, we infer the following lower bounds on the competitiveness of R:
We will show that it is not possible for R to have competitiveness strictly less than 7
3 on
each of these instances, proving the overall theorem. For the sake of contradiction, assume that
the competitiveness is strictly less than 7
3 on all four instances. Equation assures us that
PD was chosen to be arbitrarily large. Similarly Equation (10) assures us that
Combining these bounds with the knowledge of Equations (2), (5) and (6) we see
The assumption that comp R 7together with Equation (7) can be re-written to show 6
Similarly, we can conclude from Equation (8) that 6! PA
Adding these two inequalities, and referring to Equations (11) and (12), we conclude
This contradicts our assumption that algorithm R was strictly less than 7
3 -competitive on all four
instances. Therefore an oblivious adversary is always able to pick an instance on which R is at
least 7-competitive.
4.2 Without notification
For the setting in which no notification is required, the upper bound of four is achieved with a randomized
algorithm given by Goldman et al. [10]. Their algorithm, denoted Greedy-TwoLengths,
is simple to describe. All available jobs are kept in two queues, Q 1 for small jobs and Q \Delta for large
jobs. At any point the resource is idle, if there are any available large jobs, the algorithm runs the
large job with earliest deadline. If there are no large jobs but there are small jobs available, then
the algorithm flips a fair coin taking one of the following actions. With probability 1, the algorithm
runs the small job with earliest deadline. Otherwise, the algorithm immediately rejects the small
job with earliest deadline, removing it from the queue, and it virtually schedules the resource for
1 unit of time blocking all other small jobs from running (but allowing a large job to begin if one
arrives). The analysis of their algorithm is tight, as witnessed by an instance consisting of the
two jobs 1:5i. The optimal gain on this instance is 2, however the
expected gain of Greedy-TwoLengths on this instance is 1as with probability 1it begins J 1
J blocks J k
s:
s*:
pre-blocks L k

Figure

5: Definitions of blocked and pre-blocked.
at time 0, and with probability 1
rejects job J 0 while also virtually blocking the resource during
[0; 1). This provides a 4-competitive bound on this instance.
By making one minor modification to their algorithm, we are able to provide a 3-competitive
algorithm. In the case that only small jobs exist, we choose to run the job with earliest deadline
with probability 2, thus rejecting the job and virtually scheduling the resource in the remaining3 of the time. We denote this algorithm Greedy-TwoLengths-Modified. Our analysis will
be using a charging scheme which is adapted from that given by Goldman et al. We will be
interested in a fixed instance I and we let oe   denote an optimal schedule for the instance. For a
particular execution of the randomized algorithm Greedy-TwoLengths-Modified on I, we will
let oe denote the schedule produced. For a job J 2 oe, we let J oe denote the time when job J has
started running in oe, and similarly we define J oe   if J 2 oe   .
We begin with the following definitions, diagrammed in Figure 5. We say that a job J i
blocks a job J k 2 oe   if J oe
J oe
. We say that a large job L i 2 oe pre-blocks L k 2 oe   if L i
immediately follows the completion of a small job S in oe and if L oe
1.
For a single execution of the randomized algorithm Greedy-TwoLengths-Modified, we
define the following scheme, mapping charge from those jobs completed in oe to those jobs completed
in oe   .
Assignment Rule 1: If small job S is scheduled in both oe and oe   , S pays 1to itself.
Assignment Rule 2: If small job S 2 oe blocks S 0 2 oe   , S pays 1
2 to S 0 .
Assignment Rule 3: If large job L is scheduled in both oe and oe   , it pays \Deltato itself.
Assignment Rule 4: Large job L 2 oe pays 1
3 to each small job S 2 oe   blocked by L.
Assignment Rule 5: If large job L 2 oe pre-blocks large job L 0 2 oe   , L pays \Deltato L 0 .
Assignment Rule large job L 2 oe blocks large job L
3 to L 0 .
Assignment Rule 7: If L 2 oe has not yet paid out \Delta, the remaining charge is paid to the same
job as specified by Rule 6, if such a job exists.
Lemma 11 For the given charging scheme, a job J i 2 oe pays out at most p i units of charge.
Proof: A small job S 2 oe can pay out at most 1from Rule 1, and at most 1from Rule 2, as S
can block at most one job. Therefore S pays out at most 1 unit.
For a large job L 2 oe, we only need to consider Rules 3-6, as Rule 7 will never cause an
overpayment. Rule 3 can account for payment of \Delta. We claim that Rules 4-6 can account for
combined payment of at most 2\Delta. If L pre-blocks a large job, then it can block at most one other
job. The maximum payout in such a case is when the blocked job is large, in which case \Deltais paid
out by each of Rules 5 and 6. If L does not pre-block a large job, it might block up to d\Deltae other
jobs, only one of which can be large. In such a situation,
3 is paid out by Rule 4 and \Deltais paid out by Rule 6.
In considering the amount of charge collected by a particular job J 2 oe   , we must keep in mind
that the charging scheme is a random process based on a particular execution of the randomized
algorithm which leads to schedule oe. We can, however let charge(J) be a random variable which
represents the amount of charge which J collects. We can then let E[charge(J)] denote the expected
value of the collected charge, where the expectation is taken over the randomness of the algorithm.
Lemma 12 For a job J
3 .
Proof: In bounding the expectation taken over all executions, we will partition the set of possible
executions into distinct groups and we will individually analyze the conditional expectation taken
over such a group G of executions. If we are able to show that E G [charge(J i )]  p ifor each such
G, then we can conclude the general bound. Such analysis does not rely on any explicit
knowledge about the relative probability of an execution going to a particular such group G.
We begin by considering a small job S 2 oe   , examining three distinct cases based on
Case S1: Execution in which Q 1 is empty at time t.
As witnessed by the placement of S in oe   , the job has arrived on or before time t and is
otherwise available to run. Since Q 1 is empty, it must be the case that S was removed from
the queue at an earlier time and either scheduled or virtually scheduled based on a coin flip.
At such a point, there was an a priori probability of 2that S would have been scheduled and
thus received 1
2 of charge from Rule 1. Thus E[charge(S)]  2
3 in this case.
Case S2: Execution in which Q 1 is not empty at time t, and a large job L begins to run at some
point during the interval
In this case L is blocking S, and so S will receive 1
3 from Rule 4.
Case S3: Execution in which Q 1 is not empty at time t, and a small job S i receives the consideration
of a coin flip at some point during the interval
will be scheduled with probability 2and thus block S. Rule 2 would apply in this case,
and thus E[charge(S)]  2
3 .
We note that the above three cases indeed form a disjoint partition of the possible executions. In
particular, if Q 1 is not empty at time t, then either a large job is running, a small job is running
or a small job is virtually scheduled.
We next consider a large job L 2 oe   , examining three distinct cases based on
Case L1: Execution in which Q \Delta is empty at time t.
As witnessed by the placement of L in oe   , the job has arrived on or before time t and is
otherwise available to run. Since Q \Delta is empty, it must be the case that L was removed from
the queue at an earlier time and scheduled. In this case it receives \Deltabased on Rule 3.
Case L2: Execution in which Q \Delta is not empty at time t, and a large job L i
begins to run at some
point during the interval
In this case L i will be blocking L, and so L will be paid \Delta
3 according to Rule 6.
Case L3: Execution in which Q \Delta is not empty at time t, and a small job S receives the consideration
of a coin flip at some point during the interval
Based on the algorithm, S would only be given this consideration at a time when Q \Delta is empty,
yet by time t, Q \Delta is not empty. We let L f denote the first large job which arrives after the
point when S is considered. The significance of L f is that it would be the large job which
gets to run in the case that S were virtually scheduled. We further consider two sub-cases
depending on the deadline of L f .
Case L3a:
We know that if S is virtually scheduled, then L f gains the use of the resource when it
arrives during We see that L f
blocks L which begins at time t in oe   and thus
receives payment from Rules 6-7.
We claim that L will receive \Delta from L f
. As L uses the resource in oe   over the entire
interval [t; t+ \Delta), it cannot be the case that L f blocks any small jobs, and so no payment
is made through Rule 4. As L f
begins after S is virtually scheduled and thus after an
idle period, it cannot technically pre-block any job based on our definition, thus L f
makes no payment through Rule 5. Finally, we need only consider Rule 3. If it happens
that L f
L, then in any event, all \Delta charge is received by L. Alternatively if L f
we claim that L f cannot possibly be scheduled in oe   . It arrives strictly after time
and has a deadline strictly less than t Therefore it cannot fit in oe   either before
or after job L which we already know runs throughout the interval [t; t \Delta).
Since S is virtually scheduled with probability 1and in this case, L receives \Delta units, we
can be sure that the expected charge received by L for this case is at least \Delta
3 .
Case L3b: d f  t
Although we do not know whether S becomes scheduled or virtually scheduled, we claim
that L will receive \Delta
3 units of charge in either case. If S becomes virtually scheduled,
then L f will gain the resource when it arrives during In this case, L f blocks L
and so L receives \Delta
3 from Rule 6.
Alternatively, if S becomes scheduled, we claim that Q \Delta will still be non-empty when S
is completed, and therefore some large job will begin at that time, and such a large job
exactly satisfies the conditions of pre-blocking L. For this reason, L will receive \Deltafrom
Rule 5.
Again, we conclude that these three cases form a disjoint partition of all possible executions. In
particular, if Q \Delta is not empty at time t a large job would begin running or else the resource must
be currently scheduling an appropriate large or small job.
Theorem 13 In the case where jobs have one of two distinct lengths and no notification is required,
Greedy-TwoLengths-Modified is a 3-competitive randomized algorithm.
Proof: This result is a direct consequence of Lemmas 11 and 12. Given a particular instance
I chosen by an oblivious adversary, we can analyze the expected performance of a randomized
algorithm R versus the gain of the optimal schedule for that instance.
Although our charging scheme depends on the outcome of the randomized algorithm, we can
bound the expected amount of charge paid out using Lemma 11, as follows,
E[overall charge paid out]  E[
Lemma 12 provides a bound comparing each job achieved in the optimal schedule to the expected
amount of charge received by those jobs in our scheme. Summing this over all jobs in the optimal
schedule, we see,
gain opt
Finally, we use a simple rule of conservation of units of charge equating the expectations of
charge received and charge paid. This allows us to conclude:
gain opt (I)
E[overall charge paid 3:



--R


Competitive non-preemptive call control
Bandwidth allocation with preemption.
Sharing video on demand.
Symmetric binary B-trees: Data structure and maintenance
On the power of randomization in on-line algorithms
Online Computation and Competitive Analysis.
Introduction to Algorithms.
Efficient online call control algorithms.

Patience is a virtue: The effect of slack on competitiveness for admission control.
Optimization and approximation in deterministic sequencing and scheduling: A survey.
A dichromatic framework for balanced trees.
Scheduling a production line to minimize maximum tardiness.
Competitive snoopy paging.

Online interval scheduling.
Competitive routing of virtual circuits in ATM networks.
Memory versus randomization in on-line algorithms
Amortized efficiency of list update and paging rules.
--TR
Amortized efficiency of list update and paging rules
Introduction to algorithms
Memory versus randomization in on-line algorithms
Bandwidth allocation with preemption
Efficient on-line call control algorithms
Online computation and competitive analysis
Online interval scheduling
Competitive non-preemptive call control
Online scheduling with hard deadlines
Real-Time Systems
admission control;notification;online scheduling;firm deadlines