A memetic algorithm for the re-entrant permutation flowshop scheduling problem to minimize the makespan

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

Research output: Journal article publicationJournal articleAcademic researchpeer-review

12 Citations (Scopus)

Abstract

A common assumption in the classical permutation flowshop scheduling model is that each job is processed on each machine at most once. However, this assumption does not hold for a re-entrant flowshop in which a job may be operated by one or more machines many times. Given that the re-entrant permutation flowshop scheduling problem to minimize the makespan is very complex, we adopt the CPLEX solver and develop a memetic algorithm (MA) to tackle the problem. We conduct computational experiments to test the effectiveness of the proposed algorithm and compare it with two existing heuristics. The results show that CPLEX can solve mid-size problem instances in a reasonable computing time, and the proposed MA is effective in treating the problem and outperforms the two existing heuristics.
Original languageEnglish
Pages (from-to)277-283
Number of pages7
JournalApplied Soft Computing Journal
Volume24
DOIs
Publication statusPublished - 1 Jan 2014

Keywords

  • Makespan
  • Memetic algorithm
  • Re-entrant permutation flowshop scheduling

ASJC Scopus subject areas

  • Software

Cite this