Go backward to
Graham's List Scheduling Algorithm
Go up to
Top
Go forward to
Coffman-Graham Algorithm
Coffman-Graham Algorithm
What is best way to construct prioritized list?
Assume all tasks execute the
same
amount of time.
$$
mu
(T
_{i}
) = 1.
Definitions:
If
$T$
_{i}
< T
_{j}
, then
$T$
_{j}
is an
immediate successor
of
$T$
_{i}
.
Let
$S(T$
_{i}
) be all immediate successors of
$T$
_{i}
.
Let
$$
alpha
(T) be an integer label assigned to
$T$
.
Let
$N(T$
_{i}
) be the ordered sequence of integers formed from the set
$\{$
alpha
(T') | T'
in
S(T) }.
Author:
Wolfgang Schreiner
Last modification: November 15, 1996