Approximation algorithms for scheduling with a limited number of communications

摘要

We consider the case of a UET tree and an unlimited number of processors. We give a 2-approximation algorithm for minimizing the total number of communications, when there are no communication delays. This algorithm allows us to design a 6-approximation algorithm for the makespan minimization problem when there are unit length communication delays and the processors are interconnected by a single bus. Finally, we compare our 6-approximation algorithm with other algorithms by simulations. We show that its mean performance is regular (around 1.25) and we explain. for certain cases, the performance of these algorithms by considering some parameters of the problem.