最適なジョブスケジューリング

最適ジョブ スケジューリングは、スケジューリングに関連する最適化問題の一種です。このような問題への入力は、ジョブ(プロセスまたはタスクとも呼ばれる) のリストとマシン(プロセッサまたはワーカーとも呼ばれる)のリストです。必要な出力はスケジュール、つまりマシンへのジョブの割り当てです。スケジュールは、特定の目的関数を最適化する必要があります。文献では、最適ジョブ スケジューリングの問題は、マシン スケジューリング、プロセッサ スケジューリング、マルチプロセッサ スケジューリング、または単にスケジューリングと呼ばれることがよくあります。

最適ジョブスケジューリングの問題には、ジョブの性質、マシンの性質、スケジュールの制約、目的関数が異なるさまざまな問題があります。最適スケジューリング問題の便利な表記法は、 Ronald Graham、Eugene Lawler、Jan Karel Lenstra、Alexander Rinnooy Kanによって導入されました。^{[1] [2]これは、} α、β、γの3つのフィールドで構成されます。各フィールドは、コンマで区切られた単語のリストです。 α フィールドはマシン環境を、 β はジョブの特性と制約を、 γ は目的関数を記述します。^[3] 1970年代後半に導入されて以来、この表記法は常に拡張されており、一貫性がない場合もあります。その結果、今日ではいくつかの論文で異なる表記法で示されている問題がいくつかあります。

より単純な最適ジョブ スケジューリング問題では、各ジョブj は、指定された処理時間p _jを持つ単一の実行フェーズで構成されます。より複雑なバリアントでは、各ジョブは複数の実行フェーズで構成され、順番にまたは並行して実行される場合があります。

単一ステージのジョブ スケジューリング問題では、マシン環境には主に 4 つのカテゴリがあります。

• 1 :単一マシンスケジューリング。マシンは 1 台です。
• P :同一マシン スケジューリング。並列マシンが複数あり、それらは同一です。ジョブは、スケジュールされているどのマシンでも時間がかかります。${\displaystyle m}$${\displaystyle j}$${\displaystyle p_{j}}$
• Q :均一機械スケジューリング。並列機械があり、それぞれ速度が異なります。機械での作業には時間がかかります。${\displaystyle m}$${\displaystyle j}$${\displaystyle i}$${\displaystyle p_{j}/s_{i}}$
• R :無関係なマシンのスケジューリング。並列マシンがあり、それらは無関係です。マシン上のジョブには時間がかかります。${\displaystyle m}$${\displaystyle j}$${\displaystyle i}$${\displaystyle p_{ij}}$

これらの文字の後にマシンの数が続く場合があり、その数は固定されています。たとえば、P2 は2 台の並列同一マシンがあることを示します。Pmはm台の並列同一マシンがあることを示します。ここで、mは固定パラメータです。対照的に、Pはm 台の並列同一マシンがあることを示しますが、m は固定されていません (入力の一部です)。

多段階ジョブスケジューリング問題では、マシン環境に他のオプションがあります。

