Decision Support
Linear models for stockpiling in open-pit mine production scheduling problems

https://doi.org/10.1016/j.ejor.2016.12.014Get rights and content

Highlights

  • We propose new linear models for modeling stockpiles in open pit mining.

  • We compare how their assumptions affect solution quality and tractability.

  • These models include blending requirements without unrealistic assumptions.

  • Experiments show that our proposed models are tractable and yield good approximations.

Abstract

The open pit mine production scheduling (OPMPS) problem seeks to determine when, if ever, to extract each notional, three-dimensional block of ore and/or waste in a deposit and what to do with each, e.g., send it to a particular processing plant or to the waste dump. This scheduling model maximizes net present value subject to spatial precedence constraints, and resource capacities. Certain mines use stockpiles for blending different grades of extracted material, storing excess until processing capacity is available, or keeping low-grade ore for possible future processing. Common models assume that material in these stockpiles, or “buckets,” is theoretically immediately mixed and becomes homogeneous.

We consider stockpiles as part of our open pit mine scheduling strategy, propose multiple models to solve the OPMPS problem, and compare the solution quality and tractability of these linear-integer and nonlinear-integer models. Numerical experiments show that our proposed models are tractable, and correspond to instances which can be solved in a few seconds up to a few minutes in contrast to previous nonlinear models that fail to solve.

Introduction

Open pit mine production scheduling (OPMPS) is a decision problem involving which blocks, within the final pit limits, should be mined in each year, and where the blocks should be sent, e.g., mill, waste dump or stockpile, to maximize the net present value (NPV) subject to the constraints that: (i) mining and processing consume limited resources and affect the production profile in each period; and (ii) spatial precedence must be obeyed among the blocks (Fig. 1).

In open pit mine scheduling, the question arises as to how mathematically to model the stockpile and determine a strategy, and how to assess the value associated with using a stockpile. While some researchers do not consider a stockpile as part of OPMPS, others suggest using a stockpile without providing the mathematical framework. In this research, we focus on proposing tractable models which provide practical solutions.

Initially, researchers proposed linear programs to solve OPMPS without considering a stockpile. Johnson (1969) describes the first such model to maximize net present value (NPV) of an open pit mine while determining whether each block should be sent to the mill or the waste dump, subject to precedence and operational resource constraints. Because his model contains only continuous-valued variables, his precedence constraints enforce that in order to extract a certain amount of block b′, at least that same amount of predecessor block b must be extracted. The author uses Dantzig–Wolfe decomposition to solve several instances. Given hardware and software limitations at the time, he illustrates with some small examples.

An important challenge in solving OPMPS is that model instances can contain many blocks and time periods, and each block-time period combination has an associated binary decision variable in order to capture the more realistic constraint that all of a predecessor block must be extracted before any of a successor block is extracted. One way to decrease the number of decision variables in these linear-integer programs is to aggregate some blocks with similar characteristics. Askari-Nasab, Frimpong, and Szymanski (2007) discuss different aggregation techniques that can be used to fit the geology of the deposit and the time fidelity of the model. They also develop an open-pit production method which depicts the stochastic dynamic expansion of an open pit using discrete incremental pushbacks in different directions.

Ramazan (2007) uses the concept of “fundamental trees” to aggregate blocks for an open pit production scheduling problem. Boland, Dumitrescu, Froyland, and Gleixner (2009) suggest that variables or constraints which are determined to be “similar” according to some criteria can be grouped together into new variables or constraints, called aggregates. The new OPMPS problem is then solved, causing some decisions to lose their fidelity in the aggregated model. By disaggregating, i.e., reverting to the original variables, a solution for the initial problem, which is usually not optimal and possibly infeasible, is obtained. Jélvez, Morales, Nancel-Penard, Peypouquet, and Reyes (2016) present a number of heuristics to tackle the open-pit block scheduling problem. Their approach is mainly based on block aggregation. The authors first solve the aggregated problem and then obtain a feasible solution for the original instance.

