The role of different crossover methods when solving the open shop scheduling problem via a simple evolutionary approach

Abstract

The Open Shop Scheduling Problem (OSSP) is one of the most interesting, complexes and not frequently approached scheduling problems. Due to its intractability with other techniques, in this work we present an evolutionary approach to provide approximate solutions. One of the most important points in an Evolutionary Algorithm is to determine how to represent individuals of the evolving population and then to decide suitable genetic operators. In this work, we use permutations as chromosomes. Dealing with permutations requires appropriate crossover operators to ensure feasible offspring. Usual operators are partially-mapped, order, cycle and onecut- point crossover. The goal is to determine which is the most adequate for facing the OSSP with a simple evolutionary algorithm. Several known instances have been considered for testing in order to evaluate the algorithm behavior.