Transactions of Materials and Heat Treatment

Title：An algorithm of circular piece cutting stock considering generation and utilization of margin

Authors：

Unit：

KeyWords：

ClassificationCode：

year,vol(issue):pagenumber：2019,44(4):40-47

Abstract：

For the problem of circular piece cutting stock, considering the improvement of cutting efficiency from the perspective of simplifying the cutting process, a circular piece cutting stock algorithm considering the generation and utilization of margin was proposed, and the optimization with the target of minimizing the total area of sheets used by the enterprise for long term production was conducted. The algorithm adopted a cutting stock scheme of one-pass layout pattern which took into account the active generation of margin, and the generated margin inventory was used in the continuous production during the planning period. Firstly, the dynamic programming and the enumeration method were combined to generate the layout pattern. When generating the layout pattern, the normative margin could be actively generated, and the reasonable margin inventory was maintained by the upper bound constraint. Then, the final cutting stock scheme was obtained by the sequential value correction heuristic algorithm. The experimental results of long term production show that the algorithm is reasonable in time, and compared with the literature method, the application of the above cutting stock algorithm can significantly reduce the production cost.

Funds：

国家自然科学基金资助项目(71371058，61363026)

王婷婷（1994-），女，硕士研究生 E-mail：1242976190@qq.com 通讯作者：崔耀东（1957-），男，教授，博士生导师 E-mail：ydcui@263.net

Reference：

[1]崔耀东. 计算机排样技术及其应用[M]. 北京:机械工业出版社, 2004.

Cui Y D. Computer Layout Technology and Its Application [M]. Beijing: China Machine Press, 2004.

[2]Cui Y D. Generating optimal T-shape cutting patterns for circular blanks [J]. Computers & Operations Research, 2005, 32 (1): 143-152.

[3]陈菲, 刘勇, 刘睿, 等. 基于3块方式的圆形片剪冲排样算法[J]. 计算机工程, 2009, 35(14): 195-196,220.

Chen F, Liu Y, Liu R, et al. Cutting and puching layout algorithm for circle blanks based on three blocks pattern[J]. Computer Engineering, 2009, 35(14): 195-196,220.

[4]杨剑, 黄少丽, 侯桂玉, 等. 圆片剪冲下料排样算法[J]. 计算机工程与设计, 2010, 31(23): 5139-5142.

Yang J, Huang S L, Hou G Y, et al. Packing algorithm for circle cutting stock problem [J]. Computer Engineering and Design, 2010, 31(23): 5139-5142.

[5]王岩, 潘卫平, 胡钢. 生成圆形片最优四块排样方式的确定性算法[J]. 机械设计与制造, 2015, (9): 152-155.

Wang Y, Pan W P, Hu G. Deterministic algorithm for generating four-block cutting patterns of circular blanks [J]. Machinery Design & Manufacture, 2015, (9): 152-155.

[6]胡钢, 杨瑞, 潘立武. 基于价值修正的圆片下料顺序启发式算法[J]. 图学学报, 2016, 37 (3): 337-341.

Hu G, Yang R, Pan L W. Sequential value correction heuristic algorithm for circle cutting stock problem [J]. Journal of Graphics, 2016, 37(3): 337-341.

[7]管卫利, 王祺. 带剪刃长度约束的圆形片二维优化下料算法[J]. 锻压技术, 2018, 43 (3): 176-180.

Guan W L, Wang Q. Optimal algorithm of two dimensional cutting stock for circular pieces with blade length constraint [J]. Forging & Stamping Technology, 2018, 43 (3): 176-180.

[8]陈燕, 刘咏, 谢琪琦,等. 基于梯形和平行四边形的圆片剪冲下料算法设计与实现[J]. 图学学报, 2016, 37(5): 661-667.

Chen Y, Liu Y, Xie Q Q, et al. An algorithm for circle cutting stock problem based on trapezoid and parallelogram [J]. Journal of Graphics, 2016, 37(5): 661-667.

[9]陈燕, 谢琪琦, 刘咏,等. 圆形件下料顺序分组启发式算法的设计与实现[J]. 图学学报, 2017, 38(1): 5-9.

Chen Y, Xie Q Q, Liu Y, et al. The cutting stock problem of circular items based on sequential grouping heuristic algorithm [J]. Journal of Graphics, 2017, 38(1): 5-9.

[10]侯桂玉, 崔耀东, 黄少丽,等. 一种求解圆形件下料问题的启发式算法[J]. 计算机工程, 2010, 36(13): 227-229.

Hou G Y, Cui Y D, Huang S L, et al. Heuristic algorithm for cutting stock problem of circular item [J]. Computer Engineering, 2010, 36(13): 227-229.

[11]Cui Y, Song X, Chen Y, et al. New model and heuristic solution approach for one-dimensional cutting stock problem with usable leftovers [J]. Journal of the Operational Research Society, 2017, 68 (3): 269-280.

[12]Cui Y P, Cui Y D, Tang T B. Sequential heuristic for the two-dimensional bin-packing problem [J]. European Journal of Operational Research, 2015, 240(1): 43-53.

Service：

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