Transactions of Materials and Heat Treatment

Title：A solving method of two-dimensional cutting for the rectangular blank

Authors： Yi Xiangyang Tong Qingshan Pan Weiping

Unit： Guangxi University Hebei Finance University

KeyWords： cutting linear programming knapsack algorithm nesting four parts rectangular blank

ClassificationCode：TG386

year,vol(issue):pagenumber：2015,40(6):150-154

Abstract：

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.

Funds：

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

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

Reference：

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

Service：

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