Algorithme pour affecter des travailleurs aux équipes en fonction des préférences des travailleurs

Question

Nous avons N travailleurs et ils doivent être affectés à l'une des M équipes. Chaque équipe peut avoir un maximum de K travailleurs. Chaque travailleur classe les équipes par ordre de préférence, en commençant par 1 pour l'équipe préférée jusqu'à M pour l'équipe la moins préférée. Maintenant, le problème est de trouver une correspondance, de sorte que les travailleurs se retrouvent dans l'équipe qu'ils préfèrent le plus, étant donné la contrainte que chaque équipe peut avoir un maximum de K travailleurs. Au début, je pensais, c'est un Assignment problem qui pourrait être résolu en utilisant le Hungarian Algorithm. Mais je me suis rendu compte que l'algorithme hongrois ne peut être utilisé que si chaque travailleur est affecté à un seul élément. Mais dans mon cas plusieurs travailleurs peuvent être affectés à la même équipe.

Maintenant, je ne sais pas quel genre de problème c'est vraiment. Est-ce un (multiple) Knapsack problem ou Bin packing problem? Quel type d'algorithme pourrais-je utiliser pour résoudre ce problème?

Answer 1

Il existe deux façons de résoudre ce problème, et celle qui est la plus efficace dépend du nombre de personnes et du nombre d'équipes dont vous disposez, et de la taille de K. Le moyen le plus simple (qui est déjà mentionné dans la réponse de @Alex L.) est de diviser chaque équipe en équipes K, et de convertir le problème en correspondance bipartite pondérée régulière, qui peut être résolue avec l'algorithme hongrois. Maintenant, la complexité de l'algorithme hongrois est O(n^2 * m). Ici, nous choisirions n pour être le nombre de personnes, et m pour être le nombre d'équipes. Après avoir divisé chaque équipe en k, la complexité finale sera O(n^2 * m * k).

Une autre façon est de traiter ce problème comme un problème de débit max min-cost. Vous construisez un graphique avec une source et un puits étant deux nœuds supplémentaires, tous les travailleurs directement connectés à la source avec la capacité 1 et le poids 0, toutes les équipes connectées à l'évier avec la capacité k et le poids 0, et les travailleurs connectés aux équipes de capacité 1 et coûtent en fonction de leurs préférences. Le débit max min-cost a la complexité O(n^3 * m). Maintenant, si nous choisissons le nombre de travailleurs à n et le nombre d'équipes à m, nous obtenons quelque chose qui est strictement pire que hongrois (parce que vraisemblablement k < n). Mais si nous prenons n pour être le nombre d'équipes, et m pour être le nombre de travailleurs, nous pouvons potentiellement obtenir quelque chose de mieux que hongrois, si le nombre de travailleurs est grand, le nombre d'équipes est petit, et k est également important.

Tout dépend de vos contraintes. Si m est significativement plus petit que k et n, vous êtes mieux avec un débit max min-coût, sinon il suffit de diviser les équipes en k et d'utiliser l'algorithme vanille hongrois.

Answer 2

Avec un petit ajustement, il peut devenir un problème d'affectation:

Si vous dupliquez chaque équipe en K équipes avec une capacité de 1 - alors vous aurez besoin d'assigner chaque travailleur à une équipe et chaque équipe ne peut être attribué à un travailleur.

Dans un problème d'affectation, le nombre d'agents et de tâches ne doit pas nécessairement être égal.