锻压技术

单一尺寸矩形毛坯下料问题的一种确定性算法

英文标题：A deterministic algorithm of single-sized rectangular blank cutting

作者：封宇郑仕勇易向阳潘卫平

分类号：TP391

出版年,卷(期):页码：2016,41(6):156-160

摘要：

针对单一尺寸矩形毛坯下料问题，讨论了如何用最少的库存板材切割出一定数量的单一尺寸矩形毛坯。提出1种切割工艺简单的5块排样方式，该排样方式将板材划分成5块区域，每块区域中矩形毛坯按照相同方向排列。设计了1种确定性算法求解下料方案，首先构造1种基于隐式枚举思想的算法确定整张板上的最优5块排样方式；然后对该算法进行扩展，使其能够求解部分板上的最优5块排样方式。采用算例将文中下料算法和文献中递归下料算法、拼合下料算法进行比较，数值模拟分析结果表明，文中的下料算法在切割工艺和板材利用率两方面均较为有效。

For single-sized rectangular blank cutting, the method to cut a certain number of the single-sized rectangular blanks with the least stock sheets was discussed. It was put forward a five-block pattern for the simple cutting process, namely, the sheet was divide into five blocks all arranged along the same direction. Furthermore, a deterministic algorithm was designed to solve the cutting plan. First, an algorithm based on the implicit enumeration method was constructed to determine the optimal five-block pattern on the whole sheet. Then, the algorithm was extended to solve the optimal five-block pattern on the partial sheet. The above algorithm, the algorithm with recursive algorithm and joining method of the literature were compared by examples. The numerical experiment results show that the algorithm discussed is effective both in cutting process and in sheet utilization.

基金项目：

基金项目:广西自然科学基金资助项目（2015GXNFBA139264）

作者简介：封宇(1982-) ，男，硕士，讲师 E-mail：1969760398@qq.com 通讯作者：郑仕勇（1983-），男，硕士，高级工程师 E-mail：fynn2008@163.com

参考文献：

［1］Kim K, Kim B I, Cho H. Multiple-choice knapsack-based heuristic algorithm for the two-stage two-dimensional cutting stock problem in the paper industry[J]. International Journal of Production Research, 2014, 52(19): 5675-5689.

［2］Furini F, Malaguti E. Models for the two-dimensional two-stage cutting stock problem with multiple stock size[J]. Computers & Operations Research, 2013, 40(8): 1953-1962.

［3］陈仕军, 曹炬. 一种 “一刀切” 式矩形件优化排样混合算法[J].锻压技术, 2009, 34(4): 143-147.Chen S J, Cao J . Hybird algorithm of guillotine rectangular cutting problem[J]. Forging & Stamping Technology, 2009, 34(4): 143-147.

［4］Cui Y, Zhao Z. Heuristic for the rectangular two-dimensional single stock size cutting stock problem with two-staged patterns[J]. European Journal of Operational Research, 2013, 231(2): 288-298.

［5］潘卫平, 陈秋莲, 崔耀东, 等. 多板材单一矩形件下料问题的一种求解算法[J]. 锻压技术, 2014, 39(11): 6-10.Pan W P, Chen Q L, Cui Y D, et al. An algorithm for solving problem of multiple plate single rectangle cutting stock[J]. Forging & Stamping Technology, 2014, 39(11): 6-10.

［6］何琨, 黄文奇, 金燕. 基于动作空间求解二维矩形 Packing 问题的高效算法[J]. 软件学报, 2012, 23(5)：1037-1044.He K, Huang W Q, Jin Y. Efficient algorithm based on action space for solving the 2D rectangular packing problem[J]. Journal of Software, 2012, 23(5)：1037-1044.

［7］Kallrath J, Rebennack S, Kallrath J, et al. Solving real-world cutting stock-problems in the paper industry: Mathematical approaches, experience and challenges[J]. European Journal of Operational Research, 2014, 238(1): 374-389.

［8］潘卫平, 陈秋莲, 崔耀东. 考虑切割刀数的最优两段排样算法研究[J]. 广西大学学报：自然科学版, 2014,39(3)：687-692.Pan W P, Chen Q L, Cui Y D. Research on the algorithm for generating optimal two segment cutting patterns with cuts number consideration[J]. Journal of Guangxi University:Natural Science Edition, 2014,39(3)：687-692.

［9］Agrawal P K. Minimising trim loss in cutting rectangular blanks of a single size from a rectangular sheet using orthogonal guillotine cuts[J]. European Journal of Operational Research, 1993, 64(3): 410-422.

［10］Arslanov M Z. Continued fractions in optimal cutting of a rectangular sheet into equal small rectangles[J]. European Journal of Operational Research, 2000, 125(2): 239-248.

［11］崔耀东, 张春玲, 赵谊. 同尺寸矩形毛坯排样的连分数分支定界算法[J]. 计算机辅助设计与图形学学报, 2004, 16(2): 252-256. Cui Y D, Zhang C L, Zhao Y. A continued fractions and branch and bound algorithm for generating cutting patterns with equal rectangles[J].Journal of Computer-Aided Design & Computer Graphics, 2004, 16(2): 252-256.

［12］Cui Y, Gu T, Hu W. Recursive algorithms for the optimum cutting of equal rectangles[J]. International Journal of Computers and Applications,2011, 33(2): 103-107

［13］郭俐, 崔耀东. 有约束单一尺寸矩形毛坯最优排样的拼合算法[J]. 农业机械学报, 2007, 38(10): 140-144.Guo L, Cui Y D. Joining method for generating constrained cutting patterns for rectangles of a single size[J]. Transactions of the Chinese Society for Agricultural Machinery, 2007, 38(10): 140-144.

服务与反馈：

【文章下载】【加入收藏】