TY - JOUR

T1 - A very difficult scheduling problem with communication delays

AU - Hoogeveen, J.A.

AU - Woeginger, G.J.

PY - 2001

Y1 - 2001

N2 - A set of unit-time tasks has to be processed on an unrestricted number of processors subject to precedence constraints and unit-time communication delays such that the makespan is minimized. What is the smallest number m* such that increasing the number of processors beyond m* cannot decrease the makespan any more? We prove that answering this problem is complete for the complexity class . Hence, the problem is at least as difficult as all the problems in and at least as difficult as all the problems in , and unless some complexity classes collapse, it is even more difficult than all these problems. This answers a question raised by Ivan Rival.

AB - A set of unit-time tasks has to be processed on an unrestricted number of processors subject to precedence constraints and unit-time communication delays such that the makespan is minimized. What is the smallest number m* such that increasing the number of processors beyond m* cannot decrease the makespan any more? We prove that answering this problem is complete for the complexity class . Hence, the problem is at least as difficult as all the problems in and at least as difficult as all the problems in , and unless some complexity classes collapse, it is even more difficult than all these problems. This answers a question raised by Ivan Rival.

U2 - 10.1016/S0167-6377(01)00103-1

DO - 10.1016/S0167-6377(01)00103-1

M3 - Article

VL - 29

SP - 241

EP - 245

JO - Operations Research Letters

JF - Operations Research Letters

SN - 0167-6377

IS - 5

ER -