Produktion ohne Verschwendung

Terminplanung ist eine komplizierte Sache, ganz besonders in der Industrie: Welche Maschinen sollen welche Aufgaben in welcher Reihenfolge ausführen, damit alles rechtzeitig fertig wird und weder Zeit noch Ressourcen verschwendet werden? Solche Aufgaben gehören zur Klasse besonders schwieriger Probleme in der Informatik. Es ist meist nicht möglich, jede denkbare Möglichkeit durchzurechnen, um die effizienteste Variante zu ermitteln. Man braucht klug durchdachte Tricks.

Felix Winter entwickelt am Institut für Logic and Computation der TU Wien im Rahmen des "Christian Doppler Labors für Künstliche Intelligenz und Optimierung in Planung und Scheduling" Algorithmen für solche Scheduling-Aufgaben. Dabei verknüpft er abstrakte Konzepte der theoretischen Informatik mit ganz praktischen Anwendungsfällen in der Industrie: Seine Ideen werden nun für die Arbeitsplanung von Lackieranlagen und für die Herstellung von Zahnprothesen eingesetzt. Für seine Leistungen wurde Felix Winter am 14. Oktober 2022 mit dem Resselpreis der TU Wien ausgezeichnet.

In welcher Reihenfolge soll ein Industrieroboter Autoteile lackieren? Die Frage ist komplexer als man auf den ersten Blick meinen könnte: "Es gibt hier eine ganze Reihe von Bedingungen, die gleichzeitig erfüllt werden müssen", erläutert Felix Winter. Bestimmte Anzahlen von Autoteilen müssen bis zu einem bestimmten Zeitpunkt in bestimmten Farben lackiert werden. Jeder Farbwechsel kostet Zeit, daher sollten nach Möglichkeit Objekte gleicher Farbe nacheinander lackiert werden. Außerdem darf nicht jede beliebige Farbe auf jede andere Farbe folgen. Will man das alles berücksichtigen und einen möglichst effizienten Ablaufplan für den nächsten Tag erstellen, stößt man als Mensch rasch an seine Grenzen.

Also soll der Computer nach der optimalen Reihenfolge suchen – aber auch das ist schwierig: "Man unterscheidet in der Informatik zwischen sogenannten P- und NP-Problemen", erklärt Felix Winter. P-Probleme sind vergleichsweise einfach zu lösen. In diese Kategorie fällt etwa das Sortieren von Spielkarten. Je mehr Spielkarten man hat, umso länger dauert das Sortieren. Aber die Zahl der nötigen Schritte wächst bloß mit einer bestimmten Potenz der Kartenanzahl – je nach verwendetem Sortieralgorithmus zum Beispiel mit dem Quadrat der Kartenanzahl.

Es gibt aber auch NP-Probleme – und die sind deutlich herausfordernder. Bei einem NP-Problem steigt nämlich die Zahl der nötigen Schritte zumindest exponentiell an. Und dann kommt man schnell in einen Bereich, der auch für die leistungsfähigsten Computer der Welt nicht mehr zu bewältigen ist. "Scheduling-Aufgaben, wie etwa einen Zeitplan für Lackieranlagen zu erstellen, fällt in die Kategorie dieser schwierigen NP-Probleme", sagt Winter. "Die Zahl der möglichen Produktionsreihenfolgen ist in der Praxis oft höher als zehn hoch fünfhundert – verglichen damit ist die Zahl der Atome im beobachtbaren Universum winzig klein."

In manchen Fällen können Methoden der formalen Logik eingesetzt werden, um den Computer die optimale Lösung finden zu lassen – ähnlich wie man ein Sudoku auf streng logische Weise lösen kann, ohne jede mögliche Verteilung von Zahlen durchzuprobieren. "Bei bestimmten Aufgaben lässt sich dann tatsächlich mathematisch beweisen, dass die ermittelte Lösung die beste ist", sagt Felix Winter. "Doch ab einer gewissen Komplexität der Aufgabe ist das normalerweise nicht mehr möglich." Dann muss man auf sogenannte heuristische Methoden zurückgreifen: Man wendet gewisse Faustregeln und Grundannahmen an, ähnlich wie das auch ein Mensch beim Erstellen eines solchen Zeitplans machen würde. Dabei ermittelt man vielleicht nicht unbedingt die allerbeste Lösung, aber zumindest eine ziemlich gute – und das in überschaubarer Zeit.

"Solche Methoden an die konkrete Aufgabe anzupassen, ist oft heikel", sagt Felix Winter. "Da braucht es auch einiges an menschlicher Erfahrung." Die Parameter der Algorithmen müssen klug gewählt werden, man muss die passenden Methoden einsetzen, man arbeitet mit Logik und künstlicher Intelligenz.

In der Forschungsgruppe von Prof. Nysret Musliu, Felix Winters Doktorvater, hat man viel Erfahrung mit all diesen Methoden: "Wir untersuchen nicht nur die wissenschaftlichen Grundlagen solcher Probleme, sondern wir wollen damit ganz konkrete Aufgabenstellungen aus der Industrie lösen", erklärt Winter. Neben Lackieranlagen in der Autoindustrie war auch die Herstellung von Zahnprothesen ein Anwendungsfall, den der Forscher konkret untersuchte: Auch dort wird mit unterschiedlichen Farben gearbeitet, auch dort lässt sich die Effizient durch kluge Zeitplanung steigern.

Zusammengearbeitet wurde dabei unter anderem mit der MCP Algorithm Factory, einer Unternehmensberatung und Softwareentwicklungsfirma, die sich auf die Lösung von Planungsproblemen in der Industrie spezialisiert hat. "Solche Scheduling-Methoden werden in Zukunft eine wachsende Rolle spielen", ist Felix Winter überzeugt. "Schließlich bedeutet bessere Planung immer auch mehr Effizienz und weniger Verschwendung – sowohl was Zeitressourcen betrifft, als auch bei Energie oder Rohstoffen." [gr]