待ち行列理論

待ち行列理論は、待ち行列の数学的研究です。^[1]待ち行列モデルは、待ち行列の長さと待ち時間を予測できるように構築されます。^[1]待ち行列理論は、サービスを提供するために必要なリソースに関するビジネス上の意思決定を行う際に結果が使用されることが多いため、一般にオペレーションズリサーチの分野と見なされています。

待ち行列理論は、コペンハーゲン電話交換会社の着信システムを記述するモデルを作成したアグナー・クラルプ・エルランの研究に端を発しています。 ^{[1]これらのアイデアは、}テレトラフィックエンジニアリングの分野に大きな影響を与え、それ以来、電気通信、トラフィックエンジニアリング、コンピューティング、^[2] プロジェクト管理、特に産業工学に応用され、工場、店舗、オフィス、病院の設計に応用されています。^{[3] [4]}

学術研究の分野では、「queuing」よりも「queueing」という綴りが一般的に見られます。実際、この分野の代表的なジャーナルの 1 つがQueueing Systemsです。

待ち行列理論は、経営科学の分野における主要な研究分野の 1 つです。経営科学を通じて、企業はさまざまな科学的および数学的アプローチを使用してさまざまな問題を解決することができます。待ち行列分析は待ち行列の確率分析であるため、動作特性とも呼ばれる結果は、決定論的ではなく確率的です。^[5] n 人の顧客が待ち行列システムにいる確率、待ち行列システム内の顧客の平均数、待ち行列にいる顧客の平均数、待ち行列システム全体で顧客が費やす平均時間、待ち行列で顧客が費やす平均時間、そして最後にサーバーがビジーまたはアイドルである確率はすべて、これらの待ち行列モデルが計算するさまざまな動作特性です。^[5]待ち行列分析の全体的な目標は、現在のシステムについてこれらの特性を計算し、改善につながる可能性のあるいくつかの代替案をテストすることです。現在のシステムの動作特性を計算し、その値を代替システムの特性と比較することで、管理者は各潜在的なオプションの長所と短所を確認できます。これらのシステムは、節約を増やし、待ち時間を短縮し、効率を向上させる方法などを示し、最終的な意思決定プロセスに役立ちます。使用できる主な待ち行列モデルは、単一サーバー待ち行列システムと複数サーバー待ち行列システムであり、これらについては以下で詳しく説明します。これらのモデルは、サービス時間が一定か不定か、待ち行列の長さが有限か、呼び出し人口が有限かなどによってさらに区別できます。^[5]

キューまたはキューイング ノードは、ほぼブラック ボックスと考えることができます。ジョブ(分野によっては、顧客またはリクエストとも呼ばれます) はキューに到着し、しばらく待機し、処理にしばらく時間がかかり、その後キューから出ていきます。

ただし、キューイング ノードは、キューイング ノードの内部に関する情報が必要なため、完全なブラック ボックスではありません。キューには 1 つ以上のサーバーがあり、それぞれが到着するジョブとペアリングできます。ジョブが完了して出発すると、そのサーバーは再び別の到着するジョブとペアリングできるようになります。

よく使われる例えは、スーパーマーケットのレジ係です。(他のモデルもありますが、文献ではこれがよく見られます。) 顧客が到着し、レジ係によって処理されて、立ち去ります。各レジ係は一度に 1 人の顧客を処理するため、これは 1 つのサーバーのみを持つキューイング ノードです。顧客が到着したときにレジ係が忙しい場合、顧客がすぐに立ち去る設定は、バッファなし(または待機エリアなし) のキューと呼ばれます。最大n 人の顧客を待機できる設定は、サイズnのバッファを持つキューと呼ばれます。

単一のキュー (キューイング ノードとも呼ばれる)の動作は、キューへの到着とキューからの出発、および現在システム内にあるジョブの数を表す誕生 - 消滅プロセスによって記述できます。kがシステム内のジョブ数 (処理中、またはキューに待機ジョブのバッファーがある場合は待機中) を表す場合、到着によってkが 1増加し、出発によってkが 1 減少します。

