One Benders cut to rule all schedules in the neighbourhood

Ioannis Avgerinos, Ioannis Mourtos, Stavros Vatikiotis and Georgios Zois

European Journal of Operational Research, 2025, vol. 323, issue 1, 62-85

Abstract: Logic-Based Benders Decomposition (LBBD) and its Branch-and-Cut variant, namely Branch-and-Check, enjoy an extensive applicability on a broad variety of problems, including scheduling. As the application of LBBD to resource-constrained scheduling remains less explored, we propose a position-based Mixed-Integer Linear Programming (MILP) formulation for scheduling on unrelated parallel machines. To improve upon it, we notice that certain k−OPT neighbourhoods could be explored by regular local search operators, thus allowing us to integrate Local Branching into Branch-and-Check. After enumerating such neighbourhoods and obtaining their local optima – hence, proving that they are suboptimal – a local branching cut (applied as a Benders cut) eliminates all their solutions at once, thus avoiding an overload of the master problem with Benders cuts. However, to guarantee convergence to optimality, the constructed neighbourhood should be exhaustively explored, hence this time-consuming procedure must be accelerated by domination rules or selectively implemented on nodes which are more likely to reduce the optimality gap. In this study, we apply this idea on the ‘internal (job) swaps’ to construct formulation-specific 4-OPT neighbourhoods. We experiment extensively with the minimisation of total completion times and total tardiness on unrelated machines with sequence-dependent and resource-constrained setups. Our results show that our proposed use of local branching reduces optimality gaps considerably compared to standard Branch-and-Check or a monolithic Constraint Programming implementation. The simplicity of our approach allows its transferability to other neighbourhoods of the same or analogous formulations.

Keywords: Integer programming; Logic-based Benders decomposition; Local branching; Scheduling; Branch-and-check (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221724009512
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:323:y:2025:i:1:p:62-85

DOI: 10.1016/j.ejor.2024.12.009

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().