direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Preprints 1998

Scheduling Series-Parallel Orders Subject to 0/1-Communication Delays
Zitatschlüssel Report-611-1998
Autor Rolf H. Möhring and Markus W. Schäffter
Jahr 1998
Nummer 611
Notiz Appeared in Parallel Computing 25 (1999) 23-40
Institution Technische Universität Berlin, Institut für Mathematik
Zusammenfassung We consider the problem $\textrmP\infty|\textrmprec,\,c_ij\in\0,1\|\kappa$ of scheduling jobs with arbitrary processing times on sufficiently many parallel processors subject to series-parallel precedence constraints and 0/1-communication delays in order to minimize a regular performance measure κ. Such schedules without processor restrictions are used for generating approximate solutions for a restricted number of processors. For unit time communication delays we derive polynomial algorithms to construct optimal schedules when the performance measure κ is the makespan or the average weighted completion time. For $n$ jobs and $r$ precedence constraints, the run times of these algorithms are $Øh(n+r)$ and $Øh(n^3)$, respectively. On the other hand, both problems are shown to be \NP–hard in the same model for 0/1-communication delays.
Typ der Publikation Preprint
Link zur Publikation Download Bibtex Eintrag