Transactions of Materials and Heat Treatment

Title：Heuristic optimization algorithms of coiled material layout for circular parts

Authors： Qing Qiao Wu Hongle Guan Weili

Unit： Sichuan Post and Telecommunications College Hebei Finance University Nanning University

KeyWords： coiled material layout problem circular parts layout algorithm heuristic optimization algorithm maximum placement optimization index

ClassificationCode：TP391

year,vol(issue):pagenumber：2018,43(4):175-179

Abstract：

The coiled material layout of circular parts is to put a set of circular parts with different sizes on a coiled sheet with a specified width to minimize occupied area of coiled sheet. To solve this problem, a heuristic optimization algorithm of layout for sequencing first and then locating was proposed, and the mathematical model of coiled material layout for circular parts was built. Then, the optimization indexes of all feasible locations in the current layout for circular parts which are going to be placed were calculated, and the location of the maximum optimization index was selected to place circular parts. Furthermore, many different layout plans were obtained by changing the place sequence of circular parts, and the layout plan with the minimum coil sheet length was selected as the final solution. Finally, three kinds of algorithms were constructed, namely the non-incremental radius, the first circular part replacement and the sub-sequence division, and based on the examples in literature, the calculation time and coil sheet length of three algorithms and literature algorithm were compared. The experimental results show that the layout plan generated by this algorithm is with a shorter coil sheet length and a reasonable calculation time. Thus, the sub-sequence division algorithm has the best solution quality and can distribute the circular parts evenly on the coil sheet.

Funds：

广西科学研究与技术开发计划(桂科攻11107006-13，桂科攻12118017-10A)

青巧（1972-），女，硕士，高级工程师；E-mail：qqiaosc@163.com；通讯作者：管卫利（1977-），男，硕士，副教授；E-mail:gwlnn2001@126.com

Reference：

[1]王峰, 张军, 胡钢. 圆形件剪冲下料问题的一种求解算法[J]. 锻压技术, 2015, 40(10): 39-44.

Wang F, Zhang J, Hu G. An algorithm for solving the shearing problem of circular blanks[J]. Forging & Stamping Technology, 2015, 40(10): 39-44.

[2]朱强, 薛峰, 郑仕勇,等. 约束二维排样问题的一种求解算法[J]. 锻压技术, 2016, 41(9):148-152.

Zhu Q, Xue F, Zhen S Y, et al. An algorithm of the constrained two-dimensional nesting [J].Forging & Stamping Technology, 2016，41(9):148-152.

[3]扈少华，潘立武，管卫利. 复合条带三阶段排样方式的生成算法[J].锻压技术，2016，41（11）：149-152.

Hu S H，Pan L W，Guan W L. A generating algorithm of three-stage nesting patterns for composite strip[J].Forging & Stamping Technology，2016，41（11）：149-152.

[4]Wscher G, Hauner H, Schumann H. An improved typology of cutting and packing problems[J]. European Journal of Operational Research, 2007, 183(3): 1109-1130.

[5]Litvinchev I, Infante L, Ozuna L. Packing circular-like objects in a rectangular container[J]. Journal of Computer & Systems Sciences International, 2015, 54(2): 259-267.

[6]Hifi M, M'hallah R. A literature review on circle and sphere packing problems: Models and methodologies[J]. Advances in Operations Research, 2015，2009，(4)：1-22.

[7]赵新芳, 崔耀东, 杨莹, 等. 矩形件带排样的一种遗传算法[J]. 计算机辅助设计与图形学学报, 2008, 20(4): 540-544.

Zhao X F, Cui Y D, Yang Y, et al. A genetic algorithm for the rectangular strip packing problem[J]. Journal of Computer-aided Design & Computer Graphics, 2008, 20(4): 540-544.

[8]李霞, 陈弦. 一种启发式矩形毛坯带排样算法研究[J]. 山西大学学报: 自然科学版, 2011, 34(2): 215-218.

Li X, Chen X. Heuristic algorithm for the rectangular strip packing problem[J]. Journal of Shangxi University: Natural Science Edition, 2011, 34(2): 215-218.

[9]姚怡, 吴金春, 赖朝安. 采用分层搜索填充策略的启发式带排样算法[J]. 武汉大学学报: 工学版, 2014, 47(6): 854-858.

Yao Y, Wu J C, Lai C A. Heuristics for rectangular strip packing problem based on hierarchical search filled strategy[J]. Engineering Journal of Wuhan University, 2014, 47(6): 854-858.

[10]Stoyan Y, Yaskov G. Packing unequal circles into a strip of minimal length with a jump algorithm[J]. Optimization Letters, 2014, 8(3): 949-970.

[11]呼子宇, 杨景明, 侯新培，等. 基于离散差分进化算法的热连轧批量计划优化[J]. 塑性工程学报，2017，24(3):148-153.

Hu Z Y, Yang J M, Hou X P, et al. Optimization of hot rolling batch planning based on discrete differential evolution[J]. Journal of Plasticity Engineering, 2017, 24 (3): 148-153.

[12]Kubach T, Bortfeldt A, Gehring H. Parallel greedy algorithms for packing unequal circles into a strip or a rectangle[J]. Central European Journal of Operations Research, 2009, 17(4): 461-477.

Service：

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