待ち行列理論 その1

今勉強中ですがまとめがてらここに書いていきます。証明はあまり厳密ではなく書かないこともあります。

待ち行列とは

まず待ち行列について説明します。待ち行列は数学と情報学の2つの分野で研究されている現実のレジなどで起きる行列の平均客数や平均待ち時間調べる分野です。もちろん離散型と連続型があります。待ち行列を考える分野の例としては先ほど挙げたレジのような行列だけでなく、電話やネットの回線のデータを客と見たときの行列や工場での製造過程の中で作られている商品を客としてみたときの行列など様々な種類の行列があげられます。本質的には待つ対象と待つ場所があれば行列ができるので意外と待ち行列理論の適用範囲は広いのではないでしょうか。
以降特に何も言わなければ連続型を考えることにします。

用語の定義（具体例としてレジを待つ行列を考えた場合）

• サーバー：サービスを行う場所。窓口とも呼ばれる。つまりレジのことである。サーバー一つにつき同時に利用できる客は一人である。個数をCと表す。
• クライアント：サービスを受けるためにやってきた人々。つまり商品を購入してレジに行く人のこと。
• 待ち行列：キューや待合室とも呼ばれる。クライアントが並んでサービスを受けるまで待たされる行列のこと。
• 系：システムとも呼ばれる。つまり待ち行列とサーバーのこと。
• 平均到着率：クライアントがポアソン分布に従って到着したとき(ポアソン過程)の単位時間当たりの個体数の平均のこと。つまりポアソン分布における平均のことである。$\lambda$ を文字としてよく使う。逆数はクライアントが一人到着するまでにかかる平均時間となる。
• 平均サービス率：処理時間が指数分布に従うサーバーが単位時間あたりに処理できるクライアントの数のこと。$\mu$を文字としてよく使う。逆数はサーバーが一つのクライアントに対してかかる時間となり平均サービス時間となる。
• トラフィック密度：$\frac{\lambda}{\mu}$のこと。通常$a$であらわす。
• 利用率：$\frac{\lambda}{c\mu}$のこと。通常$\rho$であらわす。0.7程度がいいとされている。1を超えると$\lambda$の方が大きくなるため処理が間に合わず行列がただただ伸びていくことになるので通常は$0<\rho \leq1$で考える。しかし1と等しい場合でもシステム的には改善が必要なため$0<\rho<1$の範囲で考えることが多い。
• 過度状態：系が時間によって変化している状態のこと。つまり不安定な状態。
• 定常状態：過度状態が時間経過で変化する系が時間によって変化しないような状態のこと。つまり安定な状態。
• 時刻$t$に系全体に$k$個のクライアントがいる確率：過度状態では$P_k(t)$で、定常状態では時間に関係ないので$P_k$と表現される。
• 系全体の平均客数：意味は名前の通り。文字は$L$で表す。$L=\sum_k kP_k$で求められる。
• 待ち行列内の平均客数：意味は名前の通り。文字は$L_q$で表す。$L_q=\sum_k \max(k-c, 0)P_k$で求められる。
• サーバー内の平均客数：意味は名前の通り。文字は$L_s$で表す。サーバーの利用率と一致。
• 系全体の平均待ち時間：意味は名前の通り。文字は$W$で表す。
• 待ち行列内の平均待ち時間：意味は名前の通り。文字は$W_q$で表す。
• 一つのサーバーにおける平均サービス時間時間：意味は名前の通り。文字は$W_s$で表す。 定義から$L=L_q+L_s$と$W=W_q+W_s=W_q+\frac{1}{\mu}$が成り立つことがわかる。

リトルの法則（リトルの公式）L=λW

Wikiによると

リトルの法則 (英:Little's law) あるいはリトルの定理(Little's theorem)とは、待ち行列理論において
安定な系において長時間平均化した顧客数 L は、長時間平均化した到着率λと、長時間平均化した顧客が系に費やす時間 W の積に等しい、すなわち
L=λW
という法則である。
本法則は直感的には理にかなったものであるが、対象がどのような確率分布であってもこの振る舞いをするという点と、到着した顧客やサービスする顧客に基づいてどのようにスケジュールするかについて何の仮定も設けない点は特筆すべきである。

