关键词:两维切割; 剪切; 层排样方式; 动态规划
Dynamic programming algorithm for generating optimal layer patterns of rectangular blanks
WANG Xiao-qing, LI Shang-fang, CUI Yao-dong
(School of Computer Science & Information Engineering, Guangxi Normal University, Guilin Guangxi 541004, China)
Abstract:Focusing on the unconstrained two-dimensional guillotine cutting problem of rectangular blanks, this paper proposed a dynamic programming algorithm to generate layer patterns, making the total value of the blanks included in the plant reach its maximum. The algorithm divided the plate into layers with horizontal cuts. The length of the cuts was equal to the length or width of the plate, the width was the same as the height of the leftmost blank in the layer. The dynamic programming algorithm determined the optimal value of all the layers and the optimal combination of the layers included in the plate. The computational results indicate that the algorithm can satisfy the requirement of actual application and is efficient both in material utilization and in computation time.......