A genetic algorithm embedded with a concise chromosome representation for distributed and flexible job-shop scheduling problems

Po Hsiang Lu, Muh Cherng Wu*, Hao Tan, Yong Han Peng, Chen Fu Chen

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

41 Scopus citations

Abstract

This paper proposes a genetic algorithm GA_JS for solving distributed and flexible job-shop scheduling (DFJS) problems. A DFJS problem involves three scheduling decisions: (1) job-to-cell assignment, (2) operation-sequencing, and (3) operation-to-machine assignment. Therefore, solving a DFJS problem is essentially a 3-dimensional solution space search problem; each dimension represents a type of decision. The GA_JS algorithm is developed by proposing a new and concise chromosome representation SJ O B, which models a 3-dimensional scheduling solution by a 1-dimensional scheme (i.e., a sequence of all jobs to be scheduled). That is, the chromosome space is 1-dimensional (1D) and the solution space is 3-dimensional (3D). In GA_JS, we develop a 1D-to-3D decoding method to convert a 1D chromosome into a 3D solution. In addition, given a 3D solution, we use a refinement method to improve the scheduling performance and subsequently use a 3D-to-1D encoding method to convert the refined 3D solution into a 1D chromosome. The 1D-to-3D decoding method is designed to obtain a “good” 3D solution which tends to be load-balanced. In contrast, the refinement and 3D-to-1D encoding methods of a 3D solution provides a novel way (rather than by genetic operators) to generate new chromosomes, which are herein called shadow chromosomes. Numerical experiments indicate that GA_JS outperforms the IGA developed by De Giovanni and Pezzella (Eur J Oper Res 200:395–408, 2010), which is the up-to-date best-performing genetic algorithm in solving DFJS problems.

Original languageEnglish
Pages (from-to)19-34
Number of pages16
JournalJournal of Intelligent Manufacturing
Volume29
Issue number1
DOIs
StatePublished - 1 Jan 2018

Keywords

  • Chromosome representation
  • Chromosome space
  • Distributed flexible job-shop
  • Genetic algorithm
  • Shadow chromosomes
  • Solution space

Fingerprint

Dive into the research topics of 'A genetic algorithm embedded with a concise chromosome representation for distributed and flexible job-shop scheduling problems'. Together they form a unique fingerprint.

Cite this