二维板材圆形件剪冲的四块排样算法

doi:10.12068/j.issn.1005-3026.2021.11.018

东北大学学报（自然科学版） ›› 2021, Vol. 42 ›› Issue (11): 1650-1655.DOI: 10.12068/j.issn.1005-3026.2021.11.018

二维板材圆形件剪冲的四块排样算法

潘卫平¹，樊治平¹，黄敏^2,3

(1. 东北大学工商管理学院，辽宁沈阳110169; 2. 东北大学信息科学与工程学院，辽宁沈阳110819;3.东北大学流程工业综合自动化国家重点实验室，辽宁沈阳 110819)

修回日期:2020-11-17 接受日期:2020-11-17 发布日期:2021-11-19
通讯作者: 潘卫平
作者简介:潘卫平(1989-)，男，湖北黄冈人，东北大学博士后研究人员；樊治平(1961-)，男，江苏镇江人，东北大学教授，博士生导师；黄敏(1968-)，女，福建长乐人，东北大学教授，博士生导师.
基金资助:
国家自然科学基金资助项目(71871049)；国家自然科学基金重点国际合作研究项目(71620107003)；辽宁省“兴辽英才计划”项目(XLYC1802115)；流程工业综合自动化国家重点实验室基础科研业务费资助项目(2013ZCX11)；东北大学博士后基金资助项目(01270012810165)；中央高校基本科研业务费专项资金资助项目(N2106008).

Four-Block Layout Algorithm for Two-Dimensional Plate Shearring and Punching of Circular Parts

PAN Wei-ping¹， FAN Zhi-ping¹， HUANG Min^2,3

1. School of Business Administration， Northeastern University， Shenyang 110169， China; 2. School of Information Science & Engineering， Northeastern University， Shenyang 110819， China; 3. State Key Laboratory of Synthetical Automation for Process Industries， Northeaastern University， Shenyang 110819， China.

Revised:2020-11-17 Accepted:2020-11-17 Published:2021-11-19
Contact: PAN Wei-ping
About author:-
Supported by:
-

摘要/Abstract

摘要： 针对二维板材圆形件剪冲下料问题，提出一种基于四块排样方式的下料算法.这种排样方式将一张板材划分成四个块，在每块中排放具有相同长度和方向的条带;条带中排放若干行同种圆形件.构造排样算法生成单张板材上圆形件的四块排样方式，首先确定圆形件在条带中的布局;然后构造递归算法生成条带在块中的布局;最后采用隐式枚举算法确定板材的最优四块划分.采用列生成算法调用上述排样方法生成多个不同的排样方式，按照单纯型原理择优选择一组排样方式形成下料方案，并对小数解进行圆整操作.使用文献例题和实际生产实例将本文算法与文献算法进行对比，结果表明: 本文算法下料方案板材利用率比四种文献算法分别高0.49%， 0.32%， 6.04%和1.50%，计算时间能满足实际应用需要.

关键词: 剪冲排样;四块排样算法;递归算法;列生成算法;板材;圆形件

Abstract: A cutting stock algorithm based on four-block layout was proposed to solve the two-dimensional plate shearring and punching of circular parts. With this layout， a sheet was divided into four blocks. Only the strips with the same direction and length were arranged in each block， and several rows of the same circular parts were arranged in the strips. A four block layout method for generating circular parts on a single sheet by constructing a layout algorithm. Firstly， the layout of circular parts in the strips was determined. Secondly， recursive algorithm was constructed to generate the layout of the strips in blocks. Finally， implicit enumeration algorithm was used to determine the optimal four-block partition. The column generation algorithm was used to call the above layout algorithm to generate a number of different layouts. Based on the simplex principle， a group of layouts were selected to form the cutting plan， and the decimal solution was rounded. The results showed that the plate utilization ratio of the algorithm in the study is 0.49%， 0.32%， 6.04% and 1.50% higher than those of the four literature algorithms， respectively， and the calculation time can meet the needs of practical applications.

