A Simple Approximation Algorithm for Scheduling Forests with Unit Processing Times and Zero-One Communication Delays

Rolf H. Möhring and Markus W. Schäffter

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},p_j=1,c_ij&;{0,1}|C_max 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]