类似于 'assignment task' 的算法

Question

这里是赋值问题http://en.wikipedia.org/wiki/Generalized_assignment_problem

我有一个类似的任务，但找不到算法。我们有 m 个任务，n 个劳动者，m>n。任务完成后，劳动者拿走下一个(如果有空闲的话)。如果任务由某个劳动者承担，则其他人无法承担。每个劳动者都有自己的速度:V1..Vn，每个任务都有自己的“体积”-W1..Wm。因此，我需要以最小化完成所有任务的时间为目标在劳动者之间分配任务。

请帮我找到一个算法或者这个问题是如何命名的。)

Answer 1

这个问题是在并行的、统一相关的机器上安排作业，以最小化完工时间。由于Hochbaum and Shmoys，有一个多项式时间近似方案(使用对偶逼近算法解决调度问题:理论和实践结果，1988 年)。 btilly 是正确的，装箱问题是密切相关的； Hochbaum--Shmoys 和之前的最佳近似 MULTIFIT 的分析都是基于为 bin packing 开创的技术。