並列タスクスケジューリング

コンピュータサイエンスにおける最適化問題

並列タスクスケジューリング （並列ジョブスケジューリング^{[1] [2]}または並列処理スケジューリング^[3]とも呼ばれる）は、コンピュータサイエンスとオペレーションズリサーチにおける最適化問題です。これは最適ジョブスケジューリングの変形です。一般的なジョブスケジューリング問題では、処理時間が異なるn個のジョブJ ₁、  J ₂、...、  J _nが与えられ、メイクスパン（スケジュールの合計時間、つまりすべてのジョブの処理が完了したときの長さ）を最小化するように、これらのジョブをm個のマシンでスケジュールする必要があります。並列タスクスケジューリングと呼ばれる特殊な変形では、すべてのマシンは同一です。各ジョブjには、長さパラメータp _jとサイズパラメータq _jがあり、正確にp _jタイムステップで、正確にq _j台のマシンで並列に実行する必要があります。

Veltmanら^[4]とDrozdowski ^[3]は、この問題をGrahamら^{[5 ]が導入した}3フィールド表記法で表しています。Pは複数の同一マシンが並列に動作していることを意味します。size _jは各ジョブにサイズパラメータがあることを意味します。C _maxは最大完了時間を最小化することが目標であることを意味します。一部の著者は 代わりに を使用しています。^[1]並列マシンスケジューリングの問題は、すべてのjに対して、つまり各ジョブが単一のマシンで実行される並列タスクスケジューリングの特殊なケースであることに注意してください。 ${\displaystyle P|size_{j}|C_{\max }}$ ${\displaystyle P|m_{j}|C_{\max }}$ ${\displaystyle size_{j}=1}$

この問題の定式化の起源は1960年に遡ります。^[6]この問題では、より小さい比を持つ多項式時間近似アルゴリズムは存在しません。^{[引用が必要]} ${\displaystyle 3/2}$ ${\displaystyle P=NP}$

意味

ジョブの集合と、同一のマシンが存在します。各ジョブには処理時間（jの長さとも呼ばれます）があり、実行中に複数のマシンを同時に使用する必要があります（ jのサイズまたは幅とも呼ばれます）。 ${\displaystyle {\mathcal {J}}}$ ${\displaystyle n}$ ${\displaystyle m}$ ${\displaystyle j\in {\mathcal {J}}}$ ${\displaystyle p_{j}\in \mathbb {N} }$ ${\displaystyle q_{j}\in \mathbb {N} }$

スケジュールは、各ジョブの開始時刻と、処理対象となるマシン群を割り当てます。スケジュールが実行可能であるとは、各プロセッサが任意の時点で最大1つのジョブしか実行しないことを指します。この問題の目的は、スケジュールの長さ（メイクスパンとも呼ばれます）が最小となるスケジュールを見つけることです。スケジュールが実行可能であるための十分条件は次のとおりです。 ${\displaystyle j\in {\mathcal {J}}}$ ${\displaystyle s_{j}\in \mathbb {N} _{0}}$ ${\displaystyle m_{j}\subseteq \{1,\dots ,m\}}$ ${\displaystyle |m_{j}|=q_{j}}$ ${\displaystyle P|size_{j}|C_{\max }}$ ${\displaystyle C_{\max }=\max _{j\in {\mathcal {J}}}(s_{j}+p_{j})}$

${\displaystyle \sum _{j\in {\mathcal {J}},s_{j}\leq t<s_{j}+p_{j}}q_{j}\leq m\,\forall t\in \{s_{1},\dots ,s_{n}\}}$。

この特性がすべての開始時刻に対して満たされる場合、時刻 から始まる各時刻において、ジョブに空いているマシンを割り当てることで、実行可能なスケジュールを生成できます。^{[1] [2]}さらに、各時刻ステップでジョブが使用するマシン間隔の数とアイドル間隔の数は、 によって制限されます。^[1]ここで、マシン間隔とは、このセット内のすべてのマシンが同じジョブを処理するような、最大カーディナリティの連続するマシンの集合です。マシン間隔は、その最初と最後のマシンのインデックスによって完全に指定されます。したがって、出力を多項式サイズでエンコードするコンパクトな方法を得ることができます。 ${\displaystyle t=0}$ ${\displaystyle |{\mathcal {J}}|+1}$

計算の難しさ

