Jun Ji, Fei-fei Xing, Dan Su, Yao-dong Cui, Journal of Information Processing Systems Vol. 22, No. 1, pp. 49-61, Feb. 2026  

https://doi.org/10.3745/JIPS.01.0115
Keywords: Dynamic programming, Layout Value, Rectangular, Two-Dimensional Packing
Fulltext: PDF Full Text PubReader

Abstract

The unconstrained two-dimensional cutting stock problem is a typical NP-hard problem with high complexity. When generating the layout, both the utilization rate of the sheet and simplification of the cutting process must be considered. This study presents an algorithm for generating a same-size T-shape layout. The same-size T-shape layout is suitable for the cutting and punching processes in actual production. It includes two segments in different directions, each consisting of strips of only one size and direction. First, the algorithm determines the optimal same-size strip through dynamic programming; subsequently, it determines the layout of the same-size strip in the composite strip and the composite strip in the segment by solving the knapsack problem. Finally, two segments are selected to generate the layout with the highest piece value. Using 37 benchmark test problems from the literature, the proposed algorithm was compared with four advanced and effective layout algorithms. Our algorithm achieved optimal results for 16 test problems, and the ratio of the calculated results to the optimized results for the remaining test problems reached 99.9%. The average calculation time for each test problem was only 1.3 seconds. The experimental results indicate that the proposed algorithm offers advantages in terms of the computation time and sheet utilization rate. The algorithm not only achieves good optimization results within a reasonable time but also simplifies the cutting process while meeting the engineering requirements.

Statistics
Cite this article