とのことである。これは待ち行列に対しても成り立ち、$L_q=\lambda W_q$となる。またサーバーに対してはサーバーの数が1個なら成り立つが複数の場合もあるのでわからない。注意しないといけないのはリトルの公式は平均に対してでありどんな週刊でも成り立つというわけではない。さらに定常状態の時にしか成り立たないことにも注意しないといけない。リトルの公式の証明は省略する。

ケンドールの記号 A/B/C/X/Y/Z

Wiki参照。

• A：到着の過程。よく$M$や$E_k$や$G$が使われる。省略は不可。

記号	名称	説明
$M$	マルコフ過程（指数分布）	到着がポアソン過程となるランダム型。到着間隔は指数分布に従う。記号はMarkovianの頭文字。
$M_X$	バッチマルコフ	到着がポアソン過程となるランダム型で、Xずつ集団到着する型。
$MAP$	マルコフ到着過程	記号はMarkov Arrival Processの略記。
$BMAP$	バッチマルコフ到着過程	記号はBatch Markov Arrival Processの略記。
$MMPP$	マルコフ変調ポアソン過程	記号はMarkov Modulated Poisson Processの略記。
$D$	退化分布（単位分布）	到着間隔が一定の規則型。記号はDeterministicの頭文字。
$E_k$	位数kのアーラン分布	到着間隔が規則型とランダム型の中間である中間型（アーラン型）。
$G$	一般分布	到着間隔の詳細を問わない一般型。記号はGeneralの頭文字。
$GI$	一般な独立分布	到着間隔の詳細を問わない一般型。記号はGeneral Identifyの頭文字。
$PH$	相型分布	記号はPhase-typeの頭文字。

• B：サービス時間の分布。よく$M$や$E_k$や$G$が使われる。省略は不可。

記号	名称	説明
$M$	マルコフ過程（指数分布）	サービス時間が指数分布に従うランダム型。記号はMarkovianの頭文字。
$D$	退化分布（単位分布）	サービス時間が一定の規則型。記号はDeterministicの頭文字。
$E_k$	位数kのアーラン分布	サービス時間が規則型とランダム型の中間である中間型（アーラン型）。
$G$	一般分布	サービス時間の詳細を問わない一般型。記号はGeneralの頭文字。
$PH$	相型分布	記号はPhase-typeの頭文字。

• C：サーバーの個数。省略は不可。
• X：系全体に収容できるクライアントの個数。つまり$X-C$が待ち行列に並ぶことのできるクライアントの最大数。省略が可能で省略した場合$\infty$となる。また待ち行列に並ぶことができる個数として/Xの代わりに/X(X-C)と表記されることもある。ただし()内は待ち行列に並ぶことができるクライアントの最大数である。
• Y：系にやってくるクライアントの個数。来客数とも。省略が可能で省略された場合$\infty$となる。
• Z：サービスの規範でどのような順番でサービスを受けさせるかの条件。省略が可能で省略した場合FCFSとなる。

記号	名称	説明
FIFO(FCFS)	FIFO(FCFS)	最初に到着した客から順番にサービスを受ける。記号はFirst In First Out (First Come First Served)の略記。一般的なキューのこと。
LIFO(LCFS)	LIFO(LCFS)	最後に到着した客から順番にサービスを受ける。記号はLast In First Out (Last Come First Served)の略記。一般的なスタックのこと。
SIRO	SIRO	客は到着の順番にかかわらず、ランダムにサービスを受ける。記号はService In Random Orderの略記。
PS	PS	記号はProcessor Sharingの略記。 系内にn人の客がいるとき、それぞれの客に対してサーバーのもつ能力を1/nずつ均等に割り当て、同時にサービスを施す並列処理のこと. 計算機におけるCPUの動作モデルとしてよく用いられる。

実はこれ以外にも記号はいくつもあるらしい。

今回はここまでにします。次回は最も基本なM/M/1モデルのことを書いていこうかなと思います。