An improved heuristic for no-wait flow shop to minimize makespan

Honghan Ye, Wei Li, Amin Abedini

Research output: Contribution to journalArticlepeer-review

26 Scopus citations

Abstract

No-wait flow shop production has been widely applied in manufacturing, where no waiting time is allowed between intermediate operations. However, minimization of makespan for no-wait flow shop production is NP-hard. In this paper, we propose an average idle time (AIT) heuristic to minimize makespan in no-wait flow shop production. First, we take the current idle times and future idle times into consideration, proposing an initial sequence algorithm, and then use the insertion and neighborhood exchanging methods to further improve solutions. Compared with three existing best-known heuristics, our AIT heuristic can achieve the smallest deviations of 0.23% from optimum, based on Taillard's benchmarks and 600 randomly generated instances, in the same computational complexity.

Original languageEnglish
Pages (from-to)273-279
Number of pages7
JournalJournal of Manufacturing Systems
Volume44
DOIs
StatePublished - Jul 2017

Bibliographical note

Publisher Copyright:
© 2017 The Society of Manufacturing Engineers

Keywords

  • Computational complexity
  • Heuristics
  • Makespan
  • No-wait flow shop

ASJC Scopus subject areas

  • Software
  • Control and Systems Engineering
  • Hardware and Architecture
  • Industrial and Manufacturing Engineering

Fingerprint

Dive into the research topics of 'An improved heuristic for no-wait flow shop to minimize makespan'. Together they form a unique fingerprint.

Cite this