Improving the efficiency of logic-based benders decomposition for p-batch scheduling problems with two-dimensional packing

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%.