A heuristic approach for the stochastic optimization of mine production schedules

Traditionally, mining engineers plan an open pit mine considering pre-established conditions of operation of the plant(s) derived from a previous plant optimization. By contrast, mineral processing engineers optimize the processing plants by considering a regular feed from the mine, with respect to quantity and quality of the materials. The methods implemented to optimize mine and metallurgical plans simultaneously are known in the mining industry as global or simultaneous optimizers. The development of these methods has been of major concern for the mining industry over the last decade. Some algorithms are available in commercial mining software packages however, these algorithms ignore the inherent geological uncertainty associated with the deposit being considered, which leads to shortfalls in production, quality, and expected cashflows. This paper presents a heuristic method to generate life-of-mine production schedules that consider operating alternatives for processing plants and incorporate geological uncertainty. The method uses iterative improvement by swapping periods and destinations of the mining blocks to generate the final solution. The implementation of the method at a copper deposit shows its ability to control mine and processing capacities while increasing the expected net present value by 30% when compared with a solution generated using a standard industry practice.     

Optimization-based heuristics for underground mine scheduling

Underground mine production scheduling possesses mathematical structure similar to and yields many of the same challenges as general scheduling problems. That is, binary variables represent the time at which various activities are scheduled. Typical objectives seek to minimize costs or some measure of production time, or to maximize net present value; two principal types of constraints exist: (i) resource constraints and (ii) precedence constraints. In our setting, we maximize “discounted metal production” for the remaining life of an underground lead and zinc mine that uses three different underground methods to extract the ore. Resource constraints limit the grade, tonnage, and backfill paste (used for structural stability) in each time period, while precedence constraints enforce the sequence in which extraction (and backfill) is performed in accordance with the underground mining methods used. We tailor exact and heuristic approaches to reduce model size, and develop an optimization-based decomposition heuristic; both of these methods transform a computationally intractable problem to one for which we obtain solutions in seconds, or, at most, hours for problem instances based on data sets from the Lisheen mine near Thurles, Ireland.     

The new Fundamental Tree Algorithm for production scheduling of open pit mines

The problem of annual production scheduling in surface mining consists of determining an optimal sequence of extracting the mineralized material from the ground. The main objective of the optimization process is usually to maximize the total Net Present Value of the operation. Production scheduling is typically a mixed integer programming (MIP) type problem. However, the large number of integer variables required in formulating the problem makes it impossible to solve. To overcome this obstacle, a new algorithm termed “Fundamental Tree Algorithm” is developed based on linear programming to aggregate blocks of material and decrease the number of integer variables and the number of constraints required within the MIP formulation. This paper proposes the new Fundamental Tree Algorithm in optimizing production scheduling in surface mining. A case study on a large copper deposit summarized in the paper shows substantial economic benefit of the proposed algorithm compared to existing methods.     

Implementing a parametric maximum flow algorithm for optimal open pit mine design under uncertain supply and demand

Conventional open pit mine optimization models for designing mining phases and ultimate pit limit do not consider expected variations and uncertainty in metal content available in a mineral deposit (supply) and commodity prices (market demand). Unlike the conventional approach, a stochastic framework relies on multiple realizations of the input data so as to account for uncertainty in metal content and financial parameters, reflecting potential supply and demand. This paper presents a new method that jointly considers uncertainty in metal content and commodity prices, and incorporates time-dependent discounted values of mining blocks when designing optimal production phases and ultimate pit limit, while honouring production capacity constraints. The structure of a graph representing the stochastic framework is proposed, and it is solved with a parametric maximum flow algorithm. Lagragnian relaxation and the subgradient method are integrated in the proposed approach to facilitate producing practical designs. An application at a copper deposit in Canada demonstrates the practical aspects of the approach and quality of solutions over conventional methods, as well as the effectiveness of the proposed stochastic approach in solving mine planning and design problems.     

An Application of Branch and Cut to Open Pit Mine Scheduling

