nach oben

Erschienen in:

2021 | OriginalPaper | Buchkapitel

Short-Term Scheduling of Production Fleets in Underground Mines Using CP-Based LNS

verfasst von : Max Åstrand, Mikael Johansson, Hamid Reza Feyzmahdavian

Erschienen in: Integration of Constraint Programming, Artificial Intelligence, and Operations Research

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Coordinating the mobile production fleet in underground mines becomes increasingly important as the machines are more and more automated. We present a scheduling approach that applies to several of the most important production methods used in underground mines. Our algorithm combines constraint programming with a large neighborhood search strategy that dynamically adjusts the neighborhood size. The resulting algorithm is complete and able to rapidly improve constructed schedules in practice. In addition, it has important benefits when it comes to the acceptance of the approach in real-life operations. Our approach is evaluated on public and private industrial problem instances representing different mines and production methods. We find significant improvements over the current industrial practice.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Finding Subgraphs with Side Constraints

Nächstes Kapitel Learning to Reduce State-Expanded Networks for Multi-activity Shift Scheduling

Ahuja, R.K., Ergun, Ö., Orlin, J.B., Punnen, A.P.: A survey of very large-scale neighborhood search techniques. Discret. Appl. Math. 123(1–3), 75–102 (2002)MathSciNetCrossRef

Åstrand, M., Johansson, M., Greberg, J.: Underground mine scheduling modeled as a flow shop - a review of relevant works and future challenges. J. Southern Afr. Inst. Min. Metall. 118(12), 1265–1276 (2018)

Åstrand, M., Johansson, M., Zanarini, A.: Fleet scheduling in underground mines using constraint programming. In: van Hoeve, W.-J. (ed.) CPAIOR 2018. LNCS, vol. 10848, pp. 605–613. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-93031-2_44CrossRefMATH

Åstrand, M., Johansson, M., Zanarini, A.: Underground mine scheduling of mobile machines using constraint programming and large neighborhood search. Comput. Oper. Res. 123, 105036 (2020)MathSciNetCrossRef

Back, T.: Evolutionary Algorithms in Theory and Practice: Evolution Strategies, Evolutionary Programming, Genetic Algorithms. Oxford University Press, Oxford (1996)CrossRef

Behrens, J.K., Lange, R., Mansouri, M.: A constraint programming approach to simultaneous task allocation and motion scheduling for industrial dual-arm manipulation tasks. In: 2019 International Conference on Robotics and Automation (ICRA), pp. 8705–8711. IEEE (2019)

Booth, K.E.C., Nejat, G., Beck, J.C.: A constraint programming approach to multi-robot task allocation and scheduling in retirement homes. In: Rueher, M. (ed.) CP 2016. LNCS, vol. 9892, pp. 539–555. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-44953-1_34CrossRef

Boussemart, F., Hemery, F., Lecoutre, C., Sais, L.: Boosting systematic search by weighting constraints. In: ECAI, vol. 16, p. 146 (2004)

Carchrae, T., Beck, J.C.: Principles for the design of large neighborhood search. J. Math. Modell. Algorithms 8, 245–270 (2009)MathSciNetCrossRef

10.

Darling, P.: SME Mining Engineering Handbook, vol. 1. SME (2011)

11.

Gecode Team: Gecode: Generic constraint development environment (2019). https://www.gecode.org

12.

Grimes, D., Hebrard, E.: Solving variants of the job shop scheduling problem through conflict-directed search. INFORMS J. Comput. 27(2), 268–284 (2015)MathSciNetCrossRef

13.

Grimes, D., Hebrard, E., Malapert, A.: Closing the open shop: contradicting conventional wisdom. In: Gent, I.P. (ed.) CP 2009. LNCS, vol. 5732, pp. 400–408. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-04244-7_33CrossRef

14.

Ham, A.M.: Integrated scheduling of m-truck, m-drone, and m-depot constrainedby time-window, drop-pickup, and m-visit using constraint programming. Transp. Res. Part C: Emerg. Technol. 91, 1–14 (2018)CrossRef

15.

He, L., de Weerdt, M., Yorke-Smith, N.: Time/sequence-dependent scheduling: the design and evaluation of a general purpose tabu-based adaptive large neighbourhood search algorithm. J. Intell. Manuf. 31(4), 1051–1078 (2019). https://doi.org/10.1007/s10845-019-01518-4CrossRef

