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 the normal view instead:
scientific article; zbMATH DE number 4076608
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| 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
0.8558230400085449
0 references
0.8362765908241272
0 references
0.8185635209083557
0 references
0.8045656085014343
0 references
0.802005410194397
0 references
