A Genetic algorithm scheme for large scale open-pit mine production scheduling

Abstract

Due to the large size of open-pit mines’ long-term production scheduling (OPMPS) problem in large-scale deposits, it is challenging to solve that problem as the mixed integer linear programming (MILP) model. This study used an approach of the genetic algorithm (GA) to tackle this challenge. So, in a small hypothetical deposit, based on the blocks in the ultimate pit limit and scenarios with 2–6 phases, net present values (NPV) and computational times obtained from the GA and MILP model were compared to evaluate the GA. Also, the GA was applied to a large-scale deposit to determine the efficiency of the GA in real deposits. The maximum NPV was obtained for the four-phase scenario in the hypothetical deposit and the six-phase scenario in the large-scale deposit. Although the GA's NPV decreased slightly compared to the global optimum solution from the MILP model, the computational time was significantly reduced.

Keywords

Open-Pit mine ultimate pit limit net present value operational constraints NP-hard problem long-term production scheduling genetic algorithm mixed-integer linear programming model

Introduction

Production scheduling of open-pit mines is a fundamental problem in surface mine planning that begins with building a discrete representation of the deposit, known as a block model. A block model is a three-dimensional array of equal-sized units called a block. Thus, the deposit is broken down into blocks. A deposit's block model may contain thousands to millions of blocks regarding the size of the deposit. Each block has a set of characteristics, including mineral and contaminant grades, rock types, and rock density estimated using drill hole data (Espinoza et al. 2013). A block is extractable if the expected revenue from the sale of the metal in the block exceeds the processing cost. In other words, each block has an economic value representing the net profit. The blocks with positive and negative economic values are ore and waste, respectively (Kumral and Dowd 2021).

The open-pit mines’ long-term production scheduling (OPMPS) problem involves determining blocks extracted at each period of the mine life to maximize the mining operation's net present value (NPV). Also, different operational constraints must be observed when scheduling blocks. In addition, these blocks must be at the ultimate pit limit (UPL) of open-pit mines. The operational constraints are as follows: (Ramazan and Dimitrakopoulos 2004b; Samavati et al. 2017).

Slope constraints: All the overlying blocks that must be extracted before mining a given block must be determined. In other words, a block cannot be mined before its predecessors.

Reserve constraints: A block cannot be mined more than once.

Mining capacity constraints: The total amount of material (waste and ore) to be mined must be between or equal to two minimum and maximum available equipment capacities at each period.

Grade blending constraints: The average material grade sent to the mill must be between or equal to two minimum and maximum grade values at each period.

Processing capacity constraints: The total amount of ore cannot be more than or less than the processing capacity at each period.

The OPMPS problem has been widely studied in the last few decades due to its complexity and significant impact on the success and profitability of open-pit mine extraction projects. Solving methods for OPMPS problems can be classified into exact solution, heuristic, and metaheuristic. Exact solutions refer to techniques with a mathematical basis and ultimately find the exact answer to the problem. These methods can solve the OPMPS problem of small to medium-scaled deposits within a reasonable computational time. However, solving this problem to obtain a feasible solution for large deposits with considerable constraints may result in many decision variables, making it difficult to solve within a reasonable time. In other words, it is NP-hard, i.e. the computational time to achieve the optimal solution is not acceptable; therefore, to deal with large-scale deposits, the optimal solution is calculated approximately (Dorigo et al. 2006). As the heuristic name implies, heuristics have no mathematical basis, so the solutions obtained from these methods cannot be trusted, similar to Gershon and Wang-Sevim algorithms. Although Gershon in large block models can solve the OPMPS problem in a short time, its non-compliance with operational constraints does not provide reliable answers (Gershon 1983, 1987; Wang and Sevim 1995). Metaheuristic approaches could play a critical role in dealing with such conditions. In recent years, different researchers have tried applying these approaches to the OPMPS problem. These approaches can find the optimum or near-optimum solutions for large combinatorial problems within a reasonable time (Danish et al. 2021). The presented researches about each of these methods are stated in the following.

