A simplified steel plate stacking problem

Abstract

This article examines a simplified steel plate stacking problem. Manufactured thick steel plates arrive in series at a storage area, which consists of a certain number of uncapacitated beds. The arriving plates are first stacked on beds, after which the plates are removed in the pre-defined delivery sequence. No more than one plate can be moved simultaneously. When a target plate is not in the top position of a bed, the plates that block the target plate must be relocated. This relocation of a plate is called shift. Depending on the problem situation, it is assumed that the relocated plates must be replaced on to the original beds so they can cause multiple shifts or once they are relocated, they are treated separately in different beds so that they cause no more shifts to the original stacking. The problem is to make a storage plan that requires the minimum number of shifts in the delivery stage. This article shows that the problem is difficult to solve. Several mathematical models are developed to get optimal solutions for small problems and lower bounds for large problems. An iterative randomised approach is also proposed as a solution approach for large problem instances, and its effectiveness is shown by some computational experiments on benchmark problem sets.

Keywords:

• steel stacking problem
• mixed integer linear program
• linearisation
• heuristics

Acknowledgments

We thank Mr Sang-Jin Ko for providing the benchmark problem sets and related programs. We also thank the anonymous referees for their valuable comments and suggestions for improving this article.