システムは、各ジョブの到着率と出発率で発生する「誕生」と「死」によってkの値の間を遷移します。キューの場合、これらの率は一般にキュー内のジョブの数によって変化しないと考えられるため、単位時間あたりの到着/出発の平均率は 1 つであると想定されます。この想定では、このプロセスの到着率は、出発率は となります。 ${\displaystyle \lambda_{i}}$${\displaystyle \mu_{i}}$${\displaystyle i}$${\displaystyle \lambda ={\text{avg}}(\lambda _{1},\lambda _{2},\dots ,\lambda _{k})}$${\displaystyle \mu ={\text{avg}}(\mu _{1},\mu _{2},\dots ,\mu _{k})}$

誕生と死滅の過程の定常状態方程式はバランス方程式と呼ばれ、次のようになります。ここで は状態nにある定常状態確率を表します。 ${\displaystyle P_{n}}$

${\displaystyle \mu _{1}P_{1}=\lambda _{0}P_{0}}$

${\displaystyle \lambda _{0}P_{0}+\mu _{2}P_{2}=(\lambda _{1}+\mu _{1})P_{1}}$

${\displaystyle \lambda _{n-1}P_{n-1}+\mu _{n+1}P_{n+1}=(\lambda _{n}+\mu _{n})P_{ n}}$

最初の2つの式は

${\displaystyle P_{1}={\frac {\lambda _{0}}{\mu _{1}}}P_{0}}$

そして

${\displaystyle P_{2}={\frac {\lambda _{1}}{\mu _{2}}}P_{1}+{\frac {1}{\mu _{2}}}(\ mu _{1}P_{1}-\lambda _{0}P_{0})={\frac {\lambda _{1}}{\mu _{2}}}P_{1}={\frac {\lambda _{1}\lambda _{0}}{\mu _{2}\mu _{1}}}P_{0}}$。

数学的帰納法によって、

${\displaystyle P_{n}={\frac {\lambda _{n-1}\lambda _{n-2}\cdots \lambda _{0}}{\mu _{n}\mu _{n- 1}\cdots \mu _{1}}}P_{0}=P_{0}\prod _{i=0}^{n-1}{\frac {\lambda _{i}}{\mu _{i+1}}}}$。

この状態は ${\displaystyle \sum _{n=0}^{\infty }P_{n}=P_{0}+P_{0}\sum _{n=1}^{\infty }\prod _{i=0 }^{n-1}{\frac {\lambda _{i}}{\mu _{i+1}}}=1}$

${\displaystyle P_{0}={\frac {1}{1+\sum _{n=1}^{\infty }\prod _{i=0}^{n-1}{\frac {\lambda _{i}}{\mu _{i+1}}}}}}$

これは、の式と合わせて、必要な定常状態確率を完全に記述します。 ${\displaystyle P_{n}}$ ${\displaystyle (n\geq 1)}$

単一のキューイングノードは通常、ケンドールの表記法 A/S/ c を使用して記述されます。ここで、A はキューへの各到着間の所要時間の分布、S はジョブのサービス時間の分布、c はノードのサーバー数です。^{[6] [7]}表記法の例として、M/M/1 キューは、単一のサーバーがポアソン過程(到着間隔が指数分布)に従って到着し、指数分布のサービス時間 (M はマルコフ過程) を持つジョブを処理する単純なモデルです。M /G/1 キューでは、G は「一般」を意味し、サービス時間の 任意の確率分布を示します。

1 つのサーバーと次の特性を持つキューを検討します。