The economic viability of the modern day mine is highly dependent upon careful planning and management. Declining trends in average ore grades, increasing mining costs and environmental considerations will ensure that this situation will remain in the foreseeable future. The operation and management of a large open pit mine having a life of several years is an enormous and complex task. Though a number of optimization techniques have been successfully applied to resolve some important problems, the problem of determining an optimal production schedule over the life of the deposit is still very much unresolved. In this paper we will critically examine the techniques that are being used in the mining industry for production scheduling indicating their limitations. In addition, we present a mixed integer linear programming model for the scheduling problems along with a Branch and Cut solution strategy. Computational results for practical sized problems are discussed.     

Using aggregation to optimize long-term production planning at an underground mine

Motivated by an underground mining operation at Kiruna, Sweden, we formulate a mixed integer program to schedule iron ore production over multiple time periods. Our optimization model determines an operationally feasible ore extraction sequence that minimizes deviations from planned production quantities. The number of binary decision variables in our model is large enough that directly solving the full, detailed problem for a three year time horizon requires hours, or even days. We therefore design a heuristic based on solving a smaller, more tractable, model in which we aggregate time periods, and then solving the original model using information gained from the aggregated model. We compute a bound on the worst case performance of this heuristic and demonstrate empirically that this procedure produces good quality solutions while substantially reducing computation time for problem instances from the Kiruna mine.     

A sliding time window heuristic for open pit mine block sequencing

The open pit mine block sequencing problem (OPBS) seeks a discretetime production schedule that maximizes the net present value of the orebody extracted from an open-pit mine. This integer program (IP) discretizes the mine’s volume into blocks, imposes precedence constraints between blocks, and limits resource consumption in each time period. We develop a “sliding time window heuristic” to solve this IP approximately. The heuristic recursively defines, solves and partially fixes an approximating model having: (i) fixed variables in early time periods, (ii) an exact submodel defined over a “window” of middle time periods, and (iii) a relaxed submodel in later time periods. The heuristic produces near-optimal solutions (typically within 2% of optimality) for model instances that standard optimization software fails to solve. Furthermore, it produces these solutions quickly, even though our OPBS model enforces standard upper-bounding constraints on resource consumption along with less standard, but important, lower-bounding constraints.     

Robust Planning for an Open-Pit Mining Problem under Ore-Grade Uncertainty

Open-pit mining production planning is a risky problem: operation costs are considerable, many parameters are inherently subject to uncertainty and, moreover, the mining operation can only be done once. In this work we address uncertainty in the ore-grade, where we only assume the availability of an i.i.d. sample of the joint distribution of ore-grade in the blocks of the mining site. We consider an open-pit mining problem involving extraction and processing decisions under capacity constraints. We apply and compare the risk-hedging performance of three approaches for optimization under uncertainty: Value-at-Risk, Conditional Value-at-Risk and a proposed robust optimization approach. The latter is shown to have desirable risk-averse properties. Computational results on one small size vein-type mine are shown.     

CORO,a modeling and an algorithmic framework for oil supply,transformation and distribution optimization under uncertainty

We present a modeling framework for the optimization of a multiperiod Supply, Transformation and Distribution (STD) scheduling problem under uncertainty on the product demand, spot supply cost and spot selling price. The Hydrocarbon and Chemical sector has been chosen as the pilot area, but the approach has a far more reaching application. A deterministic treatment of the problem provides unsatisfactory results. We use a 2-stage scenario analysis based on a partial recourse approach, where the STD policy can be implemented for a given set of initial time periods, such that the solution for the other periods does not need to be anticipated and, then, it depends on the scenario to occur. In any case, it takes into consideration all the given scenarios. Novel schemes are presented for modeling multiperiod linking constraints, such that they are satisfied through the scenario tree; they are modeled by using a splitting variable scheme, via a reduntant circular linking representation.     

