Scheduling with Communication Delays

Abstract

In this paper, scheduling problems with communication delays are considered. Formally, we are given a partial order relation $\prec$ on a set of tasks $T$, a set of processors $P$, and a deadline $d$. Supposing that a unit communication delay between two tasks $a$ and $b$ such that $a\prec b$ occurs whenever $a$ and $b$ are scheduled on different processors, the question is: Can the tasks of $T$ be scheduled on $P$ within time $d$? It is shown here that the problem is NP-complete even if $d=4$. Also, for an unlimited number of processors, C. Picouleau has shown that for $d=8$ the problem is NP-complete. Here it is shown that it remains NP-complete for $d\ge 6$ but is polynomially solvable for $d<6$, which closes the gap between P and NP for this problem, as regards the deadline.