A New Algorithm for the Open-Pit Production Scheduling Optimization Problem

Open-pit mine production scheduling optimization is pivotal in ensuring a mine operates profitably. However, achieving optimality in a production schedule is often intractable. This is due to two factors. The first is the NP-hard classification of the problem, meaning there are no known efficient algorithms for finding exact solutions. The second is the large scale of realistic block models, which can lead to millions of variables and constraints with which the optimization problem is subject to. Therefore, it is common practice to rely on heuristics and block aggregation methods for generating operationally feasible solutions. However, these solutions are not guaranteed to be optimal and are more often than not far from optimality. This research presents an alternative for gathering optimal and near-optimal solutions through a novel relaxation-repair algorithm. Precedence constraints, which make up the majority of the constraints present in an open-pit production scheduling optimization problem, represent open-pit slope stability. However, due to how they are enforced, each is implied by the other precedence constraints when the full precedence set is considered. Because of this, the constraint matrix size is inflated, and the solver’s performance decreases. The goal of this research is to showcase a method for applying only subsets of precedence constraints instead of the full precedence set. The initial relaxation phase of the algorithm solves, to optimality, the problem with only a subset of the precedence constraints. However, the relaxation is not assured to be operationally feasible with respect to the full precedence set. Therefore, a final repair phase is conducted to recover feasibility. Some instances were able to achieve optimality without requiring a repair step. Through testing, this algorithm has shown that it can outperform a traditional precedence formulation in several instances. In some cases, the algorithm generated optimal and near-optimal (