direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Logo der TU Berlin

Inhalt des Dokuments

Preprint 506-1996

Combinatorial Optimization & Graph Algorithms group (COGA-Preprints)

A Simple Approximation Algorithm for Scheduling Forests with Unit Processing Times and Zero-One Communication Delays
Integrated into Scheduling series-parallel orders subject to 0/1 communication delays, Parallel Computing (1999) 23-40
not available
not available
In the last few years, scheduling jobs due to communication delays has received a great deal of attention. We consider the problem of scheduling forests due to unit processing times and zero-one communication delays and focus on the approximation algorithm of Hanen and Munier and on the algorithm of Guinand, Rapine and Trystram. These algorithms and their analysis are quite complex. In contrast, we present a very simple list scheduling algorithm for the problem P| prec=tree},pj=1,cij&;{0,1}|Cmax of scheduling trees subject to unit processing times and zero-one communication delays. For sufficiently many machines, e.g. `mgeq |V|`, the resulting schedule is optimal. For a restricted number of machines, the presented algorithm has the same absolute worst case performance as the algorithm of Guinand, Rapine and Trystram: m-1}{2}. It's relative worst case performance ratio turns out to be bounded by left(2- 1}{m} ight) even for arbitrary processing times. This simplifies an argument by Hanen and Munier for the case that an optimal schedule on an infinite number of machines can be constructed.
Download as [ps.gz]
Title: Source

Zusatzinformationen / Extras


Schnellnavigation zur Seite über Nummerneingabe