Solving The Two-Dimensional Cutting Stock Problem With Uniform Block Patterns

Two-dimensional cutting stock problem is to consider how to determine a cutting plan, where the plates are cut to the desired blanks, and the total area of plates consumed should be minimized. The solution of the problem is a cutting plan which includes a set of patterns, so the solution depends in part on the pattern generation algorithm which is good or bad. A lot of scholars have studied this issue. The approaches used commonly include the algorithms based on linear programming, the algorithms based on the sequential heuristic procedure, the intelligent algorithms, etc. The related patterns include the k-staged pattern, the k-segment pattern, the T-shaped pattern, the uniform block pattern, etc. In this paper, a sequential heuristic algorithm based on the value correction strategy is combined with the generation algorithm of the uniform block pattern, which is used to solve the rectangular two-dimensional cutting stock problem, where the main objective is to minimize the total area of the plates consumed, and the auxiliary objective is to reduce the number of different patterns in the plan. The main tasks are as follows:Firstly, a recursive algorithm for generating the uniform block pattern is presented, where the objective is to maximize the total value of blanks included in a plate. The algorithm has the full capacity characteristic, that is, after the cutting pattern of the largest plate is obtained, the cutting patterns of all the sub-plates are known.Secondly, the value correction strategy is integrated to the sequential heuristic procedure, and then the work is to combine the heuristic algorithm with the recursive algorithm which generates the uniform block pattern. In this way, the framework for solving the two-dimensional cutting stock problem is performed. The core idea is to generate a set of patterns in the plan sequentially, and to determine the frequency of each pattern, and to correct the value of blanks appeared in the current pattern by the correction formula. The algorithm is executed iteratively for many plans, from which the final plan is merit-based selected in accordance with the principle of first the smallest of the total area of plates consumed and then the minimum number of patterns.Thirdly, the development of the cutting experimental system is completed, and the experimental results demonstrate the effectiveness of the whole algorithm and the value of research.