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

Dynamic programming algorithm for generating optimal layer patterns of rectangular blanks

作　　者：王晓庆[1] 李尚芳[1] 崔耀东[1] 

机构地区：[1]广西师范大学计算机科学与信息工程学院,广西桂林541004

出　　处：《计算机应用研究》2010年第6期2040-2042,2067,共4页Application Research of Computers

基　　金：国家自然科学基金资助项目(60763011);广西科学基金资助项目;广西区研究生教育创新计划资助项目(2009106020812M64)

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

关 键 词：两维切割 剪切 层排样方式 动态规划 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]