4.

5 JOBSEQUENCING WITH DEADLINES

We are given a set of n jobs, Associated with job i is an integer deadline
>0
d, and a profit p, > 0. For any job ithe profit p;is earned iff the job is
completed by its deadline. To complete a job, one has to process the job on
machine for one unit of time. Only one machine is available for pro cessing
jobs. A feasible solution for this problem is a subset
J of jobs such that each

job in this subset can be completed by its deadline.

The value of a feasible
solution J isthe sum of the profits of the jobs in J, or iep;.
An optimal
Here again, since the
solution is a feasible solution with maximum value.
subset paradigm.
problem involves theidentification of a subset, it fits the

Example 4.5 Let n = 4, (p1,P2, P3,PA) =(100, 10, 15, 27) and (d,d2, d, d)=
(2,1, 2,1). The feasible solutions and their values are:
 CHAPTER 4. THE GREEDY
METHOD
228
feasible processing
value
solution sequence
110
1 (1, 2) 2, 1
115
2 (1, 3) 1, 3or 3, 1
127
(1, 4) 4, 1
3. 25
(2,3) 2, 3 42
(3, 4)
4, 3
100
1
(1)
2 10
(2)
3 15
8 (3)
4 27
9. (4)
only jobs I and4 are processed amd
Solution3is optimal. In this solution
in the order job follomod
the value is 127. These jobs must be processed
4

begins at time zero and that of ioh 1

by job 1. Thus the processing of job 4
iscompleted at time 2.
To formulate a greedy algorithm to obtain an optimal
solution, we must

formulate an optimization measure todetermine

how the next job is chosen.

As a first attempt we can choose the objective function EJ P; as our op

timization measure. Using this measure, the next job to include is the one
that increases EJP; the most, subject to the constraint that the resulting
J is a feasible solution. This requires us to consider jobs in nonincreasing
order of the p;'[Link] us apply this criterion to the data of Example 4.5. We
begin with J = 0and iel Pi =[Link] l is added to J
as it has the largest
profit and J = {1} is a feasible solution. Next, job 4 is considered. The
solution J = {1,4} is also feasible. Next, job 3
is considered and discardeul
as J={1,3, 4} is not feasible. Finally, job 2 is considered for inclusion

ntu
J. It is discarded as J = left with
= {1,2, 4} is not feasible. Hence, we are
the solution J = {1, 4} with value 127. This is the optimal solution for the
given problem instance. Theorem 4.5 just
proves that the greedy algorithm
described always obtains
an optimal solution to this sequencing problem.
Before whether
atternpting the proof, let us see how we
a given
can determine
J is a feasible
solution. One obvious way is to all possible
try out
permutations of the jobsin J and be pro
check whether the jobs in J can
cessed in any one of the
these permutations without violating do,
deadlines. For a given (sequences) to
permutation o = i, this is easy
Ifq > d
since the earliest i2, 31 k
time job ig; 1 <
then using o, at
least job ig will
q<k, will bee completed is q. 1
However.
if J= i, this
not be comnpleted by its deadline.
requires checking i!
t

permutations. Actually, the thejobs

feasibility
of a set
J can be
in J. This determined by checking only of

permutation is any one permutation jobs

are

ordered in one of the permutations in which

nondecreasing order of
deadlines.
Theorem 4.4 Let J be a
of jobs in
J such
the jobs in J can SSd.
set ofk
that d,, < dig
be
jobs and o

processed in the
Then J is a feasible
order o without violating any
permutation
solution
deadline
i
 JOB SEQUENCINGG WITH DEADLINES
4.5. 229

Proof:
violating
Clearly,, ifthe
any deadline,
jobs in
then J
JJ

is
can
a
feasible solution. So,
be
processed in the order o
without
we have only to
VIO Jis feasible, then o
represents a possible order in which
the
can be processed. If J is ffeasible, then there exists
jobs
ch that de, 24, lSqsk. Assume o'[Link] let
orryTk
bethe
a least index
ench that re #l Let ro la Clearly, b > a. In o we can interchange
and
represents
rh. Since
an order
dya2 drh the resulting permutation
in which the jobs can be processed without violating
osj,S2,**8
adeadline. Continuing in this way, d' can be transformed into o withont
violating any deadline. Hence, thetheorem is proved.

Theorem 4.4is true even if the jolbs have different processing times t,20
(see the exercises).

Theorem 4.5 The greedy method described above always obtains an opti
mal solution to the job sequencing problem.

Proof: Let(P,d), 1<isn,define any instance of the job sequencing

problem. Let I be the setof jobs selected
by the greedy method. Let J
an optimal
of jobs in solution. We now show that both I and J
be the set
have the same profit values and so I is also optimal. We can
assume IJ
as otherwise we have nothing to prove. Note that if JCI,
then J cannot

be optimal. Also, the case IcJis

ruled out by the greedy method. So,

there exist jobsa and b such that

