This paper presents a metaheuristic solution to the optimization of open pit long-term production scheduling with a stockpile and geological uncertainty. The optimization formulation is a two stage stochastic integer programming (SIP) model, which determines the optimal mining sequence that maximizes the total discounted cash flow, while penalizing for high deviations from production targets. A parallel implementation of Tabu Search is proposed to accelerate the solution of the SIP formulation and take full advantage of multi-core computer processing. Different variants of the proposed algorithm are applied at a case study to assess the performance of the parallel approach. The proposed algorithm and variants are benchmarked using linear relaxation of the complete problem to determine robustness and provide a better overview of the related performance. The results show a net improvement over the sequential solution and the new proposal seems to be promising when working with a large scale data set.