Balanceo de carga. ¿Por qué no usar colas prioritarias?

Question

Recientemente aprendí sobre varios algoritmos aleatorios para el equilibrio de carga. El modelo siempre es que hay $ M $ bolas y $ n $ contenedores y las bolas llegan una a la vez. La tarea es minimizar la carga máxima de cualquier contenedor. Sin embargo, hay algo que no entiendo.

¿Por qué no simplemente mantener una cola prioritaria de las cargas de los contenedores y asignar cualquier bola nueva al contenedor con la carga de corriente más baja? Esto parece darle la carga óptima sin complicaciones.

Answer 1

Tiene razón en que usar una cola prioritaria es una buena idea. Sin embargo, no da una respuesta óptima. (Suponiendo que lo que está tratando de optimizar es el momento en que el último procesador termina de ejecutar el último trabajo). Este problema de programación es NP Complete, y el método basado en la cola prioritaria ofrece una respuesta que está dentro de un factor de 2 de óptimo. Ver, por ejemplo, http://www.cs.princeton.edu/courses/archive/spr05/cos423/lectures/11approx-alg.pdf. los Página de Wikipedia en la programación de la tienda de empleo También proporciona información.