An important step when designing a Flexible Manufacturing System (FMS) using Automated Guided Vehicles (AGVs) is the definition of the number of AGVs to be used in order to reach a given productivity. A way to define this number is to consider several scenari, to define the minimal number of AGVs required by each scenario, and to keep the maximal of these numbers. In this paper, we propose a Branch and Bound (B&B) approach to define the minimal number of AGVs require for a scenario. This approach is based on an Event Graph (EG) formulation.