Ungarische Algorithmus und mehrere Faktoren

Question

Ich habe eine Situation, wo ich brauche Menschen mehrere Ereignisse zuzuordnen. Wenn wir nur einen Preis als Faktor haben, wäre es in Ordnung, aber es gibt eine Reihe von Faktoren, die kommen.

Zuerst etwas Hintergrund. Dies ist für eine gemeinnützige Organisation, die Geschichte Stunden für Kinder fördert, die aus irgendeinem Grund im Krankenhaus sind, so sind sie auf freiwilliger Arbeit zu tun. Also, da sie auf die Menschen guten Willen verlassen, sie geben den Menschen so viel Arbeit wie Menschen können / wollen, die variiert wie:

• Einige Leute können nur tun, morgens, und einige andere Leute können nur nachmittags tun;
• Einige Leute können nur noch montags und donnerstags, können andere Personen auf August oder Dezember gehen nicht;
• Einige Leute können nur gehen einmal im Monat, können andere Personen 4 mal gehen (und auch andere Menschen gegeben „Priorität“ in diesen Maßnahmen, weil sie erfahrener sind und kann zur Verfügung 10-mal im Monat zu tun)

Also, ich irgendwie die ersten beiden herausgefunden. Da der ungarische Algorithmus über den Preis, würde ich ihnen einen dümmlich hohen Preis für die Zeiten geben, die sie nicht gehen können. Aber wie würden Sie tun, um die andere?

Ich dachte an sich irgendeine Art der Partitur zu geben. Etwas entlang der Linien von: einer Person, die diese einmal im Monat tun kann, kostet so etwas wie 1000 Punkte. Wenn jemand 10 Mal im Monat gehen kann, diese Person kostet 100 Punkte (1000 Basisteilung von 10). Auch die Art und Weise, dies zu verteilen wäre, den Preis zu erhöhen, wenn eine separate Aktion getan werden würde, wie so (ausgewählte Personen einen * auf ihren damit verbunden Kosten haben):

Erste Iteration

         | August 1st 2009
Person A | 1000
Person B | 500 *

Zweite Iteration

         | August 8th 2009
Person A | 1000 *
Person B | 1000 

Dies würde die Möglichkeit, entsprechend den Menschen zwischen allen zu verteilen, mehr Maßnahmen den Vorrang zu geben, die dies mehrmals tun können.

Was denken Sie, und wie würden Sie es tun?

Answer 1

Dies ist ein Scheduling / Optimierungsproblem, so dass die entscheidende Frage lautet: „Was Menge versuchen Sie zu maximieren“? Ich würde vermuten, Sie schauen, um die Gesamtzahl der Stunden für alle Ihre Freiwilligen ohne Auseinandersetzungen, unter jedem Freiwilligen Fahrplan Einschränkungen gearbeitet zu maximieren. Sie erwähnen auch Freiwillige mit mehr Erfahrung priorisieren, so dass es klingt wie Sie sagen, „einige Freiwillige sind bevorzugt über andere“.

Dies ist dann ein klassisches bipartiter Matching-Problem . Siehe z.B. p.498 von Der Algorithmus Design Manual (2. Aufl.), von Steven Skiena. Der grundlegende Ansatz ist ein Diagramm mit den Eckpunkten zu konstruieren, sowohl die Menge der Freiwilligen darstellt, und den Satz von Zeitschlitzen Sie zu füllen versuchen. Kanten verknüpfen Freiwilligen gültigen Zeitschlitzen. Die optimale Lösung ist, dann wird die größtmögliche Menge von Kanten, wo keine Freiwilligen oder Zeitschlitz wiederholt wird. Dies ist ein Matching.

Einige Ihrer Freiwilligen der Lage sein, mehr als einen Schlitz zu tun; Dies kann durch die Replikation, die Freiwilligen Vertex mehrere Male modelliert werden.

Wenn Sie die Priorisierung von Freiwilligen implementieren möchten, dann ist dies fügt effektiv eine Gewichtung zu jeder Kante, die Modellierung der Erfahrung des Freiwilligen für diese Aufgabe. In diesem Fall, wie Sie dachten, müssen Sie so etwas wie die ungarische Algorithmus. Wenn Sie ohne diese wegkommen können, dann können Sie das Problem in ein äquivalentes Flussgraphen verwandeln, und ein Netzwerkfluss-Algorithmus anwenden. Hier ist ein Beispiel für Code, der sowohl gewichtete und ungewichtete passende implementiert.

Wenn Sie weitere Informationen wünschen, auch andere Alternativen, und mehr Links zu Implementierungen, ich selbst stark empfehlen, sich eine Kopie des Handbuchs Algorithm Design -. Es ist ein erstaunlich klare und praktische Referenz