ae
I, a J, bE J, and bI
Let a be
I and a J. It follows from the greedy
a highest-profit job
such that a e
are in J but not in I. To see this,
ethod that pa > P for all jobs b that job
method would consider job b before
ote that if p, > pa, then the greedy
a and include it into I. Let
S and S,for I and J
respectively
feasible schedules
Now,consider from t to + l in
I and ei e J. Let i bescheduled
be
O
a job such

and to
eduled in
that
'+1
in

[.+
i

1l
S,. If then we can interchange the job
t<t,
in S,with i. If no job
is scheduled in
(if any)

IE
(,+
l in
t
.
is also feasible.
[.+1. The resulting schedule can obtain
s moved to in S,. In this way,
we
then a similar transformation can be made to andJare
that all jobscommon
property which
schedules S and S with the
interval as a t l in S in
the
scheduled at the Bame time. Consider (if any) schedule
b be the job
the job a (defined above) is scheduled. Let Scheduling a rom
choice of a, Pa
P
the or job set
in S,in From a feasibleschelulehat ofJ and
JT in S
this interval,
and discarding
a) Clearly, J'
job b gives us
has a profit value
no less than

differs from I in one less job

than / does. just cdescribed,Jcan be Erana
By Tepeatedly using the
transformation
value.
Solmust be optimal
in proit jusE discssed appears
lormed into I with no decrease
of the
greedy algoritha jobs that
A high-level description an optimal set Jof
constructs
as
Algorithm 4.6. This algorithm
 THE
CHAPTER 4 GREEDY
METHOD
230

J,n)
Greedy Job(d, deadlioc
1 Algorithm by their
a set of jobs that can be comypleted
2 //0is
3
for i2 to n do

if (all jobs in JUi canthen

be completed
J JUih
8 by their deadlines)

10 )
Algorithm 4.6 High-level description of job sequencing algorithm

can be processed by their due times. The selected jobs can be processedin
the order given by Theorem 4.4.
Now, us see how to represent the set J and how to carry out the test
let

of lines 7 and 8 in Algorithm 4.6. Theorem 4.4 tells us how to determine

whether all jobs in JU
f} can be completed by their deadlines. We al
avoid sorting the jobs in J each time by keeping the
jobs in J ordered
deadlines. We can use an array d1 :
n]to store the deadlines of the jou
inthe order of their p-values. The set J itself can
Dy

<<:
be represented by a
dimensional array J1
k such that Jrl, 1 <r<k
are thejobs in
dJsdJ2) dJk] whether J U{i} is feasible, we bave
To test
just to insert i intopreserving the deadline
J that
dJrsr, ordering and then verify
1<rSk+1.
ofa fietitious job 0 with The insertion of i into J is simplified by the use
to be inserted at do) and
position q. then only
=0 = 0. Jo
Note also that if job
s
k are
changed after the
the positions of jobs Ja.
insertion. Hence, it necessary to
veri
only that these
the insertion.
jobs (andalso
The algorithm
job ) is
do not violate their deadlines following
JS that results
(Algorithm 4.7). The fron this discussion is funetion
such that Py2
d of job i P22
s at least 1.
algorithm assumes that
Pu: Further it the jobs are already
the
sorted

nland
deadline
by its Note that no assumes that finished
deadline.
the greedy Theoremn 4.6
job
proves that JS
with di can ever be <l o
strategy is a correct lmplementation
Theorem 4.6
Function JS is
nethod deseribed a
above correct
implementation of the Breedy-based

Proof: Since
greedy solution dt21,
As
the job with the beinline
the
the jobs largest willalways
are in P
s,
order of the P
noninereasing
 SEQUENCING WITH DEADLINES
45. JOB 231

1 Algorithm JS(d, j. n)
/ dll> 1, 1Sisn are the deadlines, n >1. The jobs
are ordered such that p|l| p2)22 pln]. J
/ is the ith job in the optimal solution, 1<i<k.
I Also, at termination d|J||sdJi+1J), 1<i< k.
do) := Jo :=0; // Initialize.
Ji:=l;//Include job 1.

k=1;
10 for i := 2 to n do
{
12 // Consider jobs in nonincreasing order of pli]. Find
13 //position for i and check feasibility of insertion.
14 r:= k;
15 while ((d|J(r|] > dil) and (dJrl]l r)) do r :=r-1;
16 if ((dJ(rl] < di) and >
(di] r))then
17 {
18 //Insert i into J. +
19 for q := k to (r + 1) step -1 do Jg 1] :=Jgl:
20 Jr+1:=;k:=k+ 1;
21
}
22
23 return k;
24 }

time jobs with dead

Algorithm 4.7 Greedy algorithm for sequencing unit
lines and
profits

of line
8in The for loop
Pi:
with largest method
I0 Algorithm 4.7 inchudes the job order required by the greedysolution
consicders the
remaining jobs in the in the
described of jobs already included then J is

8 earlier. At all times, the set included,

