確率的スケジューリング

確率的スケジューリングは、ランダムな処理時間、ランダムな納期、ランダムな重量、確率的な機械故障などのランダムな属性を伴うスケジューリング問題に関係します。主な用途は、製造システム、コンピュータ システム、通信システム、物流と輸送、機械学習などです。^[要出典]

確率的スケジューリング問題の目的は、総フロー時間、メイクスパン、期日を守れなかった場合の総遅延コストを最小化するなどの規則的な目的である場合もあれば、ジョブを完了するための早さと遅延の両方のコストを最小化する、または激しい台風などの災害の発生が予想される状況でタスクをスケジュールするための総コストを最小化するなどの不規則な目的である場合もあります。^[1]

定期的なパフォーマンス測定または不定期のパフォーマンス測定によって評価されるこのようなシステムのパフォーマンスは、時間の経過とともにジョブのリソースへのアクセスを優先するために採用されるスケジューリング ポリシーによって大きく左右される可能性があります。確率的スケジューリングの目標は、目的を最適化できるスケジューリング ポリシーを特定することです。

確率的スケジューリング問題は、確率的ジョブのバッチのスケジューリングに関する問題、多腕バンディット問題、待ち行列システムのスケジューリングに関する問題の3つのタイプに大別できます^[2] 。これら3つのタイプでは通常、関係するランダム変数の確率分布が事前にわかっているという意味で、完全な情報が利用可能であるという仮定が下されます。このような分布が完全に指定されておらず、関心のあるランダム変数をモデル化するために複数の競合する分布がある場合、その問題は不完全情報と呼ばれます。ベイズ法は、不完全情報を伴う確率的スケジューリング問題の処理に適用されてきました。

このクラスのモデルでは、分布が既知でランダムな処理時間を持つ固定バッチのジョブを、一連のマシンで完了して、特定のパフォーマンス目標を最適化する必要があります。 ${\displaystyle n}$${\displaystyle m}$

このクラスで最も単純なモデルは、単一のマシン上で一連のジョブを順序付けて、期待される加重フロー時間を最小化する問題です。ジョブ処理時間は、ジョブの平均である一般分布に従う独立したランダム変数です。許容されるポリシーは、非予測的 (スケジュール決定は、システムの現在までの履歴に基づいて行われる) かつ非プリエンプティブ (ジョブの処理は、開始したら中断することなく完了まで続行される必要がある) である必要があります。 ${\displaystyle n}$${\displaystyle G_{i}(\cdot )}$${\displaystyle p_{i}}$${\displaystyle i}$

ジョブ のシステムで単位時間あたりに発生するコスト率をで表し、そのランダム完了時間を で表すものとします。許容されるすべてのポリシーのクラスを で表し、ポリシー での期待値を で表すものとします。問題は次のように表すことができます 。${\displaystyle w_{i}\geq 0}$${\displaystyle i}$${\displaystyle {\tilde {C}}_{i}}$${\displaystyle \Pi}$${\displaystyle E_{\pi }[\cdot ]}$${\displaystyle \pi \in \Pi }$

$${\displaystyle \min _{\pi \in \Pi }w_{1}E_{\pi }[{\tilde {C}}_{1}]+\cdots +w_{n}E_{\pi }[ {\チルダ {C}}_{n}].}$$

特別な決定論的ケースにおける最適解は、スミスの最短加重処理時間規則によって与えられる：^[3]ジョブを優先度指数の非増加順に並べる。スミスの規則の自然な拡張は、上記の確率モデルにも最適である。^[4]${\displaystyle w_{i}p_{i}}$

一般に、すべてのジョブ処理時間分布が指数関数的である場合、^[5]すべてのジョブが非減少ハザード率関数を持つ共通の一般処理時間分布を持っている場合、 [ ^6]ジョブ処理時間分布が確率的に順序付けられている場合、予測処理時間が短いジョブに高い優先順位を割り当てるルールは、フロータイム目標に最適です。^[7]

多腕バンディットモデルは、特定の種類の最適リソース割り当て（通常は時間割り当てを伴う）を形成し、多数のマシンまたはプロセッサが競合するプロジェクト（アームと呼ばれる）のセットに対応するために割り当てられます。典型的なフレームワークでは、システムは単一のマシンと、サービスが提供されたときに連続的または特定の離散的な時点でランダムな報酬を提供する一連の確率的に独立したプロジェクトで構成されます。目的は、すべての動的に修正可能なポリシーにわたって期待される合計割引報酬を最大化することです。^[1]

