生成矩形毛坯最优两段排样方式的确定型算法  

A Deterministic Algorithm for Optimal Two-Segment Cutting Patterns of Rectangular Blanks

作　　者：季君[1] 陆一平[1] 查建中[1] 崔耀东[2] 王金敏[3] 

机构地区：[1]北京交通大学机械与电子控制工程学院,北京100044 [2]广西大学计算机与电子信息学院,南宁530004 [3]天津职业技术师范大学机械工程学院,天津300222

出　　处：《计算机学报》2012年第1期183-191,共9页Chinese Journal of Computers

基　　金：国家自然科学基金(61063031;60975046)资助~~

摘　　要：排样价值、切割工艺和计算时间是排样问题主要考虑的3个因素.文中提出一个新的基于排样模式的确定型排样算法——同质块两段排样算法,此算法适合剪冲下料工艺,在实现工艺简化的同时提高了排样价值时间比.首先通过动态规划算法生成最优同质块,然后求解一维背包问题生成块在级中的最优排样方式和级在段中的最优排样方式,最后选择两个段生成最优的两段排样方式.通过3组经典测题对该文算法进行了测试,将算法与4种著名算法进行了比较.实验结果表明,该文算法的优化结果好于以上4种著名算法,有效地提高了板材利用率,并且计算时间合理.Packing problem should consider three factors of pattern value,cutting techniques and computation time.A new deterministic algorithm is proposed for generating the optimal two-segment cutting patterns for rectangular blanks based on the homogenous block.This paper＇s algorithm is appropriate for the shearing and punching process.Both simple patterns can be obtained and value-to-time can be improved.This algorithm uses a dynamic programming to generate optimal homogenous blocks,solves one-dimensional knapsack problems to obtain the homogenous block layouts on the sections and the section layout on segments,and optimally selects two segments to compose the cutting pattern.The algorithm is tested through three group classic problems,and compares with three famous algorithms.The computational results indicate that this paper＇s algorithm is better than the above four algorithms.The algorithm is efficient in improving material usage,and the computation time is reasonable.

关 键 词：下料 二维无约束排样 同质块 背包问题 动态规划算法 

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