Scheduling tree-structured tasks with restricted execution times
- 29 July 1988
- journal article
- Published by Elsevier BV in Information Processing Letters
- Vol. 28 (4), 183-188
- https://doi.org/10.1016/0020-0190(88)90206-2
Abstract
In this article we show that scheduling a tree-structured task system with two execution times in order to minimize the schedule length is strongly NP-hard for an arbitrary number of processors. If the execution times are powers of some integer r>1, then the problem is NP-hard even for two processors.Keywords
This publication has 5 references indexed in Scilit:
- Bin packing with divisible item sizesJournal of Complexity, 1987
- On Scheduling Independent Tasks with Restricted Execution TimesOperations Research, 1982
- NP-complete scheduling problemsJournal of Computer and System Sciences, 1975
- Optimal scheduling for two-processor systemsActa Informatica, 1972
- Parallel Sequencing and Assembly Line ProblemsOperations Research, 1961