《待ち行列の極限モデル（流体近似と拡散近似）》

出典: ORWiki

【まちぎょうれつのきょくげんもでる（りゅうたいきんじとじゅうふかきんじ）(limiting models for queues (fluid and heavy traffic approximation))】

待ち行列モデルにおいては，窓口が１つの場合にポアソン到着やサービス時間が指数分布に従うことを仮定すると待ち時間や待ち人数の定常分布やそのモーメントを比較的簡単な式で表すことができる．しかし，このような解析的結果が得られるモデルは限られ，一般的なモデルについて，性能評価量を簡単な式で表すことは困難である．これに対して，数値的な評価は位相型モデルを使うことにより広い範囲で可能である．しかし，数値的結果は個別的であり，モデルの特性を大まかにつかむマクロ的な視点からは不十分である.

極限モデル　モデルをマクロ的な視点から分類し特性を調べるために，時間と空間の尺度変換（スケール変換）を行ったモデルの列の極限を使う方法がある．この極限モデルの特性が解明できるならば，広い範囲のモデルの特性について役立つ情報が得られる．例えば，実数値を取る確率過程の時間を $n$ 倍し，状態を $\tfrac{1}{n}$ 倍すると確定的な極限過程になり，状態を $\tfrac 1{\sqrt{n}}$ 倍するとブラウン運動となる場合が多い．より一般的に， $H > 0$ に対して状態を $n - H$ 倍することもある．この方法は，モデルの近似と考えることもできるが，数学的に精密に極限を求めるため直感的な近似モデルとは異なる．

このような尺度変換により現れる各種の極限モデルを窓口が１つで待合室に入る客数に制限がない先着順モデルついて述べる．システムは初め空であり，時刻 $0$ から稼働を始める． $\ell=1,2,\ldots$ に対して， $\ell$ 番目の客が時刻 $t_{\ell}$ に到着し，そのサービス時間を $S_{\ell}$ ，サービスを受けるまでの待ち時間を $W_{\ell}$ とする． $X_{\ell} = S_{\ell} - (t_{\ell+1} - t_{\ell})$ とおくと，

$W_{\ell+1} = \max( W_{\ell} + X_{\ell} , 0), \qquad \ell =1,2,\ldots,$

が成り立つ．ここに， $W 1 = 0$ とする．次に，

$Y_{\ell} = X_{1} + X_{2} + \ldots + X_{\ell}, \qquad \ell =1,2,\ldots,$

とおく．上記の関係式より，待ち時間の列 $W_{1}, W_{2}, \ldots, W_{\ell+1}$ は $Y_{1}, Y_{2}, \ldots, Y_{\ell}$ を使って表すことができる． $Y_{\ell}$ は最初の $\ell$ 人の客のサービス時間の和からサービスに使うことが可能な時間を差し引いたものであり，累積入出力過程と呼ぶ．

尺度変換を行うためには連続時間のほうが都合がよい．そこで， $t$ が $\ell \le t < \ell+1$ ならば $W(t) = W_{\ell}$ とおくことにより，連続変数 $t$ の関数 $W (t)$ を定義する．同様に， $Y_{\ell}$ に対して， $Y (t)$ を定義する．このとき， $\mathbf{W} = \{W(t); t \ge 0\}$ ， $\mathbf{Y} = \{Y(t); t \ge 0\}$ とし，半直線 $[0,\infty)$ 上の右連続で左極限をもつ関数の集合を $D$ により表すと， $D$ から $D$ への関数 $ψ$ を使って $\mathbf{W}= \psi(\mathbf{Y})$ と表すことができる（詳しくは [1] 参照）．

