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.
