Benders decompositions for order acceptance and scheduling in additive manufacturing

We study an order acceptance and parallel machine scheduling problem appearing in additive manufacturing (AM) considering two-dimensional packing with part rotation. Three joint decisions, including order acceptance, build formation and schedule construction, are made to maximize the revenue of accepted orders minus a weighted makespan, thereby capturing the trade-off between profitability and production efficiency. First, two mixed integer programming models (MIP) are formulated to optimize the three mentioned decisions simultaneously. Then, due to the specific structure of the problem, we propose a general logic-based Benders decomposition (LBBD) approach and a nested logic-based Benders decomposition (NLBBD) approach with various Benders cuts and search strategies. Finally, we undertake a comprehensive computational study to validate the effectiveness of all the proposed approaches. The computational results show that NLBBD achieves 50 % more optimal solutions than MIP models implemented in Gurobi and 35 % more than LBBD for small-sized instances. For large-sized instances, NLBBD still achieves better solutions with smaller gaps compared to Gurobi and LBBD. Further, numerical experiments confirm the effectiveness of the designed additional cuts and search strategies applied in Benders decompositions.