负载均衡。为什么不使用优先级队列呢？

Question

我最近了解了负载平衡的各种随机算法。该模型始终是有 $m$ 个球和 $n$ 个箱子，并且每次到达一个球。任务是最小化任何垃圾箱的最大负载。不过，有件事我不明白。

为什么不只保留垃圾箱负载的优先级队列并将任何新球分配给当前负载最低的垃圾箱？这似乎可以为您提供最佳负载，而不会出现任何并发症。

Answer 1

您是正确的，使用优先级队列是一个好主意。但它并没有给出最佳答案。（假设您要尝试优化的是最后一个处理器完成执行最后一个作业的时间。）此调度问题是 NP 完全问题，并且基于优先级队列的方法给出的答案在最佳值的 2 倍之内。例如，参见 http://www.cs.princeton.edu/courses/archive/spr05/cos423/lectures/11approx-alg.pdf. 。这 有关车间调度的维基百科页面 还给出了一些信息。