2
Help us understand the problem. What are the problem?

More than 5 years have passed since last update.

posted at

updated at

待ち行列理論 その2

前回の予告通りM/M/1モデルを考える。公式集的なものとして使いたい場合は見るのは最初と最後だけでかまいません。

M/M/1モデルとは

M/M/1モデルはクライアントがポアソン分布に従って到着してサービスにかかる時間が指数分布に従うような、サーバーが1つのモデルである。省略されてはいますが、行列の長さは$\infty$でサービスの規律はFCFSです。このモデルはすべてのモデルの中で最も基本的で最も簡単ですので、このモデルにおける考え方はおそらくどのモデルでも使われると思います。

系内にn人いる確率

まずポアソン過程に従ってクライアントが来ると仮定します。つまり十分短い時間間隔$\Delta t$には高々クライアントは1人しか来ないと仮定します。このとき平均到着率を$\lambda$とするとクライアントが1人来る確率は$\lambda \Delta t$と表すことができます。というのも測定時間をTとした時に、その時刻をN等分して$\Delta t$になるとするとクライアントが到着している確率は$\frac{\lambda T}{N}=\lambda \Delta t$が成り立つからです。ここで時刻tに系内でクライアントがk人いる確率を$P_k(t)$とします。この確率の$\Delta t$後の変化を記述していきます。同様に平均サービス率が$\mu$のサーバーからクライアントが出ていく確率も$\mu \Delta t$となります。以降で系内のクライアントの数の変化を表す方程式(状態方程式)ほ考えます。

  • k=0のとき

$P_0(t+\Delta t)=P_0(t)(1-\lambda \Delta t)+P_1(t)(1-\lambda \Delta t)\mu \Delta t$が成り立ちます。
というのも右辺の第1項はクライアントが0人のとき$\Delta t$後にもクライアントが到着しない確率です。そして第2項はクライアントが1人のとき$\Delta t$後にクライアントが1人も来ないで1人だけ去っていく確率です。
この式を変形させてやると$\frac{P_0(t+\Delta t)-P_0(t)}{\Delta t}=-P_0(t)\lambda+P_1(t)(\mu-\lambda\mu\Delta t)$となるので$\Delta t \to 0$としてやると左辺は$P_0(t)$の微分の形になることに注意してやると$\frac{dP_0(t)}{dt}=-P_0(t)\lambda+P_1(t)\mu$が成り立ちます。

  • k>0のとき

$P_k(t+\Delta t)=P_k(t)(1-\lambda \Delta t)(1-\mu \Delta t)+P_{k+1}(t)(1-\lambda \Delta t)\mu \Delta t+P_{k-1}(t)\lambda \Delta t(1-\mu \Delta t)+P_k(t)\lambda \Delta t \mu \Delta t$が成り立ちます。
というのも右辺の第1項はクライアントがk人のとき$\Delta t$後にもクライアントが到着しておらずなおかつクライアントが出ていかない確率です。第2項はクライアントが(k+1)人のとき$\Delta t$後にクライアントが1人も来ないで1人だけ去っていく確率です。第3項はクライアントが(k-1)人のとき$\Delta t$後にクライアントは来るが出ていかない確率です。そして第4項はクライアントがk人のときに$\Delta t$後にはクライアントが1人到着するが1人サービスを終えて出ていく確率です。
この式を変形させてやると$\frac{P_k(t+\Delta t)-P_k(t)}{\Delta t}=P_k(t)(-\lambda - \mu +2\lambda \mu \Delta t)+P_{k+1}(t)(\mu-\lambda\mu\Delta t)+P_{k-1}(t)(\lambda-\lambda\mu \Delta t)$となるので$\Delta t \to 0$としてやると左辺は$P_k(t)$の微分の形になることに注意してやると$\frac{dP_k(t)}{dt}=-P_k(t)(\lambda +\mu)+P_{k+1}(t)\mu+P_{k-1}(t)\lambda$が成り立ちます。

ここで十分時間が経ち定常状態になったとします。このとき安定した状態であるから微笑時間中の系内の人数変化はありません。つまり$\frac{dP_k(t)}{dt}=0$が成り立ちます。ここで$P_k(t)$が定常状態で一定となっているときの値を$P_k$とする。するとk=0のときは$0=-P_0\lambda+P_1\mu$つまり$P_0\lambda=P_1\mu$なので$\rho=\frac{\lambda}{\mu}$を用いて$P_1=\rho P_0$と表せます。k>0のときは$0=-P_k(\lambda +\mu)+P_{k+1}\mu+P_{k-1}\lambda$つまり$P_k(\lambda +\mu)=P_{k+1}\mu+P_{k-1}\lambda$なので同様に$\rho$を用いて$P_k(\rho +1)=P_{k+1}+P_{k-1}\rho$となります。
試しにk=1のときを考えてみることにします。このときの状態方程式は$P_1(\rho +1)=P_2+P_0\rho$なので$P_1=\rho P_0$を代入してやると$P_2=\rho P_1={\rho}^2P_0$となることがわかります。これを帰納的に計算していくことによって任意のkで確率を求めてやると$P_k={\rho}^kP_0$であることがわかります。
ここで確率が持つ性質の「取りうる状態の確率の総和は1」を利用すると$1=\sum_{k=0}^{\infty}P_k=\sum_{k=0}^{\infty}{\rho}^kP_0$より$0<\rho<1$と仮定してやることにより$1=\frac{1}{1-\rho}P_0$が成り立つことがわかるので$P_0=1-\rho$となります。以上より0を含む自然数kに対して$P_k=(1-\rho){\rho}^k$となっていることがわかります。これで系内にk人クライアントがいる確率がわかりました。
この後は待ち行列の初期の話で頻発する公式を求めてみます。

系内の平均客数 L

Lは平均値つまり期待値なので$L=\sum_{k=0}^{\infty}kP_k=\sum_{k=0}^{\infty}k(1-\rho){\rho}^k$から求めてやればいいことになります。$0<\rho<1$から$\sum_{k=0}^{\infty}k\rho^{k-1}=\frac{1}{(1-\rho)^2}$であることを利用すると$L=(1-\rho)\rho\sum_{k=0}^{\infty}k\rho^{k-1}=(1-\rho)\rho\frac{1}{(1-\rho)^2}=\frac{\rho}{1-\rho}$となる。よって$L=\frac{\rho}{1-\rho}$が成り立ちます。

系内の平均待ち時間 W

リトルの公式から$W=\frac{L}{\lambda}=\frac{\rho}{\lambda(1-\rho)}$となります。また$W=\frac{\lambda}{\mu\lambda(1-\rho)}=\frac{1}{\mu(1-\rho)}=\frac{1}{\mu-\lambda}$と表記することもできる。

待ち行列での平均客数 L_q

$L_q$は系内にいる客数の平均Lからサーバーを利用している客数の平均$L_s$を引いてやればいいです。つまり$L_q=L-L_s$を考えればいいことになります。ここで$L_s$はサーバーの利用率と等しいことが利用率の意味の定義から明らかなので$L_s=\rho$を代入すると$L_q=\frac{\rho}{1-\rho}-\rho=\frac{\rho^2}{1-\rho}$となる。これはLの公式と非常に似ているが$L=L_q+L_s$という関係式に代入して考えてみれば忘れにくいかと思います。

待ち行列の平均待ち時間 W_q

リトルの公式から$W_q=\frac{L_q}{\lambda}=\frac{\rho^2}{\lambda(1-\rho)}$となることがわかります。またこれは$L_s$の時と同様に$W=W_q+W_s$の関係式と$W_s=\frac{1}{\mu}$を使って求めてやっても同じ結果が出ます。またWの時のように$W_q=\frac{\rho}{\mu(1-\rho)}=\frac{\rho}{\mu-\lambda}$

まとめ

系内の平均客数は $L=\frac{\rho}{1-\rho}$
系内の平均待ち時間は $W=\frac{\rho}{\lambda(1-\rho)}=\frac{1}{\mu(1-\rho)}=\frac{1}{\mu-\lambda}$
待ち行列の平均客数は $L_q=\frac{\rho^2}{1-\rho}$
待ち行列の平均待ち時間は $W_q=\frac{\rho^2}{\lambda(1-\rho)}=\frac{\rho}{\mu(1-\rho)}=\frac{\rho}{\mu-\lambda}$
となります。ただし$0<\rho<1$の時です。もし$\rho=1$の時はこの公式は成り立ちません。ですが普通$0<\rho<1$の場合しか起きない(もし1を超えていたら早急にその系の改善が必要なため)のでここでは省略します。知りたい人は$\rho=1$で計算してみてください。
このように待ち行列の確率を求めて系内の平均客数を求めてLを求めてそこから芋ずる式にほかの公式を求めてやることができます。慣れるまでは状態方程式は扱うのが難しいですが慣れてしまえば万が一忘れてしまっても求めることができます。まあ面倒くさいですが。
次回はM/M/N/Nモデルを書こうと思います。

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Sign upLogin
2
Help us understand the problem. What are the problem?