算法在處理器上調度作業

Question

根據iehrlich的評論（感謝btw），術語「調度」可能是誤導，這可能是一個更合適的描述：給定一個矩陣N * N，找到一個行排列，將產生最大的對角線總和。

我有一組N個就業機會和N處理器。所有處理器可以彼此不同。對於每個（作業，處理器）對，我都具有在該處理器上運行該作業的性能。性能是在IPC（指令每週期）中測量的。

我試圖發現最大化IPC的整體和時間表（1對1的分配）。我可以通過檢查所有可能的時間表，用O（N！），這是不可行的。

我然後試圖使用「穩定的匹配」算法O（N^2），使用所述的IPC到負載和處理器的偏好進行排序。它運行速度非常快，並返回一個體面的時間表，但不是最佳的時間表。

我的問題是：

1）我真的很期待穩定的匹配算法能夠回到最佳分配。有人可以解釋爲什麼它失敗了嗎？迄今爲止，我最好的猜測是不同（工作，處理器）對之間存在關係。我也嘗試了「無差別穩定匹配」算法，但沒有運氣。 我應該提到，算法不會因爲我的實現而失敗。我正在尋找更爲理論上的答案，爲什麼算法本身無法解決這個問題。

2）你知道的算法，我可以使用這個的？有人甚至存在嗎？

Answer 1

之所以穩定匹配是錯誤的算法是，你可以用匹配風，其中一對處理器將各自喜歡對方的工作，但工作的一個更喜歡它的處理器。切換會讓某人變得更糟，所以這種匹配是穩定的。

但是，在您的問題我們關心，如果全球最佳。如果一項工作的改進超過了另一項工作的改善，那麼你就需要改變。對於全局最優的穩定匹配是必要的，但並不充分。

其實匈牙利算法是尋找全局最優解是正確的。