the set alreadyfor easy application
such
maintained in
J. If JO,1<is k, is
This allows the
that
dJ]s dJ|i+ 1<i<k. being considered,
The
WVhen jobi
of
the 1||, is
4.4. has to be inserted.
Jthisjob
feasibility test of Theorem Let w
while in position
1.

loop of line 15 determines where into

se of a included
iIsertion fjob iis
besuch fctitious job 0 (line 7) allows easy w <qsk. up in J
one position
ito J, that dJwl] < di and |Jall>dil, dJ to be moved feasibility
then k. have a move retains
 CHAPTER 4. THE GREEDY
METHOD 4.

232
+ di) > This is ve

dJa||4. wed
w 1 iff w.
at position in
i can be inserted loop if
on exit from the while
addition, ne
16(note r =
line from these observations. b
of JS follows
Thecorrectness to
in terms its of which
two possibleparameters t}
For JS there are
n, the number
of jobs, and s, thecomplexity
numnber
We can use of

can be measured. loop of line 15in Algorithm 4.7i8

the solution J. The while sl

jobsincluded in iteration takes O(1) time.

If the
k times. Each
conditional
iterated at most
executed. These
true, then 19 and 20 are lines
of line l6 is
lines require

insert job Hence, the total time for each iteration of

(k-r) time to
n-1
i.
1 times. If
is K)! This loop is iterated sis
the for loop of line 10 f
i the number of jobs in the final soluti
the fnal value of k, that is; s.

time needed by algorithm JS is (sn). Since s

<n tha
then the total

worst-case time, as a function of n alone is (n). If we consider the ich t

set p; = d, =nit1, 1<i<n, then algorithmn JS takes (n²) time

(n).
t

to determine J. Hence,the worst-case computing time for JS is In

te

addition to the space needed for d, JS needs amount of space for J. (s) tl

Note that the profit values are not needed by JS. It is sufficientto know that t

Pi 2 P+1, 1<i< n.
The computing time of JS can be reduced from O(n) to nearly O(n) E
by using the set union and find algorithms (see Section 2.5) and a
disjoint

different method to determine the feasibility of a partial solution. If J a is

feasible subset of jobs, then we can determine the processing times for each

of the jobs using the rule: if job i hasn't been assigned a processing time.
then assign it to the slot a-
1,al, where a is the largest integer r sle
that 1 <r<d, and the slot la - 1, al is free, This rule simply delays the
W
processing of job i as much as possible. Consequently,
when J is being built
up job by job, jobs already in J do not have to
be moved from their assigeu
slotsto accommodate the new job. If for
the new iob being considered t E
is no a as defined
above, then cannot be included in J. The proof of the
it
validity of this
statement is left as an
exercise.

Example 4.6 Let n = 5,

=(2,2, 1,3, 3). Using the (P1,Pps) = (20,15, 10, 5,1) and
above feasibility rule, we have

assigned slots proit

job considered action
DOne
{1}
1,2) assign to 1, 2 20
{1, 2} |0,1|, [1,2) 2 to 0, 1 3
assign
{1, 2)
|0,1,(1,2] 3 cannot fit: reject 35
{1, 2, 4} 4 3
0,1],(1,2), (2,3) assign to
(2,
5
Theoptimal reject
solution is J = {1,2,4} with a profit of 40.
 JOB SEQUENCING IWTTHDEADLINES
233
e
Since there are only n jobs and each
S job
takes one
only to consider the unit of time, it
bmin {n, max
time slots (-1,),
One way to implement the 1<i< b,
such that
is

Dition thetine slots |-

1,, 1sisb,
above scheduling rule is
into sets. We HSe ito
time slots 1, PoT any slot 1, let n, bethe largest represent
andslot n, is free. To avoid end integer such that
conditions,we introduce a fctitious
-l.0) which is always free. Two slots
i and j are in the same set
S Clearly, if i and j, i<j,are if
in the same set, then i,
in ihe sameset. Associated i+l,i+2....j
with each set k of slots is a value f(k).
L)D. Then
for all slots i in set k. Using the set
representation of Section 2.5.
ench set is represented as a tree. The root node
identifies the set. The
hunction fisdefined only for root nodes. Initially, all
slots are free and we
have b+ l sets corresponding to the b +
1 slotsi -1,i], 0 <i <b. At this
time f(i)= 0 i, <i<b. We use p(i) to link slot i into its set tree. With
the conventions for theunion and find algorithms of Section 2.5,
p(i) =-1,
0<i<b initially. If a job with deadline d is tobe scheduled, then we need
to find the root of the tree containing theslot minfn, d}. If this root is
j.
then fG) is the nearest free slot., provided fG) 0. Having used this slot.
the set with root j
should be combined with the set containing slot fj) - L.

Example 4.7 The trees defined by the p(i)'s for the first three iterations
n Example 4.6 are shown in Figure 4.5.

algorithm appears as FJS (Algorithm 4.8). Its computing time

he last

eadily observed to be O(no(2n.n)) (recall that a(2n, n) is the inverse

of
Ackermann function defined in Section 2.5). It needs
an additional 2n
Words of
space for f and p.