このモデルは $\mathbf{Y}$ により決まる．そこで， $n = 1,2, \ldots$ に対して， $\mathbf{Y}^{(n)}$ により， $n$ 番目のモデルを表す． $ψ$ は関数空間 $D$ に適切に与えた距離の下で連続であり， $n \to \infty$ のとき， $\mathbf{Y}^{(n)} \Rightarrow \mathbf{Y}^{(\infty)}$ ならば， $\psi(\mathbf{Y}^{(n)}) \Rightarrow \psi(\mathbf{Y}^{(\infty)})$ が成り立つ．ここに， $\Rightarrow$ は分布の弱収束することを表す．これを連続写像定理と呼ぶ．例えば，各 $t \ge 0$ に対して， $n$ 番目のモデルの $W (n) (t)$ の分布は， $n \to \infty$ のとき極限モデルの $W^{(\infty)}(t)$ の分布に弱収束する．このようにして， $\mathbf{Y}^{(\infty)}$ を累積入出力過程とする極限モデルが得られる．

自己相似過程への収束　具体的に極限モデルを得るために， $\mathbf{Y}$ の時間を $n$ 倍し，平均を $d n$ により調整し，大きさを $c n$ 倍縮小した尺度変換

$Y^{(n)}(t) = c_{n}^{-1} (Y_{[n t]} - d_{n} n t)$

$(1) \,$

により $\mathbf{Y}^{(n)}$ の各要素 $Y (n) (t)$ を定義する．ここに， $[a]$ は実数 $a$ を超えない最大の整数とする．このとき， $\mathbf{Y}^{(n)}$ の分布が $\mathbf{Y}^{(\infty)}$ の分布へ弱収束するならば， $\mathbf{Y}^{(\infty)}$ は自己相似過程 (self similar process)となる．そのハースト定数 (Hurst parameter)を $H > 0$ とするならば，任意の定数 $λ > 0$ に対して， $\lim_{x \to \infty} {L(\lambda x)}/{L(x)} = 1$ を満たす関数 $L (x)$ を使い， $c n = n H L (n)$ と表すことができる（[3]の4.2節参照）．

安定レヴィー過程　確率変数列 $X_{1}, X_{2}, \ldots$ は独立で同一の分布 $F$ に従うとする．このとき，(1)で定義した $Y (n) (t)$ に対して， $\{Y^{(n)}(t); t \ge 0\} \Rightarrow \{Y^{(\infty)}(t); t \ge 0 \}$ となる確定的ではない極限過程 $\mathbf{Y}^{(\infty)} \equiv \{Y^{(\infty)}(t)\}$ が存在するならば，この極限過程は自己相似である．そのハースト定数 $H$ に対し， $\alpha = \frac 1H$ とすると， $Y^{(\infty)}(1)$ は $α$ - 安定分布 (stable distribution)をもつ．この極限過程 $\mathbf{Y}^{(\infty)}$ を $α$ -安定レヴィー過程（Levy過程）と呼ぶ．この極限過程は， $X n$ の平均が有限ならば， $1 < \alpha \le 2$ であり， $X n$ の平均が存在しないならば， $0 < \alpha \le 1$ となる．例えば， $α = 2$ ならば， $\mathbf{Y}^{(\infty)}$ はブラウン運動に等しく， $0 < α < 2$ ならば，確定的変化を除くと分散が無限大で離散的な時刻でのみ変化する標本関数をもつ（[3]の4.2節参照）．

極限過程の分類　 $X_{1}, X_{2}, \ldots$ が独立で同一の分布に従い，各 $X n$ は有限な平均 $m X$ をもつと仮定する．このとき，(1)において $c n = n H, d n = m X n$ とし， $\mathbf{Y}^{(n)}$ を定義する．極限過程 $\mathbf{Y}^{(\infty)}$ が存在するならば， $\alpha = \frac 1H$ とすると，自己相似過程と安定分布の結果から次のことが成り立つ．

(i)

H = 1

ならば， $\mathbf{Y}^{(\infty)}$ は確定的な過程である．

(ii) $H \ne 1$ ならば， $\frac 12 \le H < 1$ であり， $\mathbf{Y}^{(\infty)}$ は

α

- 安定レヴィー過程である．

