Scheduling Parallel Cranes for Unit-Load Automated Storage and Retrieval Systems with Shared Storage

Abstract

Motivated by observing real-world instances of multi-aisle automated storage and retrieval systems (AS/RSs) with shared storage, we introduced a new optimization problem called the parallel crane scheduling (PCS) problem. Unlike the single crane scheduling (SCS) problem, the decisions of the PCS problem include not only the request sequencing and storage/retrieval location selection, but also assigning requests to cranes. The PCS problem better reflects the real-life situation, but it is more complex, since these three decisions are interrelated and interact with one another. In this study, since the empty location vacated by any retrieval operation is instantly available, we introduced a new dynamic programming model combined with a mixed-integer linear programming model to describe this complex problem. Considering the feature of location-dependent processing time, we transformed the PCS problem into a variant of the unrelated parallel machine scheduling problem. We developed an apparent tardiness cost-based construction heuristic and an ant colony system algorithm with a problem-specific local optimization. Our experiments demonstrated that the proposed algorithms provide excellent performance, along with the insight that globally scheduling multiple aisles could be considered to reduce the total tardiness when designing an operation scheme for multi-aisle AS/RSs.

Keywords

• automated storage and retrieval systems
• multiple aisles
• parallel crane scheduling problem
• unrelated parallel machines
• ant colony system