锻压技术

多卷材二维下料问题的一种启发式算法

英文标题：A heuristic algorithm for two-dimensional cutting problem with multiple coils

作者：扈少华何宝荣武书彦管卫利

分类号：TP391

出版年,卷(期):页码：2017,42(9):163-167

摘要：

讨论多卷材二维剪切下料问题，即使用多种不同宽度的卷材剪切出若干种一定数量的矩形件，优化目标为材料利用率最高。提出一种顺序启发式下料算法，构造排样方式生成算法，首先根据卷材宽度方向切割废料最小原则，确定矩形件在卷材宽度方向上的排列方式；然后根据卷材长度方向切割废料最小原则，确定卷材的长度以及矩形件在卷材长度方向上的排列方式。按照当前矩形件需求量调用上述排样方式生成算法，生成一个排样方式满足部分矩形件需求量，重复该过程，直到所有矩形件需求量均得到满足为止。采用实际生产中的例题将本文下料算法和文献中排样系统进行比较，数值模拟结果表明：本文算法在优化结果和计算时间两方面均有效。

The problem of two dimensional cutting multiple coils was discussed. It used a variety of different width coils to cut a certain number of rectangles of several kinds, and the optimization goal was to make the material utilization rate reach the maximum. Then, a sequential heuristic algorithm was proposed, and the pattern generation algorithm was constructed. Firstly, the arrangement of rectangle in coil width direction was determined according to the principle of minimum width trim loss, then the coil length and arrangement of rectangle in coil length direction was determined based on the principle of the minimum length trim loss. Furthermore, in view of the current demand on rectangle, the above pattern generation algorithm was applied to generate a pattern so as to meet some demand of rectangle, and the process was repeated until all the rectangle demand satisfied requirements. This sequential heuristic algorithm was compared with the nesting system in literature by practical examples, and numerical experiments show that the algorithms are effective in both optimization results and calculation time.

基金项目：

河南省科技攻关计划项目（142102210607）；广西科学研究与技术开发计划(桂科攻12118017-10A)

作者简介：扈少华（1978-），男，硕士，讲师 E-mail：hshhnmy@163.com 通讯作者：管卫利（1979-），男，硕士，副教授 E-mail：plgh2361@163.com

参考文献：

［1］赵新芳, 崔耀东, 杨莹,等. 矩形件带排样的一种遗传算法[J]. 计算机辅助设计与图形学学报, 2008, 20(4):540-544.

Zhao X F, Cui Y D, Yang Y, et al. A genetic algorithm for the rectangular strip packing problem[J]. Journal of Computer-Aided Design & Computer Graphics, 2008, 20(4):540-544.

［2］何冬黎, 崔耀东. 一种卷板填充分层递归排样的优化算法[J]. 计算机应用, 2008, 28(6):1632-1634.

He D L, Cui Y D. Recursive algorithm for generating layer patterns for strip packing[J]. Computer Applications, 2008, 28(6):1632-1634.

［3］姚怡, 吴金春, 赖朝安. 采用分层搜索填充策略的启发式带排样算法[J]. 武汉大学学报：工学版, 2014, 47(6):854-858.

Yao Y, Wu J C, Lai C A. Heuristics for rectangular strip packing problem based on hierarchical search filled strategy[J].Engineering Journal of Wuhan University,2014, 47(6):854-858.

［4］Wscher G, Hauner H, Schumann H. An improved typology of cutting and packing problems[J]. European Journal of Operational Research, 2007, 183(3):1109-1130.

［5］Belov G, Scheithauer G. A branch-and-cut-and-price algorithm for one-dimensional stock cutting and two-dimensional two-stage cutting[J]. European Journal of Operational Research, 2006, 171(1):85-106.

［6］Silva E, Alvelos F, Carvalho J M V D. An integer programming model for two- and three-stage two-dimensional cutting stock problems[J]. European Journal of Operational Research, 2010, 205(3):699-708.

［7］Macedo R, Alves C, Carvalho J M V D. Arc-flow model for the two-dimensional guillotine cutting stock problem[J]. Computers & Operations Research, 2010, 37(6):991-1001.

［8］Cintra G F, Miyazawa F K, Wakabayashi Y, et al. Algorithms for two-dimensional cutting stock and strip packing problems using dynamic programming and column generation[J]. European Journal of Operational Research, 2008, 191(1):61-85.

［9］易向阳, 仝青山, 潘卫平. 矩形件二维下料问题的一种求解方法[J]. 锻压技术, 2015, 40(6):150-153.

Yi X Y, Tong Q S, Pan W P. A solving method of two-dimensional cutting for the rectangular blanks [J].Forging & Stamping Technology, 2015, 40(6):150-153.

［10］黄少丽, 杨剑, 侯桂玉,等. 解决二维下料问题的顺序启发式算法[J]. 计算机工程与应用, 2011, 47(13):234-237.

Huang S L, Yang J, Hou G Y, et al. Sequential heuristic algorithm for two-dimensional cutting stock problem[J].Computer Engineering and Applications,2011, 47(13):234-237.

［11］梁秋月. 矩形毛坯二维下料问题的解法研究[D].南宁：广西大学, 2015.

Liang Q Y. Research on the Algorthms for Rectangular Two-dimensional Cutting Stock Problem[D].Nanning: Guangxi University,2015.

［12］崔耀东. 计算机排样技术及其应用[M]. 北京：机械工业出版社, 2004.

Cui Y D. Computer Nesting Technology and Its Application [M]. Beijing: China Machine Press,2004.

服务与反馈：

【文章下载】【加入收藏】