Abstract
In this article we investigate complexity and approximation on a processor network where the communication delay depends on the distance between the processors performing tasks. We then prove that there is no polynomial-time heuristic with a performance guarantee smaller than 65 (respectively 1413) for minimization of the makespan (respectively the total job completion time) on a processor network represented by a star. Moreover, we design an efficient polynomial-time approximation algorithm with a worst-case ratio of four. We also prove that a polynomial-time algorithm exists for a schedule with a length of at most four. Lastly, we generalize all previous results on complexity and approximation.