algorithm - 网格中使用的调度算法

Question

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

Answer 1

有许多可以并行化的作业车间调度算法。您应该从文献综述或好的参考资料开始，例如 Brucker 的“调度算法”。您的领域的细节可能允许或不允许各种伪多项式时间方法。

Answer 2

Job Shop Scheduling不是算法，据我所知，这是一个问题。

如果您有 3 台或更多机器，则为 NP 完成。有很多算法可以处理 NP 完全问题，例如禁忌搜索、遗传算法、模拟退火……其中一些可以轻松实现多线程（其他一些很难）。但是多线程的增益相比于改进算法的增益是比较小的。请参阅这张幻灯片，了解使用Drools Planner的示例之一改进 CPU/多线程 VS 改进算法的效果。

Answer 3

Floyd-Warshall 用于二分图，Edmond's Blossom 算法用于非二分图。