A block mining and re-combination enhanced genetic algorithm for the permutation flowshop scheduling problem

Pei Chann Chang, Wei Hsiu Huang, Jheng Long Wu, Edwin Tai Chiu Cheng

Research output: Journal article publicationJournal articleAcademic researchpeer-review

26 Citations (Scopus)

Abstract

The goal of block mining is to obtain a set of genes that contain dependency among gene relationships. Such blocks without overlapping of genes can be further merged to form a new chromosome and the quality of the new chromosome can be greatly improved. Based on this concept, we propose a novel block mining method that is able to locate common structures or to establish new blocks (like a small piece of puzzle) from a set of high fit chromosomes. The identified blocks (puzzles) will also be updated generation by generation through the newly updated high fit chromosomes. We develop a heuristic re-combination procedure to form a new chromosome by re-combining the blocks. We call the new chromosomes generated as artificial chromosomes (ACs) and inject them into the evolutionary process when the convergence slope of the evolutionary process is less than a predefined threshold. This new algorithm retains the regular simple genetic algorithm (SGA) operations of crossover and mutation, and utilizes the ACs generated from elites to speed up the convergence process. Experimental results indicate that the puzzle-based method of chromosome generation is very efficient and effective in solving the traditional permutation flowshop scheduling problem. The new method can be applied to tackle other NP-complete problems such as scheduling and vehicle routing problems.
Original languageEnglish
Pages (from-to)45-55
Number of pages11
JournalInternational Journal of Production Economics
Volume141
Issue number1
DOIs
Publication statusPublished - 1 Jan 2013

Keywords

  • Artificial chromosomes
  • Building blocks
  • Flowshop scheduling
  • Genetic algorithm
  • Linkage learning
  • Re-combination

ASJC Scopus subject areas

  • Business, Management and Accounting(all)
  • Economics and Econometrics
  • Management Science and Operations Research
  • Industrial and Manufacturing Engineering

Cite this