Transactions of Materials and Heat Treatment

Title：An algorithm of generating five block layout on uniform strip

Authors： Qing Qiao1 Li Jing2 Guan Weili3

Unit： Sichuan Post and Telecommunications College Zhengzhou Electronic and Information Engineering School Nanning University

KeyWords： two dimensional layout without constraint five block layout dynamic programming implicit enumeration uniform strip

ClassificationCode：TP391

year,vol(issue):pagenumber：2016,41(12):37-41

Abstract：

For the problem of two-dimensional layout without constraint on the rectangular blank, the five block layout on the uniform strip was put forward, and the blank was divided into five rectangular blocks, which were composed of uniform strips containing the same blanks respectively. Next, generation algorithm of this layout was constructed. Firstly, the optimal layouts of uniform strips on all possible size blocks were generated by dynamic programming method. Then, all possible five block layouts were investigated by implicit enumeration and branch and bound techniques. Furthermore, the optimal five block layout was confirmed and obtained based on the maximum principle of the blank layout value. Numerical experiment results show that this algorithm can effectively improve the value of the blank layout.

Funds：

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

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

Reference：

［1］季君. 基于同形块的剪切下料布局算法研究
［D］. 北京：北京交通大学, 2012.

Ji J. Research on Guillotine Cutting Stock Packing Algorithm Based on Same-shape Block
［D］. Beijing：Beijing Jiaotong University, 2012.

［2］易向阳, 仝青山, 潘卫平. 矩形件二维下料问题的一种求解方法
［J］. 锻压技术, 2015, 40(6):150-153.

Yi X Y, Tong Q S, Pan W P. A solving method of two-dimensional cutting for the rectangular blanks
［J］.Forging & Stamping Technology, 2015, 40(6):150-153.

［3］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.

［4］Andrade R, Birgin E G, Morabito R. Two-stage two-dimensional guillotine cutting stock problems with usable leftover
［J］. International Transactions in Operational Research, 2014, 23(1):121-145.

［5］Hadjiconstantinou E, Christofides N. An exact algorithm for general, orthogonal, two-dimensional knapsack problems
［J］. European Journal of Operational Research, 1995, 83(1):39-56.

［6］Chen C S, Lee S M, Shen Q S. An analytical model for the container loading problem
［J］. European Journal of Operational Research, 1995, 80(1):68-76.

［7］Cui Y. A new dynamic programming procedure for three-staged cutting patterns
［J］. Journal of Global Optimization, 2013, 55(2):349-357.

［8］潘卫平, 陈秋莲, 崔耀东, 等. 基于匀质条带的毛坯最优三块布局算法
［J］. 图学学报, 2015, 36(1): 7-11.

Pan W P, Chen Q L, Cui Y D, et al. An algorithm for generating optimal homogeneous strips three block patterns of rectangular blanks
［J］.Journal of Graphics, 2015, 36(1): 7-11.

［9］扈少华, 黄于欣, 管卫利. 矩形毛坯五块切割排样方式的生成算法
［J］. 锻压技术, 2016，41(7)：157-160.

Hu S H, Huang Y X, Guan W L. Generating algorithm of five block cutting nesting for rectangular blanks
［J］.Forging & Stamping Technology, 2016，41(7)：157-160.

［10］Kellerer H, Pferschy U, Pisinger D. Knapsack Problems
［M］.Berlin: Springer, 2004.

［11］Gun Y G, Seong Y J, Kang M K. A best-first branch and bound algorithm for unconstrained two-dimensional cutting problems
［J］. Operations Research Letters, 2003, 31(4):301-307.

Service：

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