《待ち行列における近似》

【まちぎょうれつにおけるきんじ (approximations for queues) 】

　待ち行列における近似は, 近似対象を比較的狭い範囲に固定した簡易式としての位置付けの近似式と, 汎用モデルとしての位置付けの近似解法に大きく2分される. いずれも, 解析が非常に難しい, あるいは解析は可能だが特性量の計算に非常に長い時間を要する待ち行列に対して必要かつ有用である.

　標準型待ち行列GI/G/$$s$$は, そのモデルの一般性から, これまで数多くの近似式が提案されている. 特に, 客の到着がポアソン過程にしたがうM/G/$$s$$待ち行列とその変形集団到着, 有限待合室, 優先権等)に対しては, モデルの重要性と厳密な解析の困難さのために, 待ち行列理論の歴史の中でもかなり早い段階から研究が進められてきた.

　簡易式としての位置付けから, 平均待ち時間E($$W_{q}^{{\rm {M/G}}/s}$$)にはとりわけ多くの近似式が提案されている. E($$W_{q}^{{\rm {M/G}}/s}$$)に対する近似式が最低限満たすべき性質は以下の3つである.

1. $$s=1$$のとき, E($$W_{q}^{\rm {M/G/1}}$$)に対するポラチェック・ヒンチンの公式と整合すること.

2. 指数サービス時間分布のとき, E($$W_{q}^{{\rm {M/M}}/s}$$)と整合すること.

3. 重負荷(heavy traffic)時における漸近的性質

$\lim _{\rho \to 1}\,(1-\rho )\,{\mbox{E}}(W_{q}^{{\rm {M/G}}/s})={\frac {1+c_{s}^{2}}{2s\mu }}$

と整合すること. ただし, $$\rho =\lambda /s\mu$$ はトラフィック密度, $$\lambda$$ は到着率, $$\mu$$ はサービス率, $$c_{s}$$ はサービス時間分布の変動係数を表す.

これらをすべて満たす近似式として, リー・ロントンの近似式 $$\,$ $(Lee-Longton approximation) [5] が知られている. リー・ロントンの近似式は, $$0\leq c_{s}<1$$のとき過小評価, $$c_{s}>1$$のとき過大評価する傾向がある. さらに正確な近似式を得るためには, 性質 1-3に加えて

4. 一定サービス時間分布のとき, E($$W_{q}^{{\rm {M/D}}/s}$$)と整合すること.

5. $$s\to \infty$$のときの漸近的性質

$\lim _{s\to \infty }{\frac {{\mbox{E}}(W_{q}^{{\rm {M/G}}/s})}{{\mbox{E}}(W_{q}^{{\rm {M/M}}/s})}}=1$

と整合すること.

6. 軽負荷(light traffic)時における漸近的性質

$\lim _{\rho \to 0}{\frac {{\mbox{E}}(W_{q}^{{\rm {M/G}}/s})}{{\mbox{E}}(W_{q}^{{\rm {M/M}}/s})}}=s\mu \int _{0}^{\infty }\{1-G_{e}(t)\}^{s}dt$

と整合すること. ここで, $$G_{e}(\cdot )$$はサービス時間分布の平衡分布を表す.

