Scheduling Problems in Automated Guided Vehicle Systems

Abstract

The scheduling problems in Automated Guided Vehicle Systems are investigated. A survey of vehicle routing and scheduling problems is presented. The characteristics of Automated Guided vehicle Systems (AGVS's) are described. A taxonomy is developed for the Vehicle Scheduling Problem in AGVS's, and formulations are presented for the most important problems. Heuristic algorithms are developed to solve three of the scheduling problems in AGVS's: the Vehicle Scheduling Problems (VSP's) with fixed start times and minimum route length and minimum cost objectives, and the minimum-cost VSP with time windows. A fast implementation of the Dilworth decomposition algorithm, 0(n 2 ), is developed to solve the traditional minimum-vehicle VSP as applied to AGVS's. A sub-gradient algorithm is developed to solve the minimum-cost VSP with fixed start times; the algorithm uses a new application of Lagrangian multipliers in an upper-bound heuristic. The algorithms are analysed and the heuristic algorithms are shown to have complexity 0(n 2 ) and also to be capable of solving problems with up to 800 tasks in less than 30 seconds. The solutions to problems with 100 tasks are shown to be within 20 percent of the optimal solutions, for the particular types of data used.