Scheduling parallel program tasks on multiprocessors

The authors study the problem of scheduling precedence-related tasks on a sufficiently large number of processors to minimize the total execution time. Without communication delay between processors, this problem can be solved by using the critical path method. The authors consider the case when communication delay cannot be disregarded. An algorithm with time complexity O((1.52)ⁿ×n log n) which finds an optimal schedule for a set of n tasks with tree-like precedence relations is presented