(i)の場合を流体近似，(ii)で $H = \frac 12$ の場合を拡散近似と呼ぶ． $\frac 12 < H < 1$ の場合には， $\mathbf{Y}^{(\infty)}$ は増分が無限大の分散をもち，標本関数は離散的に変化する．流体近似では極限過程が確定的であり，ランダムな要因の評価ができない．しかし，確率的な評価が難しい過渡的な現象を調べるために役立つ．これに対して，ブラウン運動は解析的に魅力あるモデルであり，拡散近似はランダムな要因を量る近似モデルとして広く使われている．また， $\frac 12 < H < 1$ の場合は解析的に扱いにくいが，サービス時間分布の裾が重い場合の近似モデルとして有効である．なお， $X_{1}, X_{2}, \ldots$ が独立でない場合には， $0 < H < \frac 12$ の場合も起こりえる．例えば，フラクタルブラウン運動では， $0 < H < 1$ であり， $H$ が大きいほど強い相関を表す．

重負荷近似　 (ii)の極限過程は， $Y^{(n)}(t) = c_{n}^{-1} (Y_{[n t]} - d_{n} n t)$ の定義から $Y (n) (t)$ の平均が $0$ のため， $\psi(\mathbf{Y}^{(\infty)})$ は定常分布をもたず，近似モデルとして使えない．定常分布が存在するためには $\eta \equiv E(Y^{(\infty)}(1)) < 0$ が必要である．そこで，(ii)のモデルの $X_{\ell}$ を $n$ ごとに変え， $X_{\ell}^{(n)}$ と表す．ただし， $X^{(n)}_{1}, X^{(n)}_{2}, \ldots$ は独立で同一の分布に従うとする．

$\tilde{Y}^{(n)}(t) = X^{(n)}_{1} + X^{(n)}_{2} + \ldots + X^{(n)}_{[nt]}, \qquad \tilde{\mathbf{Y}}^{(n)} = \{\tilde{Y}^{(n)}(t); t \ge 0\}$

とおき， $\mathbf{Y}^{(n)}$ を $Y^{(n)}(t) = c_{n}^{-1} \tilde{Y}^{(n)}(t)$ により定義する． $\tilde{\mathbf{Y}}^{(n)}$ が表す $G I / G / 1$ 待ち行列モデルの到着率を $λ n$ ，平均サービス時間の逆数を $μ n$ とおき， $ρ n = λ n / μ n$ とする． $ρ n < 1$ ， $\mu_{n} \to \mu$ $(n \to \infty)$ を仮定する．このとき， $c n = n H$ とすると

$E(Y^{(n)}(1)) = n^{-H} \Big( \frac n{\mu_{n}} - \frac n{\lambda_{n}} \Big) = \frac {\rho_{n} - 1} {\mu_{n} \rho_{n}} n^{1-H}$

である． $\frac 12 \le H < 1$ であるから， $E(Y^{(n)}(1)) \to \eta$ とするためには，

$\rho_{n} = (1 - \eta \mu_{n} n^{H-1})^{-1} + o(n^{H-1}), \qquad (n \to \infty)$

となるように $ρ n$ を選べばよい． $η < 0$ より $\rho_{n} \uparrow 1$ であるので，この極限近似を重負荷近似と呼ぶ．以後， $ρ n = (1 - ημ n n H - 1) - 1$ とする．このとき， $c_{n} = [(-\eta \mu_{n} \rho_{n})/(1-\rho_{n})]^{\frac H{1-H}}$ である．

この重負荷近似は $G I / G / 1$ モデルの漸近近似モデルとして役立つ．例えば， $\psi(\tilde{\mathbf{Y}}^{(n)})$ の時刻 $t$ での値を $W (n) (t)$ とすると， $X^{(n)}_{\ell}$ の分布に関する適切な仮定の下で，各 $t$ ごとに分布の弱収束

$\Big( \frac{1-\rho_{n}}{-\eta \mu_{n} \rho_{n}} \Big)^{\frac {H}{1-H}} W^{(n)}(t) \Rightarrow W^{(\infty)}(t), \qquad n \to \infty$

$(2) \,$

