Menu
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 \geq 6\) but is polynomially solvable for \(d < 6\), which closes the gap between P and NP for this problem, as regards the deadline.