RETRIEVAL SEQUENCING FOR UNIT-LOAD AUTOMATED STORAGE AND RETRIEVAL-SYSTEMS WITH MULTIPLE OPENINGS

Automated storage and retrieval systems (AS/RS) have made a dramatic i mpact on material handling and inventory control in warehouses and pro duct systems. A unit-load AS/RS is generic and other AS/RS represent i ts variations. In this paper, we study a problem of sequencing retriev al requests in a unit-load AS/RS. In a unit-load AS/RS, there are usua lly multiple openings and a unit-load can be stored in any opening. Gi ven a list of retrieval requests and the locations of openings, this p roblem seeks a sequence of dual cycles that minimizes total travel tim e taken by a storage/retrieval machine. Previous researchers believed that this problem is computationally intractable and provided greedy-s tyle heuristic algorithms. In this paper, we present an algorithm that combines the Hungarian method and the ranking algorithm for the assig nment problem with tour-checking and tour-breaking algorithms. We show that this algorithm finds either a verified optimal or near-optimal s olution quickly for moderate size problems. Using this algorithm, we a lso evaluate the effectiveness of the existing simple heuristics. Comp utational results are reported.