应用三块排样方式求解二维下料问题

Solving Two-dimensional Cutting Stock Problem with Three-block Patterns

本文采用顺序价值修正框架和三块排样方式求解二维下料问题。该框架顺序生成排样方案中的各个排样方式(排样图),用每个排样方式满足部分毛坯的需求,直到满足全部需求为止;动态调整毛坯价值,使毛坯价值趋于合理;多次迭代生成多个不同的排样方案,实现优选。采用的三块排样方式通过不完全枚举法生成,其中最多包含三种毛坯,从而有利于简化下料工艺。通过与线性规划算法比较,说明在毛坯需求量较小的情况下,本文算法能有效减少板材消耗量。

The proposed approach solves two-dimensional cutting stock problem using three-block patterns and a sequential value correction framework.Cutting patterns in a cutting plan are generated sequentially.Each pattern is used to fulfill some portion of the remaining items until all the required items are fulfilled.The item values are adjusted dynamically to make the value more reasonable.Multiple cutting plans are generated in order to select the optimal one.The three-block patterns are generated by an incomplete enumeration method,in which each pattern contains at most three types of items to simplify the cutting process.The comparison with the linear programming algorithm indicates that the proposed approach can effectively reduce the plate consumption when the item demands are small.