Abstract
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.
Original language | English |
---|---|
Pages (from-to) | 241-245 |
Journal | Operations Research Letters |
Volume | 29 |
Issue number | 5 |
DOIs | |
Publication status | Published - 2001 |