Go backward to
Deterministic Models
Go up to
Top
Go forward to
Graham's List Scheduling Algorithm
Optimal Schedules
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.
NP
-complete in general.
Exponential time in worst case.
Goal: good (not optimal) polynomial time scheduling algorithms.
Author:
Wolfgang Schreiner
Last modification: November 15, 1996