Multivariate Algorithmen für Scheduling mit hoher Multiplizität

• Antragsteller: Professor Dr. Matthias Mnich
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2017 bis 2024
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 382346515

Scheduling- und Planungsprobleme gehören zu den grundlegenden Fragestellungen der Algorithmik. Viele dieser Probleme erlauben höchstwahrscheinlich keine Verfahren, welche garantiert eine optimale Lösung in polynomieller Zeit berechnet. Daher wurden in den letzten Dekaden hunderte Approximationsalgorithmen für diese Probleme entwickelt. In diesem Projekt beschäftigen wir uns mit einem alternativen Lösungsansatz für Schedulingprobleme mit hoher Multiplizität, in denen eine große Menge von Jobs geplant werden müssen welche in wenige Kategorien klassifizierbar sind. Derartige Probleme treten beispielsweise beim Planen von Landesequenzen für Flugzeuge auf, deren Sicherheitsabstände vor allem von ihrer Bauart entsprechend weniger Typen abhängen. Unser Ziel ist die Entwicklung von Fest-Parameter Algorithmen, welche optimale Lösungen liefern in einer Zeit die polynomiell von der Eingabegröße ist und superpolynomiell nur in der kleinen Anzahl der Kategorien. Auf diese Weise verallgemeinern wir polynomielle Algorithmen für Spezialfälle dieser Probleme mit konstant vielen Kategorien auf realistischere Modelle, und verbessern gleichzeitig die Laufzeiten von Fest-Parameter Algorithmen welche bisher eine verschwenderische Auflistung jedes einzelnen Jobs verlangen.

• DFG-Verfahren: Sachbeihilfen