M/M/1_待ち行列

ウィキペディア

M/M/1 待ち行列

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2023/12/18 14:16 UTC 版)

M/M/1 待ち行列ノード

M/M/1 待ち行列 (英: M/M/1 queue) は確率論の一分野である待ち行列理論の用語で、1列に並んだ客や要求を1つの窓口やサーバが処理する待ち行列で、待ち行列に到着する客や要求がポアソン過程（英語版）に従い、窓口やサーバがこれらを処理する時間が指数分布に従うものを指す。なお、新しく到着した客や要求は待ち行列の一番後ろに並び、窓口やサーバは待ち行列の先頭から順に客や要求を処理するものとする（先着順（英語版）方式）。また待ち行列のバッファは無限に大きいものとする（すなわち、客が待つ部屋は無限に広く、待ち行列の長さに限界がないということ）。

M/M/1待ち行列において、待ち行列が増加する要因（＝客や要求の到着）がポアソン過程に従うという事は、待ち行列の長さが１伸びるのに要する時間が無記憶かつ指数分布に従うことを意味するので、M/M/1待ち行列では、待ち行列の長さが増加する場合も減少する（＝窓口やサーバが客や要求を処理する）場合も指数分布に従う。

またこのことから待ち行列の長さの増加および減少がいずれも無記憶のマルコフ過程に従うので、無記憶のMemoryless もしくはマルコフの Markovianとサーバの台数1とあわせて、ケンドールの記号から「M/M/1」待ち行列と名づけられた。

M/M/1待ち行列は最も基礎的な待ち行列モデルであり^[1]、このモデルからはいくつもの閉じた式（英語版）としての魅力的な研究対象を得ることができる。このモデルを複数のサーバーに拡張したものがM/M/c 待ち行列（英語版）である。

記述

M/M/1 待ち行列は待ち行列の長さによって記述可能なので、M/M/1 待ち行列は待ち行列の長さ全体の集合 {0,1,2,3,...} を状態空間を集合とする確率過程として定義可能である。M/M/1 待ち行列は前述のように長さの増減がいずれも指数分布に従うので、待ち行列への新しい要求が1つ到着するまでの平均時間が 1/λ で、サーバが１つの要求を処理する平均時間が 1/μ であるとすると、

• 待ち行列の長さが1つ増加するのにかかる時間tが従う確率密度関数：${\displaystyle \lambda e^{-\lambda t}~~~(t\geq 0)}$

  このマルコフ連鎖の推移速度行列（英語版）は以下のようになる。

  ${\displaystyle Q={\begin{pmatrix}-\lambda &\lambda \\\mu &-(\mu +\lambda )&\lambda \\&\mu &-(\mu +\lambda )&\lambda \\&&\mu &-(\mu +\lambda )&\lambda &\\&&&&\ddots \end{pmatrix}}}$

Weblio日本語例文用例辞書

「M/M/1 待ち行列」の例文・使い方・用例・文例

• 最後に入ったものが最初に出るような待ち行列（後入先出法）