A Heuristic Method For Solving Rectilinear Block Cutting Stock Problem

Cutting and packing problem is a typical combinatorial optimization problem, and it belongs to typical NP-hard problem in solving complexity. Cutting and packing problem has been widely applied in our real life and industrial production. Its solution has great important value both in theoretical research and practical application. Therefore, packing problem is an important topic among computer, operations research and combinatorial mathematics.For the two-dimensional cutting problem, regular block and completely irregular block are mainly studied in academia currently. But in the industrial production, there is the rectilinear block in between. The contours of the rectilinear block are composed of right-angle sides. And the angle between any two sides which are connected is a right angle. How to pack this block is known as the rectilinear block cutting problem. In order to solve this problem, search for the optimal cutting plan and improve the utilization of materials, this paper deeply studies the rectilinear block cutting problem. The main contents of the study are as follows:First of all, the research task is brought forward based on summarizing and analyzing current research both domestic and abroad.Next, through analyzing the complex rectilinear block cutting problem and studying the common solving method, this thesis puts forward a heuristic method to solve the rectilinear block cutting problem. First, a mixed integer programming model of the rectilinear block cutting problem is built. Then the model of the relaxation problem is solved. Next, the model of the minimum vertex cover problem (MVC problem) is built by the solution. Finally, the genetic algorithm is used to solve MVC problem and the feasible solution of MVC problem is restored to the optimal cutting programme of the cutting problem.Last, the concrete implementation method is as follows:(1) The cutting plan as the initial model which has coverage areas is generated through combining the C++language with the CPLEX software which is developed by IBM. Then the initial model is turned into the MVC problem using the C++language.(2) The genetic algorithm is used to solve MVC problem. The optimal population size, the maximum number of iteration and mutation rate are selected according to the known conditions such as the number of variables. Thus the feasible solution of the MVC problem can be found by using the genetic algorithm toolbox of MATLAB software.(3) The feasible solution of the MVC problem is restored to the optimal cutting scheme of the cutting problem by programming based on C++. The figure of the solution is got through the computer aided drawing software. Therefore the feasible solution of the rectilinear block cutting problem is got.Compared with the pure mixed integer programming, this heuristic method expands the solving scale and shortens the solving time through the heuristic approach for solving the rectilinear block cutting problem. And compared with the existing manual cutting plan, it has improved the utilization ratio of the plate about15%.