Dynamic route planning and scheduling in flexible manufacturing systems with heterogeneous resources, a max-plus approach

In this work an Auto Guided Vehicles (AGV) scheduling and routing problem is considered with maximal and minimal time lags along with heterogeneous characteristics. A framework with dynamic flow control has been proposed for the execution of events dedicated to a fleet of AGVs. The proposed framework allows the setting up for missions which are defined by a set of routes and stations regardless of the actual characteristics of the AGV fleet. The routing and scheduling method is formulated with potential inequalities and disjunctive constraints, which are expressed in Max Plus Algebra in terms of inequalities. The computation of the eigenvalue of the corresponding matrices takes the advantage of the fast Howard's algorithm for policy iteration. The Branch and Bound procedure is used to solve medium sized routing and scheduling problems involves a test on this eigenvalue.