A Self-guided Genetic Algorithm for permutation flowshop scheduling problems

Shih Hsin Chen, Pei Chann Chang, Edwin Tai Chiu Cheng, Qingfu Zhang

Research output: Journal article publicationJournal articleAcademic researchpeer-review

55 Citations (Scopus)

Abstract

In this paper we develop a Self-guided Genetic Algorithm (Self-guided GA), which belongs to the category of Estimation of Distribution Algorithms (EDAs). Most EDAs explicitly use the probabilistic model to sample new solutions without using traditional genetic operators. EDAs make good use of the global statistical information collected from previous searches but they do not efficiently use the location information about individual solutions. It is recently realized that global statistical information and location information should complement each other during the evolution process. In view of this, we design the Self-guided GA based on a novel strategy to combine these two kinds of information. The Self-guided GA does not sample new solutions from the probabilistic model. Instead, it estimates the quality of a candidate offspring based on the probabilistic model used in its crossover and mutation operations. In such a way, the mutation and crossover operations are able to generate fitter solutions, thus improving the performance of the algorithm. We tested the proposed algorithm by applying it to deal with the NP-complete flowshop scheduling problem to minimize the makespan. The experimental results show that the Self-guided GA is very promising. We also demonstrate that the Self-guided GA can be easily extended to treat other intractable combinatorial problems.
Original languageEnglish
Pages (from-to)1450-1457
Number of pages8
JournalComputers and Operations Research
Volume39
Issue number7
DOIs
Publication statusPublished - 1 Jul 2012

Keywords

  • Estimation of Distribution Algorithms
  • Permutation flowshop scheduling
  • Self-guided crossover
  • Self-guided mutation

ASJC Scopus subject areas

  • Computer Science(all)
  • Modelling and Simulation
  • Management Science and Operations Research

Cite this