On the Analysis of Crossover Schemes for Genetic Algorithms Applied to the Job Shop Scheduling Problem
R. Braune, S. Wagner, M. Affenzeller - On the Analysis of Crossover Schemes for Genetic Algorithms Applied to the Job Shop Scheduling Problem - Proceedings of the 9th World Multi-Conference on Systemics, Cybernetics and Informatics (WMSCI) 2005, Orlando, Vereinigte Staaten von Amerika, 2005, pp. 236-241
In this paper we perform a detailed analysis of crossover operators and solution decoding schemes for Genetic Algorithms (GAs) applied to the Job Shop Scheduling Problem (JSSP). Based on the job sequence matrix encoding we investigate in how far existing crossover operators are able to preserve characteristics from parent individuals. Assuming that individuals have to represent active solutions, repair techniques (forcing) have to be applied during the decoding process. We study the effects of different decoding schemes and forcing strategies and point out to what extent they cause disruption of crossover results. Finally we present computational results for selected benchmark problems.