An effective Lagrangian relaxation approach for rescheduling a steelmaking-continuous casting process

• The SCC rescheduling model is formulated based on time-indexed variables.
• An effective LR approach is proposed to address the rescheduling problem.
• A two-stage dynamic programming algorithm is presented to solve the batch-level subproblems.
• An efficient subgradient algorithm with global convergence is presented to solve the LD problem.

This paper studies a steelmaking-continuous casting (SCC) rescheduling problem with machine breakdown and processing time variations. Two objectives are considered in this study: the efficiency objective and the stability objective. The former refers to the total weighted completion time and total sojourn time, whereas the latter refers to the number of operations processed on different machines in the initial and revised schedules. We develop a time-index formulation and an effective Lagrangian relaxation (LR) approach with machine capacity relaxation to address the rescheduling problem. The LR approach decomposes the relaxed problem into batch-level subproblems with variable processing times. A polynomial two-stage dynamic programming algorithm is proposed to solve the batch-level subproblems. An efficient subgradient algorithm with global convergence is presented to solve the corresponding Lagrangian dual (LD) problem. Computational experiments based on practical production data show that the proposed approach not only produces a high quality schedule within an acceptable time but also performs much better than a practical SCC rescheduling method from a large iron and steel enterprise in China.