待ち行列理論(M/M/1モデル)を例題を用いて徹底解説【公式付き】

システム構成要素
スポンサーリンク

 

・待ち行列理論の説明難しすぎ…。

・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

応用情報技術者平成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 平均サービス時間$ $+ 平均サービス時間$
 

お疲れ様でした。

コメント

タイトルとURLをコピーしました