マルコフ型待ち行列

マルコフ型待ち行列は、ポアソン到着と指数サービス時間を持つため、顧客数は連続時間マルコフ連鎖となり、その平衡状態は明示的に解くことができます。

Definition

マルコフ型待ち行列とは、顧客がポアソン過程に従って到着し、独立な指数サービス時間を必要とするサービスシステムであり、システム内の数は誕生死連続時間マルコフ連鎖として進化し、明示的な定常状態および待ち時間分布を持ちます。

Scope

このトピックでは、待ち行列システムのケンドールの記法、単一サーバーM/M/1待ち行列とその幾何学的定常分布、複数サーバーM/M/cおよび損失システム、アーランB式とC式、安定性とトラフィック強度、そして基礎となる誕生死過程からの平均待ち行列長、待ち時間、ビジー期間量の導出について扱います。

Core questions

• M/M/1待ち行列はどのように誕生死過程として生じ、その定常分布は何ですか？
• トラフィック強度に関するどのような条件が待ち行列の安定性を保証しますか？
• 平均待ち行列長と待ち時間はどのように得られ、リトルの法則はどのように適用されますか？
• 複数のサーバーと有限容量はアーラン式をどのように変化させますか？

Key theories

M/M/1の定常分布と安定性

M/M/1待ち行列内の数は、トラフィック強度（到着率とサービス率の比）に等しいパラメータを持つ幾何学的定常分布に従い、この比が1未満である場合に限り待ち行列は安定します。

アーランの損失式と遅延式

複数サーバーシステムの場合、アーランB式は損失システムにおける呼損確率を与え、アーランC式は遅延システムにおける待ち確率を与えます。これらはいずれも誕生死平衡方程式から導出され、容量計画の中心的な要素です。

Clinical relevance

マルコフ型待ち行列は、電話回線群の規模決定、コールセンターの人員配置、サーバーファーム、サービスカウンターなどの基礎的なモデルであり、アーラン式は提供される負荷と目標サービスレベルを必要なサーバー数に変換します。

History

アーランは1909年から1917年にかけて電話トラフィックの損失式と遅延式を導出し、ケンドールは1953年に体系的な到着/サービス/サーバー記法と埋め込み連鎖解析を導入しました。クラインロックの1970年代の論文は、この理論をコンピュータおよび通信ネットワークに応用しました。

Key figures

• Agner Krarup Erlang
• David Kendall
• Leonard Kleinrock

Seminal works

• kleinrock1975

Frequently asked questions

M/M/1とは何を意味しますか？

ケンドールの記法では、最初のMはマルコフ型（ポアソン）到着を、2番目のMは指数サービス時間を、そして1は単一サーバーを意味します。

マルコフ型待ち行列はいつ安定しますか？

トラフィック強度（到着率を総サービス率で割ったもの）が1未満の場合に安定します。そうでない場合、待ち行列は無限に増大し、定常分布は存在しません。