Algorithmen für Zuordnungsprobleme
– "Die Nadel im Heuhaufen" oder "Wie findet man eine (fast) optimale Ressourcenbelegung bei mehr mögliche Lösungen als Teilen im Universum?" –
Das Forschungsvorhaben beschäftigt sich mit dem Entwurf und der Analyse von Algorithmen für verschiedene kombinatorische Optimierungsprobleme, die in die Klasse der sogenannten Packungsprobleme fallen.
Bei Packungsproblemen ist die Aufgabe aus einer Menge von Gegenständen eine geeignete Teilmenge auszuwählen und diese so auf Behälter zu verteilen, dass eine gewünschte Zielfunktion optimiert und gegebene Nebenbedingungen eingehalten werden. Bekannte Beispiele sind das Knapsack Problem oder das Generalized Assignment Problem.
Auch wenn es häufig theoretisch denkbar ist, alle zulässigen Lösungen eines Problems zu enumerieren um unter diesen eine optimale Zuordnung zu finden, ist der nötige Aufwand für Probleminstanzen von realistischer Größe meist viel zu hoch. Aus diesem Grunde interessiert man sich für Approximations-Algorithmen, die nach kurzer Laufzeit Lösungen liefern, die eine gewünschte Gütegarantie im Vergleich zur Optimallösung einhalten.
Im Rahmen des Forschungsvorhabens sollen neue Varianten dieser Probleme betrachtet werden. So werden zum einen sogenannte Mindestmengen-Restriktionen untersucht, die die Komplexität des Problems deutlich erhöhen und neue algorithmische Ansätze erfordern. Weiterhin werden Probleme betrachtet, bei denen Nebenbedingungen relaxiert werden, sodass man statt fester Kapazitätsschranken Auslastungskosten einführt, die als eine konvexe Funktion mit in die Zielfunktion eingehen.
Während es sich bei den oben erwähnten Problemen häufig um eine statische Zuordnungsentscheidung handelt, geht es beim Scheduling darum eine zeitliche Abfolge zu bestimmen, in der begrenzte Ressourcen geeignet durch Prozesse ausgelastet werden. Ein bekanntes Problem aus diesem Gebiet ist das Interval Scheduling. Dabei sind Anfangs- und Endzeiten für alle Aufträge gegeben und es muss entschieden werden welche Aufträge bearbeitet werden sollen, sodass die Anzahl der fertig gestellten Aufträge maximiert wird. Sind alle Aufträge bereits zu Beginn bekannt, kann das Problem als ein Kürzeste-Wege-Problem modelliert und mit bekannten Algorithmen gelöst werden. Der Fall, dass zu keinem Zeitpunkt Informationen über die zukünftigen Aufträge vorliegen, ist bis jetzt noch wenig untersucht. Die Online Optimierung beschäftigt sich mit der Frage wie Algorithmen aussehen müssen, die mit diesen Unsicherheiten möglichst gut umgehen.
Ziel aller entwickelten Algorithmen ist es mit zur Verfügung stehenden begrenzten Ressourcen möglichst effizient umzugehen und so zur Entscheidungsunterstützung beizutragen. Dadurch ergeben sich viele Anknüpfungspunkte zur Kooperation mit den Agrar-, Forst- und Wirtschaftswissenschaften.