The MILP model, linear programming model (LP), dynamic programming, and network flow algorithm can be mentioned among the exact solutions. Gershon proposed a MILP model for mining production scheduling. However, the large number of binary variables in the OPMPS problem model makes solving it computationally tricky (Gershon 1983). In general, the number of binary variables required for the MILP model is equal to the number of blocks in the model multiplied by the total periods to be scheduled (Ramazan and Dimitrakopoulos 2004b). Elevli proposed a dynamic programming method to solve the OPMPS problem. This approach does not guarantee the solution's optimality, and its application to large-scale problems is unclear (Elevli 1995; Osanloo et al. 2008). Caccetta and Hill used the branch and cut algorithm to solve the OPMPS problem's integer programming (IP) model. This approach can produce optimal results for medium-sized problems. However, it is computationally complex for large-size problems to produce optimal results (Caccetta and Hill 2003). Ramazan proposed a mixed integer programming (MIP) scheduling model for the OPMPS problem that reduces the number of binary variables. In this case, the variables representing only the ore blocks are defined as binary, and the remaining variables are defined linearly. This method reduces the solution time and increases efficiency. Also, Ramazan introduced a block aggregation technique named a fundamental tree algorithm to reduce the number of binary variables for large-scale deposits (Ramazan and Dimitrakopoulos 2004b; Ramazan et al. 2005; Ramazan 2007). Askari-Nasab et al. proposed a MILP model to solve the OPMPS problem. To reduce the number of binary variables in the model, they grouped the blocks into larger units using fuzzy logic clustering called mining cuts (Askari-Nasab et al. 2010). In another research, Askari-Nasab et al. examined the shortcomings of the current MILP models used for the OPMPS problem, particularly the inability to solve large-scale extraction problems. This method aggregates blocks in clusters based on attributes, e.g. rock type, grade distribution, and location, to reduce the number of binary variables (Askari-Nasab et al. 2011). Gholamnejad et al. presented an integer linear programming (ILP) formulation for solving the OPMPS problem that reduces the number of active benches in any scheduling period to reduce mining equipment movement between benches in a single scheduling period (Gholamnejad et al. 2020).

As mentioned earlier, most methods can handle either a simplified version of the OPMPS problem or small to medium-scale deposits within a sufficient implementation time. However, solving this problem to obtain a feasible solution for medium to large deposits with considerable constraints may result in many decision variables, making it difficult to solve within an acceptable time. Therefore, metaheuristics could be helpful and practical in dealing with such conditions. These techniques can find the optimum or near-optimum solution to NP-hard problems within a reasonable time. In recent years, different researchers have tried applying these approaches to the OPMPS problem.

The Genetic algorithm (GA), Simulated Annealing (SA), Tabu Search (TS), and Ant Colony algorithm can be mentioned among the metaheuristic techniques. Denby and Schofield were the first to use GA because of its robustness and speed for scheduling open-pit mine production. This method used a three-dimensional block model of a copper–gold deposit that included each block's grade and rock type information, and then slope constraints were added to the problem. Among the advantages of the GA designed for an optimization problem is that it can usually be applied on a similar problem with little or no change, and often in less than 10 generations, a near-optimal solution for some problem types is found (Denby and Schofield 1994). Alipour et al. introduced a GA-based approach to the OPMPS problem. This approach randomly generated the initial population and ensured each solution's feasibility through a normalization function. However, grade-blending constraints were not considered (Alipour et al. 2020, 2022). Kumral and Dowd were the first to use SA to solve the OPMPS problem. The Lagrangian parameterization technique obtained the initial sub-optimal solution for multi-objective SA optimization in this technique (Kumral and Dowd 2005). Lamghari and Dimitrakopoulos, to solve the OPMPS problem, used TS and variable neighbourhood descent algorithms. This approach could produce a near-optimal solution in a reasonable implementation time (Lamghari and Dimitrakopoulos 2012). Shishvan and Sattarvand applied the Ant Colony algorithm for the open-pit mine production planning problem (Shishvan and Sattarvand 2015). Finally, Khan & Niemann- Delius utilized particle swarm optimization and differential evolution to solve the open-pit mine production planning problem (Khan and Niemann-Delius 2014, 2018).

By studying different production scheduling methods, three approaches can be used to solve the OPMPS problem based on the phases created within the UPL of open pit mines. The first approach extracts the most valuable phase in the first period. In this approach, phases are divided from top to bottom. The blocks related to the selected phase are removed, and then this process is repeated for all the remained blocks in the UPL. In other words, maximizing the NPV of a mining project is achieved with high-grade ore extraction as soon as possible. Therefore, when phases are used to find the optimum production schedule, these phases should be maximum-metal phases for the resulting schedule to be optimum. A maximum-metal phase of size N is a phase that contains more metal than any other phase of the same size N. Gershon used this approach to OPMPS (Gershon 1987; Wang and Sevim 1995).

The second approach divides phases from the bottom of the UPL upwards. In this approach, the least valuable phase, or the phase with the lowest grade, is extracted in the last period. The blocks related to the selected phase are removed, and then this process is repeated in the entire area of the UPL for the remaining blocks. Wang and Sevim used this approach to the OPMPS problem (Wang and Sevim 1995).

Finally, in the third approach, all of the UPL is decided simultaneously based on NPV.

The third approach can find the optimal solution. Exact methods such as the mixed integer linear programming (MILP) model use this approach to solve the production scheduling problem. However, solving the production scheduling problem in open pit mines with this approach in large-scale deposits becomes an NP-hard problem. Generally, using the second approach leads to having maximum NPV compared to the first. Therefore, in larger-scale deposits where the MILP model cannot solve the OPMPS problem, the second approach can help solve the problem.

