Zuordnungsfehler, wenn Jobs mehr als einmal verfügbar sind

Question

Ich habe ein normales Zuordnungsproblem, wo ich Arbeiter mit Jobs abgleichen möchte. Aber es gibt mehrere Arten von Jobs, jeder mit einer bestimmten Anzahl von Positionen. Zum Beispiel würde ich 10.000 Erbauer, 5.000 Schweißer usw. benötigen. Jeder Arbeiter hat natürlich die gleiche Vorliebe für jede Position der gleichen Art von Arbeit.

Mein aktueller Ansatz ist es, den ungarischen Algorithmus zu verwenden und einfach die Matrixspalten zu erweitern, um das zu berücksichtigen. Zum Beispiel hätte es 10.000 Builder-Spalten, 5.000 Schweißer usw. Natürlich mit O (n^3) und einer Matrix, die so groß ist, kann das Erhalten von Ergebnissen eine Weile dauern.

Gibt es eine Variation des ungarischen Algorithmus oder eine andere, die die Tatsache nutzt, dass es mehrere Verbindungen zu einem Jobknoten geben kann? Oder sollten Sie lieber in Monte-Carlo- oder genetische Suchbaum-Algorithmen schauen?

edit:

Formale Beschreibung als Sascha vorgeschlagen:

Set W für Arbeiter, J für Arbeitsplätze, Gewichtsfunktion für die Bevorzugung, Funktion für die Menge der verfügbaren Arbeitsplätze

So die Funktion, die ich minimieren wollen wäre:

wo

Einschränkungen wären:

und

wie von Yay gefragt, wäre es in Ordnung, wenn sie für einen Tag oder zwei auf einer normalen Verbraucher Maschine laufen. Momentan gibt es 50.000 Arbeiter mit 10 Arten von Jobs und insgesamt 50.000 Jobs. Also ist die Matrix 50k x 50k (erweitert) im Falle des ungarischen Algorithmus, den ich gerade benutze, oder 50k x 10 für LP mit der zusätzlichen Bedingung , während und Präferenzwerte in der Matrix von 0-100 gehen .

Answer 1

Dies wird eigentlich das Transportproblem genannt. Das Transportproblem ähnelt dem Zuweisungsproblem, da beide Quellen und Ziele haben, aber das Transportproblem hat zwei weitere Werte: Jede Quelle hat ein Angebot und jedes Ziel hat eine Nachfrage. Das Zuweisungsproblem ist eine Vereinfachung des Transportproblems, bei dem die Versorgung jeder Quelle und der Bedarf jedes Ziels 1 ist.

In Ihrem Fall haben Sie 50.000 Quellen (Ihre Arbeiter) mit jeweils einer Lieferung von 1 (jeder Arbeiter kann nur einen Job arbeiten). Sie haben auch 10 Ziele (die Jobtypen), die jeweils einen bestimmten Bedarf haben (die Anzahl der Öffnungen für diesen Typ).

Das Transportproblem wird traditionell mit dem Simplex-Algorithmus gelöst. Ich kann Ihnen nicht sagen, wie es von Kopf bis Fuß funktioniert, aber es gibt viele Informationen online, wie es gemacht wird. Ich würde diese zwei Videos empfehlen: first, second.

 

Alternativ kann der Transport tatsächlich auch mit dem ungarischen Algorithmus gelöst werden.Die Idee besteht darin, Ihr Angebot und Ihre Nachfrage getrennt zu verfolgen und dann den ungarischen Algorithmus (oder einen anderen Algorithmus für das Aufgabenproblem) zu verwenden, um Angebot und Nachfrage zu lösen (dies kann unglaublich schnell sein, wenn es einseitig ist) wie 50.000 Quellen zu 10 Zielen wie in Ihrem Fall). Sobald Sie es einmal gelöst haben, verwenden Sie die Ergebnisse, um Angebot und Nachfrage der zugewiesenen Lösung entsprechend zu verringern. Wiederholen Sie dies, bis die Summe von Angebot oder Nachfrage gleich Null ist.

Dies ist jedoch möglicherweise nicht erforderlich. Ich habe vor ein paar Jahren meinen eigenen Aufgaben-Problemlöser in C++ geschrieben, und trotz der Verwendung von 2,5 GB RAM kann er ein 50.000-mal-50.000-Zuweisungsproblem in weniger als 5 Sekunden lösen. Der Trick ist, deine eigenen zu schreiben. Bevor ich meins schrieb, schaute ich mir an, was online verfügbar war, und sie waren alle ziemlich schlecht, oft mit offensichtlichen Fehlern. Wenn Sie jedoch Ihren eigenen Code dafür schreiben, wäre es besser, den Simplex-Algorithmus zu verwenden, wie in den oben verlinkten Videos beschrieben. Ich weiß nicht, dass einer schneller ist als der andere, aber der ungarische Algorithmus wurde nicht für das Transportproblem gemacht.

 

ps: Die gleiche Person, die die beiden Vorträge habe ich oben auch eine auf der Assignment Problem and the Hungarian Algorithm tat verknüpft.