Bienstock and Zuckerberg (2010) provide a new algorithm for solving the linear programming relaxation of the precedence constrained production scheduling problem by reformulating it such that many constraints are modeled as a single one. They also consider multiple processing options. Their maximum weight closure problem can be solved as a minimum cut problem with a small number of side constraints, making it amenable to Lagrangian-based approaches. Chicoisne, Espinoza, Goycoolea, Moreno, and Rubio (2012) propose a new algorithm to solve linear programming relaxations of large instances of the same problem, and a set of heuristics to solve the corresponding integer program.

Martinez and Newman (2011) present a mixed-integer model to schedule long- and short-term underground production which minimizes deviations from preplanned production quantities while adhering to operational constraints. The authors develop an optimization-based decomposition heuristic that solves large instances quickly. O’Sullivan and Newman (2015) schedule extraction and backfill at an underground Lead–Zinc mine that uses three different underground methods; their heuristic enables them to solve real-world instances.

Shishvan and Sattarvand (2015) present a metaheuristic approximation based on Ant Colony Optimization for open-pit mine production planning which considers any type of objective function and nonlinear constraints. Montiel and Dimitrakopoulos (2015) propose a risk-based method which incorporates geological uncertainty to optimize mining operations comprised of multiple pits, stockpiles, blending requirements, processing paths, operating alternatives and transportation systems. Their method perturbs an initial solution iteratively to improve the objective function. Lamghari and Dimitrakopoulos (2016) and, similarly, de Freitas Silva, Dimitrakopoulos, and Lamghari (2015) propose different heuristics such as tabu search and variable neighborhood descent to solve models that consider metal uncertainty and multiple destinations for the extracted material; low-grade material sent to the stockpile is mixed homogeneously, and the corresponding average grade is successively approximated.

Although linear and mixed integer programming models are recognized as having significant potential for optimizing production scheduling in both open pit and underground mines, most of these approaches focus on the extraction sequence and do not consider the material flow post-extraction. In particular, the use of stockpiling to manage processing plant capacity, and the interplay of material flows from the mine to a stockpile, the mine to a processing plant, and a stockpile to a plant, have not been treated as an integrated part of mine extraction sequence optimization. While industrial uses of mine planning software with stockpiling exist, these have limited benefit due to the nature of their modeling and solution techniques.

While some mining software such as Mintec (2013) and MineMax (2016) have tried to consider the stockpile as part of open pit mine scheduling, such software does not guarantee global optimal solutions. Whittle, one of the leading pieces of software in mine planning, has a stockpiling module and considers mixing material with different grades in the stockpile:

As material is moved to the stockpile, the tonnage and metal information is accumulated, so that at any point in time, the average grade is known. Stock withdrawals are considered to be at the average grade. Stockpiles are only used if they return a positive cash flow (Whittle, 2010).

Whittle does not use optimization techniques to model the stockpile, so there is no guarantee of obtaining an optimal solution with respect to the number of stockpiles and/or the grade contained in each stockpile. Academic researchers have been developing models to address these shortcomings.

Smith (1999) uses mixed integer programming to solve a short-term production scheduling problem with blending, considering stockpiles both at the mine and at the mill. He notes that correctly capturing the contents of the stockpile requires nonlinear constructs, and enhances tractability of the original model by introducing piecewise linear constructs to approximate separable terms (after reformulation) representing the product of the average grade in the stockpile and the quantity retrieved from the stockpile in a given time period. After aggregation and variable elimination, he applies the model results to a phosphorus mine in Idaho. This research represents an early attempt to correctly model the grade of a stockpile, but requires approximations whose accuracies are not quantified, to ensure tractability.

