Scheduling tree-structured tasks with restricted execution times (Q1111371)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Scheduling tree-structured tasks with restricted execution times |
scientific article; zbMATH DE number 4076608
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Scheduling tree-structured tasks with restricted execution times |
scientific article; zbMATH DE number 4076608 |
Statements
Scheduling tree-structured tasks with restricted execution times (English)
0 references
1988
0 references
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.
0 references
NP-completeness
0 references
NP-hardness
0 references
multiprocessor scheduling
0 references
tree-structured task system
0 references
schedule length
0 references
