L'équilibrage de charge. Pourquoi ne pas utiliser les files d'attente prioritaires?

Question

J'ai récemment appris sur divers algorithmes probabilistes pour l'équilibrage de charge. Le modèle est toujours qu'il ya $ m boules de $ et $ n $ bacs et les balles arrivent un à la fois. La tâche est de minimiser la charge maximale d'un bac. Cependant, il y a quelque chose que je ne comprends pas.

Pourquoi ne pas simplement garder une file d'attente prioritaire des charges des bacs et affecter tout nouveau ballon à la poubelle avec la charge actuelle le plus bas? Cela semble vous donner la charge optimale sans aucune complication.

Answer 1

Vous avez raison en utilisant une file d'attente prioritaire est une bonne idée. Il ne donne pas une réponse optimale cependant. (En supposant que ce que vous essayez d'optimiser le temps que les dernières finitions processeur exécutant le dernier emploi.) Ce problème de planification est NP-complet, et la méthode basée sur la file d'attente prioritaire donne une réponse qui est un facteur de 2 optimal. Voir, par exemple, http: // www. cs.princeton.edu/courses/archive/spr05/cos423/lectures/11approx-alg.pdf. Le wikipedia page sur Job Shop Planification donne également des informations.