Scheduling rooted forests with communication delays

We show that a greedy algorithm for scheduling unit time jobs on two machines with unit communication delays produces an optimal schedule when the precedence constraints are given by a rooted forest. We also give a min/max relationship for the length of such a schedule. The min/max result (for forests and two machines) shows that the addition of unit communication delays increases the optimal schedule length by at most one.The author thanks Ivan Rival for bringing this problem to his attention. Partially supported by a grant from the Reidler Foundation.