TY - BOOK
T1 - Three, four, five, six or the complexity of scheduling with communication delays
AU - Hoogeveen, J.A.
AU - Lenstra, J.K.
AU - Veltman, B.
PY - 1993
Y1 - 1993
N2 - A set of unit·time tasks has to be processed on identical parallel processors subject to precedence constraints and unit·time communication delays; doesthere exist aschedule of length at most d? The problem has two variants, depending on whether the number of processors is restrictively small or not. For the first variant the question can be answered in polynomial time for d=3 and is NP-complete for d=4. The second 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.
Key Words & Phrases: Identical parallel processors, precedence constraints, communication delays, makespan, complexity, approximation.
AB - A set of unit·time tasks has to be processed on identical parallel processors subject to precedence constraints and unit·time communication delays; doesthere exist aschedule of length at most d? The problem has two variants, depending on whether the number of processors is restrictively small or not. For the first variant the question can be answered in polynomial time for d=3 and is NP-complete for d=4. The second 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.
Key Words & Phrases: Identical parallel processors, precedence constraints, communication delays, makespan, complexity, approximation.
M3 - Report
T3 - Memorandum COSOR
BT - Three, four, five, six or the complexity of scheduling with communication delays
PB - Technische Universiteit Eindhoven
CY - Eindhoven
ER -