Inhalt des Dokuments
Preprint 611-1998
Combinatorial Optimization & Graph Algorithms group (COGA-Preprints)- Title
- Scheduling Series-Parallel Orders Subject to 0/1-Communication Delays
- Authors
- Publication
- Appeared in Parallel Computing 25 (1999) 23-40
- Classification
-
MSC: primary: 90C27 Combinatorial optimization secondary: 90B35 Scheduling theory, deterministic - Keywords
-
scheduling, communication delays, series-parallel order, approximation algorithm
- Abstract
-
We consider the problem P}&;| prec},cij&;{0,1}|κ 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 O(n+r) and O(n3), respectively.On the other hand, both problems are shown to be NP-hard in the same model for 0/1-communication delays.
- Source
Zusatzinformationen / Extras
Direktzugang
Schnellnavigation zur Seite über Nummerneingabe