Heuristics for the mixed no-idle flowshop with sequence-dependent setup times

Abstract

In this paper, the mixed no-idle flowshop scheduling problem with sequence-dependent setup times and makespan minimisation criterion is studied. The mixed no-idle flowshop problem considers an environment in which regular machines coexist with stages that require an uninterrupted process. We address an extension of the mixed no-idle problem which considers sequence-dependent setup times on idle machines. To the best of our knowledge, this problem has not yet been studied in the literature although it can be found in the dynamics of productive systems. We also present a mathematical formulation for this new problem and a constructive heuristic is proposed. In addition, two extensive new benchmarks were developed based on a well-known set of problems from the literature. A comprehensive statistical and computational experiment was performed with state-of-the-art constructive heuristics and our proposed method. The results show that the new heuristic outperformed the methods from the literature.

Keywords:

• Flowshop
• no-idle
• setup time
• heuristics
• Makespan

Additional information

Funding

This work was supported by the Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq) - Brazil under grant number 306075/2017-2 and 430137/2018-4.