In the studies accomplished to solve the OPMPS problem, among the three mentioned approaches, the third approach has been used in some of the exact solutions. However, other approaches have rarely been used. Also, among the studies performed using GA to solve the OPMPS problem, the shape of the pits is changed by mutation and crossover operators. In this case, reserve and slope constraints are not satisfied. Therefore, it needs a normalization step.

Nevertheless, normalization is unnecessary when the first and second approaches are used. Instead, the slope and mining capacity constraints are applied from the beginning in this approach to the problem. Therefore, this reduces the complexity of the problem. In this paper, GA is used as the second approach to solving the OPMPS problem, and all operational constraints have been applied on the studied problem.

Genetic algorithm

Most metaheuristic algorithms are inspired by the biological evolution process, swarm behaviour, and physics law. In general, these algorithms are categorized into single-solution and population-based metaheuristic algorithms. The population-based metaheuristic uses several candidate solutions during the search process. These metaheuristics maintain the variety in the population and avoid the solutions being stuck in local optima. One of the well-known population-based metaheuristic algorithms is GA, inspired by the biological evolution process. GAs perform searches in complex and large problems and provide near-optimal solutions for an optimization problem's objective or fitness function (Maulik and Bandyopadhyay 2000; Katoch et al. 2021).

GA is a population-based search algorithm that utilizes the concept of survival of the fittest. In this algorithm, the population is the solution space that includes chromosomes, which is considered an advantage of the GA because it provides a wide range of suitable solutions (chromosomes). Each chromosome consists of several genes. Also, all possible solutions must be developed to achieve the best solution (Katoch et al. 2021; Alipour et al. 2022). After calculating the fitness of each solution, which has different methods based on the type of problem, a method such as the roulette wheel is used to select a new population based on the calculated fitness (Pencheva et al. 2009). Then, crossover and mutation operators are applied to chromosomes.

Single-point crossover is the most approved crossover, which is widely in use. This way, a crossover site is randomly selected along the length of two chromosomes, and genes next to the cross-sites are interchanged. In this case, when a suitable location is chosen, better progeny can be obtained by combining the good qualities of the parents. As a challenging issue, using the crossover alone to create a child causes the GA to get stuck in the local optimal. So, the mutation is used to reduce this problem by proving the difference between new children and parents and encouraging diversity. One type of mutation is the flip-bit mutation that reverses the value of a randomly selected gene (Pencheva et al. 2009; Omar and Hirotaka 2012; Kora and Yadlapalli 2017). The process of evolution is repeated until the final condition for obtaining the chromosome with the best fitness value is met; this is known as the termination criteria (Maulik and Bandyopadhyay 2000; Hassanat et al. 2019). Since the GA is a flexible method, the results can be improved by changing its parameters. In other words, in the OPMPS problem, by performing sensitivity analysis on a number of its parameters, the NPV presented by the GA is checked, and the best value is selected (Ataei M and Osanloo M 2004; Villalba M et al. 2019). Therefore, chromosome representation, fitness function computation, crossover, mutation, and selection are the critical elements of GA. In this study, Single-point crossover and flip-bit mutation are used.

Open-pit mine production scheduling problem

OPMPS problem specifies a block mining sequence to maximize the NPV under mining and processing capacity and grade blending constraints, in addition to the slope and precedence constraints. These constraints and the methods to solve the problem will be explained in the following.

Open-pit mine production scheduling using MILP

The OPMPS problem in MILP form can be explained by representing the following formulation (Ramazan and Dimitrakopoulos 2004a). Given the sets, parameters, and decision variables in Table 1, the OPMPS problem is as follows:

Table 1

MILP sets, parameters and decision variables.

Sets and Parameters
$T$	the maximum number of scheduling periods
$n$	the total number of blocks to be scheduled
$v_{i}^{t}$	the NPV generated by mining block $i$ in period $t$
$x_{i}^{t}$	A binary variable, is equal to 1 if the block $i$ is to be mined in the period $t$ and equal to 0 otherwise
$g_{i}$	the average grade of block $i$
$G_{max}$	the maximum grade value sent to the mill
$O_{i}$	ore tonnage in block $i$
$W_{i}$	the tonnage of waste material in block $i$
$P_{max}$	the maximum capacity of processing
$M_{max}$	total available equipment capacities
$m$	the total number of blocks overlying block $k$
$k$	the index of a block considered for excavation in period $t$
$l$	the counter for the $m$ overlying blocks

The objective function:

M a x i m i z e \sum_{t = 1}^{T} \sum_{i = 1}^{n} v_{i}^{t} * x_{i}^{t}

(1)

Slope constraints:

m x_{k}^{t} - \sum_{l} \sum_{r = 1}^{t} x_{l}^{r} \leq 0

