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.

makespan, multiprocessor tasks, precedence constraints, prespecified processor allocations, release dates, total completion time
dx.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, J.A, van de Velde, S.L, & 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