direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Logo der TU Berlin

Inhalt des Dokuments

Preprint 611-1998

Combinatorial Optimization & Graph Algorithms group (COGA-Preprints)

Scheduling Series-Parallel Orders Subject to 0/1-Communication Delays
Appeared in Parallel Computing 25 (1999) 23-40
primary: 90C27 Combinatorial optimization
secondary: 90B35 Scheduling theory, deterministic
scheduling, communication delays, series-parallel order, approximation algorithm
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.
Download as [PDF] [ps.gz]
Title: Source

Zusatzinformationen / Extras


Schnellnavigation zur Seite über Nummerneingabe