Integrated Charge Batching and Casting Width Selection at Baosteel

We study an integrated charge batching and casting width selection problem arising in the continuous casting operation of the steelmaking process at Shanghai, China based Baosteel. This decision-making problem is not unique to Baosteel; it exists in every large iron and steel company in the world. We collaborated with Baosteel on this problem from 2006 to 2008 by developing and implementing a decision support system (DSS) that replaced their manual planning method. The DSS is still in active use at Baosteel. This paper describes the solution algorithms we developed and imbedded in the DSS. For the general problem that is strongly NP-hard, a column generation-based branch-and-price (B&P) solution approach is developed to obtain optimal solutions. By exploiting the problem structure, efficient dynamic programming algorithms are designed to solve the subproblems involved in the column generation procedure. Branching strategies are designed in a way that ensures that after every stage of branching the structure of the subproblems is preserved such that they can still be solved efficiently. We also consider a frequently occurring case of the problem where each steel grade is incompatible with any other grade. For this special case, a two-level polynomial-time algorithm is developed to obtain optimal solutions. Computational tests on a set of real production data as well as on a more diverse set of randomly generated problem instances show that our algorithms outperform the manual planning method that Baosteel used to use by a significant margin both in terms of tundish utilization for almost every case, and in terms of total cost for most cases. Consequently, by replacing their manual method with our DSS, the estimated benefits to Baosteel include an annual cost saving of about US $1.6 million and an annual revenue increase of about US $3.25 million.