A greedy genetic hybrid heuristic for solving the openpit production scheduling problem

Openpit mine production scheduling (OPPS) is defined as “specifying the sequence of blocks extraction from the mine to give the highest economic net present value (NPV), subject to a variety of production, grade blending and pit slope constraints.” This scheduling problem is a discrete optimization problem that is classified as a nonpolynomial time hard problem (NP hard). Accordingly, reaching global optima is computationally intensive. Hence, computational time and power are always the major concerns for OPPS optimization algorithms. This is referenced to the complexity of the problem and the substantial number of decision variables within any pit design. As a result, heuristic and metaheuristic algorithms have been more favorable than conventional optimization algorithms. Recently, evolutionary algorithms — that is, genetic algorithms (GAs) — have shown advantages in finding enhanced solutions, which provided the foundation for this study. Background The primary objective of the OPPS problem is to assign the exploitation of each block to a specific time period within the lifespan of the openpit mine. From the time point of view, production scheduling of openpit mines has been divided into three categories: long term, medium term and short term. Early attempts to solve the problem primarily depended on the conventional deterministic optimization approaches. These approaches include linear programming (LP) and usual mixed integer programming, which proved to have major disadvantages due to the complexity and the size of the problem. Hence, it was of utmost importance to intelligently design pushbacks to divide the large problem into smaller ones. Nevertheless, the prior design of the pushbacks resulted in another major optimality gap problem. Based on that, an approximate near-optimal solution has become the target of researchers in order to reduce computational time. Therefore, heuristic and search algorithms have been exploited and studied to solve the OPPS problem. Fig. 1 Box plots for the studied instances comparing NPV of GA versus GGHA. The literature review led to an observation that the research in utilizing GAs to solve the OPPS problem was promising but in its early stages. In addition, it was concluded that the reviewed studies about heuristics and metaheuristics dealt with the problem as a binary knapsack optimization problem. They mostly relied on random solution generation or using another algorithm, mainly LP. Furthermore, they applied penalty functions in order to satisfy constraints. Hence, tuning population generation and different GA parameters for the OPPS problem is an active research field. Methodology In this study, the proposed mathematical formulation of the problem can be defined by giving the liberty for the decision variable to take any integer value from the domain which represents all the possible exploitation periods for the ultimate pit design blocks. The new formulation cuts the number of decision variables drastically, in comparison with the old formulation. In addition, by nature, the new formulation forces any given block, within the ultimate pit design, to be extracted once. A downside to this formulation is that it does not give the liberty to excavate a specific block over different time periods. In other words, each block within the ultimate pit design is to be excavated once at a specific time period within the life of the mine. The proposed greedy genetic hybrid algorithm (GGHA) addresses the scheduling problem by integrating a greedy population mechanism with an integer-programming search mechanism to effectively handle high-dimensionality and strict precedence constraints. This has been achieved by adding a greedy nature to the initial population generation mechanism. In addition, the different genetic operators were applied using constraint programming and were designed to have a greedy nature. Results and discussion The evaluation of GGHA across eight instances showed a clear advantage in producing higher solution quality (NPV). This was clear in 75 percent of the test cases. By comparing the GGHA against both the previously published genetic algorithm and MiningMath commercial package, the study confirmed that the proposed hybrid provides a statistically significant improvement in economic performance, with improvements ranging from 1.5 to 3.44 percent (Table 1 and Fig. 1). Fig. 2 NPV enhancement produced by GGHA against GA. Furthermore, a direct relation was observed between the enhancement and the life of mine (Fig. 2). Accordingly, the average enhancement ratio that GGHA produced, within these eight cases, was estimated to be about 0.15 percent/year. This estimate was produced by basic linear regression with a goodness of fit of 0.77. Conclusion GGHA was found to be a promising and effective optimization heuristic for the long-term OPPS problem. This is mainly referenced to adding a greedy nature to the basic GA. It provides consistent significant improvements for solution quality (NPV) for most studied instances. Furthermore, this study highlights the need for guidance or hybridization — for example, by using a greedy heuristic — within metaheuristics in large-scale openpit mines in order to reduce the random solution generation effect. References A list of all references is available in the full paper.

A greedy genetic hybrid heuristic for solving the openpit production scheduling problem

Authored by: Mohamed Sholqamy and Mohamed Elwageeh

To view this article you must be a member of SME/UCA.

US Energy Department launches $16 million prize to grow the mining and critical minerals workforce

DOE selects S&T to build mining technology proving ground

Legacy in Motion: How CAB is Building the Future of Hanger Manufacturing

US Energy Department launches $16 million prize to grow the mining and critical minerals workforce

DOE selects S&T to build mining technology proving ground

Legacy in Motion: How CAB is Building the Future of Hanger Manufacturing

To view this article you must be a member of SME/UCA.

Improving mineworker safety using a mineworker administration shell

Enhancing quartz-amine flotation with oily bubbles

Related Articles

Improving mineworker safety using a mineworker administration shell

Application of infrared thermography and the acoustic emission technology for loose rock detection

Enhancing quartz-amine flotation with oily bubbles

Rheological characterization of tailing pastes from ore mining

US Energy Department launches $16 million prize to grow the mining and critical minerals workforce

DOE selects S&T to build mining technology proving ground

Legacy in Motion: How CAB is Building the Future of Hanger Manufacturing

US Energy Department launches $16 million prize to grow the mining and critical minerals workforce

DOE selects S&T to build mining technology proving ground

Legacy in Motion: How CAB is Building the Future of Hanger Manufacturing

Use Single Sign On