Go backward to Coffman-Graham Algorithm Go up to Top Go forward to Deadlock

Coffman-Graham Algorithm

• Find: task list for Graham's algorithm.
• Algorithm:
  1. Choose $T$_k with $S(T$_k)=0 and let $$alpha(T_k) be 1.
  2. For to $n$ do
     1. Let $R$ be the set of unlabeled tasks with no unlabeled successors.
     2. Let $T*$ be the task in $R$ such that $N(T*)$ is lexicographically smaller than $N(T)$ for all $T$ in $R$.
     3. Let $$alpha(T^*) <-i.
  3. Construct $L\; =\; (U$_n, U_n-1, ..., U₂, U₁) such that $$alpha(U_i) = i.
• Theorem: $w/w$₀ <=2 - 2/p
  • $w$ length of constructed schedule, $w$₀ length of optimal schedule, $p\; >\; 1$ processor number.
• Collary: schedule optimal for $p=2$.