We will present a novel approach to control a fleet of autonomously guided vehicles whose task is to process transportation requests arriving on-line. The main goal is to avoid deadlocks and to serve all requests without (much) delays. The vehicles work in a workshop, where there can be narrow corridors, gates, small and big halls. We define a graph representation of the layout of the operation area whose nodes are the crossing points, and the edges represent path segments that the vehicles must follow. The novelty of our approach is that by explicitly representing the schedule of the vehicles (considering each node and edge as a resource, and crossing them by jobs), we can guarantee a deadlock-free movement, and a suboptimal fulfillment of the transportation requests. However, it is not obvious how to obtain and keep up to date such a feasible schedule. For instance, when a new transportation request arrives, we have to choose a vehicle to process it, and then create a new route and insert it into the schedule. However, there can be idle vehicles at the target location or on the way of this vehicle. Such blocking vehicles must be given some route to some free, non-disturbing locations, and their movements to those locations must also be scheduled. Since the transportation requests have due dates, we bear in mind the minimization of the maximum tardiness during the insertion of the routes. We also apply a local search approach to improve the quality of the schedules.