Column Generation Methods For Batching Decision And Logistics Scheduling Problems In Iron-making And Steel-making Area

In iron and steel industry, the batching decision and logistics scheduling problems arising in ironmaking and steelmaking area are key and urgent issues of production management. Scientific solving those problems can help to improve productivity and resource utilization, to reduce production cost and energy consumption. Since most of those problems can be reduced to combinational optimization problems belong to NP-Hard, it becomes a hot research topic to investigate the efficient and suitable models and algorithms, which are curretly focused by both academic and industrial communities. As an important optimization technique, column generation combined with other algorithms has been successfully used to solve a great deal of classical combinatorial optimization problems belong to NP-Hard, by which the optimal or near optimal solutions are obtained. This dissertation makes basic research on the theory and improvement of column generation and its application research on Lot batching problem, cast batching problem, molten iron allocation problem and molten iron locomotive scheduling problem. Based on the structure of column generation and the key factors affecting algorithm performance, this algorithm is improved respectively from the following three aspects, i.e. framework of algorithm, solving pricing subproblems and obtaining integer solutions. For the practical batching decision problems, the effective algorithm besed one intelligent optimization is proposed. By embedding this algorithm, the decision support systems (DSS) software with interactive planning editor is developed. The content of the dissertation is summarized as follows.1) Improving the framework of algorithm. By embedding the subgradient based Lagrangian relaxation algorithm into the column generation framework, a new combined algorithm named LR&CG is proposed, which consists of nested double loops. In the inner loop, the Lagrangian subproblem is solved within a fixed number of iterations, and the subgradient method is employed to update Lagrangian multipliers at each iteration, and the valid lower bound and the columns corresponding to solutions of Lagrangian subproblem are obtained. In the outer loop, the columns with negative reduced costs are added to the restricted master problem, which is then solved and the upper bound of LR dual problem and shadow prices are obtained. At the initialization of the inner loop, Lagrangian multipliers are initialized as weighted decomposition of shadow prices of the restricted master problem and the best Lagrangian multipliers found so far. Its application is then studied for solving the lot batching problem in steelmaking and continuous casting. The problem is formulated as a mixed integer programming, and then the Lagrangian relaxation problem is obtained by decoupling assignment constraints which is further decomposed into two-level subproblems. Two dynamic programming algorithms are designed for solving two level subproblems respectively. The Lagrangian dual problem is transformed into an extensive linear programming which is suitable to be solved by column generation. Finally, subgradient based Lagrangian relaxation and column generation algorithms are combined to solve the Lagrangian dual problem.2) Improving the methods of solving pricing subproblems. Three different strategies are proposed for solving pricing subproblems, and they are state space relaxation, reducing search space and generating columns by heuristics, resepectively.(1) At the cost of loosing the lower bound of the master problem, state space relaxation is introduced to reduce the complexity of pricing subproblem and to accelerate the solving of pricing subproblem. Its application is put on the molten iron allocation problem. By relaxing the state space of the pricing subproblem problem which is NP-hard single machine scheduling problem, a pseudo polynomial dynamic programming algorithm is designed to obtain columns corresponding to pseudo schedules or feasible schedules. The columns obtained are allowed to add to the restricted master problem. This strategy is a compromise between the dynamic programming algorithm for the subproblem and the branch-and-bound algorithm for the master problem.(2) Reducing search space is actived when the exploring techniques are adopted to obtain the optimal solutions of pricing subproblems. In exploring technique, the partial schedules which are impossible to expand to the optimal schedule are recognized by analyzing the problem characters, and they are excluded for further expanding as early as possible, so that the CPU time for searching unpromising space is saved. Its application is put on both cast batching problem in steelmaking and continuous casting and molten iron locomotive scheduling problem. The pricing subproblem of the former can be reduced to "family elementary" shortest path problem with resource constraints. The generalization of famous Dijkstra algorithm is designed to solve it, then dominant rules and lower bound estimation of labels is introduced to suppress proliferation of labels. Based on above two techniques, unpromising space is restricted, and therefore efficiency of solving pricing subproblem is improved. Such techniques can be further extended to the pricing subproblem of molten iron locomotive scheduling problem, which can be reduced to an elementary shortest path problem with nonlinear objective and time windows constraints.(3) In the beginning, columns with negative reduced costs can be generated by heuristics to reduce the complexity of optimization methods of pricing subproblem and accordingly to save computational time. In the cast batching problem, the basic idea of such approach is to generate new columns with a negative reduced cost by modifying existing columns with a zero reduced cost. For the lot batching problem, Lagrangian subproblems are solved at the relaxed version, and a rounding procedure is employed to obtain the feasible solutions of Lagrangian subproblems in the begining of LR&CG algorithm. It aims to find columns with negative reduced costs for restricted master problem and to find an appropriate descended direction for Lagrangian relaxation algorithm.3) Obtaining integer solutions. Three different methods are proposed to obtain optimal or near optimal integer solutions, they are branch-and-bound, heuristics based on the frictional optimal solution obtained by column generation, heuristics based on the solution of Lagrangian relaxation problem.(1) By exploiting the relationship between variables of the original compact mixed integer programming and variables of the Dantzig-Wolfe decomposition formulation, the effective branching strategy is proposed and the branch-and-bound procedure is employed to obtain the optimal solution. Its application is put on the cast batching problem in steelmaking and continuous casting, molten iron allocation problem and molten iron locomotive scheduling problem, respectively.(2) The integer solution is obtained by transforming the fraction optimal solution from column generation, and two types of such strategies are proposed in this dissertation. The first one deals with the cast batching problem. Based on the optimal fraction solution of linear relaxation of master problem, a filtration strategy is employed to select some columns which are stored as part of integer solution, and then a reduced problem is obtained by deleting corresponding columns and rows, and column generation is re-executed on the reduced problem. The obtained integer solution is further improved by local search. Note that such process is not invoked at any node other than the root node of the branch-and-bound tree. The second one deals with molten iron locomotive scheduling problem in which heuristics of transforming fraction solution into integer solution is invoked at all nodes. It first calculates the assignment values between tasks and locomotives, and then schedule for each locomotive is constructed or expanded step by step according to assignment values and feasibility of insertion. Searching feasible solutions at each node of the branch-and-bound tree may considerably reduce the overall computing time needed to reach a provably optimal solution.(3) The integer solution is obtained by transforming the optimal solution of Lagrangian relaxation problem, which is often used in Lagrangian relaxation algorithm. However, no routine is existed for such transforming. In the LR&CG algorithm for lot batching problem, a heuristics is proposed by fixing lot selection decision variables, and converting the original problem into a linear programming transportation problem, which is easy to obtain fraction solution. The rounding procedure is employed to transform the fraction solution into a feasible solution.4) After analyzing the technologic constraints and management requirements, the key characters of the practical steelmaking and continuous casting batching decision problems are abstracted and taken into account. According to those characters, two mathematical models are developed, and then the effective dynamic programming based the heuristics and the tabu search algorithms are proposed. Based on the models and solution approaches, the decision support system is developed, and has been tested using the practical production data collected from an most advanced iron and steel complex in China, the computational experiments are carried out and the computational results verify the efficiency of solution approaches and stability of system.