Algorithmen für komplexe Schedulingprobleme

• Antragsteller: Professor Dr. Rolf H. Möhring
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2007 bis 2015
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 48267681

Scheduling Probleme sind in realen Anwendungen meist bedeutend komplexer als viele der bisher in der Algorithmik untersuchten Modelle. Dies gilt insbesondere für das Teilgebiet des Turnaround Scheduling, das Motivation und Anwendungshintergrund für den Erstantrag darstellte. Ein weiteres, aus dieser Sicht repräsentatives Problemfeld ist die Reihenfolgeplanung, bei der insbesondere in der Stahlindustrie sehr komplexe Nebenbedingungen zu berücksichtigen sind. Ein prototypisches Beispiel für das Turnaround Scheduling ist die Stillegung einer chemischen Anlage für technische Überprüfungen und davon abhängig ggf. die Durchführung von Wartungs- und Reparaturarbeiten. Dieser Problemtyp beinhaltet ganz unterschiedliche algorithmische Aufgaben: Eine ”idealen“ Durchführungszeit für die Stilllegung muss in Abhängigkeit der Kosten für eine schnelle Durchführung und des entgangenen Deckungsbeitrages für die Dauer der Stillegung ermittelt werden. Darüber hinaus muss der ”ideale“ Personaleinsatz unter Berücksichtigung von Obergrenzen (knappe Ressourcen) und der Möglichkeit zur Beschleunigung einzelner Aktivitäten durch erhöhten Personaleinsatz gefunden werden. Dies in vielen Fälle basierend auf unsicheren Daten, so dass Risikomaße und Politiken notwendig werden. Für diese Aufgaben wurden in der Algorithmik bisher nur Teilaspekte untersucht, und das meist auch nur aus theoretischer Sicht wie Approximation oder Online Kompetitivität. Im Bereich der Reihenfolgeplanung bietet die Planung von Bandbeschichtungsanlagen — ein kombiniertes Reihenfolgeplanungs- und Färbungsproblem unter diverser Nebenbedingungen — viele offene Probleme. In diesem Problemumfeld gibt es weder theoretische Überlegungen zu vereinfachten Problemvarianten, noch gibt es effiziente Algorithmen, die das Optimierungspotential dieser Anlage sinnvoll ausnutzen [Ass]. Die einzigen bekannten Heuristiken verwenden die entscheidende Struktur des Problems nicht und führen so zu schlechten Ergebnissen. Das Ziel dieses Antrags ist die Entwicklung und Erprobung von Algorithmen für die Lösung der genannten Aufgaben. Neben Einsichten in die Struktur solcher Probleme steht die Entwicklung von Algorithmen im Vordergrund, die auch auf großen Problemen aus der Praxis in vertretbarer Zeit nachweislich gute Lösungen liefern. Hierzu stehen realistische Daten für das Turnaround Scheduling (10.000 -100.000 Aktivitäten) und die Bandbeschichtungsplanung (80 Aufträge b= 3 Tagen) aus Kooperationen mit T.A. Cook Consultants, Berlin, bzw. PSI Buisiness Technologie zur Verfügung.

• DFG-Verfahren: Schwerpunktprogramme
• Teilprojekt zu: SPP 1307: Algorithm Engineering