再生理論と待ち行列理論

再生理論は、確率的に再帰エポックで再開するプロセスを分析し、待ち行列理論は、顧客が到着し、待ち、サービスを受けるシステムにそれを適用します。

Definition

再生理論は、到着間隔時間が独立同分布である計数プロセスを研究し、ポアソン過程を一般化します。一方、待ち行列理論は、到着プロセスとサービスプロセスを組み合わせて、待ち時間、待ち行列の長さ、および利用率を研究することにより、サービスシステムをモデル化します。

Scope

この分野は、再生プロセスと再生関数、初等的および主要な再生定理、再生プロセスと再生報酬フレームワーク、M/M/1やM/M/cなどのマルコフ型待ち行列の構造と平衡、平均数と待ち時間を関連付けるリトルの法則、および積形式解を持つ相互作用する待ち行列のネットワークを扱います。

Sub-topics

• Markovian Queues
• Queueing Networks
• Regenerative Processes
• Renewal Theory

Core questions

• 指数分布の到着間隔時間を任意の分布に一般化することは、ポアソン過程をどのように拡張するのでしょうか？
• 再生定理は、長期的な速度と漸近的な挙動について何を述べているのでしょうか？
• 平衡状態において、平均待ち行列長と待ち時間はどのように関連しているのでしょうか？
• 待ち行列のネットワークは、いつ扱いやすい積形式解を許容するのでしょうか？

Key theories

再生定理と再生報酬

初等的および主要な再生定理は、再生の長期的な速度と再生方程式の解の極限挙動を与え、再生報酬定理は、長期的な平均報酬をサイクルあたりの期待報酬を期待サイクル長で割ったものとして表現します。

リトルの法則

安定した待ち行列システムでは、存在する顧客の長期平均数は、到着率に各顧客がシステム内で過ごす平均時間を乗じたものに等しくなります。これは、スループット、占有率、および遅延を関連付ける分布に依存しない恒等式です。

Clinical relevance

再生理論と待ち行列理論は、電話およびデータネットワーク、コールセンター、製造ライン、コンピュータシステム、交通機関、および医療サービスの能力の設計と分析の基礎となり、ランダムな需要があるシステムにおける遅延、スループット、およびリソース利用率を定量化します。

History

エルランは1909年から1920年の間に電話トラフィックの公式を用いて待ち行列理論を創始し、再生理論は1940年代から1950年代にかけてフェラー、スミス、コックスによって発展しました。リトルの1961年の待ち行列長恒等式の証明とジャクソンの1957年のネットワーク結果は、この理論を複雑なサービスシステムに拡張しました。

Key figures

• Agner Krarup Erlang
• William Feller
• David Cox
• John Little

Seminal works

• asmussen2003

Frequently asked questions

再生理論はポアソン過程をどのように一般化するのでしょうか？

ポアソン過程の指数分布の到着間隔時間を、任意の独立同分布の時間に置き換えることで、プロセスは再生構造を保持しつつ、無記憶性を失います。

リトルの法則とは何ですか？

安定したシステムにおける平均顧客数は、到着率に顧客がシステム内で過ごす平均時間を乗じたものに等しいと述べており、到着分布やサービス分布には依存しません。