Go backward to
Coffman-Graham Algorithm
Go up to
Top
Go forward to
Deadlock
Coffman-Graham Algorithm
Find: task list for Graham's algorithm.
Algorithm:
Choose
$T$
_{k}
with
$S(T$
_{k}
)=0 and let
$$
alpha
(T
_{k}
) be 1.
For
$i\; <-2$
to
$n$
do
Let
$R$
be the set of unlabeled tasks with no unlabeled successors.
Let
$T*$
be the task in
$R$
such that
$N(T*)$
is lexicographically smaller than
$N(T)$
for all
$T$
in
$R$
.
Let
$$
alpha
(T
^{*}
) <-i.
Construct
$L\; =\; (U$
_{n}
, U
_{n-1}
, ..., U
_{2}
, U
_{1}
) such that
$$
alpha
(U
_{i}
) = i.
Theorem:
$w/w$
_{0}
<=2 - 2/p
$w$
length of constructed schedule,
$w$
_{0}
length of optimal schedule,
$p\; >\; 1$
processor number.
Collary: schedule optimal for
$p=2$
.
See
Quinn
, Figure 5-18.
Author:
Wolfgang Schreiner
Last modification: November 15, 1996