Effects of different chromosome representations in developing genetic algorithms to solve DFJS scheduling problems

Muh-Cherng Wu*, Chi Shiuan Lin, Chia Hui Lin, Chen Fu Chen

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

24 Scopus citations

Abstract

This paper attempts to compare the effect of using different chromosome representations while developing a genetic algorithm to solve a scheduling problem called DFJS (distributed flexible job shop scheduling) problem. The DFJS problem is strongly NP-hard; most recent prior studies develop various genetic algorithms (GAs) to solve the problems. These prior GAs are similar in the algorithmic flows, but are different in proposing different chromosome representations. Extending from this line, this research proposes a new chromosome representation (called SOP) and develops a genetic algorithm (called GA_OP) to solve the DFJS problem. Experiment results indicate that GA_OP outperforms all prior genetic algorithms. This research advocates the importance of developing appropriate chromosome representations while applying genetic algorithms (or other meta-heuristic algorithms) to solve a space search problem, in particular when the solution space is high-dimensional.

Original languageEnglish
Pages (from-to)101-112
Number of pages12
JournalComputers and Operations Research
Volume80
DOIs
StatePublished - 1 Apr 2017

Keywords

  • Chromosome representation
  • Distributed flexible job shop
  • Genetic algorithm
  • Scheduling

Fingerprint Dive into the research topics of 'Effects of different chromosome representations in developing genetic algorithms to solve DFJS scheduling problems'. Together they form a unique fingerprint.

Cite this