An improved memetic algorithm based on a dynamic neighbourhood for the permutation flowshop scheduling problem

Jianyou Xu, Yunqiang Yin, Edwin Tai Chiu Cheng, Chin Chia Wu, Shusheng Gu

Research output: Journal article publicationJournal articleAcademic researchpeer-review

14 Citations (Scopus)

Abstract

The permutation flowshop scheduling problem (PFSP) has been extensively studied in the scheduling literature. In this paper, we present an improved memetic algorithm (MA) to solve the PFSP to minimise the total flowtime. In the proposed MA, we develop a stochastic local search based on a dynamic neighbourhood derived from the NEH method. During the evolution process, the size of the neighbourhood is dynamically adjusted to change the search focus from exploration to exploitation. In addition, we introduce a new population generation mechanism to guarantee both the quality and diversity of the new populations. We also design a diversity index for the population to monitor the diversity of the current population. If the diversity index is less than a given threshold value, the current population will be replaced by a new one with good diversity so that the proposed MA has good ability to overcome local optima. We conduct computational experiments to test the effectiveness of the proposed algorithm. The computational results on randomly generated problem instances and benchmark problem instances show that the proposed MA is effective and superior or comparable to other algorithms in the literature.
Original languageEnglish
Pages (from-to)1188-1199
Number of pages12
JournalInternational Journal of Production Research
Volume52
Issue number4
DOIs
Publication statusPublished - 16 Feb 2014

Keywords

  • discrete particle swarm optimisation
  • makespan
  • permutation flowshop scheduling
  • self-adaptive diversity control
  • total flowtime

ASJC Scopus subject areas

  • Strategy and Management
  • Management Science and Operations Research
  • Industrial and Manufacturing Engineering

Cite this