Online-Optimierung

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 finden sich in Produktion und Logistik, z.B. Lager- und Materialflusssysteme, Pack- und Beladungsprobleme, Transport.

Das klassische Bewertungsmaß für Online-Algorithmen - die sog. Kompetitivität - entspricht einem Worst-Case-Maß und lässt sich in praktischen Problemstellungen kaum anwenden bzw. besitzt unzureichende Aussagekraft. Unsere Zielsetzung für Forschungsarbeiten im Bereich der Online-Optimierung liegt deshalb in der Entwicklung eines umfassenden Frameworks zur Modellierung und Analyse von Online-Problemen wie sie in der Praxis auftreten. Hierzu führen wir als Alternative zu den klassischen Bewertungsansätzen die sog. Zählverteilungsfunktionen als aussagekräftige verteilungsbasierte Bewertungsmethoden ein, die sich insbesondere in Simulationsanwendungen einfach integrieren lassen.

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.