• ${\displaystyle \lambda}$: 到着率（各顧客が到着するまでの予想時間の逆数、例：1秒あたり10人の顧客）
• ${\displaystyle \mu}$: 平均サービス時間の逆数（同じ単位時間あたり、例えば30秒あたりに連続してサービスが完了すると予想される回数）
• n : システム内の顧客数を特徴付けるパラメータ
• ${\displaystyle P_{n}}$:定常状態においてシステム内にn人の顧客が存在する確率

さらに、 はシステムが状態nに入る回数を表し、 はシステムが状態nから出る回数を表します。すると、すべてのnに対して となります。つまり、システムが状態から出る回数は、その状態に入る回数と最大で 1 だけ異なります。これは、システムが将来のある時点でその状態に戻るか ( )、戻らないか ( )のいずれかだからです。 ${\displaystyle E_{n}}$${\displaystyle L_{n}}$${\displaystyle \left\vert E_{n}-L_{n}\right\vert \in \{0,1\}}$${\displaystyle E_{n}=L_{n}}$${\displaystyle \left\vert E_{n}-L_{n}\right\vert =1}$

システムが安定状態に到達すると、到着率は出発率と等しくなるはずです。

したがってバランス方程式

${\displaystyle \mu P_{1}=\lambda P_{0}}$

${\displaystyle \lambda P_{0}+\mu P_{2}=(\lambda +\mu )P_{1}}$

${\displaystyle \lambda P_{n-1}+\mu P_{n+1}=(\lambda +\mu )P_{n}}$

暗示する

${\displaystyle P_{n}={\frac {\lambda }{\mu }}P_{n-1},\ n=1,2,\ldots }$

幾何分布の式 を導く事実${\displaystyle P_{0}+P_{1}+\cdots =1}$

${\displaystyle P_{n}=(1-\rho )\rho ^{n}}$

どこ。 ${\displaystyle \rho ={\frac {\lambda }{\mu }}<1}$

一般的な基本的な待ち行列システムはアーランによるもので、リトルの法則の修正版です。到着率λ、ドロップアウト率σ、出発率μを考えると、待ち行列の長さLは次のように定義されます。

${\displaystyle L={\frac {\lambda -\sigma }{\mu }}}$。

割合が指数分布であると仮定すると、待ち時間W はサービスを受ける到着者の割合として定義できます。これは、待機期間中に脱落しない人々の指数生存率に等しく、次の式が成り立ちます。

${\displaystyle {\frac {\mu }{\lambda }}=e^{-W{\mu }}}$

2 番目の式は通常、次のように書き直されます。

${\displaystyle W={\frac {1}{\mu }}\mathrm {ln} {\frac {\lambda }{\mu }}}$

2段階ワンボックスモデルは疫学では一般的である。^[8]

1909年、コペンハーゲン電話交換局に勤務していたデンマーク人エンジニアのアグナー・クラルプ・エルランが、現在では待ち行列理論と呼ばれる理論に関する最初の論文を発表しました。^{[9] [10] [11]}彼は、交換局に到着する電話の呼び出し数をポアソン過程によってモデル化し、 1917年にM/D/1待ち行列、 1920年にM/D/ k待ち行列モデルを解きました。 ^[12]ケンドールの表記法では、

• Mは「マルコフ」または「記憶なし」の略で、到着がポアソン過程に従って発生することを意味します。
• Dは「決定論的」の略で、キューに到着するジョブには一定量のサービスが必要であることを意味します。
• k はキューイングノードのサーバーの数を表します ( k = 1、2、3、...)

ノードにサーバーよりも多くのジョブがある場合、ジョブはキューに入れられ、サービスを待機します。

M /G/1待ち行列は1930年にフェリックス・ポラチェクによって解かれ、 ^{[13]その後}アレクサンドル・ヒンチンによって確率論的な観点から再構成され、現在ではポラチェク・ヒンチンの公式として知られています。^{[12] [14]}

