將工作分配給工作人員

Question

我一直在研究一個全面的構建系統，該系統在多臺機器上執行分佈式構建已經有相當長的一段時間了。它能夠正確處理依賴關係，並且看起來可以很好地擴展，所以我們添加了更多的項目和更多的機器，但看起來它可能表現更好。

我遇到的問題是資源分配問題。我有一個可用機器列表和一個我想要構建的項目列表，每臺機器還列出了什麼軟件，操作系統，編譯器版本等等，並且每個項目都列出了它需要的內容。當需要分配工作時，我可以運行一個數據庫查詢，列出可能的分配。現在我需要儘可能有效地執行這些任務。

最小的例子是兩個項目1和2與兩臺機器A和B.機器A可以建立任一個項目，但機器B只能建立項目1.所以我最終得到一個列表對（A，1）， （A，2），（B，1）。如果我按順序處理作業，則機器A構建項目1，我必須等到它完成後才能構建項目2.將機器A分配到項目2並將機器B分配到項目1可能會更好。機器A可能比機器B快得多，根本不使用機器B可能是正確的答案。

我確定這是一種'運營研究'問題，之前已經解決了很多次。我不一定需要一個最佳的解決方案......只是嘗試比我更好的東西 - 看起來我經常會排隊排隊和機器閒置，這樣可以避免更好的分配。任何建議最受歡迎。

Answer 1

您試圖解決的問題等同於傳統的Job Shop Scheduling問題。找到一個最佳的時間表是NP難。人們發明了大量的啓發式方法來生成時間表，但哪些是好的，是高度依賴於問題的。

一對夫婦共同啓發是：

• 附表最短的任務第一。
• 首先安排受限制最高的任務，例如，首先選擇可以在最少機器上運行的任務。

Answer 2

首先想到的是，我建議在每臺機器上運行Windows服務，其中一臺機器也運行主服務來協調分配。主服務輪詢每臺機器是否正在處理分配，如果不是，則開始處理其能夠處理的隊列中的任何分配。

Answer 3

要開始，我的首選是「拉」模型。

每臺機器在空閒時都會從中央服務器中提取任務。

中央服務器提供了一種優先級隊列，其中包依賴性順序。每臺機器都向中央服務器發出請求，並分配一些工作要做。

您有一種池模式，您有任務分類以及具有匹配分類的機器池。例如，池1中的機器可以構建某些東西。池2中的機器可以構建任何東西。把他們想象成「技能」，你會看到這是一種項目管理問題。

如果你的機器真的很慢，你必須手動優化它們到一個單獨的池中，這樣它們只能得到沒有依賴關係的小分支。

這可能是你所需要的。但是，如果你想進一步優化，這是你的下一步。

當你運行了幾次 - 並對性能有一些期望 - 然後你可以編寫一個模塊，試圖保持每臺機器儘可能忙。這個調度正是Microsoft Project所做的。

給定的任務，持續時間和依賴關係，你試圖做「資源調配」。您希望每種資源（在您的情況下編譯客戶端）儘可能地儘可能與每個客戶的技能和生產力保持一致。