处理器上作业调度算法

Question

根据iehrlich的评论(谢谢)，“调度”一词可能有误导性，这可能是一个更恰当的描述:给定一个矩阵N*N，找到一个将产生最大对角线和的行置换。

我有一组N个作业和N个处理器。所有处理器都可以彼此不同。对于每一对(作业、处理器)，我都能在该处理器上运行该作业的性能。性能用IPC (每周期指令)来衡量。

我试图找到一个计划(1比1的分配)，最大限度地提高IPC的总体总和。我可以用O(N!)检查所有可能的时间表，这是不可行的。

然后我尝试使用“稳定匹配”算法O(N^2)，使用IPC对工作负载和处理器的首选项进行排序。它运行非常快，并返回一个不错的时间表，但不是最优的。

我的问题是：

( 1)我确实期望稳定匹配算法能够返回最优分配。有人能解释一下为什么失败吗？到目前为止，我最好的猜测是在不同的(作业，处理器)对之间存在联系。我也尝试了“稳定匹配与漠不关心”算法，没有运气。--我应该提到，该算法不会因为我的实现而失败。对于为什么算法本身不能解决这个问题，我正在寻找一个更理论的答案。。

2)你知道我能用什么算法吗？有一个存在吗？

Answer 1

稳定匹配是错误的算法的原因是，您可能会得到一个匹配，其中一对处理器会彼此偏爱对方的任务，但是其中一个任务更喜欢它所使用的处理器。切换会使人更糟糕，所以这种匹配是稳定的。

然而，在你的问题上，我们关心的是全局最优。如果一份工作的改进超过了另一份工作的糟糕程度，你想换一份工作。对于全局最优，一个稳定的匹配是必要的，但还不够。

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