The operational performance of an underground mine depends critically on how the production is scheduled. Increasingly advanced methods are used to create optimized long-term plans, and simultaneously the actual excavation is getting more and more automated. Therefore, the mapping of long-term goals into tasks by manual short-term scheduling is becoming a limiting segment in the optimization chain. In this thesis we study automating the short-term mine scheduling process, and thus contribute to an important missing piece in the pursuit of autonomous mining. First, we clarify the fleet scheduling problem and the surrounding context. Based on this knowledge, we propose a flow shop that models the mine scheduling problem. A flow shop is a general abstract process formulation that captures the key properties of a scheduling problem without going into specific details. We argue that several popular mining methods can be modeled as a rich variant of a k-stage hybrid flow shop, where the flow shop includes a mix of interruptible and uninterruptible tasks, after-lags, machine unavailabilities, and sharing of machines between stages. Then, we propose a Constraint Programming approach to schedule the underground production fleet. We formalize the problem and present a model that can be used to solve it. The model is implemented and evaluated on instances representative of medium-sized underground mines. After that, we introduce travel times of the mobile machines to the scheduling problem. This acknowledges that underground road networks can span several hundreds of kilometers. With this addition, the initially proposed Constraint Programming model struggles with scaling to larger instances. Therefore, we introduce a second model. The second model 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. This model is significantly faster, and can solve instances representative of large-sized mines even when including travel times. Lastly, we focus on finding high-quality schedules by introducing Large Neighborhood Search. To do this, we present a domain-specific neighborhood definition based on relaxing variables corresponding to certain work areas. Variants of this neighborhood are evaluated in Large Neighborhood Search and compared to using only restarts. All methods and models in this thesis are evaluated on instances generated from an operational underground mine. / Underjordsgruvans operativa prestanda är till stor del beroende av schemaläggningen av de mobila maskinerna. Allt mer avancerade metoder används för att skapa optimerade långtidsplaner samtidigt som produktionsaktiviteterna blir allt mer automatiserade. Att överföra långtidsmål till aktiviteter genom manuell schemaläggning blir därför ett begränsande segment i optimeringskedjan. I denna avhandling studerar vi automatisering av schemaläggning för underjordsgruvor och bidrar således med en viktig komponent i utvecklandet av autonom gruvdrift. Vi börjar med att klargöra schemaläggningsproblemet och dess omgivande kontext. Baserat på detta klargörande föreslår vi en abstraktion där problemet kan ses som en flow shop. En flow shop är en processmodell som fångar de viktigaste delarna av ett schemaläggningsproblem utan att hänsyn tas till allt för många detaljer. Vi visar att flera populära gruvbrytningsmetoder kan modelleras som en utökad variant av en k-stage hybrid flow shop. Denna utökade flow shop innehåller en mix av avbrytbara och icke avbrytbara aktiviteter, eftergångstid, indisponibla maskiner samt gemensamma maskinpooler för vissa steg. Sedan föreslår vi ett koncept för att lösa schemaläggningsproblemet med hjälp av villkorsprogrammering. Vi formaliserar problemet och presenterar en modell som kan användas för att lösa det. Modellen implementeras och utvärderas på probleminstanser representativa för mellanstora underjordsgruvor. Efter det introducerar vi restider för de mobila maskinerna i schemaläggningsproblemet. Detta grundar sig i att vägnätet i underjordsgruvor kan sträcka sig upp till flera hundra kilometer. Med det tillägget får den initiala villkorsprogrammeringsmodellen svårt att lösa större instanser. För att möta det problemet så introducerar vi en ny modell. Den nya modellen löser inte det avbrytbara problemet direkt utan börjar med att lösa ett relaterat, icke avbrytbart, problem för att sedan transformera lösningen tillbaka till den ursprungliga tidsdomänen. Denna modell är betydligt snabbare och kan lösa probleminstanser representativa för stora underjordsgruvor även när restider inkluderas. Avslutningsvis fokuserar vi på att hitta scheman av hög kvalitet genom att optimera med Large Neighborhood Search. För att åstadkomma detta presenterar vi ett domänspecifikt grannskap baserat på att relaxera variabler som rör aktiviteter inom vissa produktionsområden. Flera varianter av detta grannskap utvärderas och jämförs med att enbart använda omstarter. Alla metoder och modeller i den här avhandlingen är utvärderade på genererade instanser från en operativ underjordsgruva. / <p>QC 20181026</p>
| Identifer | oai:union.ndltd.org:UPSALLA1/oai:DiVA.org:kth-237291 |
| Date | January 2018 |
| Creators | Åstrand, Max |
| Publisher | KTH, Reglerteknik, Stockholm |
| Source Sets | DiVA Archive at Upsalla University |
| Language | English |
| Detected Language | Swedish |
| Type | Licentiate thesis, monograph, info:eu-repo/semantics/masterThesis, text |
| Format | application/pdf |
| Rights | info:eu-repo/semantics/openAccess |
| Relation | TRITA-EECS-AVL ; 2018:81 |
Page generated in 0.0018 seconds