オペレーションズリサーチと
ゲーム理論 (3日目)
兵庫県立大学 円谷 友英
今日の対象：待ち行列(Queuing theory)
• はじめに・・・質問です
• 待つことは好きですか？
• 最近，あなたは
待ち
ましたか？
• どこかで？どんな場面で？ • なにを？何のために？ • どのように？ • なぜ待つことになりましたか？• 何かが
待っている
(と思われる)状態に気が付きましたか？
今日の対象：待ち行列(Queuing theory)
• 待つ場面
• トイレ，ATM，券売機 • レジ，レストラン，病院， USJ • チケット予約 • CPUの処理，パケット送信• 他の言い方
• トラヒック(理論) • 輻輳(ふくそう) • 大衆サービス • 確率的サービスシステム
• 入力されたら，処理して出力する
• 変換的定義• 全体統一的・円滑な流れ
• 滞らないようにする • 行列は短いほうがよい • 処理(変換)能力は無限ではない • 資源の有効活用 • 環境に左右される【今日の視点】
• 運用する
• 快適に利用し続ける
• 突発的事象への対応 • 処理(サービス)に目を向ける • 制御できること，制御できないこと• 現状を知る
• 次の一手を考える
システム 入力 出力システムの状態を待ちで考える「指標」は？
【今日の例題～単純な場合】 • 1分間に一律20アクセスある >>>到着 • 一律0.05分間隔でアクセスがある • サーバ1台 1. 処理時間は1アクセスあたり一律0.04分間 >>>サービス • 1分間に一律25アクセスを処理 2. 処理時間が0.02分間のアクセスと， 0.06分間のアクセスとが交互にある >>>サービス • 処理時間は1アクセスあたり平均0.04分 3. 処理時間が0.1分間のアクセスと，0.04分間のアクセスとが交互にある >>> サービス • 処理時間は1アクセスあたり平均0.07分1.一律0.04分間
客 到間 サ時 到着時刻 開始時刻 終了時刻 待ち時間 滞留時間 待ち客数 滞留客数 1 0.05 0.04 0.05 0.05 0.09 0.00 0.04 0 1 2 0.05 0.04 0.10 0.10 0.14 0.00 0.04 0 1 3 0.05 0.04 0.15 0.15 0.19 0.00 0.04 0 1 4 0.05 0.04 0.20 0.20 0.24 0.00 0.04 0 1 5 0.05 0.04 0.25 0.25 0.29 0.00 0.04 0 1 6 0.05 0.04 0.30 0.30 0.34 0.00 0.04 0 1 7 0.05 0.04 0.35 0.35 0.39 0.00 0.04 0 1 8 0.05 0.04 0.40 0.40 0.44 0.00 0.04 0 1 9 0.05 0.04 0.45 0.45 0.49 0.00 0.04 0 1 10 0.05 0.04 0.50 0.50 0.54 0.00 0.04 0 1 11 0.05 0.04 0.55 0.55 0.59 0.00 0.04 0 1 平均 0 0.04 0 1 0.00 0.01 0 12. 0.02分間と 0.06分間が交互
客 到間 サ時 到着時刻 開始時刻 終了時刻 待ち時間 滞留時間 待ち客数 滞留客数 1 0.05 0.06 0.05 0.05 0.11 0.00 0.06 0 1 2 0.05 0.02 0.10 0.11 0.13 0.01 0.03 1 2 3 0.05 0.06 0.15 0.15 0.21 0.00 0.06 0 1 4 0.05 0.02 0.20 0.21 0.23 0.01 0.03 1 2 5 0.05 0.06 0.25 0.25 0.31 0.00 0.06 0 1 6 0.05 0.02 0.30 0.31 0.33 0.01 0.03 1 2 7 0.05 0.06 0.35 0.35 0.41 0.00 0.06 0 1 8 0.05 0.02 0.40 0.41 0.43 0.01 0.03 1 2 9 0.05 0.06 0.45 0.45 0.51 0.00 0.06 0 1 10 0.05 0.02 0.50 0.51 0.53 0.01 0.03 1 2 11 0.05 0.06 0.55 0.55 0.61 0.00 0.06 0 1 平均 0.005 0.045 0.5 0.5 0.00 0.01 0 12. 0.1分間と0.04分間が交互
客 到間 サ時 到着時刻 開始時刻 終了時刻 待ち時間 滞留時間 待ち客数 滞留客数 1 0.05 0.1 0.05 0.05 0.15 0.00 0.10 0 1 2 0.05 0.04 0.10 0.15 0.19 0.05 0.09 1 2 3 0.05 0.1 0.15 0.19 0.29 0.04 0.14 1 2 4 0.05 0.04 0.20 0.29 0.33 0.09 0.13 1 2 5 0.05 0.1 0.25 0.33 0.43 0.08 0.18 2 3 6 0.05 0.04 0.30 0.43 0.47 0.13 0.17 2 3 7 0.05 0.1 0.35 0.47 0.57 0.12 0.22 2 3 8 0.05 0.04 0.40 0.57 0.61 0.17 0.21 3 4 9 0.05 0.1 0.45 0.61 0.71 0.16 0.26 3 4 10 0.05 0.04 0.50 0.71 0.75 0.21 0.25 3 4 11 0.05 0.1 0.55 0.75 0.85 0.20 0.30 4 5 平均 0.11 0.19 2 3 0.00 0.05 0.10 0.15 0.20 0.25 0 1 2 3 4今日の例題のまとめ1
「待ち」を考える指標 1.2.3比較
到時間 間隔 一律25 サービス 時間 終了 時刻 平均 待ち時間 平均 待ちアクセス数 1 0.05 0.04 0.59 0 0 2 0.05 0.02と0.06が 交互(0.04) 0.61 0.005 0.5 3 0.05 0.1と0.04が 交互(0.07) 0.85 0.11→増加 2→増加 0.00 0.01 0.00 0.01 0.00 0.05 0.10 0.15 0.20 0.25 0 1 0 1 0 1 2 3 4• こんなに規則正しいものだろうか･･･？
ランダムな到着 & ランダムなサービス
• ランダム，でたらめ・・・とは？
• 定常性：到着のしかたは時間に依存しない (どの時刻でも同じ) • 独立性：互いに影響を与えない (残留効果がない) • 希少性：同時に2人到着する確率は無視できるくらい小さい【今日の例題～少し現実的な場合】
• 1分間に平均20アクセスの
ランダム
なアクセスがある
>>>到着
• 平均0.05分間隔でアクセスがある• サーバ1台
4. 処理時間は1アクセスあたり一律0.04分間
5. 処理時間が0.02分間のアクセスと， 0.06分間のアクセスとが交互にある
• どうなることが予測できる？
0 時間 到時 サービス 終了時刻 待ち時間 待ち人数 1 0.05 0.04 0.59 0 0 2 0.05 0.02＆0.06 0.61 0.005 0.5(定常性)到着のしかたは時間に依存しない (独立性)残留効果がない (希少性)同時に2人到着しない
シミュレーション
M/M/1
(∞)
ポアソン到着 指数サービス 窓口1つ 指数分布に従うと仮定→指数乱数 (到着時間間隔) 平均0.05 (サービス時間) 平均0.04 0 時間【今日の例題～それらしい現況】
• 1分間に平均20アクセスの
ランダム
到着
• 平均0.05分間隔でアクセスがある• サーバ1台
6. 処理時間は1アクセスあたり
平均0.04
分間の
ランダム
サービス
待っているアクセス数
の時系列変化
平均到着時間間隔(1/λ) 0.050 分/ア 平均サービス時間(1/μ) 0.039 分/ア 平均待ち客数(Lq) 2.502 ア 平均待ち時間(Wq) 0.118 分 平均滞留客数(L) 3.305 ア 平均滞留時間(W) 0.157 分 シミューレーション • 1分間に平均20アクセスのランダム到着 • 平均0.05分間隔でアクセスがある • サーバ1台 6. 処理時間は1アクセスあたり平均0.04 分間のランダムサービス たとえば・・・ 実験的に(シミューレーション)に頼るしかない･･･？• 到着率
λ
← 1分あたり平均20アクセス (λ=20[ア/分])
• 到着時間間隔1/λ ← 何分に1アクセス？ (1/λ=0.05[分/ア])• サービス時間
1/ μ
← 1アクセスあたり平均0.04分かかる (1/μ=0.04[分/ア])
• サービス率μ ← 1分当たり何アクセス処理？ (μ=25[ア/分])• システム(窓口)に客がいる確率(=利用率)
ρ= λ/μ
• 『平衡状態』ρ<1 • システムの混雑の度合い • サービス数＞到着数ならば，行列が無限に長くはならない • 到間時間間隔＞サービス時間ならば，行列が無限に長くはならない • 『定常分布』 ρn(1-ρ) • 十分に時間が経ったとき，システムにn人いる確率 • 時刻0の状態に関係ないシステムの評価指標 (1)
n+1 人 n人 n-1 人 λ (到着) μ (終了) 1-λ-μ (到着も終了もない) p(0)= (1-λ) p(0)+ μ p(1) p(1)=(λ/μ)1p(0) p(1)= λ p(0)+ (1-λ-μ) p(1)+ μ p(2) p(2)=(λ/μ)2p(1) p(2)= λ p(1)+ (1-λ-μ) p(2)+ μ p(3) ・・・・ ・・・・ p(n)=(λ/μ)np(0) ↑ p(0)=(1-λ/μ) {1+λ/μ+・・・・+(λ/μ)n}p(0)=1 p(n)=(1-λ/μ) (λ/μ)n 定常性 独立性 なランダム 希少性システムの評価指標 (2)
• 到着率λ ← 1分あたり平均20アクセス (λ=20[ア/分]) • 到着時間間隔1/λ ← 何分に1アクセス？ (1/λ=0.05[分/ア]) • サービス時間1/ μ ← 1アクセスあたり平均0.04分かかる (1/μ=0.04[分/ア]) • サービス率μ ← 1分当たり何アクセス処理？ (μ=25[ア/分]) • システム(窓口)に客がいる確率(=利用率)ρ= λ/μ• 待っている客の平均数
Lq=ρ
2/(1-ρ)
• システムにいる客の平均数
L=ρ/(1-ρ)
←L=Lq+ρ
>>> Lq[ア]待ちでρ[ア]処理中• 平均待ち時間
Wq= Lq/ λ
←Lq=λ Wq
>>>Wq[分]間にLq[ア]到着する• 平均滞留時間
W= L/ λ
←W=Wq+(1/μ)
>>>Wq[分]間待って，(1/μ)[分]サービスを受ける 『リトルの法則』 1961年ジョン・リトル (待ち人数)＝(到着率)×(待ち時間) 待っている間に何人来るか？ システム 到着 退出 サービス今日の例題 まとめ2
システムの評価指標
理論値 と 実験値理論的に求める
• 1分間に平均20アクセ
スの
ランダム
到着
• 平均0.05分間隔• サーバ1台
6. 処理時間は1アクセ
スあたり平均
0.04
分間の
ランダム
サービス
6. 理論値 シミュレーション 平均到着率(λ) 20 ア/分 平均サービス率(μ) 25 ア/分 平均到着時間間隔(1/λ) 0.050 分/ア 0.050 分/ア 平均サービス時間(1/μ) 0.040 分/ア 0.039 分/ア 利用率(ρ) 0.8 平均待ち客数(Lq) 3.200 ア 2.502 ア 平均待ち時間(Wq) 0.160 分 0.118 分 平均滞留客数(L) 4.000 ア 3.305 ア 平均滞留時間(W) 0.200 分 0.157 分待ち行列(queuing theory)のフレームワーク
• 到着の確率法則
• サービス時間の確率法則
• 窓口(システム)の数
• システムの容量(最大数)
• サービスの順番
• 母集団の大きさ
• 窓口(システム)の配置
システム 到着 退出 サービス到着の確率法則
サービスの確率法則
• (D)一定，レギュラー ・・・点
• 既知のスケジュールに従って到着する• (G)均等，一般 ・・・一様分布，正規分布
• 集中している，限りがある• (M)ランダム，でたらめ ・・・ポアソン分布，指数分布
• ぱらぱら発生する，まれに起こる事象 0 20 40 60 80 100 120 0 0 .0 1 0 .0 2 0 .0 3 0 .0 4 0 .0 5 0 .0 6 0 .0 7 0 .0 8 0 .0 9 0 .1 0 .1 1 0 .1 2 0 .1 3 次の級 0 100 200 300 400 500 600 0.01 0.02 0.03 0.04 0.05 0.06 0.07 0 10 20 30 40 50 60 70 80 0 0.01 0.02 0.03 0.04 0.05 0.06 0.07 0.08到着 退出 サービス サービス サービス システム 到着 退出 サービス サービス サービス • 窓口(システム)の数 • 1つ • 複数 • システムの容量(最大数) • 無限大 • 有限なら・・・拒否される • サービスの順番
• 先着順: First Come(In) First Served(Out) • 優先順位つき
• 後着順: Last Come First Served
• 窓口(システム)の配置
• 直列型・・一列並び • 並列型
ケンドール(Kendall)記号
• ア/イ/ウ(エ) • ア・・・到着の確率法則 • イ・・・サービスの確率法則 • ウ・・・窓口の数 • エ・・・システムの容量 たとえば 1. D/D/1 ・・・(単純な場合) 一律0.05分間隔で到着，一律0.04分間でサービス 4. M/D/1 ・・・(少し現実的) 平均0.05分間隔でランダム到着，一律0.04分間でサービス 6. M/M/1 ・・・(現況) 平均0.05分間隔でランダム到着，平均0.04分間でランダムサービス (ア)到着 (イ)サービス M ポアソン到着 指数サービス D レギュラー到着 レギュラーサービス G 一般の到着 一般のサービス Ek 次数kのアーラン到着 次数kのアーランサービスどれくらい改善できるだろうか･･･？
次の一手を考える
【現況】
• 平均(1/20)分間隔でアクセスが
ある
• 1分間に平均20アクセス • ポアソン到着• サーバ1台
• 1アクセスあたり平均(1/25)分間
で処理
• 1分間に平均25アクセスを処理 • 指数サービス 【対策1】 7. サーバの処理速度を2倍にする 【対策2】 8. サーバを2台にする (直列) • 到着アクセスは空いているほうに割り当てる 【対策3】 9. サーバを2台にする (並列) • 到着アクセスは0.5でいずれかサーバに割り当てる 【対策4】処理方法を変更 3. 一律0.04分間かける 4. 処理時間が0.02分間と， 0.06分間の交互 平均待ちアクセス数(Lq) 3.2アクセス 平均待ち時間(Wq) 0.16分 平均アクセス数(L) 4アクセス 平均滞留時間(W) 0.2分他の場合
• D/D/1 ・・・サービスも到着も一定
• 0.05分ごとに到着，0.04分でサービス• M/M/s ・・・窓口が複数s
• 直列 • 1列に並んで空いたところでサービスを受ける • たとえば，M/M/2• M/G/1 ・・・サービス時間が一般分布
• 一様分布，正規分布，(一定)• M/G/s ・・・窓口が複数
M/M/1 システム(窓口)に客がいる確率(=利用率)ρ= λ/μ 待っている客の平均数Lq=ρ2/(1-ρ) システムにいる客の平均数L=ρ/(1-ρ) 平均待ち時間Wq= Lq/ λ 平均滞留時間W= L/ λ =Wq + 1/μ 『ポラチェク・ヒンチンの公式』 Wq(M/G/s)= (1+c2)/2 * Wq(M/M/s) c=(標準偏差)/(平均) M/M/2 システム(窓口)に客がいる確率(=利用率)ρ= λ/2μ 待っている客の平均数Lq=2ρ3/(1-ρ2) システムにいる客の平均数L=2ρ/(1-ρ2) 平均待ち時間Wq= Lq/ λ 平均滞留時間W= L/ λ【現況】 M/M/1 • 1分間に平均20アクセスランダム到着 • 1/λ=0.05 [分/ア] • サーバ1台でランダムサービス • 1/μ=0.04[分/ア] 【対策1】 M/M/1 7. サーバの処理速度を2倍にする • 1/μ=0.02[分/ア] 【対策2】 M/M/2 8. サーバを2台にする (直列) • 到着アクセスは空いているほうに 【対策3】 M/M/1 ×2 9. サーバを2台にする (並列) • 到着アクセスは確率0.5でいずれかに 1/λ=0.1[分/ア] 【対策4】 M/D/1 (M/G/1) 4. 一律0.04分間かける c=0 5. 処理時間が0.02分間と， 0.06分間の交互 c=0.02/0.04=1/2 M/M/1 システム(窓口)に客がいる確率(=利用率)ρ= λ/μ 待っている客の平均数Lq=ρ2/(1-ρ) システムにいる客の平均数L=ρ/(1-ρ) 平均待ち時間Wq= Lq/ λ 平均滞留時間W= L/ λ =Wq + 1/μ 『ポラチェク・ヒンチンの公式』 Wq(M/G/s)= = (1+c2)/2 * Wq(M/M/s) c=(標準偏差)/(平均) M/M/2 システム(窓口)に客がいる確率(=利用率)ρ= λ/2μ 待っている客の平均数Lq=2ρ3/(1-ρ2) システムにいる客の平均数L=2ρ/(1-ρ2) 平均待ち時間Wq= Lq/ λ 平均滞留時間W= L/ λ
到着 0.05分間隔 サービス 0.04分間 待ち システム内 Wq[分] Lq[アクセス] W[分] L[アクセス] 1. 一定 一定 0.000 0.000 0.040 1.000 2. 一定 一定 0.005 0.500 0.045 1.500 4.対策4 ランダム 一定 0.080 1.600 0.120 2.400 5.対策4 ランダム 一般・交互 0.100 2.000 0.140 2.800 6.現況 ランダム ランダム 0.160 3.200 0.200 4.000 7.対策1 ランダム ランダム 2倍速 0.013 0.267 0.033 0.667 8.対策2 ランダム ランダム 2台直列 0.008 0.152 0.048 0.952 9.対策3 ランダム ランダム 2台並列 0.027 0.267(×2) 0.067 0.667(×2)
今日の例題のまとめ3
今日のまとめ
• システム：入力が処理され出力さる・・・繰り返す • 到着(入力)とサービス(処理・出力)の確率法則 • ランダム，でたらめ • 平均的に • 「待ち」を測る指標 • どれくらい待つことになる？ • 何人くらい待っている？ • 制御ができるもの，制御できそうなもの • 窓口(システム)の数，システムの容量(最大数)，サービスの順番，窓口(システム)の配置 • 客の到着の仕方，客の母集団これまで3回のまとめ
問題を整理する → 定式化する → 最適解を求める → 考察する
• IT環境を安全に保つために対策を講じる
• 線形計画法・・・限られた資源を有効活用する • ゲーム理論・・・相手がいる状況での最適化 (ミニマックス)• ネットワークを設計する
• 広く，たくさん，早く，安く，安全に…etc • 線形計画法(再) • 入りと出がある • {0,1}変数 >>>> Yes/No，“ならば”演算• システムを運用する
• 待ち行列・・・待つ時間，待っている客 • ランダム，でたらめ と 平均オペレーションズリサーチと
ゲーム理論 (3日目)
兵庫県立大学 円谷 友英
システムの状態を待ちで考える「指標」は？
【今日の例題～単純な場合】 • 1分間に一律20アクセスある >>>到着 • 一律0.05分間隔でアクセスがある • サーバ1台 1. 処理時間は1アクセスあたり一律0.04分間 >>>サービス • 1分間に一律25アクセスを処理 2. 処理時間が0.02分間のアクセスと， 0.06分間のアクセスとが交互にある >>>サービス • 処理時間は1アクセスあたり平均0.04分 3. 処理時間が0.1分間のアクセスと，0.04分間のアクセスとが交互にある >>> サービス • 処理時間は1アクセスあたり平均0.07分ランダムな到着 & ランダムなサービス
• ランダム，でたらめ・・・とは？
• 定常性：到着のしかたは時間に依存しない (どの時刻でも同じ) • 独立性：互いに影響を与えない (残留効果がない) • 希少性：同時に2人到着する確率は無視できるくらい小さい【今日の例題～少し現実的な場合】
• 1分間に平均20アクセスの
ランダム
なアクセスがある
>>>到着
• 平均0.05分間隔でアクセスがある• サーバ1台
4. 処理時間は1アクセスあたり一律0.04分間
5. 処理時間が0.02分間のアクセスと， 0.06分間のアクセスとが交互にある
• どうなることが予測できる？
0 時間 到時 サービス 終了時刻 待ち時間 待ち人数 1 0.05 0.04 0.59 0 0 2 0.05 0.02＆0.06 0.61 0.005 0.5シミュレーション
M/M/1
(∞)
ポアソン到着 指数サービス 窓口1つ 指数分布に従うと仮定→指数乱数 (到着時間間隔) 平均0.05 (サービス時間) 平均0.04【今日の例題～それらしい現況】
• 1分間に平均20アクセスの
ランダム
到着
• 平均0.05分間隔でアクセスがある• サーバ1台
6. 処理時間は1アクセスあたり
平均0.04
分間の
ランダム
サービス
どれくらい改善できるだろうか･･･？
次の一手を考える
【現況】
• 平均(1/20)分間隔でアクセスが
ある
• 1分間に平均20アクセス • ポアソン到着• サーバ1台
• 1アクセスあたり平均(1/25)分間
で処理
• 1分間に平均25アクセスを処理 • 指数サービス 【対策1】 7. サーバの処理速度を2倍にする 【対策2】 8. サーバを2台にする (直列) • 到着アクセスは空いているほうに割り当てる 【対策3】 9. サーバを2台にする (並列) • 到着アクセスは0.5でいずれかサーバに割り当てる 【対策4】処理方法を変更 3. 一律0.04分間かける 4. 処理時間が0.02分間と， 0.06分間の交互 平均待ちアクセス数(Lq) 3.2アクセス 平均待ち時間(Wq) 0.16分 平均アクセス数(L) 4アクセス 平均滞留時間(W) 0.2分【現況】 M/M/1 • 1分間に平均20アクセスランダム到着 • 1/λ=0.05 [分/ア] • サーバ1台でランダムサービス • 1/μ=0.04[分/ア] 【対策1】 M/M/1 7. サーバの処理速度を2倍にする • 1/μ=0.02[分/ア] 【対策2】 M/M/2 8. サーバを2台にする (直列) • 到着アクセスは空いているほうに 【対策3】 M/M/1 ×2 9. サーバを2台にする (並列) • 到着アクセスは確率0.5でいずれかに 1/λ=0.1[分/ア] 【対策4】 M/D/1 (M/G/1) 4. 一律0.04分間かける c=0 5. 処理時間が0.02分間と， 0.06分間の交互 c=0.02/0.04=1/2 M/M/1 システム(窓口)に客がいる確率(=利用率)ρ= λ/μ 待っている客の平均数Lq=ρ2/(1-ρ) システムにいる客の平均数L=ρ/(1-ρ) 平均待ち時間Wq= Lq/ λ 平均滞留時間W= L/ λ =Wq + 1/μ 『ポラチェク・ヒンチンの公式』 Wq(M/G/s)= = (1+c2)/2 * Wq(M/M/s) c=(標準偏差)/(平均) M/M/2 システム(窓口)に客がいる確率(=利用率)ρ= λ/2μ 待っている客の平均数Lq=2ρ3/(1-ρ2) システムにいる客の平均数L=2ρ/(1-ρ2) 平均待ち時間Wq= Lq/ λ 平均滞留時間W= L/ λ
到着 0.05分間隔 サービス 0.04分間 待ち システム内 Wq[分] Lq[アクセス] W[分] L[アクセス] 1. 2. 4.対策4 5.対策4 6.現況 7.対策1 8.対策2 9.対策3
