Methodology for Self-Adaptively Solving Multi-Objective Scheduling Problems

Abstract

Scheduling practices are critical decision-making processes that substantially influence the overall performance of cloud and manufacturing environments. Therefore, scheduling problems have been a primary concern of practitioners and scholars in this field for decades. The majority of scheduling problems are known NP-hard optimization problems. Hence, heuristic and improvement methods have been conventionally adopted to address scheduling concerns. Heuristic methods exhibit a light execution time but fail to sustain high solution quality for solving complex problems. Improvement methods deliver high-quality solutions but are associated with high computational effort. To mitigate the individual limitations of both methods, scholars started investigating hybrid solution methods that may combine their advantages. The individual limitations of the conventional methods, in addition to the complex nature of the scheduling problem, result in a poor practical adoption of presented scheduling methods. Recently, Deep Reinforcement Learning (DRL) methods substantiated a fundamental breakthrough and have been successfully adopted in the gaming domain. The foundational design of DRL methods includes optimization elements, making them suitable for addressing scheduling problems. Therefore, a scheduling methodology is presented that efficiently facilitates the combined utilization of heuristic, metaheuristic, and deep reinforcement learning methods to solve scheduling problems in cloud and manufacturing environments. Since most industrial scheduling problems are subject to multi-objective optimization measures, the methodology addresses scheduling concerns considering system efficiency and customer satisfaction objective measures. Parallelization and scalability technologies have been adopted to design and develop the presented artifact to achieve computational efficiency. To conduct the research systematically, the proposed methodology relies on the Design Science Research (DSR) framework and adheres to its fundamental design activities. The identified research gap, validated by the theoretical findings and the needs of application environments, is translated into functional and non-functional requirements of the artifact. The derived functional and non-functional requirements are then mapped into functionality layers to define the overall functional structure of the proposed methodology. The artifact is designed using component and modular design practices to address single-stage and multi-stage scheduling problems in cloud and manufacturing, respectively. The combined utilization of simulation, heuristic, improvement, and deep reinforcement learning methods was achieved by designing and developing a scheduling data model, several optimization encoding models for scheduling problems, DRL scheduling models, and a DRL evaluation model. The developed scheduling data model facilitates flexible instantiation of the methodology to address single-stage or multi-stage scheduling problems considering multiple objective mea- sures. The subsequent implementation of the artifact design is presented as a proof of concept and evaluated based on the DRS framework. The developed prototype is designed to support a multi-architecture infrastructure deployment and execution. The simulation and heuristic, as well as the artifact’s optimization and machine learning subsystems, are developed and deployed with parallelization and scalability features. The developed prototype is evaluated on multiple use cases to address multi-objective scheduling problems in cloud and manufacturing environments. Its utility was evaluated for solving real multi-stage scheduling problems in manufacturing environments. Compared to related works, the artifact’s optimization and DRL methods delivered, on average, 31.7% improved solutions in minimizing the system efficiency objective measures. The solutions also minimized penalties and delays by 33.3%, contributing to higher customer satisfaction.

