A novel Lagrangian relaxation approach for a hybrid flowshop scheduling problem in the steelmaking-continuous casting process

• Published in: European journal of operational research 2014-07, Vol.236 (1), p.51-60
• Main Authors: Mao, Kun, Pan, Quan-ke, Pang, Xinfu, Chai, Tianyou
• Format: Article
• Language: English
• Subjects: Algorithms; Continuous casting; Decomposition; Hybrid flowshop; Integer programming; Iron and steel making; Job shops; Lagrange multiplier; Mathematical analysis; Mathematical models; Production scheduling; Scheduling; Steel production; Steelmaking-continuous casting; Steels; Studies; Subgradient optimization
• ISSN: 0377-2217; 1872-6860
• DOI: 10.1016/j.ejor.2013.11.010

•The SCC scheduling problem is modeled as a mixed-integer programming (MIP) problem.•A Lagrangian relaxation (LR) approach based on machine capacity relaxation is presented to address the MIP problem.•An improved subgradient level algorithm with global convergence is presented to solve the Lagrangian dual problem.•To deal with the unboundedness of the LR problem in iterations, we propose a boundedness detection method and a time horizon method. One of the largest bottlenecks in iron and steel production is the steelmaking-continuous casting (SCC) process, which consists of steel-making, refining and continuous casting. The SCC scheduling is a complex hybrid flowshop (HFS) scheduling problem with the following features: job grouping and precedence constraints, no idle time within the same group of jobs and setup time constraints on the casters. This paper first models the scheduling problem as a mixed-integer programming (MIP) problem with the objective of minimizing the total weighted earliness/tardiness penalties and job waiting. Next, a Lagrangian relaxation (LR) approach relaxing the machine capacity constraints is presented to solve the MIP problem, which decomposes the relaxed problem into two tractable subproblems by separating the continuous variables from the integer ones. Additionally, two methods, i.e., the boundedness detection method and time horizon method, are explored to handle the unboundedness of the decomposed subproblems in iterations. Furthermore, an improved subgradient level algorithm with global convergence is developed to solve the Lagrangian dual (LD) problem. The computational results and comparisons demonstrate that the proposed LR approach outperforms the conventional LR approaches in terms of solution quality, with a significantly shorter running time being observed.