Caccetta and Hill (2003) propose an exact approach to solve a monolithic OPMPS problem by defining variables representing whether a block is mined by time period t. The model includes constraints on: precedence, operational resources, and processing grade requirements. They also discuss the possibility of considering a stockpile in their model but without an associated mathematical formulation. The authors propose a branch-and-cut strategy combined with a heuristic. Asad (2005) describes a simple optimization model designed to assess the tradeoffs between cutoff grades and stockpile levels for a two-mineral deposit. His static model omits production scheduling decisions. Ramazan and Dimitrakopoulos (2013) explain that the OPMPS problem typically contains uncertainty in the geological and economic input data. They use a stochastic framework to incorporate stockpiling since the amount of material to be stockpiled is determined by the block grades in the orebody model. In these models, the authors ignore mixing of material in the stockpile. Koushavand, Askari-Nasab, and Deutsch (2014) quantify oregrade uncertainty by including a term for its cost in the objective function; their model captures typical constraints on extraction and processing limits, and on block precedence, as well as on blending, and on over- and under-production. Stockpile levels are bounded above and below, and are tracked in aggregate by time period; the authors demonstrate their model using a case study in which they assume that the stockpile has its grade set a priori and that it is used to mitigate uncertainty, i.e., overproduction can be carried over until the next time period. Smith and Wicks (2014) use a mixed-integer program (MIP) that maximizes recovered copper and accounts for constraints on shovel, extraction, stockpiling, and processing capacities, as well as blending. Here, the stockpiling constraints result in an optimistic bound on the model, in that each block is retrieved from the stockpile having preserved its characteristics upon entry to the stockpile. The authors’ life-of-mine model, solved using a sliding time window heuristic to incorporate a 60-month horizon, yields information regarding stripping ratios and qualities and quantities of ore mined.

Nevertheless, some researchers do consider material mixing in the stockpile. When placing an ore block on a stockpile, the block characteristics (e.g., grade and tonnage) are known. However, as blocks are mixed in the stockpile, the characteristics of the material removed from the stockpile must be treated as variables. Since the amount of ore removed from the stockpile is not known a priori, the model has some non-convex, nonlinear constraints. Efforts to solve this problem result in local optimal solutions or consist of linearizing the model, which might introduce unrealistic assumptions.

Tabesh, Askari-Nasab, and Peroni (2015) acknowledge that stockpiling should theoretically be modeled nonlinearly to optimize a comprehensive open-pit mine plan, and linearizes the formulation by using a “sufficient number” of stockpiles, each with a tight range of grades. No numerical results are given, however. (We will return to this model later.)

Although there have been efforts to consider stockpiling as part of OPMPS, some of these models result in locally optimal solutions and/or are intractable for big data sets. Attempting to decrease the size of the problem instances results in aggregation, which causes a loss of information regarding each type of material (Tabesh & Askari-Nasab, 2011).

Bley, Boland, Froyland, and Zuckerberg (2012a) propose two different models considering one stockpile with the following assumptions:

  • 1.

    Material in the stockpile mixes, resulting in a grade equal to the average grade of all the material inside the stockpile.

  • 2.

    Material is extracted from the stockpile at the beginning of each period, so the grade of the resulting material is the average of that of the material at the end of the previous period.

In Section 3.2, we present (Pb), which tracks the ore and mineral in the stockpile in each period, considering material mixing by adding a non-convex quadratic constraint for each period. In Section 3.3, we discuss (Pw), in which the fraction of each block in the stockpile in each period is tracked, and additional non-convex constraints force the fraction of each block in the stockpile that is sent to be processed in a given time period to be the same. Bley et al. (2012a) prove that (Pb) and (Pw) are equivalent, but the latter model provides a stronger formulation of the problem, resulting in a better upper bound.

Bley et al. (2012a) focus on exact algorithmic approaches. They study a relaxation of (Pw) by removing the non-linear constraints, and instead enforcing these restrictions using a scheme, integrated within a branch-and-bound framework, that (i) branches on the variable representing the value of the proportion of metal (versus ore) removed from the stockpile in each time period, and (ii) forces the violation of all non-linear constraints to be arbitrarily close to 0. Additionally, the authors propose a primal heuristic to obtain feasible solutions of the exact problem from a relaxed solution, and cuts and inequalities to strengthen the relaxation. Finally, they apply these techniques on two small instances, showing the impact of each solution procedure they propose.

Our research, by contrast, focuses on proposing new models, rather than on developing new algorithms, and compares how their assumptions affect solution quality and tractability. These linear-integer models include blending requirements without unrealistic assumptions, and yield good approximations using state-of-the-art methodologies on large-scale instances.

