We investigate the computational complexity of scheduling multiprocessor tasks with prespecified processor allocations. We consider two criteria: minimizing schedule length and minimizing the sum of the task completion times. In addition, we investigate the complexity of problems when precedence constraints or release dates are involved.

, , , , ,
doi.org/10.1016/0166-218X(94)90012-4, hdl.handle.net/1765/12352
ERIM Article Series (EAS)
Discrete Applied Mathematics
Erasmus Research Institute of Management

Hoogeveen, H., van de Velde, S., & Veltman, B. (1994). Complexity of scheduling multiprocessor tasks with prespecified processor allocations. Discrete Applied Mathematics, 55(3), 259–272. doi:10.1016/0166-218X(94)90012-4