• O :オープンショップ問題。各ジョブはの操作で構成されます。操作は任意の順序でスケジュールできます。操作はマシン 上のユニットに対して処理される必要があります。${\displaystyle j}$${\displaystyle m}$${\displaystyle O_{ij}}$${\displaystyle i=1,\ldots ,m}$${\displaystyle O_{ij}}$${\displaystyle p_{ij}}$${\displaystyle i}$
• F :フローショップ問題。各ジョブは、指定された順序でスケジュールされるの操作で構成されます。操作は、マシン でユニットに対して処理される必要があります。${\displaystyle j}$${\displaystyle m}$${\displaystyle O_{ij}}$${\displaystyle i=1,\ldots ,m}$${\displaystyle O_{ij}}$${\displaystyle p_{ij}}$${\displaystyle i}$
• J :ジョブショップ問題。各ジョブはの操作で構成され、その順序でスケジュールされます。操作はのユニットに対して の専用マシンで処理されなければなりません。${\displaystyle j}$${\displaystyle n_{j}}$${\displaystyle O_{kj}}$${\displaystyle k=1,\ldots ,n_{j}}$${\displaystyle O_{kj}}$${\displaystyle p_{kj}}$${\displaystyle \mu _{kj}}$${\displaystyle \mu _{kj}\neq \mu _{k'j}}$${\displaystyle k\neq k'}$

すべての処理時間は整数であると想定されています。ただし、古い研究論文の中には、有理数であると想定されているものもあります。

• ${\displaystyle p_{i}=p}$、または：すべてのジョブの処理時間は等しくなります。${\displaystyle p_{ij}=p}$
• ${\displaystyle p_{i}=1}$、または：すべてのジョブの処理時間は 1 時間単位に等しくなります。${\displaystyle p_{ij}=1}$
• ${\displaystyle r_{j}}$: 各ジョブにはリリース時刻が指定されており、それより前にはスケジュールできません。デフォルトは 0 です。
• ${\displaystyle {\text{online-}}r_{j}}$: オンラインの問題。ジョブはリリース時に公開されます。このコンテキストでは、アルゴリズムのパフォーマンスは競争率によって測定されます。
• ${\displaystyle d_{j}}$: 各ジョブには期日が与えられます。すべてのジョブは期日までに完了する必要があり、遅れて完了するジョブには何らかのペナルティがあるという考え方です。このペナルティは目標値に示されます。ジョブ特性の存在は暗黙的に想定されており、たとえば、すべての期日が特定の日付に等しいと想定するなどの制約がない限り、問題名には示されません。${\displaystyle d_{j}}$${\displaystyle d_{j}=d}$
• ${\displaystyle {\bar {d}}_{j}}$: 各ジョブには厳格な期限が与えられます。すべてのジョブは期限までに完了する必要があります。
• pmtn : ジョブは別のマシンで優先的に実行され、再開される可能性があります。 ' prmp ' で示されることもあります。
• ${\displaystyle {\text{size}}_{j}}$: 各ジョブには、同時にスケジュールする必要があるマシンの数があります。デフォルトは 1 です。これは、並列タスク スケジューリングと呼ばれるバリアントの重要なパラメーターです。

2 つのジョブの各ペアには、優先順位がある場合とない場合があります。2 つのジョブ間の優先順位とは、一方のジョブがもう一方のジョブより先に終了する必要があることを意味します。たとえば、ジョブ i がジョブ j の順序で先行する場合、ジョブ j はジョブ i が完了した後にのみ開始できます。

• prec : 優先順位には制限はありません。
• チェーン: 各ジョブは最大で 1 つの他のジョブの前身であり、最大で 1 つの他のジョブが先行します。
• ツリー:優先順位関係は、2 つの制限のいずれかを満たす必要があります。
  • intree:各ノードは最大 1 つの他のジョブの前身です。
  • outtree:各ノードの前には最大 1 つの他のジョブが存在します。
• 反対のフォレスト:優先順位関係のグラフが接続されたコンポーネントに分割される場合、各接続されたコンポーネントはインツリーまたはアウトツリーのいずれかになります。
• spグラフ:先行関係のグラフは直列並列グラフです。
• 制限された高さ: 最長の有向パスの長さは固定値に制限されます。(有向パスとは、最後のジョブを除く各ジョブがシーケンス内の次のジョブの前身となるジョブのシーケンスです。)
• レベル順序: 各ジョブにはレベルがあり、レベルはそのジョブから始まる最長の有向パスの長さです。レベル を持つ各ジョブは、レベル を持つすべてのジョブの前身となります。${\displaystyle k}$${\displaystyle k-1}$
• 間隔順序: 各ジョブには間隔[ s _x , e _x )があり、間隔の終了が間隔の開始よりも厳密に小さい場合にのみ、ジョブはの先行ジョブになります。=${\displaystyle x}$${\displaystyle x}$${\displaystyle y}$${\displaystyle x}$${\displaystyle y}$

先行関係がある場合、さらにタイムラグを想定できます。2 つのジョブ間のタイムラグは、最初のジョブが完了してから 2 番目のジョブが開始されるまでに待機する必要がある時間です。正式には、ジョブ i がジョブ j に先行する場合、はtrue である必要があります。タイムラグが指定されていない場合は、ゼロであると見なされます。タイムラグは負の値になることもあります。負のタイムラグは、2 番目のジョブが最初のジョブが終了する固定時間前に開始できることを意味します。 ${\displaystyle C_{i}+\ell _{ij}\leq S_{j}}$${\displaystyle \ell _{ij}}$

• ℓ : 各ジョブのペア間のタイムラグは同じです。
• ${\displaystyle \ell _{ij}}$: ジョブのペアによってタイムラグが異なる場合があります。

• ${\displaystyle t_{jk}}$:機械でのジョブの動作完了から機械でのジョブの動作開始までの間に、少なくとも単位の輸送遅延が発生します。${\displaystyle O_{kj}}$${\displaystyle j}$${\displaystyle k}$${\displaystyle O_{k+1,j}}$${\displaystyle j}$${\displaystyle k+1}$${\displaystyle t_{jk}}$
• ${\displaystyle t_{jkl}}$:機械でのジョブの動作完了から機械でのジョブの動作開始までの間に、少なくとも単位の輸送遅延が発生します。${\displaystyle O_{kj}}$${\displaystyle j}$${\displaystyle k}$${\displaystyle O_{l,j}}$${\displaystyle j}$${\displaystyle l}$${\displaystyle t_{jkl}}$
• ${\displaystyle t_{k}}$: マシンに依存する輸送遅延。マシンでのジョブの操作の完了とマシンでのジョブの操作の開始の間に、少なくとも単位の輸送遅延が発生します。${\displaystyle O_{kj}}$${\displaystyle j}$${\displaystyle k}$${\displaystyle O_{k+1,j}}$${\displaystyle j}$${\displaystyle k+1}$${\displaystyle t_{k}}$
• ${\displaystyle t_{kl}}$: マシンペアに依存する輸送遅延。マシンでのジョブの操作の完了とマシンでのジョブの操作の開始の間に、少なくとも単位の輸送遅延が発生します。${\displaystyle O_{kj}}$${\displaystyle j}$${\displaystyle k}$${\displaystyle O_{l,j}}$${\displaystyle j}$${\displaystyle l}$${\displaystyle t_{kl}}$
• ${\displaystyle t_{j}}$: ジョブに依存する輸送遅延。マシン上のジョブの操作の完了とマシン上のジョブの操作の開始の間に、少なくとも単位の輸送遅延が発生します。${\displaystyle O_{kj}}$${\displaystyle j}$${\displaystyle k}$${\displaystyle O_{l,j}}$${\displaystyle j}$${\displaystyle l}$${\displaystyle t_{j}}$

• rcrc : 再循環またはフレキシブル ジョブ ショップとも呼ばれます。 の約束は解除され、一部のペアでは になる可能性があります。つまり、同じジョブの異なる操作を同じマシンに割り当てることが可能です。${\displaystyle \mu }$${\displaystyle k\neq k'}$${\displaystyle \mu _{kj}=\mu _{k'j}}$
• no-wait : 操作は、操作が完了したときに正確に開始する必要があります。つまり、ジョブの 1 つの操作が完了すると、次の操作がすぐに開始される必要があります。' nwt 'と表記されることもあります。${\displaystyle O_{k+1,i}}$${\displaystyle O_{k,i}}$
• no-idle : 最初の実行の開始から最後の実行の終了までの間、どのマシンもアイドル状態になることはできません。
• ${\displaystyle {\text{size}}_{j}}$: 同一の並列マシン上のマルチプロセッサ タスク。ジョブの実行は並列マシン上で同時に行われます。${\displaystyle j}$${\displaystyle {\text{size}}_{j}}$
• ${\displaystyle {\text{fix}}_{j}}$: マルチプロセッサ タスク。すべてのジョブにはマシンのセットが与えられ、実行にはこれらすべてのマシンが同時に必要になります。「MPT」と表記されることもあります。${\displaystyle j}$${\displaystyle {\text{fix}}_{j}\subseteq \{1,\ldots ,m\}}$
• ${\displaystyle M_{j}}$: 多目的マシン。すべてのジョブは、指定されたセットのうちの 1 つのマシンにスケジュールされる必要があります。M _jと表記されることもあります。${\displaystyle j}$${\displaystyle M_{j}\subseteq \{1,\ldots ,m\}}$

