Scheduling UET task systems with concurrency on two parallel identical processors

Autor(en): Brucker, P
Knust, S 
Roper, D
Zinder, Y
Stichwörter: approximation algorithm; complexity; concurrency; identical parallel processors; Mathematics; Mathematics, Applied; MULTIPROCESSOR TASKS; Operations Research & Management Science; scheduling; unit execution time tasks
Erscheinungsdatum: 2000
Herausgeber: PHYSICA-VERLAG GMBH & CO
Journal: MATHEMATICAL METHODS OF OPERATIONS RESEARCH
Volumen: 52
Ausgabe: 3
Startseite: 369
Seitenende: 387
Zusammenfassung: 
Problems with unit execution time tasks and two identical parallel processors have received a great deal of attention in scheduling theory. In contrast to the conventional models, where each task requires only one processor, we consider a situation when a task may require both processors simultaneously. For problems without precedence constraints we present several polynomial time algorithms which complement recent results of Lee and Cai. We also show that the introduction of precedence constraints leads to NP-hardness results for maximum lateness and mean flow time objective functions. For the maximum lateness problem, a family of algorithms, based upon the idea of modified due dates, is considered. The worst case behaviour of these algorithms is analysed, and it is shown that the same upper bound is tight for each algorithm of this family.
ISSN: 14322994
DOI: 10.1007/s001860000089

Show full item record

Page view(s)

4
Last Week
0
Last month
1
checked on Apr 17, 2024

Google ScholarTM

Check

Altmetric