Improving the efficiency of logic-based benders decomposition for p-batch scheduling problems with two-dimensional packing
针对增材制造中带二维装箱的p-批调度问题，提出五种加速方法，使逻辑Benders分解求解时间在30零件实例中降低一个数量级，120零件实例在1小时内最优解率从不足4%提升至100%。
To improve the performance of Logic-based Benders Decomposition (LBBD) approaches, it is important to exploit the structure of the problem being solved. This paper develops a range of acceleration methods to improve the performance of LBBD approaches for the p-batch scheduling problem with two-dimensional (2D) packing in Additive Manufacturing (pBS-AM). The main ideas include: (1) dynamic approximation of the subproblems in the master problem to balance approximation tightness without excluding optimal solutions, (2) a prioritization mechanism based on criticality indices to obtain master problem solutions more likely to lead to feasible subproblems, (3) failure-directed variable and value ordering heuristics to accelerate the identification of infeasible subproblems, (4) generation of stronger cuts via irreducible and greedy approaches, and (5) reutilization of subproblem infeasibility information to avoid redundant subproblem evaluations. While developed for the pBS-AM, these methods generalize to other p-batch scheduling problems with 2D packing since they act on the general structure of the problem rather than features specific to Additive Manufacturing. Computational results show that these methods reduce run times by more than an order of magnitude in 30-part instances and increase the percentage of 120-part instances solved to optimality within the time limit of one hour from under 4% to 100%.