第二种负载平衡和斯特林数应用

Question

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

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

一个简单而精确的方法来做这样的“调度”将不得不考虑S（N，P）任务分区，其中S（N，P）是第二类斯特林数（应该是不切实际的大真实世界的计算）。

问：是否有用于计算这种“负载均衡”任务分区的良好且高效的近似算法？

Answer 1

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