単一マシンスケジューリング

単一マシンスケジューリングまたは単一リソーススケジューリングは、コンピュータサイエンスとオペレーションズリサーチにおける最適化問題です。処理時間の異なるn個のジョブJ ₁、J ₂、 ...、J _nが与えられ、これらを単一のマシン上で、スループットなどの特定の目標を最適化するようにスケジューリングする必要があります。

単一機械スケジューリングは同一機械スケジューリングの特殊なケースであり、同一機械スケジューリング自体は最適ジョブスケジューリングの特殊なケースである。一般的にNP困難である多くの問題も、単一機械スケジューリングでは多項式時間で解くことができる。^[1]^{: 10–20}

最適ジョブスケジューリング問題における標準的な3フィールド表記法では、単一マシン版は最初のフィールドに1が付きます。例えば、「1||」は制約のない単一マシンスケジューリング問題であり、目標は完了時間の合計を最小化することです。 $\sum C_{j}$

複数の機械に共通する目的であるメイクスパン最小化問題 1||は、メイクスパンが常に同一であるため、単一の機械では自明である。そのため、他の目的が研究されてきた。^[2] $C_{\max }$

完了時間の合計を最小化する

問題1||は、完了時間の合計を最小化することを目的としています。これは、最短処理時間優先ルール（SPT）によって最適に解くことができます。つまり、ジョブは処理時間の昇順でスケジュールされます。 $\sum C_{j}$ $p_{j}$

問題1||は、完了時間の加重和を最小化することを目指します。これは、加重最短処理時間優先ルール（WSPT）によって最適に解くことができます。WSPTとは、ジョブを比率の昇順でスケジュールすることです。^[2]^{：講義1、パート2} $\sum w_{j}C_{j}$ $p_{j}/w_{j}$

問題1|チェーン|は、チェーン形式の依存関係を持つジョブに対する上記の問題の一般化です。これは、WSPTの適切な一般化によって最適解を得ることもできます。^[2]^{：講義1、パート3} $\sum w_{j}C_{j}$

遅刻のコストを最小限に抑える

問題1||は、最大遅延を最小化することを目指します。各ジョブjには、期日が存在します。期日を過ぎて完了した場合、遅延はと定義されます。 1|| は、最早期日優先ルール ( EDD ) によって最適に解くことができます。EDD ルールとは、ジョブを期日の昇順でスケジュールするルールです。^[2]^{: 講義 2、パート 2} $L_{\max }$ $d_{j}$ $L_{j}:=C_{j}-d_{j}$ $L_{\max }$ $d_{j}$

問題1|prec|は、問題1||を2つの方法で一般化します。第一に、ジョブに任意の優先順位制約を課すことを許容します。第二に、各ジョブに任意のコスト関数h _j（完了時間の関数）を持たせることを許容します（遅延はコスト関数の特殊なケースです）。最大コストは、ローラーのアルゴリズムとして知られる貪欲アルゴリズムによって最小化できます。^[2]^{：講義2、パート1} $h_{\max }$ $L_{\max }$

問題1 ||は、各ジョブが処理可能になる $r_{j}$ リリース時刻をそれぞれ異なる値に設定することで、問題1||を一般化します。リリース時刻が存在するということは、場合によっては、まだリリースされていない重要なジョブを待つために、マシンをアイドル状態にしておくことが最適な場合があることを意味します。この設定で最大遅延を最小化することはNP困難です。しかし、実際には、分枝限定法を用いて解くことができます。^[2]^{：講義2、パート3} $L_{\max }$ $L_{\max }$

早期の利益を最大化する

期限付き設定では、ジョブが期限までに完了すれば利益p _jが得られる可能性がある。そうでなければ利益は得られない。目標は利益を最大化することにある。期限付き単一マシンスケジューリングはNP困難である。Sahni ^{[3] は、}正確な指数時間アルゴリズムと多項式時間近似アルゴリズムの両方を提示している。

スループットの最大化

問題1||は、 $\sum U_{j}$ 遅延の程度に関わらず、遅延ジョブの数を最小化することを目指します。これはホジソン・ムーアのアルゴリズムによって最適に解くことができます。 ^[4]^[2]^{：講義3、パート1}これは、時間通りに完了するジョブの数を最大化することとも解釈できます。この数はスループットと呼ばれます。

問題1||は、遅延ジョブの $\sum w_{j}U_{j}$ 重みを最小化することを目指しています。これはNP困難です。なぜなら、すべてのジョブが同じ期限を持つ特殊なケース（1||と $d_{j}=d$ $\sum w_{j}U_{j}$ 表記）はナップサック問題と等価だからです。^[2]^{：講義3、パート2}

