On the minimum number of processors for scheduling problems with communication delays

Scheduling problems with interprocessor communication delays are recent problems arising with the development of new message-passing architectures whose number of processors is increasing more and more. The scheduling problem with communication delays is NP-complete even on an unlimited number of processors, and most of the restrictions which are known to make the problem easy suppose that the number of processors is unlimited. The aim of this paper is to estimate the minimum number of processors required to realize a schedule that minimizes the makespan for problems with communication delays. Contrary to problems without communication costs, we show that the minimum number of partitioning paths of tasks is not an upper bound. Then we propose two upper bounds β and β which are valid independent of task processing times and communication costs. We show that β can be calculated in O(n²) if n designates the number of tasks. Then we give an algorithm for determining β in the special case when the precedence graph is an in-tree or an out-tree. A specific study of SCT task systems (Small Communication Time) shows that the achromatic number of the cocomparability graph is an upper bound on the minimum number of processors.