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:
  1. All tasks take unit time and graph is a forest.
  2. All tasks take unit time and we have two processors.
• NP-complete in general.
  • Exponential time in worst case.