c++ - 如何将许多可变大小的工作单元分成大小相等的桶？

Question

假设我有 300 到 400 个工作单位，它们都有不同的尺寸，在某些情况下尺寸差异很大。是否可以将它们分成固定数量的存储桶，以便我可以在固定数量的工作线程之间平衡负载？

标签： c++multithreadingalgorithmload-balancing

Answer 1

您描述的问题称为多处理器调度问题（类似于背包问题的一般化装箱问题）。众所周知，找到最佳调度是 NP-hard 的。因此，没有已知的多项式时间算法来寻找最佳调度。

一个简单的启发式（非最优）算法是最长处理时间：

• 对工作单元进行排序，最大的在前
• 对于每个单元，放入具有最早结束时间的桶中