Transactions of Materials and Heat Treatment

Title：Coil cutting algorithm of single rectangular pieces based on multi-stage layout

Authors： Qing Guangrong Qiu Gangwei Wang Kun Huang Xin

Unit： Guangxi Agricultural Vocational and Technical University Sichuan Institute of Information Technology

KeyWords： rectangular pieces coil cutting problem multistage layout dynamic programming implicit enumeration

ClassificationCode：TP391

year,vol(issue):pagenumber：2022,47(2):73-77

Abstract：

The coil cutting problem of single rectangular piece was discussed, that was, a certain number of the same kind of rectangular pieces were cut from the coil by the shearing process, and the goal was to minimize the length of the coil consumed. Then, an optimal cutting algorithm was proposed based on the implicit enumeration method and the dynamic programming algorithm, and the cutting process consisted of two stages. In the first stage, the coil was cut into segments with the same width and the length less than the cutting blade length, and in the second stage, the segments were cut into rectangular pieces. First, the length of all the segments to be investigated was determined by the implicit enumeration method, and the multi-stage layout of rectangular pieces in the segments of different lengths was determined by the dynamic programming algorithm. Then, the segment with the highest material utilization rate was selected, and the number of use for this segment was determined according to the principle of the largest use for this section and no redundant rectangular pieces. Finally, the segment with the smallest length was selected to meet the remaining demand of rectangular pieces, and the above-mentioned cutting algorithm was compared with the ordinary cutting algorithm. The experimental results show that the optimal cutting algorithm based on implicit enumeration method and dynamic programming algorithm can effectively solve the coil cutting problem of single rectangular piece.

Funds：

2019年第二批广西农业科技自筹经费项目（YKJ1929,Z2019102）；教育部新一代信息技术创新项目（2020ITA03027）；广西农业职业技术大学科学研究与技术开发计划课题（YKJ2124）

作者简介：覃广荣（1980-），男，硕士，讲师,E-mail：grqnz1@163.com;通信作者：黄欣（1983-），男，硕士，副教授,E-mail：nyzg2001@163.com

Reference：

[1]Delorme M, Iori M. Enhanced pseudo-polynomial formulations for bin packing and cutting stock problems[J]. Informs Journal on Computing, 2020, 32(1): 101-119.

[2]Furini F, Malaguti E, Thomopulos D. Modeling two-dimensional guillotine cutting problems via integer programming[J]. Informs Journal on Computing, 2016, 28(4): 736-751.

[3]Mellouli A, Mellouli R, Masmoudi F. An innovative genetic algorithm for a multi-objective optimization of two-dimensional cutting-stock problem[J]. Applied Artificial Intelligence, 2019, 33(6):531-547.

[4]Clautiaux F, Sadykov R, Vanderbeck F, et al. Pattern-based diving heuristics for a two-dimensional guillotine cutting-stock problem with leftovers[J]. EURO Journal on Computational Optimization, 2019, 7(3):265-297.

[5]Sumetthapiwat S, Intiyot B, Jeenanunta C. A column generation on two-dimensional cutting stock problem with fixed-size usable leftover and multiple stock sizes[J]. International Journal of Logistics Systems and Management, 2020, 35(2): 273-288.

[6]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.

[7]Cui Y D. Dynamic programming algorithms for the optimal cutting of equal rectangles[J]. Applied Mathematical Modeling, 2005, 29(11): 1040-1053.

[8]郭俐, 崔耀东. 有约束单一尺寸矩形毛坯最优排样的拼合算法[J]. 农业机械学报, 2007, 38(10): 140-144.

Guo L, Cui Y D. Joining method for generating constrained cutting patterns for rectangles of a single size[J]. Transactions of the Chinese Society for Agricultural Machinery, 2007, 38(10): 140-144.

[9]Cui Y D, Gu T L, Hu W. Recursive algorithms for the optimum cutting of equal rectangles[J]. International Journal of Computers & Applications, 2011, 33(2): 103-107.

[10]Cui Y D, Huang L, He D. Generating optimal multiple-segment cutting patterns for rectangular blanks[J]. Proceedings of the Institution of Mechanical Engineers, Part B: Journal of Engineering Manufacture, 2005, 218(11):1483-1490.

[11]朱强, 薛峰, 李碧青. 硅钢卷材二维剪切下料问题的一种求解算法[J]. 变压器, 2018，55(3): 18-20.

Zhu Q, Xue F, Li B Q. An algorithm for 2D guillotine cutting stock problem of silicon steel coil[J].Transformer, 2018，55(3): 18-20.

[12]Birgin E G, Lobato R D, 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.

Service：

【This site has not yet opened Download Service】【Add Favorite】