An analysis on selection methods and multirecombination in evolutionary search when solving the job shop scheduling problem

Abstract

Evolutionary algorithms (EAs) can be used as optimisation mechanisms. Based on the model of natural evolution, they work on populations of individuals instead of on single solutions. In this way, the search is performed in a parallel manner. During the last decades, there has been an increasing interest in evolutionary algorithms to solve scheduling problems. One important feature in these algorithms is the selection of individuals. Selection is the operation by which individuals (i.e. their chromosomes) are selected for mating. To emulate natural selection, individuals with higher fitness should be selected with higher probability, and thus it is one of the operators where the fitness plays an important role. There are many different models of selection (some are not biologically plausible). Commonly, proportional, ranking, tournament selection and stochastic universal sampling are used. EAs considered in this work are improved with a multiplicity feature to solve the job shop scheduling problems (JSSP). The algorithm applied here, multiple crossovers on multiple parents (MCMP), considers more than two parents for reproduction with the possibility to generate multiple children. This approach uses a permutation representation for the chromosome. The objective of this work is to compare the algorithms performance using different selection mechanisms and to analyse the different crossover methods developed to apply MCMP with a permutation representation.