Scheduling with sufficient loosely coupled processors

Finding optimal schedules for precedence-related tasks on a multiprocessor system is, in general, an NP-hard problem. With unit-time tasks and tree precedences, however, the problem is known to be solvable in polynomial time. With the introduction of communication delays due to message passing between processors, even this restricted case may again become difficult. This paper shows that when there are enough processors to run all available tasks and when communication delays are no longer than the shortest task processing time, then there is a linear-time optimal algorithm. The basic algorithm, Join Latest Predecessor, and some extensions are presented giving optimal solutions for a variety of cases.