Dense and fast: Achieving shortest unimpeded retrieval with a minimum number of empty cells in puzzle-based storage systems

This article studies puzzle-based storage (PBS) systems with multiple simultaneously movable empty cells and with block movement (i.e., multiple loads in a line can move simultaneously). Simultaneous movements can potentially reduce the retrieval time substantially, but has not yet been rigorously studied. Our aim is to determine the minimum number of empty cells sufficient for creating a shortest and unimpeded retrieval path for a requested load to the Input/Output (I/O) point at the bottom left corner of the system. We prove that four (or five) empty cells are sufficient for shortest unimpeded retrieval of a load from any interior location (or location on the left or bottom boundary), independent of the system size. This means the vast majority of cells in the system can be utilized for storing loads without any impact on the retrieval time. In addition, constructive optimal algorithms are developed for scheduling four or five empty cells to realize shortest unimpeded retrieval. Interestingly, the requested load’s shortest unimpeded retrieval path to the I/O point may contain upward or rightward movements, even if the I/O point is at the bottom left corner of the system. Compared with systems with one empty cell (sequential movements), systems with four or five empty cells (simultaneous movements) can bring about 70% (50% or more) retrieval time reduction. Furthermore, PBS systems can yield shorter average retrieval time (in addition to their intrinsic advantage of a higher storage density), compared with parallel-aisle unit-load storage systems.