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 and Chen-Fu Chen
Additional contact information
Po-Hsiang Lu: National Chiao Tung University
Muh-Cherng Wu: National Chiao Tung University
Hao Tan: National Chiao Tung University
Yong-Han Peng: National Chiao Tung University
Chen-Fu Chen: National Chiao Tung University

Journal of Intelligent Manufacturing, 2018, vol. 29, issue 1, No 2, 19-34

Abstract: Abstract This paper proposes a genetic algorithm $$GA\_JS$$ G A _ J S 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$$ G A _ J S algorithm is developed by proposing a new and concise chromosome representation $${\varvec{S}}_{{\varvec{JOB}}}$$ S J 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$$ G A _ J S , 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$$ G A _ J S 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.

Keywords: Genetic algorithm; Distributed flexible job-shop; Chromosome representation; Chromosome space; Solution space; Shadow chromosomes (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://link.springer.com/10.1007/s10845-015-1083-z Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joinma:v:29:y:2018:i:1:d:10.1007_s10845-015-1083-z

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10845

DOI: 10.1007/s10845-015-1083-z

Access Statistics for this article

Journal of Intelligent Manufacturing is currently edited by Andrew Kusiak

More articles in Journal of Intelligent Manufacturing from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().