提问者:小点点

如何将许多大小可变的工作单元拆分成大小相等的桶?


假设我有300-400个单位的工作,都有不同的大小,其中大小差异在某些情况下相当大。 有没有可能将它们拆分成固定数量的桶,这样我就可以在固定数量的工作线程之间平衡负载?


共1个答案

匿名用户

你所描述的问题被称为多处理器调度问题(它类似于背包问题的推广bin packing问题)。 寻找最优调度是一个NP难问题。 因此,没有已知的多项式时间算法来寻找最优调度。

一个简单的启发式(非最优)算法是最长处理时间:

  • 对工作单位排序,最大的在前
  • 对于每个单元,放入最早结束时间的桶中