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

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

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

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

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

 評価尺度 
FSPにおける評価尺度は（総所要時間）を対象とすることが最も多いが、以下に説明する尺度や、またこれらを複数組み合わせた尺度も研究されていることが多い。次にFSPで用いられる代表的な評価尺度を挙げる。
 （総所要時間）: 
 （Total Tardiness）:
 （number of tardy jobs）: 

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

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

 関連問題 
ジョブショップ・スケジューリング問題：仕事の作業順序の制約が与えられる問題である。
：仕事の作業順序の制約が考慮されない問題である。

 脚注 

 参考文献 

 関連項目 
 分枝限定法


Category:オペレーションズリサーチ
Category:組合せ最適化
Category:数学に関する記事