Scheduling algorithms used in a grid

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.

---

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.

---

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 for bipartite graphs and Edmond's Blossom algorithm for non-bipartite graph.