1940年代以降、待ち行列理論は数学者の研究対象となった。^[14] 1953年、デイビッド・ジョージ・ケンドールはGI/M/ k待ち行列を解き^{[15] 、現在}ケンドールの表記法として知られる待ち行列の現代的な表記法を導入した。1957年、ポラチェクは積分方程式を用いてGI/G/1を研究した。^[16] ジョン・キングマンはG/G/1待ち行列の平均待ち時間の式を与え、現在キングマンの式として知られる。^[17]

レナード・クラインロックは、 1960 年代初頭にキューイング理論のメッセージ交換への応用、 1970 年代初頭にパケット交換への応用に取り組みました。この分野への彼の最初の貢献は、1962 年にマサチューセッツ工科大学で博士論文として発表され、1964 年に書籍として出版されたことです。1970 年代初頭に発表された彼の理論的研究は、インターネットの前身であるARPANETにおけるパケット交換の使用の基礎となりました。

行列幾何学法と行列解析法は、位相型分散到着間隔とサービス時間分布を持つ待ち行列を考慮することを可能にした。 ^[18]

結合軌道を持つシステムは、無線ネットワークや信号処理への応用における待ち行列理論において重要な部分を占めています。^[19]

待ち行列理論の現代的応用は、とりわけ、（物質的な）製品が一定の体積と一定の持続時間を持つという意味で時空間的存在を持つ製品開発に関係している。 ^[20]

M/G/ kキューのパフォーマンスメトリックなどの問題は未解決のままである。^{[12] [14]}

キューイング ノードではさまざまなスケジューリング ポリシーを使用できます。

先入れ先出し

先着順（FCFS）^[21]とも呼ばれるこの原則は、顧客は一度に1人ずつサービスを受け、最も長く待っている顧客が最初にサービスを受けるというものです。^[22]

後から入ったものが先から出る

この原則でも、一度に1人ずつ顧客にサービスを提供しますが、待ち時間が最も短い顧客が最初にサービスされます。^[22]スタックとも呼ばれます。

プロセッサ共有

サービス容量は顧客間で均等に分配される。^[22]

優先度

優先度の高い顧客が最初にサービスを受けます。^[22]優先キューには、非プリエンプティブ（サービス中のジョブを中断できない）とプリエンプティブ（サービス中のジョブをより優先度の高いジョブによって中断できる）の2種類があります。どちらのモデルでも作業が失われることはありません。^[23]

最短の仕事から

次に提供される仕事は、最も小さいサイズのものです。^[24]

先制最短ジョブを優先

次に処理されるジョブは、元のサイズが最も小さいジョブです。^[25]

残り処理時間が最短

次に処理すべきジョブは、残っている処理要件が最も小さいジョブです。^[26]

サービス施設

• シングルサーバー: 顧客が並んでいて、サーバーは1つだけ
• 複数の並列サーバー（単一キュー）：顧客が列を作り、複数のサーバーが存在する
• 複数の並列サーバー（複数のキュー）：カウンターが多数あり、顧客はどのキューに並ぶかを決めることができます。

信頼できないサーバー

サーバー障害は確率的（ランダム）プロセス（通常はポアソン分布）に従って発生し、その後セットアップ期間が続き、その間サーバーは利用できなくなります。中断された顧客は、サーバーが修復されるまでサービスエリア内に留まります。^[27]

顧客の待機行動

• 躊躇：顧客は列が長すぎると列に並ばないことを決める
• 駆け引き: 顧客は、列を切り替えた方が早くサービスを受けられると考えた場合、列を切り替える。
• 契約破棄: 顧客はサービス待ち時間が長すぎると列を離れる

到着した顧客がサービスを受けられなかったこと（キューにバッファがなかったか、顧客が躊躇したり契約を破棄したりしたことによる）は、ドロップアウトとも呼ばれます。ドロップアウトの平均率は、キューを表す重要なパラメータです。

キュー ネットワークは、複数のキューが顧客ルーティングによって接続されたシステムです。顧客が 1 つのノードでサービスを受けると、別のノードに参加してサービス待ちのキューに入るか、ネットワークを離れることができます。