(2)

Reserve constraints:

\sum_{t = 1}^{T} x_{i}^{t} = 1

(3)

Grade blending constraints:

\sum_{i = 1}^{n} (g_{i} - G_{max}) * O_{i} * x_{i}^{t} \leq 0

(4)

Mining capacity constraints:

\sum_{i = 1}^{n} (O_{i} + W_{i}) * x_{i}^{t} \leq M_{max}

(5)

Processing capacity constraints:

\sum_{i = 1}^{n} (O_{i} * x_{i}^{t}) \leq P_{max}

(6)

The objective function, shown by Equation (1), is constructed to maximize the mining project's overall NPV. By Equation (2), all the overlying blocks that must be extracted before mining a given block are determined that can be implemented through cone templates representing the wall slopes of the open-pit mine. It should also be noted that a block could not be mined more than once, as shown in Equation (3). Equation (4) shows the upper bounds of the average material grade sent to the mill at each period. The total waste and ore to be mined cannot be more than the total available equipment capacities for any period, as Equation (5) and Equation (6) show the upper bound of the processing capacity for each period.

Genetic Algorithm for long-term open-pit mine production scheduling

This section examines how to create the objective function, generate the chromosome, select the new population, and determine the parameters related to the GA in the studied problem.

The objective function generation

The objective function of the OPMPS problem in this study is a function of the number of ‘candidate blocks.’ Candidate blocks are selected from downward cones that accept the mining capacity constraints. A downward cone is a cone created for each block subject to slope constraints. This cone should be limited to UPL. The highest block of each cone is the apex block. That is until that block is not extracted, blocks inside the cone cannot be mined. In this research, downward cones are utilized to employ the second approach. For example, Figure 1 shows a UPL of a hypothetical two-dimensional block model in which an upward cone is made for block A and a downward cone for block B.

Figure 1

The concept of upward and downward cones in the 2D UPL model.

Defining a specific capacity for downward cones is necessary to comply with the mining capacity constraints. In this study, the capacity is defined based on the number of blocks inside each downward cone. Accordingly, if the number of blocks inside the downward cone corresponding to each block is proportional to the defined capacity, it is called a candidate block. A candidate block is a block that has the ability and conditions to be separated from the UPL in the last period. This mean is if a downward extraction cone is made for this block, the number of blocks located in this cone should be smaller or equal to the number of blocks in the current phase.

For a better understanding of the matter, a hypothetical two-dimensional UPL is considered in Figure 2. The capacity of the last extraction phase is considered in four blocks. In this case, the block with the number 6 is not a candidate block because the number of blocks in the downward extraction cone of this block is five, which is more than the current phase mining capacity (Figure 2(a)). In addition, the block with the number 11 is a candidate block because the number of blocks located in the downward extraction cone of this block is three blocks, which is less than the desired number of blocks in the current phase (Figure 2(b)). All candidate blocks within the UPL are shown in Figure 2(c).

Figure 2

A hypothetical two-dimensional UPL, a: not a candidate block, b: a candidate block, c: all the candidate blocks in UPL.

In each step for all the blocks in the UPL (or the remaining blocks after extracted previous phase blocks), a downward cone is made; if that block is a candidate block, it can be placed in the search space of the genetic algorithm for the current period.

The chromosome generation

After generating the objective function, some random initial solutions (chromosomes) based on the population size are defined. The population size depends on the nature of the problem but typically contains 50–100 possible solutions (Mirzaei-Nasirabad and Khalokakaie 2008). In this research, the population size is considered to be 90.

The length of the chromosomes (initial solutions) equals the number of columns (the blocks in the block model in tandem layers with the same X and Y directions) with at least a candidate block. Each gene state is based on the number of candidate blocks in each column corresponding to that gene. So, the initial population is randomly made based on this number of states. For better understanding, in Figure 2(c), there are seven columns of blocks with at least a candidate block. Therefore, the chromosome length is equal to seven. For example, column 4 has two candidate blocks (block numbers 10 and 14). Therefore, the number of states this column creates in the chromosome is three. That means it can extract this column candidate blocks in three situations. (1) Mode zero: extracted no block. (2) Mode 1: extracted the cone corresponding to the candidate block with the number 14. (3) Mode 2: extracted the cone corresponding to the candidate block with the number 10. Finally, based on these states, three different chromosomes can be generated.

Apply the operational constraints

After creating the initial population, the fitness value of the chromosomes is calculated. Operational constraints related to solving the OPMPS problem should be applied to calculate this value. In this case, the processing capacity constraints and grade blending constraints can be applied by penalizing the fitness values of the chromosomes that do not meet each of these constraints or rewarding the fitness values of each. In this study, to effectively implement the mentioned constraints, a combination of both modes was used. Slope, reserve, and mining capacity constraints are satisfied by making downward cones for every selected candidate block. Then, a roulette wheel is used to select a new population. In this wheel, a random number is generated according to each chromosome. Therefore, a new individual is created based on the value of that number and each chromosome's fitness function.

