Scheduling algorithms used in a grid

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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