For the rectilinear parts cutting problem of low sheet utilization rate in practice, the concept of layout rectangle is introduced. The rectilinear parts cutting problem is decomposed into several optimization sub-problems. On this basis, the global optimal solution is constructed by solving the sub-problems based on dynamic programming. Experiment shows that compared with the traditional method of rectilinear parts cutting, the sheet utilization rate can be increased by 30%–50%. Compared with other typical algorithms, the sheet utilization rate is significantly improved and the scheme is more practical to layout.
[3] Moretti AC, de Salles Neto LL. Nonlinear cutting stock problem model to minimize the number of different patterns and objects. Computational & Applied Mathematics, 2008, 27(1): 61–78
[4] Afsharian M, Niknejad A, Wäscher G. A heuristic, dynamic programming-based approach for a two-dimensional cutting problem with defects. OR Spectrum, 2014, 36(4): 971–999. [doi: 10.1007/s00291-014-0363-x
[9] Hartmanis J. Computers and intractability: A guide to the theory of NP-completeness (Michael R. Garey and David S. Johnson). SIAM Review, 1982, 24(1): 90–91
[10] Belov G, Kartak V M, Rohling H, et al. Conservative scales in packing problems. OR Spectrum, 2013, 35(2): 505–542. [doi: 10.1007/s00291-011-0277-9
[13] Cui YD, Huang BX. Reducing the number of cuts in generating three-staged cutting patterns. European Journal of Operational Research, 2012, 218(2): 358–365. [doi: 10.1016/j.ejor.2011.10.047
[14] Korte B, Vygen J. The knapsack problem. In: Korte B, Vygen J, eds. Combinatorial Optimization: Theory and Algorithms. Berlin Heidelberg: Springer, 2012. 459–470.