We organize the remainder of this paper as follows. In Section 2, we explain an existing model that does not incorporate stockpiling; in Section 3, we present existing nonlinear models that incorporate stockpiling. In Section 4, we propose linear models with stockpiling. In Section 5, we graphically represent the difference between our proposed models, and in Section 6, we compare the results. We conclude with Section 7.

Section snippets

Lower bound model

In this section, we present the formulation of a model that provides a lower bound on the objective function value of the OPMPS problem in which the option of stockpiling does not exist; such a model can be found in Caccetta and Hill (2003), Boland et al. (2009), and as a special case of Bienstock and Zuckerberg (2010). The first section introduces notation, and the following sections provide the math. We use the term “material” to include ore, i.e., rock that contains sufficient minerals

Nonlinear models that consider stockpiling

In this section, we provide nonlinear formulations that consider a stockpile. Because we propose models with just one stockpile, we define “buckets” that represent different parts of a stockpile, where each bucket incorporates material within a specific grade range. The grade of material when removing it from the stockpile is the minimum grade of the associated bucket. First, we define additional notation:

Approximate linear models

In Sections 4.1–4.3, we formalize results from models in the literature, i.e., Akaike and Dagdelen (1999), Hoerger, Seymour, and Hoffman (1999) and Tabesh et al. (2015), respectively. In the latter case, the authors present a model that is similar to K-bucket (see Section 4.3), in which the authors categorize the possible grades in the buckets; there are, however, three differences: (i) they define a lower and an upper bound for the average grade sent to each bucket in each period, and (ii)

Graphical representations

We can assume that in a mine, some material is sent to the stockpile in the first time period and is processed at the mill in the second period. Since profit per ton is a linear function of the grade, we assume that the “grade” g of the material is defined by units of profit per ton. We can represent the total tonnage sent to the stockpile with grade greater than or equal to g using a function G(g). An illustrative example of this function appears in Fig. 2. Note that if all of this material is

Computational experiments

In this section, we examine the solution quality associated with different linear-integer and nonlinear-integer models. In Section 6.1, we compare the proposed models to the nonlinear model. This requires a reduction in problem size, accomplished by fixing the block extraction time in all models. In Section 6.2, we compare two linear-integer models using a customized solver called OMP (Rivera, Brickey, Espinoza, Goycoolea, & Moreno, 2016) without fixing the block extraction time. Unless

Conclusion

Considering stockpiling as part of open pit mine planning presents numerous challenges: (i) the most precise model in the literature at the time of this writing is nonlinear and integer, yielding a non-convexity and therefore no guarantee of a global optimum; (ii) nonlinear-integer models are often intractable, especially for realistically sized instances; (iii) even if we obtain a solution for these models, the way in which some assumptions are handled, in particular, that of homogeneous

Acknowledgments

The authors wish to thank the associate editor and referees for helpful comments on prior drafts of this paper. In addition, Eduardo Moreno and Felipe Ferreira gratefully acknowledge support from Conicyt grants FONDECYT #1130681 and PIA Anillo ACT 1407.

References (33)

  • A. Akaike et al.

    A strategic production scheduling method for an open pit mine

    Proceedings of the twenty-eighth international symposium on application of computers and operations research in the mineral industry

    (1999)
  • AMPL

    AMPL version 12.6.0.1

    (2014)
  • M. Asad

    Cutoff grade optimization algorithm with stockpiling option for open pit mining operations of two economic minerals

    International Journal of Surface Mining, Reclamation and Environment

    (2005)
  • H. Askari-Nasab et al.

    Modeling open pit dynamics using discrete simulation

    International Journal of Mining, Reclamation and Environment

    (2007)
  • D. Bienstock et al.

    Solving LP relaxations of large-scale precedence constrained problems

  • Bley, A., Boland, N., Froyland, G., & Zuckerberg, M. (2012a). Solving mixed integer nonlinear programming problems for...
  • Cited by (0)

    View full text