Groupe d’études et de recherche en analyse des décisions


A Scheduling and Conflict-free Routing Problem Solved with a Hybrid Constraint Programming/Mixed Integer Programming Approach

, et

We propose a hybrid method designed to solve a problem of dispatching and conflict-free routing of Automated Guided Vehicles (AGVs) in a Flexible Manufacturing System (FMS). This problem consists in the simultaneous assignment, scheduling and conflict-free routing of the vehicles. Our approach consists in a decomposition method where the master problem (scheduling) is modeled with Constraint Programming and the sub problem (conflict-free routing) with Mixed Integer Programming. Logic cuts are generated and used to prune optimal scheduling solutions whose routing plan exhibits conflicts. The hybrid method presented herein allowed to solve instances with up to six AGVs.

, 25 pages