《待ち行列モデルの標準形》
【まちぎょうれつもでるのひょうじゅんけい (standard models of queues) 】
標準的な待ち行列モデル 標準的な待ち行列モデル (queueing model) は, 客の到着を表す確率過程, すなわち到着過程 (arrival process) とそれぞれの客のサービス (service)に必要な時間(サービス時間という)の統計的性質, すなわちサービス時間分布 (service time distribution) という2つの確率的特性と, 待ち行列モデルの構造を表現するための, 窓口の数 (number of servers), サービスを待つ客のための待合室の容量 (capacity of waiting room), ならびに客にサービスを施す順序を表すサービス規律 (service discipline) を定めることによって得られる.
 |
| 図１：待ち行列の標準形 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle */*/{c}/{N}\, }
スタイル検討 |
到着過程とサービス時間分布 到着過程は通常, 到着間隔の確率分布関数あるいは時間間隔 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle (0, t]\, }
の間に到着する客数の確率分布関数で表現される. よく用いられる到着間隔分布には, 時間間隔 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle (0, t]\, }
の間に到着する客数の確率分布関数がポアソン分布に従うポアソン到着 (Poisson arrivals), 到着間隔が独立同一な一般分布に従う再生過程到着 (renewal arrivals) や等間隔到着などがある. また, サービス時間分布に関しては, 独立同一な指数分布に従う指数サービス (exponential services), サービス時間が全て等しい一定時間サービス, 一般の分布に従うサービスなどがある.
窓口の数と待合室の容量 窓口の数は通常, 有限であるが, 十分な数の窓口が用意されている無限窓口モデル (infinite-server model) もある. 待合室の容量に関しては通常, 無限である, すなわち十分に大きいと仮定されるが, 待合室の容量が有限である有限待合室モデル (finite-buffer model) もある.
| 図１：ケンドールの記号構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \mbox{A}/\mbox{B}/c/N/\mbox{X}\, } | ||
|
|
||
| 記号 | 意味 | |
|
|
||
| 到着間隔分布ならびにサービス時間分布 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \mbox{(A, B)}\, } | 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \mbox{M}\, } | ポアソン到着あるいは指数サービス |
| 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \mbox{D}\, } | 等間隔到着あるいは一定時間サービス | |
| 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \mbox{G}\, } | 一般の分布に従う到着あるいはサービス | |
| 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \mbox{GI}\, } | 再生過程到着あるいは独立同一な一般の分布に従うサービス | |
| 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \mbox{E}_k\, } | 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle k\, } 個の相をもつアーラン分布 | |
| 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \mbox{H}_k\, } | 個の相をもつ超指数分布 | |
| 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \mbox{PH}\, } | 一般の相型分布 | |
| 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \mbox{MAP}\, } | マルコフ型到着過程 | |
| 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \mbox{M}^{[X]}\, } | ポアソン分布に従う集団到着 | |
|
|
||
| サービス規律 | 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \mbox{FCFS}\, } | 先着順サービス |
| 先着順サービス (単一窓口の場合) | ||
| 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \mbox{LCFS}\, } | 後着順サービス | |
| 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \mbox{LIFO}\, } | 後着順サービス (単一窓口の場合) | |
| 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \mbox{ROS}\, } | ランダム順サービス | |
| 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \mbox{PS}\, } | プロセッサシェアリング | |
|
|
||
サービス規律 サービス規律には, 到着順にサービスを行う最も標準的な規律である先着順サービス (first-come first-served service) 以外に, 到着とは逆の順序でサービスを行う後着順サービス (last-come first-served service), 到着順とは無関係に, でたらめな順序でサービスを行うランダム順サービス (random order service)やサービス施設の能力をシステム内の客で均等に分け合うプロセッサシェアリング (processor-sharing) などがある. また, 複数のタイプの客が到着し, タイプ間で優先権 (priority)がある場合も考えられている.
ケンドールの記号 待ち行列モデル (queueing model) はこれらの要素を組合わせることによって定めることができるが, この組み合わせを簡便に表現するための記法として, 通常, ケンドールの記号 (Kendall's notation) が用いられる. ケンドールの記号は A/B/構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle c/N\, } という形をもっており, Aは到着間隔分布, Bはサービス時間分布, は窓口の数, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle N\, } は窓口と待合室の容量の和を表す. さらに, これらに加えて, サービス規律を付加することもある. これらを表す記号を表1に示す.
例えば M/M/3/10/FCFS (あるいは FCFS M/M/3/10) は, ポアソン到着, 指数サービス, 窓口が3つで待合室の容量が7であり, サービスが先着順で行われる待ち行列モデルを表し, GI/G/1/構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \infty\, } /LCFS (あるいは LCFS GI/G/1/構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \infty\, } ) は, 再生過程到着, 一般分布サービス, 窓口が1つで待合室の容量に制限がなく, サービスが後着順で行われる待ち行列モデルを表す. 特に, 待合室の容量に制限がない場合 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \infty\, } を省略し, またサービス規律がFCFS の場合, これを省略することが多い. 例えば M/D/2 はポアソン到着, 一定サービス, 窓口が2つで待合室の容量に制限がなく, サービスが先着順で行われる待ち行列モデルを表す.
参考文献
[1] D. Gross and C. M. Harris, Fundamentals of Queueing Theory, Third Edition, John Wiley & Sons, 1998.
[2] D. G. Kendall, "Some Problems in the Theory of Queueus," Journal of the Royal Statistical Society, Series B, 13 (1950), 151-185.