通常、目標は何らかの客観的な値を最小化することです。1 つの違いは、期限前に完了するジョブの数を最大化することを目標とする表記です。これはスループットとも呼ばれます。客観的な値は合計することができ、ジョブごとに指定された優先度の重みで重み付けすることもできます。 ${\displaystyle \sum U_{j}}$${\displaystyle w_{j}}$

• - : 目的値がない場合は、単一のダッシュで示されます。これは、問題が、与えられたすべての制約を満たす実行可能なスケジュールを作成することだけであることを意味します。
• ${\displaystyle C_{j}}$:ジョブの完了時間。は最大完了時間であり、メイクスパンとも呼ばれます。平均完了時間（ j全体の平均）に関心がある場合もあります。これはmft（平均終了時間）と表記されることもあります。^[4]${\displaystyle j}$${\displaystyle C_{\max }}$${\displaystyle C_{j}}$
• ${\displaystyle F_{j}}$:ジョブのフロー時間は、ジョブの完了時間とリリース時間の差です。${\displaystyle F_{j}=C_{j}-r_{j}}$
• ${\displaystyle L_{j}}$:遅延。すべてのジョブには期限が与えられます。ジョブの遅延は と定義されます。 は、期限のある問題の実現可能性を示すために使用されることがあります。実際、バイナリ検索を使用すると、実現可能性バージョンの複雑さは の最小化に相当します。${\displaystyle j}$${\displaystyle d_{j}}$${\displaystyle j}$${\displaystyle C_{j}-d_{j}}$${\displaystyle L_{\max }}$${\displaystyle L_{\max }}$
• ${\displaystyle U_{j}}$:スループット。すべてのジョブには期日が与えられます。時間どおりに完了するジョブ、つまり の場合は単位利益があり、それ以外の場合は単位利益があります。 の意味は文献で反転されることがあります。これは問題の決定バージョンを考えると同等ですが、近似値には大きな違いが生じます。${\displaystyle d_{j}}$${\displaystyle U_{j}=1}$${\displaystyle C_{j}\leq d_{j}}$${\displaystyle U_{j}=0}$${\displaystyle U_{j}}$
• ${\displaystyle T_{j}}$:遅刻。すべての仕事には期限が与えられます。仕事の遅刻は次のように定義されます。${\displaystyle j}$${\displaystyle d_{j}}$${\displaystyle j}$${\displaystyle T_{j}=\max\{0,C_{j}-d_{j}\}}$
• ${\displaystyle E_{j}}$:早さ。すべてのジョブには期日が与えられます。ジョブの早さは と定義されます。この目標はジャストインタイム スケジューリングにとって重要です。${\displaystyle j}$${\displaystyle d_{j}}$${\displaystyle j}$${\displaystyle E_{j}=\max\{0,d_{j}-C_{j}\}}$

