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

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-30 出版日期:2014-05-01
通讯作者: 季君
作者简介:季君(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-30 Published:2014-05-01
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]	杨建锋陈斌李雨轩. 基于点云重构的自监督点云异常检测方法[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[3]	薛振华李强黄超. 视觉大模型驱动的像素级图像异常检测模型[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[4]	蒋畅江向杰何旭颖. 面向机械臂抓取的双目视觉目标定位算法[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[5]	边小勇胡其仁袁培洋. 多注意力对比学习的红外小目标检测[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[6]	李钟华钟庚辛范萍朱恒亮. 通过边界挖掘和背景引导的伪装目标检测[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[7]	吴松霖张广朝姚远彭博. 基于判别区域引导的多视图困难气道识别[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[8]	李强白少雄熊源袁薇. 基于视觉大模型隐私保护的监控图像定位[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[9]	薛雅丽徐忠敏刘世豪. 基于多级小波残差网络的重力数据去噪方法[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[10]	况世雄姚俊波陆佳炜王琪冰肖刚. 基于动态图卷积网络的电梯乘客异常行为数据增强方法[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[11]	康斌陈斌王俊杰李昱林赵军智咸伟志. 基于多粒度共享语义中心关联的文本到人物检索方法[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[12]	张庆杨凡方宇涵. 基于多模态信息融合的中文拼写纠错算法[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[13]	王昊王金伟程鑫张家伟吴昊罗向阳马宾. 彩色图像JPEG重压缩取证综述[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