algorithm - 工作分配算法

Question

我们有一个 worker 列表和一个要分配给这些 worker 的任务列表。每个任务都属于一个特定类别(大约 10000 个任务的大约 50 个类别)。每个 worker 可以处理一组类别(每个 worker 大约 5 个类别)。此外，每个 worker 都有最大数量的任务可以分配给他。

我们需要将任务分配给 worker ，这样

a) 可以分配的最大任务数
b) 没有为 worker 分配任务，该任务超出了 worker 类别集
c) 没有 worker 闲着，如果有任务分配给他的话
d) 分配给任何 worker 的任务数应小于他的最大分配数

示例数据:

a) 任务-类别关系

T1 - C1
T2 - C1
T3 - C1
T4 - C2
T5 - C1
T6 - C3
..... (around 10k tasks, 50 categories)

b) Workers-类别-最大任务数

W1 (100) - C1 
W1 (100) - C2 
W2 (20) - C1
W2 (20) - C3
..... (around 50 workers, each can work on around 5 categories). 
      Where 100 for W1 means W1 can be assigned maximum 100 tasks 
      (across all categories, it is mapped with).

我试过遍历 worker 并获取他们的相关任务并一个一个地完成他们的分配，但是它有一个漏洞，对于一些 worker 很少的类别，分配是不公平的，一些 worker 闲置而有些类别还有剩余的任务，可以通过将任务洗牌给其他一些工作人员来更有效地分配任务。

例如，如果 C1 有 2000 个任务和三个 worker W1、W2、W3，每个 worker 最多有 1000 个任务。 C2 有 1000 个任务，只与 W1 相关联。如果我们将 C1 任务分配给 W1 和 W2，使其达到最大容量(每个任务 1000 个任务)，则我们无法分配 C2 的任务，因为关联的工作人员 W1 已被 C1 完全占用。如果我们将 C1 任务分配给 W2 和 W3，我们就可以分配所有任务。

我需要一些可以高效且公平地完成作业的算法。如果有人已经解决或知道我可以使用/探索的可能的解决方案/资源，请提出建议。

Answer 1

http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=maxFlow2

“最大二分匹配”中的示例是一个经典的“为 worker 分配工作”任务。您只需要将每个工作人员仅链接到其类别内的任务。图论是你的 friend 。