一种Benders割平面统治所有邻域调度问题

One Benders cut to rule all schedules in the neighbourhood

摘要 Abstract

逻辑驱动的Benders分解(LBBD)及其分支-切割变体,即分支-检查方法,在广泛的优化问题中具有广泛的应用,包括调度问题。尽管LBBD能够提供针对特定问题的割平面以施加更紧的对偶界,但其在资源受限调度中的应用尚待深入探索。对于在不相关并行机上的基于位置的混合整数线性规划(MILP)调度模型,我们注意到某些$k-$OPT邻域可以通过常规局部搜索算子隐式探索,从而允许我们将局部分支集成到分支-检查方案中。通过枚举这些邻域并获得其局部最优解——从而证明它们为次优解——一个局部分支割平面(作为Benders割平面应用)可以一次性消除所有这些解,从而避免主问题中包含成千上万条Benders割平面导致的过载问题。然而,为了保证收敛到最优解,所构建的邻域必须被彻底探索,因此需要通过支配规则或选择性地仅在更可能减少最优性间隙的节点上加速这一耗时过程。本研究将这一思想局限于“内部(作业)交换”以构建特定形式的$4$-OPT邻域。尽管如此,实验结果表明,该方法在两个具有挑战性的调度问题上(即在具有序列依赖和资源约束设置的不相关机器上的总完工时间最小化和总延迟最小化问题)显著减少了最优性间隙或加快了向最优解的收敛速度。我们方法的简单性使其可以推广到其他邻域和不同的排序优化问题,为改进分支-检查方法提供了有前景的前景。

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. Although LBBD offers problem-specific cuts to impose tighter dual bounds, its application to resource-constrained scheduling remains less explored. Given a position-based Mixed-Integer Linear Programming (MILP) formulation for scheduling on unrelated parallel machines, we notice that certain $k-$OPT neighbourhoods could implicitly be explored by regular local search operators, thus allowing us to integrate Local Branching into Branch-and-Check schemes. 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 thousands of 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, the realisation of this idea is limited on the common 'internal (job) swaps' to construct formulation-specific $4$-OPT neighbourhoods. Nonetheless, the experimentation on two challenging scheduling problems (i.e., the minimisation of total completion times and the minimisation of total tardiness on unrelated machines with sequence-dependent and resource-constrained setups) shows that the proposed methodology offers considerable reductions of optimality gaps or faster convergence to optimality. The simplicity of our approach allows its transferability to other neighbourhoods and different sequencing optimisation problems, hence providing a promising prospect to improve Branch-and-Check methods.

一种Benders割平面统治所有邻域调度问题 - arXiv