This paper presents a new approach for planning the dispatching, conflict-free routing, and scheduling of automated guided vehicles in a flexible manufacturing system. The problem is solved optimally in an integrated manner, contrary to the traditional approach in which the problem is decomposed in three steps that are solved sequentially. The algorithm is based on dynamic programming and is solved on a rolling time horizon. Three dominance criteria are used to limit the size of the state space. The method finds the transportation plan minimizing the makespan (the completion time for all tasks). Various results are discussed. A heuristic version of the algorithm is also proposed for an extension of the method to many vehicles.