A New Algorithm for the Open-Pit Mine Production Scheduling Problem
Artículo

Open/ Download
Publication date
2012Metadata
Show full item record
Cómo citar
Chicoisne, Renaud
Cómo citar
A New Algorithm for the Open-Pit Mine Production Scheduling Problem
Author
Abstract
For the purpose of production scheduling, open-pit mines are discretized into three-dimensional arrays known as block
models. Production scheduling consists of deciding which blocks should be extracted, when they should be extracted, and
what to do with the blocks once they are extracted. Blocks that are close to the surface should be extracted first, and
capacity constraints limit the production in each time period. Since the 1960s, it has been known that this problem can be
cast as an integer programming model. However, the large size of some real instances (3–10 million blocks, 15–20 time
periods) has made these models impractical for use in real planning applications, thus leading to the use of numerous
heuristic methods. In this article we study a well-known integer programming formulation of the problem that we refer to
as C-PIT. We propose a new decomposition method for solving the linear programming relaxation (LP) of C-PIT when
there is a single capacity constraint per time period. This algorithm is based on exploiting the structure of the precedenceconstrained
knapsack problem and runs in O4mnlog n5 in which n is the number of blocks and m a function of the
precedence relationships in the mine. Our computations show that we can solve, in minutes, the LP relaxation of real-sized
mine-planning applications with up to five million blocks and 20 time periods. Combining this with a quick rounding
algorithm based on topological sorting, we obtain integer feasible solutions to the more general problem where multiple
capacity constraints per time period are considered. Our implementation obtains solutions within 6% of optimality in
seconds. A second heuristic step, based on local search, allows us to find solutions within 3% in one hour on all instances
considered. For most instances, we obtain solutions within 1–2% of optimality if we let this heuristic run longer. Previous
methods have been able to tackle only instances with up to 150,000 blocks and 15 time periods.
Quote Item
OPERATIONS RESEARCH Vol. 60, No. 3, May–June 2012, pp. 517–528
Collections