「シフティングボトルネック法」の版間の差分
ナビゲーションに移動
検索に移動
細 ("シフティングボトルネック法" を保護しました。 [edit=sysop:move=sysop]) |
Albeit-Kun (トーク | 投稿記録) |
||
| 2行目: | 2行目: | ||
ジョブショップスケジューリングの有力な解法の1つである. まだ順序づけの済んでいない各機械に対して一機械最適順序づけを行い, 最大完了時間などの評価値を求め, その最大値を与えるボトルネック機械を見つける. ボトルネック機械を含む順序づけの済んだ機械群の中で最長経路(longest path)上の極限機械(critical machine)に対して一機械最適順序づけを行うことにより再最適化を行う. この手順をすべての機械の順序づけが終わるまで繰り返す. | ジョブショップスケジューリングの有力な解法の1つである. まだ順序づけの済んでいない各機械に対して一機械最適順序づけを行い, 最大完了時間などの評価値を求め, その最大値を与えるボトルネック機械を見つける. ボトルネック機械を含む順序づけの済んだ機械群の中で最長経路(longest path)上の極限機械(critical machine)に対して一機械最適順序づけを行うことにより再最適化を行う. この手順をすべての機械の順序づけが終わるまで繰り返す. | ||
| + | |||
| + | [[Category:スケジューリング|しふてぃんぐぼとるねっくほう]] | ||
2008年11月9日 (日) 18:29時点における最新版
【しふてぃんぐぼとるねっくほう (shifting bottleneck procedure)】
ジョブショップスケジューリングの有力な解法の1つである. まだ順序づけの済んでいない各機械に対して一機械最適順序づけを行い, 最大完了時間などの評価値を求め, その最大値を与えるボトルネック機械を見つける. ボトルネック機械を含む順序づけの済んだ機械群の中で最長経路(longest path)上の極限機械(critical machine)に対して一機械最適順序づけを行うことにより再最適化を行う. この手順をすべての機械の順序づけが終わるまで繰り返す.