锻压技术

矩形件二维下料问题的一种求解方法

英文标题：A solving method of two-dimensional cutting for the rectangular blank

作者：易向阳仝青山潘卫平

单位：广西大学河北金融学院

分类号：TG386

出版年,卷(期):页码：2015,40(6):150-154

摘要：

求解矩形件二维下料问题，即解决如何用最少的板材切割出所需的全部矩形毛坯。提出一种切割工艺简单的新型排样方式即单毛坯条带四块排样方式。首先采用经典背包算法生成排样方式，然后采用基于列生成的线性规划算法迭代调用上述排样方式生成算法求解下料方案。将文中排样方式分别与文献中经典两阶段和经典两段排样方式进行比较，实验计算结果表明，四块排样方式排样价值高于以上两种排样方式。最后通过实际下料求解，证明了使用该算法的材料利用率较高。

To solve the two-dimensional cutting was to handle that how to cut out the required rectangular blank by the least sheet metal. A new simple nesting type of the cutting process, namely nesting four parts in a single strip, was put forward. Firstly, the nesting type was generated by the classical knapsack algorithm, and then the algorithm of solving cutting process was generated by calling the above nesting type based on the linear programming iterative algorithm of column generation. It was compared with the traditional two stages and two segment nesting types respeltively. The experimental computation results show that the type of nesting four parts is higher than the above two kinds of nesting type. Finally, through the cutting example, a higher material utilization was proved.

基金项目：

国家自然科学基金资助项目(61262003）

易向阳（1973-），男，硕士，讲师;通信作者：潘卫平（1989-），男，硕士

参考文献：

［1］Malaguti E,Medina Durán R,Toth P. Approaches to real world two-dimensional cutting problems[J]. Omega,2014,(47): 99-115.
［2］陈仕军,曹炬. 一种 “一刀切” 式矩形件优化排样混合算法[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.
［3］贾志欣,殷国富，罗阳,等. 矩形件排样的模拟退火算法求解[J]. 四川大学学报: 工程科学版,2001,33(5): 35-38.Jia Z X,Yin G F,Luo Y,et al. Application of simulated annealing to the rectangular packing problem[J].Journal of Sichuan University:Engineering Science Edition,2001,33(5): 35-38.
［4］陈学松,曹炬,方仍存. 遗传模拟退火算法在矩形优化排样系统中的应用[J]. 锻压技术,2004,29(1): 27-29.Chen X S,Cao J,Fang R C . Integrated application of genetic algorithm and simulated annealing for the packing of rectangles system[J].Forging & Stamping Technology,2004,29(1): 27-29.
［5］何琨,黄文奇,金燕. 基于动作空间求解二维矩形 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.
［6］Hifi M. Exact algorithms for large-scale unconstrained two and three staged cutting problems[J]. Computational Optimization and Applications,2001,18(1): 63-88.
［7］Cui Y,He D,Song X. Generating optimal two-section cutting patterns for rectangular blanks[J]. Computers & Operations Research,2006,33(6): 1505-1520.
［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］Kellerer H,Pferschy U,Pisinger D. Knapsack Problems[M]. Berlin: Springer,2004.
［10］Furini F,Malaguti E,Medina Durán R,et al. A column generation heuristic for the two-dimensional two-staged guillotine cutting stock problem with multiple stock size[J]. European Journal of Operational Research,2012,218(1): 251-260.
［11］Arbib C,Marinelli F,Ventura P. Cutting stock with bounded open stacks: A new integer linear programming model[R]. Technical Report TRCS 007/2010,Università degli Studi di L’Aquila,2010.
［12］杨玉丽. 生成矩形毛坯最优三块排样方式的精确算法[D]. 桂林：广西师范大学,2007.Yang Y L. An Exact Algorithm for Generating Optimal Four-block Patterns for Rectangular Blanks[D]. Guilin: Guangxi Normal University,2007.

服务与反馈：

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