锻压技术

应用递归划分策略解决矩形件剪切排样问题

英文标题：Application of recursive partitioning strategy in solving guillotine cutting problem of rectangular piece

作者：沈萍邓国斌

单位：广西职业技术学院

分类号：TP391

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

摘要：

针对机械制造领域的矩形件剪切排样问题，提出一种基于递归划分思想的排样算法。用两条互相垂直呈T型的剪切线将板材划分为3个子板，称板材的左下角子板为排样块，称其余两个子板为递归块。对于排样块，按照简单方式排放矩形件；对于递归块，将其看做板材继续划分。用隐式枚举算法确定排样块的最优排样方式，得到块中排放的最优矩形件种类和矩形件的行列数；用分支定界算法确定递归块是否继续划分。采用基准例题将本文算法与文献算法进行对比，实验结果表明，本文算法排样价值高于文献算法，且计算时间能满足实际应用需要。

To discuss the guillotine cutting problem of rectangle piece in machinery manufacturing field, a cutting algorithm based on recursive partitioning was proposed. With two cutting line that perpendicular to each other and with T shape, the plate was divided into three sub plates, in which the lower left corner sub plate was called layout block,and the remaining two sub plates were called recursive blocks. For layout block, rectangle piece was discharged in a simple way, and for the recursive block, it was considered as plates to be divided. The implicit enumeration algorithm was used to determine the optimal pattern of the layout block, and the optimal rectangle type and the number of rows and columns of rectangles in the block were obtained. The branch and bound algorithm was used to determine whether the recursive block continues to be divided or not. The benchmark instances are used to compare the proposed algorithm with the literature algorithms. Experimental results show that the proposed algorithm is superior to the literature algorithms in the pattern value, and the computation time can meet the practical use.

基金项目：

广西自然科学基金资助项目（2015GXNFBA139264）;广西教育厅科研项目（KY2016YB610）

沈萍（1974-），女，硕士，实验师 E-mail：jsgxdgb@163.com

参考文献：

［1］Delorme M, Iori M, Martello S. Bin packing and cutting stock problems: Mathematical models and exact algorithms
［J］. European Journal of Operational Research, 2016, 255(1): 1-20.

［2］Hifi M. Exact algorithms for large-scale unconstrained two and three staged cutting problems
［J］. Computational Optimization and Applications, 2001, 18(1): 63-88.

［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］ Cui Y. A new dynamic programming procedure for three-staged cutting patterns
［J］. Journal of Global Optimization, 2013, 55(2):349-357.

［5］ Cui Y. Heuristic and exact algorithms for generating homogenous constrained three-staged cutting patterns
［J］. Computers & Operations Research, 2008, 35(1):212-225.

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

［7］易向阳, 仝青山, 潘卫平. 矩形件二维下料问题的一种求解方法
［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.

［8］梁秋月, 崔耀东, 游凌伟. 应用三块排样方式求解二维下料问题
［J］. 〖JP3〗广西师范大学学报：自然科学版, 2014, (3):41-45.〖JP〗
Liang Q Y, Cui Y D, You L W. Solving two-dimensional cutting stock problem with three-block patterns
［J］. 〖JP3〗Journal of Guangxi Normal University: Natural Science Edition, 2014, (3):41-45. 〖JP〗

［9］ Cui Y D. Heuristic for two-dimensional homogeneous two-segment cutting patterns
［J］. Engineering Optimization, 2013, 45(1):89-105.

［10］ Chen Q, Cui Y, Chen Y. Sequential value correction heuristic for the two-dimensional cutting stock problem with three-staged homogenous patterns
［J］. Optimization Methods & Software, 2016, 31(1):68-87.

［11］ Young-Gun 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.

服务与反馈：

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