Production Scheduling of Open Pit Mine Using Sequential Branch-and-Cut and Longest Path Algorithm: An Application from an African Copper Mine

Production Scheduling of Open Pit Mine Using Sequential Branch-and-Cut and Longest Path Algorithm: An Application from an African Copper Mine

Devendra JoshiSusanta Kumar Satpathy 

University Teaching Department, Chhattisgarh Swami Vivekanand Technical University, Bhilai, Chhattisgarh 491107, India

Department of Computer Science and Engineering, Vignan’s Foundation for Science, Technology and Research, Vadlamudi, A.P. 522213, India

Corresponding Author Email: 
joshi.dev19@gmail.com
Page: 
629-636
|
DOI: 
https://doi.org/10.18280/jesa.530505
Received: 
8 June 2020
|
Revised: 
3 September 2020
|
Accepted: 
12 September 2020
|
Available online: 
15 November 2020
| Citation

© 2020 IIETA. This article is published by IIETA and is licensed under the CC BY 4.0 license (http://creativecommons.org/licenses/by/4.0/).

OPEN ACCESS

Abstract: 

Open pit mine production scheduling assigns mining blocks in different production periods for maximising profits after satisfying geotechnical and operational constraints. In this paper, two Open pit mine production scheduling models were applied in an African copper deposit. The first model is a traditional model with more tight resource constraints; the second model is a more robust model where resource constraints are relaxed by penalizing the objective function. Both the models were solved using two step algorithms: (a) year wise production scheduling using a sequential branch-and-cut algorithm; and (b) an iterative longest path algorithm to improve the solution generated from branch-and-cut. Results demonstrated that due to the tight constraints in Model 1, the optimizer was unable to generate a feasible solution after the first period, therefore the lower limit metal production constraint was eliminated to generate a feasible solution; however, Model 2 was able to generate a feasible solution for all periods. Results show that both the models generated nearly the same amount of ore, waste, metal content, and mine life. Model 2 generates relatively more net present value as compared to Model 1, whereas, the computational time required for solving the scheduling problem is relatively less for Model 1 than for Model 2.

Keywords: 

open pit mine production scheduling, mixed integer programming, net present value, ordinary kriging

1. Introduction

The optimum pit limit of open pit mine is considered to be a fundamental problem in mine planning as it provides information which is essential in the evaluation of the economic potential of a mineral deposit. Open pit mine production scheduling (OPMPS) is a complex problem in mine planning and design [1]. OPMPS is an optimization problem used to extract the mining block from the pit by satisfying all its constraints to maximize the total discounted profit [2, 3]. OPMPS is generally defined in the form of either integer or mixed integer programming problem which solve by using a commercial solver [4]. In OPMPS the orebody is represented as three dimensional arrays of blocks. The mineral grade of each block within the orebody is estimated using limited number of explorations drilling data and applying geostatistical algorithms [5]. The economic value of block (EVB) is calculated using the calculated grades, market price of the mineral, mining and processing cost, and rate of recovery [6-11]. The EVB of the orebody is considered as input for OPMPS model. The solution of the OPMPS is assigned the blocks in different production periods by maximizing the objective value which aims to maximize the sum of discounted cash flow.

A number of theories and algorithms are proposed in literature by different researchers for OPMPS problem. The exact method is Lerchs-Grossman algorithm based on the graph theory and graph cut method by Picard for solving the ultimate pit [12, 13]. The main limitation of these algorithms is that it is difficult to determine mining and processing capacities for each period. Dagdelen and Johnson proposed a Lagrangian method to handle capacity constraints problem by incorporating the Lagrangian multiplier; however, the selection of Lagrangian multiplier is a significant problem [14]. In the other direction, Caccetta and Giannini proposed a dynamic programming algorithm to bound the optimal solution generated from graph-theoretic technique [15].

Different researchers proposed integer programming (IP) and mixed integer linear programming (MIP) algorithms for solving OPMPS [16, 17]. These algorithms generate optimum solution for production scheduling [3, 18-22]; however, the main drawback of these algorithms is that the computational time increases exponentially as decision variables and constraints are increased [23]. Block aggregations methods, efficient clustering technique and decomposition-based heuristic approach reduces the computational complexity of IP and MIP by sacrificing some amount of optimality [24-27].

The parametric graph closure approach can be iteratively solved using network flow algorithm for solving mixed integer programming in mine scheduling [28, 29]. Although, these algorithms are computationally fast, selection of set of parameters are always very difficult. Simulated Annealing application to mine production scheduling problem was developed to gradually improve an initial non-optimal solution by multiple perturbation [30]. Ant colonies optimization was proposed to solve the mine production scheduling problem [31, 32].

Ibrahimov et al. proposed a more efficient algorithm based on computational intelligence method. The approach combining genetic algorithms and Lagrangian relaxation to optimally determine the constrained long-term production scheduling problem of open pit mines [33]. The proposed Lagrangian relaxation and genetic algorithms combines genetic algorithms into Lagrangian relaxation method to update the Lagrangian multipliers. Numerical results demonstrate to improve its performance. Subsequently, near-optimal solution is achieved [34].

In this paper, we have proposed a sequential branch-and-cut algorithm for solving large scale open pit mine production scheduling problem. Two different models are considered: one integer programming model and another mixed integer programming model to solve large-scale real life mine scheduling problem. Both the models are solved in two steps process. In first step the OPMPS is iteratively solved year wise using sequential branch-and-cut algorithm. In the second step, the solution from sequential branch-and-cut improved by using longest path algorithm. The proposed method is applied as a case study in African copper mine.

2. OPMPS Methods

OPMPS is traditionally based on a block model of the ore body built by using interpolation techniques, either traditional like inverse distance, nearest neighbourhood etc. or geostatistical method like simple kriging, ordinary kriging etc., from the drillhole sample data [35]. The orebody is represented by a geological block model, having a three-dimensional array of blocks. Each block includes the volume, grade, and tonnage information. Orebody models and their geological characteristics are known to be a major source of scheduling risk [36]. Each block has a block economic value representing the net profit associated with it. The OPMPS consists of identifying which blocks should be mined during each period of the life of the mine so as to maximize the profit of the mining operation. Various physical and operational constraints have to be satisfied when scheduling blocks. OPMPS consists of several thousands of mining blocks which have to be scheduled year wise to maximize the total profit of mine over the life of mine.

According to OPMPS, geotechnical, reserve, mining, processing, and metal production constraints have to be respected while maximizing the net present value over the life of the mine. The geotechnical constraints help to maintain a stable slope in the open pit during the production operation. The reserve constraints help to ensure each physical block can only be extracted one production period. Mining constraints is set to utilize the capacity of mining equipment available for excavation. According to the equipment capacity and its availability, the model fixes the upper and lower bound of mining constraints so that the model will not extract more than the total equipment capacity and not less than certain amount to make sure that equipment is not unutilized. The processing constraint deals with the capacity of processing plant. The maximum production capacity of the plant and the minimum production requirement are necessary to ensure smooth feed of ore to mill. Metal production constraints deals with certain amount of metal to supply the customer according to agreements with customer, now for case study two models are develops.

2.1 OPMPS integer and mixed programming model

Suppose xi is a mining block of an open pit mine, where xi=X and x is set of all blocks in the deposit. Mine production scheduling can be formulated as mixed integer programs with time-indexed binary variables $x_{i, t}, i \in N, t=\{1, \ldots, T\}$, which are defined by $x_{i, t}=1$ if mining block is extracted at time t, and $x_{i, t}=0$ otherwise. This leads to the following integer programming formulation.

The mathematical representation of model 1 can be written as:

$Z=\operatorname{Max} \sum_{t=1}^{T} \sum_{i=1}^{N} c_{i t} x_{i, t}$     (1)

In this model (Model 2), a robust OPMPS model is proposed where some of the decision variables are allowed to take real value. Therefore, the model is a mixed integer programming formulation. The mathematical representation of objective function can be written as:

$Z=\operatorname{Max} \sum_{t=1}^{T} \sum_{i=1}^{N} c_{i t} x_{i, t}-\sum_{t=1}^{T} v_{t}^{o-} d_{t}^{o-}+v_{t}^{o+} d_{t}^{o+}+v_{t}^{m-} d_{t}^{m-}+v_{t}^{m+} d_{t}^{m+}$     (2)

Subject to:

Reserve constraints: A block can be mined only once during its time period which is defined as:

$\sum_{t=1}^{T} x_{i t} \leq 1 \quad i=1, \ldots, N$     (3)

Slope constraints: A block cannot be mined before its predecessors. To access a given block, a set of overlying blocks needs to be exacted. Slope constraints are written as:

$x_{i t}-\sum_{\tau=1}^{t} x_{p \tau} \leq 0 \quad p \in P_{i}, \quad t=1, \ldots, T$     (4)

Mining constraints: The total weights of blocks mined during each period should be at least equal to a minimum mining limit to ensure proper utilization of mining equipment. On the other hand, it should not exceed the mining equipment capacity available during that period. In mining constraints, both upper and lower bound have to be satisfied. The mining constraints are written as:

$\begin{array}{ll}\underline{M C} \leq \sum_{i=1}^{N} m c_{i} * x_{i t} & t=1, \ldots, T \\ \overline{M C} \geq \sum_{i=1}^{N} m c_{i} * x_{i t} & t=1, \ldots, T\end{array}$     (5)

Processing constraints: It mainly depends on the processing capacity of plants, the total amount of ore blocks mined during each period should be at least equal to minimum amount required for processing plant, but it should not exceed the processing plant capacity, then storing placed is required to store the excess ore. In model 2, the violations should not be more than for specific time period. The modified processing constraints for both upper and lower bounds can be presented in Eq. (7). The processing constraints of both models are written as Eqns. (6) and (7):

$\begin{array}{ll}\underline{P C} \leq \sum_{i=1}^{N} p c_{i} * m c_{i} * x_{i t} & t=1, \ldots, T \\ \overline{P C} \geq \sum_{i=1}^{N} p c_{i} * m c_{i} * x_{i t} & t=1, \ldots, T\end{array}$    (6)

$\underline{P C} \leq \sum_{i=1}^{N} p c_{i} * m c_{i} * x_{i t}+d_{t}^{o-} \quad t=1, \ldots, T$

$\overline{P C} \geq \sum_{i=1}^{N} p c_{i} * m c_{i} * x_{i t}-d_{t}^{o+} \quad t=1, \ldots, T$     (7)

Metal production constraints: The amount of metal recovered from the ore blocks processed should not exceed the amount that can be sold during this period and should not be less than a minimum amount, both upper and lower bound of metal production constraints has to be satisfied. Eq. (9) shows the maximum allowable violations are for lower and upper limit bounds. The metal production constraints for both models are written as:

$\underline{M P} \leq \sum_{i=1}^{N} m p_{i} * p c_{i} * x_{i t} \quad t=1, \ldots, T$

$\overline{M P} \geq \sum_{i=1}^{N} m p_{i} * p c_{i} * x_{i t} \quad t=1, \ldots, T$      (8)

$\underline{M P} \leq \sum_{i=1}^{N} m p_{i} * p c_{i} * x_{i t}+d_{t}^{m-} \quad t=1, \ldots, T$

$\overline{M P} \geq \sum_{i=1}^{N} m p_{i} * p c_{i} * x_{i t}-d_{t}^{m+} \quad t=1, \ldots, T$     (9)

Decision variables are

$x_{i t}=0$ or $1 i=1, \ldots, N, t=1, \ldots, T$

$d_{t}^{o-} d_{t}^{o+} d_{t}^{m-} d_{t}^{m+} \geq 0 \quad t=1, \ldots, T$

where,

$x_{i t}=\left\{\begin{array}{l}1 \text { if block } i \text { is mined during period } t \\ 0 \text { otherwise }\end{array}\right.$

$c_{i t}=$ block economic value of block $i$ if mined at period $t$ $=\frac{c_{i}}{(1+d)^{t}}$

ci=Economic value of block i.

d=discounted rate.

N=The number of blocks considered for scheduling.

i=Block index, i=1, ..., N.

T=The number of periods over which blocks are being scheduled (horizon).

t=period index, t=1, ..., T.

Pi=The set of predecessors of block i; i.e., blocks that should be removed before i can be mined.

si=The set of successors of block i.

$\overline{M C} $=The maximum weight of material at period t.

$\underline{M C}$=The minimum weight of material at period t.

$\underline{P C}$=minimum weight of ore required to feed the processing plant in period t (minimum processing capacity of plant).

$\overline{P C} $=maximum weight of ore that can be processed in plant at period t (maximum processing capacity of plant).

$\underline{M P}$=minimum amount of metal that should be produced in period t.

$\overline{M P} $=maximum amount of metal that should be sold in period t (metal demand).

mci=The weight of block i.

mpi=The amount of metal in block i.

$v_{t}^{o-}=\frac{c^{o-}}{\left(1+d_{2}\right)^{t}}$=Unit shortage of ore that can associated with failure meet $\underline{P C}$ during period t.

($c^{O-}$ is the undiscounted unit shortage cost, and d2 represent the risk discount rate).

$v_{t}^{o+}=\frac{c^{o+}}{\left(1+d_{2}\right)^{t}}=$=Unit surplus cost incurred if the total weight of the ore blocks mined during period t exceeds $\overline{P C} $.

$v_{t}^{m+}=\frac{v^{m+}}{\left(1+d_{2}\right)^{t}}$=Unit surplus cost incurred if the metal production during period t exceeds $\overline{M P} $.

$d_{t}^{o-}$=Shortage of amount of ore at discounted cost in time period t.

$d_{t}^{o+}$=Surplus of amount of ore at discounted cost in time period t.

$d_{t}^{m-}$=Shortage of metal for selling at discounted time period t.

$d_{t}^{m+}$=Surplus of metal for selling at discounted time period t.

The above formulation of model 1 can be solved using any integer programming solution algorithm. The solution of this formulation provides the sequence of extraction of mining blocks after satisfying all the constraints presented in Eqns. (3), (4), (5), (6) and (8). However, sometime this formulation generates infeasible solution due to the tight geotechnical, reserve, mining, processing, and metal constraints. Out of these constraints, geotechnical and reserve constraints are strict constraints which cannot violated at any circumstances. On the other hand, mining, processing, and metal production constraints are soft constraints which may be violated in certain circumstances. For an example, if mine management is planning to extract more materials from a mine for specific period, they can hire mining equipments from market on payment basis. On the other hand, if mine management unable to produce less than the minimum amount of materials, the equipments will be idle and keeping idle of such high cost equipment produces some losses due to high depreciation amount. In other example, if management is producing more amount of ore than the maximum required amount in the process plant, those excess ore needs to be stored and proper storing impose some extra cost to the management. Therefore, there is a need of more robust formulation which will generates feasible solution for the OPMPS formulation.

In model 2, the $x_{i t}$ is the first stage decision variables which can only take the binary value; however, $d_{t}^{o-} d_{t}^{o+} d_{t}^{m-} d_{t}^{m+}$ are second stage decision variables which can take any real positive values. In this paper, these variables are allowed to take any real positive value up to infinity for which the objective function is penalized. However, one can restrict the amount of maximum deviation if required. Practically, the optimizer selects positive values for these four decision variables during the optimization process, as long as they help to increase the objective function value even after penalization. The optimizer selects these decision variables values as zero, if allowing the deviation is actually reduced the objective function values.

2.2 Solution approach

The above OPMPS models cannot be solved optimally within the reasonable amount of time when the numbers of decision variables, and number of constraints are significantly high. The computational time of the OPMPS can be reduced by solving sequentially (period by period). First, the formulation of both the models are solved for period one considering T=1 using branch-and-cut algorithm [37]. The solution of formulation, when solved for first period, provides decision whether a block can be extracted in period one or not. The set of blocks, which take the decision variable value of 1 for first period solution, will be assigned to extract in first period. Then those blocks will be eliminated from the set of blocks N and the remaining blocks will be used for solving the formulation of next period considering T=1. This process will be repeated until no single block will be left in the deposit which can be extracted profitably. Although, the approximate algorithm cannot generate the optimum solution; however, it can produce a solution very fast. The more detail about the sequential solution approach can be found elsewhere [17, 38].

Although, the sequential solution can reduce the computational complexity of both the models to generate feasible solution; however, the solution generated using this process is far from the optimality. To improve the sub-optimum solution, a network flow based iterative longest path problem algorithm proposed by Lamghari and Dimitrakopoulos is applied here [39]. By this iterative process, the blocks with negative economic value are differed for latter period and the block with positive economic value are advanced for earlier period which ultimate improves the net present value. To know more about the longest path problem for improving initial feasible solutions, readers are referred [38-40].

3. Case Study Description

The studied deposit is located in the Central African Copper belt. Geologically, the deposit is a stratiform copper-cobalt deposit. Two principal stratiform mineralized horizons are developed and identified as the Upper and Lower Orebodies. The footwall of the deposit is marked by a thrust zone or breccia. The ore body’s downdip is cut off by an approximately E-W trending and relatively steep fault, which limits its depth. The ore body is divided into three types of ores: oxide, mixed and sulphide (Figure 1). The oxide and mixed parts of the ore were evaluated together but in two zones: oxide main and oxide supergene. The sulphide part was also evaluated in two zones: east sulphide and west sulphide, which are separated by a fault. The primary copper minerals (chalcopyrite and possibly bornite and digenite) and primary cobalt minerals (linnaeite and carrollite) principally occur as thin, discontinuous bands in the upper and lower ore bodies. A total of 462 boreholes were considered for creating the borehole database. This database was used for ore section interpretation, ore body modeling and resource estimation. The boreholes are drilled on average on a 50-m grid. All the assay data was composited at 10 m intervals within the ore body for all the statistical and geostatistical work.

4. Results and Discussion

Detailed statistical analysis of composited samples was carried out. The Table 1 shows the descriptive statistics of the composited data. It is seen from the Table that the grade of copper is skewed towards the left side but it has comparatively less variance.

The ordinary kriging was used for the grade estimation [41]. Spatial correlation of the data was measured using the variogram analysis [42]. The directional experimental variograms of the deposit were calculated in different directions, i.e. 0°, 45°, 90°, and 135°, with a spread of 22.5° for all four ore bodies. The lag spacing for calculating the variograms along strike for sulphides (both east and west) and oxides (both mixed and supergene) were 24 m and 32 m, respectively. The variograms along the downhole direction (-90° dip) were also calculated for all four ore bodies. A 2m lag spacing was used for all ore bodies with the exception of oxide supergene, which had a 1.6 m lag spacing. The directional variograms demonstrated the presence of anisotropy. All variograms were fitted with spherical variogram models. All variograms were fitted by single structure with nugget model for copper except for that of sulphide east along downhole (dip -90°), which was fitted with a two structure and nugget model. The block model of the deposit was estimated using the ordinary block kriging estimation technique. The estimated block size is selected as 20 m * 20 m * 10 m due to the selective mining unit (SMU) size [35]. Figure 2 shows the grade map of copper of one of the fourteen bench. The estimated block model was then used as an input for mine production scheduling.

For the OPMPS models, the economic value of block i i.e. ci is used as input. The value of block i is calculated by using the following Equation.

Figure 1. Ore body model showing oxide and sulphide ore bodies

Table 1. Descriptive statistics of composited copper data

Statistics

Sample No

Mean (%)

Variance (%2)

Coefficient of variation

Skewness

Kurtosis

Copper

1212

3.03

14.6

1.25

2.52

8.08

Figure 2. Copper grade map of one of the copper deposits using ordinary block kriging

$c_{i}=$net revenue$_{i}-$mining cost$-$processing cost

Case 1 If net revenue > processing cost

Or case 2 -mining cost, otherwise

where,

net revenue $_{i}$ $=$ tonnage $^{*}$ grade $_{i}$ * recovery* (price-selling cost)

The grade i for all blocks i are obtained from the block model which was obtained from ordinary kriging estimates. The calculated economic value of all the blocks were used in both the OPMPS models. The implementation of the OPMPS models were done in MATLAB environment and the models were solved using CPLEX solver [43]. The geotechnical and economical parameters, and the different constraints limits that are used in this paper are presented in Table 2.

Table 2. Details of different parameters values and constraints limits

Description

Values

Total number of blocks

16532

Slope angle (degree)

45°

Block dimensions (m × m × m)

20 × 20 × 10

Specific gravity of rock (ton/m3)

2.86

Recovery (%)

0.9

Cutoff grade (%)

0.2292

Discount (%)

0.10

Selling price of ore (US $/pound)

1.9

Selling cost of ore (US $/pound)

0.3

Processing cost of ore (US $/ton)

6

Mining cost of rock (US $/ton)

0.6

Blockmass or tonnage (ton)

11440

Mining constraints upper bound (Million ton)

25

Mining constraints lower bound (Million ton)

10

Processing constraints upper bound (Million ton)

8

Processing constraints lower bound (Million ton)

7

Metal production constraints upper bound (ton)

50000

Metal production constraints lower bound (ton)

45000

The Model 1 was solved first by sequentially solving branch-and-cut algorithm and then applied maximum flow longest path algorithm. However, after solving the production scheduling for the first period using branch-and-cut algorithm, it was observed that no further feasible solution can be generated from the study mine. Therefore, one of three resource constraints need to be relaxed for generating feasible solution. However, case study mine management was not willing to relaxed mining as well as processing constraints because they do not want to hire extra mining equipment, not want to allow mining equipment to be ideal, do not enough space and arrangement for storing extra ore, and finally they do not want to keep their plan idle. Therefore, the metal production constraint is relaxed. The lower limit constraint of metal production from Eq. (8) is eliminated from the formulation and the Model 1 was solved sequentially to generate the feasible solution. It was observed from the solution that the study mine can last for 10 years. This feasible solution was then improved using longest path problem. Figure 3 and 7 present a section of the production scheduling generated using Model 1 and 2 from the case study mine. It was observed that slope constraints and reserve constraints are satisfied.

Figure 3. East-west section of the production schedule of the study mine using Model 1

Figure 4 presents the comparison of raw materials production with mining capacity constraints upper and lower limit bounds. It is observed from this Figure. that at the initial period the material production was at the minimum level then started increasing and then finally starts decreasing. This behavior is due to the sequential application of branch-and-cut algorithm which tries to maximize the profit at very initial periods. Therefore, high grades ore are extracted at initial period and waste materials are deferred for the later period. Since, more ore are extracted in the initial periods, and ore and metal productions are also set of constraints in this formulation, the optimizer is not allowing to produce more materials at the initial time periods. However, in all the cases, the material productions are within the bound which demonstrated that the mining capacity constraints are satisfied.

Figure 4. Comparison of raw material production from the study mine using model 1 and 2

Figure 5. Comparison of ore production from the study mine using model 1 and 2

Figure 5 presents the ore production with upper and lower limit constraints for study mine. It was observed that the first period the ore production was relatively low and then maintained a constant production of 8 MT and drop the production at the last period. The reason for lower ore production is due to the upper limit of metal target production. With this minimum amount ore, the process plant was able to generate higher limit metal production value which is due to the extraction of higher-grade ores in the initial period. Period 2 onwards optimizer produces the maximum amount; however, at the final period the ore production drops due to the non-availability of the enough ore in the deposit. It is also necessary to mention that all the cases the ore productions were within the target limits. This demonstrated that the ore production constraints are satisfied by the model.

The actual metal production with upper and lower limit for both Models are presented in Figure 6. It was observed that only in first period the actual production was within the limit, rest of the other periods the actual production was lower than the lower limit constraints. It was noted that in Model 1, the actual formulation generates the feasible solution for the period 1 after that the solution was infeasible, and for generating the feasible solutions, the lower limit constraint was eliminated from the formulation and model was solved. Since, the lower limit of metal production constraint was eliminated after first period, the solution generated from the model doesn’t produce metal quantity within the target production limit. It was also observed from Figure 6 that actually metal production showing a decreasing trend which demonstrated the fact that the proposed OPMPS model tries to maximize the metal production in the earlier periods to maximize the return on investment early. The net present value for the study mine using Model 1 is approximately 405 M US \$. The metal production from Model 2. It was observed that none of the year the metal production is within the limits. This result is quite expected as both the upper and lower bound violation terms were in the formulation. It was also observed that in the first year the optimizer violates the upper limit constraints to generate more metal which ultimately generate more revenue. However, second period onwards, the optimizer violates the lower limit constraints. It is also interesting to observe that violations are more at the latter period than the initial period which reflects the fact that the optimizer delayed the large amount of violation for the later periods. The net present value for the study mine using Model 2 is around 408 M US \$.

Figure 6. Comparison of metal production from the study mine using model 1 and 2

Figure 7. East-west section of the production schedule of the study mine using Model 2

When compared between these two models, it was observed that over the life of the mine, both the models generate same amount of ore, waste, and metal content with same mine life. However, due to the difference in extraction sequence, Model 2 generates relatively more NPV than Model 1. The more NPV of the Model 2 attributed due to the production of more amount of ore and metal in the first year and thus more discounted cash flow. The computational time of the Model 1 is relatively less as compared to Model 2. Model 1 takes 823 seconds, whereas, Model 2 takes 1049 seconds to solve the whole problem. This is quite obvious because the number of constraints and decision variables are more in the Model 2 as compared to Model 1. Moreover, Model 2 is more robust for production scheduling; Model 1 does not guarantee the feasible solution for every situation (Figure 7).

5. Conclusion

The strategic and tactical decision making in mining is largely depend on successful OPMPS models. This paper presented two different OPMPS models. The first model is more traditional model with tight constraints; whereas, second model is more robust model allowing violation in some constraints and penalizing the objective function for such violation. Due to the nature of the formulation of the Model 2, it always ensures feasible solution; however, feasibility is not guaranteed in case of Model 1.

For solving the large scale OPMPS models, a two steps algorithm was followed. In first step, year-by-year production scheduling was performed by applying sequential branch-and-cut algorithm. And in second step, the iterative longest path algorithm was applied to improve the solution generated in first step. The results demonstrated that the proposed solution approach generates feasible solution with significantly less computational cost.

Both the OPMPS models were applied in copper mine from Africa for life of the mine production scheduling. Prior to solving the OPMPS models, a geostatistical algorithm called ordinary kriging was applied to estimate the quality and quantity of resource of the copper deposit. The economic value of each block within the resource model was calculated by considering fixed metal prices, mining and processing costs. Model 1 was unable to generate the feasible solution after period 1 for this deposit and the lower limit constraint of the metal production was eliminated from the constraint set; however, Model 2 generates the feasible solution for the study mine. The life of the mine using both the models is 10 years. The total production of ore, waste, metal is more or less same in both the models. The net present value generated from the Model 2 is slightly more than Model 1; whereas, the computational time for the Model 1 is relatively low. The final results demonstrated that the slope, reserve, mining, processing, and metal production constraints are satisfied by both the model (relaxed Model 1). The main limitation of the proposed method is that the grade value, metal price, and cost of mining and processing are considered fixed and known with full certainty. However, the mining activity is largely uncertain due to the grade uncertainty and volatility of the metal price and mining cost. Incorporation of these uncertainties can significantly improve the robustness of the OPMPS models.

  References

[1] Bley, A., Boland, N., Fricke, C., Froyland, G. (2010). A strengthened formulation and cutting planes for the open pit mine production scheduling problem. Computer and Operational Research, 37(9): 1641-1647. https://doi.org/10.1016/j.cor.2009.12.008

[2] Lamghari, A., Dimitrakopoulos, R. (2012). A diversified Tabu search approach for the open-pit mine production scheduling problem with metal uncertainty. European Journal of Operational Research, 222(3): 642-652. https://doi.org/10.1016/j.ejor.2012.05.029

[3] Ramazan, S., Dimitrakopoulos, R. (2013). Production scheduling with uncertain supply: A new solution to the open pit mining problem. Optimization and Engineering, 14(2): 361-380. https://doi.org/10.1007/s11081-012-9186-2

[4] Nasab, H., Pourrahimian, Y., Ben-Awuah, E., Kalantari, S. (2011). Mixed integer linear programming formulations for open pit production scheduling. Journal of Mining Science, 47: 338-359. https://doi.org/10.1134/S1062739147030117

[5] Wills, B., Munn, T. (2015). An introduction to the practical aspects of ore treatment and mineral recovery, wills' mineral processing technology. Butterworth-Heinemann. https://doi.org/10.1016/C2010-0-65478-2

[6] Ravenscroft, P.J. (1992). Risk analysis for mine scheduling by conditional simulation. Section A: Mining Industry, 101: 104-108. https://doi.org/10.1016/0148-9062(93)90969-K

[7] Dowd, P.A., Saraç, C. (1994). An extension of the LU decomposition method of conditional simulations. Geostatistical Simulations, 7: 23-36. https://doi.org/10.1007/978-94-015-8267-4_2

[8] Dowd, P.A. (1997). Risk in minerals projects: analysis, perception and management. Transactions of the Institution of Mining and Metallurgy, Section A: Mining Industry, 106: A9-A18

[9] Dimitrakopoulos, R., Farrelly, C., Godoy, M. (2002). Moving forward from traditional optimization: grade uncertainty and risk effects in open pit design. Transactions of the Institutions of Mining and Metallurgy: Section A, Mining Technology, 111(1): A82-A88. https://doi.org/10.1179/mnt.2002.111.1.82

[10] Dimitrakopoulos, R., Martinez, L., Ramazan, S. (2007). A maximum upside/minimum downside approach to the traditional optimization of open pit mine design. Journal of Mining Science. 43(1): 73-82. https://doi.org/10.1007/s10913-007-0009-3

[11] Dimitrakopoulos, R., Abdel Sabour, S. (2007). Evaluating mine plans under uncertainty: Can the real options make a difference? Resource Policy, 32(3): 116-125. https://doi.org/10.1016/j.resourpol.2007.06.003.

[12] Lerchs, H., Grossmann, I.F. (1965). Optimum design of open pit mines. Canadian Institute of Mining Transactions, 68: 17-24.

[13] Picard, J.C. (1976). Maximal closure of a graph and applications to combinatorial problems. Management Science, 22: 1268-1272. https://doi.org/10.1287/mnsc.22.11.1268

[14] Dagdelen, K., Johnson, T.B. (1986). Optimum open pit mine production scheduling by Lagrangian parameterization. 19th APCOM Symposium of the Society of Mining Engineers, pp. 127-142.

[15] Caccetta, L., Giannini, L.M. (1988). An application of discrete mathematics in the design of an open pit mine. Discrete Applied Mathematics, 21(1): 1-19. https://doi.org/10.1016/0166-218X(88)90030-3

[16] Caccetta, L., Hill, S.P. (2003). An application of branch-and -cut to open pit mine scheduling. Journal of Global Optimization, 27: 349-365. https://doi.org/10.1023/A:1024835022186

[17] Chowdhury, S., Chatterjee, S. (2013). Pit optimisation and life of mine scheduling for a tenement in central African copper belt. International Journal of Mining, Reclamation and Environment, 28(3): 200-213. http://dx.doi.org/10.1080/17480930.2013.811802

[18] Gershon, M. (1983). Optimal mine production scheduling evaluation of large-scale mathematical programming approaches. International Journal of Mining Engineering, 1: 315-329. https://doi.org/10.1007/BF00881548

[19] Kumral, M. (2013). Multi-period mine planning with multi-process routes. International Journal of Mining Science and Technology, 23(3): 317-321. https://doi.org/10.1016/j.ijmst.2013.05.001

[20] Little, J., Knights, P., Topal, E. (2013). Integrated optimization of under- ground mine design and scheduling. Journal of the Southern African Institute of Mining and Metallurgy, 113: 775-785. 

[21] Nehring, M., Topal, E., Kizil, M., Knights, P. (2012). Integrated short- and medium-term underground mine production scheduling. Journal of the Southern African Institute of Mining and Metallurgy, 112: 365-378. 

[22] De Carvalho Junior, J., Koppe, J., Costa, J. (2012). A case study application of linear programming and simulation to mine planning. Journal of the Southern African Institute of Mining and Metallurgy, 112: 477-484. 

[23] Rothlauf, F. (2011). Design of Modern Heuristics: Principles and Application. Springer Science & Business Media.

[24] Tabesh, M., Askari-Nasab, H. (2011). Two-stage clustering algorithm for block aggregation in open pit mines. Mining Technology: Transactions of the Institutions of Mining and Metallurgy: Section A, 120(3): 158-169. https://doi.org/10.1179/1743286311Y.0000000009

[25] Topal, E., Little, J. (2011). Strategies to assist in obtaining an optimal solution for an underground mine planning problem using mixed integer programming. International Journal of Mining and Mineral Engineering, 3(2): 152-172. https://doi.org/10.1504/IJMME.2011.042429

[26] Koushavand, B., Askari-Nasab, H., Deutsch, C. (2014). A linear programming model for long-term mine planning in the presence of grade uncertainty and a stockpile. International Journal of Mining Science and Technology, 24(4): 451-459. https://doi.org/10.1016/j.ijmst.2014.05.006

[27] Martinez, M., Newman, A. (2011). Solution approach for optimizing long- and short-term production scheduling at LKAB’s Kiruna mine. European Journal of Operational Research, 211(1): 184-197. https://doi.org/10.1016/j.ejor.2010.12.008 

[28] Asad, M.W.A., Dimitrakopoulos, R. (2013). Implementing a parametric maximum flow algorithm for optimal open pit mine design under uncertain supply and demand. Journal of the Operational Research Society, 64: 185-197. https://doi.org/10.1057/jors.2012.26

[29] Gholamnejad, J., Mojahedfar, A. (2010). Determination of the largest pit with the non-negative net profit in the open pit mines. Journal of Mining and Environment, 1(2): 45-52. https://dx.doi.org/10.22044/jme.2011.14

[30] Kumral, M., Dowd, P.A. (2005). A simulated annealing approach to mine production scheduling. Journal of the Operational Research Society, 56(8): 922-930. https://doi.org/10.1057/palgrave.jors.2601902

[31] Sattarvand, J., Niemann-Delius, C. (2013). A new metaheuristic algorithm for long-term open-pit production planning. Archives of Mining Sciences, 58: 107-118. https://doi.org/10.2478/amsc-2013-0007

[32] Shishvan, M.S., Sattarvand, J. (2015). Long term production planning of open pit mines by ant colony optimization. European Journal of Operational Research, 240: 825-836. https://doi.org/10.1016/j.ejor.2014.07.040

[33] Ibrahimov, M., Mohais, A., Schellenberg, S., Michalewicz, Z. (2014). Scheduling in iron ore open-pit mining. The International Journal of Advanced Manufacturing Technology, 72: 1021-1037. https://doi.org/10.1007/s00170-014-5619-8

[34] Moosavi, E., Gholamnejad, J., Ataee-pour, M., Khorram, E. (2014). Improvement of Lagrangian relaxation performance for open pit mines constrained long-term production scheduling problem. Journal of Central South University, 21: 2848-2856. https://doi.org/10.1007/s11771-014-2250-7

[35] Hustrulid, W.A., Kuchta, M. (2006). Open Pit Mine Planning and Design. Taylor & Francis, CRC Press, USA. ISBN: 9780415407410.

[36] Ramazan, S., Dimitrakopoulos, R. (2004). Recent applications of operations research and efficient MIP formulations in open pit mining. SME Transactions, 316: 73-78. 

[37] Wolsey, L.A. (1998). Integer Programming. New York Wiley. 

[38] De Freitas Silva, M., Dimitrakopoulos, R., Lamghari, A. (2015). Solving a large SIP model for production scheduling at a gold mine with multiple processing streams and uncertain geology. Mining Technology: Transactions of the Institutions of Mining and Metallurgy: Section A, 124(1): 24-33. https://doi.org/10.1179/1743286314Y.0000000075

[39] Lamghari, A., Dimitrakopoulos, R. (2016). A network flow-based algorithm for scheduling production in multiprocessor open pit mines accounting for metal uncertainty. European Journal of Operational Research, 250(1): 273-290. https://doi.org/10.1016/j.ejor.2015.08.051

[40] Chatterjee, S., Sethi, M.R., Asad, M.W.A. (2016). Production phase and ultimate pit limit design under commodity price uncertainty. European Journal of Operational Research, 248(2): 658-667. https://doi.org/10.1016/j.ejor.2015.07.012

[41] Goovaerts, P. (1997). Geostatistics for Natural Resources Evaluation. New York Oxford University Press.

[42] Deutsch, C., Journel, A. (1997). GSLIB: Geostatistical Software Library and User's Guide, Oxford University Press, New York. 

[43] ILOG, CPLEX 11.2 User's Manual, Armonk, IBM.