Lagrangian heuristic for scheduling a steelmaking-continuous casting process

Abstract

One of the biggest bottlenecks in iron and steel production is the steelmaking-continuous casting (SCC) process which consists of steel-making re ning and continuous casting. The production scheduling of SCC is a complex hybrid owshop (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 speciCE 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.