m個のノードを持つネットワークの場合、システムの状態はm次元ベクトル ( x ₁、x ₂、...、x _m ) で表すことができます。ここで、x _{i は}各ノードの顧客数を表します。

最も単純で非自明な待ち行列ネットワークはタンデム待ち行列と呼ばれる。^[28]この分野での最初の重要な結果はジャクソンネットワーク^{[29] [30]}であり、これには効率的な積形式定常分布が存在し、平均値分析^[31] (スループットや滞在時間などの平均メトリックを可能にする) を計算できる。^[32]ネットワーク内の顧客の総数が一定である場合、ネットワークはクローズドネットワークと呼ばれ、ゴードン・ニューウェル定理によって積形式定常分布を持つことが示された。^{[33]この結果は}BCMP ネットワーク^[34]に拡張され、非常に一般的なサービス時間、レジーム、および顧客ルーティングを持つネットワークも積形式定常分布を示すことが示された。正規化定数は、1973 年に提案されたBuzen のアルゴリズムを使用して計算できる。^[35]

ケリーネットワークなどの顧客ネットワークも研究されており、異なるクラスの顧客は異なるサービスノードで異なる優先レベルを経験する。^[36]別のタイプのネットワークはGネットワ​​ークで、1993年にエロル・ゲレンベによって最初に提案された。^[37]これらのネットワークは、古典的なジャクソンネットワークのような指数時間分布を想定していない。

離散時間ネットワークでは、どのサービスノードがいつでもアクティブになれるかという制約があるため、最大重みスケジューリングアルゴリズムは、各ジョブが1人のサービスノードのみを訪問する場合に最適なスループットを与えるサービスポリシーを選択します。^[21]ジョブが複数のノードを訪問できるより一般的なケースでは、バックプレッシャールーティングが最適なスループットを与えます。ネットワークスケジューラは、より大きなネットワークの特性に影響を与えるキューイングアルゴリズムを選択する必要があります。 ^[38]

平均場モデルは、キューの数mが無限大に近づくにつれて、経験的尺度（異なる状態にあるキューの割合）の限界挙動を考慮します。ネットワーク内の任意のキューに対する他のキューの影響は、微分方程式によって近似されます。決定論的モデルは、元のモデルと同じ定常分布に収束します。^[39]

占有率の高いシステム（利用率が1に近い）では、重交通近似を使用して、反射ブラウン運動^[40] 、オルンシュタイン-ウーレンベック過程、またはより一般的な拡散過程^[41]によって待ち行列長過程を近似することができます。ブラウン過程の次元数は待ち行列ノードの数に等しく、拡散は非負のオルタントに制限されます。

流体モデルは、プロセスが時間と空間でスケールされ、異種オブジェクトを許容する限界をとることによって得られるキューイングネットワークの連続的な決定論的類似物です。このスケールされた軌道は、システムの安定性を証明できる決定論的方程式に収束します。キューイングネットワークは安定しているが、不安定な流体限界を持つことが知られています。^[42]

