Simultaneous scheduling of machines and automated guided vehicles

This paper is an attempt to make scheduling of AGVs an integral part of the overall scheduling activity in an FMS environment. The sequence-dependent nature of travel times for the deadheading trips between successive loaded trips of the AGVs increases the problem difficulty. The problem is decomposed into two subproblems, and previous work on machine scheduling and vehicle scheduling has been exploited to arrive at an iterative heuristic procedure where makespan is the performance criterion. At each iteration, a new machine schedule, generated by a heuristic procedure, is investigated for its feasibility to the vehicle scheduling subproblem. The operation completion times obtained from the machine schedule are used to construct time windows for each material handling trip, and the second subproblem is handled as a sliding time window problem. A set of problems are solved to analyse the impact of the process times/travel times ratio on the performance of the procedure. The interaction between the layout configuration and the process routes is studied, and two AGV routeing policies are compared.