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

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

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

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

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

1 つのジョブ内の操作は、指定された順序で実行する必要があります。最初の操作は最初のマシンで実行され、(最初の操作が完了すると) 2 番目の操作は 2 番目のマシンで実行され、m番目の操作まで続きます。ただし、ジョブは任意の順序で実行できます。問題の定義では、このジョブの順序は各マシンでまったく同じであることを意味します。問題は、最適な配置、つまりジョブ実行のメイクスパンが可能な限り短い配置を決定することです。

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

1. （平均）フロー時間、${\displaystyle \sum (w_{i})F_{i}}$
2. メイクスパン、C_最大
3. （平均）遅刻、${\displaystyle \sum (w_{i})T_{i}}$
4. ....

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

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

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

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

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

フローショップには、時間ゼロで同時に利用可能な 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の処理時間である。

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

1. _{p 1j} < p _2jであるすべてのジョブを含むフォーム set1
2. _{p 1j} > p _2jのすべてのジョブを含む set2 を形成し、p _1j = p _2jのジョブはどちらのセットにも配置できます。
3. シーケンスは次のように作成します。

   _{(i) セット1のジョブが最初に実行され、p 1j}の昇順で実行されます（SPT）

   _{(ii) set2のジョブはp 2j} (LPT)の降順で並びます。同点の場合は任意に決定されます。

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

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

• オープンショップのスケジュール
• ジョブショップスケジューリング