锻压技术

约束剪切问题的三块排样方式及其生成算法

英文标题：Three-block layout pattern and its generation algorithm of constrained cutting problem

作者：罗运贞潘立武

分类号：TP391

出版年,卷(期):页码：2018,43(10):185-189

摘要：

讨论了矩形件有约束剪切排样问题，即在一张板材上剪切下若干种已知尺寸和价值的矩形件，约束每种矩形件允许剪切的数量不能超过其需求量，优化目标为使板材剪切出的矩形件总价值最大。提出了一种三块排样方式及其生成算法。这种算法用两条互相垂直的剪切线将板材分成3个块；对于每个块，排放一个矩形件在其左下角，将其剩余部分划分为2个子块；将子块看作块继续递归排样，直到其无法再容纳矩形件为止。采用基准例题将本文算法与文献算法进行实验对比，结果表明本文算法排样价值比4种文献算法分别高0.35%，0.31%，0.19%和0.37%，且计算时间可满足实际应用需要。

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.

基金项目：

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

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

参考文献：

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

服务与反馈：

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