複数の目的を持つ変種も存在するが、それらについてはあまり研究されていない。^[2]

上記の表記法を使用して定義された問題の例をいくつか示します。^[1]

• ${\displaystyle P_{2}\parallel C_{\max }}$–与えられたジョブを2台の同一マシンの1台に割り当て、マシン全体の最大合計処理時間を最小化する。これはパーティション問題の最適化バージョンである。${\displaystyle n}$
• 1|prec| – 一般的な優先順位制約を持つプロセスを単一のマシンに割り当て、最大遅延を最小限に抑えます。${\displaystyle L_{\max }}$
• R|pmtn| – 可変数の無関係な並列マシンにタスクを割り当て、プリエンプションを許可して、合計完了時間を最小限に抑えます。${\displaystyle \sum C_{i}}$
• J3| | – 単位処理時間を持つ 3 台の機械によるジョブ ショップ問題。目標は最大完了時間を最小化することです。${\displaystyle p_{ij}=1}$${\displaystyle C_{\max }}$
• ${\displaystyle P\mid {\text{size}}_{j}\mid C_{\max }}$– ジョブを並列の同一マシンに割り当てます。各ジョブには、同時にスケジュールする必要がある複数のマシンが付属し、最大完了時間を最小限に抑えます。並列タスク スケジューリングを参照してください。${\displaystyle m}$

• 上記で調査したすべての変種は、すべてのデータが計画者に知られているという点で決定論的です。また、データが事前にわかっていなかったり、ランダムに変動する可能性がある確率論的な変種もあります。^[2]
• 負荷分散ゲームでは、各ジョブは戦略エージェントに属し、戦略エージェントは自分のジョブをどこにスケジュールするかを決定できます。このゲームにおけるナッシュ均衡は最適ではない可能性があります。AumannとDombb ^[5]は、いくつかの負荷分散ゲームにおける均衡の非効率性を評価しました。

• 部分ジョブスケジューリング

• Scheduling zoo (Christoph Dürr、Sigrid Knust、Damien Prot、Óscar C. Vásquez 著): 表記法を使用して最適なスケジューリング問題を検索するためのオンライン ツール。
• スケジューリング問題の複雑性の結果 (Peter Brucker、Sigrid Knust 著): 実行時の複雑性に関する既知の情報に基づいて最適なスケジューリング問題を分類します。