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.
- Multiprocessor tasks
- Prespecified processor allocations
- Total completion time
- Release dates
- Precedence constraints
Hoogeveen, J. A., van de Velde, S. L., & Veltman, B. (1995). Complexity of scheduling multiprocessor tasks with prespecified processor allocations. Discrete applied mathematics, 55(3), 259-272. https://doi.org/10.1016/0166-218X(94)90012-4