マルチバンディット問題の最初のバージョンは、シーケンシャルデザインの分野でロビンズ（1952）によって定式化されました。^[8]それ以来、20年間本質的な進歩はありませんでしたが、ギッティンズと彼の協力者がマルコフ設定とセミマルコフ設定の下でギッティンズ（1979）、^[9]、ギッティンズとジョーンズ（1974）、^[10]、ギッティンズとグレイズブルック（1977）、^[11]、ホイットル（1980）^[12]で有名な研究成果を上げました。この初期のモデルでは、各アームは、状態遷移を行う時点が決定エポックであるマルコフまたはセミマルコフプロセスによってモデル化されます。マシンは各エポックで、処理中のアームの現在の状態の関数として表される報酬を使用してアームを選択でき、ソリューションは、アームの状態のみに依存する各状態に割り当てられた割り当てインデックスによって特徴付けられます。したがって、これらの指標はギッティンズ指標として知られており、最適な政策は、彼の定評ある貢献により、 通常、ギッティンズ指標政策と呼ばれます。

Gittins の独創的な論文の直後、分岐バンディット問題を拡張して確率的到着をモデル化する手法 (オープン バンディット問題またはアーム獲得バンディット問題としても知られる) が Whittle (1981) によって研究されました。^[13]その他の拡張には、Whittle (1988) ^[14]によって定式化された落ち着きのないバンディットのモデルがあり、このモデルでは各アームが 2 つの異なるメカニズム (アイドル モードとビジー モード) に従って落ち着きなく進化します。また、Van Oyen ら (1992) ^[15]による切り替えコスト/遅延のあるモデルでは、アーム間の切り替えにコスト/遅延が発生する場合、どのインデックス ポリシーも最適ではないことが示されました。

このクラスのモデルは、キューイング システムで最適なサービス規律を設計する問題に関係しています。キューイング システムでは、完了するジョブが最初から利用可能ではなく、時間の経過とともにランダムなエポックで到着します。この設定における主なモデル クラスは、マルチクラス キューイング ネットワーク (MQN) であり、コンピューター通信や製造システムの多目的モデルとして広く適用されています。

最も単純なタイプの MQN では、単一のサーバーで複数のジョブ クラスをスケジュールします。前述の 2 つのモデル カテゴリと同様に、単純な優先度インデックス ルールは、さまざまなこのようなモデルに最適であることがわかっています。

より一般的なMQNモデルには、あるジョブクラスから別のジョブクラスにサービスを変更するための切り替え時間（Levy and Sidi、1990）^[16]や、重複しないジョブクラスのサブセットに対応するサービスを提供する複数の処理ステーションなどの機能が含まれます。このようなモデルの扱いにくさのため、研究者は最適に近いパフォーマンスを実現する比較的単純なヒューリスティックポリシーの設計を目指してきました。

確率的スケジューリング モデルに関する研究の大部分は、処理時間やマシンの起動/停止時間などの関係するランダム変数の確率分布が事前に完全に指定されているという意味で、完全情報の仮定に基づいて確立されています。

しかし、情報が部分的にしか入手できない状況もあります。不完全な情報によるスケジューリングの例としては、環境浄化^[17]、プロジェクト管理^[18] 、石油探査^[19] 、移動ロボットのセンサースケジューリング^[20]、サイクルタイムモデリング^[21]などが挙げられます。

情報が不完全であるため、対象のランダム変数をモデル化するための競合する分布が複数存在する可能性があります。この問題に対処するために、Cai et al. (2009) ^[22]はベイズ情報更新に基づく効果的なアプローチを開発しました。このアプローチでは、競合する各分布をランダム変数 の実現値、たとえば によって識別します。最初は、は履歴情報または仮定 (履歴情報が利用できない場合は無情報である可能性があります) に基づく事前分布を持ちます。 に関する情報は、ランダム変数 の実現値が観測された後に更新される場合があります。意思決定における重要な懸念事項は、更新された情報をどのように利用して意思決定を洗練および強化するかです。スケジューリング ポリシーが時間の経過とともに変化しないという意味で静的である場合、期待される割引報酬を最小化し、共通の指数期日の下で遅延ジョブの数を確率的に最小化する最適なシーケンスが識別されます。^[22]スケジューリングポリシーが、最新の情報に基づいてプロセス中に調整を行うことができるという意味で動的である場合、事後ギッティンズ指数は、動的ポリシーのクラスで期待割引報酬を最小化する最適なポリシーを見つけるために開発されます。^[22]${\displaystyle \Theta}$${\displaystyle \Theta}$${\displaystyle \Theta}$