Groupe d’études et de recherche en analyse des décisions


Production scheduling under undertainty for an open pit mine using Lagrangian relaxation and branch-and-cut algorithm


The production scheduling of an open pit mine determines the optimal extraction sequencing that significantly impacts a mine's life as well as net present value. The optimization of production scheduling of large open pit mines with geological uncertainty is a computationally very intensive process. In this paper, an approximation algorithm is proposed to schedule an open pit mine, where instead of solving the whole problem at once, the production schedule is generated by sequentially solving sub-problems. The sub-gradient method is used to generate the upper bound solution of a Lagrangian relaxed sub-problem. If the upper bound relaxed algorithm is not a feasible solution, a mixed integer programming is applied on the generated upper-bound solution. The algorithm is validated by solving three problems and is compared to the linear relaxation of the original production scheduling problem. The results show that the proposed algorithm generates a solution very close to optimal with less than a 2% optimality gap.

An application at a copper mine with an orebody represented by 16532 mining blocks is presented using the proposed algorithm. Results show that all constraints are satisfied. The net present values are also calculated and results reveal that an 11% higher net present value (NPV) is generated when compared to the NPV generated when the same approach is applied to the deterministic model of the deposit where uncertainty is not accounted for. Furthermore, a comparative study with the conventional approach shows that the approach proposed here generates a schedule with at least 26% higher NPV. The comparative study also demonstrated that the proposed method generates a pit which is bigger in size (at least 10%) when compared with both the deterministic and conventional approaches.

, 19 pages