A combination of Lagrangian relaxation and column generation for order batching in steelmaking and continuous‐casting production |
| |
Authors: | Lixin Tang Gongshu Wang Jiyin Liu Jingyi Liu |
| |
Institution: | 1. Liaoning Key Laboratory of Manufacturing System and Logistics, The Logistics Institute, Northeastern University, Shenyang, China;2. School of Business and Economics, Loughborough University, Loughborough, Leicestershire LE11 3TU, United Kingdom;3. Department of Mathematics, Northeastern University, Shenyang, China |
| |
Abstract: | This article considers the order batching problem in steelmaking and continuous‐casting production. The problem is to jointly specify the slabs needed to satisfy each customer order and group all the slabs of different customer orders into production batches. A novel mixed integer programming model is formulated for the problem. Through relaxing the order assignment constraints, a Lagrangian relaxation model is then obtained. By exploiting the relationship between Lagrangian relaxation and column generation, we develop a combined algorithm that contains nested double loops. At the inner loop, the subgradient method is applied for approximating the Lagrangian dual problem and pricing out columns of the master problem corresponding to the linear dual form of the Lagrangian dual problem. At the outer loop, column generation is employed to solve the master problem exactly and adjust Lagrangian multipliers. Computational experiments are carried out using real data collected from a large steel company, as well as on large‐scaled problem instances randomly generated. The results demonstrate that the combined algorithm can obtain tighter lower bound and higher quality solution within an acceptable computation time as compared to the conventional Lagrangian relaxation algorithm. © 2011 Wiley Periodicals, Inc. Naval Research Logistics, 2011 |
| |
Keywords: | steelmaking and continuous‐casting batching mixed integer programming Lagrangian relaxation column generation |
|
|