고든-뉴엘 정리

확률의 수학적 이론인 큐잉 이론에서, 고든-뉴엘 정리(Gordon-Newell theorem)는 오픈 큐잉 네트워크에서 고객이 네트워크를 떠날 수 없는 지수 서버의 클로즈드 큐잉 네트워크로 ^[1]잭슨의 정리를 확장한 것이다.잭슨의 정리는 폐쇄 네트워크 내의 노드의 큐 길이가 네트워크 모집단에 의해 제한되기 때문에 폐쇄 네트워크에 적용할 수 없습니다.Gordon-Newell 정리는 개방형 네트워크 솔루션을 계산한 후 확률을 정규화함으로써 실현 불가능한 상태를 제거합니다.전체 상태 공간을 열거해야 하므로 정규화 상수를 계산하면 처리가 더 어려워집니다.Buzen의 알고리즘 또는 평균값 분석을 사용하여 정규화 상수를 ^[2]보다 효율적으로 계산할 수 있습니다.

Gordon-Newell 네트워크의 정의

상호 연결된 m개의 큐 네트워크는 Gordon-Newell 네트워크^[3] 또는 다음 조건을 충족하는 경우 폐쇄형^[4] Jackson 네트워크라고 불립니다.

1. 네트워크가 닫혀 있다(네트워크에 출입할 수 없는 고객,
2. 모든 서비스 시간은 기하급수적으로 분산되며 모든 큐의 서비스 규율은 FCFS입니다.
3. 큐에서 서비스를 완료한 고객은 ${\displaystyle {\mathrm{Pi}}_{}}$ j$(\$의 ${\displaystyle {확률}_{}}$로 큐 j로 이동합니다.${\displaystyle {\mathrm{Pij}}_{}}$는 $\underset{}{\overset{}{}}$$(\$ ${\mathrm{P\_}}_{}$${ij})$입니다.$\underset{}{\overset{}{이}}$ 경우$,\underset{}{\overset{}{}}$ j ${}_{}$ $\underset{}{\overset{}{1}}${$textstyle \sum$ _${j=1}^{$m_ij}$P_{ij$
4. 모든 큐의 사용률이1 미만입니다

정리

m개의 큐로 이루어진 닫힌 Gordon-Newell 네트워크에서는 총 K개의 큐를 가진 (${\displaystyle {}_{}{}_{}}$1, ${\displaystyle {k\mathrm{}}_{}}$2,${\displaystyle \dots ,}$ ${\displaystyle k_{}}$m $){${($k_{1$},$k_{2},\ldots,k_{m}}}}}($여기서_i k는 네트워크 상태에 대해 큐 i의 길이)라고 입력합니다.

${\displaystyle S(K,m)=\left\{\mathbf {k}\in \mathbb {N}^{m}{\text{}}\sum _{i=1}^{m}k_{i}=K\right\}.}$

그러면 평형 상태 확률 분포가 존재하고 다음과 같이 주어집니다.

$\pi (k_{1},k_{2},\ldots,k_{m}=prod _{i=1}{m}\left\frac {e_{i}}{\mu _{i}}}\right)^{k_{i}}}$

여기서 큐 i의 서비스 시간은 파라미터_i μ에 의해 지수적으로 분포됩니다.정규화 상수 G(K)는 다음과 같습니다.

$\displaystyle G(K)=\sum _{\mathbf {k}\in S(K,m)}\prod _{i=1}^{m}\left\frac {e_{i}}{\mu _{i}}\right}^{k_{i}},$

그리고_i e는 방문비이며, 연립 방정식을 풀어서 계산됩니다.

${\displaystyle e_{i}=\sum _{j=1}^{m}e_{j}p_{ji}{\text{}1\leq i\leq m.}$

「 」를 참조해 주세요.

• BCMP 네트워크

레퍼런스