A comparison of two chromosome representation schemes used in solving a family-based scheduling problem

Chen Fu Chen, Muh-Cherng Wu*, Yi Hsun Li, Pang Hao Tai, Chie Wun Chiou

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

7 Scopus citations

Abstract

Meta-heuristic algorithms have been widely used in solving scheduling problems; previous studies focused on enhancing existing algorithmic mechanisms. This study advocates a new perspective-developing new chromosome (solution) representation schemes may improve the performance of existing meta-heuristic algorithms. In the context of a scheduling problem, known as permutation manufacturing-cell flow shop (PMFS), we compare the effectiveness of two chromosome representation schemes (Sold and Snew) while they are embedded in a meta-heuristic algorithm to solve the PMFS scheduling problem. Two existing meta-heuristic algorithms, genetic algorithm (GA) and ant colony optimization (ACO), are tested. Denote a tested meta-heuristic algorithm by X-Y, where X represents an algorithmic mechanism and Y represents a chromosome representation. Experiment results indicate that GA- Snew outperforms GA-Sold, and ACO-Snew also outperforms ACO-Sold. These findings reveal the importance of developing new chromosome representations in the application of meta-heuristic algorithms.

Original languageEnglish
Pages (from-to)21-30
Number of pages10
JournalRobotics and Computer-Integrated Manufacturing
Volume29
Issue number3
DOIs
StatePublished - 1 Jan 2013

Keywords

  • Ant Colony optimization
  • Chromosome representation
  • Genetic algorithm
  • Scheduling

Fingerprint Dive into the research topics of 'A comparison of two chromosome representation schemes used in solving a family-based scheduling problem'. Together they form a unique fingerprint.

Cite this