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.
Original language | English (US) |
---|---|
Pages (from-to) | 183-188 |
Number of pages | 6 |
Journal | Information Processing Letters |
Volume | 28 |
Issue number | 4 |
DOIs | |
State | Published - Jul 29 1988 |
All Science Journal Classification (ASJC) codes
- Computational Theory and Mathematics