锻压技术

考虑余料生成及利用的圆片下料算法

英文标题：An algorithm of circular piece cutting stock considering generation and utilization of margin

作者：王婷婷崔耀东陈燕王睿

单位：广西大学华南理工大学

分类号：

出版年,卷(期):页码：2019,44(4):40-47

摘要：

针对圆片下料问题，从简化切割工艺的角度来考虑提高下料利用率，提出一种考虑余料生成及利用的圆片下料算法，并以企业长期消耗的板材总面积最小为目标进行优化。该算法采用考虑主动生成余料的直切布局图组成下料方案，产生的余料库存应用于计划期内的连续生产当中。首先，运用动态规划与枚举结合的方法生成布局图，在生成布局图时可以主动生成规范的余料，并通过上限约束保持合理的余料库存量；然后，采用顺序价值修正启发式算法得到最终的下料方案。长期生产的实验结果表明，该算法时间合理，与文献方法相比，应用本文下料算法可较明显地降低生产成本。

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.

基金项目：

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

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

参考文献：

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

服务与反馈：

【本网站尚未开通全文下载服务】【加入收藏】