Scheduling in the presence of processor networks : complexity and approximation

In this paper, we study the problem of makespan minimization for the multiprocessor scheduling problem in the presence of communication delays. The communication delay between two tasks i and j depends on the distance between the two processors on which these two tasks are executed. Lahlou shows that a simple polynomial‐time algorithm exists when the length of the schedule is at most two (the problem becomes NP‐complete when the length of the schedule is at most three). We prove that there is no polynomial‐time algorithm with a performance guarantee of less than 4/3 (unless = P=NP) to minimize the makespan when the network topology is a chain or ring and the precedence graph is a bipartite graph of depth one. We also develop two polynomial‐time approximation algorithms with constant ratio dedicated to cases where the processor network admits a limited or unlimited number of processors.