矩形毛坯最优层排样方式的动态规划算法*

讨论矩形毛坯无约束二维剪切排样问题，提出层排样方式的动态规划算法，使板材所含毛坯总价值最大。排样时使用一组平行的剪切线将板材分割为多个层，层的长度等于板材的长度或宽度，宽度等于最左边主毛坯的高度。通过动态规划算法确定所有可能尺寸层的最大价值和板材中层的最优组合。实验结果表明,该算法在满足实际应用要求的同时，板材利用率和计算时间两方面都较有效。

Dynamic programming algorithm for generating optimal layer patterns of rectangular blanks

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.