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.
Giroudeau et al. (Mon,) studied this question.