基于匀质块五块模式的矩形件非剪切排样算法

doi:10.12068/j.issn.1005-3026.2018.06.003

东北大学学报:自然科学版 ›› 2018, Vol. 39 ›› Issue (6): 771-775.DOI: 10.12068/j.issn.1005-3026.2018.06.003

基于匀质块五块模式的矩形件非剪切排样算法

张瑞友，潘卫平，刘士新

(东北大学信息科学与工程学院，辽宁沈阳110819)

收稿日期:2017-02-20 修回日期:2017-02-20 出版日期:2018-06-15 发布日期:2018-06-22
通讯作者: 张瑞友
作者简介:张瑞友(1979-)，男，辽宁朝阳人，东北大学副教授，博士生导师；刘士新(1968-)，男，辽宁调兵山人，东北大学教授，博士生导师.冯明杰(1971-)，男，河南禹州人，东北大学副教授; 王恩刚(1962-)，男，辽宁沈阳人，东北大学教授，博士生导师.
基金资助:
国家自然科学基金资助项目(71471034，61573089，71571037)；中央高校基本科研业务费专项资金资助项目(N160404011).国家自然科学基金资助项目(51171041).

Non-guillotine Cutting Algorithm of Rectangular Items Based on Five-Homogeneous-Block Mode

ZHANG Rui-you， PAN Wei-ping， LIU Shi-xin

School of Information Science & Engineering， Northeastern University， Shenyang 110819， China.

Received:2017-02-20 Revised:2017-02-20 Online:2018-06-15 Published:2018-06-22
Contact: PAN Wei-ping
About author:-
Supported by:
-

摘要/Abstract

摘要： 基于匀质块五块排样模式对一类矩形件非剪切排样问题进行了研究.基于动态规划和隐枚举的思想设计了无约束矩形件非剪切排样问题的匀质块五块排样算法.与文献中的矩形件非剪切排样算法的对比试验表明:这种算法能够快速给出问题的最优解，而且可以降低板材切割工艺难度并减少矩形件的分拣成本.与2种矩形件剪切排样算法的对比进一步表明了引入“非剪切”的经济效益.

关键词: 非剪切排样问题, 五块模式, 动态规划算法, 隐枚举

Abstract: A type of non-guillotine cutting problem of rectangular items was studied based on the use of five-homogeneous-block mode. According to the idea of dynamic programming and implicit enumeration， a five-homogeneous-block cutting algorithm for an unconstrained non-guillotine cutting problem was designed. The comparative experiments with existing non-guillotine cutting algorithms indicated that optimal solutions of the problem could be quickly given by this algorithm， and both the difficulty of plate cutting process and the sorting cost of rectangular items could be reduced. Furthermore， comparisons with another experiment with two guillotine cutting algorithms show the benefits of “non-guillotine”.

Key words: non-guillotine cutting problem, five-block mode, dynamic programming algorithm, implicit enumeration

中图分类号:

TP391

张瑞友，潘卫平，刘士新. 基于匀质块五块模式的矩形件非剪切排样算法[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.

参考文献

[1]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.
[2]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.
[3]Cui Y P，Cui Y，Tang T.Sequential heuristic for the two-dimensional bin-packing problem［J］.European Journal of Operational Research，2015，240(1):43-53.
[4]Lodi A，Monaci M，Pietrobuoni E.Partial enumeration algorithms for two-dimensional bin packing problem with guillotine constraints［J］.Discrete Applied Mathematics，2017，217:40-47.
[5]Beasley J E.Algorithms for unconstrained two-dimensional guillotine cutting［J］.Journal of the Operational Research Society，1985，36(4):297-306.
[6]Cui Y，He D，Song X.Generating optimal two-section cutting patterns for rectangular blanks［J］.Computers & Operations Research，2006，33(6):1505-1520.
[7]杨传民，王树人，王心宇.基于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.)
[8]潘卫平，陈秋莲，崔耀东，等.基于匀质条带的矩形件最优三块布局算法［J］.图学学报，2015，36(1):7-11.(Pan Wei-ping，Chen Qiu-lian，Cui Yao-dong，et al.An algorithm for generating optimal homogeneous strips three block patterns of rectangular blanks ［J］.Journal of Graphics，2015，36(1):7-11.)
[9]Fekete S P，Schepers J，Van der Veen J C.An exact algorithm for higher-dimensional orthogonal packing［J］.Operations Research，2007，55(3):569-587.
[10]Egeblad J，Pisinger D.Heuristic approaches for the two-and three-dimensional knapsack packing problem［J］.Computers & Operations Research，2009，36(4):1026-1049.
[11]Birgin E G，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.
[12]易向阳，潘卫平，张俊晖.基于五块模式的单一矩形件排样算法［J］.图学学报，2015，36(4):521-525.(Yi Xiang-yang，Pan Wei-ping，Zhang Jun-hui.Algorithm for generating five block mode cutting patterns of single rectangular items［J］.Journal of Graphics，2015，36(4):521-525.)

