Abstract: This paper discusses the problem of generating optimal cutting plan for circles. The cutting plan consists of several cutting patterns. First a knapsack algorithm that generating four-block cutting patterns of circle strips was constructed; then the sequential value correction heuristic algorithm was used to generate the cutting plan, it iteratively calls the above knapsack algorithm procedure improves the objective function based on the principle of minimum production cost and correct the current value of circles, generates a new pattern according to the current value; in the end a set of optimal cutting patterns was choose to form the cutting plan. The cutting stock algorithm was tested with the benchmark problems of literatures, and compared with the T-shape algorithm and heuristic algorithm. The results of numerical experiments show that, the material utilization rate of the algorithm is higher 0.83% and 3.63% than the above two algorithms.

Key words: wafer, cutting stock, four block patterns, knapsack problem, heuristic algorithm