Background: Optimal scheduling is a common practice in various industries, facili-tating efficient workflow management. Accelerating the generation of schedules while maintaining their optimality could encourage broader adoption of this approach inindustry settings. Previous work has aimed to estimate the makespan for the JobShop Scheduling Problem, showing promising results. Objectives: Given the increasing demand for AI and Machine Learning (ML) solutions across industries, this research aims to explore the integration of ML techniquesinto optimal scheduling processes. Specifically, the goal is to develop a faster scheduling solution without compromising the optimality of the generated schedules. The proposed approach combines the effectiveness and speed of ML with the optimal results obtained from mathematical scheduling models. Methods: This thesis focuses on the Job Shop Scheduling (JSS) Problem, where a mathematical scheduler is tasked with minimizing the makespan of a set of jobs while following a predefined set of rules. An initial investigation is performed to establish if there is potential in providing the scheduler with its optimal makespan to decrease the scheduling time. To generalize the application of the concept, the study investigates the potential efficiency acceleration achieved by providing the scheduler with a Machine Learning estimated makespan. This involves training a Neural Network(NN) to estimate the optimal makespan of job sets, which is then utilized to speedup the scheduling process. Results: The preliminary investigation demonstrates that providing the scheduler with the optimal makespan results in an average speed-up of schedule generationby 24%. The results of the scheduling time with the NN estimated makespan is on the other hand not as well performing. Despite achieving a level of accuracy in estimating the makespan, the resulting speed-up in the scheduler’s performance falls short. For the scheduler to benefit from being provided an estimated makespan it is therefore theorized to require a close-to-perfect estimation of the makespan, which was not achieved with the trained NN model. The trained NN reached an average accuracy of 95.75%. Conclusions: The study concludes that while ML models can accurately estimate makespan, the observed speed-up in scheduling performance is not as significant as anticipated. The correlation between well-estimated makespan and speed-up appearsto be inconsistent, indicating potential limitations in the current approach. Further investigation into the search algorithm employed by the scheduling tool Gurobi mayprovide insights into optimizing the scheduling process more effectively. In summary, while the integration of ML techniques shows promise in accelerating scheduling processes, a higher accuracy of the ML model would be required. Additional researchis needed to refine the approach and potentially bring a faster optimal scheduling solution into the future. / Bakgrund: Optimal schemaläggning är en vanlig implemetation inom flera olika branscher och underlättar hantering och effektiviserar arbetsflöden. Att påskynda genereringen av scheman samtidigt som den optimala aspekten av schemaläggning inte går till spillo, skulle kunna främja en bredare användning av optimal schemaläggning för fler brancher. Tidigare undersökningar har gjorts för att estimera "makespan" för Job Shop problemet inom schemaläggning och har visat lovande resultat. Syfte: Med den ökande efterfrågan på AI- och maskininlärnings lösningar inom olika branscher syftar denna forskning till att utforska integrationen av ML-tekniker i den optimala schemaläggningsprocessen. Målet är att utveckla en snabbare schemaläggningslösning utan att kompromissa med det genererade schemats optimalitet. Det föreslagna tillvägagångssättet kombinerar ML’s effektivitet och hastighet med de optimala resultaten som den matematiska schemaläggningsmodellen erbjuder. Metod: Forskningen fokuserar på problemet med schemaläggning för jobbshoppen(JSSP), där en matematisk schemaläggare har i uppgift att minimera makespan fören uppsättning jobb med hänsyn till ett par fördefinierade regler. En initial under-sökning görs, vilket visar att det finns potential i att tillhandahålla schemaläggarendess optimala makespan för att minska schemaläggningstiden. För att generalisera tillämpningen undersöker studien den potentiella accelerationen som uppnås genomatt tillhandahålla schemaläggaren ett maskininlärt uppskattat makespan. Detta medför att träna ett neuralt nätverk för att uppskatta det optimala makespanet för en mängd jobbuppsättningar, som sedan används för att påskynda schemaläggningsprocessen. Resultat: Den preliminära undersökningen visar att schemaläggaren resulterar i igenomsnittlig hastighetsökning av schemagenereringen med cirka 24% när den får tillgång till det optimala makespanet för de givna jobben. Resultaten av schemaläggningstiden med det neurala nätverkets uppskattade makespan är dock lägre än förväntat. Trots att en viss noggrannhetsnivå uppnås vid estimeringen av makespanet, når den resulterande hastighetsökningen i schemaläggarens prestanda inte upp tillförväntningarna. För att schemaläggaren ska dra nytta av att tillhandahålla ett uppskattad makespan krävs en nära perfekt uppskattning av makespan, vilket inte uppnåddes med det tränade neurala nätverket. Slutsatser: Studien drar slutsatsen att även om ML-modeller kan uppskatta makespan någorlunda noggrant, är den observerade hastighetsökningen i schemaläggningen inte lika betydande som förväntat. Korrelationen mellan väl uppskattad makespan och hastighetsökning verkar vara inkonsekvent, vilket indikerar potentiella begränsningar i det nuvarande tillvägagångssättet. Vidare undersökning av sökalgoritmen som används av schemaläggningsverktyget Gurobi kan ge insikter för att optimera schemaläggningsprocessen mer effektivt. Sammanfattningsvis visar integrationen av ML-tekniker lovande resultat för att accelerera schemaläggningsprocesser, men en bättre estimering av makespan skulle krävas. Ytterligare forskning behövs för att förbättra tillvägagångssättet och potentiellt introducera en snabbare optimal schemaläggningslösning för framtiden.
| Identifer | oai:union.ndltd.org:UPSALLA1/oai:DiVA.org:bth-26326 |
| Date | January 2024 |
| Creators | Holm, Tobias, Waters, Phoebe |
| Publisher | Blekinge Tekniska Högskola, Institutionen för datavetenskap |
| Source Sets | DiVA Archive at Upsalla University |
| Language | English |
| Detected Language | Swedish |
| Type | Student thesis, info:eu-repo/semantics/bachelorThesis, text |
| Format | application/pdf |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0032 seconds