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

ジョブショップ スケジューリング、ジョブショップ問題( JSP ) またはジョブショップ スケジューリング問題( JSSP ) は、コンピュータ サイエンスとオペレーションズ リサーチにおける最適化問題です。これは最適ジョブ スケジューリングの変形です。一般的なジョブ スケジューリング問題では、処理時間の異なるn個のジョブJ ₁、  J ₂、...、  J _nが与えられ、これらのジョブは処理能力の異なるm台のマシンでスケジュールされる必要があり、メイクスパン(スケジュールの合計長さ、つまりすべてのジョブの処理が完了したときの長さ)を最小化しようとします。ジョブショップ スケジューリングと呼ばれる特定の変形では、各ジョブは特定の順序 (優先順位制約と呼ばれる)で処理する必要がある操作のセットO ₁、  O ₂、...、  O _nで構成されます。各操作には、それを処理する必要がある特定のマシンがあり、ジョブ内の1 つの操作だけが特定の時間に処理できます。 一般的な緩和策はフレキシブルジョブ ショップです。

この名前はもともとジョブショップにおけるジョブのスケジューリングに由来していますが、このテーマはそのような例以外にも幅広く応用されています。この問題は最もよく知られている組み合わせ最適化問題の1つであり、 1966年にグラハムによって競合分析が初めて提示された問題です。^[1]メイクスパン目標を持つ基本モデルの最良の問題例は、タイラールによるものです。^[2]

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

この問題には、次のようなさまざまなバリエーションが存在します。

• 機械は重複して持つことも（重複した機械を持つフレキシブルジョブショップ）、同一の機械のグループに属することもできます（フレキシブルジョブショップ）。^[3]
• マシンはジョブ間に一定の間隔を必要としたり、アイドル時間がない場合があります。
• マシンにはシーケンスに依存するセットアップが可能です。
• 目的関数は、メイクスパン、 L _pノルム、遅刻、最大遅延などを最小化することです。また、多目的最適化問題になることもあります。
• ジョブには制約がある場合があります。たとえば、ジョブi はジョブj を開始する前に終了する必要があります(ワークフローを参照)。また、目的関数は複数の基準にすることができます。^[4]
• ジョブのセットは、異なるマシンのセットに関連付けることができます。
• 決定論的（固定）処理時間または確率的処理時間。

巡回セールスマン問題はNP 困難であるため、シーケンス依存セットアップを伴うジョブショップ問題も NP 困難であることは明らかです。これは、TSP が単一のジョブを持つ JSP の特殊なケースであるためです (都市がマシンで、セールスマンがジョブです)。^{[引用が必要]}

分離グラフ[ ^5]は、ジョブショップスケジューリング問題のインスタンスを記述するために使用される一般的なモデルの1つです。^[6]

この問題の数学的表現は次のように表すことができます。

と を2 つの有限集合とします。この問題は産業上の問題であるため、 はマシンと呼ばれ、 はジョブと呼ばれます。 ${\displaystyle M=\{M_{1},M_{2},\dots ,M_{m}\}}$${\displaystyle J=\{J_{1},J_{2},\dots ,J_{n}\}}$ ${\displaystyle \displaystyle M_{i}}$${\displaystyle \displaystyle J_{j}}$

は、すべてのジョブがすべてのマシンによって正確に1回実行されるような、マシンへのジョブの連続割り当ての集合を表します。要素は行列として表すことができ、その列にはマシンが実行するジョブが順番にリストされます。たとえば、行列 ${\displaystyle \displaystyle \ {\mathcal {X}}}$${\displaystyle x\in {\mathcal {X}}}$${\displaystyle n\times m}$${\displaystyle \displaystyle i}$${\displaystyle \displaystyle M_{i}}$

${\displaystyle x={\begin{pmatrix}1&2\\2&3\\3&1\end{pmatrix}}}$

は、機械が 3 つのジョブをの順序で実行し、機械がの順序でジョブを実行することを意味します。 ${\displaystyle \displaystyle M_{1}}$${\displaystyle \displaystyle J_{1},J_{2},J_{3}}$${\displaystyle \displaystyle J_{1},J_{2},J_{3}}$${\displaystyle \displaystyle M_{2}}$${\displaystyle \displaystyle J_{2},J_{3},J_{1}}$

また、何らかのコスト関数 があると仮定します。コスト関数は「合計処理時間」として解釈され、機械がジョブを実行するためのコスト/時間である時間で表現される場合があります。 ${\displaystyle C:{\mathcal {X}}\to [0,+\infty ]}$${\displaystyle C_{ij}:M\times J\to [0,+\infty ]}$${\displaystyle \displaystyle M_{i}}$${\displaystyle \displaystyle J_{j}}$

