算法在处理器上调度作业

Question

根据iehrlich的评论（感谢btw），术语“调度”可能是误导，这可能是一个更合适的描述：给定一个矩阵N * N，找到一个行排列，将产生最大的对角线总和。

我有一组N个就业机会和N处理器。所有处理器可以彼此不同。对于每个（作业，处理器）对，我都具有在该处理器上运行该作业的性能。性能是在IPC（指令每周期）中测量的。

我试图发现最大化IPC的整体和时间表（1对1的分配）。我可以通过检查所有可能的时间表，用O（N！），这是不可行的。

我然后试图使用“稳定的匹配”算法O（N^2），使用所述的IPC到负载和处理器的偏好进行排序。它运行速度非常快，并返回一个体面的时间表，但不是最佳的时间表。

我的问题是：

1）我真的很期待稳定的匹配算法能够回到最佳分配。有人可以解释为什么它失败了吗？迄今为止，我最好的猜测是不同（工作，处理器）对之间存在关系。我也尝试了“无差别稳定匹配”算法，但没有运气。 我应该提到，算法不会因为我的实现而失败。我正在寻找更为理论上的答案，为什么算法本身无法解决这个问题。

2）你知道的算法，我可以使用这个的？有人甚至存在吗？

Answer 1

之所以稳定匹配是错误的算法是，你可以用匹配风，其中一对处理器将各自喜欢对方的工作，但工作的一个更喜欢它的处理器。切换会让某人变得更糟，所以这种匹配是稳定的。

但是，在您的问题我们关心，如果全球最佳。如果一项工作的改进超过了另一项工作的改善，那么你就需要改变。对于全局最优的稳定匹配是必要的，但并不充分。

其实匈牙利算法是寻找全局最优解是正确的。