【情報システム基礎論】シラバスへ

第17回講義内容へ

講義のツボメニューへ

問題解決１（待ち行列）

【日付 2001,11,28】 【連載回数 15 〜 16回】

待ち行列の説明

待ち行列とは同じ種類のデータを一列に並べたデータ構造で、人間の順番待ちと同様に、最初に格納したデータが最初に取り出されるというもので、このしくみを FIFO(先入れ先出し)と言います。

待ち行列の図


買い物やタクシー乗り場、駐車場や有料道路の料金所の例にも当てはめることができます。
ここでは銀行の預金・引出しの機械を例として考えます。

待ち行列の長さに影響を与える要因

●データ（お客さん）の到着間隔
　　○到着するデータ（お客さん）の間隔はどのような分布になるか
　　○データ（お客さん）は等間隔に来るのではない
●サービスの時間
　　○サービス時間はどのような分布になるのか
　　○サービスにかかる時間はお客さん
●窓口の数
　　○「サーバー数」といいます

といった要因が考えられます。

平衡状態と遷移確率

平衡状態kにある確率を$P$_kと書くと

$\lambda P$_k-1+μP_k+1=λP_k+μP_k=(λ+μ)P_k

ただし、$\lambda P$₀=μP₁

したがって、$P$_kの確率分布は以下の式より求まる。

$P$₁=λ/μP₀=ρP₀(λ/μ=ρ)

$P$_k=ρ^kP₀

ここで、ρ＜１であれば

$\Sigma$_k=0^∞P_k=Σ_k=0^∞ρ^kP₀=(1/1-ρ)P₀=1

したがって、$P$₀=1-ρより

$P$_k=ρ^k(1-ρ)
が成り立つ。

【情報システム基礎論】シラバスへ

第17回講義内容へ