基于两段排样方式的矩形件优化下料算法

An Optimization Algorithm for Rectangular Items Cutting Stock Problem Based on Two-Segment Patterns

针对矩形件下料问题,提出一种基于两段排样方式的优化下料算法。首先构造一种约束排样算法,生成矩形件在板材上的两段排样方式。然后采用列生成算法依据矩形件剩余需求量迭代调用上述约束排样算法生成一个虚拟下料方案,按照不产生多余矩形件原则选取虚拟下料方案中的部分排样方式加入到实际下料方案中,更新矩形件剩余需求量;重复上述步骤直到矩形件剩余需求量为零。采用文献中基准例题将该算法与2种文献算法进行比较,数值实验结果表明该算法下料利用率比2种文献算法分别高1.61%和0.78%。

For on the rectangular items cutting stock problem, an optimization algorithm based on two-segment patterns is proposed. Firstly, a constrained packing algorithm is constructed to generate the two-segment patterns of rectangular items on the plate. Then, column generation algorithm is used to generate a virtual cutting plan according to the current remaining demand of rectangular items, several patterns are added into actual cutting plan according to the rule that no redundant rectangular item is generated, and the current remaining demand of rectangular items is updated. The above steps are repeated until the remaining demand of rectangular items is zero. Compared the proposed algorithm with two algorithms in the literature through benchmark instances, results of numerical experiments show that material utilization of the proposed algorithm is higher than two literature algorithms about 1.61% and 0.78%, respectively.