Complexity of scheduling multiprocessor tasks with prespecified processor allocations
January 1994
Article
volume 55, issue 3 pp 259-272.
This publication is part of collection
| Related Files |
|---|
View PDF Version
(ComplexityofScheduling_1994.pdf, 0.9MB) |
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.
Keywords
- total completion time
- makespan
- multiprocessor tasks
- precedence constraints
- prespecified processor allocations
- release dates
Automatically Extracted Terms
- problem
- partition
- schedule
- processing
- completion time
- processor
- instance
- completion
- sense
- np-hard
- proof
- number
- 3- partition
- length
- scheduling
- processing time
- precedence constraints
- theorem
- complexity
- scheduling multiprocessor tasks
