Go backward to
Optimal Schedules
Go up to
Top
Go forward to
Coffman-Graham Algorithm
Graham's List Scheduling Algorithm
Heuristic algorithm.
Given: list of tasks ordered by priority.
Tasks
$L\; =\; (T$
_{1}
, T
_{2}
, ..., T
_{n}
).
Precedence relation
$<$
.
Time
$$
mu
: T ->[0,
infinity
].
Find: a schedule.
Algorithm: When processor has no work to do, execute first ready task in
$L$
.
Task whose predecessors have completed execution.
Execution time may
increase
when
Number of processors
increases
.
Execution time of some task
decreases
.
Some precedence constraint is
removed
.
(see
Quinn
, Figure 5-17)
Author:
Wolfgang Schreiner
Last modification: November 15, 1996