•Proposes a model of multiple automated guided vehicles.•Proposes an algorithm providing their optimal work sequence minimizing a given cost.•Tackles the robustness issue pertaining their nominal and real performance.•Proposes a fault-tolerant control strategy for multiple automated guided vehicles.•The proposed algorithm can perform on-line with low computational burden. An advanced control of manufacturing and transportation systems forms a prominent research field with powerful algorithms developed in the last decades. Challenges still arise, if several automated guide vehicles (AGV) have to be coordinated. This paper focuses on the modelling and fault-tolerant control of multiple AGVs. The considered application concerns a highly flexible AGV transportation system delivering product items to transfer stations at a high-storage warehouse in a manufacturing system. The research contribution concerns the development of a mathematical description of a set of multiple AGVs along with an algorithm that can generate an optimum sequence of item outlet delivery times. The proposed solution addresses both synchronization and concurrency issues, which are inevitable in this kind of multiple-vehicle systems. Apart from these issues, modelling inaccuracy is also addressed using interval analysis coupled with max-plus algebra. Subsequently, fault diagnosis and fault-tolerant control are also investigated and addressed in the proposed approach. This leads to a fault-tolerant control framework, which is based on a fusion of the predictive control and interval max-plus algebra. The distinct quality of the proposed approach is that the optimization can be carried out in a reliable way and that certain faults and modeling uncertainties can be tolerated. The paper concludes with illustrative examples, which show the performance of the proposed approach using both fault-free and faulty scenarios.