Two-Dimensional Cutting and Packing Problems in the Sheet Metal Industry

This thesis addresses real-world optimization problems in the sheet metal industry, where decision-making involves various operations to process raw material into finished objects. These processes can include cutting operations on material plates, as well as bending, assembly, and storage of the cut objects. Optimization goals typically aim to minimize material waste, reduce processing time, or maximize the efficiency of downstream operations. Salvagnini Italia S.p.A. is a leading company in the sheet metal industry, providing cutting and bending machines, along with specialized software that offers automated solutions to the aforementioned problems. This thesis focuses on Salvagnini's cutting machines, and, specifically, on the problem of generating cutting layouts for rectangular objects. This involves placing items to be cut into available material sheets in a way that minimizes waste. The problem incorporates both general and specific constraints arising from the technologies used by the reference company, creating a complex scenario that extends beyond standard formulations in the literature. In this regards, the problem presents specific attributes such as the presence of optional items to cut, production precedence among items, and required safety distances to maintain cut quality or optimize shared cuts. The aim of our research is to develop a solution method for the problem under study that is applicable to real-world scenarios. Moreover, we seek to ensure that this method is competitive with the current third-party software used by the company, offering a viable alternative solution procedure. Various approaches have been explored, including exact methods, heuristics, and matheuristics. Among these, a heuristic approach based on a beam search algorithm proved itself to be particularly effective, delivering high-quality solutions with the required speed for practical industrial use. The beam search algorithm's performance makes it a valid alternative to the existing software, balancing execution time and solution quality. Concerning the other methods explored in this thesis, they provided valuable insights into the problem's specific challenges. These methods offer different perspectives on the problem and can be effective in particular scenarios, underscoring the need for diverse solutions tailored to varying conditions. Additionally, this research investigates an irregular variant of the problem, where the items to be cut are irregularly shaped. In this context, we explore the integration of a recently proposed framework to handle the geometric aspects of the problem, comparing it with more established geometric tools from the literature. Although this extension is still under development, preliminary results are promising and induce significant industrial interest. The irregular variant introduces new challenges, especially related to managing the geometric complexity of the shapes, but it also holds potential for enhancing flexibility and efficiency in production processes. Future work will focus on further refining the beam search algorithm, including leveraging more parallel computing to better optimize computational efficiency. Moreover, additional efforts will be directed towards testing and improving the irregular variant, integrating it with real-world attributes, and comparing it with existing methods to ensure practical applicability. The thesis contributes to the field of cutting and packing problems by addressing real-world attributes and developing advanced solution methods to be integrated into real cutting environments. The thesis also provides practical benchmarks from the reference company, and highlights the beam search algorithm as a robust tool for industrial applications. The exploration of the irregular variant paves the way for future research and practical implementation, offering valuable implications for both academic research and industrial purposes.