Scheduling UET‐tasks on a star network: complexity and approximation

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 $$\frac{6}{5}$$ (respectively $$\frac{14}{13}$$ ) 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.