Key words: shearring and punching layout; four-block layout algorithm; recursive algorithm; column generation algorithm; plate; circular part

中图分类号:

TH164

潘卫平，樊治平，黄敏. 二维板材圆形件剪冲的四块排样算法[J]. 东北大学学报（自然科学版）, 2021, 42(11): 1650-1655.

PAN Wei-ping， FAN Zhi-ping， HUANG Min. Four-Block Layout Algorithm for Two-Dimensional Plate Shearring and Punching of Circular Parts[J]. Journal of Northeastern University(Natural Science), 2021, 42(11): 1650-1655.

参考文献

[1]Cui Y.Generating optimal T-shape cutting patterns for circular blanks［J］.Computers & Operations Research，2005，32(1):143-152.
[2]张瑞友，潘卫平，刘士新.基于匀质块五块模式的矩形件非剪切排样算法［J］.东北大学学报(自然科学版)，2018，39(6):771-775.(Zhang Rui-you，Pan Wei-ping，Liu Shi-xin.Non-guillotine cutting algorithm of rectangular items based on five-homogeneous-block mode［J］.Journal of Northeastern University(Natural Science)，2018，39(6):771-775.)
[3]侯桂玉，崔耀东，黄少丽，等.一种求解圆形件下料问题的启发式算法［J］.计算机工程，2010，36(13):227-229.(Hou Gui-yu，Cui Yao-dong，Huang Shao-li，et al.Heuristic algorithm for cutting stock problem of circular item［J］.Computer Engineering，2010，36(13):227-229.)
[4]王峰，张军，胡钢.圆形片剪冲下料问题的一种求解算法［J］.锻压技术，2015，40(10):39-44.(Wang Feng，Zhang Jun，Hu Gang.An algorithm for solving the shearing problem of circular blanks［J］.Forging & Stamping Technology，2015，40(10):39-44.)
[5]Cui Y，Huang B.A heuristic for constrained T-shape cutting patterns of circular items［J］.Engineering Optimization，2011，43(8):867-877.
[6]Cui Y，Gu T，Hu W.A bi-objective guillotine cutting problem of stamping strips of equal circles［J］.International Journal of Computer Mathematics，2010，87(12):2716-2721.
[7]Furini F，Malaguti E.Models for the two-dimensional two-stage cutting stock problem with multiple stock size［J］.Computers & Operations Research，2013，40(8):1953-1962.
[8]Silva E，Alvelos F，Carvalho J.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.
[9]Chen Q，Cui Y，Chen Y.Sequential value correction heuristic for the two-dimensional cutting stock problem with three-staged homogenous patterns［J］.Optimization Methods and Software，2016，31(1):68-87.
[10]Cui Y，Yao Y，Cui Y P.Hybrid approach for the two-dimensional bin packing problem with two-staged patterns［J］.International Transactions in Operational Research，2016，23(3):539-549.
[11]胡钢，杨瑞，潘立武.基于价值修正的圆片下料顺序启发式算法［J］.图学学报，2016，37(3):337-341.(Hu Gang，Yang Rui，Pan Li-wu.Sequential value correction heuristic algorithm for the circle cutting stock problem［J］.Journal of Graphics，2016，37(3):337-341.)
[12]Cui Y，Wang Q.Exact and heuristic algorithms for the circle cutting problem in the manufacturing industry of electric motors［J］.Journal of Combinatorial Optimization，2007，14(1):35-44.
[13]Birgin E，Lobato R，Morabito R.Generating unconstrained two-dimensional non-guillotine cutting patterns by a recursive partitioning algorithm［J］.Journal of the Operational Research Society，2012，63(2):183-200.
[14]Dolatabadi M，Lodi A，Monaci M.Exact algorithms for the two-dimensional guillotine knapsack［J］.Computers & Operations Research，2012，39(1):48-53.
[15]Pedroso J，Cunha S，Tavares J.Recursive circle packing problems［J］.International Transactions in Operational Research，2016，23(1/2):355-368.
[16]Cui Y.Dynamic programming algorithms for the optimal cutting of equal rectangles［J］.Applied Mathematical Modeling，2005，29(11):1040-1053.
[17]Ozlen M，Burton B，MacRae C.Multi-objective integer programming:an improved recursive algorithm［J］.Journal of Optimization Theory and Applications，2014，160(2):470-482.
[18]杨传民，王树人，王心宇.基于4块结构的斩断切割布局启发性算法［J］.机械设计，2007，24(2):25-26.(Yang Chuan-min，Wang Shu-ren，Wang Xin-yu.Heuristic algorithm on layout of chopped cutting based on 4 pieces of structure［J］.Journal of Machine Design，2007，24(2):25-26.)