この問題は、マシンが2台しかなく、すべてのジョブのサイズが（つまり、各ジョブは1台のマシンでのみ実行する必要がある）の場合でもNP困難です。 で表されるこの特殊なケースは、NP困難であることが知られている分割問題の変種です。 ${\displaystyle q_{j}=1}$ ${\displaystyle P2||C_{\max }}$

マシンの数mが最大3の場合、つまり、変種およびに対して、問題を正確に解く擬似多項式時間アルゴリズムが存在する。 ^[7] ${\displaystyle P2|size_{j}|C_{\max }}$ ${\displaystyle P3|size_{j}|C_{\max }}$

対照的に、マシンの数が少なくとも4の場合、つまり、任意の の変種の場合、問題は強力にNP困難でもあります^[8] (この結果は、 に対して強力なNP困難性を示した以前の結果^[7]を改善しました)。 ${\displaystyle Pm|size_{j}|C_{\max }}$ ${\displaystyle m\geq 4}$ ${\displaystyle m\geq 5}$

マシンの数が定数で制限されていない場合、 でない限り、 より小さい近似比を持つ近似アルゴリズムは存在しません。これは、すべてのジョブの処理時間が である特殊なケースにも当てはまります。これは、ビンパッキング問題と同等であるためです。つまり、各タイムステップはビンに対応し、mはビンのサイズ、各ジョブはサイズq _jのアイテムに対応し、メイクスパンを最小化することはビンの数を最小化することに対応します。 ${\displaystyle 3/2}$ ${\displaystyle P=NP}$ ${\displaystyle p_{j}=1}$

変種

この問題にはいくつかの変種が研究されてきた。^[3]以下の変種も互いに組み合わせて検討されてきた。

連続ジョブ：この変形では、機械の順序は固定されています。ジョブを任意のサブセットに割り当てるのではなく、連続した機械区間に割り当てる必要があります。この問題は、ストリップパッキング問題の問題定式化に対応します。 ${\displaystyle (M_{1},\dots ,M_{m})}$ ${\displaystyle m_{j}\subseteq \{M_{1},\dots ,M_{m}\}}$

複数のプラットフォーム：このバリアントでは、マシンセットが独立したプラットフォームに分割されます。スケジュールされたジョブは、1つのプラットフォームのマシンのみを使用でき、処理時に複数のプラットフォームにまたがることはできません。

成形可能なジョブ：この変形では、各ジョブには実行可能なマシンカウントの集合があります。各カウントについて、ジョブはd台のマシンで並列処理でき、この場合、処理時間は になります。ジョブをスケジュールするには、アルゴリズムでマシンカウントを選択し、開始時刻にjを割り当て、時間間隔 の間にマシンに割り当てる必要があります。この種の問題では、ジョブの総作業負荷（ と定義）は、マシン数の増加に対して非増加である と仮定するのが一般的です。 ${\displaystyle j\in {\mathcal {J}}}$ ${\displaystyle D_{j}\subseteq \{1,\dots m\}}$ ${\displaystyle d\in D_{j}}$ ${\displaystyle p_{j,d}}$ ${\displaystyle j\in {\mathcal {J}}}$ ${\displaystyle d\in D_{j}}$ ${\displaystyle s_{j}}$ ${\displaystyle d}$ ${\displaystyle [s_{j},s_{j}+p_{j,d}).}$ ${\displaystyle d\cdot p_{j,d}}$

リリース日: で示されるこのバリアントでは、すべてのジョブが時刻 0 に利用可能になるわけではありません。各ジョブj は、固定された既知の時刻r _jに利用可能になります。その時刻以降にスケジュールする必要があります。 ${\displaystyle P|size_{j},r_{j}|C_{\max }}$

プリエンプション: で示されるこのバリアントでは、すでに実行中のジョブを中断し、その時点で利用可能になる他のジョブをスケジュールすることが可能です。 ${\displaystyle P|size_{j},r_{j},{\text{pmtn}}|C_{\max }}$

アルゴリズム

