ユーザ用ツール

サイト用ツール


フローショップスケジューリング

flow shop scheduling

 フローショップ,すなわち,すべてのジョブが同一の機械順序で処理されるシステムに対するスケジューリング.すべての機械でジョブの処理順序が同一のスケジュールを特に順列(パーミュテーション)スケジュールと呼ぶ.順列スケジュールは機械が4台以上のフローショップに対して最適解になる保証はないが,近似最適解を与えることがわかっている.特に,機械が2台のフローショップで,評価基準が最大完了時刻最小化の場合,ジョンソン・アルゴリズムが最適解を与える解法として知られている.