Entwicklung von Approximationsalgorithmen für Scheduling auf heterogenen Maschinen

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

In diesem Projekt arbeiten wir an mehreren offenen Fragen bezüglich dem Problem Scheduling auf Heterogenen Maschinen mit Makespan Minimierung. Scheduling auf Heterogenen Maschinen ist ein klassisches kombinatorisches Problem, in welchem eine Menge von Jobs auf eine Menge von Maschinen verteilt werden soll. Jeder Job j hat eine Ausführungszeit p_ij abhängig von der Maschine i, auf der er ausgeführt wird. Das Ziel ist die maximale Last über alle Maschinen, den Makespan, zu minimieren.Unsere Forschung hat einen besonderen Fokus auf das Restricted Assignment Problem (ist aber nicht darauf beschränkt), in welchem p_ij entweder gleich p_j (unabhängig von der Maschine i) oder unendlich ist. Für diesen Spezialfall wurde eine lokale Suche mit Güte 33/17 OPT_LP gefunden, wobei OPT_LP das Optimum des Konfigurations-LP, einer besonders starken LP-Relaxierung, ist. Dieser Algorithmus konnte aber bisher nur benutzt werden, um das Integrality Gap des Konfigurations-LPs zu beschränken, weil noch keine nützlichen Schranken für seine Laufzeit bekannt sind. Eine polynomielle Variante wäre von enormer Bedeutung, da damit die vor über 25 Jahren entdeckte 2-Approximation erstmals verbessert werden würde.Wir wollen zusätzlich LP-/SDP-Hierarchien, darunter die Lasserre-Hierarchie, im Kontext von dem Problem Scheduling auf Heterogenen Maschinen untersuchen. Interessant ist vor allem, ob diese genutzt werden können, um noch stärkere Relaxierungen als das Konfigurations-LP zu finden.

• DFG-Verfahren: Sachbeihilfen