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

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

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

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

問題のバリエーション

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

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

NP困難性

巡回セールスマン問題はNP困難であるため、シーケンス依存セットアップのジョブショップ問題もNP困難である。これは、TSPが単一のジョブ（TSPのセールスマン）と機械（TSPの都市）を持つJSPの特殊なケースであるためである。[ 5 ]

問題の表現

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

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

とを二つの有限集合とする。この問題が工業化の分野に端を発していることから、を機械、を仕事と呼ぶ。 M＝{M1、M2、…、Mメートル}{\displaystyle M=\{M_{1},M_{2},\dots ,M_{m}\}}J＝{J1、J2、…、Jn}{\displaystyle J=\{J_{1},J_{2},\dots ,J_{n}\}}M私{\displaystyle \displaystyle M_{i}}Jj{\displaystyle \displaystyle J_{j}}

機械へのジョブの割り当て順序の集合を とすると、すべてのジョブがすべての機械によって正確に1回ずつ実行される。要素は行列として表すことができ、各列には機械が実行するジョブが順番に並べられる。例えば、次の行列は  X{\displaystyle \displaystyle \ {\mathcal {X}}}×∈X{\displaystyle x\in {\mathcal {X}}}n×メートル{\displaystyle n\times m}私{\displaystyle \displaystyle i}M私{\displaystyle \displaystyle M_{i}}

×＝（122331）{\displaystyle x={\begin{pmatrix}1&2\\2&3\\3&1\end{pmatrix}}}

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

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

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

スケジュールの効率化

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

