Approximation algorithms for scheduling trees with general communication delays

摘要

We consider the problem of scheduling a tree with general communication delays. Jakoby and Reischuk proved that this problem is NP-hard for binary trees and unlimited number of processors. Firstly, we develop a clustering procedure based on the same lower bounds as Papadimitriou and Yannakakis for a related problem. We deduce an approximation algorithm for an unlimited number of processors with relative performance 2- 1/(1 + p). where p de- notes the maximum ratio between communication delays and duration of tasks. We also prove that, for a limited number of identical processors m, any list schedule using the clusters structure has a relative performance bounded by 1 + (1 - 1/m)(2- 1/(1 + p)) and that this bound is tight.