オペレーションズリサーチとゲーム理論 (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.01 1 0.00 0
2. 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.01 1 0.00 0
2. 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.25 0.20 0.15 0.10 0.05 0.00 4 3 2 1 0
今日の例題のまとめ 1 待ち を考える指標 1.2.3 比較 到時間間隔一律 25 サービス時間 終了時刻 平均待ち時間 平均待ちアクセス数 0.01 1 1 0.05 0.04 0.59 0 0 0.00 0 0.01 1 2 0.05 0.02 と 0.06 が交互 (0.04) 0.61 0.005 0.5 0.00 0 3 0.05 0.1 と 0.04 が交互 (0.07) 0.85 0.11 増加 2 増加 0.25 0.20 0.15 0.10 0.05 0.00 4 3 2 1 0 こんなに規則正しいものだろうか?
ランダムな到着 & ランダムなサービス ランダム, でたらめ とは? 定常性 : 到着のしかたは時間に依存しない ( どの時刻でも同じ ) 独立性 : 互いに影響を与えない ( 残留効果がない ) 希少性 : 同時に 2 人到着する確率は無視できるくらい小さい 0 時間 今日の例題 ~ 少し現実的な場合 1 分間に平均 20アクセスのランダムなアクセスがある >>> 到着 平均 0.05 分間隔でアクセスがある サーバ1 台 4. 処理時間は1アクセスあたり一律 0.04 分間 5. 処理時間が0.02 分間のアクセスと, 0.06 分間のアクセスとが交互にある どうなることが予測できる? 到時 サービス 終了時刻待ち時間 待ち人数 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 分間のランダムサービス ( 定常性 ) 到着のしかたは時間に依存しない ( 独立性 ) 残留効果がない ( 希少性 ) 同時に 2 人到着しない 0 時間
待っているアクセス数の時系列変化 シミューレーション 1 分間に平均 20 アクセスのランダム到着 平均 0.05 分間隔でアクセスがある サーバ 1 台 6. 処理時間は 1 アクセスあたり平均 0.04 分間のランダムサービス たとえば 平均到着時間間隔 (1/λ) 平均サービス時間 (1/μ) 平均待ち客数 (Lq) 平均待ち時間 (Wq) 平均滞留客数 (L) 平均滞留時間 (W) 0.050 分 / ア 0.039 分 / ア 2.502 ア 0.118 分 3.305 ア 0.157 分 実験的に ( シミューレーション ) に頼るしかない?
1-λ-μ ( 到着も終了もない ) システムの評価指標 (1) n-1 λ μ n+1 到着率 λ 1 分あたり平均 20アクセス (λ=20[ ア / 分 ]) 到着時間間隔 1/λ 何分に1アクセス? (1/λ=0.05[ 分 / ア ]) サービス時間 1/ μ 1アクセスあたり平均 0.04 分かかる (1/μ=0.04[ 分 / ア ]) サービス率 μ 1 分当たり何アクセス処理? (μ=25[ ア / 分 ]) システム ( 窓口 ) に客がいる確率 (= 利用率 )ρ= λ/μ 平衡状態 ρ<1 システムの混雑の度合い サービス数 > 到着数ならば, 行列が無限に長くはならない 到間時間間隔 > サービス時間ならば, 行列が無限に長くはならない 定常分布 ρ n (1-ρ) 十分に時間が経ったとき, システムに n 人いる確率 時刻 0 の状態に関係ない 人 ( 到着 ) n 人 ( 終了 ) p(0)= (1-λ) p(0)+ μ p(1) p(1)=(λ/μ) 1 p(0) p(1)= λ p(0)+ (1-λ-μ) p(1)+ μ p(2) p(2)=(λ/μ) 2 p(1) p(2)= λ p(1)+ (1-λ-μ) p(2)+ μ p(3) p(n)=(λ/μ) n p(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-ρ) リトルの法則 1961 年ジョン リトル ( 待ち人数 )=( 到着率 ) ( 待ち時間 ) 待っている間に何人来るか? システムにいる客の平均数 L=ρ/(1-ρ) L=Lq+ρ >>> Lq[ ア ] 待ちで ρ[ ア ] 処理中 平均待ち時間 Wq= Lq/ λ Lq=λ Wq >>>Wq[ 分 ] 間に Lq[ ア ] 到着する 平均滞留時間 W= L/ λ W=Wq+(1/μ) >>>Wq[ 分 ] 間待って,(1/μ)[ 分 ] サービスを受ける
今日の例題まとめ 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) のフレームワーク 到着の確率法則 サービス時間の確率法則 到着 システム サービス 退出 窓口 ( システム ) の数 システムの容量 ( 最大数 ) サービスの順番 母集団の大きさ 窓口 ( システム ) の配置
0 0.01 0.02 0.03 0.04 0.05 0.06 0.07 0.08 0.09 0.1 0.11 0.12 0.13 次の級 600 到着の確率法則サービスの確率法則 500 400 300 80 70 60 (D) 一定, レギュラー 点 既知のスケジュールに従って到着する 200 100 0 0.01 0.02 0.03 0.04 0.05 0.06 0.07 50 40 30 20 10 0 0 0.01 0.02 0.03 0.04 0.05 0.06 0.07 0.08 (G) 均等, 一般 一様分布, 正規分布 集中している, 限りがある (M) ランダム, でたらめ ポアソン分布, 指数分布 ぱらぱら発生する, まれに起こる事象 120 100 80 60 40 20 0
到着 システム サービスサービスサービス 退出 窓口 ( システム ) の数 1 つ 複数 システムの容量 ( 最大数 ) 無限大 有限なら 拒否される サービス サービスの順番 先着順 : First Come(In) First Served(Out) 優先順位つき 後着順 : Last Come First Served 到着 サービス 退出 窓口 ( システム ) の配置 直列型 一列並び 並列型 サービス
ケンドール (Kendall) 記号 ア / イ / ウ ( エ ) ア 到着の確率法則 イ サービスの確率法則 ウ 窓口の数 エ システムの容量 ( ア ) 到着 ( イ ) サービス M ポアソン到着指数サービス D レギュラー到着レギュラーサービス G 一般の到着一般のサービス E k 次数 k のアーラン到着次数 k のアーランサービス たとえば 1. D/D/1 ( 単純な場合 ) 一律 0.05 分間隔で到着, 一律 0.04 分間でサービス 4. M/D/1 ( 少し現実的 ) 平均 0.05 分間隔でランダム到着, 一律 0.04 分間でサービス 6. M/M/1 ( 現況 ) 平均 0.05 分間隔でランダム到着, 平均 0.04 分間でランダムサービス
どれくらい改善できるだろうか? 次の一手を考える 現況 平均 (1/20) 分間隔でアクセスがある 1 分間に平均 20 アクセス ポアソン到着 サーバ 1 台 1 アクセスあたり平均 (1/25) 分間で処理 1 分間に平均 25 アクセスを処理 指数サービス 対策 1 7. サーバの処理速度を 2 倍にする 対策 2 8. サーバを 2 台にする ( 直列 ) 到着アクセスは空いているほうに割り当てる 対策 3 9. サーバを 2 台にする ( 並列 ) 到着アクセスは 0.5 でいずれかサーバに割り当てる 平均待ちアクセス数 (Lq) 3.2 アクセス平均待ち時間 (Wq) 0.16 分平均アクセス数 (L) 4 アクセス平均滞留時間 (W) 0.2 分 対策 4 処理方法を変更 3. 一律 0.04 分間かける 4. 処理時間が 0.02 分間と, 0.06 分間の交互
他の場合 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/μ M/M/2 システム ( 窓口 ) に客がいる確率 (= 利用率 )ρ= λ/2μ 待っている客の平均数 Lq=2ρ 3 /(1-ρ 2 ) システムにいる客の平均数 L=2ρ/(1-ρ 2 ) 平均待ち時間 Wq= Lq/ λ 平均滞留時間 W= L/ λ ポラチェク ヒンチンの公式 Wq(M/G/s)= (1+c 2 )/2 * Wq(M/M/s) c=( 標準偏差 )/( 平均 )
現況 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/μ M/M/2 システム ( 窓口 ) に客がいる確率 (= 利用率 )ρ= λ/2μ 待っている客の平均数 Lq=2ρ 3 /(1-ρ 2 ) システムにいる客の平均数 L=2ρ/(1-ρ 2 ) 平均待ち時間 Wq= Lq/ λ 平均滞留時間 W= L/ λ ポラチェク ヒンチンの公式 Wq(M/G/s)= = (1+c 2 )/2 * Wq(M/M/s) c=( 標準偏差 )/( 平均 )
今日の例題のまとめ 3 到着 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 ランダム 8. 対策 2 ランダム 9. 対策 3 ランダム ランダム 2 倍速 ランダム 2 台直列 ランダム 2 台並列 0.013 0.267 0.033 0.667 0.008 0.152 0.048 0.952 0.027 0.267( 2) 0.067 0.667( 2)
今日のまとめ システム : 入力が処理され出力さる 繰り返す 到着 ( 入力 ) とサービス ( 処理 出力 ) の確率法則 ランダム, でたらめ 平均的に 待ち を測る指標 どれくらい待つことになる? 何人くらい待っている? 制御ができるもの, 制御できそうなもの 窓口 ( システム ) の数, システムの容量 ( 最大数 ), サービスの順番, 窓口 ( システム ) の配置 客の到着の仕方, 客の母集団
これまで 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 人到着する確率は無視できるくらい小さい 0 時間 今日の例題 ~ 少し現実的な場合 1 分間に平均 20アクセスのランダムなアクセスがある >>> 到着 平均 0.05 分間隔でアクセスがある サーバ1 台 4. 処理時間は1アクセスあたり一律 0.04 分間 5. 処理時間が0.02 分間のアクセスと, 0.06 分間のアクセスとが交互にある どうなることが予測できる? 到時 サービス 終了時刻待ち時間 待ち人数 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 でいずれかサーバに割り当てる 平均待ちアクセス数 (Lq) 3.2 アクセス平均待ち時間 (Wq) 0.16 分平均アクセス数 (L) 4 アクセス平均滞留時間 (W) 0.2 分 対策 4 処理方法を変更 3. 一律 0.04 分間かける 4. 処理時間が 0.02 分間と, 0.06 分間の交互
現況 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/μ M/M/2 システム ( 窓口 ) に客がいる確率 (= 利用率 )ρ= λ/2μ 待っている客の平均数 Lq=2ρ 3 /(1-ρ 2 ) システムにいる客の平均数 L=2ρ/(1-ρ 2 ) 平均待ち時間 Wq= Lq/ λ 平均滞留時間 W= L/ λ ポラチェク ヒンチンの公式 Wq(M/G/s)= = (1+c 2 )/2 * Wq(M/M/s) c=( 標準偏差 )/( 平均 )
今日の例題のまとめ 到着 0.05 分間隔 サービス 0.04 分間 待ち システム内 Wq[ 分 ] Lq[ アクセス ] W[ 分 ] L[ アクセス ] 1. 2. 4. 対策 4 5. 対策 4 6. 現況 7. 対策 1 8. 対策 2 9. 対策 3