Graph-Based Multi-Agent Reinforcement Learning on the Dynamic and Flexible Job-Shop Scheduling Problem

Abstract

Effizientes Scheduling ist eine zentrale Anforderung moderner Smart-Manufacturing-Umgebungen. Produktionsumgebungen sind zunehmend durch wechselnde Anforderungen, flexible Maschinenfähigkeiten und stochastische Ereignisse wie Verzögerungen oder maschinenbezogene Störungen geprägt. Das dynamische und flexible Job-Shop Scheduling Problem (JSSP) modelliert diese Herausforderungen.Diese Arbeit untersucht Graph-basiertes Multi-Agent Reinforcement Learning (MARL) für das dynamische und flexible JSSP. Der Fokus der Arbeit ist zweigeteilt. Erstens wird analysiert, wie sich die architektonischen Hyperparameter und die Regularisierung des von den Agenten verwendeten neuronalen Netzwerks auf die Konvergenz im flexiblen JSSP auswirken. Dafür werden Multi-Layer Perceptron (MLP)- und Convolutional Neural Network (CNN)-Architekturen über verschiedene Instanzgrößen hinweg verglichen. Zweitens wird analysiert, welche dynamischen Faktoren von einem Graph-basierten MARL-Scheduling-Algorithmus gelernt werden können. Die zwei getesteten dynamischenFaktoren sind Verzögerungen, die durch Maschinen verursach twerden, und Verzögerungen, die durch Jobs verursacht werden.Jobs und Maschinen werden durch eine Graph-basierte Repräsentation dargestellt. Die daraus entstehenden Embeddings werden verwendet, um Jobs für Maschinen auszuwählen. Die Performanz der Modelle wird anhand von Makespan und Utilization bewertet und mit einem statischen Modell sowie einfachen regelbasierten Baselines verglichen.Die Ergebnisse zeigen, dass die getesteten MLP-Architekturen besser geeignet waren als die getesteten CNN-Architekturen. Eine Erhöhung der Anzahl der Schichten verbesserte die Ergebnisse nicht. Dies deutet darauf hin, dass die Architektur des neuronalen Netzwerks zur gewählten Zustandsrepräsentation passen muss.Für die dynamischen Experimente zeigen die Ergebnisse einen deutlichen Unterschied zwischen Maschinenverzögerungen und Jobverzögerungen. Maschinenverzögerungen erzeugen ein konsistentes Lernbarkeitssignal. Die dynamische Policy verbessert sich in allen Maschinenverzögerungs-Szenarien gegenüber der statischen Policy und erreicht in den meisten Konfigurationen den niedrigsten Makespan. Jobverzögerungen zeigen ebenfallseine konsistente, aber deutlich schwächere Verbesserung gegenüber der statischen Policy. Diese Verbesserung ist jedoch klein, und die dynamische Policy dominiert die heuristischen Baselines nicht in allen Konfigurationen. Die Ergebnisse deuten daher darauf hin, dass dynamische Faktoren nicht gleichermaßen lernbar sind.

Efficient Scheduling is an essential requirement for modern Smart Manufacturing. Production environments are increasingly characterized by changing requirements, flexible machine capabilities, and stochastic events such as delays or machine-related disturbances. The dynamic and flexible JSSP models these challenges, but its combinatorial search space makes exact solutions infeasible for larger instances.This thesis investigates Graph-based MARL on the dynamic and flexible JSSP. The focus of the work is twofold. First, the thesis analyzes how the architectural hyperparameters and regularization of the neural network used by the agents affect convergence on the flexible JSSP. For this purpose, MLP and CNN architectures are compared across different instance sizes. Second, the thesis analyzes which dynamic factors can be learned by a Graph-based MARL Scheduling algorithm. The two dynamic factors tested are delayscaused by machines and delays caused by jobs.To answer these questions, a Shopfloor environment was implemented that can generate static, flexible, and dynamic JSSP instances. Jobs and machines are represented through a Graph-based state representation. The resulting embeddings are used by the agents to select jobs for machines. The performance of the trained models is evaluated using makespan and utilization and is compared against a static model and simple rule-based baselines.The results show that the tested MLP architectures were more suitable than the tested CNN architectures. The best results were achieved with a comparatively small MLP using two layers and dropout of 0.1. Increasing the number of layers did not improve the results, and CNN architectures did not converge well in the tested setup. This indicates that the neural network architecture must fit the chosen state representation.For the dynamic experiments, the results show a clear difference between machine delays and job delays. Machine delays produced a strong and consistent learnability signal. The dynamic policy improved over the static policy across all machine-delay scenario medians and achieved the best makespan in most machine-delay configurations. Job delays also showed a consistent but much weaker improvement over the static policy. However, this improvement was small and the dynamic policy did not dominate the heuristic baselines in all configurations. This suggests that dynamic factors are not equallylearnable. Learnability depends on where the disturbance is located in the Shopfloor and how actionable the disturbance pattern is for the scheduling policy.