問題1| | は、 $r_{j}$ $\sum U_{j}$ 異なるジョブが異なるリリース時間を持つことを許容することで、問題1|| $\sum U_{j}$ を一般化します。この問題はNP困難です。しかし、すべてのジョブの長さが等しい場合、この問題は多項式時間で解くことができます。この問題にはいくつかのバリエーションがあります。

重み付き最適化変種1| | $r_{j},p_{j}=p$ $\sum w_{j}U_{j}$ は、時間で解くことができる。^[5] $O(n^{7})$
重み付けなしの最適化変種は、時間通りに終了するジョブの数 （1| |と表記）を最大化し、リリース時間と期限がすべて整数の場合、 $r_{j},p_{j}=p$ $\sum U_{j}$ 動的計画法を使用して時間内に解くことができます。^[6]^[7] $O(n^{5})$
与えられたジョブがすべて時間通りに完了する可能性があるかどうかを決定するという決定変種は、いくつかのアルゴリズムによって解決することができ、^[8]最も速いものは時間内に実行されます。^[9] $O(n\log n)$

ジョブには実行間隔を設定できます。ジョブjには処理時間t _jと開始時刻s _jがあるため、間隔 [ s _j , s _j +t _j ] で実行する必要があります。間隔の一部は重複するため、すべてのジョブを完了できるわけではありません。目標は、完了したジョブの数、つまりスループットを最大化することです。より一般的には、各ジョブには複数の間隔が設定でき、各間隔には異なる利益を設定できます。目標は、ジョブごとに最大で 1 つの間隔を選択し、総利益を最大化することです。詳細については、間隔スケジューリングのページを参照してください。

より一般的には、ジョブは開始時刻と期限を持つタイムウィンドウを持つことができ、そのタイムウィンドウはジョブの長さよりも長くなる場合があります。各ジョブは、そのタイムウィンドウ内の任意の位置にスケジュールできます。Bar-Noy、Bar-Yehuda、Freund、Naor、およびSchieber ^[10]は、(1- ε )/2近似を提示しています。

一定でない長さのジョブ

労働者や機械は、一定時間働くと疲労し、次のジョブの処理速度が低下することがよくあります。一方で、労働者や機械はより効率的に作業する方法を学習し、次のジョブの処理速度を向上させることもあります。どちらの場合も、ジョブの長さ（処理時間）は一定ではなく、それ以前に処理されたジョブに依存します。このような状況では、最大完了時間を最小化することさえ容易ではありません。ジョブの長さの変化をモデル化する一般的な方法は2つあります。

仕事の長さは、仕事の開始時間に依存する場合がある。 ^[11]仕事の長さが開始時間の弱増加関数である場合、それは劣化効果と呼ばれ、弱減少関数である場合、それは学習効果と呼ばれる。
ジョブの長さは、以前に処理されたジョブの通常の処理時間の合計に依存する場合があります。長さがこの合計の弱増加関数である場合、それはしばしば老化効果と呼ばれます。^[12]

開始時間に基づく長さ

ChengとDingは、時刻s _jに予定されているジョブjの実際の長さが次のように与えられる場合のメイクスパン最小化と最大遅延最小化を研究した。

${\widehat {p_{j}}}(s_{j})=p_{j}-b\cdot s_{j}$ ここで、p _jはjの通常の長さです。

彼らは以下の結果を証明しました。

ジョブに任意の期限がある場合、問題は3分割からの縮約によりNP困難となる。^[13]
ジョブに2つの期限のうちの1つがある場合、問題は分割からの縮約によりNP完全となる。^[14]
ジョブが任意のリリース時間を持つことができる場合、問題は任意の期限を持つ問題からの帰結として、強くNP困難である。 ^[15]
ジョブのリリース時刻が0またはRの2通りの場合、問題はNP完全である。^[15]

クビアックとヴァン・デ・ヴェルデ^[16]は、疲労が共通の納期d以降にのみ始まる場合のメイクスパン最小化を研究した。つまり、時刻s _jに予定されているジョブjの実際の長さは、

${\widehat {p_{j}}}(s_{j})=\max(p_{j},p_{j}+b_{j}\cdot (s_{j}-d))$ 。

したがって、ジョブがdより前に開始された場合、その長さは変化しません。d より後に開始された場合、その長さはジョブ依存の速度で増加します。彼らはこの問題がNP困難であることを示し、時間で実行される擬似多項式アルゴリズムを示し、最大100ジョブのインスタンスを妥当な時間で解く分岐限定アルゴリズムを提示しています。また、ジョブが共通の最大劣化日 D > d より後に開始された場合にp _{j の}増加が停止する、限界劣化についても研究しています。この場合、彼らは2つの擬似多項式時間アルゴリズムを提示しています。 $O(nd\sum _{j}p_{j})$

