A multiprocessor scheduling scheme using problem-space genetic algorithms

Abstract

Efficient assignment and scheduling of tasks of a parallel program is of prime importance in the effective utilization of multiprocessor systems. In this paper, we describe an efficient scheme for static scheduling of precedence constrained task graphs with non - neg lig i b le i n ter t as k 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 heuristic in order to reduce the completion time and to increase the resource utilization. We demonstrate the effectiveness of our technique by comparing against several of the existing static scheduling techniques for the test examples reported in literature.