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.