Column Generation-Based Methods For Supply Chain Planning And Scheduling In Iron And Steel Industry

Supply chain planning and scheduling are to optimize the allocation of resources and the arrangement of production and logistics reasonably, and can help achieve competitive advantage by matching supply with demand. Iron and steel industry is a typical multi-stage process industry which provides backdrop for intense research on the theory, method and technology of supply chain planning and scheduling since there are significant differences in production technologies, manufacturing modes and product characters among the multi stages. Supply chain planning and scheduling have been key and urgent issues in steel operation management. These supply chain optimization problems are always combinational optimal problems which are hard to be solved to optimality. Therefore, it becomes a hot research topic to investigate the efficient and suitable models and algorithms, which are currently investigated by academic communities.In this dissertation, several supply chain planning and scheduling problems are extracted from the practical production, such as sintering-ironmaking low carbon supply chain planning problem, supply chain production and logistics planning problem for steelmaking and hot rolling, steelmaking-continuous casting and hot rolling supply chain scheduling problem. For these problems, based on the analysis of their problem structures and features, the dissertation designs corresponding column generation-based branch-and-price algorithms. The content of the dissertation is summarized as follows.1) With the hot metal demands and the carbon cap and trade mechanism, the dissertation considers the requirements of sintering and ironmaking recipes and make decisions on raw materials purchase, production recipes choices, raw materials and sinters inventories, and carbon trade in the sintering-ironmaking low carbon supply chain planning problem. A mixed integer programming model is developed to minimize the total cost which includes purchase cost, production cost, inventory cost and carbon trade cost. The model combines the carbon emission curb mechanism and combinational optimization, and balances the economic objective and the carbon emission reduction.2) The algorithm for the sintering-ironmaking low carbon supply chain planning problem has been investigated. The dissertation proposes a column generation-based branch-and-price algorithm. Since the large scale problem is hard to be solved to optimality rapidly, the algorithm is enhanced by two tailored techniques. First, the relaxation of master problem is strengthened by introducing two families of valid inequalities which can improve the lowerbound whithout changing the subproblem structures. Second, variables elimination by path reduced cost is used to fix some integer variables and reduce the solution space, and lead to a considerable speedup of the overall algorithm. The computational results on random experiments show that the proposed algorithm is effective and superior to the business software CPLEX.3) Based on the background of steelmaking and hot rolling, the supply chain production and logistics planning has been investigated. The conflict between the diversity of hot coil demand and the mass production in steelmaking leads to either unreasonable inventories of slabs and hot coils, or backlogging. Considering the steelmaking and hot rolling capacities and three types of connection, a mixed integer programming model is developed to minimize the costs of production, logistics and backlogging. This dissertation proposes a column generation-based branch-and-price algorithm to solve it. The extreme points of the convex of hot rolling planning are analyzed theoretically when the capacity constraints are relaxed. The original problem is equally decomposed by a hybrid principle which combines convexification and projected discretization, in which the discrete variables and continuous variables are separated. The new Dantzig-Wolfe reformation is compact, and the column generation convergence is improved. The computational results over the random instances demonstrate that the proposed algorithm is effective.4) Under the condition of technological constraints in multi stages, the dissertation investigates the relationships among slabs, charges and casts. The steelmaking-continuous casting and hot rolling supply chain scheduling is to decide their sequences and timetables on the corresponding machines. To minimize the total costs which contain the waiting penalties of charges and slabs, and the changeover cost in hot rolling, a mixed integer programming model is proposed. The optimal model decides not only the machine choices and sequences for charges and casts, but also the rolling turn choices and sequences for slabs on hot rollers, as well as the sequences of the turns on each roller. The scheduling problem has complex coupling constraints.5) The algorithm for the steelmaking-continuous casting and hot rolling supply chain scheduling problem has been investigated. The dissertation proposes a new and compact Dantzig-Wolfe decomposition based on production time windows as well as machines and turns. The pricing problems for steelmaking and continuous casting are stated as a single machine scheduling problem which aims to minimize the total weighted completion time with production time windows. The optimal properties are proposed and a bidirectional dynamic programming algorithms are used to solve them. The pricing problem for hot rolling turn is stated as an elementary shortest path problem with resource constraint and linear time-dependent cost. Applying the state space relaxation, the turn pricing problem can be solved to optimality by a pseudo-polynomial time algorithm. In addition, according to the technology requirements in hot rolling, a family of valid inequalities based on the rounded capacity cut is proposed to enhance the performance of the branch-and-price algorithm. The computational results on random experiments show that the proposed algorithm is effective.