Intralogistik und Produktion
- Hohe Auslastung von (teuren) Assets und effizienter Einsatz des Personals
- Regulatorische Anforderungen (Arbeitszeitregelung, ...)
- Reaktion auf Peaks / Ausnahmesituationen
- Systemanalyse sowie Bewertung von Entscheidungen
- Entscheidungsunterstützung in Planung und operativem Betrieb
Typische Fragestellungen
- Produktionsplanung (Maschinenbelegung und Auftragsreihenfolgen)
- Lagerlogistik (Materialflusssteuerung und Auftragssteuerung)
- Räumliche & zeitliche Konsolidierung (Packplanung)
- Servicelevel und Liefertreue
Modellierung von Online-Problemen und Bewertungskriterien für Online-Algorithmen
Die Online-Optimierung befasst sich mit der Optimierung von Systemen, die einem ständigen Zulauf an Daten unterliegen. Im Gegensatz zur klassischen Offline-Optimierung, bei der angenommen wird, dass alle Problemdaten bereits vor der Verwendung eines Lösungsverfahrens bekannt sind, müssen dynamisch bekanntgegebene Daten im Verfahrensablauf von Online-Algorithmen berücksichtigt werden. Die Anwendungsfelder der Online-Optimierung sind vielfältig und breit gestreut:
- Lager- und Materialflusssysteme
- Packungsprobleme
- Transportprobleme
- Rent-or-buy Probleme
Als klassisches Bewertungsmaß für Online-Algorithmen wird bislang vornehmlich die sogenannte Kompetitivität eingesetzt. Diese vergleicht den Zielfunktionswert des Online-Algorithmus mit dem Zielfunktionswert eines Offline-Algorithmus, der die gesamte Folge der Eingabedaten gekannt hätte. Da die Kompetitivität in Form einer Worst-Case-Analyse ermittelt wird, ist ihr Wert für praktische Problemstellungen häufig von geringer Aussagekraft. Vielmehr tritt oftmals sogar der Effekt auf, dass Online-Algorithmen mit einer verhältnismäßig guten Kompetitivität ein inakzeptables Verhalten für typische Eingabefolgen aufweisen. Grund hierfür ist das Design vieler Online-Algorithmen: Sie wurden ausschließlich vor dem Hintergrund einer möglichst guten Kompetitivität entwickelt, ohne Rücksicht auf problemtypische Eingabefolgen zu nehmen. Ein weiteres Defizit der kompetitiven Analyse ist die Vernachlässigung von Anforderungen realer Probleme: In vielen Praxis-Problemen wird erwartet, dass verwendete Lösungsalgorithmen in Echtzeit operieren, und dass der verwendete Speicherplatz beschränkt ist.
Unsere Zielsetzung für Forschungsarbeiten im Bereich der Online-Optimierung liegt in der Entwicklung eines umfassenden Frameworks zur Modellierung und Analyse von Online-Problemen. Zum Einen soll dieses Framework in der Lage sein, die wesentlichen Struktureigenschaften einer Problemstellung zu beschreiben; zum Anderen soll die Verwendung alternativer Bewertungskriterien für die Güte eines Online-Algorithmus dessen praktische Einsatzfähigkeit besser abschätzen als es bislang durch die Kompetitivität gelingt. Alternative Bewertungskriterien berücksichtigen als knappe Ressource gleichermaßen Information, Rechenzeit und Speicherbedarf.
Ein weiteres Ziel der Analyse stellt die Einbeziehung sogenannter Lookaheads dar. Hierunter versteht man das Vorhandensein einer Teilmenge zukünftiger Daten, die von einem Online-Algorithmus in die Entscheidungsfindung einbezogen werden können. Online-Probleme mit Lookahead stehen somit zwischen den beiden Extremfällen der Offline- und Online-Optimierung. In der Theorie der Online-Algorithmen blieben Lookahead-Effekte bislang ohne große Beachtung, obwohl sie in vielen praktische Problemstellungen, wie z.B. der Transportplanung - nachweislich zu einer deutlichen Verbesserung des Zielfunktionswerts beitragen. Im Rahmen der Forschungsarbeiten soll untersucht werden, welche Abhängigkeiten zwischen der Problemstellung und den zu erwartenden Lookahead-Effekten bestehen.