Improvement of Lagrangian relaxation performance for open pit mines constrained long-term production scheduling problem

Abstract

Constrained long-term production scheduling problem (CLTPSP) of open pit mines has been extensively studied in the past few decades due to its wide application in mining projects and the computational challenges it poses become an NP-hard problem. This problem has major practical significance because the effectiveness of the schedules obtained has strong economical impact for any mining project. Despite of the rapid theoretical and technical advances in this field, heuristics is still the only viable approach for large scale industrial applications. This work presents an approach combining genetic algorithms (GAs) and Lagrangian relaxation (LR) to optimally determine the CLTPSP of open pit mines. GAs are stochastic, parallel search algorithms based on the natural selection and the process of evolution. LR method is known for handling large-scale separable problems; however, the convergence to the optimal solution can be slow. The proposed Lagrangian relaxation and genetic algorithms (LR-GAs) combines genetic algorithms into Lagrangian relaxation method to update the Lagrangian multipliers. This approach leads to improve the performance of Lagrangian relaxation method in solving CLTPSP. Numerical results demonstrate that the LR method using GAs to improve its performance speeding up the convergence. Subsequently, highly near-optimal solution to the CLTPSP can be achieved by the LR-GAs.

Keywords

constrained long-term production scheduling problem / open pit mine / Lagrangian relaxation / genetic algorithm

References

[1] JohnsonT BOptimum open pit mine production scheduling [D], 1968, Berkeley, Operations Research Department, University of California, Berkeley: 539-562

[2] KingB. Optimal mining practice in strategic planning [J]. Journal of Mining Science, 2011, 47(2): 247-253

[3] GershonM E. Optimal mine production scheduling: Evaluation of large scale mathematical programming approaches [J]. International Journal of Mining Engineering, 1983, 1(4): 315-329

[4] DagdelenKOptimum multi-period open pit mine production scheduling [D], 1985, Colorado, Colorado School of Mines, Golden

[5] DagdelenK, JohnsonT B. Optimum open pit mine production scheduling by Lagrangian parameterization [C]. 19th Application of Computers and Operations Research in the Mineral Industry, 1986, Philadelphia, Pennsylvania State University: 127-142

[6] AkaikeA, DagdelenK. A strategic production scheduling method for an open pit mine [C]. Proceedings of the 28th Application of Computers and Operation Research in the Mineral Industry, 1999, Colorado, Colorado School of Mines, Golden: 729-738

[7] MogiG, AdachiT, AkaikeA, YamatomiJ. Optimum production scale and scheduling of open pit mines using revised 4D network relaxation method [C]. Proceedings of the 17th International Symposium on Mine Planning and Equipment Selection, New Delhi, 2001337-344

[8] BolandN, DumitrescuI, FroylandG, GleixnerA M. LP-based disaggregation approaches to solving the open pit mining production scheduling problem with block processing selectivity [J]. Computer Operation Research, 2009, 36(4): 1064-1089

[9] GleixnerASolving large-scale open pit mining production scheduling problems by integer programming programming [D], 2008, Berlin, Technische Universität Berlin

[10] ElevliB. Open pit mine design and extraction sequencing by use of OR and AI concept [J]. Int J Surf Mining Reclam Environ, 1995, 9: 149-153

[11] BoucherA, DimitrakopoulosR. Multivariate block block-support simulation of the Yandi iron ore deposit, Western Australia [J]. Mathematical Geosciences, 2012, 44(4): 449-468

[12] ZhangM. Combination genetic algorithms and topological sort to optimize open-pit mine plans [C]. In 15th Mine Planning and Equipment Selection. Torino, Italy, 20061234-1239

[13] GuX-w, WangQ, ChuD-z, ZhangBin. Dynamic optimization of cutoff grade in underground metal mining [J]. Journal of Central South University of Technology, 2010, 17: 492-497

[14] BleyA, BolandN, FrickeC, FroylandG. A strengthened formulation and cutting planes for the open pit mine production scheduling problem [J]. Computer Operation Research, 2010, 37(9): 1641-1647

[15] TabeshM, Askari-NasabH. Two-stage clustering algorithm for block aggregation in open pit mines [J]. Mining Technology, 2011, 120: 158-169

[16] EpsteinR, GoicM, WeintraubA, CatalanJ, SantibanezP, UrrutiaR, CancinoR, GaeteS, AguayoA, CaroF. Optimizing long-term production plans in underground and open-pit copper mines [J]. Operation Research, 2012, 60(1): 4-17

[17] LamghariA, DimitrakopoulosR. A diversified Tabu search approach for the open-pit mine production scheduling problem with metal uncertainty [J]. European Journal of Operational Research, 2012, 222(3): 642-652

[18] AsadM, DimitrakopoulosR. A heuristic approach to stochastic cutoff grade optimization for open pit mining complexes with multiple processing streams [J]. Resources Policy, 2013, 38(4): 591-597

[19] PourrahimianY, Askari-NasabH, TannantD. A multi-step approach for block-cave production scheduling optimization [J]. International Journal of Mining Science and Technology, 2013, 23(5): 739-750

[20] EspinozaD, GoycooleaM, MorenoE, NewmanA. MineLib: A library of open pit mining problems [J]. Annals of Operations Research, 2013, 206(1): 93-114

[21] NewmanA, RubioE, CaroR, WeintraubA, EurekK. A review of operation research in mine planning [J]. Interface, 2010, 40(3): 222-245

[22] JungerM, LieblingT, NaddefD, NemhauserG, PulleyblankW, ReineltG, RinaldiG, WolseyL50 Years of Integer Programming 1958–2008 [M], 2010, Berlin, Springer: 619-645

[23] HeldM, WolfeP, CrowderH. Validation of Sub-gradient Optimization [J]. Mathematical Programming, 1974, 6: 62-88

[24] GoldbergD EGenetic algorithms in search, optimization, and machine learning [M], 1989, Ontario, Addison, Wesley Publishing Company, Inc: 412

[25] MagdaR. Modelling the mine production process in terms of planning the output volume with regard to the aspects of uncertainty and risk [J]. Mineral Resources Management (Gospodarka Surowcami Mineralnymi), 2011, 27(4): 45-57

[26] FisherM L. The Lagrangian relaxation method for solving integer programming problems [J]. Management Science, 1981, 27(1): 1-18

[27] HollandJ HAdaptation in natural and artificial systems [M], 19922nd ed.Cambridge, MA, MIT Press: 211

[28] GholamnejadJ, MoosaviE. A new mathematical programming model for long-term production scheduling considering geological uncertainty [J]. Journal of the Southern African Institute of Mining and Metallurgy, 2012, 112(2): 77-81

[29] HoffmanKL, RalphsTKInteger and combinatorial optimization [R], 2013

[30] AkaikeAStrategic planning of Long term production schedule using 4D network relaxation method [D], 1999, Colorado, Colorado school of mines, Golden