
・待ち行列理論の説明難しすぎ…。
・M/M/1って何なの?メガマック1つ?
・用語を一覧表示されてもよくわからない
今回の記事では、このような方にとって有用な記事になっています。似たような多くの用語も、「自然な流れで説明」「例の使用」をすることにより、スムーズな理解を図っています。
また、今回は簡単のため、M/M/1 モデルに絞り解説していきます。
M/M/1モデル とは
そもそも M/M/1 とは何なのでしょうか。これはケンドール記号というものに従った書き方になります。そして、 M/M/1 は簡単に言えば、
「ランダムに処理要求が来て(M)、処理に掛かる時間もランダムであり(M)、1台のサーバーで対応する」
という意味になります。ちなみに、M は Markovian(マルコフ過程) の M です。
利用率
「待ち行列理論の最大のキモは利用率」です。利用率を中心に各用語を確認していくことで、スムーズな理解が得られます。まずは、利用率とは何かを確認しましょう。
利用率とは
利用率をひとことで言えば、
単位時間にサーバー(窓口)を利用している割合
です。分かりやすいように言い換えれば、
- 「1時間に、窓口が何分間接客しているのか」
- 「1秒間に、何ミリ秒トランザクションを処理しているのか」
という風になります。イメージできましたでしょうか。そして、この利用率というのは待ち行列理論でよく使われる用語を用いて、2通りの求め方があります。例題を用いて順に確認していきましょう。
利用率の求め方1(公式1)
一つ目の求め方(公式)は
$利用率(ρ) = \dfrac{平均サービス時間}{平均到着間隔} = (\dfrac{1}{μ} ) \div ( \dfrac{1}{λ})$
というものです。先ほどの利用率の意味を理解していれば、これだけで大体理解できてしまっているのではないでしょうか。それでは、順に用語の意味を説明していきます。
※μ, λの意味は後程解説
平均サービス時間
1トランザクション(1人のお客さん)が「サービスを受けるのに掛かる平均時間」です。
例 1秒間に10個のトランザクションを処理可能な場合、
平均サービス時間=$\dfrac{1秒}{10}=100ミリ秒$
平均到着間隔
前のトランザクション(お客さん)から次のトランザクション(お客さん)が来るまでの時間です。
例 1秒間に20個のトランザクションが到着する場合、
平均到着間隔=$\dfrac{1秒}{20}=50ミリ秒$
利用率の求め方2(公式2)
二つ目の求め方(公式)は
$利用率(ρ) = \dfrac{平均到着率}{平均サービス率} = \dfrac{λ}{μ} $
です。先ほどの公式1と違い、「 ‘到着’ と ‘サービス’ が分母分子逆」になっているのに注意してください。それでは、順に用語の意味を見ていきましょう。
平均サービス率(μ)
単位時間当たりにサービス可能なトランザクション(お客さん)の数です。μ(ミュー)という記号が普通使われます。
例 1秒間に10個のトランザクションを処理可能な場合、
平均サービス率=$\dfrac{10個}{1分}=10個/分$
平均到着率(λ)
単位時間当たりに来るトランザクション(お客さん)の数です。λ(ラムダ)という記号が普通使われます。
例 1秒間に20個のトランザクションが到着する場合、
平均到着間隔=$\dfrac{20個}{1秒}=20個/秒$
利用率の利用
ここまでは準備です。今から説明する箇所が最も情報技術者試験で出題される範囲です。しっかり理解しておきましょう。
イメージは以下の通りです。
平均待ち時間
「サービスを受けている時間は除いた」待ち時間です。求め方の公式は以下の通りです。
$平均待ち時間=\dfrac{ρ}{1-ρ}\times 平均サービス時間$
この式の証明は待ち行列理論(M/M/1モデル)の定理とその証明をご覧ください。
平均応答時間(平均滞在時間)
「サービスを受けている時間を含む」待ち時間です。ようするに、平均待ち時間に、平均サービス時間を足し合わせればいいだけです。よって、求め方の公式は以下の通りです。
$平均応答時間=\dfrac{ρ}{1-ρ}\times 平均サービス時間$ $+ 平均サービス時間$
例題
では、例題を解いて理解を深めていきましょう!

応用情報技術者平成26年秋期 午前問3
解答までの道筋
今回求めないといけないのは利用率(ρ)ですね。
そして、平均待ち時間が T になるらしいので、平均待ち時間について立式すればとけそうです。平均待ち時間の公式は、
$平均待ち時間=\dfrac{ρ}{1-ρ}\times 平均サービス時間$
でした。では、平均待ち時間が T とわかっており、利用率ρは変数としてあつかいますので、あとは平均サービス時間が文章中に隠されているはずです。探してみましょう。
すると、最後の行に「1件の伝票データの処理時間は平均 T 秒」と書いてありますね!
計算
つまり、平均サービス時間も T 秒という訳です。これらの情報を元に立式すると…。
$\dfrac{ρ}{1-ρ}\times T \geqq T$
∴ $\dfrac{ρ}{1-ρ} \geqq 1$
∴ $ρ \geqq 1-ρ$
∴ $2ρ \geqq 1$
∴ $ρ \geqq 0.5$
つまり、利用率が 50% 以上となった時ですね!
よって、答えは イ です。
まとめ
では、最後にすべての公式を列挙しておきます。
$利用率(ρ) = \dfrac{平均サービス時間}{平均到着間隔} = (\dfrac{1}{μ} ) \div ( \dfrac{1}{λ})$
$利用率(ρ) = \dfrac{平均到着率}{平均サービス率} = \dfrac{λ}{μ} $
$平均待ち時間=\dfrac{ρ}{1-ρ}\times 平均サービス時間$
$平均応答時間=\dfrac{ρ}{1-ρ}\times 平均サービス時間$ $+ 平均サービス時間$
お疲れ様でした。
コメント
誤植だろうと思いますけど、答えは イ ですね。
ご指摘誠にありがとうございます。
誤っておりましたので、答え修正させていただきました。