pro*_*mou 5 algorithm np-complete job-scheduling
根据iehrlich的评论(感谢顺便说一句),术语"调度"可能会产生误导,这可能是一个更恰当的描述:给定一个矩阵N*N,找到一个行排列,它将产生最大的对角线和.
我有一套N个工作和N个处理器.所有处理器可以彼此不同.对于每个(作业,处理器)对,我在该处理器上运行该作业的性能.性能以IPC(每周期指令)测量.
我正在尝试找到一个最大化IPC总和的时间表(1对1分配).我可以通过查看所有可能的时间表来完成,使用O(N!),这是不可行的.
然后,我尝试使用"稳定匹配"算法O(N ^ 2),使用IPC对工作负载和处理器的首选项进行排序.它运行速度非常快,并且返回了一个不错的时间表,但不是最佳的.
我的问题是:
1)我真的希望稳定匹配算法能够返回最优分配.有人能解释为什么会失败吗？到目前为止,我最好的猜测是不同(工作,处理器)对之间存在联系.我也尝试过"稳定匹配无差异"算法而没有运气.我应该提一下,由于我的实现,算法不会失败.我正在寻找一个更理论的答案,为什么算法本身无法解决这个问题.
2)你知道我可以使用的算法吗？甚至还存在吗？
稳定匹配是错误算法的原因是，您可能会得到这样的匹配：一对处理器各自更喜欢彼此的作业，但其中一个作业更喜欢它所在的处理器。切换会使某人的情况变得更糟，因此这种匹配是稳定的。
然而，在你的问题中，我们关心的是全局最优值。如果一项工作的进步超过了另一项工作的恶化程度，你就会想换工作。对于全局最优来说，稳定匹配是必要的，但还不够。
事实上，匈牙利算法是寻找全局最优解的正确算法。