Abstract: The time required by an optimal exact algorithm to solve the large-scale rectangle two-dimensional cutting problems may become unbearable.So an algorithm for two-stage homogeneous strip patterns for pieces is presented.The algorithm not only is appropriate for the shearing and punching process,but also reasonable in time.Firstly,vertical cuts divide the stock sheet into composite strips,and then horizontal cuts divide the composite strips into homogeneous strips.The algorithm uses a dynamic programming recursion to determine the optimal homogeneous strip layout,solves knapsack problems to obtain the homogeneous strip layout on the composite and the composite strip layout on the sheet.The algorithm is tested through benchmark problems,and compares with three famous algorithms,the classic two-stage algorithm,the TABU500 algorithm and optimal algorithm.The pattern value of this algorithm is better than that of the classic two-stage and TABU500 algorithm.What’s more,this algorithm can give solutions very close to optimal algorithm,and the computation time is shorter than optimal algorithm.

Key words: layout, homogeneous strip, knapsack problem