冲裁条带最优多段排样方式的动态规划算法

计算机工程与应用 ›› 2011, Vol. 47 ›› Issue (34): 238-241.

冲裁条带最优多段排样方式的动态规划算法

李尚芳1，崔耀东2，王晓庆1

1.广西师范大学计算机科学与信息工程学院，广西桂林 541004
2.广西大学计算机与电子信息学院，南宁 530004

收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2011-12-01 发布日期:2011-12-01

Dynamic programming algorithm for optimal multiple-segment patterns of punched strips

LI Shangfang1，CUI Yaodong2，WANG Xiaoqing1

1.School of Computer Science and Information Engineering，Guangxi Normal University，Guilin，Guangxi 541004，China
2.School of Computer and Electronics Information，Guangxi University，Nanning 530004，China

Received:1900-01-01 Revised:1900-01-01 Online:2011-12-01 Published:2011-12-01

摘要/Abstract

摘要： 讨论冲裁件无约束剪冲排样问题，用动态规划算法生成冲裁条带多段排样方式。采用一组相互平行的分割线将板材分成多个段，每段含一组方向和长度都相同的条带。通过动态规划算法确定所有可能尺寸段的最优价值以及板材中段的最优组合，使整张板材价值达到最大。实验结果表明该算法能够提高材料利用率，计算时间能满足实际应用的需要。

关键词: 冲裁件, 剪冲下料, 排样, 二维切割, 多段排样方式

Abstract: Focusing on the unconstrained two-dimensional cutting and punching problem of punched blanks，a dynamic programming algorithm is proposed for generating multiple-segment cutting patterns of punched strips.The stock sheet is divided into segments by dividing cuts which are perpendicular to each other.Each segment contains a group of strips which have the same orientation and length.The dynamic programming algorithm determines the optimal value of all the segments and the optimal combination of the segments included in the plate so as to maximize the value of the whole sheet.Computational results indicate that the algorithm can improve the material usage，and the computation time of the algorithm is reasonable for practical use.

Key words: punched blanks, cutting and punching, nesting, two-dimensional cutting, multiple-segment pattern

李尚芳1，崔耀东2，王晓庆1. 冲裁条带最优多段排样方式的动态规划算法[J]. 计算机工程与应用, 2011, 47(34): 238-241.

LI Shangfang1，CUI Yaodong2，WANG Xiaoqing1. Dynamic programming algorithm for optimal multiple-segment patterns of punched strips[J]. Computer Engineering and Applications, 2011, 47(34): 238-241.

[1]	夏以冲，陈秋莲，宋仁坤. 基于自适应遗传模拟退火算法的矩形件排样[J]. 计算机工程与应用, 2018, 54(22): 229-232.
[2]	孙佳正，郭骏. 改进的双种群遗传算法在矩形件排样中的应用[J]. 计算机工程与应用, 2018, 54(15): 139-146.
[3]	陈秋莲1，2，王成栋2. 二维剪切排样的束搜索启发式算法[J]. 计算机工程与应用, 2017, 53(9): 236-239.
[4]	王严欣，崔耀东，李华. 应用精确两阶段排样图的板材下料算法[J]. 计算机工程与应用, 2017, 53(5): 236-240.
[5]	杨卫波1，2，王万良1，张景玲3，赵燕伟3. 基于遗传模拟退火算法的矩形件优化排样[J]. 计算机工程与应用, 2016, 52(7): 259-263.
[6]	曾兆敏1，管卫利2，潘卫平3. 冲裁件条料最优四块剪切下料方案的生成算法[J]. 计算机工程与应用, 2016, 52(20): 75-79.
[7]	郑明月1，刘林1，2，阚方1，方昶1. 结合批量问题的多目标矩形件优化排样[J]. 计算机工程与应用, 2014, 50(22): 260-264.
[8]	钟相强. 基于成组原理的船舶件排样系统研究[J]. 计算机工程与应用, 2014, 50(15): 194-198.
[9]	杨卫波1，2，王万良2. 改进临界多边形生成算法[J]. 计算机工程与应用, 2013, 49(1): 32-35.
[10]	许继影. 矩形件优化排样的混合启发式方法[J]. 计算机工程与应用, 2012, 48(13): 234-239.
[11]	刘睿¹，严玄²，崔耀东². 矩形件三阶段带排样问题的遗传算法[J]. 计算机工程与应用, 2010, 46(33): 221-224.
[12]	彭文. 一种快速的有约束矩形件优化排样模型[J]. 计算机工程与应用, 2010, 46(27): 214-216.
[13]	陈仕军，曹炬. 矩形件优化排样的一种启发式算法 [J]. 计算机工程与应用, 2010, 46(12): 230-232.
[14]	宋亚男¹，徐荣华¹，杨宜民¹，叶家玮². 混合算法在排样问题上的应用研究[J]. 计算机工程与应用, 2009, 45(34): 17-20.
[15]	梁利东,叶家玮. 基于遗传算法的不规则件优化排样研究 [J]. 计算机工程与应用, 2009, 45(2): 223-224.