Algorithm Engineering für Real-Time Scheduling und Routing

• Antragsteller: Professor Dr. Friedrich Eisenbrand; Professor Dr. Martin Skutella
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2007 bis 2016
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 47960878

Forschungsgegenstand dieses Projekts ist Algorithm Engineering im Zusammenhang mitReal-Time Systemen. Es werden effiziente Algorithmen für Real-Time Scheduling- undRoutingprobleme entwickelt, analysiert, implementiert und getestet. Dabei wird besondererWert auf eine enge Rückkopplung der mit den Algorithmen erzielten experimentellenErgebnissen an die Weiterentwicklung und Verbesserung dieser Algorithmen gelegt. Ziel istdie Entwicklung einer Algorithmenbibliothek zur Lösung verschiedener großerOptimierungsprobleme, die im Rahmen von Real-Time Systemen von Bedeutung sind, jedochbei Weitem noch nicht zufriedenstellend gelöst sind.Die entwickelten Algorithmen bauen auf Methoden aus der Mathematischen Programmierungund Kombinatorischen Optimierung auf. Die bislang erzielten Ergebnisse haben gezeigt, dassdiese Methoden das Potenzial besitzen, zu deutlich verbesserten Algorithmen zu führen. Siewurden bislang in der Literatur nur in sehr beschränktem Umfang bei Real-Time SchedulingundRoutingproblemen angewendet, da es nur wenig Austausch zwischen denWissenschaftlern dieser Gebiete und der Real-Time Community gab. Im Rahmen des Projektswird hier eine Brücke geschlagen. Aktuelle Methoden der Mathematischen Programmierungund Kombinatorischen Optimierung werden dem Bereich der Real-Time Systeme zugänglichgemacht. Umgekehrt stellen die Optimierungsprobleme aus dem Bereich der Real-TimeSysteme eine neue, sehr interessante Herausforderung für die Mathematische Programmierungund Kombinatorische Optimierung dar.

• DFG-Verfahren: Schwerpunktprogramme
• Teilprojekt zu: SPP 1307: Algorithm Engineering
• Internationaler Bezug: Schweiz