シフティングボトルネック法

提供: ORWiki
ナビゲーションに移動 検索に移動

【しふてぃんぐぼとるねっくほう (shifting bottleneck procedure)】

ジョブショップスケジューリングの有力な解法の1つである. まだ順序づけの済んでいない各機械に対して一機械最適順序づけを行い, 最大完了時間などの評価値を求め, その最大値を与えるボトルネック機械を見つける. ボトルネック機械を含む順序づけの済んだ機械群の中で最長経路(longest path)上の極限機械(critical machine)に対して一機械最適順序づけを行うことにより再最適化を行う. この手順をすべての機械の順序づけが終わるまで繰り返す.