Algorithm Research And Experiment Of One-Dimensional Multiple Stock Size Cutting Stock Problem

Today, cutting stock problem exists widely in the national economic production. One-dimensional multiple stock size cutting stock problem refers to the variety of raw materials and the dimensions of blanks are required for one-dimensional, in the case of the known conditions of supply, to consider how to cut stocks, not only to meet the needs of rough, but also maximize material utilization. In steel, alloy metal wire and other industrial production areas, the optimal cutting solution can help the enterprises to reduce production costs and improve efficiency. With the rapid development of science and technology, the increasing popularity of computer technology, more and more sophisticated research techniques and methods have been applied to solve cutting stock problems in the process. Therefore, whether in theory or in practice, this method of problem solving is of great significance.In this thesis, for the lock of existing linear programming method, the joint algorithm researches the linear programming method with sequential method, difference method and ratio method, discusses the implementation steps of each method, through experiments to compare those implementation strategies, and uses the results to provide experimental evidence for the actual application development. Particularly using difference method and ratio method, the one-dimensional multiple stock size cutting system that can effectively improves the computational efficiency, reduces computing time. Experimental results show that comparing with the traditional methods the difference method and ratio method have the advantages of fast calculation. Major research paper is as follows: First of all, establish the mathematical model of one-dimensional multiple stock size cutting for the research questions. On this basis, discuss the basic idea used in the joint algorithm and the realization principle. This article uses a linear programming-based optimization of one-dimensional multiple stock size cutting algorithm. The algorithm bases on the linear programming algorithm. The basic idea is to use the simplex-method, before selection of cutting patterns.Secondly, based on the best way to layout a mathematical model to solve the knapsack problem, different lengths of stock generate the largest nesting each way value. According to the sequential method, the difference method and the ratio method for their different strategies, choose a better way as for nesting into the base. Among them, the ratio method uses the value of nesting divided by the length of stock used, taking the ratio of the maximum and the corresponding cutting patterns as a basis for entry, into the simplex iterative method. This ensures the most meaningful way to layout the first to be swapped, so reducing the number of total income for the optimal solution to ensure access to the same time shorten the computing time.Finally, to the actual needs, determine the feeding system under the basic functional modules, develop the algorithm based on linear programming optimization of one-dimensional multiple stock size cutting system and its interface to integrate planning, to make it more beautiful and humane. Realized in the system which based on the joint algorithm, by testing a large number of experimental data, compared the results of each algorithm, the results show that with optimal material utilization, the ratio method cost much less running time than other algorithms. It is an effective algorithm to solve one-dimensional cutting stock problem.