同尺寸矩形毛坯排样的连分数分支定界算法

A Continued Fractions and Branch-and-Bound Algorithm for Generating Cutting Patterns with Equal Rectangles

在确定同尺寸矩形毛坯最优排样方式的算法中 ,连分数算法的时间效率最高 ,但所生成排样方式的切割工艺复杂 提出连分数分支定界算法 ,该算法应用连分数法确定毛坯数最优值 ,采用贴切的上界估计方法 ;在搜索过程中只保留上界不小于最优值的分支 ,遇到下界等于最优值的分支时结束搜索 实验结果表明 ,该算法的时间效率和连分数算法接近 ,并可以有效地简化切割工艺 ,生成切割工艺最简单的排样方式 最后 。

Among the algorithms for generating optimal cutting patterns with equal rectangles, the continued fractions algorithm is the most time efficient one, yet the patterns generated by it are complex to cut. This paper presents a solution that can generate the simplest pattern. The algorithm determines the optimal number of blanks by the continued fractions method, and estimates the upper bound more tightly. In the searching process, only branches of upper bounds not smaller than the optimal number are kept. The searching process ends when a branch of a lower bound equal to the optimal number is found. Experimental computations are performed to test the algorithm and the continued fractions approach. The results show that time efficiencies of the two algorithms are nearly the same, while the proposed algorithm may simplify the cutting process. It is also compared with the pattern often used in production to illustrate the potential of the approach in saving material.