キューイング理論は、コンピュータ サイエンスと情報技術で幅広く応用されています。たとえば、ネットワークでは、キューはルータやスイッチに不可欠なものであり、パケットはそこで送信のためにキューイングされます。キューイング理論の原理を適用することで、設計者はこれらのシステムを最適化し、応答性の高いパフォーマンスと効率的なリソース利用を確保できます。技術の領域を超えて、キューイング理論は日常的な体験に関連しています。スーパーマーケットで列に並んでいるときでも、公共交通機関で列に並んでいるときでも、キューイング理論の原理を理解することで、これらのシステムを最適化してユーザー満足度を高めるための貴重な洞察が得られます。いつかは、誰もがキューイングに何らかの形で関わることになります。一部の人にとっては不便に見えるものが、最も効果的な方法である可能性もあります。キューイング理論は、応用数学とコンピュータ サイエンスに根ざした学問であり、キューまたは待ち行列の研究と分析、およびさまざまなアプリケーションにおけるキューイングの影響に特化した分野です。この理論的枠組みは、キューの存在を特徴とするシステムの効率を理解し、最適化する上で役立つことが証明されています。キューの研究は、交通システム、コンピュータ ネットワーク、電気通信、サービス運用などのコンテキストで不可欠です。待ち行列理論は、到着プロセスとサービス プロセスを中心に、さまざまな基本概念を掘り下げます。到着プロセスは、エンティティが時間の経過とともにキューに参加する方法を示し、多くの場合、ポアソン過程などの確率過程を使用してモデル化されます。待ち行列システムの効率は、主要なパフォーマンス メトリックによって測定されます。これには、平均キュー長、平均待機時間、およびシステム スループットが含まれます。これらのメトリックは、システムの機能性に関する洞察を提供し、パフォーマンスの向上と待機時間の短縮を目的とした決定を導きます。参考文献: Gross, D.、Harris, CM (1998)。Fundamentals of Queueing Theory。John Wiley & Sons。Kleinrock, L. (1976)。Queueing Systems: Volume I - Theory。Wiley。Cooper, BF、Mitrani, I. (1985)。Queueing Networks: A Fundamental Approach。John Wiley & Sons

• グロス、ドナルド、カール・M・ハリス（1998）。待ち行列理論の基礎。ワイリー。ISBN 978-0-471-32812-4。オンライン
• Zukerman, Moshe (2013). 待ち行列理論と確率的テレトラフィックモデル入門(PDF) . arXiv : 1307.2968 .
• デイテル、ハーベイ M. (1984) [1982]。オペレーティングシステム入門（初版再版）。アディソン・ウェスレー。673 ページ。ISBN 978-0-201-14502-1。第15章、380～412ページ
• ゲレンベ、エロル、イシ・ミトラニ (2010)。コンピュータシステムの分析と統合。ワールド・サイエンティフィック第 2 版。ISBN 978-1-908978-42-4。
• Newell, Gordron F. (1971 年 6 月 1 日)。待ち行列理論の応用。Chapman および Hall。
• レナード・クラインロック、「大規模通信ネットワークにおける情報の流れ」（MIT、ケンブリッジ、1961年5月31日）博士論文提案
• レナード・クラインロック。大規模通信ネットワークにおける情報の流れ（RLE 四半期進捗レポート、1961 年 7 月）
• レナード・クラインロック著『コミュニケーション ネット: 確率的メッセージ フローと遅延』 (McGraw-Hill、ニューヨーク、1964 年)
• クラインロック、レナード（1975年1月2日）。待ち行列システム：第1巻 - 理論。ニューヨーク：ワイリーインターサイエンス。pp.417。ISBN 978-0-471-49110-1。
• クラインロック、レナード（1976 年 4 月 22 日）。キューイング システム: 第 2 巻 - コンピュータ アプリケーション。ニューヨーク: ワイリー インターサイエンス。576 ページ。ISBN 978-0-471-49111-8。
• Lazowska, Edward D.、John Zahorjan、G. Scott Graham、Kenneth C. Sevcik (1984)。定量的システムパフォーマンス: キューイングネットワークモデルを使用したコンピュータシステム分析。Prentice-Hall, Inc. ISBN 978-0-13-746975-8。
• ジョン・クラインバーグ。エヴァ・タルドス（2013年6月30日）。アルゴリズム設計。ピアソン。ISBN 978-1-292-02394-6。

無料辞書のウィクショナリーで「queuing 」 または「queuing」を調べてください。

• Teknomo のキューイング理論チュートリアルと計算機
• Virtamo のキューイング理論コース
• Myron Hlynka のキューイング理論ページ
• LINE: 待ち行列モデルを解決するための汎用エンジン