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

Renaud Chicoisne (), Daniel Espinoza (), Marcos Goycoolea (), Eduardo Moreno () and Enrique Rubio ()
Additional contact information
Renaud Chicoisne: Department of Industrial Engineering, Universidad de Chile, 8370439 Santiago, Chile
Daniel Espinoza: Department of Industrial Engineering, Universidad de Chile, 8370439 Santiago, Chile
Marcos Goycoolea: School of Business, Universidad Adolfo Ibañez, 7941169 Santiago, Chile
Eduardo Moreno: Faculty of Engineering and Sciences, Universidad Adolfo Ibañez, 7941169 Santiago, Chile
Enrique Rubio: Department of Mining Engineering and Advanced Mining Technology Center, Universidad de Chile, 8370439 Santiago, Chile

Operations Research, 2012, vol. 60, issue 3, 517-528

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 precedence-constrained knapsack problem and runs in O ( mn log n ) 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.

Keywords: open-pit mining; optimization; mixed integer programming (search for similar items in EconPapers)
Date: 2012
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (38)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.1120.1050 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:60:y:2012:i:3:p:517-528

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().