This paper presents an approach to provide stochastic bounds for models based on task graphs completion when the elementary durations are stochastic and not independent. When the parameters are deterministic, the complexity of computing the completion time is polynomial. Here, we consider the much more complex case where the durations are discrete random variables. Such an assumption drastically changes the complexity of the problem. Furthermore, we assume that these random variables are somehow correlated. We propose to give stochastic bounds based on the stochastic order for discrete multivariate random vectors to compute bounds on the completion time.