An exact algorithm for two-staged cutting patterns of rectangular pieces

Packing of rectangular is an NP-complete problem, and is widespread application in the industry. An algorithm is proposed for generating the optimal two-staged cutting patterns for rectangular blanks based on the homogenous block. In 43 problems, compared with the general two-staged algorithm, the pattern value of this paper´s algorithm is larger in 21 problems, equal in 22 problems. In 20 problems, compared with the three block algorithm, the pattern value of this paper´s algorithm is larger in 13 problems, equal in 7 problems. In all instances, the computation time of this paper´s algorithm is 0-2 seconds.