Short-term Underground Mine Scheduling
An Industrial Application of Constraint Programming
Time: Thu 2021-06-10 09.00
Location: link for online defense (English)
Subject area: Electrical Engineering
Doctoral student: Max Åstrand , Reglerteknik
Opponent: Docent Mats Carlsson, RISE., Swedish ICT, SICS, Computer Systems Laboratory
Supervisor: Professor Mikael Johansson, Reglerteknik
The mining industry is facing a surge in automation in the pursuit of safe and profitable operations. As the excavation process is increasingly automated, today's mining companies seek to optimize the coordination of the now automated mining activities. This coordination is called short-term mine scheduling, and it is the process of allocating resources and determining feasible start and end times for the upcoming mining activities. Unfortunately, current industrial practice relies heavily on manual labor, making the performance critically dependent on the expertise of the individual scheduler. In this thesis, we study how to automate the short-term mine scheduling process to increase the efficiency in a vital part of the underground mine planning chain.
First, the short-term underground mine scheduling problem is detailed, and the surrounding operational context is clarified. Central aspects of the excavation process are shown to be adequately described by a scheduling abstraction known as a hybrid flow shop. We demonstrate that some popular mine production methods can be considered rich variants of a k-stage hybrid flow shop exhibiting a mix of interruptible and uninterruptible activities, sequence-dependent setup times, and sharing of machines between stages.
An approach based on constraint programming is then presented that can be used for short-term scheduling in underground mines. For mines that have vast underground road networks, it is important to consider the travel times needed for the mobile machines between subsequent activities. The proposed extension of the first approach can unfortunately only solve small instances in reasonable computation times. To solve industrially relevant problem sizes, we introduce a second approach. The second approach does not solve the interruptible scheduling problem directly; instead, it solves a related uninterruptible problem and transforms the solution back to the original time domain. It is significantly faster than the first approach and can be used to solve larger instances, even when including travel times. The second approach is also extended to support more general mining scenarios that cannot be described as hybrid flow shops.
To improve the quality of the schedules, we introduce a domain-specific neighborhood definition that is used in large neighborhood search. Initially, different fixed neighborhood sizes are investigated. Upon observing that there is no clear dominant strategy, we propose an algorithm for dynamically adjusting the size of the explored neighborhoods. The constructed schedules are improved rapidly using the proposed algorithm, which also introduces local optimality properties that are beneficial when it comes to industrial acceptance. For all models and methods presented in this thesis, we perform extensive numerical evaluations on problem instances derived from operational underground mines.
This thesis is concluded by presenting practical experiences from automating the short-term scheduling process in underground mines. Assumptions and design choices are motivated by earlier experiences from using simpler scheduling algorithms. Finally, senior mine schedulers from two different mine sites assess the real-life applicability of the final scheduling approach.