Lagrangian heuristic for scheduling a steelmaking-continuous casting process

One of the biggest bottlenecks in iron and steel production is the steelmaking-continuous casting (SCC) process, which consists of steel-making, refining and continuous casting. The production scheduling of SCC is a complex hybrid flowshop (HFS) scheduling with following features: job grouping and precedence constraints, no dead time inside the same group of jobs, setup time constraints on the casters. A mixed-integer programming (MIP) model is established with the objective of minimizing the total weighted penalties of the earliness/tardiness and the job waiting. Through relaxing the operation precedence constraints to the objective function, the relaxed problem can be decomposed into to smaller subproblems, each of which corresponds a specific stage. A new dynamic programming algorithm is developed for solving the subproblems which are parallel machine scheduling problem with objective of minimizing total weighted completion time where the weights of jobs may be negative. The Lagrangian dual problem is solved by an improved subgradient level algorithm which can guarantee global convergence. A novel heuristic is presented to adjust subproblem solutions to obtain a feasible schedule. The computational results demonstrate that the propose LR approach can generate a high quality schedule within an acceptable computation time.