Load balancing. Why not use priority queues?

Question

I have recently learned about various randomized algorithms for load balancing. The model is always that there are $m$ balls and $n$ bins and the balls arrive one at a time. The task is to minimize the maximum load of any bin. However there is something I don't understand.

Why not just keep a priority queue of the loads of the bins and allocate any new ball to the bin with the lowest current load? This seems to give you the optimal load without any complications.

Answer 1

You are correct that using a priority queue is a good idea. It doesn't give an optimal answer though. (Assuming that what you are trying to optimize is the time that the last processor finishes executing the last job.) This scheduling problem is NP-complete, and the priority queue based method gives an answer that is within a factor of 2 of optimal. See, for example, http://www.cs.princeton.edu/courses/archive/spr05/cos423/lectures/11approx-alg.pdf. The wikipedia page on Job Shop Scheduling also gives some information.