Solving the flexible job-shop scheduling problem based on the hierarchical collaborative evolution multi-objective artificial raindrop algorithm

Im Herzen der modernen Fertigung spielt sich eine stille Spannung zwischen Geschwindigkeit, Kosten und der Umwelt ab. Fabriken müssen Waren schnell produzieren, um wettbewerbsfähig zu bleiben, doch sie stehen auch unter dem wachsenden Druck, weniger Energie zu verbrauchen und weniger Geld für jedes einzelne hergestellte Teil auszugeben. Dieser Balanceakt wird als Zeitplanung (Scheduling) bezeichnet. Stellen Sie sich eine Werkstatt vor, in der Dutzende verschiedener Produkte gebaut werden müssen und jedes Produkt eine Reihe von Schritten erfordert, die an spezifischen Maschinen durchgeführt werden. In einer einfachen Fabrik hat ein Schritt möglicherweise nur eine einzige Maschine, die ihn ausführen kann. In einer flexiblen Werkstatt kann ein einzelner Schritt jedoch von einer beliebigen der mehreren verfügbaren Maschinen ausgeführt werden, wobei jede ihre eigene Geschwindigkeit, ihren eigenen Energieverbrauch und ihre eigenen Kosten hat. Die Herausforderung besteht darin, zu entscheiden, welche Maschine welchen Schritt in welcher Reihenfolge ausführt. Wenn der Plan schlecht ist, steht die Fabrik still, Energie wird verschwendet und die Kosten geraten außer Kontrolle. Wenn der Plan gut ist, läuft die Fabrik wie ein gut geöltes Uhrwerk, erledigt die Arbeit schneller und gibt dabei weniger aus.

Über Jahrzehnte hinweg haben Forscher versucht, dieses Rätsel mithilfe von Computeralgorithmen zu lösen, die die Natur nachahmen, wie etwa die Art und Weise, wie Vögel flocken oder Ameisen Nahrung finden. Diese Methoden sind gut darin, brauchbare Lösungen zu finden, aber sie stoßen oft an ihre Grenzen, wenn das Problem zu komplex wird oder wenn die Ziele miteinander in Konflikt stehen. Ein Plan, der die Zeit minimiert, verbraucht vielleicht zu viel Strom, während ein Plan, der Energie spart, vielleicht zu lange dauert. Das Ziel ist es, einen Satz von „bestmöglichen“ Kompromissen zu finden, bei denen man ein Ziel nicht verbessern kann, ohne ein anderes schlechter zu machen. Dies ist die zentrale Herausforderung, mit der sich ein Forschungsteam der Hebei University of Engineering befasst hat, das eine neue Methode entwickelt hat, um sich in dieser schwierigen Landschaft zurechtzufinden.

Die Forscher konzentrierten sich auf eine spezifische Art von Zeitplanungsproblem, bei dem die Fabrik drei konkurrierende Ziele jonglieren muss: alle Aufträge so schnell wie möglich abzuschließen, den Gesamtenergieverbrauch so gering wie möglich zu halten und die Gesamtkosten der Produktion so niedrig wie möglich zu halten. Um dies anzugehen, entwickelten sie einen neuen Computeralgorithmus namens „hierarchical co-evolutionary multi-objective artificial raindrop algorithm“. Der Name leitet sich von der Art und Weise ab, wie der Algorithmus das Verhalten von Regentropfen nachahmt, die über eine Landschaft fallen und fließen. In der Natur sammeln sich Regentropfen, fließen in Bäche und vereinigen sich schließlich zu Flüssen. Die Forscher nutzen diese Idee, um zu simulieren, wie potenzielle Lösungen für das Planungsproblem sich im Laufe der Zeit bewegen und verbessern. Die ursprüngliche Version dieser „Regentropfen“-Methode hatte jedoch Einschränkungen; sie startete manchmal mit einem schlechten Satz an Ideen und hatte Schwierigkeiten, die Suche nach neuen, breiten Lösungen mit der Verfeinerung guter Lösungen in Einklang zu bringen.

