根据iehrlich的评论(感谢顺便说一句),术语"调度"可能会产生误导,这可能是一个更恰当的描述:给定一个矩阵N*N,找到一个行排列,它将产生最大的对角线和.
我有一套N个工作和N个处理器.所有处理器可以彼此不同.对于每个(作业,处理器)对,我在该处理器上运行该作业的性能.性能以IPC(每周期指令)测量.
我正在尝试找到一个最大化IPC总和的时间表(1对1分配).我可以通过查看所有可能的时间表来完成,使用O(N!),这是不可行的.
然后,我尝试使用"稳定匹配"算法O(N ^ 2),使用IPC对工作负载和处理器的首选项进行排序.它运行速度非常快,并且返回了一个不错的时间表,但不是最佳的.
我的问题是:
1)我真的希望稳定匹配算法能够返回最优分配.有人能解释为什么会失败吗？到目前为止,我最好的猜测是不同(工作,处理器)对之间存在联系.我也尝试过"稳定匹配无差异"算法而没有运气.我应该提一下,由于我的实现,算法不会失败.我正在寻找一个更理论的答案,为什么算法本身无法解决这个问题.
2)你知道我可以使用的算法吗？甚至还存在吗？