Research On The Optimization Method For Integration Of Order Allocation And Batch Planning

Most large iron and steel enterprises usually have more than one shop at steelmaking stage.It is a key decision problem in the operation management of steel production to allocate customer orders to different steelmaking shops such that the loads of different shops are balanced and the production efficiency is increased.Moreover,large-scale facilities in steelmaking shop such as converter and continuous caster is often run in batch mode,while customer orders are characterized as multi-varieties and small-batch.Thus,another key decision problem in the operation management of steel production is to group different orders into batches to coincide the batch production model of the large-scale facilities.Order allocation and batch planning are two closely related problems,and their decisions are strong coupled.From the perspective of overall coordination,this thesis studies the integrated optimization problem of order allocation and batch planning.The main contents of this thesis are as follows.(1)Taking the selection of shop,steel grade and width for each order as a decision variable,and considering the constraints such as compatibility between order and shop,upgrade and substitution relation between grades,capacity limitation on converter,load balance between multiple shops,we formulate the problem as a novel integer programming which is used to quantitatively describe the key combinatorial features of the problem.The objective is to minimize production amount of surplus slabs,production amount of slabs being upgraded,the amount of loss for slab cutting,total dis-matching cost between orders and shops.(2)The combinatorial characteristics of the model lead to computational complexity,and hence it is difficult to use commercial optimization software to obtain the optimal solution or even the feasible solution directly in a limited time.In this thesis,a conventional Dantzig-Wolfe decomposition technology is implied to decompose the original model into a master problem and a set of subproblems.Each subproblem corresponds to a 0-1 knapsack problem under a given three tuple of shop,steel grade and width.Column generation algorithm is then implied to solve the master problem and subproblems iteratively to get the lower bound of the original problem.By embedding the column generation into branch-and-bound framework,the optimal integer solution can be obtained by performing a branch search process.(3)The conventional Dantzig-Wolfe decomposition leads to a large amount of subproblems.It is difficult for the master problem to effectively coordinate the coupling relationship between multiple subproblems.This thesis proposes a novel Dantzig-Wolfe decomposition strategy based on aggregation of multiple constraints.It decompose the original model according to the steel grade(or subset of grades),and each subproblem corresponds to a multiple knapsack problem under a given tuple of shop and steel grade(or subset of grades).The proposed new decomposition strategy can decrease the number of subproblems and reduce their coupling relation,which simplifies the solving the master problem and improves the lower bound.The column generation algorithms based on the conventional Dantzig-Wolfe decomposition and the new decomposition with multiple constraints aggregation are both implemented using the C++ language on a personal computer with Intel Core(TM)2 Quad 2.83 GHz CPU and 3.25 GB RAM.Numerical experiments are carried out and the experimental results verify the efficiency of the new decomposition with multiple constraints aggregation.