Benders decomposition for the mixed no-idle permutation flowshop scheduling problem

Bektas, Tolga ORCID: 0000-0003-0634-144X, Hamzadayi, Alper and Ruiz, Ruben (2020) Benders decomposition for the mixed no-idle permutation flowshop scheduling problem. JOURNAL OF SCHEDULING, 23 (4). pp. 513-523.

Text
Hybrid_Benders_for_Flowshop_Scheduling.pdf - Author Accepted Manuscript
Download (277kB) | Preview

Official URL: http://dx.doi.org/10.1007/s10951-020-00637-8

Abstract

<jats:title>Abstract</jats:title><jats:p>The mixed no-idle flowshop scheduling problem arises in modern industries including integrated circuits, ceramic frit and steel production, among others, and where some machines are not allowed to remain idle between jobs. This paper describes an exact algorithm that uses Benders decomposition with a simple yet effective enhancement mechanism that entails the generation of additional cuts by using a referenced local search to help speed up convergence. Using only a single additional optimality cut at each iteration, and combined with combinatorial cuts, the algorithm can optimally solve instances with up to 500 jobs and 15 machines that are otherwise not within the reach of off-the-shelf optimization software, and can easily surpass ad-hoc existing metaheuristics. To the best of the authors’ knowledge, the algorithm described here is the only exact method for solving the mixed no-idle permutation flowshop scheduling problem.</jats:p>

Item Type:	Article
Uncontrolled Keywords:	Flowshop scheduling, Mixed no-idle, Benders decomposition, Referenced local search
Depositing User:	Symplectic Admin
Date Deposited:	06 Jan 2020 08:37
Last Modified:	19 Jan 2023 00:11
DOI:	10.1007/s10951-020-00637-8
Related URLs:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3069279