Apply the GA parameters

In the next step, crossover and mutation operators are applied on the population after applying mentioned constraints on chromosome fitness. Therefore, single-point crossover and flip-bit mutation were used to solve the OPMPS problem with GA. Crossover and mutation were also selected from intervals [0.3,0.5] and [0.05,0.15], respectively (Mirzaei-Nasirabad and Khalokakaie 2008). The goal is to reach the maximum NPV during the life of the mine in the shortest time possible. Then, the fitness value of the chromosomes is calculated again, and the chromosome with the lowest fitness value is picked in the lowest phase. In other words, in the selection step, the chromosome with the lowest fitness is determined. This process is repeated until a termination condition has been reached. The optimizing process will be terminated if the best solution does not change during m iteration. In this study, m is considered 500 iterations. Therefore, the blocks related to the designed phase are removed; Then, the algorithm is repeated for the next phase with the remaining blocks in the UPL. Finally, the algorithm continues until all the blocks within the UPL are assigned to different phases.

As mentioned before, using sensitivity analysis, the best deals are got for the parameters of the GA, namely crossover and mutation, obtained when the maximum NPV is received. The most common approach to using sensitivity analysis is changing one factor at a time to understand what effect this produces on the output. That appears logical, as any change observed in the result will unambiguously be due to the single parameter change. Furthermore, one can keep all other parameters fixed to their central or base values by changing one parameter simultaneously. This method increases the comparability of the results (all ‘effects’ are computed regarding the same central point in space) and minimizes the chances of computer program crashes, more likely when several input factors are changed simultaneously (Saltelli and Annoni 2010). Therefore, the sensitivity analysis results are checked to determine the maximum NPV and the best crossovers and mutations are determined.

The mentioned steps of the GA for solving the OPMPS problem are according to Figure 3.

Figure 3

Steps of the GA to solve the OPMPS problem.

Implementations and results

In this section, to evaluate the results of solving the OPMPS problem in open pit mines by GA, this algorithm and MILP model were applied on a hypothetical deposit. Then, to determine the efficiency of GA in solving the OPMPS problem in real mines, the algorithm was also applied on a large-scale deposit. In the following, the results related to the hypothetical and the real deposits are discussed separately.

A small hypothetical deposit

A small hypothetical deposit was used to evaluate and verify the GA results compared to the MILP because implementing the MILP on the real deposit was very time-consuming. In addition, before performing OPMPS, it is necessary to determine the UPL for the mentioned deposit. Then, the production schedule should be done for the blocks inside this area. The attributes of the deposit's block model and its UPL are given in Tables 2 and 3, respectively. Also, the grade histogram of blocks in UPL is according to Figure 4.

Figure 4

The UPL's blocks grade histogram of the hypothetical deposit.

Table 2

The attributes of the hypothetical deposit's block model.

Block model	Block numbers	Block numbers in X, Y and Z directions	Dimension of the blocks in X,Y and Z (m)	Processing cost ($/ton)	Mining costs ($/ton)
hypothetical deposit	1350	15,15,6	10,10,10	1620	810

Block model	Waste density (g/cm³)	Ore density (g/cm³)	Selling price ($/ton)	Mean grade (%)	Cut of grade (%)	Recovery (%)
hypothetical deposit	3.7	4.1	8100	0.31	0.3	100

Table 3

The attributes of the hypothetical deposit's UPL.

Block model	Economic value of UPL	Block numbers in UPL	Stripping ratio of UPL	Ore block numbers in UPL	Waste block numbers in UPL	Life of mines (years)
hypothetical mine	113,050	475	2.6	133	342	6

The GA and MILP were applied on the block model in different scenarios. These scenarios are based on the number of phases between 2 and 4. That is 2 phases as the first scenario, 3 phases as the second scenario, and 4 phases as the third scenario. Then the NPV obtained from each scenario is compared with the others, and the highest value is selected as the optimal state.

The study is executed in the Intel Core™i7-4702 PC (3.4 GHz) with 16 GB of RAM. The CPLEX exact solver linked to MATLAB was used to solve the problem of the current study with the MILP model.

The NPV of the production scheduling problem and the computational time to solve this problem by using the GA and MILP in the hypothetical deposit are summarized in Table 4. It should be noted that the NPV for GA was obtained after performing the sensitivity analysis. In other words, the highest NPV obtained with the best crossover and mutation was selected. After applying sensitivity analysis, the best values for crossover and mutation operators are 0.3 and 0.05, respectively.

Table 4

The results of solving the OPMPS problem by MILP and GA in the hypothetical deposit.

