Algorithm For The Two-Dimensional Cutting Stock Problem With Exact Two-Staged Patterns

The cutting stock problem exists in many industries of the national economy, such as metal sheet and strip cutting, wood sawing, glass cutting. In which the two-dimensional cutting stock problem is applied widely, and the rectangle cutting stock problem is the base of the two-dimensioned cutting stock problem. In this paper, two-dimensional rectangular blank cutting stock problem is the emphasis:produce all the required blanks with the smallest plate cost. The solution of the cutting stock problem is a cutting plan which includes one or more cutting patterns. The quality of the solution depends on the choice of pattern generating algorithm. The cutting algorithm with homogeneous-strip Patterns and uniform-strip Patterns which is considered is simple in the cutting process and without trimming, which is suitable for fast cutting occasion. The approach combines the sequential heuristic procedure and a pattern-generation algorithm to generate the greatest cutting plan, the main research works are as follows:(1) Applying two-staged pattern with sequential value correction frame:The two-staged pattern generating algorithm and sequential heuristic procedure generates cutting patterns in a cutting plan sequentially to meet some blank demands, the patterns are generated one after another until all item demands are met. It uses the value-correction strategy to adjust the values of the included blanks after each pattern is generated. Multiple cutting plans are generated through iteration, and the minimum number of sheets is selected, if there are the same number of sheets, choose a small number of patterns as the optimal.(2) Applying homogeneous-two-staged pattern generating algorithm which items in the strips are all the same direction and size. The size of the plate is fixed and the items can rotate. We can determine the number of homogeneous strips of different plate and different kind of items after running the homogeneous- two-staged pattern generating algorithm recursively. Repeat this process until the size of plate the kind of items are all the maxed, the current pattern is generated. Experiments are carried out to compare the proposed approach with commercial stock-cutting software package, the results show that the proposed approach is the most effective to save time and improve the utilization of the plate.(3) Applying uniform-two-staged pattern generating algorithm which items in the strips are all the same width. The size of the plate is fixed and the items can rotate, we can determine a strip after running the uniform-two-staged pattern generating algorithm. Correct the number of items, repeat this process until the current pattern is generated. Set up a time, if the time limit is reached, then select the optimal pattern as the current pattern. Experiments are carried out to compare the proposed approach with both commercial stock-cutting software package and published algorithms, the results show that the proposed approach is the most effective to save time and reduce plate cost.