Computational complexity of some scheduling problems with multiprocessor tasks
- Publication Type:
- Journal Article
- Discrete Optimization, 2005, 2 (4), pp. 391 - 408
- Issue Date:
The paper is concerned with scheduling problems with multiprocessor tasks and presents conditions under which such problems can be solved in polynomial time. The application of these conditions is illustrated by two quite general scheduling problems. These results are complemented by a proof of NP-hardness of the problem with a UET task system, two parallel processors, the criterion of total completion time, and precedence constraints in the form of out-trees. © 2005 Elsevier B.V. All rights reserved.
Please use this identifier to cite or link to this item: