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. We 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 generic 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 our genetic algorithm produces much better results in terms of quality of solutions, although being slower in terms of execution time.