矩形件同质条料五块排样方式的生成算法

An Algorithm for Generating the Homogeneous Strips Five Block Pattern of Rectangular Pieces

材料利用率和切割工艺复杂度是金属板材切割排样中主要考虑的两个因素。提出矩形件同质条料五块排样方式的生成算法,用以解决金属板材切割排样问题。这种算法将板材分为五个块,各块中只排放方向和长度均相同的条料。通过求解背包问题优化块中条料的布局,使得块中排放的矩形件总价值达到最大;采用隐式枚举法考察所有可能的五块组合的排样价值,选择排样价值最大的一个组合作为最终的五块排样方式。用文献中的基准测题,验证文中的五块排样算法。数值实验结果表明,文中算法在提高材料利用率和简化板材切割工艺两方面均有效,且算法计算时间较短。

Material utilization and cutting process complexity are the two main factors that be considered in the metal sheet cutting process. In order to solve the metal sheet cutting problem, this paper presents an algorithm which can generate the homogeneous strip five block pattern of rectangular pieces. This algorithm divides the sheet into five blocks, each of which consists of strips of the same length and direction. The algorithm first uses an knapsack algorithm to determine the optimal strips layout in the block and maximize the value of the pieces cut; and then uses an implicit enumeration method to consider all possible five blocks combination, from which the highest pattern value combination is selected. The algorithm was tested on benchmarks problems in the literature. The numerical experimental results show that the proposed algorithm is effective in the improving material utilization and simplify sheet cutting process , and also has a shorter computation time.