Um diese Probleme zu lösen, führten die Forscher ein System der „hierarchischen Koevolution“ ein. Anstatt jede potenzielle Lösung gleich zu behandnehmen, sortierten sie diese in drei verschiedene Gruppen basierend darauf, wie gut und wie einzigartig sie im Vergleich zu den anderen waren. Die erste Gruppe, die „Exploratoren“, bestand aus den einzigartigsten und vielfältigsten Lösungen. Diesen wurde eine Strategie zugewiesen, die darauf ausgelegt war, weit und breit nach neuen Möglichkeiten zu suchen, um sicherzustellen, dass die Suche nicht in einem kleinen Bereich stecken bleibt. Die zweite Gruppe, die „Exploitatoren“, enthielt die stärksten Lösungen, die sich sehr ähnlich waren. Diesen wurde eine andere Strategie gegeben, die auf Feinabstimmung und Politur fokussiert war, um tief in die vielversprechendsten Bereiche einzudringen und das letzte Quäntchen Verbesserung herauszuholen. Die dritte Gruppe, das Basis-Update-Team, behielt die ursprüngliche, stetige Methode des Regentropfen-Algorithmus bei, um einen stabilen Fluss von Ideen aufrechtzuerhalten. Indem sie diese drei Gruppen gemeinsam evolvieren ließen, konnte der Algorithmus neues Terrain erschließen und gleichzeitig die besten gefundenen Ideen perfektionieren.

Die Forscher testeten diese neue Methode anhand eines Standard-Sets von zehn schwierigen Planungsproblemen, den sogenannten Brandimarte-Benchmarks, die in ihrer Größe von kleinen Werkstätten bis hin zu großen, komplexen Fabriken variieren. Sie verglichen ihren neuen Regentropfen-Algorithmus mit mehreren anderen populären Methoden, die die Natur nachahmen, einschließlich solcher, die auf Partikelschwärmen und Mistkäfern basieren. Die Ergebnisse zeigten, dass die neue Regentropfen-Methode die anderen Methoden konsequent übertraf. In Bezug auf die Zeit, die benötigt wurde, um alle Aufträge abzuschließen, fand die neue Methode in sieben von zehn Testfällen die schnellsten Zeitpläne und teilte sich in den verbleibenden drei Fällen den Spitzenplatz. Sie gelang es ihr auch, den Energieverbrauch und die Kosten in den meisten Szenarien niedriger zu halten als die anderen Methoden.

Über das Finden schnellerer Zeitpläne hinaus produzierte die neue Methode eine wesentlich bessere Sammlung von Abwägungsoptionen. In einem Problem mit mehreren Zielen gibt es selten eine einzige „perfekte“ Antwort; stattdessen gibt es eine Reihe guter Optionen. Die Forscher fanden heraus, dass ihr Algorithmus einen Satz von Lösungen generierte, die gleichmäßiger verteilt waren und ein breiteres Spektrum an Möglichkeiten abdeckten als die anderen Methoden. Dies bedeutet, dass einem Fabrikmanager ein reichhaltigeres Menü an Entscheidungen zur Verfügung steht, egal ob er Geschwindigkeit, Energieeinsparung oder Kosten priorisieren möchte. Die Studie beinhaltete auch Tests, um zu sehen, welche Teile der neuen Methode am wichtigsten waren. Als die Forscher die spezielle Art und Weise entfernten, mit der der Algorithmus seine Suche startete, oder wenn sie die Fähigkeit wegnahmen, den Fluss der „Regentropfen“ anzupassen, sank die Leistung. Dies bestätigte, dass jeder Teil ihres neuen Designs eine notwendige Rolle für den endgültigen Erfolg spielte.

Die Studie kommt zu dem Schluss, dass dieser hierarchische Ansatz ein leistungsstarkes neues Werkzeug für die grüne Fertigung bietet. Durch die Balance zwischen der Notwendigkeit, neue Ideen zu erforschen, und der Notwendigkeit, die besten zu verfeinern, kann der Algorithmus die komplexen, widersprüchlichen Anforderungen der modernen Produktion bewältigen. Während die aktuellen Tests in einer simulierten Umgebung durchgeführt wurden, in der Maschinen niemals ausfallen und Aufträge niemals verspätet eintreffen, deutet das Ergebnis auf einen starken Weg nach vorne hin. Die Methode bietet einen Weg, um Zeitpläne zu erstellen, die nicht nur effizient, sondern auch wirtschaftlich und ökologisch sinnvoll sind, was Fabriken hilft, sich auf eine nachhaltigere Zukunft zuzubewegen, ohne Geschwindigkeit oder Gewinn zu opfern.