锻压技术

可减少条带数的矩形件二维下料算法

英文标题：Two-dimensional blanking algorithm reducing the number of strips for rectangular parts

分类号：TP391

出版年,卷(期):页码：2022,47(1):63-68

摘要：

从板材上切割矩形件的过程通常包含两个阶段:第1阶段用大型刀具将板材切成条带;第2阶段用小型刀具将条带切成所需要的矩形件。第1阶段的切割成本随着下料方案中条带数的增加而增加。针对矩形件二维下料问题，提出一种可减少条带数的下料算法，其优化目标是最小化材料成本和切割成本之和。首先，建立该问题的整数线性规划模型；然后，构造T型排样算法生成矩形件在单张板材上的排样方式；最后，采用列生成算法调用T型排样算法迭代构造下料方案。实验结果表明，该算法在维持较高板材利用率的同时，可大幅度减少下料方案的条带数。

The process of cutting rectangular parts from sheets usually consists of two stages. In the first stage, the sheets are cut into strips by large cutter, and in the second stage, the strips are cut into rectangular parts needed by small cutter. However, the cutting cost of the first stage increases with the increasing of the number of strips in the cutting scheme. Therefore, for the two-dimensional blanking problem of rectangular parts, a blanking algorithm reducing the number of strips was proposed, and the optimization goal was to minimize the sum of material cost and blanking cost. Firstly, the integer linear programming model of the problem was established, and the T-shape layout algorithm was constructed to generate the layout method of rectangular parts on a single sheet. Finally, the blanking scheme was iteratively constructed by using the column generation algorithm to call the T-shape layout algorithm. The results of experiment show that the algorithm can greatly reduce the number of strips in the blanking scheme while maintaining a high utilization rate of sheet.

基金项目：

广西农业科技项目（YKJ1929，Z2019102）；教育部新一代信息技术创新项目（2020ITA03027）

作者简介：覃广荣（1980-），男，硕士，讲师 E-mail：grqnz1@163.com 通信作者：吕圣林（1980-），男，学士，副教授 E-mail：lslnyg@163.com

参考文献：

[1]王莉. 矩形件排样问题的遗传模拟退火混合求解算法[J]. 锻压技术, 2021, 46(8):70-76.

Wang L. Genetic simulated annealing hybrid algorithm on layout problem of rectangular part [J]. Forging & Stamping Technology, 2021, 46(8):70-76.

[2]Cui Y, Huang B. Heuristic for constrained T-shape cutting patterns of rectangular pieces[J]. Computers & Operations Research, 2012, 39(12): 3031-3039.

[3]Cui Y P, Cui Y, Tang T, et al. Heuristic for constrained two-dimensional three-staged patterns[J]. Journal of the Operational Research Society, 2015, 66(4): 647-656.

[4]Velasco A S, Uchoa E. Improved state space relaxation for constrained two-dimensional guillotine cutting problems[J]. European Journal of Operational Research, 2019, 272(1): 106-120.

[5]Aktin T, zdemir R G. An integrated approach to the one-dimensional cutting stock problem in coronary stent manufacturing[J]. European Journal of Operational Research, 2009, 196(2): 737-743.

[6]Cui Y, Cui Y P, Zhao Z. Pattern-set generation algorithm for the one-dimensional multiple stock sizes cutting stock problem[J]. Engineering Optimization, 2015, 47(9): 1289-1301.

[7]Vanderbeck F. Exact algorithm for minimising the number of setups in the one-dimensional cutting stock problem[J]. Operations Research, 2000, 48(6): 915-926.

[8]Haessler R W, Sweeney P E. Cutting stock problems and solution procedures[J]. European Journal of Operational Research, 1991, 54(2): 141-150.

[9] Foerster H, Wascher G. Pattern reduction in one-dimensional cutting stock problems[J]. International Journal of Production Research, 2000, 38(7): 1657-1676.

[10]Yanasse H H, Limeira M S. A hybrid heuristic to reduce the number of different patterns in cutting stock problems[J]. Computers & Operations Research, 2006, 33(9): 2744-2756.

[11]Dikili A C, Sarz E, Pek N A. A successive elimination method for one-dimensional stock cutting problems in ship production[J]. Ocean Engineering, 2007, 34(13): 1841-1849.

[12]Yanasse H H, Lamosa M J P. An integrated cutting stock and sequencing problem[J]. European Journal of Operational Research, 2007, 183(3): 1353-1370.

[13]Belov G, Scheithauer G. Setup and open-stacks minimization in one-dimensional stock cutting[J]. INFORMS Journal on Computing, 2007, 19(1): 27-35.

[14]Gradiar M, Resinovi G, Kljaji M. A hybrid approach for optimization of one-dimensional cutting[J]. European Journal of Operational Research, 1999, 119(3): 719-728.

[15]Cui Y. Generating optimal T-shape cutting patterns for rectangular blanks[J]. Proceedings of the Institution of Mechanical Engineers, Part B: Journal of Engineering Manufacture, 2004, 218(8): 857-866.

[16]Kellerer H, Pferschy U, Pisinger D. Knapsack Problems [M]. Berlin: Springer, 2004.

服务与反馈：

【文章下载】【加入收藏】