Cheng、Ding、Lin ^[11]は_、時刻sjにスケジュールされたジョブjの長さが線形または区分線形であり、変化率が正または負になる可能性がある劣化効果に関するいくつかの研究を調査しました。

処理時間の合計に基づく長さ

老化の影響には 2 つの種類があります。

位置ベースのエージングモデルでは、ジョブの処理時間は、それより前に処理されたジョブの数、つまりシーケンス内の位置に依存します。^[17]
処理時間の合計に基づくエイジングモデルでは、ジョブの処理時間は、それ以前に処理されたジョブの通常の（エイジングの影響を受けない）処理時間の合計の弱増加関数である。^[18]

ワン、ワン、ワン、ワン^{[19]は、処理時間の合計に基づくエイジングモデルを研究した。ここで、位置}vにスケジュールされたジョブjの処理時間は次のように与えられる。

${\widehat {p_{j}}}(\pi ,v)=p_{j}\cdot \left(1+\sum _{l=1}^{v-1}p_{\pi (l)}\right)^{\alpha }$

ここで、は位置にスケジュールされたジョブであり、α は機械の「経年変化特性」です。このモデルでは、順列の最大処理時間は次のようになります。 $\pi (l)$ $l$ $\pi$

$\sum _{l=1}^{n}{\widehat {p_{\pi (l)}}}(\pi ,l)$

ルデック^[20]は、疲労を処理時間とは異なるものとし、ジョブに依存する老化特性を許容するという2つの方法でモデルを一般化した。

${\widehat {p_{j}}}(\pi ,v)=p_{j}\cdot \left(1+\sum _{l=1}^{v-1}f(p_{\pi (l)})\right)^{\alpha _{j}}$

ここで、fは疲労と処理時間の関係を表す増加関数であり、α _jはジョブjの老化特性である。このモデルにおいて、彼は以下の結果を証明した。

最大完了時間の最小化と最大遅延の最小化は、多項式時間で解決可能です。
一部のジョブに期限がある場合、最大完了時間の最小化と最大遅延の最小化は、非常に NP 困難です。

参照

インターバルスケジュール

単一機械スケジューリング問題の解決には、多くの解法が用いられてきました。以下にそのいくつかを挙げます。

参考文献

