Complexity of Scheduling Multiprocessor Tasks with Prespecified ProcessorAllocations

摘要

The authors investigate the computational complexity of scheduling multiprocessortasks with prespecified processor allocations. They consider two criteria: minimizing schedule length and minimizing the sum of the task completion times. In addition, they investigate the complexity of problems when precedence constraints or release dates are involved.