Statik und Dynamik des Multiprozessor Scheduling Problems

• Applicant: Dr. Stephan Mertens
• Subject Area: Statistical Physics, Nonlinear Dynamics, Complex Systems, Soft and Fluid Matter, Biological Physics
• Term: from 2003 to 2007
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 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 Programme: Research Grants