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 -