On the efficiency of a genetic algorithm for the multiprocessor scheduling problem

Abstract

In the multiprocessor scheduling problem a given program is to be scheduled in a given multiprocessor system such that the program's execution time is minimized. This problem being very hard to solve exactly, many heuristic methods for finding a suboptimal schedule exist. An efficient genetic algorithm which introduces some knowledge about the scheduling problem represented by the use of a list heuristic in the crossover and mutation genetic operations was recently proposed [3] in this paper we investigate the efficiency of this genetic algorithm from a theoretical point of view. In particular , we demonstrate the ability of the knowledge-augmented crossover operator to generate all the space of feasible solutions.