Study On The Optimization Model And Algorithm For The Complex Cutting Stock Problem

The cutting stock problem is the process of cutting smaller-size, different-length and varied-shape semi-finished products with larger-size fixed-style raw materials according to production requirements, and these semi-finished products can be further processed into various products with different specifications. Because of the complexity of the cutting stock problem and the limitations of the existing methods, the waste of raw materials is inevitable. In the manufacturing field, the raw material cost accounts for a large proportion in the total product cost, so how to reduce the cost of raw material during the cutting processing has very important economic and social significance.The cutting stock problem in the actual production is a large, multi-constraints and multi-targets problem, and it is very complex. Most of the existing literatures on the cutting problems simplified and abstracted the problem when developing models and designing algorithms, so that the final results cannot be directly applied to practical production. This paper does not conduct the research on the mathematically cutting stock problems, but investigates the enterprise cutting stock problem under complex environment from the actual situation of production. This paper discussed three kinds of common problems:the cutting stock problem of truncated cone material, two-dimensional rectangular packing problem, the cutting stock problem in Internet of things, according to the actual production process. The research contents of this paper are as follows:(1) This thesis established the mathematical model of variable cross section one-dimensional cutting stock problem. The model not only considered the cutting rate of material, but also considered the effects of product position, cutting scheme number, blade number restrictions, knife thickness, forging ratio and the ratio of height to diameter.(2) This thesis improved the SHP algorithm to solve the problem of variable cross-section raw materials cutting stock problem, and the improvement of the algorithm is:a) the relationship between product cutting position and cutting length is studied according to the characteristics of variable cross-section of raw material cutting stock problem; b) a length-transited function is added for SHP algorithm; c) a product selection process is improved for SHP algorithm based on the left products diversity, to avoid the cutting rate reducing as products number decreasing; d) a new algorithm is designed to solve a special knapsack problem, and the complexity of the improved algorithm is reduced; e) the cutting SHP process is changed to avoid the SHP algorithm "end conditions"; f) the algorithm parameters are analyzed to get the algorithm’s parameters of user’s willing wait time, and an automatic parameter adjustment algorithm is designed.(3) This thesis developed a decision support prototype system for two-dimensional rectangular based on improved intelligent algorithms, including some existing rectangular. In view of the existing rectangular blanking algorithm, we developed a decision support prototype system for two-dimensional rectangular, so that the user could combine existing algorithms in the algorithm library to satisfy the actual requirements under the specific circumstances.(4) This thesis developed a multi-objective mathematical model of cutting stock problem in Internet of Things and designed the algorithm. The situation that the uncut ingot library products and the cutting material which has been cut in the field of product can be replaced is considered in the model. The cutting products can be delayed if their delivery dates are relatively late, and some urgent products can be processed in advance. The SHP algorithm is designed to solve the stock problem, which can meet delivery requirements and reduce the cost of inventory.The problem is derived from the actual production of enterprises. It summarizes the general rules of cutting problem, establishes the model of cutting stock problem under enterprises complex environment, and designs the corresponding algorithms to get the satisfaction solution within the allowed cost. The research results of the thesis had been applied in Ma’anshan Steel Corp wheel company actual production line.