Precedence constrained scheduling in (2-7/3p+1) . optimal
We present a polynomial time approximation algorithm for unit time precedence constrained scheduling. Our algorithm guarantees schedules which are at most (2 - 7/3p +1) factor as long as the optimal, where p > 3 is the number of processors. This improves upon a long standing bound of (2 - 2/p) due to Coffman and Graham. (C) 2008 Elsevier Inc. All rights reserved.
precedence constrained scheduling approximation algorithm deadline