States	Methods	Scenario 1	Scenario 2	Scenario 3
NPV($)	GA	2694.3	3123.7	3493.3
NPV($)	MILP	2994.5	3327.5	3497.7
implementation times (S)	GA	1	8	17
implementation times (S)	MILP	23	50	305

Table 5 shows the difference between the values of the NPV resulting from the GA compared to the values corresponding to the MILP.

Table 5

The difference in the NPV resulting from GA and MILP.

States	Scenario 1	Scenario 2	Scenario 3
The NPV difference (%)	10	6.12	0.12

According to Table 4, it can be seen that in both methods, the highest NPV is related to the third scenario. Therefore, the best way to the long-term production schedule for this deposit (among the available instances) is to extract it in four phases. In addition, the NPV obtained from the GA (Table 5) is only 0.12% lower than the value related to the MILP. Instead, the computational time of the GA is much less than its corresponding value in the MILP. Table 6 illustrates the average grade, stripping ratio, and block numbers in each scenario of MILP and GA.

Table 6

The average grade, stripping ratio, and block numbers in each scenario.

States	Methods	Phases	Scenario 1	Scenario 2	Scenario 3
Each phase's block number	GA	1	250	160	122
		2	225	158	115
		3		157	116
		4			122

	MILP	1	237	157	118
		2	238	159	119
		3		159	119
		4			119

Each phase's average grade	GA	1	0.45	0.45	0.45
		2	0.44	0.43	0.45
		3		0.45	0.41
		4			0.45

	MILP	1	0.48	0.50	0.52
		2	0.41	0.43	0.43
		3		0.40	0.43
		4			0.40

Each phase's stripping ratio	GA	1	3.01	2.8	2.3
		2	2.3	3.3	2.2
		3		2	2.8
		4			2.3

	MILP	1	2.6	2.5	2.6
		2	2.6	2.6	2.6
		3		2.6	2.6
		4			2.6

The typical cross-section of UPL for scenario 3 of GA is shown in Figure 5.

Figure 5

A cross-section (X = 190) view of the hypothetical deposit's UPL for scenario 3 of GA.

A large-scale deposit

After evaluating the GA results in solving the OPMPS problem in the small deposit, this section studies its capability on the real deposit. The attributes of the large-scale deposit's block model and its UPL are given in Tables 7 and 8, respectively. Also, the grade histogram of blocks in the UPL is according to Figure 6.

Figure 6

The UPL's blocks grade histogram of the large-scale deposit.

Table 7

The attributes of the large-scale deposit's block model.

Block models	Block numbers	Block numbers in X, Y and Z directions	Dimension of the blocks in X,Y and Z (m)	Processing cost ($/ton)	Mining costs ($/ton)
The large-scale deposit	94050	57,50,33	10,10,5	1150	650

Block models	Waste density (g/cm³)	Ore density (g/cm³)	Selling price ($/ton)	Mean grade (%)	Cut of grade (%)	Recovery (%)
The large-scale deposit	2.16	2.39	3000	2.4	0.6	100

Table 8

The attributes of the large-scale deposit's UPL.

Block models	Economic value of UPL	Block numbers in UPL	Ore block numbers in UPL	Waste block numbers in UPL	Life of mines (years)
The large-scale deposit	215,360	23,040	18,556	4484	35

The GA was applied on the block model in five scenarios. These scenarios have 2–6 phases. Then the NPVs obtained from scenarios were compared, and the highest NPV was selected as the optimal state.

The computational time, NPV, the number of blocks in each phase, the average grade of each phase, and the stripping ratio are shown in Table 9. According to Table 9, this deposit achieves the highest NPV if extracted in six phases. In this case, the crossover and mutation operator values should be 0.3 and 0.15. In addition, iterations and population size should be considered 300 and 90, respectively.

Table 9

The results of solving the OPMPS problem by GA in the large-scale deposit.

States	Phases	Scenario 1	Scenario 2	Scenario 3	Scenario 4	Scenario 5
Each phase's block number	1	10,850	6147	7650	4301	4734
	2	12,190	10,764	7354	5549	5091
	3		6129	4956	5967	4730
	4			3080	4952	4153
	5				2271	2705
	6					1627
Each phase's average grade	1	1.6	1.4	1.5	1.4	1.5
	2	1.1	1.1	1.4	1.4	1.5
	3		1.0	1.4	1.3	1.3
	4			1.2	1.3	1.3
	5				1.3	1.3
	6					1.2
Each phase's stripping ratio	1	0.3	0.39	0.36	0.45	0.42
	2	0.2	0.21	0.20	0.30	0.30
	3		0.20	0.20	0.15	0.15
	4			0.16	0.22	0.18
	5				0.14	0.23
	6					0.10
NPV ($)	6780.6	12,668	29,184	23,706	34,025
Implementation times (S)	756	986	1261	1828	2140

