combinatorics - 应用负载均衡和第二类斯特林数

Question

比如说，我有 P 个线程和 N > P 个任务要使用上述方法执行。我有一个与每个任务相关的正整数值，表示该特定任务意味着多少工作。

我想在 P 个线程之间划分 N 个任务，这样如果我们考虑每个线程的“工作整数”之和，它们将大致相同。

进行这种“调度”的一种简单但精确的方法必须考虑 S(N,P) 任务分区，其中 S(N,P) 是第二类斯特林数（在现实世界的计算中应该是不切实际的大）。

问：有没有什么好的高效的近似算法来计算这种“负载均衡”的任务划分？

Answer 1

如果您只有 2 个处理器，则将任务分成两个相等的任务的问题称为分区问题。众所周知，它是 NP 难的。因此，这可能表明找到最佳解决方案可能是一个难题。我只想要一个近似值，我会选择某种贪婪算法：系统地将最大的剩余任务分配给工作量较少的线程。这将为您提供一个易于实现的算法，时间复杂度为 O（任务数 * 线程数）。