Produktionsplanungsprobleme in modernen industriellen Umgebungen sind durch eine große Anzahl von Arbeitsschritten und komplexe Randbedingungen gekennzeichnet. Um auf dem Markt wettbewerbsfähig zu bleiben, ist es für Unternehmen entscheidend, in kurzer Zeit effiziente und präzise Produktionspläne zu erstellen. Zur Bewältigung dieser Herausforderungen werden innovative Ansätze erforscht oder bestehende Lösungsansätze weiter verbessert, um optimale Ergebnisse zu erreichen. Die Tabu-Suche ist eine beliebte Metaheuristik zur Lösung komplexer Optimierungsprobleme, die auch in der Produktionsplanung angewendet wird. In diesem Artikel wird eine Erweiterung dieses Algorithmus vorgestellt, die eine signifikante Leistungsverbesserung ermöglicht. Das zentrale Konzept dieser Erweiterung besteht darin, während der Suche wertvolle Lösungsinformationen zu sammeln und vielversprechende Lösungsmuster zu identifizieren. Wenn es notwendig wird, das Suchverhalten der Tabu-Suche zu variieren, um ein breiteres Spektrum des Lösungsraums zu erkunden, werden diese identifizierten, vielversprechenden Lösungsteile beibehalten und in den weiteren Suchprozess integriert.
Die genaue und effiziente Ableitung von Produktionsplänen ist in der heutigen Fertigungslandschaft von entscheidender Bedeutung. Die zugrunde liegenden Produktionsplanungsprobleme sind oft schwierige Optimierungsprobleme unterschiedlicher Größe. Die verfügbaren Ansätze für deren Lösung lassen sich grob in exakte Methoden und Metaheuristiken einteilen. Exakte Algorithmen finden immer eine optimale Lösung und können deren Optimalität beweisen. Die Rechenzeit kann aber deutlich mit der Größe des Problems steigen. Obwohl sie nicht garantieren, dass eine optimale Lösung gefunden wird, bieten Metaheuristiken einen guten Kompromiss zwischen Lösungsqualität und Rechenzeit sowie eine hohe Flexibilität bei der Umsetzung der Restriktionen des Optimierungsproblems.
Tabu-Suche ist eine Metaheuristik, die erstmals 1986 von Fred W. Glover vorgestellt und 1989 formalisiert wurde. Sie galt schon kurz darauf, zusammen mit Simulated Annealing und genetischen Algorithmen, als äußerst vielversprechend für praktische Anwendungen [1]. Tabu-Suche hat seither zahlreiche und weit verbreitete erfolgreiche Anwendungen gefunden und wird weiterhin zur Lösung schwieriger kombinatorischer Optimierungsprobleme eingesetzt.
Tabu-Suche geht von einer anfänglichen zulässigen Lösung aus und verwendet lokale Suchmethoden, um den Lösungsraum zu erkunden. Dies erfolgt, indem sie sich von einer zulässigen Lösung zu einer verbesserten Lösung in ihrer Nachbarschaft bewegt. Die Suche endet, wenn ein Abbruchkriterium erfüllt ist (z.B. eine maximale Anzahl von Iterationen oder ein Bewertungsschwellenwert), allerdings in den meisten Fällen ohne Garantie für die Lösungsqualität. Lokale Suchmethoden neigen dazu, in suboptimalen Regionen oder Plateaus stecken zu bleiben, in denen keine verbesserten Nachbarn verfügbar sind. Um dieses Problem zu lösen, verwendet die Tabu-Suche Speicherstrukturen mit unterschiedlichen Zeitspannen, die es dem Algorithmus ermöglichen, lokale Minima zu verlassen und neue Regionen des Suchraums zu erkunden. Das einfachste Beispiel hierfür ist die Tabu-Liste, die kürzlich besuchte Lösungen aufzeichnet, um sicherzustellen, dass sie nicht erneut besucht werden (https://en.wikipedia.org/wiki/Tabu_search).
Der Erfolg von Metaheuristiken bei der Erzielung hochwertiger Lösungen für schwierige Optimierungsprobleme hängt von der Entwicklung geeigneter Intensivierungs- und Diversifizierungsstrategien und einem Ausgleichsmechanismus zwischen beiden ab.
Um die beiden Begriffe zu veranschaulichen, nehmen wir das Beispiel eines Urlaubsaufenthalts in einer Stadt, mit dem Ziel das beste Restaurant zu finden. Die Suche wird zunächst auf ein Gebiet von 2 km rund um die Unterkunft beschränkt. Die Intensivierung bedeutet, dass die Restaurants nur in dieser Umgebung angeschaut werden. Nach gewisser Zeit kann man versuchen, auch andere Umgebungen der Stadt zu erkunden, die von der Unterkunft weiter entfernt sind. Dies würde die Suche diversifizieren.
Intensivierung und Diversifizierung sind in anderen Bereichen der Entscheidungsfindung als Exploitation und Exploration anzutreffen. Der Balanceakt zwischen beiden ist bekannt als das Explorations- und Exploitationsdilemma.
Ein erster Versuch, einen Tabu-Search-Algorithmus zu diversifizieren, besteht darin, die Größe der Tabu-Liste zu ändern. Für einige kleine Anwendungen ist dies alles, was nötig ist. Bei komplizierteren Anwendungen sind wirksame Diversifizierungsstrategien jedoch auf ein längerfristiges Gedächtnis angewiesen. Ein möglicher Ansatz basiert auf dem Grundgedanken, dass durch die Vornahme nur kleiner Änderungen an der Lösung in jeder Iteration möglicherweise keine anderen vielversprechenden Bereiche des Lösungsraums besucht werden. Sie verwenden stattdessen sehr große Verschiebungen, die bis zu 30-40% des Lösungskandidaten neu anordnen können. Bei diesen Ansätzen handelt es sich um „remove-insert“-Operationen, die auch als „destroy-and-repair“-Operationen bezeichnet werden:
In [2] wurde ein Optimierungsframework, basierend auf Tabu-Suche, für die Lösung von realen Scheduling-Problemen mit komplexen Restriktionen und dynamischen Eigenschaften vorgeschlagen, das leicht an verschiedene Scheduling-Fragestellungen angepasst werden kann. Dieser hochgradig erweiterbare Tabu-Suche-Algorithmus wurde von der RISC Software GmbH erfolgreich zur Lösung von Produktionsplanungsproblemen eingesetzt.
Das zugrundeliegende Produktionsplanungsproblem beinhaltet die Reihenfolge von Arbeitsschritten und deren Zuteilung auf Maschinen. Diese Arbeitsschritte sind durch Vorgänger/Nachfolger-Beziehungen verbunden und dürfen nicht durch andere Arbeitsschritte unterbrochen werden. Sie haben eine Menge kompatibler Maschinen und maschinenabhängige Kapazitätsbedarfe, Rüst-, Bearbeitungs- und Abrüstzeiten. Zusätzlich können sie Überlappungen, Wartezeiten und Transportzeiten definiert haben.
Abbildung 1: Neun Arbeitsschritte, in fünf Aufträge, und zwei Maschinen (oben) und eine mögliche Zuteilung auf Maschinen (unten)
Die Größe der mit dem Tabu-Suche Framework gelösten Produktionsplanungsprobleme reicht von 850 Arbeitsschritte bis zu etwa 20.000 Gesamtarbeitsschritte und von etwa 50 Maschinen bis zu 110 Maschinen. Eine der Herausforderungen bei der Lösung solcher großen Scheduling-Probleme mit einem metaheuristischen Ansatz ist der Entwurf einer Diversifikationsstrategie, die es ermöglicht, vielversprechendere Bereiche des Lösungsraums ausreichend schnell und auf intelligente Weise zu erreichen.
Das Memory-Based Perturbation Framework (MBP) ist eine Erweiterung des bestehenden Tabu-Suche-Optimierungsframeworks und besteht aus einer Diversifikationsstrategie mit Lösungsgedächtnis [4]. Konkret enthält es zwei Operatoren mit verschiedenen Parametern, die im ersten Schritt Teile der Lösungen als vielversprechend identifizieren. Die anderen Lösungsteile werden in folgenden Schritten entfernt und nach einem bestimmten Mechanismus wieder hinzugefügt. Das Framework hat sich als effektiv erwiesen, um das beschriebene Scheduling-Problem unterschiedlicher Größe zu lösen.
Abbildung 2: Die ersten drei und der letzte Arbeitsschritt wurden als vielversprechende Lösungsteile identifiziert, die anderen Arbeitsschritte werden entfernt und wieder hinzugefügt (unten ist der dadurch resultierende Plan).
Die Hauptkomponenten dieses Frameworks werden im Folgenden kurz beschrieben:
Die Motivation für dieses Framework war die Lösung realer, dynamischer Scheduling-Probleme mit umfangreichen Restriktionen, wie sie von einem Industriepartner der RISC Software GmbH bereitgestellt wurden. Das MBP-Framework wurde auf einer solchen Instanz mit 905 Arbeitsschritte und 67 Maschinen evaluiert und hat sich als effektiv erwiesen. Die zwei umgesetzten Operatoren des MBP-Frameworks, mit bestmöglichen Parametereinstellungen, bringen erhebliche Verbesserungen der berücksichtigten Zielfunktionen, siehe Abbildung 3 für ein solches Beispiel.
Abbildung 3: Der Verlauf eines Zielfunktionswertes für den realen Anwendungsfall aus der Industrie für die zwei neuen Operatoren des Memory-Based Perturbation Frameworks (mit rot und grün gezeichnet) im Vergleich zu zwei anderen verfügbaren Operatoren.
Die vielversprechenden Ergebnisse bilden die Grundlage für weitere Anwendungen des Tabu-Search-Algorithmus mit dem MBP-Framework auf andere reale Planungsprobleme. Mit größerem Umfang und komplexeren Zielfunktionen, zielen diese Planungsprobleme auf andere relevante Ziele der Produktion ab.
Die Digitalisierung der Produktion bringt neben all ihren Vorteilen auch eine erhöhte Komplexität der Scheduling-Probleme und die Notwendigkeit intelligenter Lösungen zur Bewältigung dieser Herausforderungen mit sich. Lösungsansätze basierend auf Metaheuristiken wie die Tabu-Suche finden in diesem Bereich nach wie vor Anwendung. Der Entwurf und die Umsetzung guter Frameworks für Intensivierung und Diversifizierung, sowie die Definition des Trade-Offs zwischen den beiden, sind Schlüsselkomponenten für den Erfolg dieser Lösungsansätze. Die vielversprechenden Ergebnisse der Integration des MBP-Frameworks in den bestehenden Tabu-Suche-Algorithmus zeigen, dass sie sich eignen komplexe Scheduling-Probleme in der Produktion zu bewältigen.
Das MBP-Framework und die Ergebnisse wurden von M. Schlenkrich auf der ICORES 2024 Konferenz (13th International Conference on Operations Research and Enterprise Systems) vorgestellt.
Acknowledgements. Parts of the work described in this paper have been funded by the State of Upper Austria, Austria, as part of the program ,,#upperVISION2030” within the project ,,Secure Prescriptive Analytics“. Project number: Wi-2021-305601/18-Au.
1. F. Glover, E. Taillard, E. de Werra, A user’s guide to tabu search, Annals of Operations Research 41 (1993), 3-28.
2. F. Glover, Z. Lü, J.-K. Hao, Diversification-driven tabu search for unconstrained binary quadratic problems. J. Oper Res (2010), 8:239-253.
3. M. Bögl, A. Gattinger, I, Knospe, M. Schlenkrich, R. Stainko. Real-life scheduling with rich constraints and dynamic properties – an extendable approach. Proceedings of the 2nd International Conference on Industry 4.0 and Smart Manufacturing (ISM 2020), 180:534–544.
4. M. Schlenkrich, M. Bögl, A. Gattinger, I. Knospe, S. Parragh. Integrating Memory-Based Perturbation Operators into a Tabu Search Algorithm for Real-World Production Scheduling Problems. In Proceedings of the 13th International Conference on Operations Research and Enterprise Systems – ICORES; ISBN 978-989-758-681-1; ISSN 2184-4372, SciTePress, 213-220. DOI: 10.5220/0012271900003639
Mathematical Optimization Engineer
Mathematical Optimization Engineer
