生成矩形毛坯最优两段排样方式的递归算法

Recursive Algorithm for Generating Optimal Two-Segment Cutting Patterns of Rectangular Blanks

提出一种递归算法生成矩形毛坯两维两段排样方式。这种算法将板材分成两段,同一段中所有条带的长度和方向都相同,二段的条带方向相互平行或垂直,不同尺寸的毛坯可以在一根条带中出现。通过递归在段上生成最优条带布局,隐式地讨论所有长度的段,确定所有两段组合的价值,选择价值最大的一个组合作为最优解。计算结果表明,该算法在计算时间和材料利用率两方面都有效。最后,一个实际问题的解表明:使用该算法,材料利用率较高。

A recursive algorithm is proposed for generating optimally unconstrained two-dimensional twosegment cutting patterns of rectangular blanks. The stock sheet is diveded into two segments by the algorithm. Each segment consists of strips with the same length and the direction. Rectangular blanks of different sizes appear in one strip. Strip directions of two segments are either parallel or perpendicular to each other. By the optimal strip layouts on segments through the recursion, and all possible segment lengths and values of all possible combinations of two segments are determined, the combination having the maximum value is selected as the optimal solution. Computational results indicate that the algorithm is efficient in both the computation time and the material utilization rate. Finally, the solution to an example is given to prove that the material utilization rate is higher.