《待ち行列モデルの標準形》のソースを表示

'''【まちぎょうれつもでるのひょうじゅんけい (standard models of queues) 】'''

'''標準的な待ち行列モデル'''　標準的な[[待ち行列モデル]] (queueing model) は, 客の[[到着]]を表す確率過程, すなわち[[到着過程]] (arrival process) とそれぞれの客の[[サービス]] (service)に必要な時間(サービス時間という)の統計的性質, すなわち[[サービス時間分布]] (service time distribution) という2つの確率的特性と, 待ち行列モデルの構造を表現するための, [[窓口の数]] (number of servers), サービスを待つ客のための[[待合室の容量]] (capacity of waiting room), ならびに客にサービスを施す順序を表す[[サービス規律]] (service discipline) を定めることによって得られる. 


\begin{figure}[htb]
\unitlength 1mm
\thicklines
\begin{center}
\begin{picture}(130, 60)(0, 10)
\put(0, 40){\vector(1, 0){20}}
\put(105, 40){\vector(1, 0){20}}
%
\multiput(25, 32)(0, 16){2}{\line(1, 0){45}}
\multiput(25, 32)(10, 0){2}{\line(0, 1){16}}
\multiput(50, 32)(10, 0){3}{\line(0, 1){16}}
\put(70, 40){\line(1, 0){15}}
\put(85, 20){\line(0, 1){40}}
\put(85, 20){\line(1, 0){5}}
\put(85, 45){\line(1, 0){5}}
\put(85, 60){\line(1, 0){5}}
%
\put(95, 20){\circle{10}}
\put(95, 45){\circle{10}}
\put(95, 60){\circle{10}}
%
\put(10, 45){\makebox(0, 0){客の到着}}
\put(10, 35){\makebox(0, 0){到着過程}}
\put(30, 40){\makebox(0, 0){$N$}}
\multiput(38.75, 40)(3.75, 0){3}{\circle*{.7}}
\put(55, 40){\makebox(0, 0){$c$+2}}
\put(65, 40){\makebox(0, 0){$c$+1}}
\put(47.5, 53){\makebox(0, 0){待合室}}
\put(95, 70){\makebox(0, 0){窓口}}
\put(95, 60){\makebox(0, 0){1}}
\put(95, 45){\makebox(0, 0){2}}
\multiput(95, 28.75)(0, 3.75){3}{\circle*{.7}}
\put(95, 20){\makebox(0, 0){$c$}}
\put(95, 10){\makebox(0, 0){サービス時間分布}}
\put(115, 45){\makebox(0, 0){客の退去}}
%
\put(77.5, 48){\makebox(0, 0){\shortstack{サ\\\rule{.6pt}{7pt}\\ビ\\ス}}}
\put(77.5, 35){\makebox(0, 0){\shortstack{規\\律}}}
%
\end{picture}
\end{center}
\caption{待ち行列の標準形 */*/{\it c}/{\it N}}
\end{figure}


'''到着過程とサービス時間分布'''　到着過程は通常, 到着間隔の確率分布関数あるいは時間間隔 $(0, t]$ の間に到着する客数の確率分布関数で表現される. よく用いられる到着間隔分布には, 時間間隔 $(0, t]$ の間に到着する客数の確率分布関数がポアソン分布に従う[[ポアソン到着]] (Poisson arrivals), 到着間隔が独立同一な一般分布に従う[[再生過程到着]] (renewal arrivals) や等間隔到着などがある. また, サービス時間分布に関しては, 独立同一な指数分布に従う[[指数サービス]] (exponential services), サービス時間が全て等しい一定時間サービス, 一般の分布に従うサービスなどがある. 

'''窓口の数と待合室の容量'''　窓口の数は通常, 有限であるが, 十分な数の窓口が用意されている[[無限窓口モデル]] (infinite-server model) もある. 待合室の容量に関しては通常, 無限である, すなわち十分に大きいと仮定されるが, 待合室の容量が有限である[[有限待合室モデル]] (finite-buffer model) もある. 

\begin{table}[ht]
\begin{center}
\caption{ケンドールの記号 $\mbox{A}/\mbox{B}/c/N/\mbox{X}$}\label{B-A-02+Kendall}
\begin{tabular}{lll}\hline
& \multicolumn{1}{c}{記号} & 
\multicolumn{1}{c}{意味\hspace*{3cm}}
\\
\hline
%
& M & ポアソン到着あるいは指数サービス \\
& D & 等間隔到着あるいは一定時間サービス \\
& G & 一般の分布に従う到着あるいはサービス \\
到着間隔分布 & GI & 再生過程到着あるいは独立同一な \\
ならびにサー & & 一般の分布に従うサービス \\
ビス時間分布 & $\mbox{E}_k$ & $k$ 個の相をもつアーラン分布 \\
(A, B) & $\mbox{H}_k$ & $k$ 個の相をもつ超指数分布 \\ 
 & PH & 一般の相型分布 \\
 & MAP & マルコフ型到着過程 \\
 & $\mbox{M}^{[X]}$ & ポアソン分布に従う集団到着 \\
\hline
& FCFS & 先着順サービス \\
& FIFO & 先着順サービス (単一窓口の場合) \\
サービス規律 & LCFS & 後着順サービス \\
(X) & LIFO & 後着順サービス (単一窓口の場合) \\
& ROS & ランダム順サービス \\
& PS & プロセッサシェアリング \\
\hline
\end{tabular}
\end{center}
\end{table}

\clearpage

'''サービス規律'''　サービス規律には, 到着順にサービスを行う最も標準的な規律である[[先着順サービス]] (first-come first-served service) 以外に, 到着とは逆の順序でサービスを行う[[後着順サービス]] (last-come first-served service), 到着順とは無関係に, でたらめな順序でサービスを行う[[ランダム順サービス]] (random order service)やサービス施設の能力をシステム内の客で均等に分け合う[[プロセッサシェアリング]] (processor-sharing) などがある. また, 複数のタイプの客が到着し, タイプ間で[[優先権]] (priority)がある場合も考えられている. 

'''ケンドールの記号'''　[[待ち行列モデル]] (queueing model) はこれらの要素を組合わせることによって定めることができるが, この組み合わせを簡便に表現するための記法として, 通常, [[ケンドールの記号]] (Kendall's notation) が用いられる. ケンドールの記号は A/B/$c/N$ という形をもっており, Aは到着間隔分布, Bはサービス時間分布, $c$ は窓口の数, $N$ は窓口と待合室の容量の和を表す. さらに, これらに加えて, サービス規律を付加することもある. これらを表す記号を表1に示す. 

　例えば M/M/3/10/FCFS (あるいは FCFS M/M/3/10) は, ポアソン到着, 指数サービス, 窓口が3つで待合室の容量が7であり, サービスが先着順で行われる待ち行列モデルを表し, GI/G/1/$\infty$/LCFS (あるいは LCFS GI/G/1/$\infty$) は, 再生過程到着, 一般分布サービス, 窓口が1つで待合室の容量に制限がなく, サービスが後着順で行われる待ち行列モデルを表す. 特に, 待合室の容量に制限がない場合 $\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.