Approximationsalgorithmen für Durchsatzoptimierung auf dem nächsten Level

• Antragsteller: Professor Dr. Andreas Wiese
• Fachliche Zuordnung: Theoretische Informatik ; Mathematik
• Förderung: Förderung seit 2025
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 551896423

Die Kombinatorische Optimierung ist ein Bereich der theoretischen Informatik, der sich mit der Suche nach der besten Lösung aus einer diskreten Menge von Möglichkeiten beschäftigt. Die untersuchten Probleme haben Anwendungen in einer Vielzahl von Bereichen wie Terminplanung, Logistik oder Netzwerkoptimierung. Insbesondere können Techniken der kombinatorischen Optimierung eingesetzt werden, um begrenzte Ressourcen optimal zu nutzen. Eine wichtige Anwendung davon ist die Durchsatzoptimierung in einem gegebenen System, zum Beispiel bei Maschinen in einer Fabrik, die zur Produktion von Gütern eingesetzt werden, wie etwa in einem just-in-time Produktionssystem. Da Maschinen eine teure Resource sind, ist es wichtig, die verfügbaren Maschinen optimal zu nutzen. In den letzten Jahren wurden enorme Fortschritte bei einem wichtigen Problem der Durchsatzmaximierung erzielt, dem Unsplittable Flow on a Path Problem (UFP). Dieses Problem modelliert die Auswahl von Jobs mit festen Ausführungszeitintervallen auf einer einzelnen Maschine, wobei sich die Jobs eine gemeinsame (begrenzte) Ressource teilen, wie z.B. Energie, Netzwerkbandbreite oder Arbeitskräfte. Das Ziel besteht darin, die besten Jobs auszuwählen, für die genügend Resourcen zur Verfügung stehen. Dieses Problem ist mittlerweile sehr gut verstanden und wir kennen seinen bestmöglichen Approximationsfaktor, insbesondere aufgrund der Ergebnisse des Antragstellers dieses Projekts und seiner Co-Autoren. Allerdings gibt es viele natürliche Verallgemeinerungen dieses Problems, die wir nicht annähernd so gut verstehen. Dies gilt zum Beispiel für den Fall, in dem es ein Zeitfenster für jeden Job gibt, in dem er ausgeführt werden muss (aber das genaue Ausführungsintervall nicht festgelegt ist), den Fall, bei dem die Jobs in Gruppen (Bags) aufgeteilt werden, so dass wir nur einen Job pro Gruppe auswählen können, wenn mehr als eine Maschine gegeben sind oder wenn mehr als eine Ressourcen gegeben ist. Unser Ziel in diesem Projekt ist es, unser Verständnis der Durchsatzmaximierung in diesen allgemeineren Fällen deutlich zu verbessern. Im Idealfall wollen wir sie genauso gut verstehen wie das klassische Szenario, in dem es nur eine Maschine, eine Ressource und keine Zeitfenster oder Bags gibt. Da unsere untersuchten Probleme NP-schwer sind, wollen wir Approximationsalgorithmen für sie zu entwickeln, also Algorithmen mit polynomieller Laufzeit, die immer eine Lösung berechnen, die beweisbar nahe an der optimalen Lösung liegt. Außerdem wollen wir Komplexitätsresultate beweisen, die die Grenzen effizienter Algorithmen in unseren Fällen beschreiben, z.B. durch einen Beweis, dass bestimmte Approximationsgüten nicht erreicht werden können (unter gewissen komplexitätstheoretischen Annahmen).

• DFG-Verfahren: Sachbeihilfen
• Internationaler Bezug: Schweiz
• Kooperationspartner: Professor Fabrizio Grandoni