Hardware Reference
In-Depth Information
A simple algorithm that solves this problem was found by Jackson in 1955. It is called
Earliest Due Date
(EDD) and can be expressed by the following rule [Jac55]:
Theorem 3.1 (Jackson's rule)
Given a set of
n
independent tasks, any algorithm that
executes the tasks in order of nondecreasing deadlines is optimal with respect to min-
imizing the maximum lateness.
Proof.
Jackson's theorem can be proved by a simple interchange argument. Let
σ
be
a schedule produced by any algorithm
A
.If
A
is different than EDD, then there exist
two tasks
J
a
d
b
, such that
J
b
immediately precedes
J
a
in
σ
.Now,
let
σ
be a schedule obtained from
σ
by exchanging
J
a
with
J
b
, so that
J
a
immediately
precedes
J
b
and
J
b
, with
d
a
≤
in
σ
.
As illustrated in Figure 3.1, interchanging the position of
J
a
and
J
b
in
σ
cannot in-
crease the maximum lateness. In fact, the maximum lateness between
J
a
and
J
b
in
σ
d
a
, whereas the maximum lateness between
J
a
and
J
b
in
σ
can
be written as
L
max
(
a, b
)=
max
(
L
a
,L
b
). Two cases must be considered:
is
L
max
(
a, b
)=
f
a
−
1. If
L
a
≥
L
b
, then
L
max
(
a, b
)=
f
a
−
d
a
, and, since
f
a
<f
a
,wehave
L
max
(
a, b
)
<
L
max
(
a, b
).
2. If
L
a
≤
L
b
, then
L
max
(
a, b
)=
f
b
−
d
b
=
f
a
−
d
b
, and, since
d
a
<d
b
,wehave
L
max
(
a, b
)
<L
max
(
a, b
).
Since, in both cases,
L
max
(
a, b
)
<L
max
(
a, b
), we can conclude that interchanging
J
a
and
J
b
in
σ
cannot increase the maximum lateness of the task set. By a finite number
of such transpositions,
σ
can be transformed in
σ
EDD
and, since in each transposition
the maximum lateness cannot increase,
σ
EDD
is optimal.
The complexity required by Jackson's algorithm to build the optimal schedule is due
to the procedure that sorts the tasks by increasing deadlines. Hence, if the task set
consists of
n
tasks, the complexity of the EDD algorithm is
O
(
n
log
n
).
Search WWH ::
Custom Search