Long-term open pit mine scheduling is generally assessed with a mixed integer programming (MIP) formulation which can be solved with different operations research techniques. To be closer to the reality of the exploitation, a model can, for instance, take into account a substantial number of blocks to represent the ore body, include several destinations, or consider the uncertainty of the geology with a stochastic formulation. The inherent complexity of such a model becomes too great to obtain an optimal solution or even a good feasible solution within a reasonable computational time. This paper first proposes several strategies to facilitate the resolution of such an MIP by reducing the number of binary variables. To do so, no assumptions are made over the final result; only a relaxation of binary constraints over a special pattern is considered. A fast heuristic method, defined as a stochastic topological sorting method, is also developed and provides a proof of optimality. The proposed methods are tested on a real case study and provide results within 2% of optimality after 12 minutes and down to 0.3% if a longer running time is allowed.