TU Berlin

Combinatorial Optimization & Graph Algorithms group (COGA)1999

COGA 5-Wheel

Page Content

to Navigation

Preprints 1999

Scheduling Series-Parallel Orders Subject to 0/1-Communication Delays
Citation key Report-611-1998
Author Rolf H. Möhring and Markus W. Schäffter
Year 1998
Number 611
Note Appeared in Parallel Computing 25 (1999) 23-40
Institution Technische Universität Berlin, Institut für Mathematik
Abstract 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.
Bibtex Type of Publication Preprint
Link to publication Download Bibtex entry


Quick Access

Schnellnavigation zur Seite über Nummerneingabe