A new solution approach is developed herein to address the topic of multi-product open-pit mine production scheduling with multi-element uncertainty. The method is based on extending the Bienstock-Zuckerberg (BZ) algorithm to the stochastic optimization. The purpose of the BZ algorithm is to exploit the structure of the problem to solve its linear programming relaxation (LP) efficiently. Numerical results on a real-size instance show that the LP can be solved to optimality in few minutes, while Cplex takes several hours to solve it. Following this with a rounding heuristic based on topological sorting and a second heuristic based on Tabu Search, a feasible integer solution is then obtained within 1-2% of optimality.