フローショップ・スケジューリング問題
フローショップ・スケジューリング問題（英: Flowshop Scheduling Problem、略称: FSP）とは、いくつかの作業が複数の機械によって全て同様の工程を経て処理される場合に、評価尺度（機械全体の稼働時間の最小化、作業の納期遅れの最小化など）を最適にするような機械の稼働スケジュール（機械ごとの仕事の処理順序）を決める問題である。組み合わせ最適化の生産スケジューリング問題の一種である。フローショップ・スケジューリング問題はジョブショップ・スケジューリング問題の作業順序の制約がどの仕事も全て同じである特殊な問題ともいえる[1]。各機械で処理する仕事の順序をどの機械も同じ順序という制約を加えたものを、特に順列フローショップ・スケジューリング問題（Permutation Flowshop Scheduling Problem、PFSP）という[2]。
概要
フローショップ・スケジューリング問題（FSP）は、n個の仕事とm個の機械がが全て機械1, …, 機械mの順番で処理する場面で、各機械は常に高々1つの仕事を処理し、また一度仕事を処理し始めたら、処理を中断する ことができない。また各仕事が各機械でかかる処理時間はそれぞれ異なる。このとき、処理の総所要時間や納期遅れ時間などの評価尺度が最適となるように仕事の処理順序を求める問題である。
FSPでは以下の仮定の下で仕事の処理順序を求める[3]。
- 全ての仕事は互いに影響を受けることなく処理を行うことができ、いつでも処理を開始することができる。
- 各機械は連続して利用可能である。
- 各機械は一度に高々 1 つの仕事を処理できる。
- 各仕事は一度にどこか 1 つの工程のみ割り当てることができる。
- 仕事の処理が開始されると、その処理は中断することができない。
- 仕事の順序に依存した段取り時間（各工程間に必要な準備時間）を考慮しない。
仕事数n、機械数mのとき、フローショップ・スケジューリング問題の実行可能スケジュール数（組み合わせ数）は 
この項目は、数学に関連した書きかけの項目です。この項目を加筆・訂正などしてくださる協力者を求めています（プロジェクト:数学／Portal:数学）。
- フローショップ・スケジューリング問題のページへのリンク
