Bicriteria approximation algorithms for scheduling problems with communications delays

We study the problem of simultaneously minimizing the makespan and the average weighted completion time for the precedence multiprocessor constrained scheduling problem with unit execution times and unit communication delays, known as the UET–UCT problem. We propose a simple (16/9)-approximation algorithm for the problem with an unrestricted number of machines. We improve our algorithm by adapting a technique first introduced by Aslam et al. and provide a (1.745)-approximate solution. For the considered scheduling problem, we prove the existence of a (1.445)-approximate solution, improving the generic existence result of Aslam et al. Also notice that our results for the case of an unrestricted number of processors hold for the more general scheduling problem with small communication delays (SCT problem), and for two other classical optimality criteria: maximum lateness and weighted lateness. Finally, we propose an approximation algorithm for the UET–UCT problem with a restricted number of processors.