Using Layer Patterns In Solving The Two-dimensional Cutting Stock Problem

There has a lot of cutting stock problems in many industries of the national economy. It is a very meaningful task to give a cutting solution with the maximum utilization of materials or near to it. Traditional works are completed by men, which leads to long working hours and low material utilization. Computer Aided Nesting (CAN) come into being with the continuous development of modern optimal computing technology and computer technology, whose purpose is to generate the cutting solution with high utilization of the material, to reduce ultimately product costs by saving material, reducing the workload and simplifying the cutting process.The two-dimensional cutting stock problem (TDCS) of rectangle blanks is to minimize the total area of the plates consumed to fulfill the blank demands. Which has an important and widely application in industrial production, at the same time, the research of this problem is the base of the two-dimension cutting stock problem of the irregular blanks. Therefore, the discussion of this problem has certain importance whether in practice or in theory. The solution to TDCS is a cutting plan that consists of a set of distinct cutting patterns with given frequencies. Scholars in and abroad have done extensive research on this problem, the sequential heuristic procedure (SHP), the linear programming approach (LPA), or some simulate optimal algorithm are usually used to solve TDCS.With the development of production, factors which affect the cutting process continue to change. Packing problems with new features appear continually. For example, some factories of the furniture manufacturing industry use the two-phase cutting process. At the first phase, an automatic machine with multiple parallel cutters divides the plate into several sections in one pass. The sections are divided into blanks by simple tools at the second phase. Pattern types that can make better use of the automatic machine and reduce the work load of the second phase are expected. This paper general the optimal layer patterns, and then combined with the linear programming approach, to solve, the two-dimensional cutting stock problem of rectangular blanks using the two-phase cutting process. The main contents include the following three aspects:Firstly, the dynamic programming for the unconstrained patterns has been designed, to maximize the pattern value that is the total value of the blanks included in the plate. The algorithm divides the plate into layers with horizontal cuts. The width of the layer is the same as the height of the leftmost blank (referred to as the main blank) in the layer. The region right to the main block contains a simple block pattern that is determined using a dynamic programming procedure. Layer patterns have the expected feature, because the plate can be divided into several layers in one pass at the first phase, the average area of the layers is not large, which will be helpful for reducing the work load of the second.Secondly, the unconstrained algorithm and the linear programming approach are combined to solve the two-dimensional cutting stock problem of rectangle blanks. The results are often fractional and must be round to integers because they represent the frequencies of the patterns. Most papers only perform rounding operation on the optimal (final) LPA solution. Because the rounding operation exist errors, scholars have proposed to examine the rounding results. This paper makes the following improvements:In each cycle of the simplex iteration, it calls a dynamic programming procedure to generate an optimal layer pattern, and introduces it into the base matrix to obtain a new solution. Each LPA solution (often fractional) is rounded to obtain the integer solution. The best integer solution is taken as the final solution.Finally, designing and developing the rectangle packing system. The algorithm is tested by a number of experiments, and the results are compared with the interrelated literatures. The results show that the algorithm presented in this paper is appropriate for the two-phase cutting process, and lead to high material utilization, is an efficient algorithm to solve the two-dimensional cutting stock problem of rectangle blanks.