生成圆形片最优四块排样方式的确定性算法  

Deterministic Algorithm for Generating Four-Block Cutting Patterns of Circular Blanks

作　　者：王岩 潘卫平[2] 胡钢[3] 

机构地区：[1]南通理工学院软件工程系,江苏南通226002 [2]广西大学计算机与电子信息学院,广西南宁530004 [3]四川信息职业技术学院,四川广元628017

出　　处：《机械设计与制造》2015年第9期152-155,共4页Machinery Design & Manufacture

基　　金：国家自然科学基金资助项目(11461038)

摘　　要：为解决圆形片无约束剪冲排样问题,提出一个生成圆形片最优四块排样方式的确定性算法。四块排样方式首先用一条父分界线将板材分为两块,然后用两条与父分界线垂直的子分界线将两块分为四块;每个块里面只包含方向和长度均相同的圆形片条带。该算法首先求解一维背包问题生成块里面的条带最优布局;然后隐式枚举三条分界线位置得到所有可能的四块组合,选择排样价值最大的四块组合生成最优的四块排样方式。实验结果表明,该算法在计算时间和板材利用率两方面都有效。In order to solve the unconstrained circle cutting problem, it presents an optimal algorithm for generating fourblock cutting patterns of circle. It uses three cutting line to divide the sheet into four blocks, each of which contains circle strips of the same direction and length. The algorithm first solves one-dimensional knapsack problem to generates strip layout in this block, and finally four different block combinations obtained by implicit enumeration three cutting line position, choose the four composite which can make the sheet have a maximum value to generate the optimal four block layout. The experimental results show that, the algorithm is efficient in both the computation time and the material utilization rate.

关 键 词：圆形片 剪冲排样 四块排样方式 背包问题 最优布局 

分 类 号：TH16[机械工程—机械制造及自动化] TP391[自动化与计算机技术—计算机应用技术]