| Threadnapping: Programmierfrage (Logik) |  |
Nabend,
vielleicht kann mir jemand bei einer Frage der Programmierlogik helfen?
Etwas vereinfacht dargestellt geht es darum, Bewerber mit Gutachtern zu matchen.
Dabei sollen aber die Bewerber und die Gutachter nicht von der gleichen Universität kommen, und nicht die gleiche Nationalität haben. Jeder Bewerber braucht genau einen Gutachter (zumindest in unserem Beispiel).
Angestrebt ist, die Lösung in Excel mittels VBA zu umzusetzen - es geht mir aber nicht um Code, sondern um die Logik des Matchings. (Excel deshalb, weil die Quelldaten so vorliegen, und die Kollegen, die das effektiv nutzen, damit umgehen können. Auch die Zieldaten sollten wieder in Excel vorliegen.)
Mein (sehr) grundlegender Ansatz wäre, mittels Schleife durch alle Datensätze zu gehen, die Kriterien zu prüfen, und bei jeder passenden Paarung diese entsprechend zu vermerken.
Allerdings kann dieses Verfahren dazu führen, dass am Ende die Zuteilung nicht aufgeht, obwohl es eine Lösung gibt.
Ich habe irgendwie die Vermutung, dass es für solche Probleme bereits Lösungen gibt, aber ich habe sie noch nicht gefunden.
Beispiel:
Nehmen wir an, ich hätte diese Gutachter:
Kim, Seoul University, Korean
Peter, Harvard University, American
Michael, Stanford University, British
Sowie diese Bewerber:
Petra, Sofia University, Bulgarian
Anna, Harvard University, German
Mary, Harvard University, British
Und würde nun starten, die Bewerber der Reihe nach auf die Gutachter zu verteilen. Nach jedem erfolgreichen Match geht es von vorne los.
1. Lauf
Petra > Kim = erlaubt
Ergebnis: Petra / Kim
2. Lauf
Anna > Kim = nicht erlaubt, da Kim bereits zugewiesen
Anna > Peter = nicht erlaubt, Konflikt University
Anna > Michael = erlaubt
Ergebnis: Anna / Michael
3. Lauf
Mary > Kim = nicht erlaubt, da Kim bereits zugewiesen
Mary > Peter = nicht erlaubt, Konflikt University
Mary > Michael = nicht erlaubt, Konflikt Nationality
Ergebnis: Fehler, komplette Zuteilung nicht gelungen
Allerdings gibt es mindestens diese Lösung:
Mary > Kim
Anna > Michael
Petra > Peter
Wie löse ich das Problem jetzt algorithmisch?
1. Bei jedem Fehlschlag einfach einen Bewerber später anfangen? Vermutlich garantiert mir das auch nicht die Lösung.
2. Bei einem Mismatch versuchen, für diesen Bewerber einen passenden Match zu finden, und den damit verdrängten Bewerber dann ebenfalls neu zuteilen, usw., bis es endlich passt? Mit etwas Pech könnte das ne Endlosschleife werden, oder? Da ist auch keine Auflösung garantiert?
3. Versuchen, die Datensätze irgendwie zu flaggen, z.B. nach Schwierigkeit der Zuordenbarkeit (hier z.B. American, British, Harvard), und dann die schwierigen erstmal mit den leichten matchen?
4. Oder anders gesagt: Es muss doch eine Logik geben, die eine vorhandende Lösung garantiert findet?
Hinweis: Es sind in der Realität rund 400 Bewerber auf ca. 30 Gutachter zu verteilen, und jeder wird dreimal begutachtet (also quasi 1200 => 80). Es wäre nicht schlimm, wenn das Skript ein paar Minuten bräuchte, aber es darf auch nicht unhandlich lange dauern.
Ankedote: Letztes Jahr haben wir für die Lösung einen Online-Dienst namens OpenConf genutzt. Wollen wir aber nicht weiter nutzen, da sehr user-unfreundlich. Auch dieser Dienst hat keine perfekte Lösung gefunden - ob sie möglich gewesen wäre, kann ich nicht sagen. In der Praxis kann man das relativ einfach lösen, in dem man die Bewerber halt nicht gleichmäßig zuteilt, sondern ungleichmäßig.
Dennoch interessiert mich der Lösungsansatz, zudem muss das Skript wenigstens ein 99%-Matching hinkriegen. Einen Einzelfall kann man lösen, aber es dürfen nicht mehr als eine Hand voll unzugewiesen bleiben.
Falls jemand gute Ideen hat, würde ich mich freuen.
Danke & Grüße,
Wolfgang