オープンショップのスケジュール
オープンショップスケジューリングまたはオープンショップスケジューリング問題（OSSP）は、コンピュータサイエンスとオペレーションズリサーチにおける最適化問題です。これは最適ジョブスケジューリングの一種です。一般的なジョブスケジューリング問題では、処理時間の異なるn個のジョブJ 1、 J 2、…、 J nが与えられ、これらを処理能力の異なるm台のマシンにスケジュールし、メイクスパン（すべてのジョブの処理が完了したとき）を最小化するようにします。オープンショップスケジューリングと呼ばれる特殊な変種では、各ジョブは任意の順序で処理する必要がある一連の操作O 1、 O 2、…、 O nで構成されます。この問題は、 1976年にTeofilo F. GonzalezとSartaj Sahniによって初めて研究されました。[ 1 ]
最適ジョブスケジューリング問題における標準的な3フィールド表記法において、オープンショップ型は最初のフィールドにOで示されます。例えば、「O3| |」で示される問題は、単位処理時間を持つ3台の機械によるジョブショップ問題であり、目標は最大完了時間を最小化することです。
意味
オープンショップ スケジューリング問題への入力は、 n個のジョブのセット、別のm個のワークステーションのセット、および各ジョブが各ワークステーションで費やす時間 (ゼロの可能性もある) の 2 次元テーブルで構成されます。各ジョブは、一度に 1 つのワークステーションでのみ処理でき、各ワークステーションは、一度に 1 つのジョブのみを処理できます。ただし、ジョブショップ問題とは異なり、処理ステップが発生する順序は自由に変更できます。目標は、各ワークステーションで処理される各ジョブの時間を割り当て、2 つのジョブが同じワークステーションに同時に割り当てられないようにし、すべてのジョブが各ワークステーションに必要な時間割り当てられるようにすることです。ソリューションの品質の通常の基準は、メイクスパン、つまりスケジュールの開始 (ワークステーションへのジョブの最初の割り当て) から終了 (最後のワークステーションでの最後のジョブの終了時間) までの時間です。
計算の複雑さ
オープンショップスケジューリング問題は、ワークステーションが2台、またはジョブが2台しかないインスタンスの場合、多項式時間で解くことができます。また、すべての非ゼロ処理時間が等しい場合にも、多項式時間で解くことができます。この場合、問題は、ジョブとワークステーションを頂点とし、非ゼロ処理時間を持つジョブとワークステーションのペアごとに辺を持つ二部グラフの辺彩色と等しくなります。彩色における辺の色は、ジョブとワークステーションのペアが処理される予定の時間区分に対応します。二部グラフの線グラフは完全グラフであるため、二部グラフの辺彩色は多項式時間で可能です。
3つ以上のワークステーション、または3つ以上のジョブがあり、処理時間が異なる場合、オープンショップスケジューリングはNP困難である。[ 2 ]
関連する問題
- ジョブショップスケジューリングも同様の問題ですが、さらに制約が追加されます。つまり、操作は特定の順序で実行されなければなりません。
- フローショップ スケジューリングはジョブショップ スケジューリングですが、フロー制約が追加されており、各操作は特定のマシンで実行する必要があります。
参考文献
- ^ Gonzalez, Teofilo; Sahni, Sartaj (1976)、「仕上げ時間を最小化するオープンショップスケジューリング」、Journal of the ACM、23 (4): 665– 679、CiteSeerX 10.1.1.394.1507、doi : 10.1145/321978.321985、MR 0429089、S2CID 1642775。
- ^ウィリアムソン、DP ;ルイジアナ州ホール。ホーヘフェーン、JA;カリフォルニア州ハルケンス。レンストラ, JK ;セヴァスタジャノフ、SV; Shmoys、DB (1997)、「ショート ショップ スケジュール」、オペレーションズ リサーチ、45 (2): 288–294、doi : 10.1287/opre.45.2.288、JSTOR 171745、MR 1644998
