【応用情報】M/M/1型の待ち行列の公式まとめ【過去問解説】

今回は、応用情報技術者試験でもよく出題される、M/M/1 型の待ち行列についてまとめてみようと思います。
※あくまで応用情報技術者試験レベルです。

待ち行列とは、私達が日常的に使っているスーパーやコンビニなどで、レジに並んでるとき(サービスを受けることを待っている状態)などが例に挙げられます。

この待ち行列の平均待ち時間・平均応答時間などを理論的に求める、
基本的な待ち行列理論が M/M/1 です。

待ち行列には公式があり、公式に数字を当てはめて時間を求めていきます。
公式は丸暗記するしかありませんが、公式さえ覚えれば計算自体は簡単です。

必要な公式
1.平均到着率(λ):単位時間当たりの到着件数
  例:10分当たり平均到着件数は60件
    λ = 6(分)  or  λ = 360(時間)

2.平均処理時間(ts):1件当たりの処理時間
  例:1件あたりの平均処理時間は5秒
    ts = 5(秒)  or  ts = 5/60(分)

3.利用率(ρ):窓口(レジ)が処理中である確率
  ρ = λ × ts
  例:1と2の数字を使います
    ρ = 6(分) × 5/60(分) = 0.5
    ※ ρ を求めるときは λ と ts の単位(時間)を揃える必要があります。

4.平均待ち時間:到着してから処理されるまでの時間
  平均待ち時間 = p / ( 1 - p ) × ts
  例:2と3の数字を使います
    平均待ち時間 = 0.5 / ( 1 - 0.5 ) × 5/60 = 5/60

5.平均応答時間:到着してから処理が終わるまでの時間
  平均応答時間 = 平均待ち時間 + ts
  例:2と4の数字を使います
    平均応答時間 = 5/60 + 5/60 = 1/6

他にも公式はありますが、とりあえずこの5つが頭に入っていれば大丈夫です。

では、実際に応用情報技術者試験の過去問を解いてみようと思います。
引用した問題は平成22春期の午後問4(一部抜粋)です。

Z社は,利用者が希望する映画のタイトル,あらすじ,上映館,上映期間などの映画情報を表示する情報提供サービスを行っており,平均待ち時間の目標値を40ミリ秒以下としている。
 Webサーバとデータベースサーバ(以下,DBサーバという)を一体のシステムとして,現在のシステムの状況を調査したところ,1分当たりのアクセス数は平均600件,1アクセス当たりの平均処理時間 Tp は40ミリ秒であった。

現在のZ社の情報提供システムについて,(1)~(4)に答えよ。ただし,(1)は,整数で答えよ。(2)~(4)は,小数第2位を四捨五入して小数第1位まで求めよ。

(1):平均到着時間間隔Tr(ミリ秒)を求めよ。
(2):利用率ρを求めよ。
(3):平均待ち時間Tw(ミリ秒)を求めよ。
(4):平均応答時間Ts(ミリ秒)を求めよ。

まず、λ と ts を求めます。
λ = 10(秒) ts = 40/1000(秒) = 0.04(秒) = 40(ミリ秒)

(1)平均到着時間間隔Tr(ミリ秒)
 λ = 10(秒) なので、1秒で10件到着します。
 なので 1秒/10件 = 0.1(秒) = 100(ミリ秒)

(2)利用率ρ
 公式を使います。
 ρ = λ × ts
 ρ = 10(秒) × 0.04(秒) = 0.4

(3)平均待ち時間Tw(ミリ秒)
 公式を使います。
 Tw = p / ( 1 - p ) × ts
 Tw = 0.4 / ( 1 - 0.4 ) × 40(ミリ秒) = 26.666… ≒ 26.7(ミリ秒)

(4)平均応答時間Ts(ミリ秒)
 公式を使います。
 Ts = Tw + ts
 Ts = 26.7(ミリ秒) + 40(ミリ秒) = 66.7(ミリ秒)

 実際に解いてみるとこのような感じになります。

応用情報技術者試験で出題される程度の問題であれば、公式を覚えれば必ず解けるので、良い得点源にしましょう。