Optimization strategies for resource-constrained project scheduling problems in underground mining. (English) Zbl 1505.90058
Summary: Effective computational methods are important for practitioners and researchers working in strategic underground mine planning. We consider a class of problems that can be modeled as a resource-constrained project scheduling problem with optional activities; the objective maximizes net present value. We provide a computational review of math programming and constraint programming techniques for this problem, describe and implement novel problem-size reductions, and introduce an aggregated linear program that guides a list scheduling algorithm running over unaggregated instances. Practical, large-scale planning problems cannot be processed using standard optimization approaches. However, our strategies allow us to solve them to within about 5% of optimality in several hours, even for the most difficult instances.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
Keywords:
underground mine planning; resource-constrained project scheduling; constraint programming; mathematical programmingReferences:
| [1] | Artigues C (2017) On the strength of time-indexed formulations for the resource-constrained project scheduling problem. Oper. Res. Lett. 45(2):154-159.Crossref, Google Scholar · Zbl 1409.90085 · doi:10.1016/j.orl.2017.02.001 |
| [2] | Artigues C, Demassey S, Néron E (2008) Resource-Constrained Project Scheduling: Models, Algorithms, Extensions and Applications (Wiley, New York).Crossref, Google Scholar · doi:10.1002/9780470611227 |
| [3] | Baptiste P, Le Pape C, Nuijten W (2012) Constraint-Based Scheduling: Applying Constraint Programming to Scheduling Problems (Springer, New York).Google Scholar |
| [4] | Berthold T, Heinz S, Lübbecke M, Möhring R, Schulz J (2010) A constraint integer programming approach for resource-constrained project scheduling. Lodi A, Milano M, Toth P, eds. Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (Springer, Berlin), 313-317.Crossref, Google Scholar · Zbl 1285.90045 · doi:10.1007/978-3-642-13520-0_34 |
| [5] | Bienstock D, Zuckerberg M (2010) Solving LP relaxations of large-scale precedence constrained problems. Eisenbrand F, Shepherd FB, eds. International Conference on Integer Programming and Combinatorial Optimization (Springer, Berlin), 1-14.Crossref, Google Scholar · Zbl 1285.90006 · doi:10.1007/978-3-642-13036-6_1 |
| [6] | Blazewicz J, Lenstra JK, Kan AR (1983) Scheduling subject to resource constraints: Classification and complexity. Discrete Appl. Math. 5(1):11-24.Crossref, Google Scholar · Zbl 0516.68037 · doi:10.1016/0166-218X(83)90012-4 |
| [7] | Brickey A (2015) Underground production scheduling optimization with ventilation constraints. Unpublished doctoral dissertation, Colorado School of Mines, Golden, CO.Google Scholar |
| [8] | Brickey A, Chowdu A, Newman A, Goycoolea M, Godard R (2021) Barrick’s Turquoise Ridge gold mine optimizes underground production scheduling operations. INFORMS J. Appl. Analytics 51(2):106-118.Link, Google Scholar |
| [9] | Brucker P, Drexl A, Möhring R, Neumann K, Pesch E (1999) Resource-constrained project scheduling: Notation, classification, models, and methods. Eur. J. Oper. Res. 112(1):3-41.Crossref, Google Scholar · Zbl 0937.90030 · doi:10.1016/S0377-2217(98)00204-5 |
| [10] | Carrasco RA, Iyengar G, Stein C (2013) Single machine scheduling with job-dependent convex cost and arbitrary precedence constraints. Oper. Res. Lett. 41(5):436-441.Crossref, Google Scholar · Zbl 1286.90053 · doi:10.1016/j.orl.2013.05.008 |
| [11] | Carrasco RA, Iyengar G, Stein C (2018) Resource cost aware scheduling. Eur. J. Oper. Res. 269(2):621-632.Crossref, Google Scholar · Zbl 1388.90051 · doi:10.1016/j.ejor.2018.02.059 |
| [12] | Carvajal R, Ahmed S, Nemhauser G, Furman K, Goel V, Shao Y(2014) Using diversification, communication and parallelism to solve mixed-integer linear programs. Oper. Res. Lett. 42(2):186-189.Crossref, Google Scholar · Zbl 1408.90194 · doi:10.1016/j.orl.2013.12.012 |
| [13] | Cherkassky B, Goldberg A (1997) On implementing the push-relabel method for the maximum flow problem. Algorithmica 19(4):390-410.Crossref, Google Scholar · Zbl 0898.68029 · doi:10.1007/PL00009180 |
| [14] | Chicoisne R, Espinoza D, Goycoolea M, Moreno E, Rubio E (2012) A new algorithm for the open-pit mine production scheduling problem. Oper. Res. 60(3):517-528.Link, Google Scholar · Zbl 1260.90087 |
| [15] | Chowdu A, Nesbitt P, Brickey A, Newman A (2022) Operations research in underground mine planning: A review. INFORMS J. Appl. Analytics 52(2):109-132.Link, Google Scholar |
| [16] | Christofides N, Alvarez-Valdés R, Tamarit J (1987) Project scheduling with resource constraints: A branch and bound approach. Eur. J. Oper. Res. 29(3):262-273.Crossref, Google Scholar · Zbl 0614.90056 · doi:10.1016/0377-2217(87)90240-2 |
| [17] | Danna E, Rothberg E, Le Pape C (2005) Exploring relaxation induced neighborhoods to improve MIP solutions. Math. Programming 102(1):71-90.Crossref, Google Scholar · Zbl 1131.90036 · doi:10.1007/s10107-004-0518-7 |
| [18] | De Azevedo GHI, Pessoa AA, Subramanian A (2021) A satisfiability and workload-based exact method for the resource constrained project scheduling problem with generalized precedence constraints. Eur. J. Oper. Res. 289(3):809-824.Crossref, Google Scholar · Zbl 1487.90285 · doi:10.1016/j.ejor.2019.07.056 |
| [19] | Debels D, Vanhoucke M (2007) A decomposition-based genetic algorithm for the resource-constrained project-scheduling problem. Oper. Res. 55(3):457-469.Link, Google Scholar · Zbl 1167.90664 |
| [20] | Espinoza D, Goycoolea M, Moreno E, Newman A (2013) MineLib: A library of open pit mining problems. Ann. Oper. Res. 206:93-114.Crossref, Google Scholar · Zbl 1271.90115 · doi:10.1007/s10479-012-1258-3 |
| [21] | Fischetti M, Lodi A, Monaci M, Salvagnin D, Tramontani A (2016) Improving branch-and-cut performance by random sampling. Math. Programming Comput. 8(1):113-132.Crossref, Google Scholar · Zbl 1334.90079 · doi:10.1007/s12532-015-0096-0 |
| [22] | Fisher M (1973) Optimal solution of scheduling problems using Lagrange multipliers: Part I. Oper. Res. 21(5):1114-1127.Link, Google Scholar · Zbl 0294.90085 |
| [23] | Fuentes D, Carrasco RA, Moreno E (2021) Algorithms for resource-constrained project scheduling in underground mining operations. Unpublished master’s thesis, Industrial Engineering and Operations Research, Universidad Adolfo Ibáñez, Santiago, Chile.Google Scholar |
| [24] | Goldberg A, Tarjan R (1988) A new approach to the maximum-flow problem. J. ACM 35(4):921-940.Crossref, Google Scholar · Zbl 0661.90031 · doi:10.1145/48014.61051 |
| [25] | Gu H, Schutt A, Stuckey PJ (2013) A Lagrangian relaxation based forward-backward improvement heuristic for maximising the net present value of resource-constrained projects. Gomes C, Sellmann M, eds. Internat. Conf. AI OR Techniques Constriant Programming Combin. Optim. Problems (Springer, Berlin), 340-346.Google Scholar · Zbl 1382.90120 |
| [26] | Gu H, Stuckey PJ, Wallace MG (2012) Maximising the net present value of large resource-constrained projects. Milano M, ed. Internat. Conf. Principles Practice Constraint Programming (Springer, Berlin), 767-781.Google Scholar |
| [27] | Hall L, Schulz A, Shmoys D, Wein J (1997) Scheduling to minimize average completion time: Off-line and on-line approximation algorithms. Math. Oper. Res. 22(3):513-544.Link, Google Scholar · Zbl 0883.90064 |
| [28] | Hartmann S, Briskorn D (2022) An updated survey of variants and extensions of the resource-constrained project scheduling problem. Eur. J. Oper. Res. 297(1):1-14.Crossref, Google Scholar · Zbl 1487.90294 · doi:10.1016/j.ejor.2021.05.004 |
| [29] | Hochbaum DS (2008) The pseudoflow algorithm: A new algorithm for the maximum-flow problem. Oper. Res. 56(4):992-1009.Link, Google Scholar · Zbl 1167.90394 |
| [30] | Hustrulid W, Bullock R (2001) Underground Mining Methods: Engineering Fundamentals and International Case Studies (SME, Littleton, CO).Google Scholar |
| [31] | IBM (2018) IBM ILOG AMPL version 12.8 user’s guide: Standard (Command-line) version including CPLEX directives.Google Scholar |
| [32] | Johnson TJR (1967) An algorithm for the resource constrained project scheduling problem. Unpublished doctoral dissertation, Massachusetts Institute of Technology, Cambridge, MA.Google Scholar |
| [33] | Kahn AB (1962) Topological sorting of large networks. Comm. ACM 5(11):558-562.Crossref, Google Scholar · Zbl 0106.32602 · doi:10.1145/368996.369025 |
| [34] | Kimms A (2001) Maximizing the net present value of a project under resource constraints using a Lagrangian relaxation based heuristic with tight upper bounds. Ann. Oper. Res. 102(1-4):221-236.Crossref, Google Scholar · Zbl 0990.90510 · doi:10.1023/A:1010962300979 |
| [35] | King B, Newman A (2018) Optimizing the cutoff grade for an operational underground mine. Interfaces 48(4):357-371.Link, Google Scholar |
| [36] | King B, Goycoolea M, Newman A (2017a) New integer programming models for tactical and strategic underground production scheduling. Mining Engrg. 69(3):37-42.Crossref, Google Scholar · doi:10.19150/me.7360 |
| [37] | King B, Goycoolea M, Newman A (2017b) Optimizing the open pit-to-underground mining transition. Eur. J. Oper. Res. 257(1):297-309.Crossref, Google Scholar · Zbl 1394.90408 · doi:10.1016/j.ejor.2016.07.021 |
| [38] | Kolisch R, Sprecher A (1997) PSPLIB—a project scheduling problem library. Eur. J. Oper. Res. 96(1):205-216.Crossref, Google Scholar · Zbl 0947.90587 · doi:10.1016/S0377-2217(96)00170-1 |
| [39] | Kolisch R, Sprecher A, Drexl A (1995) Characterization and generation of a general class of resource-constrained project scheduling problems. Management Sci. 41(10):1693-1703.Link, Google Scholar · Zbl 0870.90070 |
| [40] | Laborie P (2005) Complete MCS-based search: Application to resource constrained project scheduling. Proc. 19th Internat. Joint Conf. Artificial Intelligence, Edinburgh, UK, July 30-August 5, 181-186.Google Scholar |
| [41] | Laborie P (2009) IBM ILOG CP optimizer for detailed scheduling illustrated on three problems. Hoeve W-J, Hooker JN, eds. Internat. Conf. AI OR Techniques Constraint Programming Combin. Optim. Problems (Springer, Berlin), 148-162.Google Scholar |
| [42] | Laborie P, Refalo P, Shaw P (2013) Model presolve, warmstart and conflict refining in CP optimizer. CP Solvers: Model. Appl. Integration Standardization (CP2013 Workshop), Uppsala, Sweden, September 16.Google Scholar |
| [43] | Laborie P, Rogerie J, Shaw P, Vilím P (2018) IBM ILOG CP optimizer for scheduling. Constraints 23(2):210-250.Crossref, Google Scholar · Zbl 1400.90169 · doi:10.1007/s10601-018-9281-x |
| [44] | Lambert WB, Brickey A, Newman A, Eurek K (2014) Open-pit block-sequencing formulations: A tutorial. Interfaces 44(2):127-142.Link, Google Scholar |
| [45] | Lerchs H, Grossmann IF (1965) Optimum design of open-pit mines. Trans. Canadian Inst. Mining 68:17-24.Google Scholar |
| [46] | Leyman P, Vanhoucke M (2015) A new scheduling technique for the resource-constrained project scheduling problem with discounted cash flows. Internat. J. Prod. Res. 53(9):2771-2786.Crossref, Google Scholar · doi:10.1080/00207543.2014.980463 |
| [47] | Lodi A, Tramontani A (2013) Performance variability in mixed-integer programming. Topaloglu H, ed. Theory Driven by Influential Applications (INFORMS, Catonsville, MD), 1-12.Link, Google Scholar |
| [48] | Möhring R, Schulz A, Stork F, Uetz M (2003) Solving project scheduling problems by minimum cut computations. Management Sci. 49(3):330-350.Link, Google Scholar · Zbl 1232.90213 |
| [49] | Muñoz G, Espinoza D, Goycoolea M, Moreno E, Queyranne M, Letelier OR (2018) A study of the Bienstock-Zuckerberg algorithm: Applications in mining and resource constrained project scheduling. Comput. Optim. Appl. 69(2):501-534.Crossref, Google Scholar · Zbl 1403.90353 · doi:10.1007/s10589-017-9946-1 |
| [50] | Newman A, Kuchta M (2007) Using aggregation to optimize long-term production planning at an underground mine. Eur. J. Oper. Res. 176(2):1205-1218.Crossref, Google Scholar · Zbl 1103.90333 · doi:10.1016/j.ejor.2005.09.008 |
| [51] | Newman A, Rubio E, Caro R, Weintraub A, Eurek K (2010) A review of operations research in mine planning. Interfaces 40(3):222-245.Link, Google Scholar |
| [52] | Ogunmodede O, Lamas P, Brickey A, Bogin G, Newman A (2022) Underground production scheduling with ventilation and refrigeration considerations. Optim. Engrg., ePub ahead of print January 13, http://dx.doi.org/https://doi.org/10.1007/s11081-021-09682-4.Crossref, Google Scholar · doi:10.1007/s11081-021-09682-4 |
| [53] | O’Sullivan D, Newman A (2015) Optimization-based heuristics for underground mine scheduling. Eur. J. Oper. Res. 241(1):248-259.Crossref, Google Scholar · Zbl 1338.90178 · doi:10.1016/j.ejor.2014.08.020 |
| [54] | Patterson JH (1984) A comparison of exact approaches for solving the multiple constrained resource, project scheduling problem. Management Sci. 30(7):854-867.Link, Google Scholar |
| [55] | Phillips C, Stein C, Wein J (1998) Minimizing average completion time in the presence of release dates. Math. Programming 82(1-2):199-223.Crossref, Google Scholar · Zbl 0920.90074 · doi:10.1007/BF01585872 |
| [56] | Pritsker AAB, Waiters LJ, Wolfe PM (1969) Multiproject scheduling with limited resources: A zero-one programming approach. Management Sci. 16(1):93-108.Link, Google Scholar |
| [57] | Reyck BD, Herroelen W (1998) An optimal procedure for the resource-constrained project scheduling problem with discounted cash flows and generalized precedence relations. Comput. OR 25(1):1-17.Crossref, Google Scholar · Zbl 0909.90175 · doi:10.1016/S0305-0548(98)80003-8 |
| [58] | Rivera Letelier O, Espinoza D, Goycoolea M, Moreno E, Muñoz G (2020) Production scheduling for strategic open pit mine planning: A mixed-integer programming approach. Oper. Res. 68(5):1425-1444.Link, Google Scholar · Zbl 1455.90069 |
| [59] | Russell A (1970) Cash flows in networks. Management Sci. 16(5):357-373.Link, Google Scholar · Zbl 0187.18201 |
| [60] | Schutt A, Feydy T, Stuckey PJ (2013) Explaining time-table-edge-finding propagation for the cumulative resource constraint. Gomes C, Sellmann M, eds. Internat. Conf. AI OR Techniques Constriant Programming Combin. Optim. Problems (Springer, Berlin), 234-250.Google Scholar · Zbl 1382.68232 |
| [61] | Schutt A, Chu G, Stuckey PJ, Wallace MG (2012) Maximising the net present value for resource-constrained project scheduling. Beldiceanu N, Jussien N, Pinson E, eds. Internat. Conf. Integration AI OR Techniques Constraint Programming (Springer, Berlin), 362-378.Google Scholar |
| [62] | Schutt A, Feydy T, Stuckey PJ, Wallace MG (2009) Why cumulative decomposition is not as bad as it sounds. Gent IP, ed. Principles Practice Constraint Programming (CP 2009) (Springer, Berlin), 746-761.Google Scholar |
| [63] | Schutt A, Feydy T, Stuckey PJ, Wallace MG (2011) Explaining the cumulative propagator. Constraints 16(3):250-282.Crossref, Google Scholar · Zbl 1226.68099 · doi:10.1007/s10601-010-9103-2 |
| [64] | Schwindt C, Zimmermann J (2015) Handbook on Project Management and Scheduling (Springer, Berlin).Crossref, Google Scholar · doi:10.1007/978-3-319-05443-8 |
| [65] | Talbot FB (1982) Resource-constrained project scheduling with time-resource tradeoffs: The nonpreemptive case. Management Sci. 28(10):1197-1210.Link, Google Scholar · Zbl 0493.90042 |
| [66] | Terblanche S (2017) Resource constrained project scheduling models and algorithms applied to underground mining. Unpublished doctoral dissertation, Stellenbosch University, Stellenbosch, South Africa.Google Scholar |
| [67] | Vanhoucke M (2009) A genetic algorithm for net present value maximization for resource constrained projects. Cotta C, Cowling P, eds. Evolutionary Computation in Combinatorial Optimization (Springer, Berlin), 13-24.Crossref, Google Scholar · doi:10.1007/978-3-642-01009-5_2 |
| [68] | Vanhoucke M (2010) A scatter search heuristic for maximising the net present value of a resource-constrained project with fixed activity cash flows. Internat. J. Prod. Res. 48(7):1983-2001.Crossref, Google Scholar · Zbl 1197.90235 · doi:10.1080/00207540802010781 |
| [69] | Vanhoucke M, Coelho J, Batselier J (2016) An overview of project data for integrated project management and control. J. Modern Project Management 3(3):6-21.Google Scholar |
| [70] | Vanhoucke M, Demeulemeester E, Herroelen W (2001) On maximizing the net present value of a project under renewable resource constraints. Management Sci. 47(8):1113-1121.Link, Google Scholar · Zbl 1232.90215 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
