MILP-based local search procedures for minimizing total tardiness in the No-idle Permutation Flowshop Problem
Loading...
Files
Published version
Supplementary data
Date
2022-05-17
Authors
Balogh, Andrea
Garraffa, Michele
O'Sullivan, Barry
Salassa, Fabio
Journal Title
Journal ISSN
Volume Title
Publisher
Elsevier
Published Version
Abstract
We consider the No-idle Permutation Flowshop Scheduling Problem (NPFSP) with a total tardiness criterion. We present two Mixed Integer Linear Programming (MILP) formulations based on positional and precedence variables, respectively. We study six local search procedures that explore two different neighborhoods by exploiting the MILP formulations. Our computational experiments show that two of the proposed procedures strongly outperform the state-of-the-art metaheuristic. We update 63% of the best known solutions of the instances in Taillards’ benchmark, and 77% if we exclude those instances for which we proved that the previous best known solutions are optimal.
Description
Keywords
Scheduling , Flowshop , No-idle , MILP , Hybrid heuristics
Citation
Balogh, A., Garraffa, M., O'Sullivan, B. and Salassa, F. (2022) 'MILP-based local search procedures for minimizing total tardiness in the No-idle Permutation Flowshop Problem', Computers & Operations Research, 146, 105862 (15 pp). doi: 10.1016/j.cor.2022.105862