A novel genetic algorithm to solve travelling salesman problem and blocking flow shop scheduling problem Online publication date: Wed, 16-Oct-2013
by Arkabandhu Chowdhury; Arnab Ghosh; Subhajit Sinha; Swagatam Das; Avishek Ghosh
International Journal of Bio-Inspired Computation (IJBIC), Vol. 5, No. 5, 2013
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.
Online publication date: Wed, 16-Oct-2013
If you are not a subscriber and you just want to read the full contents of this article, buy online access here.Complimentary Subscribers, Editors or Members of the Editorial Board of the International Journal of Bio-Inspired Computation (IJBIC):
Login with your Inderscience username and password:
Want to subscribe?
A subscription gives you complete access to all articles in the current issue, as well as to all articles in the previous three years (where applicable). See our Orders page to subscribe.
If you still need assistance, please email firstname.lastname@example.org