いかにしてM/M/1 待ち行列理論の問題をとくか
情報処理技術者試験でよく出題されるM/M/1 待ち行列理論の問題の解き方を調べていたところ、- サルでもわかる待ち行列 が見つかった。たいへんよいコンテンツで大いに参考になった。ただ、検討してみて(自分にとっては)より簡単な形にまとまったのでそれを紹介してみる。本家では
何度もトライしたけど待ち行列が理解できない人向けです． 正確な定義や論理展開は重視せず，いかに効率的にこの理論を覚えることができるかに焦点を絞ってみました．
をゴールにしているが、ここではさらにレベルを下げて、何度もトライしたけど待ち行列理論問題が正解できない・すぐ忘れる人向け(理解しなくてもいい)とし、いかに効率的に情報処理技術者試験でこの問題を解くかに焦点を絞ってみた。
結論
λ … 単位時間あたりの、とぼとぼ歩いてくる患者数 [人数/時間]
σ … 単位時間あたりの、さらさらカルテを書いて医者が診る患者数 [人数/時間]
のとき、ターンアラウンドタイム(自分の診療時間を含む)は
ターンアラウンドタイム = $\frac{1}{σ - λ}$
待ち時間は、一人の診療時間は$\frac{1}{σ}$[時間/人数]であることから、
待ち時間 = $\frac{1}{σ - λ}$ - $\frac{1}{σ}$
動機
- サルでもわかる待ち行列 はとても覚えやすく、特にλ をとぼとぼ歩く患者、σ をさらさらカルテを書く医者に見立てるのが気に入った。ただ練習問題を解くときに、まずρ(込み具合)を$\frac{λ}{σ}$で求めてからさらに計算をするのを見て、「それなら最初からλ とσ だけで計算していったらもっと計算が簡単なのでは」と思ったのがきっかけ。するとターンアラウンドタイムが前述のようなとてもシンプルな式になった。
利点
式と計算が簡単になったことに加え、ρ を使わないことによってそもそも覚えることが減った。
また、分母に注目すると、以下のことが簡単にわかる：
ターンアラウンドタイム = $\frac{1}{σ - λ}$
- 医者の処理能力が増えるほど分母が小さくなり、ターンアラウンドタイムが減る。
- 患者数が増えるほど分母が大きくなり、ターンアラウンドタイムが増える。
- 医者の処理能力より患者到着率が上回ると、値がマイナスになってしまい、いつまでたっても終わらない。
これはρ=$\frac{λ}{σ}$ からも同様にわかることだが、割り算が引き算になっていることで、よりわかりやすくなっているように思う。
さらに、うろ覚えでも間違いに気づきやすい。もし式を間違って$\frac{1}{λ - σ}$を計算した場合、値が負になるのですぐに間違ったことに気付く。 いっぽうρ を使う場合、間違えてρ=$\frac{σ}{λ}$ とするとρ > 1 となり、しっかり理解していればρが1以上になるのはおかしいと気付けるものの、負の値になることの気付きやすさには及ばない。
問題を解くのに必要なこと
まずは- サルでもわかる待ち行列 の理解に努める。
そしてλ とσ の意味を正しく覚えておく。「単位時間あたり」に着目しておくとよい。また、問題文中に直接λ やσ の[人数/時間]の値がなく、その逆数の単位である[時間/人数]が示されていることがある。例えば「患者が平均で15分に一人来る」とある場合、λ[人数/時間]は15ではなくその逆数の1/15。単位を手がかりにλとσを求められるようにしておく。
$\frac{1}{σ - λ}$の式は暗記しておくが、待ち時間の式はターンアラウンドタイムの式からから導き出せるようにしておく。そのためには、一人の診察時間が$\frac{1}{σ}$であることを理解しておかなければならない。覚える方法、また忘れてしまった場合はやはり単位を手がかりにするとよい。σ の単位が[人数/時間]でなので、それを[時間/人数]にするには、と考えれば$\frac{1}{σ}$になる。
練習問題
ある病院では、患者は平均で1時間に一人来る。また医者は一人で、平均で1時間に二人処理できる。このときの待ち時間は平均どのくらいか。
あえてシンプルな問題にしたのは、単に公式に当てはめて答えを出す前に、情景と答えをイメージしてもらいたいため。そうすれば公式や計算を間違えたときにおかしいと気づける可能性が上がるし、理解が深まる。
解答だが、解くにはまずそろえる単位時間を決める。1時間か1分が考えられるが、ここでは1時間にする。
λ = 1
σ = 2
ターンアラウンドタイム = 1/(2-1) = 1[時間]
待ち時間 = ターンアラウンドタイム - $\frac{1}{σ}$ = 1 - 1/2 = 1/2[時間] = 30[分]
平均で30分待って、自分の診療を30分してもらって、合計1時間かかる。イメージと合っていただろうか。
ここで医者の処理速度が2倍になり、1時間に4人診られるという条件に変えてみよう。すると$\frac{1}{ρ-λ}$のρ が2から4に変わるので、ターンアラウンドタイムが1/(2-1)=1から1/(4-1)=1/3になる。式がシンプルなので、ρ やλ の変化がどのようにターンアラウンドタイムに反映されるか、$\frac{ρ}{1-ρ}$を使う場合よりもイメージしやすい。
もっと練習してみたい人のために以下を挙げておく：
平成29年秋期問23 プリンタの平均印刷時間｜ネットワークスペシャリスト.com
令和3年春期問23 M/M/1の待ち行列モデル｜ネットワークスペシャリスト.com
補足
情報処理技術者試験にも以下のように$\frac{ρ}{1-ρ}$をベースにした問題が出題されるので、$\frac{ρ}{1-ρ}$もやっぱり押さえておかなければならない。場面に応じて両方使いこなせるのがよい。
平成26年秋期問2 M/M/1の待ち行列モデル｜ネットワークスペシャリスト.com
令和元年秋期問2 M/M/1の待ち行列モデル｜ネットワークスペシャリスト.com
