Optimal Algorithms for Scheduling Multiple Simultaneously Movable Empty Cells to Retrieve a Load in Puzzle-Based Storage Systems

Puzzle-based storage systems (PBSs) can achieve very high utilization of expensive and scarce storage space coupled with fully automated storage and retrieval of unit loads. A PBS system with one empty cell is comparable to the well-known 15-puzzle, in which 15 tiles slide in a 4×4 grid. This paper studies PBSs that contain multiple (two or more) empty cells that can move simultaneously, while also allowing block movement (i.e., multiple loads located in a line can move simultaneously). Efficient algorithms are developed to minimize the number of steps required for retrieving a requested load from any location to the I/O point at the bottom left corner of the system. We first distinguish two types of delay conflicts among simultaneously moving empty cells. The first type of conflict can be avoided by properly scheduling empty cell movements. We develop a lower bound model to determine the optimum number of steps for situations where the second type of conflict can occur. Subsequently, we construct optimal algorithms, based on the optimal solutions of the lower bound model, for the original problem. Our results show that an optimal path can contain upward or rightward movements of the requested load, even if the I/O point is at the bottom left corner. In addition, at most five empty cells are needed to unimpededly retrieve a requested load from any location to the I/O point. A specific correspondence exists between each location and the minimum number of empty cells needed to retrieve a requested load from this location to the I/O point without delays