A multiprocessor scheduling scheme using problem-space genetic algorithms

Efficient assignment and scheduling of tasks of a parallel program is of prime importance in the effective utilization of multiprocessor systems. We describe an efficient scheme for static scheduling of precedence constrained task graphs with non-negligible intertask communication onto fully connected multiprocessor systems with the objective of minimizing the completion time. Our technique is based on problem-space genetic algorithms (PSGA). It combines the search power of genetic algorithms with list scheduling heuristics in order to reduce the completion time and to increase the resource utilization. We demonstrate the effectiveness of our technique by comparing this against several of the existing static scheduling techniques for the test examples reported in the literature