kobadbadbadbadbad

モチベ維持

待ち行列1

待ち行列(Queuing Theory)

モチベ

輪講でやってるので、理解のためにもまとめておきましょ

LaTeX面倒すぎてLaTeXでしかかけなそうな所だけ使った。。。

待ち行列とは

待ち行列理論(まちぎょうれつりろん 英語: Queueing Theory)とは、顧客がサービスを受けるために行列に並ぶような確率的に挙動するシステムの混雑現象を数理モデルを用いて解析することを目的とした理論である。応用数学のオペレーションズ・リサーチにおける分野の一つに数えられる。 Wikipedia より

例: ) 病院、電話網、サーバやルータにおけるバッファ設計。

待ち行列のタイプ(モデル)

  1. 即時式
  2. 対応を即時に行う。(待ちができない) ex) 電話対応
  3. 機会損失(利益を出すチャンス)の大きさを推定して、いかにすくなくするか
  4. 待時式
  5. 利用者は待ってくれる。(待ちができる) ex) 病院の待ち列
  6. 待たせるコストと待たせなくするためにかかるコストのバランスを考える。


  1. 損失系
  2. 即時式では機会損失が起こるので、損失系のモデルになる。
  3. 非損失系

モデル作成において考えること

  • 待ち行列の要素
    • 客(人、モノ、情報、、、)
      • 母集団の大きさを見る(無限か有限か)
    • 到着の仕方
      • 定間隔 -> 対策しやすい
      • ランダム -> 到着状況はポアソン分布。到着間隔は指数分布。電話の呼び出しの場合はアーラン分布に従う。
      • 平均到着率 = λ
    • 窓口
      • 数 -> 待たせるコストと数を増やすコストを考えてベストな数を決める。
      • 質 -> すべての窓口が同じ質のサービスをするのか、そうでないのか
    • 時間
      • 客ごとの所要時間。このバラツキは指数分布かアーラン分布に従う。
      • 待ち行列では、平均サービス時間 μ (単位時間に何人にサービスするか)を利用する。
      • 1/μ = 平均サービス時間
    • 大きさ(待合室の大きさ)
    • 満員になって次に来た客が帰ってしまう -> 機会損失
    • 機会損失の大きさを評価する(損失系の場合)

ケンドール記号

モデル = 到着/サービス/窓口数(系の大きさ) とあらわす。

  • 到着、サービス
    • M -> ポアソンor指数分布
    • D -> 一定分布
    • Ek -> アーラン分布
    • G -> 一般分布
  • 窓口数
    • 数字
  • 系の大きさ
    • 待ち行列に並んでいる客とサービス中の客の合計
    • 無限大なら省略

何を求めるのか

保持してるデータ

λ: 平均到着率
μ: 平均サービス時間
ρ: 窓口利用率(ρ = λ/μ)

求める解

Pq: 待たされる確率
L: 系内にいる平均客数
Lq: 待ち行列の平均の長さ
Wq: 平均待ち時間

※ P -> Probability,q = Queue, L = Length, W = Wait

基本モデル

M/M/1 Model

ポアソン/指数/窓口1つ

Pq = ρ
L = ρ/1-ρ
Lq = ρ^2/1-ρ
Wq = ρ/μ(1-ρ)

M/M/1(N) Model

ポアソン/指数/窓口1つでN人しか入れない

Pq = 1 - P_0
L = (ρ-(N+1)ρ^(N+1) + Nρ^(N+2) / (1-ρ)^2 ) * P_0
Lq = (ρ^2 - Nρ^(N+1) + (N-1)ρ^(N+2) / (1-ρ)^2 ) * P_0

M/M/S

M/M/1の窓口が複数になった場合。窓口数 = S

{ \displaystyle
b_n = \sum_{m=0}^{N-1} a_m
}

