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

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

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


図１：待ち行列の標準形 <math>*/*/{c}/{N}\, </math>


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

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


<table width="70%" border="0" cellspacing="0" cellpadding="0">
			<tr>
				<td colspan="3" align="center">図１：ケンドールの記号 <math>\mbox{A}/\mbox{B}/c/N/\mbox{X}\, </math></td>
			</tr>
			<tr>
				<td colspan="3">
					<hr>
				</td>
			</tr>
			<tr>
				<td width="20%"></td>
				<td width="15%" td align="center">記号</td>
				<td align="center">意味</td>
			</tr>
			<tr>
				<td colspan="3">
					<hr>
				</td>
			</tr>
			<tr>
				<td rowspan="9">到着間隔分布ならびにサービス時間分布 <math>\mbox{(A, B)}\, </math> </td>
				<td align="center"><math>\mbox{M}\, </math></td>
				<td>ポアソン到着あるいは指数サービス </td>
			</tr>
			<tr>
				<td align="center"><math>\mbox{D}\, </math></td>
				<td>等間隔到着あるいは一定時間サービス </td>
			</tr>
			<tr>
				<td align="center"><math>\mbox{G}\, </math></td>
				<td>一般の分布に従う到着あるいはサービス </td>
			</tr>
			<tr>
				<td align="center"><math>\mbox{GI}\, </math></td>
				<td>再生過程到着あるいは独立同一な一般の分布に従うサービス</td>
			</tr>
			<tr>
				<td align="center"><math>\mbox{E}_k\, </math></td>
				<td><math>k\, </math>個の相をもつアーラン分布</td>
			</tr>
			<tr>
				<td align="center"><math>\mbox{H}_k\, </math></td>
				<td><math>k\, </math>個の相をもつ超指数分布</td>
			</tr>
			<tr>
				<td align="center"><math>\mbox{PH}\, </math></td>
				<td>一般の相型分布</td>
			</tr>
			<tr>
				<td align="center"><math>\mbox{MAP}\, </math></td>
				<td>マルコフ型到着過程 </td>
			</tr>
			<tr>
				<td align="center"><math>\mbox{M}^{[X]}\, </math></td>
				<td>ポアソン分布に従う集団到着</td>
			</tr>
			<tr>
				<td colspan="3">
					<hr>
				</td>
			</tr>
			<tr>
				<td rowspan="6">サービス規律<math>\mbox{(X)}\, </math></td>
				<td align="center"><math>\mbox{FCFS}\, </math></td>
				<td>先着順サービス</td>
			</tr>
			<tr>
				<td align="center"><math>\mbox{FIFO}\, </math></td>
				<td>先着順サービス (単一窓口の場合)</td>
			</tr>
			<tr>
				<td align="center"><math>\mbox{LCFS}\, </math></td>
				<td>後着順サービス</td>
			</tr>
			<tr>
				<td align="center"> <math>\mbox{LIFO}\, </math></td>
				<td>後着順サービス (単一窓口の場合)</td>
			</tr>
			<tr>
				<td align="center"><math>\mbox{ROS}\, </math></td>
				<td>ランダム順サービス </td>
			</tr>
			<tr>
				<td align="center"><math>\mbox{PS}\, </math></td>
				<td>プロセッサシェアリング</td>
			</tr>
			<tr>
				<td colspan="3">
					<hr>
				</td>
			</tr>
</table>


'''サービス規律'''　サービス規律には, 到着順にサービスを行う最も標準的な規律である[[先着順サービス]] (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.