二维板材圆形件剪冲的四块排样算法

Four-Block Layout Algorithm for Two-Dimensional Plate Shearring and Punching of Circular Parts

RichHTML

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

[1]	王海艳，王健宇，陶克新. 碳纤维复合材料螺旋铣孔瞬时切削力系数识别[J]. 东北大学学报:自然科学版, 2020, 41(10): 1432-1437.
[2]	张耀满，李万鹏，杨铭宇. 球头铣刀加工钛合金零件的铣削力特性[J]. 东北大学学报:自然科学版, 2020, 41(6): 852-857.
[3]	牛艺静，孙聪，庞刚，修世超. 预应力时效性对磨削强化表面应力的影响[J]. 东北大学学报:自然科学版, 2020, 41(4): 546-550.
[4]	孙聪，李清良，修世超，刘宏伟. 端面磨削加工工件表面材料的去除机理[J]. 东北大学学报:自然科学版, 2020, 41(3): 393-398.
[5]	黎柏春，王振宇，张斌，王宛山. 球头铣刀切削刃存在差异的切削力系数辨识[J]. 东北大学学报:自然科学版, 2019, 40(9): 1316-1322.
[6]	张荣闯，黎柏春，张景强. 圆柱齿轮滚齿切削力的预测[J]. 东北大学学报:自然科学版, 2019, 40(7): 980-985.
[7]	王博，黎柏春，杨建宇，王宛山. 面向球头铣刀多轴铣削加工的铣削力系数辨识[J]. 东北大学学报:自然科学版, 2018, 39(11): 1630-1635.
[8]	王琳，张永健，钟诗胜. 基于UML和XML的工艺族信息模型表达方法[J]. 东北大学学报:自然科学版, 2016, 37(6): 839-844.
[9]	黎柏春，王振宇，王国勋，王宛山. 基于瞬时铣削力的球头铣刀铣削力系数辨识[J]. 东北大学学报:自然科学版, 2016, 37(5): 678-682.
[10]	盛忠起，徐涛，旋嘉耀，宋均有. 基于遗传算法的数控机床服务模块配置设计[J]. 东北大学学报:自然科学版, 2015, 36(6): 848-852.
[11]	张荣闯，王宛山，王军. 滚齿切削厚度仿真计算[J]. 东北大学学报:自然科学版, 2015, 36(1): 95-99.
[12]	陈亚东，马国强，尚德浩，王宛山. 基于ABAQUS的下颌骨生物力学分析[J]. 东北大学学报:自然科学版, 2014, 35(3): 423-428.
[13]	张锴锋，袁惠群，聂鹏. 基于广义维数与优化BP神经网络的刀具磨损量预测[J]. 东北大学学报(自然科学版), 2013, 34(9): 1292-1295.
[14]	修世超，卢跃，孙聪，李清良. 端面磨削动态热力耦合效应及对表面去除过程影响[J]. 东北大学学报（自然科学版）, 2021, 42(3): 389-395.
[15]	姚云龙，修世超，孙聪，洪远. 基于40Cr高温动态力学性能的磨削表面动态再结晶行为[J]. 东北大学学报（自然科学版）, 2021, 42(8): 1120-1126.