Glossar · approach
Zuordnungsproblem
Eins-zu-eins-Zuordnung einer Ressourcenmenge (Personen, Fahrzeuge, Maschinen) zu einer Aufgabenmenge mit minimalen Kosten oder maximalem Nutzen.
Assignment ProblemHungarian AlgorithmUngarische Methode
Das Zuordnungsproblem (assignment problem) ist das Problem, n Ressourcen (z. B. Arbeiter, Techniker, Fahrzeuge) eins zu eins auf n Aufgaben zuzuordnen, sodass die Gesamtkosten minimal oder der Gesamtnutzen maximal sind. Die klassische Form wurde 1955 von Kuhn mit dem 'ungarischen Algorithmus' in polynomialer Zeit gelöst — eine der ältesten und elegantesten Lösungen der OR. Das verallgemeinerte Zuordnungsproblem (GAP) erlaubt mehrere Aufgaben pro Ressource und ist NP-schwer. Auf dem Zuordnungsproblem baut die Mathematik vieler Probleme auf: Technikerdispo im Außendienst, Schichtplanung, Stundenplanung, Auftragsvergabe, Roboter-Aufgabe-Zuteilung.
Örnek
5 Techniker auf 5 Kunden zuordnen, wobei jede Fahrzeit unterschiedlich ist. Der ungarische Algorithmus findet die Zuordnung mit minimaler Gesamtfahrzeit in Sekunden.