Integrating list heuristics into genetic algorithms for multiprocessor scheduling

In the multiprocessor scheduling problem a given program is to be scheduled in a 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. The authors propose a new combined approach, where a genetic algorithm is improved with the introduction of some knowledge about the scheduling problem represented by the use of a list heuristic in the crossover and mutation genetic operations. This knowledge-augmented genetic approach is empirically compared with a “pure” genetic algorithm and with a “pure” list heuristic, both from the literature. Results of the experiments carried out with synthetic instances of the scheduling problem show that the genetic algorithm produces much better results in terms of quality of solutions, although being slower in terms of execution time