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. ISSN 1094-6136, 1099-1425

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

Abstract

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.

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:	16 Jun 2026 16:43
DOI:	10.1007/s10951-020-00637-8
Related Websites:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3069279
Disclaimer:	The University of Liverpool is not responsible for content contained on other websites from links within repository metadata. Please contact us if you notice anything that appears incorrect or inappropriate.