Minimizing makespan in flow shops with a reinforcement learning like approach : A learning beam search for the no-wait flow shop scheduling problem with release times

Abstract

Maschinenbelgungsplanungsprobleme (FSP) existieren in unterschiedlichen Varianten.Eine dieser Varianten ist das no-wait FSP with release times (NWFSP-RT). Es besteht aus einer Menge an Aufgaben und einer Menge an Maschinen. Beim NWFSP-RT müssen alle Aufgaben in derselben vordefinierten Reihenfolge auf allen Maschinen abgearbeitet werden.Zusätzlich dürfen Aufgaben auf der ersten Maschine erst nach einer gegebenen Release-Zeit beginnen. Anwendungen finden sich in der Stahl- und Lebensmittelproduktion zufinden. Hier können Wartezeiten zu einer Verschlechterung der Qualität führen.Wir verwenden eine Beam Search (BS), d.h. eine Breitensuche mit beschränkter Breite,zum Lösen des NWFSP-RT. Auf jeder Suchebene behält BS nur die besten Knoten. Umzu entscheiden, welche Knoten behalten werden, verwendet BS eine heuristische Funktion(GF). In dieser Arbeit verwenden wir das Learning Beamsearch (LBS) Framework von Huber und Raidl [HR21] um GFs zu lernen. Bei der LBS werden in jeder Iteration Trainingsdaten unter Verwendung der aktuell gelernten GF erzeugt und diese anschließend verwendet um das neuronale Netzwerk (NN) zu trainieren.Wir präsentieren zwei neuartige graphbasierte NN Typen inklusive Feature-Vektoren.Die NN Typen aggregieren Daten aller Aufgaben einer Instanz und der nähesten benachbarten Aufgaben jeder Aufgabe. Unter den Features ist eine neuartige Methode zur Berechnung unterer Schranken (ITLB) für das NWFSP-RT enthalten. Die beschriebenen Algorithmen und NN Typen wurden von uns implementiert und auf Vergleichsinstanzen,sowie zufälligen Instanzen evaluiert. Im Zuge der Evaluierung wurden auch statistische Signifikanztests durchgeführt. Die Ergebnisse zeigen, dass BS in Kombination mit den zwei neuartigen NN Typen in neun und zehn von 16 Konfigurationen signifikant bessere Ergebnisse erzielt als BS in Kombination mit ITLB verglichen auf Testinstanzen gleicher Größe, auf welcher die NN Typen trainiert wurden. Des Weitern generalisiert mindestens eine Konfiguration jedes der vier NN Typen gut über die Anzahl an Aufgaben, verglichen mit den besten bekannten Ergebnissen aus [Pou+20]. Während unserer Tests liefern die NN Typen für einzelne Instanzen bessere Ergebnisse als die besten bekannten Ergebnisse trotz der Einschränkung, dass die Tests mit einer kleineren maximalen Breite und ohne lokaler Suche durchgeführt wurden. Insgesamt war einer unserer Ansätze, evaluiert mit einer kleineren Breite als in [Pou+20], auf 11 von 46 getesteten Instanzklassen im Durchschnitt besser als die besten bekannten Ergebnisse und auf 43 von 46 Instanzklassen besser als BS ohne lokale Suche von [Pou+20].

The flow shop problem (FSP) is a scheduling problem with many variants. One variantis the no-wait FSP with release times (NWFSP-RT). It consists of a set of jobs and a setof machines. It further imposes the constraints that jobs must pass all machines in apredefined order, the jobs are not allowed to wait on a machine until being processed, andjobs may only start processing on the first machine when their release time is exceeded.The goal is to find a schedule optimizing the desired objective, i.e., the makespan. TheNWFSP-RT has applications in steel or food production where the product is not allowedto wait before being further processed to avoid degradation.Beam search (BS), a limited width breadth-first search technique, has shown to be an effective heuristic in finding proper solutions to optimization problems within a limited time. Only the best nodes are kept and further branched on at every layer when the number of nodes exceeds a specific limit. To decide which nodes to keep, BS uses a guidance function (GF). We build upon the learning beam search (LBS) framework proposed by Huber and Raidl [HR21] to learn GFs. The LBS framework uses an iterative approach. In every iteration, training data is generated with a BS guided by the currentlylearned GF, and the neural network (NN) is trained to approximate the training data.We propose two novel NN types, inspired by graph neural networks, that aggregate data over all individual jobs in a problem instance and their nearest neighbors. Further, we present feature sets for the NN types, including a novel lower bound, called ITLB, for the NWFSP-RT. We implement the algorithms, evaluate them over benchmark setsand random test instances, and perform statistical tests. The results show that a BSguided by two of our NN types produces significantly better results in nine and ten outof 16 configurations, respectively, than a BS guided by ITLB alone when run on similar instance sizes as the NNs were trained. The evaluation of the generalization abilities ofthe NNs shows that for each of the four NN types, at least one configuration generalizes well over the number of jobs compared with the best-known results. Our approaches frequently improve the state-of-the-art on even though running with a smaller beam width and without local search compared to the BS from Pourhejazy et al. [Pou+20] that represented the state-of-the-art so far. Overall, one of our approaches, evaluated with smaller beam width than in [Pou+20], was able to outperform the state-of-the-art on 11out of 46 tested instance classes and to outperform the BS from [Pou+20] without local search on 43 out of 46 tested instance classes on average.