Planungsalgorithmen, die in einem Raster verwendet werden

Question

Ich versuche die Planung in einer Gitterumgebung zu simulieren. Ich weiß nicht, welche Algorithmen zu verwenden sind. Ich denke über den Planungsalgorithmus des Job Shop nach http://en.wikipedia.org/wiki/job_shop_scheduling Aber keine Kurs, wenn es in Gittern verwendet wird. Welche Algorithmen werden normalerweise in Gitterumgebungen verwendet, um eingehende Jobs für Ressourcen zu planen? Jede Hilfe wäre sehr geschätzt. Vielen Dank.

Answer 1

Es gibt viele Job-Shop-Planungsalgorithmen, die parallelisiert werden können. Sie sollten mit einer Literaturübersicht oder einer guten Referenz beginnen, wie Bruckers "Planungsalgorithmen". Die Einzelheiten Ihrer Domäne ermöglichen wahrscheinlich verschiedene polynomiale Ansätze für Pseudopolynom.

Answer 2

Job Shop Planing Ist es nicht ein Algorithmus, es ist ein Problem, soweit ich weiß.

Wenn Sie 3 oder mehr Maschinen haben, ist es NP vollständig. Es gibt eine Reihe von Algorithmen, die mit NP -vollständigen Problemen umgehen können, wie z. Tabu -Suche, Genetische Algorythmen, Simuliertes Glühen, ... einige davon können leicht multi-thread (andere hart) sein. Der Gewinn von Multi-Threading ist jedoch im Vergleich zum Gewinn der Verbesserung des Algorithmus relativ gering. Sehen Diese Folie Für den Effekt der Verbesserung der CPU/Multi-Threading gegenüber Verbesserung des Algorithmus mit einem der Beispiele von Sabberer Planer.

Answer 3

Floyd-warshall für zweigliedrige Graphen und Edmonds Blütenalgorithmus für nicht-bipartite Graphen.