Abstract: Production grids are complex and highly variable systems whose behavior is not well understood and difficult to anticipate. The goal of this study is to estimate the impact of the variability of those infrastructures on the performance of workflow-based applications. A probabilistic model of workflows execution time is proposed and evaluated. Results show that the variability of the EGEE grid infrastructure impacts the execution time of a particular medical image analysis application by a factor 2. The model gives interesting insights on the grid behavior for different application parallelization modes.