Algorithme pour planifier les travaux sur les processeurs

Question

Selon le commentaire d'iehrlich (merci btw), le terme «ordonnancement» pourrait être trompeur et cela pourrait être une description plus appropriée: étant donné une matrice N * N, trouver une permutation de ligne qui donnera la plus grande somme diagonale.

J'ai un ensemble de N tâches et N processeurs. Tous les processeurs peuvent être différents les uns des autres. Pour chaque paire (travail, processeur), les performances de ce travail s'exécutent sur ce processeur. La performance est mesurée en IPC (instructions par cycle).

J'essaie de trouver un calendrier (allocation 1-à-1) qui maximise la somme globale de IPC. Je peux le faire en passant par tous les horaires possibles, avec O (N!), Ce qui n'est pas viable. J'ai ensuite essayé d'utiliser l'algorithme O (N^2) de «matching stable», en utilisant les IPC pour trier les préférences des charges de travail et des processeurs. Il fonctionne très vite et renvoie un horaire décent, mais pas le meilleur.

Mes questions sont les suivantes:

1) Je me attendais vraiment l'algorithme de correspondance stable pour être en mesure de retourner l'affectation optimale. Quelqu'un peut-il expliquer pourquoi cela échoue? Ma meilleure estimation jusqu'ici est l'existence de liens entre différentes paires (travail, processeur). J'ai aussi essayé l'algorithme "stable matching with indifference" sans aucune chance. Je dois mentionner que l'algorithme n'échoue pas à cause de ma mise en œuvre. Je cherche une réponse plus théorique pour expliquer pourquoi l'algorithme lui-même ne peut pas résoudre ce problème.

2) Connaissez-vous un algorithme que je peux utiliser pour cela? Est-ce que l'on existe même?

Answer 1

La raison pour laquelle la correspondance stable est un mauvais algorithme est que vous pouvez vous retrouver avec une correspondance où une paire de processeurs préférerait chacun des travaux de l'autre, mais l'un des travaux préfère le processeur sur lequel il se trouve. La commutation rend quelqu'un pire, donc cette correspondance est stable.

Cependant, dans votre problème, nous nous soucions de l'optimum global. Si l'amélioration d'un travail dépasse la qualité de l'autre, vous voulez changer. Pour l'optimum global, une adaptation stable est nécessaire mais pas suffisante.

L'algorithme hongrois est en fait le bon pour trouver la solution globalement optimale.