The plan view of UPL for scenario 5 at level 1610 is shown in Figure 7.

Figure 7

A 2D view of large-scale deposit's UPL for plan 1610.

Exact solutions always provide the best answer in solving optimization problems. However, implementing these methods, similar to MILP on large-scale deposit production scheduling, is time-consuming and is increased with the increasing number of phases (Table 9). Production scheduling studies need to provide an appropriate answer in a reasonable time. Therefore, GA is proposed as a fast method with a near-optimal answer. In this case, by considering all the operational constraints, the GA can provide an appropriate answer in a shorter time than MILP. In addition, by applying sensitivity analysis, the appropriate value of its parameters similar to crossover and mutation can be adjusted to achieve the maximum NPV.

Conclusions

OPMPS problem in large-scale deposits using exact solutions such as MILP becomes an NP-hard problem. That is, it cannot be solved in a reasonable time, or it cannot be solved at all because of the many blocks followed by many binary variables. One way to solve this problem is to use metaheuristics such as GA because it performs the search in large-scale problems and provides the near-optimal solution for the OPMPS problem in less time than the MILP. The advantage of this algorithm over the other metaheuristic algorithms is that GA maintains the variety in the population and avoids the solutions being stuck in local optima.

This research aims to use GA in long-term open-pit mine production scheduling. The GA results obtained in the production scheduling of a small hypothetical deposit were compared with those obtained from MILP to evaluate the efficacy of GA. These two methods were applied on this block model in three scenarios based on the number of phases. By comparing the NPVs obtained from the two methods, it was found that the NPV obtained from the GA in the four-phase scenario is, at most, 0.12% lower than the NPV obtained from the MILP. However, it provided the answer in just 17 s, which is 288 s faster than MILP. This computation time difference in large-scale deposits may reach several days. Then, GA was applied on a real mine to determine its capability on large-scale deposits. The maximum computing time for GA in this deposit was approximately 36 min, corresponding to the six-phase scenario. This item provides the highest amount of NPV. So considering all the operational constraints, GA is proposed as a faster solution method with a near-optimal solution.

Footnotes

Disclosure statement

No potential conflict of interest was reported by the author(s).

References

Alipour

, Khodaiari

, Jafari

, Tavakkoli-Moghadam

2020. Production scheduling of open-pit mines using genetic algorithm: a case study. Int J Manag Sci Eng Manag. 15(3):176–183. doi:10.1080/17509653.2019.1683090.

Alipour

, Khodaiari

, Jafari

, Tavakkoli-Moghadam

2022. An integrated approach to open-pit mines production scheduling. Resour Policy. 75:102459. doi:10.1016/j.resourpol.2021.102459.

Askari-Nasab

, Awuah-Offei

, Eivazy

2010. Large-scale open pit production scheduling using mixed integer linear programming. Int J Min Miner Eng. 2(3):185–214. doi:10.1504/IJMME.2010.037624.

Askari-Nasab

, Pourrahimian

, Ben-Awuah

, Kalantari

2011. Mixed integer linear programming formulations for open pit production scheduling. J Min Sci. 47(3):338–359. doi:10.1134/S1062739147030117.

Ataei

, Osanloo

2004. Using a combination of genetic algorithm and the grid search method to determine optimum cutoff grades of multiple metal deposits. Int J Surf Mining, Reclam Environ. 18(1):60–78. doi:10.1076/ijsm.18.1.60.23543.

Caccetta

, Hill

2003. An application of branch and cut to open pit mine scheduling. J Glob Optim. 27(2–3):349–365. doi:10.1023/A:1024835022186.

Danish

AAK

, Khan

, Muhammad

, Ahmad

, Salman

2021. A simulated annealing based approach for open pit mine production scheduling with stockpiling option. Resour Policy. 71:102016. doi:10.1016/j.resourpol.2021.102016.

Denby

, Schofield

1994. Open-pit design and scheduling by use of genetic algorithms. Trans Inst Min Metall Sec A Min Ind. 103.

Dorigo

, Birattari

, Stutzle

2006. Ant colony optimization. IEEE Comput Intell Mag. 1(4):28–39. doi:10.1109/MCI.2006.329691.

10.

Elevli

1995. Open pit mine design and extraction sequencing by use of OR and AI concepts. Int J Surf Min Reclam Environ. 9(4):149–453. doi:10.1080/09208119508964741.

11.

Espinoza

, Goycoolea

, Moreno

, Newman

2013. MineLib: a library of open pit mining problems. Ann Oper Res. 206(1):93–114. doi:10.1007/s10479-012-1258-3.

12.

Fathollahzadeh

, Asad

, Mardaneh

, Cigla

2021. Review of solution methodologies for open Pit mine production scheduling problem. Int J Min Reclam Environ. 1–36.

13.

Gershon

