基于T型布局方式的异构矩形件下料算法  

A cutting stock algorithm of heterogeneous rectangular pieces based on T-shaped layout

作　　者：胡钢[1] 张春利[2] 潘立武[3] 

机构地区：[1]四川信息职业技术学院信息工程系,四川广元628017 [2]河北金融学院实验教学中心,河北保定071051 [3]河南牧业经济学院自动化与控制系,河南郑州450011

出　　处：《锻压技术》2017年第6期180-185,共6页Forging & Stamping Technology

基　　金：河南省科技厅科技攻关项目(152102210320);河南省高等学校重点科研项目(15B52000)

摘　　要：讨论异构矩形件下料问题,提出一种基于T型布局方式的优化下料算法。首先构造一种约束布局算法,生成矩形件在单张板材上的T型布局方式,然后采用列生成算法,依据当前矩形件剩余需求量,迭代调用上述约束布局算法,生成一个虚拟下料方案,按照不产生多余矩形件原则,选取虚拟下料方案中的部分布局方式加入到实际下料方案中,更新当前矩形件剩余需求量,重复上述步骤,直到矩形件剩余需求量为零。采用文献中基准例题将本文算法与3种文献中算法进行比较,数值实验结果表明,本文算法比3种文献中算法分别节省3.93%,1.27%和1.17%的板材。The cutting stock problem of heterogeneous rectangular pieces was discussed, and an optimization cutting algorithm based on T- shaped layout was proposed. Firstly, a constrained layout algorithm was constructed to generate the T-shaped layout of rectangular pieces on the single sheet. Then, the column generation algorithm was used to generate a viflual cutting plan according to the current remaining demand of rectangular pieces, partial layouts was admitted into actual cutting plan according to the rule that no redundant rectangular pieces was generated, and the current remaining demand of rectangular pieces was updated. The above steps were repeated until the remaining demand of rectangular pieces was zero. Comparing the proposed algorithm with three algorithms in the literature through benchmark instances, the results of numerical experiments show that the proposed algorithm can save sheets by 3.93%, 1.27% and 1.17% respectively.

关 键 词：下料问题 T型布局方式 列生成算法 约束布局算法 异构矩形件 

分 类 号：O221[理学—运筹学与控制论]