Optimal and near optimal tree scheduling for parallel systems

The authors present seven algorithms for multiprocessor scheduling of task trees. The objective function of the algorithms is to minimize parallel time (the time between the start of the first processor and the completion of the last processor) in an environment where interprocessor communication costs are significant. Test results are given for implementations of (1) an optimal algorithm that produces a schedule that cannot be improved upon, (2) a greedy algorithm that has minimal overhead, and (3) a `light load´ algorithm which combines the best features of the optimal algorithm and the greedy one. The authors illustrate the trade-off between generating optimal schedules and creating scheduling programs that perform their allocation in a reasonable amount of time. They also give a new NP-complete result