読む編集履歴表示

ケンドールの記号

ウィキペディアから、無料の百科事典

待ち行列理論において、ケンドールの記号（Kendall's notation、Kendall notation）とは、待ち行列モデルを説明および分類するのに使われる標準的な表現方法である。

1953年に、David George Kendallによって、列（キュー）の特徴を描写するための3要因が「A/B/C」の表現方法で提案された。これは最大6つの異なる要因を含ませることまで拡張できる。

この表現方法は、例えば現在待ち行列理論の分野で最も標準的な記法として使われている。

表記

列（キュー）は、「A/B/C/K/N/D」又はより簡単な「A/B/C」によって略記表記で表現される。後者の簡単な表記では、以下のように見なされる。

表記の「A」の部分は、到着の過程・分布を示している。

この部分で使われる記号は以下のとおりである。

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

表記の「B」の部分は、サービス時間の分布を示している。

この部分で使われる記号は以下のとおりである。

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

表記の「C」の部分は、サービスチャネルの数（サーバーの台数や、窓口の数など）を示している。

システムに収容できる客の容量を示す。すなわち、サービスを受けている客の数とそれ以外のサービスを待っている客の収容可能数の総和で表される。これは、サービス窓口の数と待合室における収容可能人数の和に相当する。「K」が省略された場合、K = ∞ (列の人数に制限がない)と見なされる。

システムに来る客の最大値を示す。「N」が省略された場合、N = ∞と見なされる。

表記の「D」の部分は、どのような順番で客がサービスを受けるかのルールを示している。「D」が省略された場合、D = FIFOであるとされる。

この部分で使われる記号は以下のとおりである。

記号	名称	説明
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の略記。
PNPN	PNPN
PS	PS	記号はProcessor Sharingの略記。