Research On Mathematical Optimization Algorithm For Virtual Order Planning Problem In The Steel Industry

In steel enterprises,dealing with excess open-order slabs is a usual case in the hot rolling process.Planners always cluster the slabs as virtual orders for sales to reduce the inventory.During making virtual orders,it is difficult to consider production,inventory and logistics costs simultaneously.To optimal the virtual order planning problem,an integer programming model is formulated,a branch-and-price algorithm for medium-size problems and a near-optimal engineering optimization method of practical-size problems are designed.In addition,embedding the models and algorithms,a decision support system for virtual order planning problem is designed and developed.The detailed work in this thesis is as follows:1)For the virtual order planning problem,an integer programming model is formulated.The objective is to minimize the number of virtual orders,the mismatching cost of slabs belongs to the same virtual order,and cost caused by transportation.The constraints are the technical rules of slabs clustering,the lower and upper limits of the total weight of an virtual order,and the lower limit of allocation in each production line.Through the solving the model by standard optimization software,the efficiency of the model with different sizes is analyzed.The experimental results show that the integer programming model can solve small-size problems but not larger ones.2)For medium-size instances of the problem,the original integer programming model is reformulated to a set-packing problem model,and then a branch-and-price algorithm based on column generation is designed.Specifically,a heuristic algorithm is designed for obtaining the initial solutions,and a relaxed lower bound is obtained through column generation algorithm.Then,the column generation algorithm is embedded into the branch-and-bound frame,the optimal solution for the problem can be obtained by the branch-and-price algorithm.Through numerical experiments and comparison between the proposed branch-and-price algorithm and commercial solution software,we can see that the branch-and-price algorithm is superior than the commercial solution software when solving the in medium-size problems.3)For practical-size instance of the problems,an engineering optimization method is designed to get near optimal solutions quickly.On one hand,the open-order slabs are divided into several subsets to reduce the scale of decision variables and the number of constraints,thus the sub-problem model is simplified;For the other hand,by analyzing the minimum number of virtual orders,a group of valid inequalities are added into the master problem model to improve the lower bound of the relaxed problem and thus speed up the convergence of the branch-andprice algorithm.Adding the two engineering optimization strategies to the basic branch-andprice algorithm,and solving the instances under different sizes,it's proved that the engineering optimization method is effectively for solving the practical-size problems.4)By embedding the algorithms,a decision support system for virtual order planning is designed and developed.The system can automatically make the virtual order plan,and thus improve the work efficiency of planners,as well as reduce the production and inventory cost.