基于两阶段排样方式的卷材下料算法研究

讨论矩形件卷材下料问题,采用切割工艺简单的两阶段排样方式采进行下料。这种排样方式采用一组平行于卷材宽度方向的剪切线将卷材切割成多个条带,然后将每个条带切割成所需要的矩形件。首先,构造一种有界背包算法确定矩形件在条带中的优化布局;然后,采用基于列生成的线性规划算法调用上述有界背包算法生成排样方式;最后,采用顺序启发式算法,用当前矩形件剩余需求量反复调用线性规划算法生成各个排样方式,直至每种矩形件剩余需求量均为零,组合各个排样方式形成下料方案。将本文算法与2种文献算法进行比较,计算结果表明,本文算法下料方案比2种文献算法分别节省1.97%和1.66%的卷材。

Research on coil cutting algorithm based on the two-stage cutting layout

The problem of rectangles coil cutting was discussed, and the cutting process was carried out by simple two-stage cutting layout.Through this cutting layout, the coil was cut into a variety of strips by a set of shearing lines which were paralleled to the coil width direction, then each strip was cut into desirable rectangles.Firstly, a bounded backpack algorithm was constructed to determine the optimal layout of the rectangles in the strip.Next, the cutting layout was generated by the linear programming algorithm to call the bounded backpack algorithm based on the column generation.Finally, a variety of cutting layout were generated by the sequential heuristic algorithm to repeat call the linear programming algorithm through the remaining demand of current rectangle until zero, and a cutting plan was formed by combining each cutting layout.The results of calculation comparisons between the proposed algorithm and the two literature algorithms show that the proposed algorithm can save 1.97% and 1.66% of the coil, respectively.