16.

Laborie, P.: An update on the comparison of MIP, CP and hybrid approaches for mixed resource allocation and scheduling. In: van Hoeve, W.-J. (ed.) CPAIOR 2018. LNCS, vol. 10848, pp. 403–411. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-93031-2_29CrossRefMATH

17.

Laborie, P., Godard, D.: Self-adapting large neighborhood search: application to single-mode scheduling problems. Proceedings MISTA-07, Paris 8 (2007)

18.

Luby, M., Sinclair, A., Zuckerman, D.: Optimal speedup of Las Vegas algorithms. Inf. Process. Lett. 47(4), 173–180 (1993)MathSciNetCrossRef

19.

Mears, C., De La Banda, M.G., Demoen, B., Wallace, M.: Lightweight dynamic symmetry breaking. Constraints 19(3), 195–242 (2014)

20.

Mishchenko, K., Åstrand, M., Molander, M., Lindkvist, R., Viklund, T.: Developing a tool for automatic mine scheduling. In: Topal, E. (ed.) MPES 2019. SSGG, pp. 146–153. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-33954-8_18CrossRef

21.

Papadimitriou, C., Steiglitz, K.: Combinatorial Optimization: Algorithms and Complexity. Courier Corporation (1998)

22.

Pisinger, D., Ropke, S.: A general heuristic for vehicle routing problems. Comput. Oper. Res. 34(8), 2403–2435 (2007)MathSciNetCrossRef

23.

Ropke, S., Pisinger, D.: An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows. Transp. Sci. 40(4), 455–472 (2006)CrossRef

24.

Schulze, M., Rieck, J., Seifi, C., Zimmermann, J.: Machine scheduling in underground mining: an application in the potash industry. OR Spectrum 38(2), 365–403 (2015). https://doi.org/10.1007/s00291-015-0414-yMathSciNetCrossRefMATH

25.

Schulze, M., Zimmermann, J.: Staff and machine shift scheduling in a German potash mine. J. Scheduling 1–22 (2017)

26.

Seifi, C., Schulze, M., Zimmermann, J.: A two-stage solution approach for a shift scheduling problem with a simultaneous assignment of machines and workers. In: The 39th International Symposium on Application of Computers and Operations Research in the Mineral Industry, Wroclaw, Poland (2019)

27.

Seifi, C., Schulze, M., Zimmermann, J.: A new mathematical formulation for apotash-mine shift scheduling problem with a simultaneous assignment of machines and workers. Eur. J. Oper. Res. 292, 27–42 (2020)CrossRef

28.

Shaw, P.: Using constraint programming and local search methods to solve vehicle routing problems. In: Maher, M., Puget, J.-F. (eds.) CP 1998. LNCS, vol. 1520, pp. 417–431. Springer, Heidelberg (1998). https://doi.org/10.1007/3-540-49481-2_30CrossRef

29.

Simonis, H.: Building industrial applications with constraint programming. In: Goos, G., Hartmanis, J., van Leeuwen, J., Comon, H., Marché, C., Treinen, R. (eds.) CCL 1999. LNCS, vol. 2002, pp. 271–309. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-45406-3_6CrossRef

30.

Song, Z., Schunnesson, H., Rinne, M., Sturgul, J.: Intelligent scheduling for underground mobile mining equipment. PloS One 10(6), e0131003 (2015)CrossRef

31.

Žulj, I., Kramer, S., Schneider, M.: A hybrid of adaptive large neighborhood search and tabu search for the order-batching problem. Eur. J. Oper. Res. 264(2), 653–664 (2018)MathSciNetCrossRef

Titel: Short-Term Scheduling of Production Fleets in Underground Mines Using CP-Based LNS
verfasst von: Max Åstrand
Mikael Johansson
Hamid Reza Feyzmahdavian
Verlag: Springer International Publishing
Buch: Integration of Constraint Programming, Artificial Intelligence, and Operations Research
Print ISBN: 978-3-030-78229-0

Electronic ISBN: 978-3-030-78230-6

Copyright-Jahr: 2021
DOI: https://doi.org/10.1007/978-3-030-78230-6_23

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner