Models and algorithms for shuffling problems in steel plants

作者：Tang Lixin^*; Zhao Ren; Liu Jiyin

来源：Naval Research Logistics, 2012, 59(7): 502-524.

DOI：10.1002/nav.21503

• shuffling problem
• steel warehouse
• integer programming
• heuristics
• rolling horizon
• tabu search

In this article, we study item shuffling (IS) problems arising in the logistics system of steel production. An IS problem here is to optimize shuffling operations needed in retrieving a sequence of steel items from a warehouse served by a crane. There are two types of such problems, plate shuffling problems (PSP) and coil shuffling problems (CSP), considering the item shapes. The PSP is modeled as a container storage location assignment problem. For CSP, a novel linear integer programming model is formulated considering the practical stacking and shuffling features. Several valid inequalities are constructed to accelerate the solving of the models. Some properties of optimal solutions of PSP and CSP are also derived. Because of the strong NP-hardness of the problems, we consider some special cases of them and propose polynomial time algorithms to obtain optimal solutions for these cases. A greedy heuristic is proposed to solve the general problems and its worst-case performances on both PSP and CSP are analyzed. A tabu search (TS) method with a tabu list of variable length is proposed to further improve the heuristic solutions. Without considering the crane traveling distance, we then construct a rolling variable horizon heuristic for the problems. Numerical experiments show that the proposed heuristic algorithms and the TS method are effective.

• 出版日期2012-10
• 单位东北大学