A Comparative Study of Crossover Operators for Genetic Algorithms to Solve the Job Shop Scheduling Problem

Genetic algorithms (GA) are wide class of global optimization methods. Many genetic algorithms have been applied to solve combinatorial optimization problems. One of the problems in using genetic algorithms is the choice of crossover operator. The aim of this paper is to show the influence of genetic crossover operators on the performance of a genetic algorithm. The GA is applied to the job shop scheduling problem (JSSP). To achieve this aim an experimental study of a set of crossover operators is presented. The experimental study is based on a decision support system (DSS). To compare the abilities of different crossover operators, the DSS was designed giving all the operators the same opportunities. The genetic crossover operators are tested on a set of standard instances taken from the literature. The makespan is the measure used to evaluate the genetic crossover operators. The main conclusion is that there is a crossover operator having the best average performance on a specific set of solved instances.