A variable neighbourhood descent algorithm for the open-pit mine production scheduling problem with metal uncertainty

Uncertainty is an inherent aspect of the open-pit mine production scheduling problem (MPSP); however, little is reported in the literature about solution methods for the stochastic versions of the problem. In this paper, two variants of a variable neighbourhood descent algorithm are proposed for solving the MPSP with metal uncertainty. The proposed methods are tested and compared on actual large-scale instances, and very good solutions, with an average deviation of less than 3% from optimality, are obtained within a few minutes up to a few hours.     

A two-stage stochastic program for scheduling and allocating cross-trained workers

A two-stage stochastic program is developed for scheduling and allocating cross-trained workers in a multi-department service environment with random demands. The first stage corresponds to scheduling days-off over a time horizon such as a week or month. The second stage is the recourse action that deals with allocating available workers at the beginning of a day to accommodate realized demands. After the general two-stage model is formulated, a special case is introduced for computational testing. The testing helps quantify the value of cross-training as a function of problem characteristics. Results show that cross-training can be more valuable than perfect information, especially when demand uncertainty is high.     

Schumann,a modeling framework for supply chain management under uncertainty

We present a modeling framework for the optimization of a manufacturing, assembly and distribution (MAD) supply chain planning problem under uncertainty in product demand and component supplying cost and delivery time, mainly. The automotive sector has been chosen as the pilot area for this type of multiperiod multiproduct multilevel problem, but the approach has a far more reaching application. A deterministic treatment of the problem provides unsatisfactory results. We use a 2-stage scenario analysis based on a partial recourse approach, where MAD supply chain policy can be implemented for a given set of initial time periods, such that the solution for the other periods does not need to be anticipated and, then, it depends on the scenario to occur. In any case, it takes into consideration all the given scenarios. Very useful schemes are used for modeling balance equations and multiperiod linking constraints. A dual approach splitting variable scheme is been used for dealing with the implementable time periods related variables, via a redundant circular linking representation.     

A fuzzy goal programming approach to integrated loading and scheduling of a batch processing machine

This paper concerns a real-life problem of loading and scheduling a batch-processing machine. The integrated loading and scheduling problem is stated as a multicriteria optimization problem where different types of objectives are included: (1) short-term objectives of relevance to the shop floor, such as throughput maximization and work-in-process inventory minimization, and (2) long-term objectives such as balancing of end product inventory levels and meeting financial targets imposed by the higher production planning level. Two types of uncertainty are considered: (1) uncertainty inherent in loading and scheduling objective targets (goals) such as the allocated budget and end product demand, and (2) uncertainty in importance relations among the objectives. These two types of uncertainty are modelled using fuzzy sets and fuzzy relations, respectively. A fuzzy goal programming model and the corresponding method are developed which handle both fuzzy and crisp goals and fuzzy importance relations among the goals. Numerical examples are given to illustrate the effectiveness of the developed model.     

MineLib: a library of open pit mining problems

Similar to the mixed-integer programming library (MIPLIB), we present a library of publicly available test problem instances for three classical types of open pit mining problems: the ultimate pit limit problem and two variants of open pit production scheduling problems. The ultimate pit limit problem determines a set of notional three-dimensional blocks containing ore and/or waste material to extract to maximize value subject to geospatial precedence constraints. Open pit production scheduling problems seek to determine when, if ever, a block is extracted from an open pit mine. A typical objective is to maximize the net present value of the extracted ore; constraints include precedence and upper bounds on operational resource usage. Extensions of this problem can include (i) lower bounds on operational resource usage, (ii) the determination of whether a block is sent to a waste dump, i.e., discarded, or to a processing plant, i.e., to a facility that derives salable mineral from the block, (iii) average grade constraints at the processing plant, and (iv) inventories of extracted but unprocessed material. Although open pit mining problems have appeared in academic literature dating back to the 1960s, no standard representations exist, and there are no commonly available corresponding data sets. We describe some representative open pit mining problems, briefly mention related literature, and provide a library consisting of mathematical models and sets of instances, available on the Internet. We conclude with directions for use of this newly established mining library. The library serves not only as a suggestion of standard expressions of and available data for open pit mining problems, but also as encouragement for the development of increasingly sophisticated algorithms.     

