Das Assignment-Problem (deutsch: Zuordnungsproblem) ist ein klassisches Optimierungsproblem der Kombinatorik: n Aufgaben sollen auf n Bearbeiter so verteilt werden, dass jede Aufgabe genau einmal vergeben wird, jeder Bearbeiter genau eine Aufgabe übernimmt und die Gesamtkosten minimal sind. Es ist eng mit dem Matching in bipartiten Graphen verwandt.
Formale Beschreibung
Gegeben sind Kosten cij für die Zuordnung von Aufgabe i zu Bearbeiter j. Gesucht ist eine Permutation π der Bearbeiter, die die Summe ∑ ci,π(i) minimiert. Es gibt n! mögliche Zuordnungen — schon bei 20 Aufgaben sind das rund 2,4·1018 Varianten, eine naive Suche ist also aussichtslos.
Die Ungarische Methode
Die klassische Lösung ist die Ungarische Methode (Harold Kuhn 1955, verfeinert von James Munkres 1957). Sie arbeitet auf der Kostenmatrix, zieht Zeilen- und Spaltenminima ab, sucht eine optimale Deckung der Nullen und korrigiert iterativ. Ihre Laufzeit ist O(n³) — das Assignment-Problem ist damit polynomial lösbar und gehört zur Klasse P, nicht zu den NP-vollständigen Problemen. Auch als lineares Programm formuliert, liefert es dank totaler Unimodularität der Inzidenzmatrix immer eine ganzzahlige Optimallösung.
Komplexität und Varianten
Die zweidimensionale Standardform ist effizient lösbar. Anders das dreidimensionale Assignment-Problem (drei gleich große Mengen, Tripel statt Paare): Es ist NP-vollständig. In der Praxis nutzt man für große Instanzen außerdem Greedy-Verfahren, dynamische Programmierung oder Heuristiken, wenn die Komplexität der exakten Methode zu hoch erscheint.
Anwendungen
- Zuordnung von Jobs zu Maschinen oder Mitarbeitern (Personaleinsatzplanung)
- Zuordnung von Fahrzeugen zu Aufträgen in der Logistik
- Feature-Zuordnung in der Bildverarbeitung über eine Kostenmatrix der Ähnlichkeiten
- Verwandte Paarungsprobleme: Während das Assignment-Problem Kosten minimiert, sucht der Gale-Shapley-Algorithmus stabile Paarungen; das gewichtete Matching verallgemeinert die Auswahl optimaler Kanten.
Grundlegendes Werkzeug bleibt der Algorithmus-Begriff selbst — das Assignment-Problem ist eines seiner schönsten Beispiele für „schwer zu raten, leicht zu berechnen“.