を満たすことが要求される. 性質 1-5を満たす近似式の中で, 木村の近似式(Kimura's approximation) [1]

${\mbox{E}}(W_{q}^{{\rm {M/G}}/s})\approx {\frac {1+c_{s}^{2}}{\displaystyle {\frac {2c_{s}^{2}}{{\mbox{E}}(W_{q}^{{\rm {M/M}}/s})}}+{\frac {1-c_{s}^{2}}{{\mbox{E}}(W_{q}^{{\rm {M/D}}/s})}}}}$

は, $$c_{s}$$ の値に依らず比較的安定した精度をもつことが知られている.

　性質1-5まではサービス時間の2~次までのモーメント(平均, 分散)のみを用いて表されるため, これらの性質を用いて得られる近似式を2モーメント近似(two-moment approximation)と呼ぶ. これに対し, 性質 6はサービス時間の分布情報を必要とするため, 性質1-6をすべて満たす近似式は2モーメント近似よりも簡易式としての利便性をやや欠くことになる. さらに, 中程度以上の負荷がかかる状況では近似精度で2 モーメント近似との間で大きな差を生じないため, 実用上は性質 1-5を満たす2モーメント近似で十分である. 性質6はそれ自身軽負荷近似 (light traffic approximation)として用いられることもある.

　M/G/$$s$$待ち行列の平均待ち時間以外の重要な特性量としては, 到着客の待ち確率(delay probability) $$\Pi ^{{\rm {M/G}}/s}$$が挙げられる. 理論的および数値的検証によって

$\Pi ^{{\rm {M/G}}/s}\approx \Pi ^{{\rm {M/M}}/s}$

が非常に良い近似となることが確かめられており, アーランの待ち確率近似(Erlang delay probability approximation)と呼ばれている. この他, 待ち時間分布や系内客数分布に対する近似式 [7], 有限待合室の場合の呼損率に対する近似式 [3] 等が研究されている.

　一般到着分布をもつGI/G/$$s$$待ち行列に対する近似式は, M/G/$$s$$待ち行列ほど成功しているとは言い難い. その第1の原因は, 特性量が満たすべき性質の理論的解明が進んでいない点にある. 例えばE($$W_{q}^{{\rm {GI/G}}/s}$$)に対する近似式が満たすべき性質としては, E($$W_{q}^{{\rm {M/G}}/s}$$)に対する性質に加えて

7. E($$W_{q}^{{\rm {D/M}}/s}$$)あるいはE($$W_{q}^{{\rm {GI/M}}/s}$$)と整合すること.

が課せられる程度でしかない. ここで, 重負荷時における性質3は, 到着時間間隔分布の変動係数を$$c_{a}$$とすると

$\lim _{\rho \to 1}(1-\rho ){\mbox{E}}(W_{q}^{{\rm {GI/G}}/s})={\frac {c_{a}^{2}+c_{s}^{2}}{2s\mu }}$

で置き換えられることに注意しよう. また第2の原因としては, 到着過程の3次以上のモーメントが特性量に強く影響するために, 簡易な2モーメント近似が本質的に得にくい点が挙げられる. 性質1-5および7を満たすE($$W_{q}^{{\rm {GI/G}}/s}$$)に対する近似式としてはページの近似式 (Page's approximation) [6] が知られているが, $$c_{a}>1$$または$$c_{s}>1$$のとき過大評価する傾向がある. この他の近似式については [2]を参照のこと.

　汎用モデルとして位置付けられる近似解法は極めて限られる. 流体近似 (fluid approximation)と拡散近似 (diffusion approximation) [4] は, 待ち行列における代表的な汎用モデルである. 両者は, 系内客数過程のような離散値確率過程を連続値を取る過程でモデル化するという点で共通している. この意味で, これら2~つの近似解法を待ち行列の連続モデルと捉えることもできる. 系内客数過程$$\{N(t);\,t\geq 0\}$$を例に取ると, 拡散近似は, 適当な境界条件の下で線形確率微分方程式

${\mbox{d}}X(t)=(\lambda -\mu ){\mbox{d}}t+(\lambda c_{a}^{2}+\mu c_{s}^{2}){\mbox{d}}B(t),\qquad t\geq 0$

で記述されるブラウン運動 (Brownian motion)$$\{X(t);\,t\geq 0\}$$を$$\{N(t);\,t\geq 0\}$$の連続モデルとして用いる. ここで, $$\{B(t);\,t\geq 0\}$$は標準ブラウン運動を表す. 流体近似は, 確率変動を表すこの方程式の右辺第2項を無視した場合に相当する.

　連続モデルの一般的短所として, 過程の離散的性質を無視できない軽負荷時において, 離散モデルの厳密解との間に大きな乖離を生ずることが挙げられる. 特に, 流体近似においては $$\rho <1$$ のとき行列が生じないため, その定常解析は意味をなさない. しかし, 解析的には連続モデルの方が離散モデルよりもむしろ容易であり, 過渡解析のモデルとしては離散モデルよりも優っている.

---

参考文献

[1] T. Kimura, "A Two-Moment Approximation for the Mean Waiting Time in the GI/G/$s$ Queue," Management Science, 32 (1986), 751-763.

[2] T. Kimura, "Approximations for Multi-Server Queues: System Interpolations," Queueing Systems, 17 (1994), 347-382.

[3] T. Kimura, "A Transform-Free Approximation for the Finite Capacity M/G/$s$ Queue," Operations Research, 44 (1996), 984-988.

[4] 木村俊一, 「拡散近似: 離散と連続のはざまで」, 『オペレーションズ・リサーチ』, 42 (1997), 540-546.

[5] A. M. Lee and P. A. Longton, "Queueing Process Associated with Airline Passenger Check-In," Operational Research Quarterly, 10 (1957), 56-71.

[6] E. Page, Queueing Theory in OR, Butterworth, 1972.

[7] H. C. Tijms, Stochastic Models: An Algorithmic Approach, Wiley, 1994.