Minimizing makespan for no-wait flowshop scheduling problems with setup times

Kuo Ching Ying, Shih Wei Lin*

*Corresponding author for this work

Research output: Contribution to journalJournal Article peer-review

19 Scopus citations


This study investigates no-wait flowshop scheduling problems with sequence-independent and sequence-dependent setup times aimed at minimizing the makespan. We propose an efficient two-phase matheuristic, which can optimally solve all tested instances of three existing benchmark problem sets and a new generated large-sized test problem set, with up to 20-machine and 2000-job test instances, in acceptable computational times. This is a dramatic improvement over all previously known algorithms. In view of the strongly NP-complete nature of the two problems addressed herein, this study contributes an exact method that can find optimal solutions for solving these problems with the efficiency necessary to meet real-world scheduling requirements.

Original languageEnglish
Pages (from-to)73-81
Number of pages9
JournalComputers and Industrial Engineering
StatePublished - 07 2018
Externally publishedYes

Bibliographical note

Publisher Copyright:
© 2018 Elsevier Ltd


  • Makespan
  • Matheuristic
  • No-wait flowshop
  • Scheduling
  • Setup times


Dive into the research topics of 'Minimizing makespan for no-wait flowshop scheduling problems with setup times'. Together they form a unique fingerprint.

Cite this