Planungsabläufe sind entscheidende Prozesse, die die Gesamtleistung von Cloud- und Produktionsumgebungen maßgeblich beeinflussen. Daher beschäftigen sich Praktiker und Wissenschaftler seit Jahrzehnten intensiv mit Planungsproblemen. Die meisten Maschinenplanungsprobleme gelten als NP-schwere Optimierungsprobleme, weshalb häufig Heuristiken und Optimierungsmethoden zur Lösung eingesetzt werden. Heuristische Methoden zeichnen sich durch kurze Ausführungszeiten aus, können jedoch bei komplexen Problemen keine hohe Lösungsqualität garantieren. Im Ge- gensatz dazu liefern Optimierungsmethoden hochwertige Lösungen, sind jedoch mit erheblichem Rechenaufwand verbunden. Um die Nachteile beider Methoden zu überwinden, haben Wissenschaftler hybride Lösungsmethoden erforscht, die die Vorteile beider Ansätze kombinieren. Aufgrund der individuellen Einschränkungen herkömmlicher Methoden sowie der Komplexität von Maschinenplanungsproblemen finden diese Ansätze jedoch selten praktische Anwendung. In den letzten Jahren haben Methoden des Deep Reinforcement Learning (DRL) bedeutende Fortschritte erzielt und wurden erfolgreich im Gaming-Bereich eingesetzt. Das Grundkonzept von DRL-Methoden beinhaltet Optimierungselemente, was sie für die Lösung von Maschinenplanungsproblemen besonders geeignet macht. Deshalb wird eine neue Scheduling-Methodik vorgestellt, die eine effiziente und präzise Kombination von heuristischen, metaheuristischen und Deep Reinforcement Learning-Methoden zur Lösung von Maschinenplanungsproblemen in Cloud- und Produktionsumgebungen ermöglicht. Da die meisten industriellen Maschinenplanungsprobleme multikriteriellen Optimierungsmaßnahmen unterliegen, berücksichtigt diese Methodik sowohl die Systemeffizienz als auch die Kundenzufriedenheit als Zielgrößen. Bei der Konzeption und Entwicklung des vorgestellten Artefakts wurden Technologien zur Parallelisierung und Skalierbarkeit genutzt, um eine hohe Recheneffizienz zu gewährleisten. Um die Forschung systematisch durchzuführen, stützt sich die vorgeschlagene Methodik auf den Rahmen der Design Science Research (DSR) und folgt deren grundlegenden Designaktivitäten. Die identifizierte Forschungslücke, die durch theoretische Erkenntnisse und praktische Bedürfnisse validiert wurde, wird in funktionale und nicht-funktionale Anforderungen an das Artefakt übersetzt. Diese Anforderungen werden dann in verschiedene Funktionalitätsschichten abge- bildet, um die gesamte funktionale Struktur der Methodik zu definieren. Das Artefakt wird unter Verwendung komponenten- und modularer Techniken entwickelt, um sowohl einstufige als auch mehrstufige Maschinenplanungsprobleme in Cloud- und Fertigungsumgebungen zu lösen. Die integrierte Nutzung von Simulations-, Heuristik-, Verbesserungs- und Deep Reinforcement Learning-Methoden wurde durch den Entwurf und die Entwicklung eines Datenmodells, mehrerer Optimierungskodierungsmodelle für Maschinenplanungsprobleme, DRL-modelle und eines DRL-Evaluierungsmodells erreicht. Die anschließende Implementierung des Artefaktdesigns wird als Proof of Concept vorgestellt und auf der Grundlage des DRS-Frameworks evaluiert. Der entwi- ckelte Prototyp ist so konzipiert, dass er den Einsatz und die Ausführung einer Multi-Architektur-Infrastruktur unterstützt. Die Simulation und Heuristik sowie die Teilsysteme für Optimierung und maschinelles Lernen des Artefakts werden mit Parallelisierungs- und Skalierungsfunktionen entwickelt und eingesetzt. Der entwickelte Prototyp wurde anhand mehrerer Anwendungsfälle evaluiert, um multikriteielle Maschinenplanungsprobleme in Cloud- und Produktionsumgebungen zu lösen. Sein Nutzen wurde für die Lösung realer mehrstufiger Maschinenplanungsprobleme in Produktionsumgebungen evaluiert. Im Vergleich zu verwandten Arbeiten lieferten die Optimierungs- und DRL-Methoden des Artefakts im Durchschnitt 31, 7% bessere Lösungen bei der Minimierung der Makepan und der Gesamtzahl der Hauptrüstzeiten, was zu einer höheren Systemeffizienz beitrug. Die Lösungen minimierten auch Penalties und Lieferterminverzögerungen um 33, 3%, was zu einer höheren Kundenzufriedenheit beitrug.