n Aufgaben + n Personen / Maschinen — Wen Ordne Ich Worauf Zu, Damit Die Gesamtkosten Oder Zeit Minimal Sind?

Editorische Notiz

Das Problem heißt umgangssprachlich “Aufgabenverteilung”, “Personaleinsatz”, “Auftragszuordnung” oder “Ressourcenverteilung”. In der akademischen Literatur trägt es den Namen Zuordnungsproblem (Assignment Problem); die klassische Lösung heißt Ungarische Methode oder Kuhn-Munkres-Algorithmus, ein O(n³) polynomieller kombinatorischer Algorithmus. Der Name stammt aus den bipartiten Matching-Sätzen, die die ungarischen Mathematiker Dénes König und Jenő Egerváry in den frühen 1900er Jahren entwickelten; Harold Kuhn baute den Algorithmus 1955 auf dieser Basis auf, James Munkres goss ihn 1957 in eine formale polynomielle Prozedur. Nicht zu verwechseln mit #072 (Stable Matching): Stable Matching arbeitet mit zwei-seitigen Präferenzlisten — Kandidat A bevorzugt Institution X, Institution X bevorzugt Kandidat A, das Matching wird so konstruiert, dass kein Blocking-Pair entsteht. Bei der Zuordnung gibt es nur eine ein-seitige Kostenmatrix — die Person hat Kosten auf der Aufgabe, die Aufgabe hat keine Präferenzreihenfolge; keine Zahlung, aber Kosten; Optimierungsziel ist die Summe der Kosten (soziales Optimum) — die strategische Manipulation wird anders analysiert. Nicht zu verwechseln mit #094 (Transportproblem): dort können m Quellen und n Senken unterschiedlich sein (m≠n), jede Quelle kann teilbare Mengen an mehrere Senken senden; Angebots-/Nachfrage-Bilanz wird anders restringiert. Bei der Zuordnung geht jede Ressource zu genau einer Senke, jede Senke erhält von genau einer Quelle — quadratische 0/1-Zuordnung. Das Transportproblem verallgemeinert die Zuordnung.

Im Feld am häufigsten übersehener Punkt: Dummy-Erweiterung für den rechteckigen Fall (m≠n). Kuhns Original-Ungarische Methode verlangt eine n×n-quadratische Matrix; im Feld kommt 7 Personen + 12 Aufgaben oder 15 Personen + 9 Aufgaben. Die Lösung ist einfach, aber der Praktiker kennt sie nicht: Erweitere die Matrix mit Dummy-Zeilen/-Spalten zur quadratischen Form. (a) m<n (weniger Personen als Aufgaben): füge (n-m) Dummy-Personen hinzu, jede Dummy-Person hat auf jeder Aufgabe Kosten M (sehr groß) — wenn ‘jede Aufgabe muss zugeordnet werden’ verlangt wird; andernfalls 0, dann landen nicht zugeordnete Aufgaben bei Dummy-Personen (real unzugeordnet). (b) m>n (mehr Personen als Aufgaben): umgekehrt Dummy-Aufgaben hinzu; einer Dummy-Aufgabe zugeordnetes Personal heißt ‘in dieser Woche kein Auftrag’. Praktiker kennen diese Prozedur nicht — ‘Personalrest’ oder ‘Aufgabenrest’ bleibt manuell, Optimum-Verlust 10-25%. Zweiter übersehener Punkt: Maximierung ↔ Minimierung. Manche Probleme sind in der Form ‘Gesamtnutzen maximieren’ (z.B. Kompetenz + Mandantenpassung); die Ungarische Methode ist ein Minimierungs-Algorithmus, aber ein Ersatz Kosten := -Nutzen oder die Transformation (max_Nutzen - Nutzen) macht daraus ein Minimierungs-Problem; derselbe Algorithmus läuft. Dritter übersehener Punkt: Kostenmatrix-Schätzdrift. Damit der Algorithmus das Optimum liefert, muss C[i,j] korrekt geschätzt sein; schlechte Schätzungen liefern schlechte Zuordnungen. Wie die Matrix geschätzt wird (historische Dauer, Kompetenzformel, Anfahrtskosten-Tarif) ist ein Modellierungsproblem, das dem Algorithmus vorausgeht — Praktiker tun dies in der Regel intuitiv, und die Ausgabequalität ist an die Schätzungsqualität gebunden. Vierter übersehener Punkt: Verwechslung mit dem Quadratischen Zuordnungsproblem (QAP). Beim klassischen linearen Problem sind die Zellen unabhängig (C[i,j] hängt nur von i und j ab); beim QAP interagieren zwei Zuordnungen (wenn Person i und i’ beide in dieselbe Region zugeordnet werden, entstehen Transferkosten, etc.) — NP-schwer, eigene Algorithmenklasse (Koopmans-Beckmann 1957). Vermischen führt zur Überraschung ‘warum dauert das so lang’.

Schritt-für-Schritt-Pfad für KMU

Stufe 1 — Miss die Kostenmatrix zuerst und mach sie explizit. Mindestens 6-12 Monate Historie: für jedes Person-Aufgabe-Paar die tatsächliche Dauer, Qualitätsbewertung, Anfahrtsweg, Mandanten-/Projekt-Passung. Kostenformel schriftlich: C[i,j] = α × geschätzte_Dauer[i,j] × Stundensatz[i] + β × Anfahrtsweg[i,j] + γ × Kompetenz-Mismatch[i,j] + δ × Mandanten-Kontinuitätsstrafe[i,j]. Gewichte (α, β, γ, δ) sind Führungsentscheidung; mindestens als Startpunkt α=1, β=0.5, γ=2 (schwer), δ=0.3. Nach jeder Zuordnung wird die Ist-vs-Schätz-Abweichung protokolliert.

