Reihenfolgeplanung in der Werkstattfertigung durch systematische Lösungsraumnavigation
Zusammenfassung der Projektergebnisse
Durch die Ausrichtung der Produktion auf Konzepte wie Industrie 4.0 verändern sich Rahmenbedingungen zahlreicher Verfahren für die Reihenfolgeoptimierung der Werkstattfertigung. Hierbei kann sich die Reihenfolge je nach Arbeitsauftrag individuell ändern. Zur Reihenfolgeproblematik existieren viele unterschiedliche Lösungsansätze, während die Lösungsraumnavigation selbst noch nicht untersucht worden ist. Es fehlt die Verfeinerung einer Optimierungsstrategie auf Basis der systematischen Nutzung des dynamisch gewonnenen Wissens über den Lösungsraum. Ein ungültiger oder extrem ungünstiger Reihenfolgeplan kann durch Vertauschen zweier Arbeitsschritte durchaus zu einem sehr guten Plan führen. Zum Auffinden von derartig versteckten, guten Lösungen eignen sich Verfahren, die nicht berechenbar im Lösungsraum liegen. Mutation und Rekombination können als derartige Navigationsstrategien verstanden werden. Durch sie werden ausgehend von einer Ausgangslösung neue Punkte im Lösungsraum angesteuert. Dieses nicht berechenbare Suchen durch genetische Strategien kann durch gezielte Navigationsstrategien nachgebildet werden. Die Herausforderung bestand darin, den Charakter des Unberechenbaren nicht nur zu erhalten, sondern idealtypisch bzw. mit beliebiger Intensität zu emulieren. In diesem Projekt ist ein Ansatz des systematischen Lösungsraumindexierung und -navigation erarbeitet und untersucht worden. Die Menge aller möglichen (und realisierbaren) Lösungen ist zunächst über unterschiedliche Ordnungsansätze „begehbar” und durchsuchbar gemacht worden. Hierfür wird ein mehrdimensionaler Raum aufgespannt, in dem die Lösungspunkte nach einer einheitlichen Systematik angeordnet sind, sodass sie durch eine Indexzahl oder durch eine Musterbeschreibung sofort auffindbar und ansteuerbar gemacht werden. Dies ermöglicht die Definition von Pfaden durch den Lösungsraum, bei denen jeweils nur Lösungen mit bestimmten Eigenschaften angesteuert werden. Diese Pfade werden aus Mustern zusammengesetzt, sodass Punkte mit voraussichtlich guten Lösungswerten gezielt ausgesucht und Punkte mit voraussichtlich schlechten Lösungswerten gezielt umgangen werden. Um derartige Muster effizient beschreiben zu können, ist eine spezielle Permutations-Arithmetik entwickelt worden. Die Definition von Sprungmustern über (Dezimal-)Zahlen hatte sich als ineffizient erwiesen, weil die Systematik einer Zahlenfolge nicht der Systematik von Sequenzpermutationen entspricht und somit diese Repräsentationsformen nicht adäquat konvertiert werden können. Durch die Permutations-Arithmetik ist ein direktes Rechnen mit Sequenzen möglich, sodass Sprungmuster problemadäquat definiert werden können. Die Implementierung der Lösungsraumnavigation hat gezeigt, dass die Lösungsraumnavigation als eigenständiges Optimierungsverfahren für Reihenfolgeprobleme genutzt werden kann. Im Vergleich mit klassischen, iterativen Verfahren zeigt sich, dass die Lösungsraumnavigation mit steigender Rechenzeit oder bei steigender Komplexität des Produktionsproblems bessere Ergebnisse liefert. Dies gilt insbesondere für die Breite guter Lösungen, sodass nicht nur einzelne Top-Lösungen gefunden werden, sondern die Menge der n besten Lösungen im Durchschnitt besser ist. Noch keine Berücksichtigung haben Heuristiken gefunden. Es ist möglich, diese als positive oder negative Muster zu definieren, sodass die Optimierung schon in frühen Iterationsschritten über gute Navigationspfade verfügt und sich diese nicht erst zeitverzögert über die Mustersuche in den Zwischenergebnissen erarbeiten muss.
Projektbezogene Publikationen (Auswahl)
- Marktüberblick Reihenfolgeplanung. Productivity Management, 22(3):43-48, 2017
Weber, Edzard, Anselm Tiefenbacher und Hanna Theuer
- Reihenfolgeplanung im Zeitalter von Industrie 4.0 - Optimierung in der Werkstattfertigung. Productitity Management, 23(1):23-26, 2018
Gronau, Norbert und Edzard Weber
(Siehe online unter https://doi.org/10.30844/3_2018-1_23-26) - Need for Standardization and Systematization of Test Data for Job-Shop Scheduling. Data, 4(1):32, 2019
Weber, Edzard, Anselm Tiefenbacher und Norbert Gronau
(Siehe online unter https://doi.org/10.3390/data4010032) - Solution Space Navigation for Job-shop Scheduling Problems. Technischer Bericht WI-2019-04, Lehrstuhl für Wirtschaftsinformatik, insb. Prozesse und Systeme, Universität Potsdam, 2019
Weber, Edzard, Eduard Schenke, Luka Dorotic und Norbert Gronau
