A novel genetic algorithm to solve travelling salesman problem and blocking flow shop scheduling problem
This paper presents a novel genetic algorithm (GA) to address a wide range of sequencing and scheduling optimisation problems. As for the performance analysis we have applied our algorithm on travelling salesman problems (TSPs) and flow shop scheduling problems (FSPs). Our main objective is to develop an adaptive method which is equally applicable to all kind of optimisation problems with discrete decision variables. Keeping that view in mind we present some new crossover and mutation operators to tackle TSP as well as FSP with GA with path representation. We have also used a new ring parent topology to generate offspring. A new selection procedure, trio-selection procedure is applied to avoid undesirable clustering before reaching the optima. Faster convergence is assured by applying some modified mutation schemes in finding optimal order of cities in TSP and minimising the maximum completion time (i.e., make span) for blocking flow shop scheduling problems. This novel GA variant ensures much better results compared to other heuristics, which is apparent from the experimental results and comparisons with other existing algorithms provided below.
genetic algorithm travelling salesman problem flow shop scheduling problem tsp fsp crossover mutation ring parent topology trio-selection makespan