Une nouvelle approche est développée dans cet article pour résoudre le problème de la planification stratégique de production d'une mine à ciel-ouvert dans un contexte d'incertitude à éléments multiples. La méthode repose sur l'extension de l'algorithme Bienstock-Zuckerberg (BZ) à l'optimisation stochastique. Le but de l'algorithme BZ est d'exploiter la structure particulière du problème pour résoudre efficacement sa relaxation linéaire. Les résultats numériques, suite à une application sur une instance de taille réelle, montrent que la relaxation linéaire peut être résolue à l'optimal en quelques minutes, alors que Cplex prend plusieurs heures à le résoudre. Ensuite, en appliquant successivement une heuristique d'arrondissement basée sur un ordonnancement topologique et une seconde heuristique basée sur la recherche Tabou, une solution entière réalisable est obtenue avec un saut d'optimalité allant de 1 à 2%.