Journal
NAVAL RESEARCH LOGISTICS
Volume 58, Issue 4, Pages 370-388Publisher
WILEY-BLACKWELL
DOI: 10.1002/nav.20452
Keywords
steelmaking and continuous-casting; batching; mixed integer programming; Lagrangian relaxation; column generation
Categories
Funding
- National Natural Science Foundation of China [71032004, 70728001]
Ask authors/readers for more resources
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. (C) 2011 Wiley Periodicals, Inc. Naval Research Logistics 58: 370-388, 2011
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available