The complexity and on-line algorithm for automated storage and retrieval system with stacker cranes on one rail

This paper considers an on-line scheduling and routing problem concerning the automated storage and retrieval system from tobacco industry. In this problem, stacker cranes run on one common rail between two racks. Multiple input/output-points are located at the bottom of the racks. The stacker cranes transport bins between the input/output-points and cells on the racks to complete requests generated over time. Each request should be accomplished within its response time. The objective is to minimize the time by which all the generated requests are completed. Under a given physical layout, the authors study the complexity of the problem and design on-line algorithms for both one-stacker-crane model and two-stacker-crane model. The algorithms are validated by instances and numerical simulations.