^ Eugene L. Lawler, Jan Karel Lenstra, Alexander HG Rinnooy Kan, David B. Shmoys (1993-01-01). 「第9章シーケンスとスケジューリング：アルゴリズムと複雑性」 .オペレーションズ・リサーチ・アンド・マネジメント・サイエンス・ハンドブック. 4 : 445– 522. doi :10.1016/S0927-0507(05)80189-6. ISBN 9780444874726. ISSN 0927-0507.{{cite journal}}: CS1 maint: multiple names: authors list (link)
^ abcdefgh Grinshpoun, Tal (2020). 「スケジュール管理における主題」www.youtube.com . 2021年9月12日閲覧。
^ Sahni, Sartaj K. (1976-01-01). 「独立タスクのスケジューリングアルゴリズム」. Journal of the ACM . 23 (1): 116– 127. doi : 10.1145/321921.321934 . ISSN 0004-5411. S2CID 10956951.
^ Lawler, EL (1994-07-01). 「ナップサック型スケジューリング問題、ムーア・ホジソンアルゴリズム、そして『集合の塔』特性」.数学およびコンピュータモデリング. 20 (2): 91– 106. doi : 10.1016/0895-7177(94)90209-7 . ISSN 0895-7177.
^ Baptiste, P. (1999). 「単一マシン上で処理時間が等しい遅延ジョブの重み付き数を最小化する多項式時間アルゴリズム」 . Journal of Scheduling . 2 (6): 245– 252. doi :10.1002/(SICI)1099-1425(199911/12)2:6<245::AID-JOS28>3.0.CO;2-5.
^ クロバック、マレク;デュール、クリストフ。ヤヴォル、ヴォイチェフ。コワリク、ウカシュ。クロウスキー、マチェジ (2006-02-01)。「スループットを最大化するための等しい長さのジョブのスケジュールに関するメモ」。スケジュールジャーナル。9 (1): 71–73。arXiv : cs / 0410046 。土井：10.1007/s10951-006-5595-4。ISSN 1099-1425。S2CID 7359990。
^ クロバック、マレク;ドゥル、クリストフ。ヤヴォル、ヴォイチェフ。コワリク、ルカシュ。クロウスキー、マチェジ（2021-05-12）。「スループットを最大化するための等しい長さのジョブのスケジュールに関するメモ」。arXiv : cs/0410046。
^ Simons, Barbara (1978-10-16). 「シングルプロセッサスケジューリングのための高速アルゴリズム」 .第19回コンピュータサイエンス基礎シンポジウム (SFCS 1978) . IEEEコンピュータ協会. pp. 246– 252. doi :10.1109/SFCS.1978.4. S2CID 10284575.
^ Garey, MR; Johnson, DS; Simons, BB; Tarjan, RE (1981-05-01). 「任意のリリース時間と期限を持つユニットタイムタスクのスケジューリング」 . SIAM Journal on Computing . 10 (2): 256– 269. doi :10.1137/0210018. ISSN 0097-5397.
^ Bar-Noy, Amotz; Bar-Yehuda, Reuven; Freund, Ari; (Seffi) Naor, Joseph; Schieber, Baruch (2001-09-01). 「リソース割り当てとスケジューリングの近似値化への統一的アプローチ」 . Journal of the ACM . 48 (5): 1069– 1090. doi :10.1145/502102.502107. ISSN 0004-5411. S2CID 12329294.
^ ab Cheng, TC E; Ding, Q; Lin, BM T (2004-01-01). 「時間依存処理時間を考慮したスケジューリングに関する簡潔な調査」 . European Journal of Operational Research . 152 (1): 1– 13. doi :10.1016/S0377-2217(02)00909-8. ISSN 0377-2217.
^ Chang, Pei-Chann; Chen, Shih-Hsin; Mani, V. (2009-01-01). 「学習/老化効果を考慮した納期割り当てと単一機械スケジューリングに関する考察」 . International Journal of Production Economics . 117 (1): 142– 149. doi :10.1016/j.ijpe.2008.10.004. ISSN 0925-5273.
^ Cheng, TCE; Ding, Q. (1999-07-01). 「時間依存型機械メイクスパン問題は強力NP完全である」 . Computers & Operations Research . 26 (8): 749– 754. doi :10.1016/S0305-0548(98)00093-8. ISSN 0305-0548.
^ Cheng, TCE; Ding, Q. (1998-06-01). 「2つの異なる期限と処理時間の減少率が同一である単一マシンスケジューリングの複雑性」 . Computers & Mathematics with Applications . 35 (12): 95– 100. doi :10.1016/S0898-1221(98)00099-6. ISSN 0898-1221.
^ ab Cheng, TCE; Ding, Q. (1998-01-29). 「開始時間依存タスクとリリース時間を考慮したスケジューリングの複雑さ」 . Information Processing Letters . 65 (2): 75– 79. doi :10.1016/S0020-0190(97)00195-6. ISSN 0020-0190.
^ クビアク、ヴィースワフ;ファン・デ・ヴェルデ、シュティーフ（1998年8月）。「メイクスパンを最小限に抑えるために悪化するジョブをスケジュールする」。海軍研究兵站。45 (5): 511–523.doi : 10.1002 /(SICI)1520-6750 ( 199808)45:5<511::AID-NAV5>3.0.CO;2-6。ISSN 0894-069X。
^ Gawiejnowicz, Stanisław (1996-03-25). 「実行ジョブ数に応じて速度が変化する単一プロセッサ上のスケジューリングに関する考察」 . Information Processing Letters . 57 (6): 297– 300. doi :10.1016/0020-0190(96)00021-X. ISSN 0020-0190.
^ Gordon, VS; Potts, CN; Strusevich, VA; Whitehead, JD (2008-10-01). 「劣化と学習を伴う単一機械スケジューリングモデル：優先度生成による先行制約の処理」 . Journal of Scheduling . 11 (5): 357– 370. doi :10.1007/s10951-008-0064-x. ISSN 1099-1425. S2CID 31422825.
^ Wang, Ji-Bo; Wang, Li-Yan; Wang, Dan; Wang, Xiao-Yuan (2009-08-01). 「時間依存劣化を考慮した単一機械スケジューリング」 .国際先進製造技術ジャーナル. 43 (7): 805– 809. doi :10.1007/s00170-008-1760-6. ISSN 1433-3015. S2CID 110043439.
^ Rudek, Radosław (2012-03-01). 「拡張された処理時間合計ベースの経年劣化効果を考慮した単一機械スケジューリング問題」.国際先進製造技術ジャーナル. 59 (1): 299– 309. doi : 10.1007/s00170-011-3481-5 . ISSN 1433-3015.