待ち行列理論は、理解できていなくても合格できます。(午前問題の一問が解けるどうかくらいの影響しかない)
従い、気が向いたら読む程度にしておいてください。
大抵の「応用情報技術者試験」の本にも載っているのですが、どの本にも「公式を覚えろ」としか書いてありません。
そんな内容でわかった気になれるはずもなく、少し考えて見ました。
以下に自分なりに理解した内容を整理しておきます。
あるサービスにおいて、サービスの処理時間の平均を「平均サービス時間」、サービスの来客の間隔時間の平均を「平均到着間隔」とし、利用率ρを以下の様に定義する。
すると、平均の待ち行列の長さは以下の式で表すことができる。
ここでは、 M/M/1のケースを考えます。
ざっくり言うと
「来客のタイミングはランダムで(M)、サービスの処理時間もランダムで(M)、サービスの窓口は1つ」
ということです。
例えば病院で、「平均診察時間が3分で、患者さんの平均来院間隔が10分」の場合の平均待ち時間を考えてみましょう。
「次の患者さんが来るまでに平均の空き時間が7分あるから、患者さんの待ち時間が発生することなんてないのではないか?」
と思う人もいるでしょう。
しかし、実際には平均の待ち時間は発生します。
ベルトコンベアなどで一定間隔で流れて来る工場などとは違います。
・時には患者さんが診察している間に、別の患者さんが来ることもあります。
・一方、患者さんが来ない場合もあります。しかし、それでも医師が暇になるだけですね。
次に来た患者さんは待ち時間なしで診察を受けられますが、それでも待ち時間は0です。
「患者は待つこともあるが、待つことなく診察を受けられる場合もある」ということです。当たり前ですね。
以下は実例です。
①利用率ρについて直感的に理解する
「平均処理時間を平均到着間隔で割ったもの」が利用率で、ρ(ロー)で表現されます。
「平均すると10分おきに新しい患者が来て、一人の診察に7分かかる」場合の利用率は70%です。
「行って見たら誰かが『診察中』である確率」というようなイメージです。
②n人待ちである確率を考えてみる
例えば、「2人待ち」なのは、
「1人目が待っている」「さらにもう1人待っている」「その後は来ない」
なので、ρ x ρ x (1-ρ)になります。
「n人待ちである」ということは、「前の診療中にn人がやってきた」かつ「n+1人目以降は来ない」なので、
確率は以下の通りになります。
ツリーにしてみますね。この方が理解しやすい人も多いかもしれないので。
③待ち行列の平均の長さを求めてみよう
待ち行列の平均の長さを求めるには、上で求めた「待ち人数がn人である確率」に「待ち人数:n」をかけて、nを1~∞まで合計すれば良いのです。
となります。
平均待ち時間は、この行列の長さに平均診察時間をかければ、計算できます。
最後の式が直感的にわからないかもしれないので説明しておきます。
つまり
が成り立つことを示します。
Σの項を見てみましょう。決まったパターンが無限に繰り返してます。
こういった決まったパターンが無限に繰り返すものを単純にするときによく用いられるのが、「”それ自身”から”繰り返し分ずらしたそれ自身”を引くことで、無限部分を消し込む」方法です。
無限少数を分数で表現するときによく使いますね。
今回は、それの数列バージョンです。Σの項に(1ーρ)を二回かけることで、無限部分を消去します。
1.(1ーρ)をかける:一回目
Σ × (1-ρ) = Σ - ρΣ ですから、Σの項からρをかけたΣの項を引きます。
ですから
2.もう一度(1ーρ)をかける:二回目
上の結果にもう一度(1ーρ)をかけてみましょう。
「1.の結果」から「1の結果にρをかけたもの」を引きます。
無限部分が消えました。
これで「最初のシグマの項に(1 ーρ)を二回かけると、ρになる」こととなり、
最初の式が成り立っていることがわかると思います。
あなたもジンドゥーで無料ホームページを。 無料新規登録は https://jp.jimdo.com から