將工作人員分配到工作區的算法

Question

我正在尋找一種算法來將工作人員分配給工作場所，並將不同的任務和工作負荷組合在一起。

1. 有幾個工作場所（假設工廠：F1，F2）
2. 在工作場所，有不同的任務類型的等待工作量，以各種量（讓我們在F1說每一項任務，我們需要使10件產品X，20件產品Y和30件產品Z;另一個工廠F2有不同的工作量）
3. 每個工人可以執行一個或多個工作負荷類型（W1可以使產品X，W2可以使產品X和Y，W3可以生產Y和Z），爲了簡單起見，我們假設所有的工人都具有相同的技能，產品的生產時間相等。
4. 該算法必須適用於任何非零數量的工作場所，任務類型和工作人員。顯然，如果工作場所比工作場所多，則該算法必須在迭代中運行。當一個工作場所的工作完成後，工人將重新平衡到一個不同的工作場所，剩下一些工作。

有沒有一種高效的算法，可以將工人分配給工作場所以最小化生產時間？我認爲它符合匈牙利算法，但我認爲這不是同一個問題。

感謝您的指點。

Answer 1

我認爲使用匈牙利算法的問題在於整個事情可能需要多次迭代。如果您爲匈牙利語算法提供了每個工作人員有N份副本的問題版本，那麼也許您可以找到N次迭代的最佳時間表。

在這種情況下，你可以嘗試N = 1,2,4 ...直到找到一個工作的N，然後在這個N和最高的N之間的二進制斬波試圖找不到（N/2）可以解決問題的最小N值。