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

フローショップによる生産方式

仕事数4、機械数3のFSPに対するガントチャートの例

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

概要

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

FSPでは以下の仮定の下で仕事の処理順序を求める。

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

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

評価尺度

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

• メイクスパン（総所要時間）: $C_{\max }$
• 総納期遅れ（Total Tardiness）:$\sum {}\max(0,d_{i})$
• 納期遅れ仕事数（number of tardy jobs）: $\sum {}U_{i}$

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

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

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

関連問題

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

参考文献

• Baker, K. R. (1974). Introduction to Sequencing and Scheduling. Yew York: John Wiley&Sons. ISBN 0471045551. LCCN 74-8010 
• 鍋島一郎『スケジューリング理論』森北出版、東京、1974年。ISBN 9784627003705。 
• 久保幹雄『Pythonによる実務で役立つ最適化問題100+ (3)』朝倉書店、東京、2022年。ISBN 978-4-254-12275-6。 
• 今泉淳（著）、東洋大学経営研究所（編）「フローショップスケジューリング問題とその諸変形：モデルとその分類」『経営研究所論集』第23号、2000年、259-274頁、CRID 1520572358002264576、ISSN 09133283、NAID 40004627561。 
• M.R.Garey; D.S.Johoson; R.Sethi (1976). “The Complexity of Flowshop and Jobshop Scheduling”. Mathematics of Operations Research (INFORMS) 1 (2): 117-129. CRID 1361418520298416768. doi:10.1287/moor.1.2.117. ISSN 0364-765X. JSTOR 3689278. 
• MacCarthy, B.; Liu, J. (1993). “Addressing the gap in scheduling research: a review of optimization and heuristic methods in production scheduling”. International Journal of Production Research (Taylor & Francis) 31 (1): 59-79. doi:10.1080/00207549308956713. ISSN 1366-588X. 
• V. Fernández-Viagas Escudero. (2016). The permutation flowshop scheduling problemanalysis, solution procedures and problem extensions (PDF) (Ph.D. thesis) (英語). セビリア大学. hdl:11441/44476. 2024年4月3日閲覧。

関連項目

• 分枝限定法
• NP完全問題の一覧