Algorithme d'ordonnancement pondéré des ressources d'équilibrage de charge

Question

Une application logicielle sur laquelle je travaille doit pouvoir attribuer des tâches à un groupe d'utilisateurs en fonction du nombre de tâches qu'ils ont actuellement, les utilisateurs ayant le moins de tâches à effectuer étant les plus susceptibles d'obtenir la tâche suivante. Cependant, la charge de tâches actuelle doit être traitée comme une pondération plutôt que comme une définition d'ordre absolue. IOW, je dois mettre en œuvre un algorithme d'équilibrage de charge pondéré.

Supposons qu'il y a cinq utilisateurs, avec le nombre de tâches suivant:

A: 4 B: 5 C: 0 D: 7 E: 9

Je souhaite hiérarchiser les utilisateurs pour la tâche suivante dans l'ordre CABDE, où C est le plus susceptible d'obtenir l'assignation et E, le moins probable. Il y a deux choses importantes à noter ici:

• Le nombre d'utilisateurs peut varier de 2 à plusieurs dizaines.
• Le nombre de tâches assignées à chaque utilisateur peut varier de 1 à plusieurs centaines.

Pour l'instant, nous pouvons traiter toutes les tâches de la même manière, même si cela ne me dérangerait pas d'inclure la tâche difficile en tant que variable que je pourrais utiliser à l'avenir - mais ceci est une pure cerise sur le gâteau.

Les idées que j'ai proposées jusqu'à présent ne sont pas très bonnes dans certaines situations. Ils peuvent pondérer les utilisateurs de trop près les uns des autres s’il ya un grand nombre d’utilisateurs, ou bien s’effondrer si un utilisateur n’a pas de tâches en cours, ou ....

J'ai essayé de parcourir le Web, mais je n'ai pas eu beaucoup de chance. Quelqu'un peut-il me donner un résumé rapide d'un algorithme qui fonctionnerait bien? Je n'ai pas besoin d'une implémentation réelle - je vais faire cette partie - juste une bonne description. Alternative: existe-t-il un bon site Web librement accessible?

De plus, même si j’apprécie certainement la qualité, cela n’est pas nécessairement parfait du point de vue statistique. Donc, si vous pouvez penser à une technique bonne mais pas excellente, je suis intéressée!

Answer 1

Comme vous l'avez fait remarquer, il s'agit d'un problème d'équilibrage de charge. Ce n'est pas vraiment un problème de planification, puisque vous n'essayez pas de minimiser quoi que ce soit (temps total, nombre de travailleurs simultanés, etc.). Il n’existe aucune contrainte particulière (durée de l’emploi, conflits de temps, compétences à faire correspondre, etc.). Votre problème se résume donc à la sélection d’une fonction de pondération appropriée.

Vous dites que vous souhaitez éviter certaines situations, comme une pondération trop rapprochée des utilisateurs. Pouvez-vous fournir plus de détails? Par exemple, qu'y a-t-il de mal à faire en sorte que les chances d'être affecté soient proportionnelles à la charge de travail actuelle, normalisée par la charge de travail des autres travailleurs? Vous pouvez visualiser cela comme une séquence de blocs de différentes longueurs (les tâches), placés dans un ensemble de bacs (les ouvriers), dans lesquels vous essayez de garder la hauteur totale des bacs aussi uniforme que possible.

Avec plus d'informations, nous pourrions vous recommander des fonctions qui pourraient fonctionner pour vous.

Éditer: exemples de fonctions d'équilibrage de charge

Sur la base de vos commentaires, voici quelques exemples de fonctions simples pouvant vous donner un comportement d'équilibrage différent. Une question fondamentale est de savoir si vous voulez un comportement déterministe ou probabiliste. Je vais vous donner quelques exemples.

Pour utiliser l'exemple de la question, 4 + 5 + 0 + 7 + 9 = 25 tâches actuellement attribuées. Vous voulez choisir qui aura le travail 26.

1) Une batterie de tâches simple. Pour chaque travail, sélectionnez toujours le travailleur ayant le moins de travaux en attente. Les travailleurs rapides ont plus à faire, mais tout le monde termine à peu près au même moment.

2) Garantissez une charge de travail équitable. Si les travailleurs travaillent à des vitesses différentes et que vous ne voulez pas en faire plus que d'autres, suivez le nombre de travaux terminés + en attente pour chaque travailleur. Attribuez le travail suivant pour que ce nombre soit uniformément réparti (les travailleurs rapides bénéficient de pauses gratuites).

3) Normalisation linéaire de base. Choisissez un nombre maximal de travaux pour chaque travailleur. La charge de travail de chaque travailleur est normalisée à ce nombre. Par exemple, si le nombre maximum de tâches / travailleur est de 15, vous pouvez ajouter 50 tâches supplémentaires avant que vous n'atteigniez votre capacité maximale. Donc, pour chaque travailleur, la probabilité d’être affecté au prochain travail est

P(A) = (15 - 4)/50 = 0.22  
P(B) = (15 - 5)/50 = 0.2  
P(C) = (15 - 0)/50 = 0.3  
P(D) = (15 - 7)/50 = 0.16  
P(E) = (15 - 9)/50 = 0.12

Si vous ne souhaitez pas utiliser un seuil maximal spécifique, vous pouvez utiliser le serveur avec le nombre actuel le plus élevé de travaux en attente comme limite. Dans ce cas, c’est le travailleur E, donc les probabilités seraient

P(A) = (9 - 4)/20 = 0.25  
P(B) = (9 - 5)/20 = 0.2  
P(C) = (9 - 0)/20 = 0.45 
P(D) = (9 - 7)/20 = 0.1  
P(E) = (9 - 9)/20 = 0

Notez que dans ce cas, la normalisation garantit que le travail E ne peut se voir attribuer aucun travail - il est déjà à la limite. De plus, le fait que C n’ait rien à faire ne signifie pas qu’il aura la garantie de trouver un nouvel emploi (c’est plus probable).

Vous pouvez facilement implémenter la fonction de choix en générant un nombre aléatoire r compris entre 0 et 1 et en le comparant à ces limites. Donc si r est & Lt; 0,25, A obtient le travail, 0,25 & Lt; r < 0,45, B obtient le travail, etc.

4) Normalisation non linéaire. L'utilisation d'une fonction de journalisation (au lieu de la soustraction linéaire) pour pondérer vos nombres est un moyen simple d'obtenir une normalisation non linéaire. Vous pouvez l'utiliser pour biaiser les probabilités, par exemple. pour rendre beaucoup plus probable que les travailleurs sans beaucoup d'emplois reçoivent plus.

Le fait est que le nombre de façons de le faire est pratiquement illimité. La fonction de pondération que vous utilisez dépend du comportement spécifique que vous essayez d'activer. J'espère que cela vous a donné quelques idées que vous pouvez utiliser comme point de départ.