Equipment selection with heterogeneous fleets for multiple-period schedules

In a simple surface mining scenario we consider a mine to have one mining location and dumpsite connected by a truck route. We determine a purchase and salvage policy for trucks and loaders, which minimises the cost of materials handling over a multiple period schedule. This problem becomes large scale when we consider large sets of equipment and long schedules. Pre-existing equipment can lead to heterogeneous fleets; non-uniformity in the operating cost function coupled with compatibility issues also adds to the complexity of the problem. We present an integer programme for this problem, where we introduce a specialised linear constraint set to ensure satisfaction of production requirements while accounting for equipment compatibility. Many aspects of the presented model, such as the consideration of multiple periods and pre-existing equipment, are novel for the mining industry and ensure that the model is both a new and advanced equipment selection tool.     

On solving stochastic production planning problems via scenario modelling

Summary Linear Porgramming models for stochastic planning problems and a methodology for solving them are proposed. A production planning problem with uncertainty in demand is used as a test case, but the methodology presented here is applicable to other types of problems as well. In these models, uncertainty in demand is characterized via scenarios. Solutions are obtained for each scenario and then these individual scenario solutions are aggregated to yield an implementable non-anticipative policy. Such an approach makes it possible to model correlated and nonstationary demand as well as a variety of recourse decision types. For computational purposes, two alternative representations are proposed. A compact approach that is suitable for the Simplex method and a splitting variable approach that is suitable for the Interior Point Methods. A crash procedure that generates an advanced starting solution for the Simplex method is developed. Computational results are reported with both the representations. Although some of the models presented here are very large (over 25000 constraints and 75000 variables), our computational experience with these problems is quite encouraging.     

Iron ore production scheduling to improve product quality

Iron ore quality depends upon successive shipments being uniform in composition, not only in iron but also in several other minerals. The production process involves several stages of scheduling, from the mine face, through railing, stockpiling and ship loading. At each of these stages there is potential to improve the composition uniformity through appropriate scheduling procedures. This paper discusses a variety of algorithms and simulation models developed to aid these scheduling decisions.     

A column generation algorithm for tactical timber transportation planning

We present a tactical wood flow model that appears in the context of the Canadian forestry industry, and describe the implementation of a decision support system created for use by an industrial partner. In this problem, mill demands and harvested volumes of a heterogeneous set of log types are given over a multi-period planning horizon. Wood can be stored at the forest roadside before delivery at a financial cost. Rather than solve this as a network linear programme on the basis of out-and-back deliveries, we choose to model this problem as a generalization of a log-truck scheduling problem. By routing and scheduling the trucks in the resolution, this allows us to both anticipate potential backhaul opportunities for cost and fuel savings, and also minimize queuing times at log-loaders, management of which is a major concern in the industry. We model this problem as a mixed integer linear programme and solve it via column generation. The methodology is tested on several case studies.     

Solving project scheduling problem with the philosophy of fuzzy random programming

Project scheduling problem is to determine the schedule of allocating resources to achieve the trade-off between the project cost and the completion time. In real projects, the trade-off between the project cost and the completion time, and the uncertainty of the environment are both considerable aspects for managers. Due to the complex external environment, this paper considers project scheduling problem with coexisted uncertainty of randomness and fuzziness, in which the philosophy of fuzzy random programming is introduced. Based on different ranking criteria of fuzzy random variables, three types of fuzzy random models are built. Besides, a searching approach by integrating fuzzy random simulations and genetic algorithm is designed for searching the optimal schedules. The goal of the paper is to provide a new method for solving project scheduling problem in hybrid uncertain environments.