网格中使用的调度算法
我正在尝试在网格环境中模拟调度。我不知道该使用什么算法。我正在考虑作业车间调度算法http://en.wikipedia.org/wiki/Job_shop_scheduling但是不知道是否在网格中使用。在网格环境中通常使用哪些算法来将传入作业调度到资源？任何帮助将不胜感激。谢谢。
I am trying to simulate scheduling in a grid environment. I don't know what algorithms to use. I am considering Job Shop Scheduling algorithm http://en.wikipedia.org/wiki/Job_shop_scheduling but dunno if it is used in grids. What algorithms are typically used in grid environments for scheduling incoming jobs to resources?. Any help would be much appreciated. Thanks.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
有许多作业车间调度算法可以并行化。您应该从文献综述或好的参考文献开始，例如布鲁克的“调度算法”。您的领域的细节可能允许或不允许各种伪多项式时间方法。
There are many job-shop scheduling algorithms that can be parallelized. You should start with a literature review or a good reference, like Brucker's "Scheduling Algorithms." The particulars of your domain are likely to allow or disallow various pseudo-polynomial time approaches.
作业车间调度不是一种算法，据我所知，这是一个问题。
如果您有 3 台或更多机器，则它是 NP 完全的。有很多算法可以处理 NP 完全问题，例如禁忌搜索，遗传算法，模拟退火，......一些其中可以很容易地实现多线程（其他则很难）。但与改进算法的增益相比，多线程的增益相对较小。请参阅 这张幻灯片通过 流口水规划师。
Job Shop Scheduling isn't an algorithm, it's a problem as far as I know.
If you have 3 or more machines, it's NP complete. There are bunch of a algorithms that can deal with NP complete problems, such as Tabu Search, Genetic Algorithms, Simulated Annealing, ... Some of which can be multi-threaded easily (others hard). But the gain of multi-threading is relatively small compared to the gain of improving the algorithm. See this slide for the effect of improving CPU/multi-threading VS improving the algorithm with one of the examples of Drools Planner.
Floyd-Warshall 用于二分图，Edmond's Blossom 算法用于非二分图。
Floyd-Warshall for bipartite graphs and Edmond's Blossom algorithm for non-bipartite graph.