Stufe 2 — Wissenskapital aufbauen. Kompetenzkarte des Personals (Kompetenz × Niveau), Aufgaben-Taxonomie (Klassen + benötigte Kompetenzen + Durchschnittsdauer), Anfahrtsweg-Tarif (Region×Region), Mandanten-Kontinuitätsregeln (welche Mandanten verlangen denselben Mitarbeiter, welche bevorzugen ihn). Dieser Datensatz ist die Eingabe für das Kostenmatrix-Schätzmodell.

Stufe 3 — Pilot. 6-10 Wochen. Auf einer Teilmenge (z.B. eine Region, ein Aufgabentyp) berechne die optimale Zuordnung mit der Ungarischen Methode und stelle sie parallel zur aktuellen manuellen Zuordnung. Der Planer entscheidet; der Algorithmus empfiehlt. Teste die Dummy-Prozedur für den rechteckigen Fall. Erfolgskriterien vorab definiert: Gesamtkosten -10% min., Zuordnungszeit -50% min., Auslastungs-Schiefe -20% min.

Stufe 4 — Rollout. In 9-15 Monaten Ausweitung auf den gesamten Servicebereich + Mehr-Ziel-Optimierung (Kosten + Fairness + Kontinuität). Monatliche Zuordnungs-Kommission: Ist-vs-Optimum-Abweichungsanalyse, Kostenmatrix-Kalibrierung (alle 3 Monate), Auslastungsbilanz, Mandanten-Kontinuitätsquote.

Risiken — was schiefgehen kann

1. Schätzdrift der Kostenmatrix. Wenn C[i,j] falsch geschätzt ist, findet der Algorithmus das falsche Optimum. Z.B. Person X auf Aufgabentyp Y geschätzt 4 Stunden, tatsächlich 10 Stunden — Zuordnung ‘optimum’, Feld bricht. Gegenmaßnahme: Kostenmatrix wird nach jeder Zuordnung mit Feedback aktualisiert; mindestens 3-monatige Kalibrierung; Zellen mit Abweichung >25% lösen Tiefenanalyse aus.

2. Kompetenz ist mehrdimensional — ein einzelner Skalar reicht nicht. Die Kompetenz einer Person auf einer Aufgabe kann ‘Grundkompetenz + spezifisches Mandantenwissen + Sprache’ in mehreren Dimensionen sein; das in einem einzigen C[i,j] zusammenzufassen verliert Entscheidungsinformation. Gegenmaßnahme: Mehr-Ziel-Formulierung (Kosten + Fairness + Kontinuität getrennt), oder Berichten der Kostenkomponenten getrennt.

3. Widersprüchliche Präferenzen (soziale Dimension). Die optimale Zuordnung folgt der Kostenmatrix, aber die Mitarbeiterpräferenz (wer auf welcher Aufgabe arbeiten will, wer welchen Mandanten wiedersehen will) ist nicht in der Matrix; das Optimum kann in Mitarbeiterzufriedenheit Punkte verlieren. Gegenmaßnahme: Präferenzinformation als Präferenzstrafe (γ × Präferenz-Mismatch[i,j]) in die Kostenmatrix einbauen; oder Alternativen entlang der Pareto-Front bieten.

4. Single-Supplier-Workforce-Management-Lock-in. Ohne Vertragsklausel für jährlichen Standardformat-Export von Kostenmatrix-Historie, Zuordnungsarchiv, Personal-Kompetenzregister, Mandanten-Kontinuitätsregister und Algorithmusparametern verliert ein Wechsel das operative Gedächtnis. Zuordnungssysteme laufen 5-15 Jahre — Single-Supplier-Abhängigkeit ist Langzeitrisiko.

Technische Sicht auf die Lösung

Zielfunktion — Wahl:

• Ziel 1 — Minimum der Gesamtkosten: Klassisches lineares Zuordnungsproblem; Kostenkomponenten gewichtete Summe.
• Ziel 2 — Minimum der Gesamtzeit: Zeit-fokussiert; identisch zu Kosten, wenn Stundensätze gleich.
• Ziel 3 — Bottleneck (max-min-Fairness): Minimiere maximale zugeordnete Kosten; Fairness-fokussiert.
• Ziel 4 — Mehr-Ziel (Kosten + Fairness + Kontinuität): Pareto-Front oder gewichtete Summe.

Zuordnungsvarianten — nach Feld wählen:

• Klassische lineare Zuordnung (quadratisch + ausgeglichen): n×n-Matrix, Eins-zu-eins, Ungarische Methode O(n³).
• Rechteckige Zuordnung (m≠n): Dummy-Erweiterung + Ungarisch; oder LAPJV direkt rechteckig.
• Maximierungsvariante: Kosten := -Nutzen, derselbe Algorithmus.
• Bottleneck-Zuordnung: Threshold-Binärsuche + Ungarisch; max-min-Fairness.
• Verallgemeinerte Zuordnung (GAP): Jede Ressource hat Kapazität, jede Aufgabe einen Bedarf — NP-schwer, MIP/Metaheuristik.
• Quadratische Zuordnung (QAP): Person-Person-Interaktionskosten — NP-schwer, Koopmans-Beckmann 1957.
• Dynamische Zuordnung: Mehrperioden, Aufgaben kommen dynamisch — Rolling Horizon.
• Stochastische Zuordnung: Kostenmatrix unsicher, Erwartungswert oder CVaR-Optimierung.

Akademische Quellen

In den Frontmatter unter sources aufgeführt.