生成最优同形块两阶段布局方式的确定型算法

doi:10.11772/j.issn.1001-9081.2014.05.1511

计算机应用 ›› 2014, Vol. 34 ›› Issue (5): 1511-1515.DOI: 10.11772/j.issn.1001-9081.2014.05.1511

生成最优同形块两阶段布局方式的确定型算法

季君¹,邢斐斐²,杜钧¹,师宁¹,崔耀东³

1. 北京电子科技职业学院自动化工程学院,北京 100176;
2. 北京机电院高技术股份有限公司,北京 100027;
3. 广西大学计算机与电子信息学院,南宁 530004

收稿日期:2013-10-12 修回日期:2013-11-14 出版日期:2014-05-01 发布日期:2014-05-30
通讯作者: 季君
作者简介:季君(1979-),女,山东泰安人,讲师,博士,主要研究方向:智能设计与布局、优化计算;
邢斐斐(1981-),女,山东济南人,工程师,博士,主要研究方向:智能设计与布局、机械制造及其自动化;
杜钧(1965-),女,山西太原人,副教授,硕士,主要研究方向:计算机辅助设计、机械制造及其自动化;
师宁(1981-),女,河北邢台人,讲师,硕士,主要研究方向:控制理论及控制工程、计算机辅助设计;
崔耀东(1957-),男,河南林州人,教授,博士,主要研究方向:优化计算、计算机辅助设计。
基金资助:
国家自然科学基金资助项目;北京电子科技职业学院科研项目

Deterministic algorithm for optimal two-stage cutting layouts with same-shape block

JI Jun¹,XING Feifei²,DU Jun¹,SHIning ¹,CUI Yaodong³

1. School of Mechanical, Electronic and Control Engineering, Beijing Polytechnic, Beijing 100176, China
2. Hi-Tech Company Limited, Beijing Machinery and Electricity Institute, Beijing 100027, China
3. School of Computer, Electronics and Information, Guangxi University, Nanning Guangxi 530004, China

Received:2013-10-12 Revised:2013-11-14 Online:2014-05-01 Published:2014-05-30
Contact: JI Jun

摘要/Abstract

摘要：

为解决大规模二维布局问题,提出一种生成同形块两阶段布局方式的确定型算法。首先通过动态规划确定最优同形块；然后求解背包问题确定同形块在同形级中的布局方式和同形级在同形段中的最优布局方式；最后选择两个同形段生成最优同形块布局方式。通过43道基准测题,将该算法与经典两阶段和三块算法进行比较。实验结果表明,该算法不仅能满足剪切工艺,在计算时间和板材利用率上优于以上算法,而且能在合理时间内取得好的优化结果。

Abstract:

A deterministic algorithm for two-stage cutting layout with same-shape block was proposed to solve the large-scale two-dimensional cutting problems. The algorithm used dynamic programming to generate the optimal same-shape block, solved the knapsack problem to determine the optimal layout of the same-shape block in the same-shape section and the same-shape section in the same-shape segment, and optimally selected the two segments to compose the optimal same-shape block layout. The algorithm was tested through 43 benchmark problems, and compared with the classic two-stage and the three-block algorithms. The experimental results indicate that the algorithm is superior in both computation time and material usage rate, it not only meets the requirements of shearing and punching process, but also achieves good results within reasonable time.

中图分类号:

TP391

季君邢斐斐杜钧师宁崔耀东. 生成最优同形块两阶段布局方式的确定型算法[J]. 计算机应用, 2014, 34(5): 1511-1515.

JI Jun XING Feifei DU Jun SHIning CUI Yaodong. Deterministic algorithm for optimal two-stage cutting layouts with same-shape block[J]. Journal of Computer Applications, 2014, 34(5): 1511-1515.

参考文献

