Robuste Online-Algorithmen für Scheduling- und Packungsprobleme

• Antragsteller: Professor Dr. Klaus Jansen
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2016 bis 2020
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 320260044

Das Ziel dieses Forschungsvorhabens ist die Entwicklung robuster Online-Algorithmen für fundamentale Packungs- und Schedulingprobleme, wie z.B. Scheduling auf identischen und uniformen Maschinen, sowie Bin und Strip Packing Probleme. Während es bei den Offline-Varianten dieser Probleme approximative Algorithmen bzw. Approximationsschemata gibt, die Lösungen in polynomieller Zeit nahe am Optimum berechnen, ist dies im klassischen Online-Setting nicht mehr möglich. So kann man zum Beispiel für Scheduling auf identischen Maschinen zeigen, dass keine Online-Algorithmen mit einer kompetitiven Rate besser als 1,88 existieren. Motiviert durch praktische Anwendungen, wurden verschiedene interessante Modelle in der Forschung untersucht, bei der der aktuelle Schedule nach Eintreffen eines neuen Jobs geändert werden darf. Genauer gesagt wird die Migration durch einen Faktor beschränkt, den sogenannten Migrationsfaktor \beta. Bei Ankunft eines Jobs mit Ausführungszeit p_j dürfen in diesem Modell also Jobs mit Gesamtausführungszeit \beta p_j umgepackt werden. Interessant sind sogenannte robuste Online-Algorithmen, bei der der Migrationsfaktor konstant ist. Im Fokus unserer Betrachtungen liegt der Trade-off zwischen garantierter Lösungsqualität der Algorithmen und dem benötigten Migrationsfaktor. Wir wollen verschiedene offene Fragen lösen. Weitere Zielsetzungen umfassen die Weiterentwicklung zugrunde liegender Techniken der Sensitivitätsanalyse (ganzzahliger) linearer Programme (I)LPs und das Bestimmen von unterer Schranken für den benötigten Migrationsfaktor eines robusten Approximationsschemas, sowie Untersuchungen dazu, inwieweit einfache Algorithmen mit kleinem Migrationsfaktor bereits untere Schranken für die Online-Versionen von Problemen ohne Migration schlagen können.

• DFG-Verfahren: Sachbeihilfen