1983. Optimal mine production scheduling: evaluation of large scale mathematical programming approaches. Int J Min Eng. 1(4):315–329. doi:10.1007/BF00881548.

14.

Gershon

1987. Heuristic approaches for mine planning and production scheduling. Int J Min Geol Eng. 5(1):1–13. doi:10.1007/BF01553529.

15.

Gholamnejad

, Lotfian

, Kasmaeeyazdi

2020. A practical, long-term production scheduling model in open pit mines using integer linear programming. J South Afr Inst Min Metall. 120(12):665–670. doi:10.17159/2411-9717/769/2020.

16.

Hassanat

, Almohammadi

, Alkafaween

, Abunawas

, Hammouri

, Prasath

VB.

2019. Choosing mutation and crossover ratios for genetic algorithms – a review with a new dynamic approach. Information. 10(12):390. doi:10.3390/info10120390.

17.

Katoch

, Chauhan

, Kumar

2021. A review on genetic algorithm: past, present, and future. Multimed Tools Appl. 80(5):8091–8126. doi:10.1007/s11042-020-10139-6.

18.

Khan

, Niemann-Delius

2014. Production scheduling of open pit mines using particle swarm optimization algorithm. Adv Oper Res. 2014. doi:10.1155/2014/208502.

19.

Khan

, Niemann-Delius

2018. A differential evolution based approach for the production scheduling of open pit mines with or without the condition of grade uncertainty. Appl Soft Comput. 66:428–437. doi:10.1016/j.asoc.2018.02.010.

20.

Kora

, Yadlapalli

2017. Crossover operators in genetic algorithms: a review. Int J Comput Appl. 162(10).

21.

Kumral

, Dowd

PA.

2005. A simulated annealing approach to mine production scheduling. J Oper Res Soc. 56(8):922–930. doi:10.1057/palgrave.jors.2601902.

22.

Lamghari

, Dimitrakopoulos

2012. A diversified Tabu search approach for the open-pit mine production scheduling problem with metal uncertainty. Eur J Oper Res. 222(3):642–652. doi:10.1016/j.ejor.2012.05.029.

23.

Maulik

, Bandyopadhyay

2000. Genetic algorithm-based clustering technique. Pattern Recognit. 33(9):1455–1465. doi:10.1016/S0031-3203(99)00137-5.

24.

Mirzaei-Nasirabad

, Khalokakaie

2008. Optimum open pit design with the use of genetic algorithm. 5th international conference and exhibition on mass mining; Luleå, Sweden.

25.

Omar

, Hirotaka

2012. A survey of computational approaches to portfolio optimization by genetic algorithms. In: 18th international conference computing in economics and finance, society for computational economics.

26.

Osanloo

, Gholamnejad

, Karimi

2008. Long-term open pit mine production planning: a review of models and algorithms. Int J Min Reclam Environ. 22(1):3–35. doi:10.1080/17480930601118947.

27.

Pencheva

, Atanassov

, Shannon

2009. Modelling of a roulette wheel selection operator in genetic algorithms using generalized nets. Int J Bioautomation. 13(4):257.

28.

Ramazan

2007. The new Fundamental Tree Algorithm for production scheduling of open pit mines. Eur J Oper Res. 177(2):1153–1166. doi:10.1016/j.ejor.2005.12.035.

29.

Ramazan

, Dagdelen

, Johnson

TB.

2005. Fundamental tree algorithm in optimising production scheduling for open pit mine design. Min Technol. 114(1):45–54. doi:10.1179/037178405X44511.

30.

Ramazan

, Dimitrakopoulos

2004a. Recent applications of operations research and efficient MIP formulations in open pit mining. Soc Min Metall Explor Inc Trans. 316.

31.

Ramazan

, Dimitrakopoulos

2004b. Traditional and New MIP models for production scheduling with In-situ grade variability. Int J Surf Min. 18:13.

32.

Saltelli

, Annoni

2010. How to avoid a perfunctory sensitivity analysis. Environ Model Softw. 25(12):1508–1517. doi:10.1016/j.envsoft.2010.04.012.

33.

Samavati

, Essam

, Nehring

, Sarker

2017. A local branching heuristic for the open pit mine production scheduling problem. Eur J Oper Res. 257(1):261–271. doi:10.1016/j.ejor.2016.07.004.

34.

Shishvan

, Sattarvand

2015. Long term production planning of open pit mines by ant colony optimization. Eur J Oper Res. 240(3):825–836. doi:10.1016/j.ejor.2014.07.040.

35.

Villalba Matamoros

, Kumral

2019. Calibration of genetic algorithm parameters for mining-related optimization problems. Nat Resour Res. 28(2):443–456. doi:10.1007/s11053-018-9395-2.

36.

Wang

, Sevim

1995. Alternative to parameterization in finding a series of maximum-metal pits for production planning. Min Eng. 178–182.