M/M/1 待ち行列
M/M/1 待ち行列 (英: M/M/1 queue) は確率論の一分野である待ち行列理論の用語で、1列に並んだ客や要求を1つの窓口やサーバが処理する待ち行列で、待ち行列に到着する客や要求がポアソン過程(英語版)に従い、窓口やサーバがこれらを処理する時間が指数分布に従うものを指す。なお、新しく到着した客や要求は待ち行列の一番後ろに並び、窓口やサーバは待ち行列の先頭から順に客や要求を処理するものとする(先着順(英語版)方式)。また待ち行列のバッファは無限に大きいものとする(すなわち、客が待つ部屋は無限に広く、待ち行列の長さに限界がないということ)。
M/M/1待ち行列において、待ち行列が増加する要因(=客や要求の到着)がポアソン過程に従うという事は、待ち行列の長さが1伸びるのに要する時間が無記憶かつ指数分布に従うことを意味するので、M/M/1待ち行列では、待ち行列の長さが増加する場合も減少する(=窓口やサーバが客や要求を処理する)場合も指数分布に従う。
またこのことから待ち行列の長さの増加および減少がいずれも無記憶のマルコフ過程に従うので、無記憶のMemoryless もしくはマルコフの Markovianとサーバの台数1とあわせて、ケンドールの記号から「M/M/1」待ち行列と名づけられた。
M/M/1待ち行列は最も基礎的な待ち行列モデルであり、このモデルからはいくつもの閉じた式(英語版)としての魅力的な研究対象を得ることができる。このモデルを複数のサーバーに拡張したものがM/M/c 待ち行列(英語版)である。
時間 t→∞ のときのM/M/1待ち行列の漸近的な振る舞いは
ρ = λ/μ
という値(平均利用率)によって特徴付けられる。
ρ ≥ 1 の場合は λ≥μ であるので、時間がたつにつれて待ち行列の長さが際限なく伸びていき、定常分布を持たない。
逆に ρ < 1 であれば安定であり、定常過程を持つことを示すことができる。