グリッドで使用されるスケジューリング アルゴリズム

Question

グリッド環境でのスケジューリングをシミュレートしようとしています。どのようなアルゴリズムを使用すればよいのかわかりません。Job Shop のスケジューリング アルゴリズムを検討しています http://en.wikipedia.org/wiki/Job_shop_scheduling ただし、グリッドで使用されるかどうかはわかりません。グリッド環境では、受信ジョブをリソースにスケジュールするために通常どのようなアルゴリズムが使用されますか?助けていただければ幸いです。ありがとう。

Answer 1

がある 多くの 並列化可能なジョブショップ スケジューリング アルゴリズム。文献レビューや、Bruckerの「Scheduling Algorithms」のような良い参考資料から始めるとよいでしょう。ドメインの詳細によって、さまざまな擬似多項式時間アプローチが許可または禁止される可能性があります。

Answer 2

ジョブショップのスケジューリング 私が知る限り、それはアルゴリズムではありません。

3つ以上のマシンがある場合、 NP完了. 。 NPの完全な問題に対処できるアルゴリズムの束があります。 タブー検索, 遺伝的アルゴリズム, 焼き鈍し法, 、...その一部は簡単にマルチスレッドできます（他のものは難しいものです）。しかし、マルチスレッドの増加は、アルゴリズムの改善の増加と比較して比較的少ないです。見る このスライド CPU/マルチスレッドとアルゴリズムの改善を改善する効果については、の例の1つで Drools Planner.

Answer 3

Bipartiteグラフ用のFloyd-Warshallと非バイパルタイトグラフ用のEdmond's Blossom Algorithm。