An iterated greedy algorithm for the no-wait flowshop scheduling problem to minimize makespan subject to total completion time

Abstract

This article addresses the m-machine no-wait flowshop scheduling problem with the objective of minimizing makespan subject to an upper bound on total completion time. An iterated greedy-with-local-search algorithm is proposed and compared with a mathematical model and the best method found in the literature for solving this problem. Computational experiments and statistical analysis are conducted to evaluate the methods. The results show that the proposed approach offers fast and high quality solutions when compared with the mathematical model and at the same time outperforms the best existing algorithm in effectiveness and efficiency.

Keywords:

• Flowshop
• no-wait
• makespan
• total completion time

Acknowledgments

This work was supported by the Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq) [Nos. 306075/2017-2, 430137/2018-4 and 160347/2019-0]; the Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) [No. 88882.379108/2019-01].

Disclosure statement

No potential conflict of interest was reported by the author(s).

Additional information

Funding

This work was supported by the Brazilian National Council for Scientific and Technological Development (Conselho Nacional de Desenvolvimento Científico e Tecnológico) [Nos. 306075/2017-2, 430137/2018-4 and 160347/2019-0]; the Brazilian Coordination for the Improvement of Higher Education Personnel (Coordenação de Aperfeiçoamento de Pessoal de Nível Superior) [No. 88882.379108/2019-01].