Die Kraft von Restarts in Online-Scheduling

• Antragsteller: Professor Dr. Rob van Stee
• Fachliche Zuordnung: Theoretische Informatik ; Mathematik
• Förderung: Förderung seit 2021
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 451155613

Optimieren unter Unsicherheit ist ein weit erforschter Bereich mit vielen unterschiedlichen Anwendungen. In Online-Scheduling machen wir die Annahme dass die Aufträge eins nach dem anderen (oder mit der Zeit) ankommen und ohne Kenntnisse über die restliche Eingabe an Maschinen zugewiesen werden müssen. Das Ziel ist es, das Kompetitivitätsverhältnis zu minimieren. Für Minimierungsproblem ist das definiert als das höchst mögliche Verhältnis über alle Eingaben zwischen den Kosten eines Algorithmus für die Eingabe und die optimale Kosten für dieselbe Eingabe.Wir interessieren uns für Online-Scheduling-Proleme in die Aufträge mit der Zeit ankommen. In diesem Projekt werden wir fokussieren auf mehrere bekannte Zielfunktionen wie die Gesamtfertigstellungszeit, Flow-Time, Throughput und die gewichtete Versionen dieser Funktionen. Wir werden uns damit beschäftigen, wie mann diese Zielfunktionen im Restarts-Modell optimieren kann.In diesem Modell ist es möglich, bereits angefangene Jobs zu unterbrechen, falls ein wichtigerer Job ankommt (d.h.~ein kleinerer, oder schwererer Job). Ein unterbrochener Job muss aber ganz neu gestartet werden: die bereits gemachte Arbeit geht also verloren. Dieser Modell heißt auch Preemption mit Restarts. Es ist nicht das Gleiche wie das bekanntere Preemption mit Wiederaufnahme-Modell, in das ein Job, der unterbrochen wird, später einfach weiter ausgeführt werden kann.Das Modell mit Restarts ist wohlmotiviert, da es nicht immer möglich ist, laufende Aufträge zu unterbrechen ohne dass die gemachte Arbeit verlorengeht. Es ist deshalb wichtig zu verstehen, inwiefern Restarts helfen können, die Leistung von Online-Scheduling-Algorithmen zu verbessern. Unsere Arbeit wird bessere Ergebnisse, und in manchen Fällen die erste Ergebnisse, für diese weithin ignorierte Forschungsrichtung liefern.

• DFG-Verfahren: Sachbeihilfen
• Internationaler Bezug: Großbritannien, Israel, Tschechische Republik
• Kooperationspartner: Professor Yossi Azar; Dr.-Ing. Matthias Englert; Professor Jiri Sgall