システムと待ち行列の理論

1
2015年システム工学
システムと待ち行列の理論
1. システムと待ち行列
▫ 渋滞問題
▫ 高トラフィック設計
2. 到着・サービスの確率法則
1. 定間隔到着
2. ランダム到着
3. 一般的独立到着
4. サービス機構
5. 指数分布とアーラン分布
3. 単一窓口と待ち行列

M/M/1(1)

M/M/1

M/M/1(N)
4. 複数窓口の待ち行列
1.
M/M/s
2.
トラフィックモデル
2
2015年システム工学
情報処理システムと待ち行列
• OSとTask処理 / プロセス管理
task
task
task
task
task
CPU
• 通信の転送バッファ
msg
msg
msg
msg
network
msg
msg
msg
msg
3
2015年システム工学
システムと待ち行列 / 渋滞問題
• システムの共通概念
▫ サービスを要求する客(customer)の流れ
 単一窓口待ち行列(single server queue)
 複数窓口待ち行列(many server queue)
▫ サービスにある制約
 同時に一定数以下の客しかサービスを受けられない
 順番を待つ・・・・渋滞(congestion)が発生する
• 渋滞を記述する方法
▫ 到着の型
▫ サービス機構
▫ 待ち行列の規則
4
2015年システム工学
システムと待ち行列 / 高トラフィック設計
1.
2.
3.
4.
システム研究
システム設計
資料の蒐集
システム解析
▫
▫
▫
5.
6.
7.
直接的実験（要因分析法，等）
数学的解析
シミュレーション
最適システムの選定
試作
実施
5
2015年システム工学
システムと待ち行列 /
高トラフィック設計 / システム規定要因
• 到着の型
▫
▫
▫
▫
全体の平均到着率を改善
定間隔到着，時刻指定制などによる到着時刻の制御
全期間を通じた到着率の平均化
待ち行列に対する客の意志の反映
• サービスの機構
▫
▫
▫
▫
平均サービス時間の変更
サービス時間の一定化
システムの容量の変化
窓口の利用可能性を上げる
• 待ち行列の規則
▫ 先取りの優先権
▫ 長い待ち行列が起こる確率を小さくする
▫ 複数窓口の場合の特別窓口の設置
6
2015年システム工学
到着・サービスの確率法則
• 定間隔到着
▫ 到着率 α=1/a,
a:時間間隔
• ランダム到着
▫ 定常性
 一人が到着する確率 αΔt
 一人も到着しない確率
1 - αΔt + o(Δt)
▫ 希少性
 二人またはそれ以上の客が到着する確率
o(Δt)
▫ 残留効果なし
 時間区間(t, t+Δt)で起こることは，この区間と重ならない任意の時間
