Perfomance evaluation of selection methods to solve the job shop scheduling problem

Abstract

In evolutionary algorithms selection mechanisms aim to favour reproduction of better individuals imposing a direction on the search process. It does not create new individuals; instead it selects comparatively good individuals from a population and typically does it accorgind to their fitness. The idea is that interacting with other individuals (competition), those with higher fitness have a higher probability to be selected for mating. In that manner, because the fitness of an individual gives a measure of its “goodness”, selection introduces the influence of the fitness function to the evolutionary process. Moreover, selection is the only operator of genetic algorithm where the fitness of an individual affects the evolution process. In such a process two important, strongly related, issues exist: selective pressure and population diversity. In this work we are showing the effect of applying different selection mechanisms to a set of instances of the Job Shop Scheduling Problem, with different degress of complexity. For these experiments we are using multiplicity features in the selection of parents for the reproduction with the possibility to generate multiple number of children too, because the results using these approaches outperform to those obtained under traditional evolutionary algorithms. This was shown in our previous works. A description of each method, experiments and preliminary results under different combinations are reported.