Study on Optimization of Three-Stage Sheet Nesting with Integration of Virtual Component Construction and Greedy Algorithm

Abstract

Nesting optimization problems are critical in the industrial manufacturing sector, playing a significant role in cost control and resource conservation. This paper focuses on the nesting problem presented in the first question of the 2022 “China Optics Valley Huawei Cup” Postgraduate Mathematical Modeling Competition, B Question. A three-stage nesting model based on a greedy algorithm is constructed. The specified cutting method is “flush cutting” with a maximum of three stages and consistent cutting line directions within the same stage. Factors such as saw blade width are not considered. By concatenating products with the same width or length into virtual components and processing products in descending order, the algorithm prioritizes placing the longest product available at the bottom left corner of the original sheet, updating the nesting space in stages. Experiments on datasets A1-A4 demonstrate that this algorithm achieves a material utilization rate exceeding 94%, providing an efficient solution for two-dimensional nesting optimization.