A linear time algorithm to schedule trees with communication delays optimally on two machines
Marinus Veldhorst · 1993
In this paper we prove that a minimum length schedule on 2 machines can be found in linear time for a set of n unit length tasks with a forest of intrees as precedence relations, and with unit interprocessor communication delays, while duplication of tasks is not allowed.