Worst case analysis of Lawler's algorithm for scheduling trees with communication delays

This paper is devoted to the analysis of an algorithm proposed by Lawler [Law93] for scheduling unit execution times trees on m identical processors in the presence of communi-cation delays. Lawler proved that a schedule computed by his algorithm exceeds an optimal solution by no more than (m 2) time units. We improve this bound by a factor of 2 and propose a family of trees which reaches it for any number of processors.