Portal de Periódicos da CAPES

A nested column generation algorithm to the meta slab allocation problem in the steel making industry

2008; Taylor & Francis; Volume: 47; Issue: 13 Linguagem: Inglês

10.1080/00207540801968625

1366-588X

Sang Hwa Song,

Scheduling and Optimization Algorithms

Abstract This paper addresses one of the key operational decision problems in the steel industry which is related to the allocation of orders to stock materials in the surplus inventory. The meta slab allocation problem can be stated as the 'multi-stage multiple knapsack problem' where the problem is to design slabs using orders with similar properties (the first stage) and allocating these designed slabs into the existing meta slabs in the inventory yard (the second stage). The objective of the problem is to maximise the allocated order weights in slabs and meta slabs. For the given problem, we propose a column generation algorithm, where a column in the master problem represents meta slabs and the sub problem is to design 'bins', here slabs with the given orders. The sub problem itself also becomes a multiple knapsack problem and we proposed a practical set-partitioning heuristic. The proposed algorithm was tested with daily operation data given from an integrated steel company in the Asia Pacific. The computational results showed that the proposed heuristic solved the real instances pretty well. The proposed algorithm was successfully deployed to the integrated steel mill. Keywords: column generationsteel industrymaterial allocationmultiple knapsack problem Acknowledgements I thank Dr Jayant Kalagnanam for his helpful suggestions in designing the overall algorithm structure, and Dr Chandra Reddy, Dr Sanjeeb Dash and Mr Yong Kwan Kim for their help in clarifying the problem to be solved. I also thank Mr Mark Trumbo for his help in implementing a part of the solution algorithms.