待ち行列理論(その 7・最終回)

数学・OR

M/M/s 型待ち行列(まとめ)

ランダム到着・ランダムサービス(客の到着間隔とサービス時間が共に指数分布に従う)における諸結果をまとめておきます。
L_q=\frac{\lambda\mu(\lambda/\mu)^s}{(s-1)!(s\mu-\lambda)^2}p_0
L=L_q+\frac{\lambda}{\mu}
W_q=\frac{\mu(\lambda/\mu)^s}{(s-1)!(s\mu-\lambda)^2}p_0
W=W_q+\frac{1}{\mu}
ただし
p_0=\frac{1}{\sum_{n=0}^{s-1}\frac{1}{n!}(\frac{\lambda}{\mu})^n+\frac{(\lambda/\mu)^s}{(s-1)!\{s-(\lambda/\mu)\}}}

\mu W_q の意味

\mu W_q は s と \rho=\frac{\lambda}{s\mu} だけで表すことができます。実際
\mu W_q=\frac{s^{s-1}\rho^s}{s!(1-\rho)^2}p_0
ただし
p_0=\frac{1}{\sum_{n=0}^{s-1}\frac{s^n\rho^n}{n!}+\frac{s^s\rho^s}{s!(1-\rho)}}
となります。ところで \mu W_q は、「列に並び始めてからサービスを受け始めるまでの待ち時間は、平均サービス時間の何倍であるか」を示す尺度となります。例えば s=1,\rho=0.8 のときは
\mu W_q=\frac{\rho}{1-\rho}=\frac{0.8}{1-0.8}=4
となるので、待ち時間は平均サービス時間の 4 倍であるとわかります。仮に平均サービス時間が 30 秒ならば、待ち時間は平均で 2 分ということになります。
今、客の平均到着率が 2 倍になった状況を考えてみます。このとき窓口を 2 つに増やせば(s=2)、\rho=0.8 のままです。
そうすると
p_0=\frac{1}{\frac{2^0 0.8^0}{0!}+\frac{2^1 0.8^1}{1!}+\frac{2^2 0.8^2}{2!(1-0.8)}}=\frac{1}{1+\frac85+\frac{32}{5}}=\frac19
\mu W_q=\frac{2^{2-1}0.8^2}{2!(1-0.8)^2}\times\frac19=\frac{16}{9}
となるので、待ち時間は平均サービス時間の \frac{16}{9} 倍に短縮されます。平均サービス時間が先程と同じ 30 秒であれば、待ち時間は \frac{160}{3}=53.33\dots (秒)となります。

実はコンピュータにおけるデュアルコアの考え方は、正にこの考え方に基づいています。これまではシングルコアのクロック周波数を高めることで PC の高速化が図られてきましたが、CPU 単体での高速化には限界があります。そこで、CPU にコアを複数搭載する、すなわちタスクの受け入れ窓口を増やすことによって、増加した処理すべきタスクの待ち時間を短縮し、PC の高速化を図ろうというわけです。待ち行列の理論は、こんなところでも活かされているわけです。

待ち行列には、まだまだ、例えば列の長さに制限がある場合や、到着分布やサービス分布が指数分布以外の場合の理論などがありますが、今回は最も基本的なものだけを紹介させていただきました。より理論を追求したい方は、専門書も出ていますので、そちらを手にとって勉強されると良いと思います。一冊だけ参考書を挙げておきます。

待ち行列理論

待ち行列理論