が成り立つ．したがって， $W (n) (t)$ を漸近的に $\Big( \frac{-\eta \mu_{n} \rho_{n}}{1-\rho_{n}} \Big)^{\frac {H}{1-H}} W^{(\infty)}(t)$ により表すことができる．ここに， $α = 1 / H$ とするとき， $W^{(\infty)}(t)$ は $α$ -安定レヴィー過程である．特に， $H = \frac 12$ のとき， $X^{(n)}_{1}$ の分散を $\sigma_{n}^{2}$ とし, $\sigma_{n} \to \sigma$ $(n \to \infty)$ とすれば， $\mathbf{Y}^{(\infty)}$ はブラウン運動となり，拡散近似となる．このとき， $η = - 1$ とすると， $Y^{(\infty)}(t)$ は平均が $- t$ 分散が $σ 2 t$ の正規分布に従う．

定常分布の近似　 $G I / G / 1$ モデルの拡散近似の場合に， $n$ を固定し $t \to \infty$ としたときの $W (n) (t)$ と $W^{(\infty)}(t)$ の極限分布に従う確率変数を $W^{(n)}(\infty)$ と $W^{(\infty)}(\infty)$ により表す． $n \to \infty$ に対して， $\rho_{n} \uparrow 1$ ， $\mu_{n} \to \mu$ ， $\sigma_{n}^{2} \to \sigma^{2}$ のとき，

$\frac{1-\rho_{n}} {\mu_{n} \rho_{n}} W^{(n)}(\infty) \Rightarrow W^{(\infty)}(\infty), \qquad n \to \infty$

が成り立つ．この結果は(2)から直接導かれるように見えるが，極限の交換が必要のため証明は容易ではない． $W^{(\infty)}(\infty)$ は平均が $\frac {\sigma^{2}} 2$ の指数分布に従う（[3]の5.7節参照）ので，平均について，

$E(W^{(n)}(\infty)) \sim \frac {\sigma^{2} \mu_{n} \rho_{n}}{2(1-\rho_{n})} , \qquad n \to \infty$

という漸近的な式が成り立つ．特に，客の到着がポアッソン過程に従うならば，右辺は $M / G / 1$ 待ち行列の平均待ち時間と漸近的に一致する．

適用範囲　極限モデルの存在は $G I / G / 1$ モデルの待ち時間過程に限られるものではない．例えば，待ち時間については，有限待合室モデル，複数窓口モデル，優先権付きモデルのような複数の種類の客がいる場合などに対して，拡散近似モデルが極限モデルとして得られている．ただし，有限待合室の大きさや窓口数を漸近的に大きくする必要がある．待ち時間以外の量としては，連続時間確率過程である系内残余仕事量，待ち人数などについても同様なことが成り立つ．また，流入や流出の率がが確率的に変化する確率的流体モデルやネットワーク待ち行列モデルに対しても極限モデルの存在が確かめられている．最近では，極限モデルが簡単になることを生かして，待ち行列の最適制御への応用についても研究が進んでいる．

参考文献

[1] P. Billingsley, Convergence of Probability Measures, 2nd edition John Wiley & Sons, 1999.

[2] W. Feller, An Introduction of Probability Theory and Its Applications, 2nd edition, John Wiley & Sons, 1971.

[3] W. Whitt, Stochastic-Process Limits An Introduction to Stochastic-Process Limits and Their Applications to Queues, Springer, 2001.

"http://www.orsj.or.jp/~wiki/wiki/index.php/%E3%80%8A%E5%BE%85%E3%81%A1%E8%A1%8C%E5%88%97%E3%81%AE%E6%A5%B5%E9%99%90%E3%83%A2%E3%83%87%E3%83%AB%EF%BC%88%E6%B5%81%E4%BD%93%E8%BF%91%E4%BC%BC%E3%81%A8%E6%8B%A1%E6%95%A3%E8%BF%91%E4%BC%BC%EF%BC%89%E3%80%8B" より作成

カテゴリ: 待ち行列

《待ち行列の極限モデル（流体近似と拡散近似）》

出典: ORWiki

表示

個人用ツール

ナビゲーション

検索

ツールボックス