［1］JI J, LU Y, ZHA J. Exact algorithm for generating optimal homogenous strip T-shape layouts ［J］. Journal of Computer Applications, 2012,32(9):2634-2637. (季君,陆一平,查建中.生成最优单毛坯条带T型布局方式的精确算法［J］.计算机应用,2012,32(9):2634-2637.)［2］JIANG X, LYU X, LIU C. Lowest-level left align best-fit algorithm for the 2D rectangular strip packing problem ［J］. Journal of Software, 2009,20(6):1528-1538. (蒋兴波,吕肖庆,刘成城.二维矩形条带装箱问题的底部左齐择优匹配算法［J］. 软件学报, 2009,20(6):1528-1538.)［3］JIANG Y, YANG Z, ZHANG C. Two-stage segment optimal packing of single size rectangle ［J］. Journal of Computer Applications, 2011,31(6):1689-1691. (姜永亮,杨志强,张诚一.基于两阶段的分段单一毛坯矩形优化排样［J］.计算机应用,2011,31(6):1689-1691.)［4］JI J, LU Y, ZHA J,et al. A deterministic algorithm for optimal two-segment cutting patterns of rectangular blanks［J］. Chinese Journal of Computers, 2012, 35(1): 183-291. (季君,陆一平,查建中,等.生成矩形毛坯最优两段布局方式的确定型算法［J］.计算机学报,2012, 35(1):183-191.)［5］GILMORE P C, GOMORY R E. Multistage cutting stock problem of two and more dimensions ［J］. Operations Research, 1965, 13（1）: 94-120.［6］WANG Y,SHI Y,TENG H. An improved scatter search for circles packing problem with the equilibrium constraint ［J］. Chinese Journal of Computers, 2009, 32(6): 1214-1220. (王奕首,史彦军,滕弘飞.用改进的散射搜索法求解带平衡约束的圆形Packing问题［J］.计算机学报,2009,32(6):1214-1220.)［7］HUANG W, LIU J. A deterministic heuristic algorithm based on Euclidian distance for solving the rectangles packing problem ［J］. Chinese Journal of Computers, 2006, 29(5): 735-739. (黄文奇,刘景发.基于欧氏距离的矩形Packing问题的确定性启发式求解算法［J］. 计算机学报,2006,29(5):735-739.)［8］CUI Y, HUANG J, ZHANG X. Recursive algorithm for unconstrained two-dimensional guillotine cutting problem of rectangular pieces ［J］. Journal of Computer-Aided Design and Computer Graphics, 2006,18(7): 948-951. (崔耀东,黄健民,张显全.矩形毛料无约束二维剪切排样的递归算法［J］.计算机辅助设计与图形学学报, 2006,18(7): 948-951.)［9］CUI Y, ZHANG X. Two-stage general block patterns for the two-dimensional cutting problem ［J］. Computers and Operations Research, 2007, 34(10): 2882-2893.［10］G Y G, SEONG Y J, KANG M K. A best-first branch and bound algorithm for unconstrained two-dimensional cutting problems ［J］. Operations Research Letters, 2003, 31(4): 301-307.
［11］HIFI M, ZISSIMOPOULOS V. A recursive exact algorithm for weighted two-dimensional cutting ［J］. European Operation Research, 1996, 91(3): 553-564.［12］HIFI M. Exact algorithm for large-scale unconstrained two and three staged cutting problems ［J］. Computers Optimization and Application, 2001, 18(1): 63-88.［13］YANG Y, CUI Y, JING Y, et al. An exact algorithm for generating optimal three-block patterns of rectangular items ［J］. Machinery Design and Manufacture, 2008(9):11-13.(杨玉丽,崔耀东,景运革,等.生成矩形毛坯最优三块排样方式的精确算法［J］.机械设计与制造, 2008(9):11-13.)［14］CUI Y. Dynamic programming algorithms for the optimal cutting of equal rectangles ［J］. Applied Mathematical Modelling, 2005, 29(11): 1040-1053.

[1]	吴军欧阳艾嘉张琳. 基于影响度的统计显著序列模式挖掘算法[J]. 计算机应用, 0, (): 0-0.
[2]	张璐方春祝铭. 基于Res2Net-YOLACT和融合特征的室内跌倒检测算法[J]. 计算机应用, 0, (): 0-0.
[3]	殷雨昌王洪元陈莉冯尊登肖宇. 基于单标注样本的多损失学习与联合度量视频行人重识别[J]. 计算机应用, 0, (): 0-0.
[4]	胡军许正康刘立钟福金张清华. 融合多粒度社区信息的网络嵌入方法[J]. 计算机应用, 0, (): 0-0.
[5]	李润泽孙雪姣. 基于时间条件提取序列的数据流偏好查询[J]. 计算机应用, 0, (): 0-0.
[6]	罗圣钦陈金怡李洪均. 基于注意力机制的多尺度残差UNet实现乳腺癌灶分割[J]. 计算机应用, 0, (): 0-0.
[7]	曹一珉蔡磊高敬阳. 基于生成对抗网络的基因数据生成方法[J]. 计算机应用, 0, (): 0-0.
[8]	陈冲闫珠赵继轩何为梁华庆. 基于集合经验模态分解和长短期记忆网络的催化裂化装置NOx排放预测[J]. 计算机应用, 0, (): 0-0.
[9]	徐光柱林文杰陈莎匡婉雷帮军周军. U-Net与自适应阈值脉冲耦合神经网络相结合的眼底血管分割方法[J]. 计算机应用, 0, (): 0-0.
[10]	杨鼎康黄帅王顺利翟鹏李一丹张立华. 基于对抗生成网络和网络集成的面部表情识别方法EE-GAN[J]. 计算机应用, 0, (): 0-0.
[11]	李讷徐光柱雷帮军马国亮石勇涛. 交通道路行驶车辆车标识别算法[J]. 计算机应用, 0, (): 0-0.
[12]	孟杰王莉杨延杰廉飚. 基于多模态深度融合的虚假信息检测[J]. 计算机应用, 0, (): 0-0.
[13]	秦庭威赵鹏程秦品乐曾建朝柴锐黄永琦. 基于残差注意力机制的点云配准算法[J]. 计算机应用, 0, (): 0-0.
[14]	鲁永帅唐英杰马鑫然. 基于深度特征融合的无纺布低对比度浆丝缺陷检测方法[J]. 计算机应用, 0, (): 0-0.
[15]	王宇航周永霞吴良武. 基于高斯函数的池化算法[J]. 计算机应用, 0, (): 0-0.

生成最优同形块两阶段布局方式的确定型算法

Deterministic algorithm for optimal two-stage cutting layouts with same-shape block

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics