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

Question

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

Answer 1

2部グラフの場合はFloyd-Warshall、非2部グラフの場合はEdmond'sBlossomアルゴリズム。

Answer 2

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

Answer 3

Job Shop Schedulingはアルゴリズムではなく、私の知る限り問題です。

3台以上あればNPコンプリートです。Tabu Search、Genetic Algorithms、Simulated Annealingなど、NP 完全問題を処理できるアルゴリズムがたくさんあります。簡単にマルチスレッド化できるものもあります (難しいものもあります)。しかし、マルチスレッド化によるメリットは、アルゴリズムの改善によるメリットに比べると小さいものです。Drools Plannerの例の 1 つを使用して、アルゴリズムを改善した CPU/マルチスレッド VS の改善の効果については、このスライドを参照してください。