GareyとGrahamによるリスト・スケジューリング・アルゴリズム^[9]には絶対比 があり、これはTurekら^[10]やLudwigとTiwari ^[11]によって指摘されています。Feldmann 、Sgall、およびTeng ^[12]は、リスト・スケジューリング・アルゴリズムによって生成される非プリエンプティブ・スケジュールの長さは、実際には最大で最適なプリエンプティブ・メイクスパンの倍数であると観察しました。プロセッサ数が定数である場合（ と表記）の多項式時間近似スキーム（PTAS）は、Amouraら^[13]とJansenら^[14]によって発表されました。 その後、JansenとThöle ^[2]は、プロセッサ数がジョブ数に対して多項式的に制限される場合のPTASを発見しました。このアルゴリズムでは、マシン数はアルゴリズムの時間計算量に対して多項式的に現れます。一般に、マシンの数はインスタンスのサイズに対して対数的にしか現れないため、このアルゴリズムは擬似多項式時間近似方式でもあります。Jansen ^[15]は、任意の小さな を除いての下限との差を埋める -近似を与えました。 ${\displaystyle 2}$ ${\displaystyle (2-1/m)}$ ${\displaystyle m}$ ${\displaystyle Pm|size_{j}|C_{\max }}$ ${\displaystyle (3/2+\varepsilon )}$ ${\displaystyle 3/2}$ ${\displaystyle \varepsilon }$

連続ジョブと非連続ジョブの違い

並列タスクスケジューリング問題の例題では、最適なメイクスパンはマシンの隣接性制約に応じて異なる可能性があります。ジョブを非隣接マシンにスケジューリングできる場合、最適なメイクスパンは、隣接マシンにスケジューリングしなければならない場合よりも小さくなる可能性があります。隣接スケジュールと非隣接スケジュールの違いは、1992年に^[16]、 タスク、プロセッサ、、およびの例題で初めて実証されました。Błądekら^[17]は、これらのいわゆるc/nc差を研究し、以下の点を証明しました。 ${\displaystyle n=8}$ ${\displaystyle m=23}$ ${\displaystyle C_{\max }^{nc}=17}$ ${\displaystyle C_{\max }^{c}=18}$

• ac/nc差異が発生するには、少なくとも3つのタスクが必要です。 ${\displaystyle q_{j}>1.}$
• ac/nc差異が発生するには、少なくとも3つのタスクが必要です。 ${\displaystyle p_{j}>1.}$
• ac/nc-difference が発生するには、少なくとも 個のプロセッサが必要です (また、 で ac/nc-difference が発生するインスタンスが存在します)。 ${\displaystyle m=4}$ ${\displaystyle m=4}$
• ac/nc差異が発生するには、非連続スケジュールの長さが少なくとも ${\displaystyle C_{\max }^{nc}=4.}$
• 最大c/nc差は少なくとも最大 ${\displaystyle \sup _{I}C_{\max }^{c}(I)/C_{\max }^{nc}(I)}$ ${\displaystyle 5/4}$ ${\displaystyle 2.}$
• 特定のインスタンスに c/nc 差があるかどうかを判断することは NP 完全です。

さらに、彼らは以下の2つの仮説を提唱したが、これらは未だ証明されていない。

• ac/nc 差異が発生するには、少なくともタスクが必要です。 ${\displaystyle n=7}$
• ${\displaystyle \sup _{I}C_{\max }^{c}(I)/C_{\max }^{nc}(I)=5/4}$

関連する問題

関連するスケジューリング問題として、各ジョブが複数の作業から構成され、それらを並列ではなく順番に実行する必要があるものがあります。これらは、オープンショップスケジューリング、フローショップスケジューリング、ジョブショップスケジューリングです。

参考文献

