Optimal decomposition approach for solving large nesting and scheduling problems of additive manufacturing systems

This paper addresses the challenges associated with nesting and production scheduling in additive manufacturing (AM). The problem studied consists of grouping a set of parts into batches, which are then assigned to and sequenced across the available machines, guaranteeing the production of all parts. This work stands out by proposing exact methods for the AM nesting and scheduling problem considering irregular-shaped parts with specific release dates, processing times, and due dates, with the aim of minimizing the cumulative tardiness. The proposed approaches include two logic-based Benders decompositions: one combining Mixed Integer Programming (MIP) and Constraint Programming (CP), and the other relying solely on CP. To deal with the sub-problems, a strategic procedure was developed to reduce the solution space while maintaining low resolution times per iteration. Problem-specific cuts are also generated to improve the efficiency of these approaches. Computational experiments show that both decompositions significantly outperform a prior monolithic CP model, with the decomposition based solely on CP yielding the best results. Moreover, the results show that this approach has the potential to achieve similar computational performance of non-exact approaches that are currently considered state-of-the-art. A set of instances is provided to serve as a benchmark for future studies.