Optimization Algorithms Research For The Order-grouping System

Seamless steel pipe is a kind of important industrial material, it is widely used in petroleum, chemical industry, boiler, power station, shipbuilding, machinery manufacturing, automotive, aviation, aerospace, energy, geology, architecture and military industry etc. Order-grouping is an important link of seamless steel pipe production. Good order-grouping plans can improve the utilization rate of raw materials and save for the cost of enterprise, it is necessary to do some research on the order-grouping problem area.Order-grouping problem can be also known as two-stage steel-pipe cutting stock problem. It belongs to a special case of one-dimensional cutting stock problem, and it is based on two-stage. In the process of seamless steel pipe hot rolling, at first stage machines cut raw material tube into several intermediate lengths in hotspot and they are equal length. At second stage machines cutting stock the intermediate length into finished length which is specified by the orders in cold area. Orders demand fixed length and unfixed length. The finished length of unfixed orders is limited by the interval of length which specify in orders. The typical one-dimensional cutting stock problem is to directly cut the original length of the strip material into different length. It belongs to one-stage cutting stock problem and just for fixed orders. Cutting stock problem is a type of complex problem of the combination and scheduling. Due to combination explosion, cutting stock problem is often described as a large-scale integer programming, and proved as a NP-hard problem.Firstly, the thesis proposes the mathematic model of two-stage steel-pipe cutting stock problem based on the analysis of the characteristics of the one-dimensional cutting stock problem and the existing mathematic model of one-stage cutting stock problem. The model is to minimize inventory, waste and surplus inventory surplus distribution, excess levels of unfixed orders as the target. Secondly, the thesis will present one existing heuristic algorithm for the two-stage steel-pipe cutting stock problem, which contains five stages, and each stage will be analyzed through actual examples. The disadvantage of this heuristic algorithm is that will arise many waste, and it uses non-standard steel pipes lead to reduce the production efficiency. Finally, according to the classical column generation technique proposed by Gilmore and Gomory, the thesis will propose a modified row-and-column generation algorithm to solve this problem. We simulate the row-and-column generation algorithm and develop a generator of random two-stage by Microsoft Visual C++. We observe the specific performance of the algorithm by changing any parameter and the results show that the performance of this algorithm is better than the existing heuristic algorithm.