Scheduling multiprocessor tasks on three dedicated processors (Q1197982)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Scheduling multiprocessor tasks on three dedicated processors |
scientific article |
Statements
Scheduling multiprocessor tasks on three dedicated processors (English)
0 references
16 January 1993
0 references
The authors analyse the problem of scheduling a set of uni- and duo- processor tasks on three dedicated processors. The objective of the problem is to find a schedule with minimum length. The general problem is shown to be strongly NP-hard, which strengthens the best known complexity result. Finally, they present polynomially solvable special cases as well as an approximation algorithm for some hard subproblems.
0 references
parallel processing
0 references
polynomial algorithm
0 references
NP-complete
0 references
resource allocation
0 references
scheduling
0 references
