A novel iterated greedy algorithm for no-wait permutation flowshop scheduling to minimize weighted quadratic tardiness

Abstract

This article addresses the no-wait permutation flowshop layout where the jobs must be processed continuously in the available machines without interruption. The objective function is weighted quadratic tardiness minimization. Since the problem under study is NP-hard, an iterated greedy algorithm is introduced where the parameters are selected according to a variable neighbourhood descent framework. In the authors' innovative algorithm, in the first iteration of the search process, the parameters are initialized with a fixed number. In the remaining iterations, such parameters are reduced deterministically, aiming to explore distinct values throughout the search process. The proposal is compared with five other algorithms proposed for closely related problems, considering two performance measures: the Relative Deviation Index (RDI) and the Success Rate (SR). The proposed algorithm produced average values of RDI and SR of 1.2% and 86.9%, respectively. The computational results demonstrated that the authors' proposal outperformed all the other five algorithms under comparison.

Keywords:

• Production scheduling
• weighted quadratic tardiness
• no-wait flowshop
• iterated greedy algorithm

Disclosure statement

The authors declare that they have no conflict of interest.

Availability of data and materials

The data sets are available at http://soa.iti.es/problem-instances. The results of all computational tests are available at https://www.researchgate.net/publication/360040702_Results_-_A_novel_iterated_greedy_algorithm_for_the_no-wait_permutation_flowshop_scheduling_-to_minimize_weighted_quadratic_tardiness?showFulltext=1&linkId=625eb87d4173a21-a0d1ec944.

Additional information

Funding

This study was financed in part by the Coordination for the Improvement of Higher Education Personnel (CAPES) and the National Council for Scientific and Technological Development (CNPq) [grants 404232/2016-7, 303594/2018-7, 306075/2017-2, 430137/2018-4, 312585/2021-7, 407151/2021-4].