待ち行列理論（M/M/1モデル）がようやく分かった（情報処理技術者試験レベルで）

毛利です。

ようやく待ち行列理論（M/M/1モデル）が（直感的に）理解できたのでメモ。
※2012/12/08 読み直して分かりづらかったので少し修正

平均到着率、平均サービス率という概念がイメージできずにいたが、何が分からなかったのかが分かった

「平均ｘｘ率」と「平均ｘｘ時間」をごっちゃにしてた。
例えば、1時間あたりx人(到着|サービス)します、という場合。（情報処理技術者試験ではトランザクション処理要求、トランザクション1件当たりの処理時間という文脈で使用される）
以下の3つの考え方があるかと思う。

1時間あたり人数と考える（←平均(到着|サービス)率）
1分あたりの人数と考える（←平均(到着|サービス)率）
y分毎に1人と考える（←これは平均(到着|サービス)時間。1/μや1/λで表される概念）

■「1時間あたり6人」の場合

6(6人/1時間)
0.1(6人/60分)
10分(60分/6人)

■「1時間あたり12人」の場合

12(12人/1時間)
0.2(12人/60分)
5分(60分/12人)

1時間あたりの人数が倍になると、1,2は2倍（6:12 もしくは 0.1:0.2）、3だと半分（10:5で0.5倍）となる。
前者が「平均ｘｘ率」の概念。後者は「平均ｘｘ時間」。

なお前者は比率なので、1時間あたりで考えるか(1)、1分あたりで考えるか(2)はどちらでも良い。
(3)は単位に注意。

待ち行列理論に出てくる概念（用語）を整理

こちらより引用（というかここを読んだほうが早いな…）。

μ：平均サービス率(単位時間あたりサービス件数の平均値)
Ts：平均サービス時間(= 1/μ)
λ：平均到着率(単位時間に到着する客の人数の平均値)
Ta：平均到着時間(= 1/λ)
ρ：サービス利用率（単位時間あたりのサービスを受ける客の人数に対する、単位時間あたりに到着する客の人数）の比」）定義より ρ＝λ／μ ＝ Ts / Ta
Tw：待ち時間の平均
Lw：待ち行列の長さ

なお、Tw（待ち時間の平均：平均待ち時間）は「Lw * Ts」で求められる。
Lw=ρ/(1-ρ) は、待ち人数と考えたほうが直感的ではないかと思う。
Ts は1人当りの待ち時間と考える。

そう考えると、

Tw(例えば、病院に行った時に待たなければ行けない時間)
　= Lw(先に待ってる人の数)
　* Ts(1人あたりの診察時間)

だと直感的ではないだろうか。

これに加えて、情報処理技術者試験では

平均応答時間（Tr(Tresponse)？ここから）

が出てくる。簡単に言うと待ち時間(Tw)＋処理時間(Ts)。
病院に例えると、自分が呼ばれるまで待って、呼ばれて、診察を終えるまでの時間。

記号の読み方メモ。

λ: ラムダ
μ: ミュー
ρ: ロー

個人的に覚えておけばいいと思う公式

ρ（平均利用率(サービス利用率、混み具合などの表記も見かける)）: ρ=λ/μ

Lw（待ち行列の長さ(何人待っているか、が直感的と思う)）: Lw=ρ/(1-ρ)

Tr（平均応答時間(待ち時間＋処理時間)）: Tr=1/(1-ρ) * Ts

Lwは理屈は分からない（なぜ ρ/(1-ρ) となる？）けど至るところで見るので間違ってはないと思う。
Trはいろいろ読んだ結果こう覚えといた方が良さそうと個人的に考えたことなので間違ってるかも…。

予想問題集の問題を解いてみる

9/23 追記：使ってるのはこれの2010年度版

2012 システムアーキテクト予想問題集 (予想問題シリーズ) (情報処理技術者試験対策書)

posted with ヨメレバ

アイテック情報技術教育研究部アイテック 2012-05-14

あるシステムのサーバには,1分間に平均6件のトランザクション処理要求がある。そして,トランザクション1件当たりの処理時間は平均6秒である。処理要求とサーバの処理時間がM/M/1の待ち行列モデルに従うとき,平均応答時間は何秒か。

平均応答時間(ここではTrと定義)を求めるので 1/(1-ρ) * Ts
ρはλ/μなので、先にλとμを求める
λは「1分間に平均6件のトランザクション処理要求」によりλ=6
μは「1件当たりの処理時間は平均6秒」から求める。これは平均サービス時間(Ts)なので、平均サービス率に変換する。60秒/6秒=10件(1分あたり)。μ=10
ρは6/10なので、ρ=0.6
ようやくTrを求める。1/(1-0.6) * Ts(1件当たりの処理時間は平均6秒) = 1/0.4 * 6 = 15

答えは 15 秒。

チケット売場の窓口の待ち時間が長くなったというユーザからの苦情を受けて,実際の状況を調べたところ,昨年の同時期に比べ平均待ち時間が6倍になっていることが分かった。昨年の窓口利用率は0.2であったが,今年はおよそ幾つになっているか。客の到着や処理は, M/M/1待ち行列モデルに従うものとし,客一人に対するサービス時間は昨年と変わらないものとする。