Complexity and approximation algorithm for scheduling communication delays problem  with limited communication resource

This paper is devoted to the complexity and approximation for scheduling communication delays problem with limited communication resource. In this model, the number of allowed communication between two consecutive time is bounded by a constant. In such context, it is important to decide a ordered list among the successors that will be scheduled on the same processor, and also select and ordered successors according to the availability of resources that will executed on other processors. Therefore, we propose some complexity results according to the topology of the precedence graph. Moreover, we develop efficient polynomial-time approximation algorithms for bipartite graph for the minimization of the length of the schedule (resp. the sum of completion time) in presence or not of duplication.