待ち行列理論とは?待ち行列モデル(M/M/1)、平均待ち時間を計算する方法についてまとめました。
【待ち行列理論】待ち行列モデル(M/M/1)、平均待ち時間
| 項目 | 概要 |
|---|---|
| 待ち行列モデル | 銀行のATMに並ぶ顧客の列、レジに並ぶ顧客の列などのように順番待ちの行列を確率モデル化したもの(情報処理ではトランザクションがサーバ処理を待つケースなど)。ステムの性能評価の1つとして待ち行列モデルを用いて「待ち時M/M/1|到着分布／サービス時間分布／窓口の数の組合せでモデルを表現すること。「M」はMarkovianの略で到着がポアソン分布となるランダム型、到着間隔は指数分布に従うことを表す。 |
| 平均待ち時間 | 処理待ち行列に並んでからサービス(処理)が開始されるまでの待ち時間の平均。M/M/1の待ち行列モデルでは、平均待ち時間は「(利用率/(1-利用率))×サービス平均時間」で計算できます。 |
【例題】応用情報技術者試験 平成30年秋期 午前問2
コンピュータによる伝票処理システムがある。このシステムは，伝票データをためる待ち行列をもち，M/M/1の待ち行列モデルが適用できるものとする。平均待ち時間がT秒以上となるのは，処理装置の利用率が少なくとも何%以上となったときか。ここで，伝票データをためる待ち行列の特徴は次のとおりである。
伝票データは，ポアソン分布に従って到着する。
伝票データをためる数に制限はない。
1件の伝票データの処理時間は，平均T秒の指数分布に従う。
【解答】
「1件の伝票データの処理時間は，平均T秒の指数分布に従う。」とあり、平均サービス時間はT秒なので、
平均待ち時間={利用率／(1－利用率)}×平均サービス時間={利用率／(1－利用率)}×T
となる。
平均待ち時間がT秒以上となる利用率を求めたいので、
{利用率／(1－利用率)}×T > T となる条件は利用率が0.5以上である。
【応用数学】確率・統計、数値解析、数式処理、グラフ理論、待ち行列理論
確率・統計、数値解析、数式処理、グラフ理論、待ち行列理論についてまとめました。
algorithm.joho.info
2019.01.25
【情報処理入門】用語解説・資格試験対策まとめ
情報処理分野の用語・原理・資格試験対策について解説します。
algorithm.joho.info
2023.08.08
コメント