Retrieval time performance in puzzle-based storage systems

Puzzle-based storage is a novel approach enabling very dense storage. Previous analytical studies have focussed on retrieval time when one or more usable escort locations (empty slots) are located near the system input/output location, and on simulation results for more complex situations. The purpose of this paper is to extend analytical results to determine retrieval time performance when multiple escorts are randomly located within the system.

Closed-form expressions for retrieval time are developed and proven for cases in which the number of free, randomly placed escorts is equal to one or two. Heuristics with associated worst case bounds are proposed for larger numbers of free escorts.

Puzzle-based storage systems are practical and viable ways to achieve storage density, but retrieval time is heavily dependent upon suitable use of escort locations. Analytical and heuristic methods developed within the paper provide worst-case retrieval time performance in a variety of settings.

As the number of free, randomly located escorts increases, optimal analytical solutions are difficult to obtain. Heuristics provide viable retrieval strategies in these situations, and worst-case bounds are relatively easily developed.

The primarily contribution of this paper is to make theoretical extensions of optimal methods for puzzle-based storage systems. It motivates additional research in multiple-escort systems and provides insights that should prove useful for the development of 3-dimensional puzzle-based systems and for systems in which concurrent item movement is permitted.