Title: A novel genetic algorithm to solve travelling salesman problem and blocking flow shop scheduling problem

Authors: Arkabandhu Chowdhury; Arnab Ghosh; Subhajit Sinha; Swagatam Das; Avishek Ghosh

Addresses: Department of Electronics and Telecommunication Engineering, Jadavpur University, Kolkata – 700032, India ' Department of Electronics and Telecommunication Engineering, Jadavpur University, Kolkata – 700032, India ' Department of Electronics and Telecommunication Engineering, Jadavpur University, Kolkata – 700032, India ' Electronics and Communication Sciences Unit, Indian Statistical Institute, Kolkata – 700018, India ' Department of Electronics and Telecommunication Engineering, Jadavpur University, Kolkata – 700032, India

Abstract: 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., makespan) 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.

Keywords: genetic algorithms; crossover operators; mutation operators; trio-selection; ring parent topology; travelling salesman problem; TSP; flow shop scheduling; FSP; makespan; scheduling optimisation; sequencing optimisation.

DOI: 10.1504/IJBIC.2013.057172

International Journal of Bio-Inspired Computation, 2013 Vol.5 No.5, pp.303 - 314

Received: 03 Apr 2012
Accepted: 04 Feb 2013
Published online: 31 Mar 2014 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article