Go backward to Optimal Schedules Go up to Top Go forward to Coffman-Graham Algorithm

Graham's List Scheduling Algorithm

• Given: list of tasks ordered by priority.
  • Tasks $L\; =\; (T$₁, T₂, ..., 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)