Research On Rectangle Two-Dimensional Guillotine Cutting Stock Problem

The two dimensional cutting problem is a NP hard problem with high computational complexity. It is widely used in machinery, furniture, shipbuilding and other manufacturing industries. This paper studied the rectangle two-dimensional guillotine cutting stock problem, the optimization objective is to find a cutting plan that satisfies the rectangular blank demands, with the smallest total area of sheets. The multiple blank cutting stock problem and single blank cutting stock problem are studied from the aspects of the mathematical model of optimization and its adaptability and efficiency for the optimal packing problem. The main work is as follows:(1)For the multiple blank cutting stock problem, this paper presents a dynamic programming algorithm to generate the optimal four block patterns(FBP). In the patterns, the sheet is divided into four blocks. Each block only contains homogeneous strips with the same direction and length. The knapsack model to generate the optimal layout of strips on the block is firstly solved, and all possible sizes of blocks are obtained through implicit enumeration. All values of four block packs are determined, and the pack of the maximum value is selected as the optimal solution. The linear programming algorithm is used to generate the cutting plans, it iteratively call the FBP procedure and improves the objective function based on the principle of minimum production cost, and change the current value of blanks. And generates a new pattern according to the current value, then chooses a group of optimal patterns to form the cutting plan. The experimental results show that, the algorithm is efficient both in improving cutting stock utilization and in simplifying cutting process.(2)For the single blank cutting stock problem, this paper presents an optimization algorithm to generate multiple plate single rectangle cutting plan. Firstly, the dynamic programming method with the characteristics of full capacity is applied to generate all of the single plate patterns once. Then the integer programming model is established to solve the cutting plan, the optimization goal is to minimize the total area of used plates under the constraint that all demands of blanks are satisfied. The experimental results show that, for the plate number unconstrained problems and constrained problems, the material utilization of the algorithm is higher about 2.01%and 0.99%than the literature’s single plate cutting stock algorithm.