こなさんち

しがないメンヘラエンジニアの日記。

基礎理論~待ち行列~

概要

今回は 待ち行列 について。

私も当初苦手で「公式覚えるの…?」とか思っていましたが、用途や背景を知ると理解が深まります。

待ち行列とは

その名の通り、「行列にて待つ」度合いの色々を表します。よく例として挙げられるのはレジやATMでしょうか。

例えば、「混み具合」「レジがさばき終わるまでの時間」「ATMで自分の順番が回ってくるまでの時間」など、様々な計算に用いられます。

今回はレジを例として使用していきます。

ケンドール記法

既に待ち行列を学ばれた方なら分かるかもしれませんが FEやAPでは M/M/1 モデル というものを採用します。

というよりも、M/M/1モデル以外は採用されないような気がします。

あらゆる参考書も、本ページも、M/M/1モデル前提で話します。

さて、この ○/○/○ のかたちをケンドール記法と言います。

  • 1つ目の○:サービス発生頻度・・・どの頻度でレジにお客さんが並ぶか
  • 2つ目の○:サービス時間・・・レジで会計開始から終了までの時間
  • 3つ目の○:サービス窓口・・・レジの数

という意味があります。

ここで、「M」というのは簡単に言うとランダムという意味です。

つまり、M/M/1モデルは レジに並ぶお客さんもランダム、会計に係る時間もランダム、レジは1つの場合 を前提した計算です。

分布

ここでは、分布の名前が2種類出てきます。分布は、 発生頻度 のようなニュアンスでおぼえていてくれた良いです。

この分布とは、レジにお客さんがどの程度の頻度で来るかな、などの「ばらつき」を示します。このばらつきの種類が2種類あるんですね。

ポアソン分布

レジに人が並ぶ場合を考えてみると、一人のお客さんもいれば、団体客、また0人の場合もあります。

この0もありうる分布をポアソン分布といいます。

指数分布

これはレジにてお客さんをさばく時間ですね。商品が多く長く掛かる人もいれば、一品で簡単に終わる人もいます。でも、 0はない んですよね。

この0はない分布が指数分布です。

出てくるギリシャ文字(コラム)

別にギリシャ文字でなくても良いのでしょうが、昔から待ち行列では

ギリシャ文字 読み方 意味
ρ ロー 混み具合
μ ミュー サービス率
λ ラムダ 到着率

使い方、意味などは後述しますが、「こんなの使うのか…」と知っておくと良いでしょう。

サービス率

サービス率、とは言いますが、これは「サービスを行う時間」やその指数です。

1時間あたりのサービス数 を表し、「平均サービス」といいます。

逆数は 1件あたりの時間 を表し「平均サービス時間」といいます。Tsという記号があります。

この平均サービス率を「μ」と書きます。

{\displaystyle
μ=1/Ts
}

{\displaystyle
Ts = 1/μ
}

ですね。

到着率

レジに到着する頻度を指します。

1時間あたりの到着サービス数 (1時間あたりに何人お客さんが来店するのか) を表し、「平均到着」といいます。

逆数は 1件あたりの時間 を表し「平均到着時間」といいます。Taという記号があります。

この平均到着率を「λ」と書きます。なんだかトボトボ入店してくる人に見えます。イメージ戦法。

{\displaystyle
λ=1/Ta
}

{\displaystyle
Ta = 1/λ
}

ですね。

利用率

これは、来店する客と、レジにて会計中の人の比率です。

{\displaystyle
λ > μ
}

ならば、会計中の人より来店してる人が多いので「さばききれてない状態」を表します。

この混み具合を「平均利用率」といい「ρ」で表します。公式は以下。

{\displaystyle
ρ = λ / μ
}

待ち時間

この混み具合がわかると次に、「現在何人待っているか」という人数が把握できます。

{\displaystyle
ρ / (1 - ρ)
}

です。

また、1件あたりのサービス時間は Ts でしたよね。μの逆数。

なので、合計で待つ時間を Tw とすると、

{\displaystyle
Tw = (ρ / (1 - ρ)) * Ts
}

おわり

公式ばかりと思うかもしれませんが、根本的な用途は「待っている人数や時間、頻度などを求める学問」です。

以上です!