One Benders cut to rule all schedules in the neighbourhood

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.