Merits of using chromosome representations and shadow chromosomes in genetic algorithms for solving scheduling problems

Chi Shiuan Lin, I. Ling Lee, Muh-Cherng Wu*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

3 Scopus citations

Abstract

Two conjectures, the use of incomplete chromosome representations and shadow chromosomes may improve the performance of genetic algorithms (GAs), are examined in this study. The examination entails testing distributed flexible job shop scheduling (DFJS) problems subject to preventive maintenance (PM) that involve four scheduling decisions. Genetic algorithms based on a complete chromosome representation that explicitly models the four decisions have been developed previously. By contrast, herein, two incomplete chromosome representations are proposed, whereby the conjectured advantages are two-fold. First, an incomplete chromosome representation models two scheduling decisions, and the remaining two are decoded by heuristic rules designed to ensure the load balance of manufacturing resources. Therefore, scheduling solutions with load imbalance will not be generated, which will help prevent the execution of ineffective searches. Second, a novel method of generating new chromosomes is developed and employed, instead of using traditional genetic operations. These chromosomes, called shadow chromosomes, are generated from good quality scheduling solutions and they may improve performance. Based on these two conjectures, four GAs are proposed. Numerical experiments reveal that each proposed GA outperforms the prior GAs substantially and the two conjectures are thus well justified. These findings shed light on the application of the two conjectures for developing metaheuristic algorithms to solve other high-dimensional space search problems.

Original languageEnglish
Pages (from-to)196-207
Number of pages12
JournalRobotics and Computer-Integrated Manufacturing
Volume58
DOIs
StatePublished - 1 Aug 2019

Keywords

  • Chromosome representation
  • Genetic algorithm
  • Scheduling and preventive maintenance
  • Shadow chromosome

Fingerprint Dive into the research topics of 'Merits of using chromosome representations and shadow chromosomes in genetic algorithms for solving scheduling problems'. Together they form a unique fingerprint.

Cite this