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

フローショップスケジューリングは、コンピュータサイエンスとオペレーションズリサーチにおける最適化問題です。これは、最適ジョブスケジューリングのバリエーションです。一般的なジョブスケジューリング問題では、処理時間の異なるn個のジョブJ ₁、 J ₂、...、 J _nが与えられます。これらのジョブは、処理能力の異なるm台のマシンでスケジュールする必要があり、メイクスパン(スケジュール全体の長さ、つまり、すべてのジョブの処理が完了したときの長さ) を最小化するようにします。フローショップスケジューリングと呼ばれる特定のバリエーションでは、各ジョブにm個の操作が含まれます。ジョブのi番目の操作は、 i番目のマシンで実行する必要があります。どのマシンも、同時に複数の操作を実行することはできません。各ジョブの各操作に対して、実行時間が指定されます。

フローショップ・スケジューリングは、ジョブショップ・スケジューリングの特殊なケースであり、すべてのジョブにおいて実行されるすべての操作に厳密な順序が定められています。フローショップ・スケジューリングは、コンピュータ設計だけでなく、生産設備にも適用できます。フローショップ・スケジューリング問題の特殊なタイプとして、順列フローショップ・スケジューリング問題があります。これは、リソース上のジョブの処理順序が、後続の各処理ステップで同じである問題です。

最適ジョブスケジューリング問題における標準的な3フィールド表記法では、フローショップ型は最初のフィールドにFで示されます。例えば、「 F3| | $p_{ij}$ 」で示される問題は、単位処理時間を持つ3台の機械によるフローショップ問題であり、最大完了時間を最小化することが目標となります。 $C_{\max}$

正式な定義

m 台のマシンとn台のジョブがあります。各ジョブには正確にm 個の操作が含まれます。ジョブのi番目の操作はi番目のマシンで実行する必要があります。どのマシンも複数の操作を同時に実行することはできません。各ジョブの各操作には、実行時間が指定されています。

1つのジョブ内の操作は、指定された順序で実行されなければなりません。最初の操作は1台目のマシンで実行され、（最初の操作が完了すると）2台目のマシンで2番目の操作が実行され、m番目の操作まで同様に実行されます。ただし、ジョブは任意の順序で実行できます。問題は、最適な順序、つまりジョブ実行メイクスパンが可能な限り短くなる順序を決定することです。

シーケンス性能測定（γ）

シーケンス問題は、1 つまたは複数のシーケンス目標が最適化されるようにシーケンス S を決定することとして説明できます。

（平均）流動時間、 $\sum (w_{i})F_{i}$
メイクスパン、C _max
（平均）遅刻、 $\sum (w_{i})T_{i}$
....

パフォーマンス測定に関する詳細な議論はMalakooti（2013）に記載されている。^{[ 1 ]}

フローショップスケジューリングの複雑さ

Gareyら(1976)が発表したように、^{[ 2 ]}フローショップスケジューリング問題の拡張のほとんどはNP困難であり、そのうちO(nlogn)で最適に解けるものはほとんどありません。例えば、F2|prmu|C _maxはジョンソンの法則を使って最適に解くことができます。^{[ 3 ]}

テイラードはフローショップ、オープンショップ、ジョブショップのスケジューリングに関する実質的なベンチマーク問題を提供している。^{[ 4 ]}

解決方法

フローショップスケジューリング問題を解決するために提案されている方法は、分岐限定法などの正確なアルゴリズムと遺伝的アルゴリズムなどのヒューリスティックアルゴリズムに分類できます。

メイクスパン、C _{maxの最小化}

F2|prmu|C _maxとF3|prmu|C _maxはジョンソン則^{[ 3 ]}を用いて最適に解くことができるが、一般的なケースでは解の最適性を保証するアルゴリズムは存在しない。

フローショップには、時刻0において同時に利用可能なn個のジョブがあり、それらは2台の機械で処理されます。これらの機械は、機械間に無制限の保管スペースを有しています。すべてのジョブの処理時間は確実に分かっています。メイクスパンを最小化するように、n個のジョブを各機械にスケジューリングする必要があります。2台の機械フローショップにおけるジョブのスケジューリングに関するジョンソンの規則を以下に示します。

最適なスケジュールでは、min{p _1i ,p _2j } < min{p _1j ,p _2i }の場合、ジョブ i はジョブ j に先行します。ここで、p _1iはマシン1におけるジョブ i の処理時間、p _2iはマシン2におけるジョブ i の処理時間です。同様に、p _1jとp _2jはそれぞれマシン1とマシン2におけるジョブ j の処理時間です。

ジョンソンのアルゴリズムの場合:

p _{1j を}マシン1のジョブjの処理時間とする

p _2jはマシン2でのジョブjの処理時間である。

ジョンソンのアルゴリズム:

_{p 1j} < p _2jとなるすべてのジョブを含むフォーム set1
_{p 1j} > p _2jのすべてのジョブを含むフォーム set2 では、 p _1j = p _2jのジョブはどちらのセットにも配置できます。
シーケンスを次のように形成します。
_{(i) セット1のジョブがシーケンスの先頭になり、p 1j}の昇順で実行されます（SPT）
_{(ii) set2のジョブはp 2j} (LPT)の降順で並びます。同点の場合は任意に決定されます。

このタイプのスケジュールはSPT(1)-LPT(2)スケジュールと呼ばれます。

利用可能な解決方法の詳細な議論はMalakooti（2013）によって提供されています。^{[ 1 ]}

参照

参考文献

^ ^a ^bマラクーティ、B (2013). 『多目的オペレーションと生産システム』ジョン・ワイリー・アンド・サンズ. ISBN 978-1-118-58537-5。
^ Garey, MR; Johnson, DS; Sethi, Ravi (1976). 「フローショップとジョブショップスケジューリングの複雑性」.オペレーションズ・リサーチ数学. 1 (2): 117– 129. doi : 10.1287/moor.1.2.117 .
^ ^a ^b Johnson, SM (1954). 「セットアップ時間を考慮した最適な2段階および3段階生産スケジュール」海軍研究ロジスティクス季刊誌. 1 (1): 61– 68. doi : 10.1002/nav.3800010110 .
^ Taillard, E. (1993年1月). 「基本的なスケジューリング問題のためのベンチマーク」 .ヨーロッパオペレーションズリサーチジャーナル. 64 (2): 278– 285. doi : 10.1016/0377-2217(93)90182-M .

[Malakooti-1] マラクーティ、B (2013). 『多目的オペレーションと生産システム』ジョン・ワイリー・アンド・サンズ. ISBN 978-1-118-58537-5。

[Garey-2] Garey, MR; Johnson, DS; Sethi, Ravi (1976). 「フローショップとジョブショップスケジューリングの複雑性」.オペレーションズ・リサーチ数学. 1 (2): 117– 129. doi : 10.1287/moor.1.2.117 .

[Johnson-3] Johnson, SM (1954). 「セットアップ時間を考慮した最適な2段階および3段階生産スケジュール」海軍研究ロジスティクス季刊誌. 1 (1): 61– 68. doi : 10.1002/nav.3800010110 .

[Taillard-4] Taillard, E. (1993年1月). 「基本的なスケジューリング問題のためのベンチマーク」 .ヨーロッパオペレーションズリサーチジャーナル. 64 (2): 278– 285. doi : 10.1016/0377-2217(93)90182-M .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]