Algorithm selector for dynamic AGV scheduling in a smart manufacturing environment using machine learning
Date
2022-11
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Stellenbosch : Stellenbosch University
Abstract
ENGLISH ABSTRACT: Artificial intelligence is considered as significant technology for driving the future evolution of smart manufacturing environments forward. At the same time, automated guided vehicles (AGVs) play an essential role in manufacturing systems because they have such great potential when it comes to improving internal logistics by increasing production flexibility. Consequently, the productivity of the entire system relies on the quality of the schedule, which is capable of achieving massive cost savings by minimizing delay and the total makespan. However, traditional scheduling algorithms often have difficulties in adapting to changing environment conditions, and the performance of a selected algorithm depends on the individual scheduling problem. That is why the analysis of scheduling problem classes can help to identify the most suitable algorithm depending on a given problem. Currently, the focus in the literature lies on individual algorithm approaches for specific AGV scheduling scenarios, but the influence of framework conditions to the algorithm performance lacks attention. More research is necessary in terms of the dynamic and independent reaction for optimizing the AGV scheduling procedure without human surveillance in case of failures. To develop an algorithm selection approach for AGV scheduling scenarios, this research answered the question of how machine learning approaches must be implemented so that the allocation of tasks in the context of dynamic AGV scheduling can be improved to increase performance. This study followed Design Science Research, particularly the cognition process based on Osterle et al. (2011) that builds on an analysis, design, evaluation, and diffusion phase. During the design phase, laboratory experiments unveiled the successful implementation of two constraint programming solvers for solving scheduling problems based on the Job Shop Scheduling Problem (JSSP) and Flexible Job Shop Scheduling Problem (FJSSP). OR-Tools developed by Google and CP Optimizer of IBM solved large instances in reasonable time, and the performance of the solver strongly depended on the given scheduling problem class and problem instance. Consequently, it is beneficial to make use of an algorithm selection, as the overall production performance increased by selecting the most suitable algorithm for a given instance. The field experiment within the learning factory of Reutlingen University enabled the implementation of the approach within a dynamic environment, that can react to disruptions like machine break-downs or AGV failures. As a limitation, the research considered a simplification of the AGV scheduling problem based on the JSSP and FJSSP. As such, the parameters are limited to transport orders, transport durations, sequences and AGVs. Furthermore, the training of the selector was with a limited amount of 544 benchmark instances. Nevertheless, this research showed an exemplary extension of existing scheduling approaches to develop an algorithm selection model which can be built upon in the future. This research places the focus on constraint programming solutions for scheduling problems and emphasizes the benefits of applying machine learning for algorithm selection on a per-instance base. In this way, scheduling systems can be computationally faster and more efficient in the future and help to achieve the desired overall performance of smart manufacturing systems.
AFRIKAANS OPSOMMING: Kunsmatige Intelligensie word beskou as 'n belangrike tegnologie om die toekomstige evolusie van intelligente vervaardigingsomgewings aan te dryf. Terselfdertyd is Outonome Geleide Voertuie (OGV's) 'n noodsaaklike deel van vervaardigingstelsels vanwee hul hoe potensiaal om interne logistiek te verbeter deur produksiebuigsaamheid te verhoog. Die produktiwiteit van die hele stelsel berus op die kwaliteit van die skedule, wat die vermoe het om massiewe kostebesparings te bewerkstellig deur vertragings en die totale produksie leityd te verminder. Tradisionele skeduleringsalgoritmes het egter dikwels probleme om aan te pas by veranderende omgewingstoestande, en die werkverrigting van 'n geselekteerde algoritme hang af van die individuele skeduleringsprobleem. Die ontleding van skeduleringsprobleemklasse kan dus help om die mees geskikte algoritme te identifiseer afhangende van 'n gegewe probleem. Tans le die fokus in die literatuur op individuele algoritmebenaderings vir spesifieke OGV skeduleringsscenario's, maar die invloed van raamwerkvoorwaardes op die algoritmeprestasie kort verdere aandag. Meer navorsing is nodig in terme van dinamiese en onafhanklike reaksie vir die optimering van die AGV-skeduleringsprosedure sander menslike toesig in geval van mislukkings. Om 'n algoritmeseleksie benadering vir AGV-skedulering-scenario's te ontwikkel, het hierdie navorsing die vraag beantwoord oor hoe masjienleerbenaderings ge"irnplementeer moet word om die toekenning van take in die konteks van dinamiese AGV-skedulering te verbeter en sodoende prestasie te verhoog. Hierdie studie het die ontwerpwetenskap navorsingsmetodologie gevolg, veral die kognisieproses gebaseer op Osterle et al. (2011) wat voortbou op 'n analise-, ontwerp-, evaluerings- en verspreidingsfase. Tydens die ontwerpfase het laboratoriumeksperimente die suksesvolle implementering van twee beperkingsprogrammeringsoplossers onthul vir die oplossing van skeduleringsprobleme gebaseer op die Werkwinkel Skedulering Probleem (WWSP) en Buigsame Werkwinkel Skedulerings probleem (BWWSP). Operasionele Navorsing (ON)-Gereedskap ontwikkel deur Google en Beperking Programmering (BP) optimering van IBM het groot gevalle binne redelike tyd opgelos, en die werkverrigting van die oplosser het sterk afgehang van die gegewe skeduleringsprobleemklas en probleemgeval. Gevolglik is dit voordelig om van 'n algoritme seleksie gebruik te maak, aangesien die algehele produksieprestasie toegeneem het deur die mees geskikte algoritme vir 'n gegewe geval te kies. Die veldeksperiment binne die leerfabriek van Reutlingen Universiteit het die implementering van die benadering in 'n dinamiese omgewing bewys, wat kan reageer op ontwrigtings soos masjienonderbrekings of OGV-onderbrekings. As 'n beperking het die navorsing 'n vereenvoudiging van die OGV-skeduleringsprobleem, gebaseer op die WWSP en BWWSP, oorweeg. Daarom is die parameters beperk tot die vervoer bestellings, duur, reekse en OGV's. Verder is die opleiding van die keurder met 'n beperkte hoeveelheid van 544 maatstafgevalle beperk. Nietemin het hierdie navorsing 'n uitbreiding van bestaande skeduleringsbenaderings getoon deur 'n 'n algoritmeseleksiemodel te ontwikkel om in die toekoms op voort te bou. Hierdie navorsing het gefokus op BP-oplossings vir skeduleringsprobleme en beklemtoon die voordele van die toepassing van masjienleer vir algoritmeseleksie op 'n per-instansie basis. Op hierdie manier kan skeduleringstelsels in die toekoms rekenaarmatig vinniger en doeltreffender wees en help om die verlangde algehele werkverrigting van intelligente vervaardigingstelsels te bereik.
AFRIKAANS OPSOMMING: Kunsmatige Intelligensie word beskou as 'n belangrike tegnologie om die toekomstige evolusie van intelligente vervaardigingsomgewings aan te dryf. Terselfdertyd is Outonome Geleide Voertuie (OGV's) 'n noodsaaklike deel van vervaardigingstelsels vanwee hul hoe potensiaal om interne logistiek te verbeter deur produksiebuigsaamheid te verhoog. Die produktiwiteit van die hele stelsel berus op die kwaliteit van die skedule, wat die vermoe het om massiewe kostebesparings te bewerkstellig deur vertragings en die totale produksie leityd te verminder. Tradisionele skeduleringsalgoritmes het egter dikwels probleme om aan te pas by veranderende omgewingstoestande, en die werkverrigting van 'n geselekteerde algoritme hang af van die individuele skeduleringsprobleem. Die ontleding van skeduleringsprobleemklasse kan dus help om die mees geskikte algoritme te identifiseer afhangende van 'n gegewe probleem. Tans le die fokus in die literatuur op individuele algoritmebenaderings vir spesifieke OGV skeduleringsscenario's, maar die invloed van raamwerkvoorwaardes op die algoritmeprestasie kort verdere aandag. Meer navorsing is nodig in terme van dinamiese en onafhanklike reaksie vir die optimering van die AGV-skeduleringsprosedure sander menslike toesig in geval van mislukkings. Om 'n algoritmeseleksie benadering vir AGV-skedulering-scenario's te ontwikkel, het hierdie navorsing die vraag beantwoord oor hoe masjienleerbenaderings ge"irnplementeer moet word om die toekenning van take in die konteks van dinamiese AGV-skedulering te verbeter en sodoende prestasie te verhoog. Hierdie studie het die ontwerpwetenskap navorsingsmetodologie gevolg, veral die kognisieproses gebaseer op Osterle et al. (2011) wat voortbou op 'n analise-, ontwerp-, evaluerings- en verspreidingsfase. Tydens die ontwerpfase het laboratoriumeksperimente die suksesvolle implementering van twee beperkingsprogrammeringsoplossers onthul vir die oplossing van skeduleringsprobleme gebaseer op die Werkwinkel Skedulering Probleem (WWSP) en Buigsame Werkwinkel Skedulerings probleem (BWWSP). Operasionele Navorsing (ON)-Gereedskap ontwikkel deur Google en Beperking Programmering (BP) optimering van IBM het groot gevalle binne redelike tyd opgelos, en die werkverrigting van die oplosser het sterk afgehang van die gegewe skeduleringsprobleemklas en probleemgeval. Gevolglik is dit voordelig om van 'n algoritme seleksie gebruik te maak, aangesien die algehele produksieprestasie toegeneem het deur die mees geskikte algoritme vir 'n gegewe geval te kies. Die veldeksperiment binne die leerfabriek van Reutlingen Universiteit het die implementering van die benadering in 'n dinamiese omgewing bewys, wat kan reageer op ontwrigtings soos masjienonderbrekings of OGV-onderbrekings. As 'n beperking het die navorsing 'n vereenvoudiging van die OGV-skeduleringsprobleem, gebaseer op die WWSP en BWWSP, oorweeg. Daarom is die parameters beperk tot die vervoer bestellings, duur, reekse en OGV's. Verder is die opleiding van die keurder met 'n beperkte hoeveelheid van 544 maatstafgevalle beperk. Nietemin het hierdie navorsing 'n uitbreiding van bestaande skeduleringsbenaderings getoon deur 'n 'n algoritmeseleksiemodel te ontwikkel om in die toekoms op voort te bou. Hierdie navorsing het gefokus op BP-oplossings vir skeduleringsprobleme en beklemtoon die voordele van die toepassing van masjienleer vir algoritmeseleksie op 'n per-instansie basis. Op hierdie manier kan skeduleringstelsels in die toekoms rekenaarmatig vinniger en doeltreffender wees en help om die verlangde algehele werkverrigting van intelligente vervaardigingstelsels te bereik.
Description
Thesis (MEng)--Stellenbosch University, 2023.