1. Johannes, Berit (2006-10-01). 「メイクスパンを最小化するための並列ジョブのスケジューリング」. Journal of Scheduling . 9 (5): 433– 452. doi :10.1007/s10951-006-8497-6. hdl : 20.500.11850/36804 . ISSN  1099-1425. S2CID  18819458.
2. Jansen, Klaus.; Thöle, Ralf. (2010-01-01). 「並列ジョブのスケジューリングのための近似アルゴリズム」. SIAM Journal on Computing . 39 (8): 3571– 3615. doi :10.1137/080736491. ISSN  0097-5397.
3. Drozdowski, Maciej (2009). 「並列処理のためのスケジューリング」.コンピュータ通信とネットワーク. doi :10.1007/978-1-84882-310-5. ISBN 978-1-84882-309-9. ISSN  1617-7975.
4. Veltman, B; Lageweg, B. J; Lenstra, J. K (1990-12-01). 「通信遅延を考慮したマルチプロセッサスケジューリング」.並列コンピューティング. 16 (2): 173– 182. doi :10.1016/0167-8191(90)90056-F. ISSN  0167-8191.
5. Graham, RL; Lawler, EL; Lenstra, JK; Rinnooy Kan, AHG (1979). 「決定論的シーケンスとスケジューリングにおける最適化と近似：概説」(PDF) . NATOシステム科学パネルおよび離散最適化シンポジウムの離散最適化およびシステム応用に関する先端研究機関の議事録. Elsevier. pp. (5) 287–326.
6. Codd, EF (1960-06-01). 「マルチプログラムスケジューリング」. Communications of the ACM . 3 (6): 347– 350. doi : 10.1145/367297.367317 . S2CID  14701351.
7. Du, Jianzhong.; Leung, Joseph Y.-T. (1989年11月1日). 「並列タスクシステムのスケジューリングの複雑性」. SIAM Journal on Discrete Mathematics . 2 (4): 473– 487. doi :10.1137/0402042. ISSN  0895-4801.
8. Henning, Sören; Jansen, Klaus; Rau, Malin; Schmarje, Lars (2020年1月1日). 「並列タスクスケジューリングとストリップパッキングにおける計算量と近似不可能性の結果」.計算システム理論. 64 (1): 120– 140. arXiv : 1705.04587 . doi :10.1007/s00224-019-09910-6. ISSN  1433-0490. S2CID  67168004.
9. Garey, MR; Graham, RL (1975年6月1日). 「リソース制約を考慮したマルチプロセッサスケジューリングの境界」. SIAM Journal on Computing . 4 (2): 187– 200. doi : 10.1137/0204015 . ISSN  0097-5397.
10. Turek, John; Wolf, Joel L.; Yu, Philip S.「並列化可能なタスクをスケジュールする近似アルゴリズム | Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures」dl.acm.org . doi :10.1145/140901.141909. S2CID  15607549.
11. Ludwig, Walter; Tiwari, Prasoon (1994). 「適応型および非適応型並列タスクのスケジューリング | 第5回ACM-SIAM離散アルゴリズムシンポジウム議事録」第5回ACM-SIAM離散アルゴリズムシンポジウム (SODA) : 167–176 . ISBN 978-0-89871-329-9。
12. Feldmann, Anja; Sgall, Jiří; Teng, Shang-Hua (1994年8月1日). 「並列マシンにおける動的スケジューリング」.理論計算機科学. 130 (1): 49– 72. doi : 10.1016/0304-3975(94)90152-X . ISSN  0304-3975.
13. Amoura, Abdel Krim; Bampis, Evripidis; Kenyon, Claire; Manoussakis, Yannis (2002年2月1日). 「独立マルチプロセッサタスクのスケジューリング」. Algorithmica . 32 (2): 247– 261. doi :10.1007/s00453-001-0076-9. ISSN  1432-0541. S2CID  17256951.
14. Jansen, Klaus; Porkolab, Lorant (2002年3月1日). 「柔軟な並列タスクのスケジューリングのための線形時間近似スキーム」. Algorithmica . 32 (3): 507– 520. doi :10.1007/s00453-001-0085-8. hdl : 11858/00-001M-0000-0014-7B6C-D . ISSN  1432-0541. S2CID  2019475.
15. Jansen, Klaus (2012). 「成形可能および成形不可能な並列タスクのスケジューリングのための_(3/2+ε)近似アルゴリズム」.第24回ACMアルゴリズムとアーキテクチャにおける並列性に関するシンポジウムの議事録. pp.  224– 235. doi :10.1145/2312005.2312048. ISBN 978-1-4503-1213-4. S2CID  6586439。
16. 「並列化可能なタスクをスケジュールする近似アルゴリズム | Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures」. doi :10.1145/140901.141909. S2CID  15607549. {{cite journal}}:ジャーナルを引用するには|journal=（ヘルプ）が必要です
17. ブウォデク、硫黄;ドロズドフスキ、マチェジ。ギナン、フレデリック。シェプラー、ザビエル（2015 年 10 月 1 日） 「連続および非連続の並列タスクのスケジューリングについて」。スケジュールジャーナル。18 (5): 487–495 .土井: 10.1007/s10951-015-0427-z。ISSN  1099-1425。

「https://en.wikipedia.org/w/index.php?title=Parallel_task_scheduling&oldid=1320654367」から取得