内で，客が到着するかしない確率は，統計的に独立
7
2015年システム工学
note: ランダウの記号(small o – omicron”ο”)
• 無限大における漸近挙動
▫ あるサイズ n の問題を解くのに掛かる時間あるいは手順数
T(n) = 4n2 - 2n + 2
• 無限小における漸近挙動
▫ ex − (1 + x + x2/2) という差（誤差）の絶対値が 0 の近くの x については
|x|3 の適当な定数倍よりも小さいということを意味する
• 定義
▫ f(x) と g(x) は実数からなるある集合上で定義されているとするとき、
「f(x) が x → ∞ のとき O(g(x)) 程度である」
▫ g(x) が a の十分近くで 0 にならないならこれらの定義を上限値を使って
統一的に記述できる。つまり「f(x) が x → a のとき O(g(x) の程度であ
る」とは
8
2015年システム工学
到着・サービスの確率法則 / 到着客数の確率分布
• ２項分布の確率法則によ
り，全時間t0を通じてちょ
うどr人の客が到着する確
率
m!
r
m r

t  o t  1   t  o t 
 t  0 r! m  r !
w r t 0   lim
r
t  t 
m!
 r o r 1  0 
 lim
m   r! m  r !
m 
m 


• 時間t0内の到着数をXとす
る，これは確率変数であ
る
t 0 r
r!
t 0 r
r!
mr
m!
 t 
lim r
lim 1  0 
m   m m  r ! m  
m 

mr
4.1
e  t 0
w r t 0   P  X  r  
 t 0 r
r!
e  t 0
r  1,2,3,...
4 . 2 
9
2015年システム工学
到着・サービスの確率法則 / 到着客数の確率分布
• 客は１人ずつ来る（希少性を仮定）
• 各人の到着時間間隔は確率法則に従う
▫ 到着時間間隔 T1,T2,T3, ….は互いに独立な確率変数で分布は同一
▫ すぐ続く２人の到着時間間隔がt0以上であるから，t0時間間隔には１人
も到着しない
P T  t 0   w0 t 0   e t
P T  t 0   1  e t
0
0
4.3
4.4
▫ ある時間間隔に到着する客数がポアソン分布（指数分布）に従うことと，
到着時間間隔が指数分布に従うこととは，同等である
10
2015年システム工学
到着・サービスの確率法則 / 到着客数の確率分布
• ポアソン分布の平均と分散

E  X    rw r t 0    t 0
4.5 
r 0
   E  X    r
V X   E X
2

2
2
w r t 0    t 0    t 0
2
4.6 
r 0
• ランダム到着の場合の相続く客の到着時間間隔Tは指数分布である
P t  T  t  dt    e  t dt

1
0

E T     e  t dt 
 

E T 2    t 2 e t dt 
0
 
4.8
2

V T   E T 2  E T  
2
4.7 
4.9
2
1

2
4.10
11
2015年システム工学
未来を知るために
• ある時刻にシステムが正常であるとき，その後 t 時間内に故障を起こす
確率は，今までどのくらい正常であったかということことに無関係
• ある時刻に正常なシステムは，その時刻から s 時間前から運用を始めた
として，その後 t 時間後に故障を起こす確率は，運用後 s+t 以下である
条件付確率である
P T  s  t | s  T  
P s  T  s  t  P T  s  t   P T  s 

P s  T 
P s  T 

1 e

  s  t 
 1  e   1  e
 s
e  s
• これは， s に無関係であることを示している
 t
4.11
12
2015年システム工学
到着・サービスの確率法則 / サービス機構
• サービスの動作



サービス時間・・・・すべて同一の確率分布に従う独立な確率変数である
システムの容量・・・単一窓口の容量は１，ｍ個の窓口の場合はｍ
利用可能性・・・・・いつ利用可能か，
同時にサービスを受ける客の数をシステムの容量以下に
する制約
• サービスに要する時間の長さ
▫ 一定サービス時間
▫ 指数サービス時間
 確率変数 T がサービス時間
 サービス時間が区間Δt 内で終わる確率はどれほど長くサービスが続いているかと
は独立に，微小時間区間に終わる確率は一定
▫ 一般的独立サービス

 一定サービス時間
4.12
PT  t0    e t dt  e t0
 指数サービス時間
t0

PT  t0  t | T  t0   1  e t
4.13
13
2015年システム工学
指数分布とアーラン分布
• ランダム到着の場合，相続く客の到着時間間隔 T が指数分布に従う
P t  T  t  dt    e  t dt
• 到着時間，サービス時間が指数分布とは思えない場合が多い
確率密度関数は t=0 で最大
• t=o では小さく，t=a>0 付近で最大になる分布が現実には多い
現実に近く，理論的に複雑にならない分布=アーラン分布が考えられた
• k=1 で指数分布
kを増すと平均は変わらな
いが，分散は次第に減少
するとがった分布
 k k t k 1 k  t
e

g t    k  1!
0

t  0
4.15
t  0
k
ES k   ET1  T2  T3    Tn    ETi   k 
t 1
k
V S k   V Si   k 
i 1
1
k 
2
2

1
k
2
1
1

k 
4.17
4.16
14
2015年システム工学
A. 単一窓口待ち行列 / M/M/1(1)
• 特徴 X/Y/s (Kendallの記号)
▫ X:到着分布
▫ Y:サービス分布
▫ s:サービスステーション
M:指数分布 D:単位分布 E:アーラン分布 G:一般分布
サービス分布
• 待ち行列システムのモデル
到着分布
１
２
行列の長さ
システム中の客の数
Ｓ
15
2015年システム工学
A. 単一窓口待ち行列 / M/M/1(1)
Ａ
▫ 到着率：λ
▫ サービス率：μ
Ｂ
• 状態Ａにある確率PA(t)，Ｂにある確率PB(t)
• 待ち行列過程の基本方程式
 PA t  t   1   t PA t   tPB t   o t 
▫ Δtの間に客が到着して
状態Ａ⇒状態Ｂ⇒状態Ａ
と戻る確率は無視できる
確率でしか起こらない．

 PB t  t   1   t PB t   tPA t   o t 
 dPA t 
 dt    PA t   PB t 

 dPB t 
4.19 
  PA t   PB t 

dt

 PA t   PB t   1


4.18
16
2015年システム工学
A. 単一窓口待ち行列 / M/M/1(1)
 t
• 遷移確率図
Ａ
Ｂ
1   t
• 平衡方程式
 t


    t
    t




P
t

1

e

P
0
e
A
A




 P t    1  e    t  P 0 e     t
B
 B

• 定常状態
PA  PB

 PA  PB  1
1   t
4.22




4.20 
t   , e     t  0






P

P


lim
P
t

A
A
 A
t 



 P  P    lim P t   
B
B
t 
 B

4.21
17
2015年システム工学
B. 単一窓口待ち行列 / M/M/1
• 客が到着したとき，
▫ 先客がサービス中の場合は，行列を作って待つ
▫ 窓口が空くと直ちに行列の先頭の客がサービスを受け始める
• ポアソン分布，指数分布サービスの下で扱う
• 待ち行列の状態
▫ 待ち行列過程で状態n：システム中の客=行列で待っている客+サービス中の客
• 方程式
λ
0
λ
λ
1
μ
λ
n-1
μ
μ
λ
n
μ
λ
n+1
μ
μ
18
2015年システム工学
B. 単一窓口待ち行列 / M/M/1

P0

n  1,   P0  P2     P1
P1 
• 連立方程式
2

P2    P0   2 P0

n  2,
• 利用率
• トラフィック密度
• 入量率

P  P
1
 0
Pn1  Pn1     Pn

 Pn  1
n0
 P1  P3     P2
3
n  1,2,3.
4.24

P3    P0   3 P0


n

Pn    P0   n P0

4.28
19
2015年システム工学
B. 単一窓口待ち行列 / M/M/1
平衡状態例4.3
• 例4.3
▫
▫
▫
▫
▫
既にｋ人が行列を作って待っている
今来た客が自分のサービスを受けるまでの時間をTk
この客が来てから r 番目の客が窓口を去る時間τrとおく
確率変数は互いに独立で，平均1/μの指数分布に従っている
k人が窓口に並んでいるところに来た客は，k+1人が窓口を去れば，自分がサービ
スを受ける
Tk  X 1  X 2    X k 1
k 1
E Tk    E  X i  
i 1
k 1



k 0
k 0
W q   Pk 1  E Tk     k 1 P0
k 1





1
1
 P0  k  1 k  P0


L q 4.36 
 k 0
 1   2  1    
20
2015年システム工学
B. 単一窓口待ち行列 / M/M/1
例4.4, 4.5
• 例4.4
▫ 順番が来るまで行列に並んで待っている待ち時間をT
▫ サービス時間をS
1
W  E T  S   E T   E S   W q 
▫ システムのなかで費やされる

全時間の平均W

1
1
1

• 例4.5
▫ 窓口に到着した客が自分のサー
ビスを受けるまで t 時間より多く
待たされる確率P(T>t)
▫ 自分がサービスを受けるまでの
待ち時間Tk
▫ Tkがt以上になる確率は時間t の
間に多くともk-1人がサービスを
受け終わる確率に等しい
 1  




 1  




k 1
k 1
k 1
r 0

P T  t    p k P Tk  t    p k  e
 P1e
 t

k 1
 P1e
 t


r 0

k 1
 t  r
r 0
r!
 
k 1
L
 t
 P1e
  t r
r!
 t

  t r
r 0
r!



k 1 r
 t r
r
1


P1 e   t e   t
r! 1   1  
 1    1   t
e
 e 1   t
1 
4.38
k 1
21
2015年システム工学
B. 単一窓口待ち行列 / M/M/1
例4.6
• 例4.6
▫ 市役所の窓口
 住民の到着する時間間隔は平均５分のポアソン分布
 手続き平均時間の平均は４分
 4
1
1
 0.2,    0.25,     1
 5
5
4
 4



1

1

P

  0.8
0
(1) 住民が待たされる確率
 5
(2) 事務手続きのために

0.2


2
L


4
市役所に居る住民の
   0.25  0.2

平均の数
(3) 平均待ち時間
2

0.2
3 Wq  Lq  


 16

           0.25(0.25  0.2)
1
1
22
2015年システム工学
B. 単一窓口待ち行列 / M/M/1
例4.7
• 例4.7
▫ ある駅の窓口
 平均２分間に１人の割合のポアソン分布で乗客が到着する
 １分間に２人の切符を指数分布で発売する

1
   0.5,   2,
 0.25  1

2
(1) 窓口に来た客が待たないで済む確率 1 P0  1    0.75
(2) 待ち行列の平均の長さ
2
0 .5 2
1


2
L



q
(3) システムなかの乗客数の平均
     22  0.5 12
(4) 乗客の平均待ち時間
3 L    0.5  1
   2  0 .5 3
4  W q 1 Lq 

1 1 1
 
0.5 12 6
23
2015年システム工学
B. 単一窓口待ち行列 / M/M/1
例4.8
• 例4.8
▫ 機械の故障が１時間に平均３台の割合でポアッソン分布に従って起こる
 応募者
 Ａ
 Ｂ
修復率μa: １時間に平均５台を修復する，５０００円/時間を要求
修復率μb:１時間に平均４台を修復する，４０００円/時間を要求
 会社にとって10000円の損失になる
▫ Ａの場合

3
3


A   5  3 2
3
S A   10000  5000  20000
2
▫ Ｂの場合

3
3


B   4  3 1
3
S B   10000  4000  34000
1
LA 
LB 
24
2015年システム工学
C. 単一窓口待ち行列 / M/M/1(N)
• 待ち行列に制限がある，即ちＮ人までしか入れない
P0  P1
P  P     P ,
n 1
n
 n 1
PN 1  PN
N
 Pn  1
 n  0
▫ Ａの場合は，N=1
▫ Bの場合は，N=∞
▫ n=Nの場合に修正が必要
Pn 
1 
1 
N 1
 n,
n  0,1,2, , N 
1   N  1 N  N  N 1
L
1    1   N 1

   N  1  N 1 1     2  N  2   2 N  3
2
VL 
Lq
4.41

2
1    1  
N 1
  N  1 N
2 1  N

1   1   N 1 
2

N 1 2
4.42 
4.43
n  1,2,, N  1
4.39 
25
2015年システム工学
C. 単一窓口待ち行列 / M/M/1(N) 例4.9
•例4.9
▫出荷所






車は単位時間当たりλ台で
ポアソン到着
積荷時間は平均1/μの
指数分布
積荷のための単位時間
当たりの経費はAμ円
車１台当りの利益はB円
駐車場には積載中の車を
含めてＮ台のみ
図4.6を参照
1 
1  N
N
 
1  PN  1 
1   N 1
1   N 1
B 1   N 
B 1  PN  
1   N 1
 N 1  N 
1  N
C  B
 A  B N 1
 A
N 1
N 1
 
1 
dC
N N 1  N  1 N  N 1
N 1
 B
A
2


2
N

1
N

1
d

1   
N 1
A
N 1 N   N  1  
 
B
1   N 1 2
4.45
4.44 
26
2015年システム工学
通信トラフィック理論/ M/M/s(N)
サービス速度が，どれでも同じような窓口が s 個並列にある場合
窓口が１つの場合と異なるのは，nという状態からn-1の状態に移行する割合がμでなく，
n≦sの場合はｎμ，ｎ＞sの場合はsμとなる
窓口が同時に終わる確率は無視できるので，全部ふさがっている場合はsμ，一部のn個が
ふさがっている場合はｎμの割合で，どれか一つのサービスが終わる
λ
0
λ
1
μ
λ
λ
s-1
2μ
(s-1)μ sμ
λ
s
λ
s+1
sμ
sμ
27
2015年システム工学
通信トラフィック理論/ M/M/s(N)
サービス速度が，どれでも同じような窓口が s 個並列にある場合
• 状態方程式
 P0   P1

 Pn 1  n  1 Pn 1    n  P n
 P n 1  sPn 1    s  Pn

 Pn  1
 n  0
a
n  1,2,  , s  1
n  s , s  1, 
4.46 


, 

s
an
eq 4.46   P1  aP0 ,  , P n 
P0 n  0,1,2,  , s  1 4.47 
n!
an
ss  n
n  s; Pn 
P0 
P0 n  s, s  1,  4.48
s! s n  s
s!

 s 1 a n

as
4.49 
  Pn  1   1, P0  1  

n 0
 n  0 n! s  1!s  a 
28
2015年システム工学
通信トラフィック理論/ M/M/s
システムの中の客数の平均L，行列の名がsの平均Lq，待ち時間の平均Wq，
システムの中で費やされる全時間の平均W，窓口が全てふさがっている確率Pc，
t 時間より多く待たされる確率P
L  L q a
4.50
  as
Lq 
P
2 0
s  1!s   
1
4.52
W  Wq 

4.51
 as
1
Wq 
P

Lq
2 0

s  1!s   
s s P0
Pc   Pn 
s!
ns

P T  t  
4.53
 P0 a s
s s P0  s
 






s  1!s   
s
!
1

n s

n
1
Ps e 1  s  t  Pc e  1   st
1   
4.55
 PT  0
4.54
29
2015年システム工学
B. トラフィックモデル
•
•
•
•
•
呼：接続要求（客）
保留時間：呼の継続時間（サービス時間）
トラフィック T(t,s)：時間(t, t+s)における総保留時間
同時接続数 N(t)：ある時刻に接続中の呼数
トラフィック密度(呼量)
T t , s   
t s
t
N  x dx
4.56 
1
1 ts
4.57 
a t , s   T t , s    N  x dx
t
s
s
1 t s
a t   lim a t , s   lim  N  x dx  N t 
s0
s 0 s t
4.58 / 59 
30
2015年システム工学
呼損失
• 呼損失 M/M/1(1) 式(4.21)
• アーランの損失率 / アーランB式 M/M/s
• アーランの待ち合せ式 /アーランC式
as
Ps 
s!
an
 n !  E s a 
n0
s
aE s a 
E s 1 a  
s  1  aE s a 


 a  


4.61
E 0 a   1 4.62
 as
C s, a  
P0  Pc
s  1!s   
sE s a 
C s, a  
s  a1  E s a 
4.63
4.64 
31
2015年システム工学
通信トラフィック理論/ M/G/1
現実のモデルでは，バッファサイズは有限である
実際のバッファ数は，N-s である
• 状態方程式
• システムの構成法
▫ システムに入ってきた呼を何もしないで棄却する
▫ 呼を発生する側のシステムに情報を与え，これからの呼の発生をブ
ロックさせる

Download Report