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

フローショップ・スケジューリング問題（テンプレート:Lang-en-short、略称: FSP）とは、いくつかの作業が複数の機械によって全て同様の工程を経て処理される場合に、評価尺度（機械全体の稼働時間の最小化、作業の納期遅れの最小化など）を最適にするような機械の稼働スケジュール（機械ごとの仕事の処理順序）を決める問題である。組み合わせ最適化のテンプレート:仮リンクの一種である。フローショップ・スケジューリング問題はジョブショップ・スケジューリング問題の作業順序の制約がどの仕事も全て同じである特殊な問題ともいえるテンプレート:Sfn。各機械で処理する仕事の順序をどの機械も同じ順序という制約を加えたものを、特に順列フローショップ・スケジューリング問題（Permutation Flowshop Scheduling Problem、PFSP）というテンプレート:Sfn。

概要

フローショップ・スケジューリング問題（FSP）は、n個の仕事とm個の機械がが全て機械1, …, 機械mの順番で処理する場面で、各機械は常に高々1つの仕事を処理し、また一度仕事を処理し始めたら、処理を中断することができない。また各仕事が各機械でかかる処理時間はそれぞれ異なる。このとき、処理の総所要時間や納期遅れ時間などの評価尺度が最適となるように仕事の処理順序を求める問題である。

FSPでは以下の仮定の下で仕事の処理順序を求めるテンプレート:Sfn。

全ての仕事は互いに影響を受けることなく処理を行うことができ、いつでも処理を開始することができる。
各機械は連続して利用可能である。
各機械は一度に高々 1 つの仕事を処理できる。
各仕事は一度にどこか 1 つの工程のみ割り当てることができる。
仕事の処理が開始されると、その処理は中断することができない。
仕事の順序に依存した段取り時間（各工程間に必要な準備時間）を考慮しない。

仕事数n、機械数mのとき、フローショップ・スケジューリング問題の実行可能スケジュール数（組み合わせ数）は $(n!)^{m}$ である。また各機械の仕事順序が全て同一の順列フローショップ・スケジューリング問題の実行可能スケジュール数は $n!$ であるテンプレート:Sfn。仕事と機械の数が増大すると最適解を求めることが劇的に難しくなる。

評価尺度

FSPにおける評価尺度はテンプレート:仮リンク（総所要時間）を対象とすることが最も多いが、以下に説明する尺度や、またこれらを複数組み合わせた尺度も研究されていることが多いテンプレート:Sfn テンプレート:Sfn。次にFSPで用いられる代表的な評価尺度を挙げる。

テンプレート:仮リンク（総所要時間）: $C_{\max}$
テンプレート:仮リンク（Total Tardiness）: $\sum \max (0, d_{i})$
テンプレート:仮リンク（number of tardy jobs）: $\sum U_{i}$

その他の評価尺度は納期遅れ#定式化 (英語版)を参照。

メイクスパンを最小化するFSP

メイクスパンを最小化するFSPでは、機械1で処理を始めてから機械mで全ての仕事の処理を終えるのにかかった時間が最小となる仕事の処理順序を求める問題である。この問題は機械数が3以上のときNP困難であることが知られているテンプレート:Sfn。機械数m=2および一部のm=3のFSPではジョンソンによって計算量 $O (n \log n)$ で最適な仕事順序を求めるアルゴリズムのテンプレート:仮リンクが知られているテンプレート:Sfn^[1]。

脚注

テンプレート:脚注ヘルプテンプレート:Reflist

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

目次

概要

評価尺度

メイクスパンを最小化するFSP

関連問題

脚注

参考文献

関連項目

ナビゲーションメニュー

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

概要

評価尺度

メイクスパンを最小化するFSP

関連問題

脚注

参考文献

関連項目

ナビゲーション メニュー

検索

ナビゲーションメニュー