オープンショップのスケジュール

オープンショップスケジューリングまたはオープンショップスケジューリング問題( OSSP ) は、コンピュータサイエンスとオペレーションズリサーチにおける最適化問題です。これは、最適ジョブスケジューリングの変形です。一般的なジョブスケジューリング問題では、処理時間の異なるn個のジョブJ ₁、  J ₂、...、  J _nが与えられ、これらのジョブは、処理能力の異なるm台のマシンでスケジュールされる必要があり、メイクスパン(スケジュールの合計長さ、つまりすべてのジョブの処理が終了したとき) を最小化しようとします。オープンショップスケジューリングと呼ばれる特定の変形では、各ジョブは、任意の順序で処理する必要がある一連の操作O ₁、  O ₂、...、  O _nで構成されます。この問題は、1976 年にTeofilo F. GonzalezとSartaj Sahniによって初めて研究されました。^[1]

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

オープンショップ スケジューリング問題への入力は、 n 個のジョブのセット、別のm 個のワークステーションのセット、および各ジョブが各ワークステーションで費やす時間 (ゼロの場合もある) の 2 次元テーブルで構成されます。各ジョブは一度に 1 つのワークステーションでのみ処理でき、各ワークステーションは一度に 1 つのジョブのみを処理できます。ただし、ジョブショップ問題とは異なり、処理ステップが発生する順序は自由に変更できます。目標は、各ワークステーションで処理される各ジョブの時間を割り当て、2 つのジョブが同じワークステーションに同時に割り当てられないようにし、2 つのワークステーションに同時にジョブが割り当てられないようにし、すべてのジョブが各ワークステーションに必要な時間割り当てられるようにすることです。ソリューションの品質の通常の尺度は、スケジュールの開始 (ジョブのワークステーションへの最初の割り当て) から終了 (最後のワークステーションでの最後のジョブの終了時間) までの時間であるメイク スパンです。

オープンショップ スケジューリング問題は、ワークステーションが 2 つだけ、またはジョブが 2 つだけのインスタンスの場合は、多項式時間で解決できます。また、すべての非ゼロ処理時間が等しい場合も、多項式時間で解決できます。この場合、問題は、ジョブとワークステーションを頂点とし、非ゼロ処理時間を持つジョブとワークステーションのペアごとにエッジを持つ2 部グラフのエッジ色付けと同等になります。色付けにおけるエッジの色は、ジョブとワークステーションのペアが処理されるようにスケジュールされている時間セグメントに対応します。2部グラフの線グラフは完全グラフであるため、2 部グラフは多項式時間でエッジ色付けできます。

3つ以上のワークステーション、または3つ以上のジョブがあり、処理時間が異なる場合、オープンショップスケジューリングはNP困難である。^[2]

• ジョブショップスケジューリングも同様の問題ですが、さらに制約が追加されます。つまり、操作は特定の順序で実行されなければならないということです。
• フローショップ スケジューリングはジョブショップ スケジューリングですが、フロー制約が追加されており、各操作は特定のマシンで実行する必要があります。