Heuristics to optimize total completion time subject to makespan in no-wait flow shops with sequence-dependent setup times

Abstract

We propose four algorithms for the no-wait flow shop scheduling problem. The objective is minimizing total completion time such that makespan is not greater than a maximum value. We address the problem with sequence-dependent setup times, an important production constraint that has never been considered for this problem before. The proposed algorithms start from an initial solution and then iterate through a process that destroys and repairs the incumbent solution in order to improve it. The methods are build combining distinct destruction and construction mechanisms, where the search intensification-diversification is explored at different levels. After an initial assessment, the best proposed algorithm (IG₄) is chosen to be compared with three literature methods (PAL, TOB, ISA-2) developed for similar problems. Computational experiments revealed that the overall average relative percentage deviation of PAL, TOB, ISA-2, and IG₄ are 10.97%, 4.44%, 2.07%, and 0.36%, respectively. The statistical analysis confirms that IG₄ significantly outperforms the existing methods.

Keywords:

• Flow shop
• no-wait
• sequence-dependent setup
• total completion time
• makespan
• greedy

Disclosure statement

No potential conflict of interest was reported by the authors.

Additional information

Funding

This work was supported by Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq) - Brazil under grant numbers 306075/2017-2, 430137/2018-4, 312585/2021-7 and the Coordena cão de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) - Brazil under grant number 88882.379108/2019-01.