Scheduling multiprocessor tasks on three dedicated processors (Q1197982): Difference between revisions
From MaRDI portal
Set profile property. |
ReferenceBot (talk | contribs) Changed an Item |
||
Property / cites work | |||
Property / cites work: Scheduling Multiprocessor Tasks to Minimize Schedule Length / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Complexity of Scheduling Parallel Task Systems / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: `` Strong '' NP-Completeness Results / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The complexity of scheduling independent two-processor tasks on dedicated processors / rank | |||
Normal rank |
Revision as of 15:34, 16 May 2024
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