Transactions of Materials and Heat Treatment

Title：Three-block layout pattern and its generation algorithm of constrained cutting problem

Authors： Luo Yunzhen Pan Liwu

Unit： Guangxi Vocational & Technical College Henan University of Animal Husbandry & Economy

KeyWords： constrained guillotine cutting problem threeblock layout pattern recursive generation algorithm rectangular part

ClassificationCode：TP391

year,vol(issue):pagenumber：2018,43(10):185-189

Abstract：

The constrained guillotine cutting problem of rectangular part was discussed, namely, a number of rectangular parts known size and value were cut down from a sheet, and each rectangular part was contained to allow the number of cutting parts not to exceed its demand. Therefore, the optimization objective was to maximize the total value of the parts cut from the sheet, and a three-block layout pattern and its generation algorithm were proposed. This algorithm divided the sheet into three blocks with two mutually perpendicular shear lines, and a rectangular part was placed in the lower left corner for each block. Then, the remainder was divided into two sub-blocks, and the sub-block was regarded as a block to recursive layout until no rectangular part was accommodated. The experimental comparison between the proposed algorithm and the literature algorithm was conducted by the benchmark examples. The results show that the proposed algorithm is 0.35%, 0.31%, 0.19% and 0.37% higher than four kinds of literature algorithms respectively, and the calculation time can meet the needs of practical application.

Funds：

河南省科技厅科技攻关项目(152102210320)

罗运贞（1980-），男，硕士，讲师，E-mail：luoyzgz@163.com；通讯作者：潘立武（1971-），男，博士，高级工程师，E-mail:panlw71@163.com

Reference：

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

[2]曾兆敏, 张春利. 基于两段方式的圆形片约束排样算法[J]. 锻压技术, 2017, 42(8):180-184.

Zeng Z M, Zhang C L. A constrained nesting algorithm of circular pieces based on twosegment patterns[J]. Forging & Stamping Technology, 2017, 42(8):180-184.

[3]崔耀东. 生成矩形毛坯最优T形排样方式的递归算法[J]. 计算机辅助设计与图形学学报, 2006, 18(1):125-127.

Cui Y D. Recursive algorithm for generating optimal Tshape cutting patterns of rectangular blanks[J]. Journal of Computeraided Design & Computer Graphics, 2006, 18(1): 125-127.

[4]Russo M, Sforza A, Sterle C. An exact dynamic programming algorithm for largescale unconstrained twodimensional guillotine cutting problems[J]. Computers & Operations Research, 2014, 50(10):97-114.

[5]潘卫平, 陈秋莲, 崔耀东, 等. 基于匀质条带的矩形件最优三块布局算法[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.

[6]Dusberger F, Raidl G R. Solving the 3staged 2dimensional cutting stock problem by dynamic programming and variable neighborhood search[J]. Electronic Notes in Discrete Mathematics, 2015, 47:133-140.

[7]扈少华，潘立武，管卫利. 复合条带三阶段排样方式的生成算法[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.

[8]Cui Y, Huang B. Heuristic for constrained Tshape cutting patterns of rectangular pieces[J]. Computers & Operations Research, 2012, 39(12): 3031-3039.

[9]Cui Y, Zhao X, Yang Y, et al. Uniform block patterns for constrained guillotine cutting of rectangular items[J]. International Journal of Information and Management Sciences, 2009, 20(1): 89-101.

[10]罗丹, 崔耀东, 李秋蓉. 生成匀质块排样方式的递推算法[J]. 计算机工程与设计, 2013, 34(3):1112-1115.

Luo D, Cui Y D, Li Q R. Recursive algorithm for uniform block patterns[J].Computer Engineering and Design, 2013, 34(3): 1112-1115.

[11]Cui Y P, Cui Y, Tang T, et al. Heuristic for constrained twodimensional threestaged patterns[J]. Journal of the Operational Research Society, 2015, 66(4): 647-656.

Service：

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