C′＝1+∑私l私∑j、けpjけ＝C。メートル∑j、けpjけ{\displaystyle C'=1+{\sum _{i}l_{i} \over \sum _{j,k}p_{jk}}={C.m \over \sum _{j,k}p_{jk}}}

ここで、 は機械iのアイドル時間、Cはメイクスパン、mは機械台数です。この定式化では、メイクスパンを機械台数と総処理時間で正規化し、様々なサイズのジョブショップスケジューリング（JSP）インスタンス間でのリソース利用率の比較を可能にしています。[ 8 ]li{\displaystyle l_{i}}

無限コストの問題

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

主な成果

グラハムは1966年にリストスケジューリングアルゴリズムを導入した。これは(2 − 1/m)-競合性を持つ（ここでmはマシン数）。[ 1 ]後に、マシン2台および3台の場合に最適なオンラインアルゴリズムであることが証明された。均一長ジョブに対するコフマン・グラハムアルゴリズム（1972年）もマシン2台の場合に最適であり、(2 − 2/m)-競合性を持つ。[ 9 ] [ 10 ]

1992年にBartal、Fiat、Karloff、Vohraは1.986の競合アルゴリズムを発表し[ 11 ]、続いて1994年にKarger、Philips、Torngが1.945の競合アルゴリズムを発表しました[ 12 ]。同年、Albersは1.923の競合アルゴリズムを発表しました[ 13 ] 。最もよく知られている結果はFleischerとWahlによるもので、1.9201の競合比を達成しました[ 14 ] 。

アルバースはまた、1.852という下限を確立した。[ 15 ]テイラードインスタンスは、メイクスパン目標を持つジョブショップスケジューリングの開発において重要な役割を果たしている。

1976年にGareyはこの問題がm > 2の場合にはNP完全であることを証明した。つまりP=NPでない限り多項式時間で最適解を計算できないことを意味する。[ 16 ]

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

オフラインでのメイクスパンの最小化

原子力関連の仕事

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

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

複数の操作で構成されるジョブ

M台の機械で複数の（M）工程からなるジョブをスケジューリングする問題の基本形は、フローショップ・スケジューリング問題として知られています。この場合、最初の工程はすべて最初の機械で実行され、2番目の工程はすべて2番目の機械で実行され、といった具合で、単一のジョブは並列に実行できません。遺伝的アルゴリズムを含む様々なアルゴリズムが存在します。[ 20 ]

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

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

ジョブ 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インスタンスの最適なメイクスパンを予測するために使用されています。 [ 8 ]予備的な結果では、教師あり学習を使用した最適なスケジューリング効率によって、ランダムに生成された小さなJSPインスタンスを分類する際に約80％の精度が得られています。

例

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

パラメーターN_JOBS ;パラメーターN_MACHINES ;JOBSを1 .. N_JOBSに設定し、MACHINESを1 .. N_MACHINESに設定し、パラメータProcessingTime { JOBS , MACHINES } > 0 ;param CumulativeTime { JOBS内のi 、 MACHINES内のj } = sum { MACHINES内のjj : ord ( jj ) <= ord ( j )} ProcessingTime [ i 、 jj ];パラメーターTimeOffset { JOBS内のi1 、 JOBS内のi2 : i1 <> i2 } = max { MACHINES内のj } ( 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の対象{ JOBS内のi1 、 JOBS内のi2 : ord ( i1 ) < ord ( i2 )}: precedes [ i1 、 i2 ] ==> start [ i2 ] >= start [ i1 ] + TimeOffset [ i1 、 i2 ];no21_conflictの対象{ i1 in JOBS 、 i2 in JOBS : ord ( i1 ) < ord ( i2 )}: ! precedes [ 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 ;

参照

参考文献

  1. ^ a b Graham, R. (1966). 「特定のマルチプロセッシング異常の境界」(PDF) . Bell System Technical Journal . 45 (9): 1563– 1581. doi : 10.1002/j.1538-7305.1966.tb01709.x .
  2. ^ 「Taillard Instances」 . mistic.heig-vd.ch . 2025年3月17日閲覧。
  3. ^ Maccarthy (1993). 「スケジューリング研究のギャップへの取り組み：生産スケジューリングにおける最適化とヒューリスティック手法のレビュー」
  4. ^ Malakooti,​​ B (2013). 『多目的オペレーションと生産システム』 John Wiley & Sons. ISBN 978-1-118-58537-5。
  5. ^ Sharma, P. (2016年3月). 「セットアップ時間を考慮したジョブショップスケジューリングのレビュー」Proceedings of the Institution of Mechanical Engineers, Part B: Journal of Engineering Manufacture . 230 (3): 517– 533. doi : 10.1177/0954405414560617 . ISSN 0954-4054 . 
  6. ^ B. ロイ、B. サスマン、Les problèmes d'ordonnancement avecconstraines disjonctives、SEMA、Note DS、No. 9、パリ、1​​964 年。
  7. ^ Błażewicz, Jacek (2000年12月). 「ジョブショップスケジューリング問題の分離グラフマシン表現」. European Journal of Operational Research . 127 (2): 317– 331. doi : 10.1016/S0377-2217(99)00486-5 . ISSN 0377-2217 . 
  8. ^ a b Mirshekarian, Sadegh; Šormaz, Dušan N. (2016年6月9日). 「ジョブショップ・スケジューリング問題の特徴とスケジューリング効率の相関関係」(PDF) . Expert Systems with Applications . 62 : 131–147 . doi : 10.1016 /j.eswa.2016.06.014 . 2018年4月17日時点のオリジナルよりアーカイブ。
  9. ^ Coffman, EG Jr. ; Graham, RL (1972)、「2プロセッサシステムの最適スケジューリング」（PDF）、Acta Informatica、1（3）：200– 213、doi：10.1007/bf00288685、MR 0334913、S2CID 40603807  。
  10. ^ Lam, Shui; Sethi, Ravi (1977)、「2つのスケジューリングアルゴリズムの最悪ケース分析」、SIAM Journal on Computing、6 (3): 518– 536、doi : 10.1137/0206037、MR 0496614 。
  11. ^ Bartal, Y.; A. Fiat; H. Karloff; R. Vohra (1992). 「古代のスケジューリング問題に対する新しいアルゴリズム」. Proc. 24th ACM Symp . Theory of Computing. pp.  51– 58. doi : 10.1145/129712.129718 .
  12. ^ Karger, D. ; S. Phillips; E. Torng (1994). 「古代のスケジューリング問題に対するより良いアルゴリズム」 . Proc. Fifth ACM Symp . 離散アルゴリズム.
  13. ^ Albers, Susanne ; Torben Hagerup (1992). 「同時書き込みなしの並列整数ソートの改良」 .第3回ACM-SIAM離散アルゴリズムシンポジウム議事録. 離散アルゴリズムシンポジウムアーカイブ. pp.  463– 472.
  14. ^フライシャー、ルドルフ (2000).アルゴリズム – ESA 2000 . ベルリン/ハイデルベルク: シュプリンガー. pp.  202– 210. doi : 10.1007/3-540-45253-2_19 . ISBN 978-3-540-41004-1。
  15. ^ Albers, Susanne (1999). 「オンラインスケジューリングのより良い境界」. SIAM Journal on Computing . 29 (2): 459– 473. CiteSeerX 10.1.1.685.8756 . doi : 10.1137/S0097539797324874 . 
  16. ^ Garey, MR; Johnson, DS; Sethi, Ravi (1976). 「フローショップとジョブショップスケジューリングの複雑性」.オペレーションズ・リサーチ数学. 1 (2): 117– 129. doi : 10.1287/moor.1.2.117 . JSTOR 3689278 . 
  17. ^チェン、シン;ラン、ヤン。ベンク、アッティラ;ドーサ、ジェルジ。ハン、シン (2011)。「最後に制限付き再配置を行うオンライン スケジューリングのための最適なアルゴリズム」。理論的なコンピューターサイエンス。412 (45): 6269–6278。土井: 10.1016/j.tcs.2011.07.014。
  18. ^ Liu, M.; Xu, Y.; Chu, C.; Zheng, F. (2009). 「2台の均一機械におけるメイクスパン最小化のためのオンラインスケジューリング」 . Theoret. Comput. Sci . 410 ( 21– 23): 2099– 2109. doi : 10.1016/j.tcs.2009.01.007 .
  19. ^ Hochbaum, Dorit ; Shmoys, David (1987). 「スケジューリング問題における双対近似アルゴリズムの使用：理論的および実践的結果」(PDF) . Journal of the ACM . 34 (1): 144– 162. CiteSeerX 10.1.1.125.5753 . doi : 10.1145/7531.7535 . S2CID 9739129 .  
  20. ^ Khuri, Sami; Miryala, Sowmya Rao (1999). 「オープンショップスケジューリング問題を解くための遺伝的アルゴリズム」.第9回ポルトガル人工知能会議議事録：人工知能の進歩. ロンドン: Springer Verlag . CiteSeerX 10.1.1.29.4699 . 
  21. ^ SM Johnson、「セットアップ時間を考慮した最適な2段階および3段階生産スケジュール」Naval Res. Log. Quart. I(1954)61-68。
「 https://en.wikipedia.org/w/index.php?title=Job-shop_scheduling&oldid=1327740297」より取得