An Interactive Planning and Scheduling Framework for Optimising PitstoCrushers Operations
 Author: Liu Shi Qiang, Kozan Erhan
 Organization: Liu Shi Qiang; Kozan Erhan
 Publish: Industrial Engineering and Management Systems Volume 11, Issue1, p94~102, 01 March 2012

ABSTRACT
In this paper, an interactive planning and scheduling framework are proposed for optimising operations from pits to crushers in ore mining industry. Series of theoretical and practical operations research techniques are investigated to improve the overall efficiency of mining systems due to the facts that mining managers need to tackle optimisation problems within different horizons and with different levels of detail. Under this framework, mine design planning, mine production sequencing and mine transportation scheduling models are integrated and interacted within a whole optimisation system. The proposed integrated framework could be used by mining industry for reducing equipment costs, improving the production efficiency and maximising the net present value.

KEYWORD
Open Pit , Mine Design Planning , Mine Production Sequencing , Mine Transportation Scheduling , Pits to Crushers

1. INTRODUCTION
Nowadays, mining activities take place all over the world and become a major source of a country’s natural wealth. Modern mining is very complicated procedure that may sustain over many years and necessitate huge expenditure. To maximise the profit and the utilisation of mine reserves while providing a better development program, a good mining plan/schedule must not only meet both the longrange and longterm mining requirements but also satisfy many practical details that are unique to daytoday operations. The operation of a mine is an enormous and complex task, particularly for mines having a life of many years. According to the recent literature survey, Operations Research (OR) techniques (Newman
et al. , 2009; Kozan and Liu, 2011) have been applied to resolve a number of essential mining optimisation problems.Mining is the process of excavating the natural minerals such as metallic ore (iron), nonmetallic ore (phosphate) and fossil fuels (coal) from the earth’s crust. Mining methods is mainly divided into two groups: openpit mining and underground mining. Most of the world’s ore mineral is extracted by openpit mining, especially in Australia. In this paper, we focus on the integration of openpit mine design, mine production and pitstocrushers transportation under an interactive planning and scheduling optimisation framework.
1.1 Literature Review on Mine Design Planning
The fundamental and vital mining problem is to determine the contours of an openpit mine (blocks of a mine), based on geological data and engineering feasibility requirements to yield maximum possible net income. The problem of determining the optimum ultimate pit limits (contours) of a mine is called
in this paper. To design a pit, the entire volume is subdivided into blocks and the value of the ore in each block is estimated by geological information. Due to slope requirements of a pit, precedence relationships are regarded as the most critical constraints and must be satisfied. Subject to these constraints, the objective is to determine the closed subset of blocks that maximise the net present value.mine design planning As pioneers, Lerchs and Grossmann (1965) present to the mining community an algorithm to find the optimum design for an openpit mine. Two numerical methods are proposed to determine the pit contour with the maximum profit: a simple dynamic programming algorithm for the 2D pit and a more complicated iterative algorithm (known as LerchsGrossmann algorithm) for the 3D pit. However, the LerchsGrossmann algorithm is vague due to the lack of mathematical validations. Caccetta and Giannini (1994, 1998) present several mathematical theorems in their implementation and development of LerchsGrossmann algorithm. Their work is helpful in explaining the structure and characteristics of LerchsGrossmann algorithm. Underwood and Tolwinski (1998) transform the LerchsGrossmann approach by mathematical programming settings. Thus, the minedesign graph model is represented by matrices and solved by generic linear programming formulation. A dual simplex approach is developed and compared with Lerchs Grossmann algorithm by validating some mathematical lemmas and remarks. Their academic contribution is to provide an interpretation of the network flow graph theoretic methodology from a mathematical programming viewpoint. By formulating the openpit mine as the maximum closure of a directed network flow graph, the mine design problem is actually equivalent to the maximum flow or the minimum cut problem. For the maximum flow problem, there are a number of efficient algorithms that have been developed over the last decade. Relating to implementation and performance analysis for the mine design problems, Hochbaum and Chen (2000) present a detailed study of the pushrelabel algorithm as compared to the LerchsGrossmann algorithm.
Nowadays, the openpit mine design planning problem has been widely studied since the pioneering work of Lerchs and Grossmann (1965). Due to its simplicity and usefulness, the 2D (3D) block models and Lerchs Grossmanntype approaches (including subsequent extensions and improvements) have been commonly used by most offtheshelf commercial mining software packages for openpit mine design and longterm planning.
1.2 Literature Review on Mine Production Sequencing
To distinguish the problem types, the problem for determining the sequence of the blocks (or benches) over time periods is called
in this paper. The development of optimisation models which can generate the extraction sequence of mining blocks over midterm time horizon, has become more essential in today’s competitive and high risk mining world with volatile commodity prices. In the literature, the following papers deal with the openpit mine production production sequencing problem. Sundar and Acharya (1995) present two mathematical programming models: a LP model for the choice of blocks to be blasted; and a stochastic programming model for the quantity of ores and wastes to be mined from each of the selected blocks. Caccetta and Hill (2003) present a mixed integer programming (MIP) model for a general mine production sequencing problem. The MIP model proposed by Caccetta and Hill (2003) has been well known in mining industries and received a considerable attention. The objective of this MIP model is to maximise the profits in certain periods over which the blocks (up to 88,000) are sequenced. However, due to software commercialisation and confidentiality agreements, they only summarise some important features and the full details of all aspects of their proposed branchandcut solution approach are not provided in this paper. To solve this type MIP model, Bolandmine production sequencing et al. (2009) develop a LPbased disaggregation approach based on column generation approaches. Furthermore, Bleyet al. (2010) relax this MIP formulation by adding inequalities derived by combining the precedence and production constraints.Many researchers indicate that large size of realworld cases has made the mine production MIP model intractable for use, thus leading to the development of numerous heuristic methods. The following papers address heuristic approaches for mine production sequencing problems. Cullenbine, Wood and Newman (2011) recently develop a slidingtimewindow heuristic for the openpit mine block sequencing problem. This heuristic algorithm uses an “earliest start time” or “earliest extraction period” for each block under maximum production and maximum processing capacities. However, the proposed heuristic approach cannot guarantee to find a feasible solution of submodels because of assumptions and relaxed variables. Myburgh and Deb (2010) report an application of evolutionary algorithm for mine production sequencing. In their proposed evolutionary optimisation procedure, a starting feasible sequence of blocks represented as a chromosome is iteratively improved by genetic operators such as crossover and mutation. However, it is unclear how the feasibility of neighbouring solutions can be guaranteed subject to constraints of precedence relationships, resource capacities and time periods. Ramazan (2007) develops a socalled “Fundamental Tree Algorithm” with LP to aggregate a subset of blocks as branched trees. This algorithm is useful to reduce number of integer variables and number of constraints required within the MIP formulation for mine production sequencing. However, the author cannot further propose a heuristic algorithm to solve the relaxed MIP model. Kumral and Dowd (2005) develop a simulated annealing (SA) metaheuristic to deal with mine production sequencing. In their method, optimisation procedure is carried out in two stages. In the first stage, Lagrangian relaxation is applied to obtain an initial suboptimal solution. Then, SA algorithm is implemented to improve the initial suboptimal solution further. However, it is hard to justify the correctness of this method because the detail of constructing a feasible solution is not provided in the paper. Tolwinski and Underwood (1996) propose a guidedsearch heuristic algorithm to find a path with maximum value in an acyclic direct graph. Then, this socalled pathgeneration procedure is developed to determine the sequence of blocks based on the valuebased decision rule. However, solutions of largesize realistic instances may be quite far away from optimality.
1.3 Literature Review on Mine Transportation Scheduling
Compared to mine design and mine production models, a limited amount of research interests focus on optimising mine transportation. Choi and Nieto (2011) propose a modified leastcost path algorithm for the optimal haulage routing of offroad dump trucks in construction and mining sites. Topal and Ramazan (2010) apply MIP to minimise maintenance cost of mining equipment such as trucks over a multiyear time horizon. Souza
et al. (2010) deal with an dynamic truck allocation problem. Using geographical information system (GIS), Choiet al. (2009) develop a model that combines multicriteria (speed, water body, orebody, curve, visibility, haul road maintenance) evaluation and leastcostpath analysis to determine the optimal haulage routes of dump trucks in large scale openpit mines.According to the above literature review, most research results in the literature concentrate on mine design (selection of blocks) models and mine production (sequencing of blocks) models, with the objective function of maximising the net present values. However, the decision variable in these models is binary that equals one if one block is mined in given periods or zero otherwise. In other words, these models cannot efficiently determine the timing elements (e.g., starting time, completion time and tardiness) of operations in an algorithmic way. Most mine transportation problems aim at minimising the equipment cost (e.g., trucks) of fleet management using planning algorithms such as leastcost path analysis. In realworld applications, mine transportation models should be tightly integrated with mine design and mine production problems to achieve the overall efficiency improvement. Therefore, the main purpose of this paper is to optimise the pitstocrushers mining operations and investigate an interactive framework of mine design planning, mine production sequencing and mine transportation scheduling for optimising these mining operations within a whole system.
2. MINING OPERATIONS FROM PITS TO CRUSHERS
According to our observations at the Australian iron ore mine sites, the practical overall flow process of openpit mining operations has been grouped as follows. In the first step, a set of blocks are selected by the mine design planning model. In the second step, the operation of vegetation clearing may be executed. After vegetation clearing, top soil is removed by loaders and trucks in the third step. In the fourth step, each block is drilled for the purpose to collect the blasting block samples. In the fifth step, the ore samples collected in drilling operations are sent to laboratories for checking the ore properties such as ingredients, grade and density. In the sixth step, the Mobile Processing Units (MPUs) provides leading explosive equipment and blasting services.
After blasting, the ore and waste rocks of a chosen subset of blocks in an openpit mine are excavated and transported by trucks to the crusher directly if it is high grade, or to blended stockpiles if it is low grade, or to the dump points if it is waste. The ore is then crushed in a semiautogenous grinding (SAG) mill in an open circuit. More details of the overall ore movement and processing procedure are described in Figure 1.
Thus, the following three types of models for mine design planning, mine production sequencing and mine transportation scheduling are developed and integrated to optimise the mining operations from pits to crushers. For better understanding, the brief description and definition of mine design planning, mine production sequencing and mine transportation scheduling are presented in the following sections.
2.1 Mine Design Planning Module
To design a pit, the entire volume is subdivided into blocks and the value of the ore in each block is estimated by geological information. Precedence relationships of blocks must be satisfied because they are the most critical constraints to specify slope requirements of the pit and to guarantee engineering feasibility requirements.
Figure 2(a) illustrates the precedence relationship of a 2D block model for mine design. In most cases, it is assumed that the pit slope cannot exceed 45 degree, which thus means that a block (block 1) cannot be mined until the one (block 2) located directly above it and its two immediate neighbours (blocks 3 and 4) have been removed. Obviously, the 3D block model is much more complicated than the 2D block model because of more complicated precedence relationships.
Figure 2(b) illustrates the precedence relations of a 3D block model, in which a block (block 5) cannot be extracted until the blocks (i.e., blocks 6, 7, 8, 9 and 10) on the level directly above and one of four blocks facing this block on the same level (i.e., one of four blocks directly under blocks 7, 8, 9 and 10) have been excavated.
Subject to these constraints, the objective is to determine the closed subset of blocks that maximise the net present value. Illustrated in Figure 3, the openpit mine design problem can be represented by a directed
network flow graph
G = (V, A ), whereV is a set of nodes (blocks) andA is a set of conjunctive arcs. Note that nodes of sink and source are dummy nodes.In this graph, precedence constraints determined by
A is equivalent to imposing the slope requirements. If blockj (e.g., node 6 in Figure 3) is extracted immediately before blocki (e.g., node 2), there is a conjunctive arc from nodei to nodej (e.g., a directed arc from node 2 to node 6). Each block corresponds to a node inV with a weightb_{j} representing the net value of an individual blockj . The value ofb_{j} is either positive or negative as it is the difference between ore value in this block and the cost of excavating this block. Thus, to decide which set of blocks are selected to be mined for maximising the net present value is equivalent to finding a subset of nodes leading to a maximum sum of block weights.The basic mine design planning problem has been modelled as a linear programming model as below.
Parameters V a set of nodes (blocks) in a directed network flow graph
A a set of conjunctive arcs in a directed network flow graph
bj weigh of node j that corresponds to block j
Decision variables xj a binary variable that is 1 if node j is chosen, and 0 otherwise.
Mathematical Formulation Constraint (2) ensures that if node
i is chosen, nodej should also be selected because of their precedence relationship. Constraint (3) requires that decision variables be binary values.As pioneers, Lerchs and Grossmann (1965) present to the mining community an algorithm to find the optimum design for an openpit mine. The planning of a mining program involves the design of the ultimate shape of this open surface. They show that an optimal solution of the mine design problem is equivalent to finding the maximum closure of a directed network flow graph model. Two numerical methods are proposed to determine the pit contour with the maximum profit: a simple dynamic programming algorithm for the 2D pit and a more complicated iterative algorithm (known as LerchsGrossmann algorithm) for the 3D pit.
More details about solution techniques for mine design planning models can be found at Lerchs and Grossmann (1965), Caccetta and Giannini (1998), Underwood and Tolwinski (1998) and Hochbaum and Chen (2000).
2.2 Mine Production Sequencing Module
After a given subset of blocks is selected by the mine design planning model, the purpose of mine production sequencing problem is to decide when they should be extracted over certain periods.
With regard to mine production sequencing, the MIP model proposed by Caccetta and Hill (2003) has been well known in mining industries and received considerable attention. The objective of this MIP model is to maximise the profits in certain periods over which the blocks are sequenced. The following constraints are considered in their MIP model: a block is removed in one period only; the precedence relationships between blocks are satisfied; the ore tonnage of each block equals milling capacity in each period; the amount of ore that is milled in each period is between the predetermined lower bound and upper bound values; the tonnage of waste removed does not exceed the prescribed upper bounds. The decision variable
is a binary variable that equals one if block
i is mined in periods from 1 tot ; and zero otherwise. However, this MIP model is not an accurate scheduling model in a rigorous sense because it cannot determine timing factors in an algorithmic way.According to our analysis, the cost functions are primarily reflected by timing factors (i.e., ready times, starting times, completion times, flowtimes, tardiness) of jobs in the sequencing/scheduling model. Thus, the objective of maximising the profits over a time horizon is equivalent to the objectives of minimising the maximum completion time, the mean weighted flowtime and the mean weighted tardiness if the due dates of each block are given.
Therefore, to solve the mine production sequencing problem in a more standard and convenient way, we are exploring to model it as a standard singlestage sequencing problem with special mining production constraints and cost functions.
The mathematical formulation model for a basic singlestage mine production sequencing problem is presented below.
Parameters J a set of n blocks to be mined; a block is equivalent to a job in this singlestage sequencing model.
rj release dates of job j, j ∈ J; equivalently it is the earliest available time of block j that is determined by the precedence relationships of blocks.
pj processing time of job j, j ∈ J; equivalently it is the mining time of block j.
dj due dates of job j, j ∈ J; equivalently it is the required finishing time of block j that is determined by the demand of a crusher mill.
wj weight of job j, j ∈ J; equivalently it is the ore value of block j.
L a sufficiently large number.
Decision variables Sj starting time of job j, j ∈ J; equivalently it is the time point when block j starts to be mined.
Cj completion time of job j, j ∈ J; equivalently it is the time point when block j has been mined and removed from a pit: Cj = Sj+Pj.
Cmax the maximum completion time or makespan: Cmax = maxj Cj.
Fj flowtime of job j, j ∈ J; equivalently it is the total amount time of block j that spends in the system: Fj = Cj  rj.
Tj tardiness of job j, j ∈ J; which is the lateness of block j if it fails to meet the due date, or zero otherwise: Tj = max {0, Cj  dj}.
xij a binary variable that is 1 if job i precedes job j or 0 otherwise.
Mathematical Formulation The objective of this mine production sequencing model is to minimise the total cost that is determined by a function associated with the maximum completion time, the weighted mean flow time and the weighted mean tardiness.
Equation (5) restricts that the completion time of each job should be no earlier than the makespan.
Equation (6) restricts that the starting time of each job should be greater than or equal to the release date.
Equations (7, 8) define the precedence relationship between any pair of jobs
i and jobj .Our proposed model will differ from the current mine production MIP sequencing models in the literature in accordance with the following distinct characteristics. Firstly, our proposed methodology for mine production sequencing problems is based on machine scheduling theory in the literature. Secondly, the objective functions of our proposed model are associated with the maximum completion time, the weighted mean flowtime or the weighted mean tardiness. Thirdly, the decision variables are timing factors such as starting times, completing times, flowtimes and tardiness. Fourthly, our proposed model is more flexible to be extended to deal with more complex scenarios in a standard way.
2.3 Mine Transportation Scheduling Module
Mine transportation problem could be modelled as a special type multiresource multistage scheduling model with a variety of mining constraints such as the limited number of trucks, the fixed transportation routes, etc.
Such a generic and sophisticated multiresource multistage scheduling model for optimising the transportation operations from pits to crushers is being proposed and analysed by an extended disjunctive graph model. The objective functions of this mine transportation scheduling problem are to minimise the maximum completion time or minimise the number of mining equipments in a time window.
In this disjunctive graph, the conjunctive arcs for the fixed production sequences of blocks in a pit are determined by the mine production sequencing module and the mine design planning module, as explained above. In addition, the other sets of conjunctive arcs are determined by the fixed bidirectional transportation routes (e.g., pit to stockpiles, pit to dump points, pit to crushers, stockpiles to pit, dump points to pit, crushers to pit). The transportation routes could be determined by the shortest path (or leastcostpath) algorithm with the help of GIS and the analysis of planning network graph.
To build the feasible mine transportation scheduling model, the output results of mine design planning model and mine production sequencing model are very important as they are used as the input data to set up the conjunctive arcs for this disjunctive graph model. As a result, this multiresource multistage scheduling model must incorporate the results of the mine design planning problem and mine production sequencing problem with the development of an extended disjunctive graph model.
The definition of disjunctive arcs is also important to determine the feasible solution of mine transportation. In a sense, determining a schedule corresponds with selecting one direction for each pair of disjunctive arcs and discarding the redundant arcs so that obtained schedule leads to the optimal objective function value. The details of mine transportation scheduling will be reported in another paper.
3. INTERACTIVE MINING OPTIMISATION FRAMEWORK
For improving the overall efficiency of ore mining systems, an interactive optimisation framework for mining industry is proposed in this paper. This framework has an interactive mechanism that allows interactive feedback among the mine design planning, mine production sequencing and mine transportation scheduling modules. This feedback mechanism enables the optimisation process to go through several iterations, for the purpose of supporting better decision makings and improving the solution quality by updating input data interactively.
To construct this framework, the first important thing is to clearly distinguish mine design planning, mine production sequencing and mine transportation scheduling. In the literature, mine design planning and mine production sequencing problems are easy to be confused. The mine design problem is a “
planning ” problem because it doesn’t need to sequence the blocks over time periods. Moreover, most researchers misuse the term “scheduling ” for midterm mine production sequencing problems. In the literature, the solution of most mine production problems is a sequence of blocks to be mined over time periods. In fact, many of mine production problems (eg., Caccetta and Hill, 2003; Razaman, 2007; Bolandet al. , 2009; Bleyet al. , 2010) are the sequencing models, because they do not determine detailed timing elements (e.g., starting time, flowtime, completion time and tardiness) in an algorithmic way.According to sequencing and scheduling theory (Baker, 1974), “the pure sequencing problem is a specialised scheduling problem in which an ordering of the jobs completely determines a schedule” (see the first sentence in Page 10, “
Introduction to Sequencing and Scheduling ”). The basic pure sequencing problem is called singlestage sequencing with independent jobs in which there is only a single resource (machine) and each job consists of only one operation. The total number of distinct solutions to this basic singlestage sequencing problem isn !, which is the number of different permutations ofn elements (jobs). In comparison, the total number of distinct solutions to basic multiresource multistage scheduling problem is (n !)^{m}, wherem is the number of resources.Within the proposed interactive planning and scheduling framework, mine design planning problems differ from mine production sequencing/mine transportation scheduling problems in numerous ways.
Firstly, time horizons of most mine design planning problems are longterm or longrange. In contrast, mine production sequencing models are usually defined over a midterm time horizon. In a longterm time horizon that is commonly over two years, the mining industry would be interested in making strategic decisions whether to explore a mine and how to determine the contours (block models) of this mine to maximise the longterm net present value. In contrast, midterm time horizon for mine production usually has a time frame of three months to two years. From a tactical viewpoint, the mine industry commonly needs to aggregate the production targets by selecting the set of blocks (benches) to be mined in this midterm horizon for satisfying midterm export demands. The decisions made by mine transportation scheduling models are operational decisions in a shortterm horizon. As such, these daytoday decisions tend to be of the very specific focus on narrow entities over short time intervals.
Secondly, mine design planning is mainly concerned about the optimum selection of blocks’ subsets in a pit and allocating the limited resources for minimising total costs. The unit measured in planning decision variables is often a cost unit. In comparison, the objective of mine production models is fundamentally associated with the functions of completion times of the jobs and the unit measured in decision variables is often a time unit.
Thirdly, most mine design planning problems are simplified and modelled as a linear programming model or nonlinear programming model, while most mine production sequencing/mine transportation scheduling models include more real life constraints and real time elements and they are usually NPhard.
Finally, for most mine sequencing/scheduling problems, the scope is considerably narrower with regard to time as well as space, but the level of details taken into considerations is much higher.
Under various practical circumstances, there may be a specified reason necessitating a feedback between planning, sequencing and scheduling modules. For example, a disruption in the mine design planning module (e.g., cancellation of some selected blocks to be mined due to volatile demands) may be of such magnitude that it not only affects its facility (e.g., a pit) where it occurs and other facilities (e.g., stockpiles and crushers) as well. In this situation, the results of shortterm mine transportation scheduling module may further indicate that the data from the output of longterm mine design planning or midterm mine production sequencing modules may turn to imprecise or inaccurate. As a result, the original mine design planning or mine production sequencing procedures may need to be updated and reconstructed in an interactive way.
A generic framework with a feedback mechanism, which allows the overall mine planning and sequencing/ scheduling processes (i.e., mine design planning, mine production sequencing and mine transportation scheduling) to regularly communicate and iterate, is elucidated in Figure 4.
In such a framework, the output results of the longterm mine design planning model could serve as the input data to the midterm mine production sequencing process. The output results of mine production sequencing model could be applied as the input data to the mine transportation scheduling model. Obviously, such an interaction between a mine planning module and a mine scheduling module may be sophisticated in realworld scenarios. However, they are able to be integrated, share information and interact reactively with one another.
The proposed interactive mining optimisation framework has many merits:
i) it is flexible to adopt other optimisation modules and consider as many realistic constraints as possible (e.g., maintenance activities, etc);ii) it is applicable to optimise a very complicated system by decomposing into several interdependent simplified optimisation modules;iii) it is straightforward to be understood and applied by the mining industry practitioners.4. CONCLUSIONS
In this paper, an interactive framework is proposed for optimising the operations from pits to crushers in ore mining industry. Under this framework, the mine design planning problem, the mine production sequencing problem and the mine transportation scheduling problem are investigated and integrated within a whole mining optimisation system. The mine design planning problem can be modelled as a linear programming model or a directed network flow graph model and solved by traditional solution techniques such as LerchsGrossman algorithm or the maximum flow algorithm. A new mine production sequencing model is proposed, which is based on singlestage sequencing theory with special mining production constraints and associated cost functions. This approach is different from most current mine production MIP sequencing models in the literature. Using the results of longterm mine design planning and midterm mine production sequencing as input data, a complicated multiresource multistage scheduling model is developed and analysed by an extended disjunctive graph for optimising the shortterm truck transportation operations from pits to crushers.
In the direction of future study, the collection of realworld data, the development of integrated solution algorithms and the implementations in realistic mine sites are essential to validate the proposed methodology.

[Figure 1.] Flow Diagram of Ore Processing Operations.

[Figure 2.] Illustration of Precedence Relationship between a Block and Its Immediate Predecessors.

[Figure 3.] A Directed Network Flow Graph for Mine Design Planning.

[Figure 4.] An Interactive Mining Optimisation Framework.