网格中使用的调度算法

Question

我想模拟网格环境中的调度。我不知道使用什么算法。我正在考虑Job Shop Scheduling算法http://en.wikipedia.org/wiki/Job_shop_scheduling，但不知道它是否在网格中使用。网格环境中通常使用哪些算法来将传入作业安排到资源？任何帮助将非常感激。谢谢。

Answer 1

有许多可以并行化的作业车间调度算法。你应该从文献综述或者一个很好的参考文献开始，比如Brucker的“调度算法”。您的域的详细信息可能允许或禁止各种伪多项式时间方法。

Answer 2

作业车间调度不是一个算法，这是一个问题，据我所知。

如果您有3台或更多机器，它是NP完成。有一堆算法可以处理NP完整问题，如禁忌搜索,遗传算法,模拟退火，...其中一些可以容易地多线程（其他难）。但与改进算法的收益相比，多线程的收益相对较小。请参阅this slide以获得改善CPU /多线程的效果，并通过Drools Planner的其中一个示例改进算法。

Answer 3

Floyd-Warshall for bipartite graph and Edmond's Blossom algorithm for non-bipartite graph。