algorithm - 类似于“分配任务”的算法

Question

这是分配问题http://en.wikipedia.org/wiki/Generalized_assignment_problem

我有类似的任务，但找不到算法。我们有 m 个任务，n 个工人，m>n。任务完成后，劳动者拿下一个（如果有空闲的话）。如果任务由某个劳动者承担，其他人就无法承担。每个工人都有自己的速度：V1..Vn，每个任务都有自己的“体积”——W1..Wm。所以，我需要在劳动者之间分配任务，以尽量减少完成所有任务的时间。

请帮我找到一个算法或如何命名这个问题。）

Answer 1

这个问题是在并行的、统一相关的机器上调度作业，以最小化制造时间。由于Hochbaum 和 Shmoys，有一个多项式时间近似方案（使用双近似算法解决调度问题：理论和实践结果，1988 年）。btilly 是正确的，装箱问题密切相关；Hochbaum--Shmoys 和之前的最佳近似 MULTIFIT 的分析均基于用于装箱的首创技术。

Answer 2

这看起来像是http://en.wikipedia.org/wiki/Bin_packing_problem的一个 np-complete 变体。因此，我不会担心确切的算法。

假设任务是独立的，我的第一次尝试将是一个贪婪的启发式。给定完成时间的估计，在所有时间点为每个工人分配他们在完成时间之前可以完成的最长任务。现在进行二分搜索以找到您可以逃脱的最短完成时间。你最初的上限时间是最快的工人做所有事情的时间。您最初的较低时间是所有工人在同时工作的情况下完成那么多工作的时间。

这显然并不总是完美的。但它应该工作得相当好。