Statik und Dynamik des Multiprozessor Scheduling Problems

• Antragsteller: Dr. Stephan Mertens
• Fachliche Zuordnung: Statistische Physik, Nichtlineare Dynamik, Komplexe Systeme, Weiche und fluide Materie, Biologische Physik
• Förderung: Förderung von 2003 bis 2007
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 5401609

Das Multiprozessor Scheduling Problem, ein klassisches Problem der kombinatorischen Optimierung, ist formal äquivalent zu einem Modellsystem der statistischen Physik. Diese Analogie wird ausgenutzt, um Eigenschaften des Optimierungsproblems und seiner Algorithmen mit Methoden der theoretischen Physik zu untersuchen. Das Multiprozessor Scheduling Problem ist im Sinne der klassischen Komplexitätstheorie besonders schwierig (NPschwierig). Die besten heuristischen Algorithmen liefern Lösungen, die um einen exponentiell mit der Problemgröße wachsenden Faktor vom globalen Optimum abweichen. Erste Analysen des korrespondierenden physikalischen Modells haben starke Indizien dafür geliefert, dass das Tieftemperaturvehalten sehr gut durch ein Random Energy Modell beschrieben werden kann. Für das Optimierungsproblem heißt das, dass die Kostenfunktion keine brauchbaren Informationen mehr liefert sobald man sich dem Optimum nähert. Dieses Bild bietet eine überraschende Erklärung für das schlechte Abschneiden der heuristischen Verfahren. Im Rahmen des vorliegenden Projektes soll untersucht werden, für welche Energieskalen das Random-Energy-Modell zutreffend ist, was genau beim Übergang zu den Energien passiert, die von den besten Heuristiken erreicht werden und, darauf aufbauend, soll versucht werden, bessere Algorithmen für dieses hartnäckige Problem zu finden. Ergebnisse und Methoden sollen auf verwandte Optimierungsprobleme übertragen werden.

• DFG-Verfahren: Sachbeihilfen