Precedence constrained scheduling in (2−73p+1)⋅optimal

摘要

We present a polynomial time approximation algorithm for unit time precedence constrained scheduling. Our algorithm guarantees schedules which are at most (2−73p+1) factor as long as the optimal, where p>3 is the number of processors. This improves upon a long standing bound of (2−2p) due to Coffman and Graham.