3, 4, 5, 6, OR THE COMPLEXITY OF SCHEDULING WITH COMMUNICATION DELAYS

A set of unit-time tasks has to be processed on identical parallel pro cessors subject to precedence constraints and unit-time communication delays; does there exist a schedule of length at most d? The problem h as two variants, depending on whether the number of processors is rest rictively small or not. For the first variant the question can be answ ered in polynomial time for d = 3 and is NP-complete for d = 4. The se cond variant is solvable in polynomial time for d = 5 and NP-complete for d = 6. As a consequence, neither of the corresponding optimization problems has a polynomial approximation scheme, unless P = NP.