[1]	庞彦伟，苏畅，龙涛. 自适应构造与聚合多尺度代价体的双目立体匹配[J]. 东北大学学报（自然科学版）, 2023, 44(4): 457-468.
[2]	丁其川，王力，刘成. 融合长距离信道注意力与病理特征的肺结节分类[J]. 东北大学学报（自然科学版）, 2023, 44(4): 476-485.
[3]	李海燕，熊立昌，郭磊，李海江. 基于U-net边缘生成和超图卷积的两阶段修复算法[J]. 东北大学学报（自然科学版）, 2023, 44(3): 331-339.
[4]	杨丹，刘国如，任梦成，裴宏杨. 多尺度卷积核U-Net模型的视网膜血管分割方法[J]. 东北大学学报（自然科学版）, 2021, 42(1): 7-14.
[5]	韩东红，张宏亮，朱帅伟，齐孝龙. 面向新浪微博的情感社区检测算法[J]. 东北大学学报（自然科学版）, 2021, 42(1): 21-31.
[6]	原培新，陈鼎夫. 双能X射线高动态范围安检图像压缩算法[J]. 东北大学学报（自然科学版）, 2021, 42(1): 96-101.
[7]	魏颖, 徐楚翘, 刁兆富, 李伯群. 基于生成对抗网络的多目标行人跟踪算法[J]. 东北大学学报（自然科学版）, 2020, 41(12): 1673-1680.
[8]	李稷，徐安军. 炼钢车间多天车动态调度仿真方案[J]. 东北大学学报:自然科学版, 2020, 41(12): 1699-1707.
[9]	李占山，吕艾娜. 基于新冗余度的特征选择方法[J]. 东北大学学报:自然科学版, 2020, 41(11): 1550-1556.
[10]	王鑫，王翠荣，王聪，苑迎. 双通道多感知卷积神经网络图像超分辨率重建[J]. 东北大学学报:自然科学版, 2020, 41(11): 1564-1570.
[11]	张春雷，戴丽，刘宇，李鹤. 基于三点法和ICP算法的手术导航系统患者配准[J]. 东北大学学报:自然科学版, 2020, 41(11): 1584-1590.
[12]	陈剑，何涛，闻英友，马林涛. 基于BERT模型的司法文书实体识别方法[J]. 东北大学学报:自然科学版, 2020, 41(10): 1382-1387.
[13]	张田，田勇，王子，王昭东. 基于清晰度评价的自适应阈值图像分割法[J]. 东北大学学报:自然科学版, 2020, 41(9): 1231-1238.
[14]	张丽杰，刘建昌，谭树彬. 复杂建筑火灾中的人员疏散路径多目标规划[J]. 东北大学学报:自然科学版, 2020, 41(6): 761-766.
[15]	赵海，周冰玲，朱宏博，窦圣昶. 基于连续最大流的三维肺实质快速分割算法[J]. 东北大学学报:自然科学版, 2020, 41(4): 470-474.

基于匀质块五块模式的矩形件非剪切排样算法

Non-guillotine Cutting Algorithm of Rectangular Items Based on Five-Homogeneous-Block Mode

RichHTML

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价