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

doi:10.11772/j.issn.1001-9081.2014.05.1511

Journal of Computer Applications ›› 2014, Vol. 34 ›› Issue (5): 1511-1515.DOI: 10.11772/j.issn.1001-9081.2014.05.1511

Previous Articles Next Articles

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

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

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

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

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

Abstract

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.

摘要：

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

CLC Number:

TP391

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.

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

References

［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]	. Pavement defect detection algorithm with enhanced morphological perception [J]. Journal of Computer Applications, 0, (): 0-0.
[2]	YANG Jianfeng, CHEN Bin, LI Yuxuan. Self-supervised point cloud anomaly detection method based on point cloud reconstruction [J]. Journal of Computer Applications, 0, (): 0-0.
[3]	XUE Zhenhua, LI Qiang, HUANG Chao. Vision foundation model-driven pixel-level image anomaly detection model [J]. Journal of Computer Applications, 0, (): 0-0.
[4]	. Binocular vision object location algorithm for robot arm grasping [J]. Journal of Computer Applications, 0, (): 0-0.
[5]	. Multi-attention contrastive learning for infrared small target detection [J]. Journal of Computer Applications, 0, (): 0-0.
[6]	LI Zhonghua, ZHONG Gengxin, FAN Ping, ZHU Hengliang. Camouflaged object detection by boundary mining and background guidance [J]. Journal of Computer Applications, 0, (): 0-0.
[7]	. Multi-view difficult airway recognition based on discriminant region guidance [J]. Journal of Computer Applications, 0, (): 0-0.
[8]	. Privacy preserving localization of surveillance images based on large vision models [J]. Journal of Computer Applications, 0, (): 0-0.
[9]	. Gravity data denoising method based on multilevel wavelet residual network#br# #br# [J]. Journal of Computer Applications, 0, (): 0-0.
[10]	. Data augmentation method for abnormal passenger behavior in elevators based on dynamic graph convolutional network [J]. Journal of Computer Applications, 0, (): 0-0.
[11]	. Text-based person retrieval method based on multi-granularity shared semantic center association [J]. Journal of Computer Applications, 0, (): 0-0.
[12]	ZHANG Qing, YANG Fan, FANG Yuhan. Chinese Spelling Correction Algorithm Based on Multi-Modal Information Fusion [J]. Journal of Computer Applications, 0, (): 0-0.
[13]	WANG Hao, WANG Jinwei, CHENG Xin, ZHANG Jiawei, WU Hao, LUO Xiangyang, MA Bin. A Review of JPEG Recompression Forensics for Color Images [J]. Journal of Computer Applications, 0, (): 0-0.
[14]	. Distribution adaptation and dynamic curriculum pseudo-labeling framework for semi-supervised fire detection [J]. Journal of Computer Applications, 0, (): 0-0.
[15]	. Multimodal harmful content detection method based on weakly supervised modality semantic enhancement [J]. Journal of Computer Applications, 0, (): 0-0.

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

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

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics