15 待ち行列モデルの基礎
- ケンドールの記号を理解する．
- 滞在時間，待ち時間，系内客数，待ち行列長などの評価指標を理解する．
- リトルの法則を理解し，適用できる．
- \(G/G/1\)，\(G/G/c\) 待ち行列の基本的な関係式を理解する．
図 15.1 は，典型的な待ち行列システムを示している．待ち行列システムは待ち行列とサーバから構成される．これ以降は，待ち行列システムを単にシステムと呼ぶことにする．図に示すように，客（customer）はシステムに到着（arrival）し，待ち行列（queue）に並び，サービスを受け，最後にシステムを退出（departure）する．
15.1 ケンドールの記号
待ち行列モデルは，ケンドールの記号（Kendall’s notation）により表現する．
\[ A/B/X \]
ここで，\(A\) は到着間隔分布の種類，\(B\) はサービス時間分布の種類，\(X\) はサーバ数を表す．\(A\) と \(B\) には以下の記号が用いられる．
| 記号 | 意味 |
|---|---|
| \(M\) | 指数分布 |
| \(D\) | 決定論的 |
| \(G\) | 一般分布 |
| \(E_k\) | \(k\) 次アーラン分布 |
| \(H_k\) | \(k\) 次超指数分布 |
例えば，客の到着間隔が指数分布に従い，サービス時間が一定であり，サーバ数が1である場合，その待ち行列モデルは \(M/D/1\) と表される．本章の最後では，\(G/G/1\) 待ち行列と \(G/G/c\) 待ち行列について説明する．これらのモデルから得られた一般的な結論は，他の多くの待ち行列モデルにも適用できる．
- アーラン分布 \(E_k\) と間違えないようにするため．
- 指数分布のマルコフ性（Markovian property）と無記憶性（memoryless property）に由来する．
15.2 評価指標
待ち行列理論の代表的な性能評価指標を紹介する．
滞在時間は客がシステムに到着してサービスを受け，システムを退出するまでにかかる時間である．待ち時間は，客がシステムに到着してからサービスを受けるまでの時間である．平均滞在時間は \(W\)，平均待ち時間は \(W_q\) で表す．
系内客数は待ち行列システム内にいる客数である．待ち行列長は待ち行列にいる客数である．平均系内客数は \(L\)，平均待ち行列長は \(L_q\) で表す．
| システム | 待ち行列 | |
|---|---|---|
| 客数 | 系内客数 | 待ち行列長 |
| 時間 | 滞在時間 | 待ち時間 |
15.3 リトルの法則
リトルの法則（Little’s Law）は，待ち行列理論における基本的な関係式であり，平均系内客数 \(L\)，平均到着率 \(\lambda\)，平均滞在時間 \(W\) の関係を示すものである．リトルの法則は \(L = \lambda W\) と表される．すなわち，平均系内客数 \(L\) は，平均到着率 \(\lambda\) と平均滞在時間 \(W\) の積に等しい．
例 15.1 (大学の在籍学生数) ある大学の経営システム系では，毎年80人の新入生が入学し，卒業までに4年間在籍する．このとき，経営システム系に在籍している学生の平均人数を求めよ．
平均到着率 \(\lambda\) は80人/年，平均滞在時間 \(W\) は4年である．リトルの法則により，平均系内客数 \(L\) は次のように求められる．
\[ L = \lambda W = 80 \times 4 = 320 \text{ 人} \]
よって，経営システム系には320人の学生が在籍していることになる．
例 15.2 ある銀行では，1時間に平均20人の客が来店し，各客が銀行に滞在する平均時間は12分である．このとき，この銀行には平均何人の客がいるか．
平均到着率 \(\lambda\) は20人/時間，平均滞在時間 \(W = 12 \text{ 分} = 12/60 \text{ 時間}\) である．リトルの法則から，平均系内客数 \(L\) は
\[ L = \lambda W = 20 \times \frac{12}{60} = 4 \text{ 人} \]
となる．すなわち，銀行内には平均して4人の客が滞在する．平均滞在時間 \(W\) や平均到着率 \(\lambda\) が増加すると，平均系内客数 \(L\) も増加することがわかる．
時刻 \(t\) までに累積到着客数を \(A(t)\) とする．時刻 \(t\) における系内客数を \(N(t)\) とする．客 \(k\) の滞在時間を \(W^(k)\) とする．\(t \to \infty\) とすると，極限が存在するとき，平均到着率 \(\lambda\)，平均系内客数 \(L\)，平均滞在時間 \(W\) はそれぞれ次の式で定義される．
\[ \lambda = \lim_{t \to \infty} \frac{A(t)}{t} , \quad L = \lim_{T \to \infty} \frac{1}{T} \int_0^T N(t) dt, \quad W = \lim_{k \to \infty} \frac{1}{k} \sum_{i=1}^k W^{(i)} \]
これまでは，システム全体に関するリトルの法則を紹介したが，待ち行列を「システム」として考えた場合にも同様の関係が成り立つ．平均待ち行列長を \(L_q\)，平均待ち時間を \(W_q\)，平均到着率を \(\lambda\) とすると，
\[ L_q = \lambda W_q \]
が成り立つ．
15.4 \(G/G/1\)，\(G/G/c\) 待ち行列
\(G/G/1\) と \(G/G/c\) 待ち行列における一般的な結論を説明する．記号のまとめを以下に示す．
| 記号 | 意味 |
|---|---|
| \(\lambda\) | 平均到着率，単位時間あたりの到着客数の平均 |
| \(L\) | 平均系内客数 |
| \(W\) | 平均滞在時間 |
| \(L_q\) | 平均待ち行列長 |
| \(W_q\) | 平均待ち時間 |
| \(S\) | サービス時間を表す確率変数 |
| \(\mu\) | 平均サービス率，単位時間あたりに処理できる客数の平均 |
| \(c\) | サーバ数 |
| \(\rho\) | 利用率 |
15.4.1 サービス率と利用率
\(S\) をサービス時間を表す確率変数とする．平均サービス時間を \(E[S]\) と表す．単位時間あたりに一つのサーバが処理できる客数の平均は \[ \mu = \frac{1}{E[S]} \] で計算する．\(\mu\) を平均サービス率（average service rate）と呼ぶ．
平均サービス時間は客がサービスを受けるのにかかる時間の平均であり，平均サービス率は単位時間あたりに処理できる客数の平均である．
利用率 \(\rho\) は，次の式で定義される．
\[ \rho = \frac{\lambda}{c \mu} \]
ここで，\(c\) はサーバ数を表す．利用率 \(\rho\) は，到着率 \(\lambda\) がシステムの処理能力 \(c \mu\) に対してどの程度であるかを示す指標である．システムの忙しさを表す．
システムの使用を開始するとき，システムの状態（系内客数など）は初期状態に大きく依存する．時間が十分に経過すると，システムの状態は初期状態の影響を受けなくなり，一定の条件下で定常状態（steady state）にある．定常状態において，システムの状態は一定の確率分布に従い，時間が経過しても変化しない．定常状態が存在するためには，\(\rho < 1\) である必要がある．
\(\lambda\) と \(\mu\) が与えられたとき，\(\rho < 1\) という条件を用いて，システムが定常状態に達するためのサーバ数 \(c\) の最小値を求めることができる．すなわち，
\[ \rho = \frac{\lambda}{c \mu} < 1 \]
を満たす最小の整数 \(c\) を求めればよい．
例 15.3 あるコールセンターでは，オペレーター10人が勤務している．1件の電話対応に平均して10分かかる．1時間あたり30件の電話がかかってくるとする．
- 社員一人1時間あたりに対応できる電話の平均件数を求めよ．
- このコールセンターの利用率を求めよ．
- 安定した運用のために必要な最小のサーバ数を求めよ．
平均サービス時間 \(E[S] = 10 \text{ 分} = 1/6 \text{ 時間}\) である．平均サービス率 \(\mu\) は \[ \mu = \frac{1}{E[S]} = \frac{1}{1/6} = 6 \text{ 件/時間} \] となる．すなわち，社員一人は1時間あたり平均6件の電話に対応できることになる．
平均到着率 \(\lambda\) は30件/時間，平均サービス率 \(\mu\) は6件/時間，サーバ数 \(c\) は10である．利用率 \(\rho\) は次のように計算される．
\[ \rho = \frac{30}{10 \times 6} = \frac{30}{60} = 0.5 \]
よって，このコールセンターの利用率は0.5である．
安定した運用のためには，\(\rho < 1\) を満たす必要がある．すなわち，
\[\begin{align*} c & > \frac{\lambda}{\mu} \\ c & > 5 \end{align*}\]
したがって，必要な最小のサーバ数は6である．
15.4.2 \(L\)，\(W\)，\(L_q\)，\(W_q\) の関係
客がシステムに到着してから退出するまでの平均滞在時間 \(W\) は，平均待ち時間 \(W_q\) と平均サービス時間 \(E[S]\) の和で表される．すなわち，
\[ W = W_q + E[S] = W_q + \frac{1}{\mu} \]
である．リトルの法則により，
\[ L = \lambda W = \lambda \left( W_q + \frac{1}{\mu} \right) =\lambda W_q + \frac{\lambda}{\mu} = L_q + \frac{\lambda}{\mu} \]
が成り立つ．\(L = L_q + \lambda / \mu\) が成り立つから，\(\lambda/ \mu\) はサービスを受けている客数の平均を表していると言える．また，\(\lambda/ \mu = L - L_q\) であるから，稼働中のサーバ数の平均を表しているとも言える．
以上の関係式をまとめると，次のようになる．
\[\begin{align*} L & = \lambda W \\ W & = W_q + \frac{1}{\mu} \\ L_q & = \lambda W_q \\ L & = L_q + \frac{\lambda}{\mu} \end{align*}\]
これらの関係式は4つの指標 \(L\)，\(W\)，\(L_q\)，\(W_q\) のうち，1つがわかれば，他の3つを計算できることを示している．
15.5 用語集
| 英語 | 日本語 |
|---|---|
| service facility | サービス施設 |
| server | サーバ |
| number of servers | サーバ数 |
| interarrival time | 到着間隔 |
| service time | サービス時間 |
| arrival rate | 到着率 |
| service rate | サービス率 |
| offered load |
15.6 演習問題
練習 15.1 (アイスクリーム屋さん) あるアイスクリーム屋さんでは，1名の店員が客の注文を受け付け，アイスクリームを提供している．平均して，1時間に30人の客が来店している．店員は，1時間に60人の客に対応できる．客の平均待ち時間を \(5\) 分とする．
- このアイスクリーム屋さんの利用率を求めよ．
- 客の平均滞在時間，平均系内客数，平均待ち行列長を求めよ．
解答 15.1. 平均到着率 \(\lambda\) は30人/時間，平均サービス率 \(\mu\) は60人/時間である．サーバ数 \(c = 1\) であるため，利用率は
\[ \rho = \frac{30}{1 \times 60} = 0.5 \] となる．
平均サービス時間 \(E[S] = 1 \text{ 分}\)，平均待ち時間 \(W_q = 5 \text{ 分}\) であるから，平均滞在時間 \(W\) は
\[ W = W_q + E[S] = 5 + 1 = 6 \text{ 分} \] となる．リトルの法則により，平均系内客数 \(L\) は \[ L = \lambda W = 30 \times \frac{6}{60} = 3 \text{ 人} \] となる．同様に，平均待ち行列長 \(L_q\) は \[ L_q = \lambda W_q = 30 \times \frac{5}{60} = 2.5 \text{ 人} \] となる．