Computational complexity of some scheduling problems with multiprocessor tasks

Publisher:
Elsevier
Publication Type:
Journal Article
Citation:
Discrete Optimisation, 2005, 2 pp. 391 - 408
Issue Date:
2005-01
Full metadata record
Files in This Item:
Filename Description Size
Thumbnail2005002885.pdf1.06 MB
Adobe PDF
The paper is concerned with scheduling problems with multiprocessor tasks and presets conditions under which such problems can be solved inpolynomial time. The application of these conditions is illutrated by two quite general scheduling problems. These results are complemented by a proof of NP-hardness of the problem witha UET task system, two parallel processors, the criterion of total completion time, and precednece constraints in the form of out-trees
Please use this identifier to cite or link to this item: