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.

I sitt sökande efter en säker och lönsam drift rör sig gruvindustrin mot en ökad automation. I takt med att driften automatiseras finns en önskan hos dagens gruvbolag att optimera koordineringen av de allt mer automatiserade gruvaktiviteterna. Denna koordinering benämns korttidsplanering och kan beskrivas som den process genom vilken man fördelar resurser och bestämmer start- och stopptider för de kommande gruvaktiviteterna. 

Dagens industripraxis vad gäller korttidsplanering vilar i hög grad på manuellt arbete vilket gör utförandet starkt beroende av den enskilda schemaläggarens expertis. I denna avhandling studeras hur automatisering av korttidsplaneringsprocessen för underjordsgruvor kan öka effektiviteten inom en vital del av underjordsgruvans planeringskedja.

Avhandlingen inleds med att problemet med korttidsplanering av underjordsgruvor klargörs och sätts i en operativ kontext. Efter det föreslås en hybrid flow shop-abstraktion som fångar centrala aspekter av gruvbrytningsprocessen. Här visas att några populära produktionsmetoder kan ses som utökade varianter av en k-stage hybrid flow shop vilka uppvisar, till exempel, en mix av avbrytbara och icke avbrytbara aktiviteter, sekvensberoende samt resursdelning mellan olika steg i processen. 

Sedan presenteras en villkorsprogrammeringsmodell för korttidsplanering av underjordsgruvor. Denna modell täcker viktiga delar av schemaläggningsproblemet och kan användas för att lösa realistiska probleminstanser från gruvindustrin. Modellen tar dock inte hänsyn till den tid det tar för mobila maskiner att transporteras till nästföljande aktivitet. Vägnätet i underjordsgruvor kan sträcka sig upp till flera hundra kilometer vilket gör restid till en viktig aspekt. I och med att restid läggs till i den initiala villkorsprogrammeringsmodellen får den svårt att lösa större instanser och därför introduceras en andra modell. Denna andra modell löser inte det avbrytbara problemet direkt utan löser istället ett relaterat, icke avbrytbart, problem och transformerar lösningen tillbaka till den ursprungliga tidsdomänen. Den här modellen är signifikant snabbare och kan lösa instanser som är representativa för stora underjordsgruvor även när restid inkluderas. Modellen utökas sedan för att stödja mer generella produktionsscenarier.

En utvärdering görs av Large Neighborhood Search i sökandet efter högkvalitativa scheman. En domänspecifik grannskapsdefinition presenteras, vilken är baserad på att relaxera variabler som härrör till specifika platser i gruvan. Inledningsvis undersöks fasta grannskapsstorlekar och detta jämförs med omstartsbaserad sökning. När det visar sig att det inte finns någon tydligt dominerande strategi för att använda fasta grannskapsstorlekar föreslås en algoritm för en dynamisk justering av grannskapens storlek. Algoritmen har den fördelen att vara både komplett och samtidigt kapabel att snabbt förbättra konstruerade scheman. Vidare introducerar algoritmen lokala optimalitetsegenskaper som är fördelaktiga för industriell acceptans. 

Avhandlingen avrundas med en redovisning av praktiska erfarenheter från automatisering av korttidsplanering i verkliga gruvmiljöer. Vidare motiveras antaganden och val av design på grundval av tidigare erfarenheter från användandet av enklare schemaläggningsalgoritmer för korttidsplanering av underjordsgruvor. Avslutningsvis får erfarna schemaläggare från två olika gruvor bedöma den slutgiltiga schemaläggningsmetodiken för att bekräfta dess tillämpningsbarhet i verkliga gruvmiljöer.