此問題可以模擬爲 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