M/M/1待ち行列モデルとは
待ち行列の長さがどの程度になるかを推測するモデル
待ち行列と言うのは、例えば病院の診察待ち、銀行や市役所窓口での待ち、ラーメンの待ち行列、オフィスのコピー機の待ち行列、コールセンターへ問合せしたときの待ち時間のように、日常的なシーンで見られると思います。情報処理の世界でも、システム上の処理要求が出されてから、処理が終了するまでの待ち時間を推測するために使われます。
◆待ち行列モデルの概要
今回は、病院の診察を例に、待ち行列モデルをイメージしてみてください。
待ち行列モデルでは、３つの要素が待ち時間を推測するために用いられます。
１．患者の到着間隔
患者が何分おきに到着するかの時間です。
２．診察にかかる時間
診察（サービス）にかかる時間です。
３．窓口数（お医者さんの数）
同時にサービスできる窓口の数、病院でいうと診察できるお医者さんの数です。
M/M/1待ち行列モデルとは、
・到着時間がランダムである（マルコフ過程である） → M
・サービス時間がランダムである（マルコフ過程である） → M
・窓口数が１である → １
を並べて、M/M/1と表現しています。
「マルコフ過程」とは、過去の経緯によって未来が変わらないことを言います。例えば午前中にたくさん患者が来たから、午後は患者が少なくなる、と言ったことが起きない事です。すなわち、患者の到着状況に関係なく、ランダムな時間で到着するということです。
到着時間がランダムなので患者が全く来ないということもあり得るますが、現実問題としてはそういうことが起きる確率は低いですよね。これを表現するために、「平均到着時間」を平均値として、それぞれの到着時間の発生確率を決定します。
例えば、平均到着時間が20分であれば、20分で来る人が最も多い。その次に19分や21分で来る人が多い、その次は18分や22分と言った具合です。到着時間がランダムとはいっても、たいてい20分間隔で来るし、間違っても10分から30分の間隔では来る、といったイメージです。
専門的には到着時間がどのようにランダムかというのは、「指数分布に従う」という形になります。なお、到着率（時間当たりの到着人数）はポワソン分布に従う形でランダムとしています。
サービス時間も同様で、平均サービス時間が10分であれば、たいていの人は10分で、10分でなくても5分から15分の間に診察が終わる。ということになります。
◆モデルで使用する変数の定義
モデルに使用する変数をこのように定義します。
１．患者の平均到着間隔 → 平均到着時間 Ta
時間当たりの到着人数 → 到着率 λ
※ λは「ラムダ」と読みます。ギリシア文字です。
この時、下記の関係が成り立ちます。
10分おきに1人到着するなら、1分当たりに到着する人数は1/10人ということです。
２．平均診察時間 → 平均処理時間 Ts
時間当たりのサービス人数 → サービス率 μ
※ μは「ミュー」と読みます。これもギリシア文字です。
この時、下記の関係が成り立ちます。
10分で1人の診察が終わるなら、1分当たりに診察が完了する人数は1/10人ということです。
３．利用率 ρ
「混雑しやすさの指標」です。平均サービス時間と平均到着時間の比率で表現されます。
利用率は下記の式で表されます。
詳しくは後述しますが下記の性質があります。
・この値が大きければ大きいほど行列が伸びやすく、小さければ小さいほど行列が短くなりやすい
・基本的に0から1の範囲に収まる
※ ρは「ロー」と読みます。これもギリシア文字です。
利用率は、待ち時間を表現するときに役に立ってくれます。
◆ずっと続けていることを想定する
このモデルを理解するうえで、もう1つ重要な事があります。
それは、待ち時間を計算するのがどの時点かということです。
普通の病院であれば、病院の診察時間が始まってすでに患者が３人いた場合。最初に並んだ人の待ち時間は0分、次の人は20分後、その次の人は40分後となります。（診察時間が常に20分の場合）つまり、いつ、どこに並んだかによって待ち時間が変動してしまいます。
待ち行列モデルでは、「患者が平均20分おきに来る」、「診察が平均10分で終わる」という条件で、ずーっと診療を続けた結果、「待ち時間が何分に落ち着くか」を計算して推測します。言い換えると、「患者が来るペース」と「患者が帰るペース」が釣り合ったときに、待ち行列にどのくらいの人がいるか、を推測することです。
◆ずっと続けるとどこで釣り合うのか？
３つのパターンに分けて考えてみましょう。
１．「平均到着時間」の方が「平均処理時間」より短い場合 （つまり、 Tλ > Tμ の場合）
２．「平均到着時間」と「平均処理時間」が等しい場合 （つまり、 Tλ = Tμ の場合）
３．「平均到着時間」の方が「平均処理時間」より長い場合 （つまり、 Tλ < Tμ の場合）
１．「平均到着時間」の方が「平均処理時間」より長い場合 （つまり、 Tλ < Tμ の場合）
この場合は、前の人の診察が終わる前に次の人が並ぶことになり、列は無限に伸び続けることになります。
平均到着時間が10分、平均処理時間が20分の場合は、サービスを行っている20分の間に、新しく2人並んでしまうことになります。その2人を対応しているうちに4人、その4人を対応しているうちに8人と、どんどん行列が伸びていってしまいます。ずっと営業することを想定すると列の長さは無限大となって、永遠に「患者が来るペース」と「患者が帰るペース」は釣り合うことができません。
この場合の利用率は、 ρ > 1 となります。
２．「平均到着時間」と「平均サービス時間」が等しい場合 （つまり、 Tλ = Tμ の場合）
この場合は、「不定」が答えになります。
例えば、平均到着時間が20分、平均処理時間が20分とすると、来るペースと帰るペースが釣り合って、行列の長さが一定になりそうに見えます。しかしながら、モデル上においては列の長さは不定となってしまう、が答えになります。現実的に考えると「増減を繰り返して定まらない」と言うことになると思います。来る時間も平均20分と言っても変動するし、帰る時間も平均20分と言っても変動します。なので、列の長さはランダムに変動する「来る時間」と「帰る時間」に即して増減を繰り返していって、定まらない、「不定」が答えということになります。
この場合の利用率は、 ρ = 1 となります。
３．「平均到着時間」の方が「平均処理時間」より長い場合 （つまり、 Tλ < Tμ の場合）
この場合は、直観的には待ち行列が全く発生しないように思いますが、待ち行列は発生して、特定の長さに落ち着きます。
例えば、平均到着時間が40分、平均処理時間が20分とすると、次の患者が到着するまでに前の人の診察が終わっているように思えますが、実際は2人同時に到着する場合もあるので待ち時間が生じたり、待っていた人が診察を受けていてその間に次の人が来るという場合がある為、待ち時間が生じることになります。ただし、１や２の場合と違って、帰るペースの方が早いので、行列に並ぶ人の数はある程度の人数に落ち着いていくことになります。
この場合の利用率は、 ρ < 1 となります。
なお、１と２のケースは問題が破綻するので、試験では出題されません。
◆待ち時間と待ち人数の計算
１．待ち人数 L
自分の前に並んでいる人数です。
２．待ち時間 Tw
自分の順番が来るまでの時間です。
病院の例を元に少し計算をしてみましょう。患者の平均到着時間が20分、診察にかかる時間が10分とした場合、利用率ρは0.5となります。そこから待ち行列の人数を計算すると0.5人となります。つまり、この病院に行くと大体1人が待っている状態ということになります。また、この病院に行くと診察を受けられるまでに大体10分待つということになります。
待ち人数と待ち時間の推定値の求め方は、このようになります。情報処理試験をクリアする上では式を覚えておくだけで大丈夫です。なぜこのような式になるかについては数学的な解説が必要になるので、また別途解説したいと思います。
◆待ち時間の様子をグラフでイメージしてみる
待ち時間がどのように推移するかをグラフでイメージしてみましょう。
待ち時間は、利用率ρが1に近づいていくと一気に大きくなっていくことがわかります。つまり、「入る人数」が「出る人数」に近づいていくと、一気に待ち時間が長くなっていくということになります。
ジェットコースターが長蛇の列になるのは、「入っていく人数」が「出ていく人数」よりも圧倒的に多いからです。特にρが1を超えると一気に列が長くなります。また、逆に割と空いている時間、つまり「入っていく人数」が「出ていく人数」より少ない時間帯でも、ある程度の待ち時間が生じるというのは直感とも合います。
病院がそんなに混雑していないように見えてもなかなか自分の番が回ってこないのも、こういうメカニズムなのですね。
◆リトルの公式
待ち時間を算出する公式は「リトルの公式」と言います。リトルの公式では、
「（行列の人数）÷（1分間に自分の後ろに並んだ人数）＝待ち時間」
という式で、待ち時間を推計できます。
これは、先に計算した式のことを言っています。
例えば病院に入って、10人が待っている（待ち人数L = 10）。1分経って2人がさらにやってきた（到着率λ = 2）とすると、待ち時間は5分と推測できるということです。
◆推定滞在時間の計算
推定滞在時間 Tq
並び始めてからサービスを受けて病院を出るまでの時間です。
単純に、待ち時間とサービス時間を合計すればよいです。
しかし、少し計算してみると、ρで綺麗な形で表すことができます。
加えて、平均処理時間（Ts）、平均到着時間（Ta）、推定待ち時間（Tw）、推定滞在時間（Tq）の間には、下記の関係が成立します。
「平均処理時間（Ts）と平均到着時間（Ta）」の比率と「推定待ち時間（Tw）と推定滞在時間（Tq）」の比率が同じということになります。非常にシンプルで味わい深いですね。