Copyright © 2011 M. Bouznif and R. Giroudeau. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

Abstract

We investigate complexity and approximation results on a processor networks where the communication delay depends on the distance between the processors performing tasks. We then prove that there is no heuristic with a performance guarantee smaller than 4/3 for makespan minimization for precedence graph on a large class of processor networks like hypercube, grid, torus, and so forth, with a fixed diameter . We extend complexity results when the precedence graph is a bipartite graph. We also design an efficient polynomial-time -approximation algorithm for the makespan minimization on processor networks with diameter .