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年 システム工学 到着・サービスの確率法則 / 到着客数の確率分布 • 2項分布の確率法則によ り,全時間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! mr m! t lim r lim 1 0 m m m r ! m m mr 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年 システム工学 到着・サービスの確率法則 / 到着客数の確率分布 • 客は1人ずつ来る(希少性を仮定) • 各人の到着時間間隔は確率法則に従う ▫ 到着時間間隔 T1,T2,T3, ….は互いに独立な確率変数で分布は同一 ▫ すぐ続く2人の到着時間間隔がt0以上であるから,t0時間間隔には1人 も到着しない 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年 システム工学 到着・サービスの確率法則 / サービス機構 • サービスの動作 サービス時間・・・・すべて同一の確率分布に従う独立な確率変数である システムの容量・・・単一窓口の容量は1,m個の窓口の場合はm 利用可能性・・・・・いつ利用可能か, 同時にサービスを受ける客の数をシステムの容量以下に する制約 • サービスに要する時間の長さ ▫ 一定サービス時間 ▫ 指数サービス時間 確率変数 T がサービス時間 サービス時間が区間Δt 内で終わる確率はどれほど長くサービスが続いているかと は独立に,微小時間区間に終わる確率は一定 ▫ 一般的独立サービス 一定サービス時間 4.12 PT t0 e t dt e t0 指数サービス時間 t0 PT 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 ES k ET1 T2 T3 Tn ETi 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:一般分布 サービス分布 • 待ち行列システムのモデル 到着分布 1 2 行列の長さ システム中の客の数 S 15 2015年 システム工学 A. 単一窓口待ち行列 / M/M/1(1) A ▫ 到着率:λ ▫ サービス率:μ B • 状態Aにある確率PA(t),Bにある確率PB(t) • 待ち行列過程の基本方程式 PA t t 1 t PA t tPB t o t ▫ Δtの間に客が到着して 状態A⇒状態B⇒状態A と戻る確率は無視できる 確率でしか起こらない. 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 • 遷移確率図 A B 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 Pn1 Pn1 Pn Pn 1 n0 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 ▫ ▫ ▫ ▫ ▫ 既にk人が行列を作って待っている 今来た客が自分のサービスを受けるまでの時間を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 ▫ 市役所の窓口 住民の到着する時間間隔は平均5分のポアソン分布 手続き平均時間の平均は4分 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 ▫ ある駅の窓口 平均2分間に1人の割合のポアソン分布で乗客が到着する 1分間に2人の切符を指数分布で発売する 1 0.5, 2, 0.25 1 2 (1) 窓口に来た客が待たないで済む確率 1 P0 1 0.75 (2) 待ち行列の平均の長さ 2 0 .5 2 1 2 L q (3) システムなかの乗客数の平均 22 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 ▫ 機械の故障が1時間に平均3台の割合でポアッソン分布に従って起こる 応募者 A B 修復率μa: 1時間に平均5台を修復する,5000円/時間を要求 修復率μb:1時間に平均4台を修復する,4000円/時間を要求 会社にとって10000円の損失になる ▫ Aの場合 3 3 A 5 3 2 3 S A 10000 5000 20000 2 ▫ Bの場合 3 3 B 4 3 1 3 S B 10000 4000 34000 1 LA LB 24 2015年 システム工学 C. 単一窓口待ち行列 / M/M/1(N) • 待ち行列に制限がある,即ちN人までしか入れない P0 P1 P P P , n 1 n n 1 PN 1 PN N Pn 1 n 0 ▫ Aの場合は,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μ円 車1台当りの利益はB円 駐車場には積載中の車を 含めてN台のみ 図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 個並列にある場合 窓口が1つの場合と異なるのは,nという状態からn-1の状態に移行する割合がμでなく, n≦sの場合はnμ,n>sの場合はsμとなる 窓口が同時に終わる確率は無視できるので,全部ふさがっている場合はsμ,一部のn個が ふさがっている場合は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 sPn 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! ns 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 st 1 4.55 PT 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 ts 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 s0 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 n0 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 a1 E s a 4.63 4.64 31 2015年 システム工学 通信トラフィック理論/ M/G/1 現実のモデルでは,バッファサイズは有限である 実際のバッファ数は,N-s である • 状態方程式 • システムの構成法 ▫ システムに入ってきた呼を何もしないで棄却する ▫ 呼を発生する側のシステムに情報を与え,これからの呼の発生をブ ロックさせる
© Copyright 2025 ExpyDoc