Research On Guillotine Cutting Stock Packing Algorithm Based On Same-shape Block

The packing problem belongs to a typical high complexity NP problem. Packing problem has a significant influence on the industries such as manufacturing, ship-building, automobile industry. Research of two dimensional guillotine-cutting stock packing problems is presented in this paper. The optimization objective of the problems is to find an arrangement for maximizing the material usage. This paper presents two new classes algorithms combined with dynamic programming and exact knapsack problem algorithm for generating cutting patterns based on layout, and proposes new layout scheme algorithms combine with linear programming based on column generation. Compared with the present many common effective algorithms in the same problems, experimental results show that this paper’s algorithms can obtain significant improvement in value-to-time, and simplify the cutting process. The main contents of this paper are listed as follows:(1) According to the needs of actual production, when the orientation of pieces is permitted, the paper presents exact algorithms for generating three new layouts based on same-shape block, the two-stage same-shape block cutting pattern algorithm, the two-segment same-shape block cutting pattern algorithm and the three-stage same-shape block cutting pattern algorithm.(2) To meet the needs the fixed orientation of pieces in certain industry, this paper converts the same-shape block into a special structure-same-shape strip, presents exact algorithms for generating three new layouts based on same-shape strips, the two-stage same-shape strip cutting pattern algorithm, the two-segment same-shape strip cutting pattern algorithm and the three-stage same-shape strip cutting pattern algorithm.(3) This paper’s layout algorithms combine with linear programming to generate layout scheme algorithms for solving large scale cutting stock problems.(4) The above cutting patterns compare with the general cutting patterns. We conclude the comparison about all kinds of cutting patterns, and obtain the four characteristics of the paper’s cutting patterns:high utilization of sheet, simplifying cutting process, shortening production cycle, easy extensibility.(5) Based on the above cutting pattern algorithms and layout scheme algorithms, we design runtime environment GCSRE to solve the unconstrained two dimensional guillotine-cutting problems and two dimensional guillotine-cutting stock problems. The 120problems are run on the GCSRE. Compared with several common efficient algorithms, the extensive comparative experiments verify the efficiency of this paper’s algorithms. The algorithms main results of this paper are listed as follows:(1) The same-shape block algorithms compare with three common efficient algorithms. Take the three-stage same-shape block algorithm as an example, in the61benchmark problems, the pattern value of this paper’s algorithm is larger than the general three-stage algorithm in27problems, equal in34problems; The pattern value of this paper’s algorithm is larger than the TSHB algorithm in8problems, equal in53problems. The number of problems solved to optimality is41for this paper’s algorithm, the rest problems are close to optimal. On the average computation times, this paper’s algorithm is shorter than general layout algorithm with65.5s, is shorter than general three-stage algorithm with16.06s, and is comparable with the TSHB algorithm (1.27s).(2) The same-shape strip algorithms compare with five common efficient algorithms. We take the three-stage same-shape strip algorithm as an example, in the first group42benchmark problems, compared with the T-Shape algorithm, the pattern value of this paper’s algorithm is larger in9problems, equal in33problems, compared with the general two-segment algorithm, the pattern value of this paper’s algorithm is larger in8problems, equal in34problems, compared with the general three-stage algorithm, the pattern value of this paper’s algorithm is larger in7problems, equal in35problems. In the second group20benchmark problems, compared with the heuristic TBAU500algorithm, the pattern value of this paper’s algorithm is larger in16problems, equal in3problems. The number of problems solved to optimality is43for this paper’s algorithm, the rest problems are very close to optimal. The average computation time of this paper’s algorithm is0.85s, and the calculation time is reasonable.(3) The layout scheme algorithm compares with the T-Shape scheme algorithms. In7test questions, the experiment results show that the optimization of this paper’s algorithm is better than the T-Shape scheme algorithm, and the sheet utilization average of this paper’s scheme algorithms is99.11%.Compared with the present several common effective algorithms, experimental results show that this paper’s algorithms can solve large-scale two dimensional guillotine-cutting stock packing problems more effectively.