Go backward to
Go up to
Go forward to
Graham's List Scheduling Algorithm
Given: task graph and processor number.
Find: optimal schedule.
Minimization of total exexecution time.
Polynomial time algorithms:
All tasks take unit time and graph is a forest.
All tasks take unit time and we have two processors.
-complete in general.
Exponential time in worst case.
Goal: good (not optimal) polynomial time scheduling algorithms.
Last modification: November 15, 1996