UET scheduling with unit interprocessor communication delays (Q1097163)

We consider the problem of scheduling a partially ordered set of unit execution time tasks (UET) on \(m>1\) processors where there is a communication delay of unit time between any pair of distinct processors. We show that the problem of finding an optimal schedule is NP-hard. A greedy schedule is one where no processor remains idle if there is some task available which it could process. We establish that the length of an arbitrary greedy schedule, \(\omega^ c_ g\) satisfies \[ \omega^ c_ g\leq (3-\frac{2}{m})\omega^ c_{opt}-(1-\frac{1}{m}) \] where \(\omega^ c_{opt}\) is the length of the optimal schedule. We define a generalized list schedule (a type of greedy schedule) and discuss anomalous behaviour of such schedules with respect to speed-up. The relevance of these results to the implementation of parallel languages is discussed.