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

作者：Song Sang Hwa^*

来源：International Journal of Production Research, 2009, 47(13): 3625-3638.

DOI：10.1080/00207540801968625

• column generation
• steel industry
• material allocation
• multiple knapsack problem

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.

• 出版日期2009