ジョブショップ問題とは、 が最小となるようなジョブの割り当てを見つけることです。 つまり、となるようなジョブは存在しません。${\displaystyle x\in {\mathcal {X}}}$${\displaystyle \displaystyle C(x)}$${\displaystyle y\in {\mathcal {X}}}$${\displaystyle \displaystyle C(x)>C(y)}$

スケジュールの効率は、以下のように、マシンの合計アイドル時間と合計処理時間の比率によって定義できます。

${\displaystyle C'=1+{\sum _{i}l_{i} \over \sum _{j,k}p_{jk}}={Cm \over \sum _{j,k}p_{jk}}}$

ここで、 はマシンiのアイドル時間、Cはメイクスパン、m はマシンの数です。上記の定義では、スケジューリング効率は、単にマシンの数と合計処理時間で正規化されたメイクスパンであることに注意してください。これにより、異なるサイズの JSP インスタンス間でリソースの使用状況を比較することができます。^[7]${\displaystyle l_{i}}$

JSP で最初に対処しなければならない問題の 1 つは、提案されたソリューションの多くが無限のコストを持つことです。つまり、となるような が存在します。実際、 2 台のマシンがデッドロックし、それぞれがもう一方のマシンの次のステップの出力を待つようにすることで、このような例を作り上げるのは非常に簡単です。 ${\displaystyle x_{\infty }\in {\mathcal {X}}}$${\displaystyle C(x_{\infty })=+\infty }$${\displaystyle x_{\infty}}$

グラハムは1966年に既にリストスケジューリングアルゴリズムを提供していました。これは(2 − 1/ m ) -競合的であり、ここでmはマシンの数です。^[1] また、リストスケジューリングは2台および3台のマシンに最適なオンラインアルゴリズムであることが証明されました。均一長ジョブのコフマン–グラハムアルゴリズム(1972)も2台のマシンに最適であり、(2 − 2/ m ) -競合的です。^{[8] [9]} 1992年に、Bartal、Fiat、Karloff、およびVohraは、1.986-競合的なアルゴリズムを発表しました。^[10] 1994年に、Karger、Philips、およびTorngによって1.945-競合的なアルゴリズムが発表されました。 ^[11] 1992年に、Albersは1.923-競合的な別のアルゴリズムを提供しました。^[12]現在、最もよく知られている結果は、フライシャーとワールが提示したアルゴリズムであり、競争比率1.9201を達成している。^[13]

下限値は1.852で、アルバースによって提示された。^[14] テイラードインスタンスは、メイクスパン目標を持つジョブショップスケジューリングの開発において重要な役割を果たしている。

1976年にGareyはこの問題がm>2の場合NP完全であることを証明した^[15] 。つまり、3台以上のマシンでは決定論的多項式時間で最適解を計算することはできない（P=NPでない限り）。

2011年にXin Chenらは2台の関連マシン上でのオンラインスケジューリングに最適なアルゴリズムを提供し、以前の結果を改善した^[16]。^[17]

オフラインのメイクスパン最小化問題の最も単純な形式は、アトミック ジョブ、つまり複数の操作に分割されていないジョブを扱います。これは、さまざまなサイズのアイテムを固定数のビンに詰め込み、必要な最大ビン サイズが可能な限り小さくなるようにすることと同じです。(代わりにビンの数を最小化し、ビン サイズを固定する場合、問題はビン パッキング問題と呼ばれる別の問題になります。)

ドリット・S・ホッホバウムとデイビッド・シュモイズは1987年に、オフラインのメイクスパン最小化問題に対する近似解を任意の精度で求める多項式時間近似スキームを提示した。 ^[18]

M台のマシン上で複数の（M）操作を伴うジョブをスケジュールする問題の基本形式は、最初の操作はすべて最初のマシンで実行され、2番目の操作はすべて2番目のマシンで実行されるなどであり、単一のジョブを並列に実行することはできません。これはフローショップスケジューリング問題として知られています。遺伝的アルゴリズムを含むさまざまなアルゴリズムが存在します。^[19]

SMジョンソンによるヒューリスティックアルゴリズムは、すべてのジョブを同じ順序で処理する必要がある場合の2台のマシンのNジョブ問題を解決するために使用できます。^[20] アルゴリズムの手順は次のとおりです。

ジョブ P _{i には、期間 P i1}、 P _i2の 2 つの操作があり、マシン M1、M2 でその順序で実行されます。

• ステップ 1.リスト A = { 1, 2, …, N }、リスト L1 = {}、リスト L2 = {}。
• ステップ 2.利用可能なすべての操作期間から、最小値を選択します。

最小値がP _k1に属する場合、

リスト A から K を削除します。リスト L1 の末尾に K を追加します。

最小値がP _k2に属する場合、

リスト A から K を削除します。リスト L2 の先頭に K を追加します。

• ステップ 3.リスト A が空になるまでステップ 2 を繰り返します。
• ステップ 4.リスト L1 とリスト L2 を結合します。これが最適なシーケンスです。

ジョンソンの方法は、2 台のマシンに対してのみ最適に機能します。ただし、最適であり、計算も簡単なため、一部の研究者は M 台のマシン ( M  > 2) にこの方法を採用しようとしました。

考え方は次のとおりです。各ジョブには、M1、M2、… Mm で順番に m 個の操作が必要であるとします。最初のm /2 台のマシンを (架空の) マシニング センター MC1 に結合し、残りのマシンをマシニング センター MC2 に結合します。すると、MC1 でのジョブ P の合計処理時間 = 合計 (最初のm /2 台のマシンでの操作時間)、MC2 でのジョブ P の処理時間 = 合計 (最後のm /2 台のマシンでの操作時間) になります。

そうすることで、m-Machine の問題を 2 つのマシニング センターのスケジューリングの問題に縮小できます。これは、ジョンソン法を使用して解決できます。

機械学習は最近、最適なスケジュールを実際に作成することなく、JSPインスタンスの最適なメイクスパンを予測するために使用されています。 ^[7]予備的な結果では、ランダムに生成された小さなJSPインスタンスを平均と比較した最適なスケジュール効率に基づいて分類するために教師あり機械学習手法を適用した場合、約80％の精度が示されています。

以下は、 AMPLで指標制約付きの混合整数計画問題として定式化されたジョブショップ スケジューリング問題の例です。

パラメータN_JOBS ;パラメータN_MACHINES ; 
 

JOBSを1 .. N_JOBSに設定し、MACHINES を1 .. N_MACHINESに設定し、    
    

パラメータProcessingTime { JOBS , MACHINES } > 0 ;    

param CumulativeTime { i in JOBS 、 j in MACHINES } = sum { jj in MACHINES : ord ( jj ) <= ord ( j )} ProcessingTime [ i 、 jj ];       
          

パラメータTimeOffset { i1 in JOBS 、 i2 in JOBS : i1 <> i2 } = max { j in MACHINES } ( CumulativeTime [ i1 、 j ] - CumulativeTime [ i2 、 j ] + ProcessingTime [ i2 、 j ]);          
      
         

var終了>= 0 ; var start { JOBS } >= 0 ; var は{ JOBSのi1 , JOBSのi2 : ord ( i1 ) < ord ( i2 )}バイナリに先行します。   
   
          

メイクスパンを最小化する:終了;  

makespan_def { i in JOBS }の subj : end >= start [ i ] + sum { j in MACHINES } ProcessingTime [ i , j ];   
          

no12_conflictの対象{ i1 in JOBS 、 i2 in JOBS : ord ( i1 ) < ord ( i2 )}:先行[ i1 、 i2 ] ==>開始[ i2 ] >=開始[ i1 ] + TimeOffset [ i1 、 i2 ];         
         

no21_conflictの対象{ i1 in JOBS 、 i2 in JOBS : ord ( i1 ) < ord ( i2 )}: !先行[ i1 、 i2 ] ==> start [ i1 ] >= start [ i2 ] + TimeOffset [ i2 、 i1 ];         
         

データ;

パラメータN_JOBS : = 4 ;パラメータN_MACHINES : = 4 ;   
   

パラメータProcessingTime : 1 2 3 4 : = 1 5 4 2 1 2 8 3 6 2 3 9 7 2 3 4 3 1 5 8 ; 
       
     
     
     
     

• フローショップ スケジューリングも同様の問題ですが、各操作を特定のマシンで実行する必要があるという制約はありません (順序制約のみが保持されます)。
• オープンショップスケジューリングも同様の問題ですが、順序制約はありません。

• ウィーン大学の動的最適化のための方法論、システム、ソフトウェアのディレクトリ。
• タイヤールインスタンス
• Brucker P.スケジューリング アルゴリズム。ハイデルベルク、シュプリンガー。第 5 版ISBN 978-3-540-24804-0