圆片剪冲下料排样算法  

Packing algorithm for circle cutting stock problem

作　　者：杨剑[1] 黄少丽[1] 侯桂玉[1] 崔耀东[1] 

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

出　　处：《计算机工程与设计》2010年第23期5139-5142,共4页Computer Engineering and Design

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

摘　　要：为解决圆片剪冲下料排样精确算法的运行时间过长问题,并综合考虑在保证所生成的排样方案利用率最优或接近最优的前提下,先采用动态规划算法,在精确算法的基础上,选取规范长度和规范宽度的子集进行计算,实现无约束算法,解决剪切阶段的无约束排样问题。再与线性规划方法相结合,解决两维圆片剪冲下料问题,使整个排样方案的利用率达到最大,所耗费的板材数最少。最后通过实验结果表明了该算法的有效性。To solve the problem of taking too long time for running the exact algorithm for the circle cutting stock problem,and to guaranty the utilization of the generated pattern is the best or almost the best,the dynamic programming is adopted,and based on the exact algorithm,the subset of normal size is chosen to calculate the result in the unconstrained algorithm.Then the linear programming is applied to solve the two-dimensional cutting stock problem,in order to make the utilization of the pattern reach its maximum,the number of plate is used the least.The computational results showed the effectiveness of the presented algorithm.

关 键 词：二维下料 圆片排样 剪冲下料 动态规划算法 线性规划 

分 类 号：TP391.73[自动化与计算机技术—计算机应用技术]