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

Arkabandhu Chowdhury, Arnab Ghosh, Subhajit Sinha, Swagatam Das, Avishek Ghosh

Research output: Contribution to journalArticlepeer-review

19 Scopus citations

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., 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.

Original languageEnglish (US)
Pages (from-to)303-314
Number of pages12
JournalInternational Journal of Bio-Inspired Computation
Volume5
Issue number5
DOIs
StatePublished - 2013
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science

Keywords

  • Crossover
  • Flow shop scheduling problem
  • FSP
  • Genetic algorithm
  • Makespan
  • Mutation
  • Ring parent topology
  • Travelling salesman problem
  • Trio-selection
  • TSP

Fingerprint

Dive into the research topics of 'A novel genetic algorithm to solve travelling salesman problem and blocking flow shop scheduling problem'. Together they form a unique fingerprint.

Cite this