Optimal Scheduling Strategies in a Multiprocessor System

This paper describes a set of techniques that can be used to optimally schedule a sequence of interrelated computational tasks on a multiprocessor computer system. Using a directed graph model to represent a computational process, two basic problems are solved here. First, given a set of computational tasks and the relationships between them, the tasks are scheduled such that the total execution time is minimized, and the minimum number of processors required to realize this schedule is obtained. The second problem is of a more general nature. Given k processors, the tasks are scheduled such that execution time is again minimized. Consideration is given to tasks of equal and unequal duration, and task preemption is not allowed.