Design and optimization of puzzle-based storage systems with unidimensional movements

Abstract

Puzzle-Based Storage Systems (PBS) are very high-density parts-to-person storage systems for unit loads. This type of system is composed of a grid with 𝑚 rows and 𝑛 columns. The grid is composed of cells that may carry loads on top of them. Retrieving a load from a PBS requires sequentially moving loads to cells without a load until the required load reaches the output point. Since loads need to be slid into cells without a load, these cells are commonly referred to as escorts.

A paradigm for Puzzle-Based Storage Systems (PBS) is that all cells are designed with the capability to transport loads horizontally and vertically. This study challenges this paradigm by proposing unidimensional PBS (UPBS), where some cells are limited to transporting loads either horizontal or vertical movements. UPBS require a lower investment cost, compared to traditional PBS, at the expense of lower throughput capacity.

This thesis introduces the concept of UPBS and presents a linear program (LP) formulation to find the optimal load retrieval path for a single load using a single escort in a UPBS. The LP is solved recursively to understand the cost-to-throughput tradeoffs of unidimensional designs for a 4×4 grid system. It is concluded that it is possible to design UPBS with 25% of the possible unidimensional cells, while reducing the throughput by approximately 10%. A multi-escort formulation for the single load problem is also proposed and used in combination with an existing PBS formulation to understand UPBS design tradeoffs for systems with multiple escorts and a single input/output point. It is concluded that UPBS can be designed such that the capital investment cost to throughput tradeoff is favorable when retrieving a single load.

An existing decentralized PBS algorithm for retrieving multiple loads considering multiple input/output points was coded in Python and modified for UPBS. Upon proper validation of the code, it was used to develop managerial insights for designing UPBS. For UPBS systems with simultaneous retrievals, multiple escorts, and multiple I/O Points, the layout depends on the number of loads requested at the same time (i.e., WIP level). For low WIP levels, it is possible to design UPBS with 33.33% of unidimensional rows, which would have implications of a 9.82% increase in throughput and for medium WIP levels with 41.66% of unidimensional rows would have implications of a 9.29% increase in throughput. The increase of throughput is a consequence of the decentralized PBS algorithm forcing some unrequested loads out of the system to prevent gridlocks. Therefore, UPBS with single and multiple escorts can maintain their throughput, with a lower investment cost.

Los sistemas de almacenamiento basados en rompecabezas (PBS, por sus siglas en inglés) son aquellos que cuentan con una muy alta densidad para cargas unitarias, donde la pieza se dirige al operador. Este tipo de sistema se compone de 𝑚 filas y 𝑛 columnas. La cuadrícula está compuesta de celdas que pueden llevar cargas sobre ellas. Recuperar una carga de un PBS requiere mover secuencialmente cargas a celdas sin carga hasta que la carga requerida alcance el punto de salida. Dado que las cargas deben deslizarse hasta celdas sin carga, éstas suelen comúnmente denominarse escoltas.

Un paradigma de los sistemas de almacenamiento basados en rompecabezas (PBS) es que todas las celdas están diseñadas para transportar cargas horizontal y verticalmente. Este estudio desafía este paradigma proponiendo PBS unidimensionales (UPBS, por sus siglas en inglés), en los que algunas celdas se limitan a transportar cargas en movimientos horizontales o verticales. Los UPBS requieren un menor costo de inversión, en comparación con los PBS tradicionales, a expensas de una menor capacidad de rendimiento.

Esta tesis introduce el concepto de UPBS y presenta una formulación de programación lineal (LP) para encontrar la ruta óptima de recuperación para una sola carga, utilizando una sola escolta en un UPBS. El LP es resuelto recursivamente para comprender las compensaciones entre el costo y el rendimiento de diseños unidimensionales para un sistema de cuadrícula con dimensiones 4×4. Se concluye que es posible diseñar UPBS con el 25% de las celdas unidimensionales posibles, reduciendo, al mismo tiempo, el rendimiento en aproximadamente un 10%. De igual manera, se propuso una formulación multi-escolta para una sola carga y se utiliza en combinación con una formulación de PBS existente para comprender las ventajas y desventajas del diseño UPBS para sistemas con múltiples escoltas y un único punto de entrada/salida. Se concluye que UPBS pueden ser diseñados de forma que el costo de inversión de capital y el rendimiento sean favorables cuando se recupera una sola carga.

Un algoritmo existente para recuperar múltiples cargas con múltiples puntos de entrada/salida en PBS descentralizados fue programado en Python y modificado para UPBS. Una vez validado el código, se utilizó para desarrollar ideas de gestión en el diseño de UPBS. Para sistemas UPBS con recuperaciones simultáneas, múltiples escoltas y múltiples puntos de entrada/salida, el diseño depende del número de cargas solicitadas al mismo tiempo (WIP, por sus siglas en inglés). Para niveles bajos de WIP es posible diseñar UPBS con 33.33% de filas unidimensionales, lo que implicaría un incremento en el rendimiento del 9.82% y para niveles de WIP medios, con 41.66% de filas unidimensionales tendría implicaciones en el incremento del rendimiento en 9.29%. El aumento en rendimiento es una consecuencia del algoritmo descentralizado, obligando a cargas no solicitadas a salir para prevenir el bloqueo del sistema. Por lo tanto, UPBS con escoltas simples y múltiples pueden mantener su rendimiento, con un menor costo de inversión.