此问题可以模拟为 Maximum Flow Problem。
在最大流问题中，您有一个有两个特殊节点的源节点和接收节点的有向图。图中的边具有容量，并且您的目标是将源中的流图分配给接收器，而不会超出任何边的容量。
通过（非常）精心制作的图表，我们可以从最大流程中找到满足您要求的任务。
让我编号的要求。
要求：
1. Workers are assigned no more than their maximum assignments.
2. Tasks can only be assigned to workers that match one of the task's interests.
3. Every task must be assigned to 3 workers.
4. Every worker must be assigned to at least 1 task.
可选：
5. Each worker should be assigned a number of tasks proportional to that worker's maximum assignments
6. Each worker should be assigned a variety of tasks.
我假设的最大流量是使用 Edmonds-Karp Algorithm找到。
我们首先找到符合要求1-3的图。
将图形绘制为4列节点，其中边线仅从列中的节点到邻近列中的节点向右。
在第一列中我们有源节点。在下一列中，我们将为每个工作人员提供节点。从源头上看，每个工人的能力与工人的最大分配量相等。这将强制执行要求1.
在第三列中，每个任务都有一个节点。从第二列中的每个工作人员看，该工作人员感兴趣的每个任务的边缘容量为1（如果他们的兴趣交集非空，则工作人员对任务感兴趣）。这将执行要求2。1的容量将确保每个工作人员仅为每个任务的3个插槽中的1个插槽。
在第四栏中我们有水槽。有一个从每个任务水槽边缘与容量3.这将强制要求3
现在，我们发现在使用Edmonds-Karp算法此图的最大流量。如果这个最大流量小于3 * (# of tasks)那么没有分配满足要求1-3。如果没有，就有这样的任务，我们可以通过检查最终的增强图来找到它。在增强图中，如果从任务到具有容量1的工人的边缘，则该工人被分配到该任务。
现在，我们将修改我们的图形和算法以满足其余的要求。
首先，让我们满足需求4.这将需要一个小的变化的算法。最初，将从源到工人的所有容量设置为1.在此图中查找最大流量。如果流量不等于工人数量，则没有分配会议要求4.现在，在您的最终残差图中，对于每个工人，从源到该工人的边缘具有容量0，反向边具有容量1 。分别将这些更改为that worker's maximum assignments - 1和0。现在像以前一样继续Edmonds-Karp算法。基本上我们所做的就是先找到一个任务，让每个工人分配到一个任务。然后从该任务中删除反向边，以便始终将该工作人员分配给至少一个任务（尽管可能不是第一次分配的任务）。
现在，让我们满足要求5.严格来说，这个要求只是意味着我们通过sum of all worker's maximum assignments/number of tasks将每个工人的最大任务。这很可能不会有令人满意的任务。但没关系。用这些新的最大分配初始化我们的图。运行埃德蒙兹卡普。如果它发现一个使任务到边缘的边缘饱和的流程，我们就完成了。否则，我们可以在残差图中增加从接收器到工人的能力，并继续运行Edmonds-Karp。重复，直到我们将边缘浸入水槽。不要过多地增加容量，以至于工人分配的任务太多。另外，技术上，每个工人的增量应该与该工人的最大分配成正比。这些都很容易做到。
最后让我们来满足要求6.这一个有点棘手。首先，在工作人员和任务之间添加一列，并从工作人员的任务中删除所有边缘。在这个新的专栏中，为每个工人添加一个节点，用于每个工人的兴趣。从这些新节点中的每一个节点，为具有容量1的匹配兴趣的每个任务添加一条边。将每个工作者的边添加到其容量为1的每个感兴趣节点。现在，此图中的流将强制如果工人被分配给n个任务，那么这些任务的利益与该员工的利益的交集至少为n。同样，如果没有这项任务，可能会有令人满意的任务，但是没有任何人能够完成这项任务。我们可以像要求5一样处理这个问题：运行Edmonds-Karp来完成任务，如果没有满意的任务，将工人的能力增加到他们的兴趣节点并重复。
注意，在这个修改的图我们不再满足要求3，作为一个工人可以被分配给一个任务的多个/所有插槽，如果他们的利益的交集有大小比1，我们可以解决这个问题更大。在兴趣节点和任务节点之间添加一列新节点，并删除这些节点之间的边。对于每个员工，在新列中为每个任务插入一个节点（因此每个员工对于每个任务都有自己的节点）。从这些新节点到其右侧相应的任务，添加容量为1的边。从每个工作人员的兴趣节点到该工作人员的任务节点，将每个感兴趣的容量为1的边添加到每个匹配的任务。
-
编辑：让我试图澄清这一点。假设-(n)->是n容量的边。
以前我们有worker-(1)->task为每个具有匹配兴趣的工作 - 任务对。现在我们有worker-(k)->local interest-(1)->local task-(1)->global task。现在，您可以考虑将任务与工人利益对匹配。第一条边说，对于一名工人来说，它的每个利益都可以匹配到k任务。第二个优势是每个工作人员的兴趣只能匹配一次到每个工作。第三条边说，每个任务只能分配给每个工人一次。请注意，您可以将多个流从工作人员推送到本地任务（等于他们感兴趣的交集的大小），但由于第三个边缘，只有1个流从工作人员流向全局任务节点。
-
还要注意的是，我们不能真正与一个要求5正确混合此递增。然而，对于worker-> interest边缘，我们可以对每个容量{1,2，...，r}运行整个算法一次。然后，我们需要一种方法来对作业进行排序。也就是说，当我们放宽要求5时，我们可以更好地满足要求6，反之亦然。不过，我还有另一种方法可以放松这些限制。
一种更好的方法来要求放松（灵感 - 通过/拍摄 - 从templatetypedef）
当我们希望能够放宽多种需求（例如，5和6），我们可以将其模型化为最小成本最大流量问题。这可能比我上面描述的增量搜索更简单。
例如，对于需求5，将所有边缘成本设置为0.我们有从源头到工人的初始边，容量等于worker's maximum assignments/(sum of all worker's maximum assignments/number of tasks)，成本为0.然后，您可以添加另一个边该工作人员的能力和成本1.另一种可能性是使用某种累进成本，以便在向工作人员添加任务时向该用户添加其他任务的成本增加。例如。您可以将工作人员的剩余容量分成单独的边，费用为1,2,3,4,...。
然后可以在工作节点和需求6的本地感兴趣节点之间做类似的事情。加权需要平衡以反映不同需求的相对重要性。
该方法也足以执行要求4.此外，要求5的成本可能应该使得它们与工人的最大分配成比例。然后分配1组额外的任务是用最大100人员将不及成本，最大2
复杂性分析分配额外的工人
让n = # of employees，m = # of tasks，k = max interests for a single task/worker，l = # of interests ，j = maximum of maximum assignments。
要求3意味着n = 0（m）。我们还假设l = O(m)和j = O(m)。
在较小的图中（在对请求6进行更改之前），该图具有n + m + 2 = O(m)顶点和至多n + m + k*min(n, m) = O(km)边缘。
的变化之后，它具有2 + n + n * l + n * m + m = O(nm)顶点和n + k * n + k * m * n + n * m + m = O(kmn)边缘（在技术上，我们可能需要更多的j * n + j * l节点和边缘，以便有没有从一个节点到另一个节点的多个边缘，但是这不会改变渐进绑定）。还要注意，没有边需要容量> j。
使用最小成本最大流量配方，我们可以在O(VEBlogV)中找到解决方案，其中V = # vertices，E = # edges和B = max capacity on a single edge。在我们的情况下，这给出O(kjn^2m^2log(nm))。
这是一个很棒的问题，但我很好奇你是否可以对你想要优化的内容做更具体的描述。是否有一些特定的价值想要最大化或最小化？如果是这样，你能告诉我们它是什么吗？现在这是一个有趣的问题，但我认为这有点低估。 – templatetypedef 2011-01-21 23:51:12
目标是诚实地分配更公平的任务。目前没有一个正式的算法，更多的是一种强力“循环通过任务，从首先按照最少匹配工作人员的任务排序，然后分配给工人，按已分配的人数排序”这最终会导致一些工作人员得到太多或太少的任务。 – 2011-01-25 07:16:51