Retrieval request scheduling in a shuttle-based storage and retrieval system with two lifts

We study a shuttle-based storage and retrieval system with two independent lifts shared in a single mast. In such a system, two lifts move simultaneously but cannot pass each other, and each retrieval request is finished with the cooperation of a lift and a shuttle. Therefore, given a set of retrieval requests, the retrieval request scheduling problem consists of determining the sequence in which the requests are retrieved and assigning each request to a lift with the objective of minimizing the makespan, considering both the lift-lift interaction and lift-shuttle interaction. The problem is formulated as a mixed-integer programming model and proved to be NP-hard. We propose a decomposition-based adaptive large neighborhood search heuristic to quickly compute near-optimal solutions, using the property that the assignment of requests to lifts for a given retrieval sequence can be exactly solved in polynomial time by a dynamic programming approach. Numerical results indicate that our algorithm achieves a lower makespan than the methods proposed in the literature and used in practice. We also apply the proposed algorithm using real data to a realistic setting that considers multiple planning horizons, showing that it significantly outperforms the policy the company currently uses.