Sommersemester 2020 und Wintersemester 2020/2021
Bei vielen Automobilzulieferern ist die wöchentliche Planung, wann welcher Artikel am besten auf welcher Maschine gefertigt werden soll, noch nicht automatisiert. Statt diese Maschinenbelegungsplanung einem System zu überlassen, entscheidet ein Produktionsplaner manuell über die Zuordnung der Artikel zu den einzelnen Maschinen. Ein Grund für die nicht automatisierte Erstellung von Produktionsplänen ist, dass für jede Automatisierung eines vorliegenden Praxisproblems mit seinen zahlreichen spezifischen Charakteristika passende Lösungsalgorithmen einzeln ausgewählt, angepasst und implementiert werden müssen. Lösungsalgorithmen, die in der Praxis oft angewendet werden, sind Heuristiken und Metaheuristiken. Für jede Klasse von Praxisproblemen eignen sich andere Heuristiken besonders gut, Metaheuristiken können hingegen auf viele verschiedene Probleme angewendet und wiederholt hintereinander ausgeführt werden. Um eine möglichst hohe Lösungsgüte mit möglichst wenig Rechenzeit zu erhalten, ist es ratsam, für die vorliegenden Probleme Heuristiken und Metaheuristiken zu vergleichen oder in Kombination hintereinander auszuführen. Diese Tests und Kombinationsmöglichkeiten bedeuten zusätzlichen Implementierungs- und Testaufwand. Durch die richtige Auswahl und eine Aneinanderreihung von wenigen Standard(meta)heuristiken lassen sich für eine Vielzahl von Maschinenbelegungsproblemen schon gute Ergebnisse erzielen.
Die Zuordnungsproblematik, welche Kombination von Heuristiken oder Metaheuristiken für welches Praxisproblem bezüglich Lösungsgüte und Rechenzeit gewählt werden sollte, stellt eine kombinatorische Herausforderung dar. Zur automatisierten Lösung dieser Aufgabe bietet sich unter anderem der Einsatz von Ansätzen aus der Software-Synthese an. Ein solcher Ansatz wurde bereits am Lehrstuhl 14 in Form des Synthese-Frameworks Combinatory Logic Synthesizer (CLS) entwickelt. Das CLS ist in der Lage Software aus einer Sammlung von einzelnen Komponenten zu konstruieren. Es ist möglich, Komponenten semantisch zu spezifizieren, wodurch das CLS in die Lage versetzt wird, die jeweils geeigneten Komponenten auszuwählen. Das CLS erzeugt dabei alle möglichen Kombinationen von Heuristiken automatisch. Es bietet sich folglich der Einsatz eines solchen Frameworks mit dem Zweck der automatischen Generierung von Maschinenbelegungsalgorithmen an. Im Anschluss an den Generierungsprozess müssen die erzeugten Kombinationen dann bewertet und die jeweils beste muss ausgewählt werden. Dazu ist entweder die Implementierung einer Bewertungsfunktion oder eines Lernverfahrens notwendig, mit deren Hilfe die beste generierte Lösungsmethode sowie die bestmöglichen Parametereinstellungen der (Meta-)Heuristiken hinsichtlich der Lösungsgüte und der Rechenzeit ausgewählt werden können.
Ziel der Projektgruppe (PG) ist es, auf Basis des erwähnten Synthese-Frameworks CLS ein Tool zur automatischen Erzeugung von Maschinenbelegungsplänen zu entwickeln, das Heuristiken der Maschinenbelegungsplanung auswählt, kombiniert, bewertet und so den Anwender schlussendlich mit geeigneten Algorithmen in der Maschinenbelegungsplanung unterstützt. Dazu ist es zunächst notwendig, bestehende Heuristiken und Algorithmen auf ihre Komponentisierbarkeit hin zu untersuchen und im CLS zu implementieren. Da es hier verwandte Vorarbeiten im Rahmen von Abschlussarbeiten gibt, ist dies ein einfacher Einstieg in die Realisierung. Fragen der Maschinenbelegungsplanung, die mit Hilfe der Implementierung beantwortet werden sollen, sind:
Aus der langjährigen Kooperation zwischen den Betreuern und den beteiligten Lehrstühlen sind bereits einige Vorarbeiten und Technologien hervorgegangen, welche für die Aufgabenstellung der PG genutzt werden können. Dazu gehören unter anderem ein Synthese-Framework, Prototypen von Schnittstellen zu einschlägiger Fachsoftware sowie Implementierungen zu Maschinenbelegungsalgorithmen, begleitende Simulationen im Fabrikkontext und eine umfangreiche in der Praxis erhobene Datenbasis. Die PG kann von diesen Arbeiten profitieren, auf diesen aufbauen und die vorhandenen Technologien weiterentwickeln.
Beim Combinatory Logic Synthesizer ((CL)S) handelt es sich um ein komponentenbasiertes Synthese-Framework. Es eignet sich insbesondere zur Handhabe von unvorhersehbaren Variabilitäten, was den Einsatz für die Synthese von Maschinenbelegungsalgorithmen in der Produktionsplanung empfiehlt. (CL)S ermöglicht die Spezifizierung von Komponenten, deren Implementierung sowie die Modellierung von Variabilität und die automatische Komposition von Komponenten unter Beachtung der modellierten Variabilitätsregeln. All dies geschieht innerhalb des Frameworks auf eine einheitliche Weise. Das Framework bietet demnach eine solide Basis zur Abbildung und Spezifikation einzelner Heuristiken und Algorithmen, und eignet sich zudem als technologische Grundlage für die automatische Zusammenstellung der Komponenten.
In solche Komponenten lassen sich Algorithmen zur Maschinenbelegungsplanung aufteilen. Metaheuristiken zeichnen sich beispielsweise dadurch aus, dass sie mit ähnlicher äußerer Algorithmik auf verschiedenartige Optimierungsprobleme (wie z. B. Maschinenbelegungsprobleme) angewendet werden können. Die Metaheuristik entscheidet darüber, mit welcher Systematik eine iterative Verbesserung oder Verschlechterung von Zielfunktionswerten akzeptiert wird. Die Zielfunktion an sich stellt eine weitere Komponente dieser Algorithmen dar. Pro Zielfunktion sowie pro Kategorie des Optimierungsproblems sind innerhalb der Metaheuristiken spezielle Nachbarschaftsstrategien besonders effektiv und jedes Maschinenbelegungsproblem aus der Praxis hat seine eigenen Nebenbedingungen und weitere Charakteristika, für die die Algorithmen angepasst werden sollten.
Im Rahmen des Graduiertenkollegs 2193 wurde in Zusammenarbeit mit einem Kooperationspartner eine Datenbank für eine Maschinenbelegungsplanung aufgebaut. Es handelt sich bei dem zugrundeliegenden Praxisfall um einen zweistufigen hybriden Flowshop mit maschinen- und artikelabhängigen Produktions- und Umrüstzeiten sowie artikelabhängigen Ausschussraten [9]. Diese Daten können so modifiziert werden, dass verschiedene praxisnahe Beispiele von Maschinenbelegungsproblemen geformt werden und viele der Kategorien von Maschinenbelegungsproblemen entstehen, die Pinedo [8] beschreibt. Bisher wurden für den vorliegenden Praxisfall am Lehrstuhl 4 Algorithmen mit der Zielfunktion „Minimierung der Bearbeitungszeit“ erstellt. Ebenfalls als praxisrelevant hat sich die Minimierung des Lagerbestandes zwischen den Bearbeitungsstufen herausgestellt, die die PG ebenfalls berücksichtigen könnte. Zudem enthält das beschriebene Praxisproblem eine Vielzahl von Nebenbedingungen, die berücksichtigt oder ausgelassen werden können, sodass je nach Anzahl der Teilnehmer und Verlauf der PG genug interessantes Material zur praxisnahen Durchführung der PG und für Erweiterungsmöglichkeiten zur Verfügung steht.