Research On Location Assignment And Job Scheduling In Multi-shuttle Automated Storage And Retrieval System

Warehouses play an essiential role in any supply chain. The optimizationof warehouse operation is an important approach to increase the overallefficiency of supply chain. As a dominant type of warehouse, AutomatedStorage and Retrieval System (AS/RS) is becoming a bottleneck of the supplychain with the demand of higher throughput. On the other hand, due to thecharacteristic of high throughput and high flexibility, the novel multi-shuttleAS/RS is identified as the future direction of AS/RS. Multi-shuttle AS/RScould also be seen as the generalization of traditional single-shuttle AS/RS.Therefore, the operation optimization in multi-shuttle AS/RS is not only ofsignificance to improve the performance of multi-shuttle AS/RS, but alsohelpful to instruct maximizing the existed single-shuttle AS/RSs' operationefficiency. This dissertation investigates the main operation decision problemsincluding storage location assignment and job scheduling in multi-shuttleAS/RS. The performance evaluation method is also explored.Based on the real-time location states, the study establishes a0-1programming model to describe the location assignment problem while thelocation assignment in retrieval operation is additionally considered.According to the characteristics of this problem, a genetic algorithm based onnearest neighbor strategy is developed to decide the storage locationassignment and retrieval location assignment simultaneously. Theeffectiveness of the proposed algorithm is demonstrated by numericalexperiments. Moreover, this dissertation improves the research on optimalboundaries in the class-based storage strategy by considering theacceleration/deceleration of the storage and retrieval machine.This study focuses on the job scheduling problem in multi-shuttle AS/RSby investigating the pattern of generating operation cycles. Considering therequest partitioning, request pairing and request sequencing, an integerprogramming model aiming to minimizing the travel time of performing givenrequests is constructed. This dissertation firstly proves that the job scheduling problem in multi-shuttle AS/RS is NP-hard. A column generation algorithm isproposed to yield the valid lower bound of this model.To the best of the author's knowledge, this dissertation is the first topropose the joint optimization of location assignment and job scheduling. Boththe situations of performing single operation cycle and multiple operationcycles are considered. Two related models including an integer programmingmodel and a multi-stage optimization model are developed to formulate theproblem. A two-phase tabu search algorithm is proposed to solve the integerprogramming model for the situation of performing a single operation cycle.Based on the results obtained by the two-phase tabu search algorithm, aconstruction heuristic is developed to improve the solution for the situation ofperforming multiple operation cycles. The computational results indicate thatthe two-phase tabu search algorithm is effective and efficient in finding goodsolutions especially for the large-sized problems. The result further revealsthat the construction heuristic can also significantly improve the quality of thesolution for the situation of performing multiple operation cycles.This dissertation derives the general analytical model to evaluate theperformance of multi-shuttle AS/RS. The excellent throughput performance ofmulti-shuttle AS/RS is demonstrated in theory. The numerical results fromMonte Carlo simulation experiment show the proposed model is an accuratemethod to evaluate the throughput of multi-shuttle AS/RS.