{ \displaystyle
\rho = \frac{\lambda}{S\mu}
}

 { \displaystyle
P_0 = \frac{1}{\sum_{n=0}^{S-1} \frac{1}{n!}\frac{\lambda ^ n}{\mu ^ n} + \frac{1}{S!}\frac{\lambda ^ S}{\mu ^ S}\frac{S\mu}{S\mu-\lambda}}
}

 { \displaystyle
P_q = \frac{\frac{\lambda ^ S}{\mu ^ S}P_0}{S!(1-\frac{\lambda}{\mu S})}
}

 { \displaystyle
L_q = \frac{\lambda \mu \frac{\lambda ^ S}{\mu ^ S}}{(S-1)!(S \mu - \lambda) ^ 2}P_0
}

 { \displaystyle
L = L_q + \frac{\lambda}{\mu}
}

 { \displaystyle
Wq = \frac{\mu \frac{\lambda ^ S}{\mu ^ S}}{(S-1)!(S \mu - \lambda) ^ 2}P_0
}

  • 変動係数 -> どんな分布でも共通に使える
  • 変動係数 = 標準偏差/平均値

ヒラポン・ポラチェックの公式

λ: 平均到着率
μ: 平均サービス時間
ρ: 窓口利用率(ρ = λ/μ)
Pq: 待たされる確率
L: 系内にいる平均客数
Lq: 待ち行列の平均の長さ
Wq: 平均待ち時間
C: サービス時間の変動係数
ρ: 窓口利用率(λ/μ)
T_s: 平均サービス時間(1/μ)
W_q: 平均待ち時間

のとき

W_q = (ρ/2(1-ρ)) * T_s(1_C^2)

平均値の法則の拡大

Pq = ρ
W: 系内にいる平均時間
L = λW

M/G/1 Model

W_q = (ρ/2(1-ρ)) * 1/μ(1_C^2)
Lq = λW_q
L = λ(W_q+1/μ)

M/D/1 Model

W_q = ρ/2μ(1-ρ)
Lq = λW_q
L = λ(W_q+1/μ)

M/Ek/1 Model

Ek: 位相kのアーラン分布のこと
k = 1: 指数分布
k = ∞: 一定分布
平均: 1/μ
分散: 1/(kμ^2)
C^2 = 1/k

W_q = ρ/2(1-ρ) 1/μ (1+1/k)
Lq = λW_q
L = λ(W_q+1/μ).

即時式モデル


応用例

自動券売機の行列と銀行の行列の比較

自動券売機

  • 1台ごとに行列ができる
  • 前にいる人のサービス時間に左右される。列によって速さが違う。

銀行

  • 行列は1列だけで、空いた窓口に順に入れていく。
  • 前にいる人に左右されるが、それは全員同じく影響される。

モデル作成

どちらも窓口4つで単位時間を10分と仮定。 待たされる確率(Pq)で評価、比較する。

自動券売機

窓口ごとに行列ができるので各窓口間に関連性はないため、 M/M/1モデルが4つ並んでいると見れる。

Pq = ρ
L = ρ/1-ρ
Lq = ρ^2/1-ρ
Wq = ρ/μ(1-ρ)

より

平均到着率(λ) = 8(人/10分)
平均サービス率(μ) = 10(人/10分)
窓口利用率(ρ) = λ/μ = 0.8
-> 待たされる確立(Pq) = ρ = 0.8

銀行

M/M/4モデル。

窓口数(S) = 4
平均到着率(λ) = 8*4 = 32(人/10分)
平均サービス率(μ) = 10(人/10分)
窓口利用率(ρ) = λ/μ = 0.8
P_0 =
P_q =  

より

P_0 = 75/2747
P_q = 0.6

窓口1~4を計算すると以下のようになる。

窓口数 到着率 サービス率 待たされる確率
1 8 10 0.8
2 16 10 0.71
3 24 10 0.65
4 32 10 0.6

結果

自動券売機 -> 0.8 銀行 -> 0.6

となり、銀行の待ち行列の作り方のほうが25%効率が良いことがわかる。

ほかにも公衆電話の予備機の問題(予備品在庫の問題)にも適用される