잭슨 네트워크

큐잉 이론에서, 확률의 수학적 이론 내의 한 분야인 잭슨 네트워크(때로는 잭슨^[1] 네트워크)는 네트워크가 제품 형태의 솔루션을 가지고 있기 때문에 평형 분포를 계산하기가 특히 쉬운 큐잉 네트워크의 클래스입니다.큐 네트워크 이론의 첫 번째 중요한 발전이었고, 다른 네트워크에서 유사한 제품 형태의 솔루션을 찾기 위해 정리 아이디어를 일반화하고 적용하는 것은 인터넷 ^[3]개발에 사용된 아이디어를 포함하여 많은 ^[2]연구의 주제가 되었다.네트워크는 처음에 James R에 의해 식별되었습니다. 잭슨과^[4]^[5] 그의 논문은 경영학 저널의 '경영학 최초 50년 10대 가장 영향력 있는 경영학 타이틀'에 재인쇄되었다.^[6]

잭슨은 Burke와 ^[7]Reich의 작품에서 영감을 얻었지만, Jean Walrand는 "제품 형태의 결과는 잭슨 자신이 그의 ^[8]기본 논문을 믿는 것처럼 보이는 결과보다 훨씬 덜 직접적인 결과이다."라고 언급했다.

R. R. P. Jackson은 탠덤 큐(각 고객이 순서대로 각 큐를 방문해야 하는 유한한 큐 체인) 및 순환 네트워크(각 고객이 ^[9]각 큐를 차례로 방문해야 하는 큐의 루프)에 대해 이전의 제품 형식 솔루션을 발견했습니다.

잭슨 네트워크는 다수의 노드로 구성되어 있습니다.여기서 각 노드는 서비스 레이트가 노드에 의존할 수 있는 큐(노드에 따라 서비스 레이트가 다르다)와 스테이트에 의존할 수 있는 큐(서비스 레이트가 큐 길이에 따라 변화한다)를 나타냅니다.작업은 고정 라우팅 매트릭스에 따라 노드 사이를 이동합니다.각 노드의 모든 작업은 단일 "클래스"에 속하며 작업은 동일한 서비스 시간 분포와 동일한 라우팅 메커니즘을 따릅니다.따라서 작업 제공 시 우선순위의 개념은 없습니다. 각 노드의 모든 작업은 선착순으로 제공됩니다.

한정된 수의 일자리가 닫힌 네트워크 주변을 이동하는 잭슨 네트워크도 고든-뉴엘 ^[10]정리에 의해 기술된 제품 형태의 솔루션을 가지고 있다.

잭슨 네트워크에 필요한 조건

상호 연결된 m개의 큐 네트워크는 다음 조건을 충족하는 경우 잭슨^[11] 네트워크 또는 잭슨 네트워크라고^[12] 불립니다.

네트워크가 열려 있는 경우 노드 i에 대한 외부 도착은 포아송 프로세스를 형성합니다.
모든 서비스 시간은 기하급수적으로 분산되며 모든 큐의 서비스 규율은 선착순입니다.
큐에서 서비스를 완료한 고객은 $P_{ij}$ j $(\$ $P_{ij}$ 의 $P_{ij}$ 새로운 큐 j로 이동하거나, 개방 네트워크의 경우 일부 큐의 경우 0이 아닌 확률 1 - $1-\sum _{j=1}^{m}P_{ij}$ j $1-\sum _{j=1}^{m}P_{ij}$ $1-\sum _{j=1}^{m}P_{ij}$ m $1-\sum _{j=1}^{m}P_{ij}$ $1-\sum _{j=1}^{m}P_{ij}$ $(\$ 1- $\sum$ _ ${j=1$ }^{ $m}P_{$ ij $1-\sum _{j=1}^{m}P_{ij}$ 를 시스템에 남깁니다.
모든 큐의 사용률이1 미만입니다

정리

M/M/1 큐의 오픈 Jackson 네트워크에서는 $(\$ _ ${i})$ 가 $\rho _{i}$ 모든 큐에서1 미만일 경우 평형상태 확률분포가 존재하며 상태 $\scriptstyle {(k_{1},k_{2},\ldots ,k_{m})}$ $\scriptstyle {(k_{1},k_{2},\ldots ,k_{m})}$ , $\scriptstyle {(k_{1},k_{2},\ldots ,k_{m})}$ , $\scriptstyle {(k_{1},k_{2},\ldots ,k_{m})}$ $\scriptstyle {(k_{1},k_{2},\ldots ,k_{m})}$ m $\scriptstyle {(k_{1},k_{2},\ldots ,k_{m})}$ ) { $displaystyle \scriptstyle {(k_1}, k_{2},$ \ $ldots,$ k_k $})$ 는 다음과 $\scriptstyle {(k_{1},k_{2},\ldots ,k_{m})}$ 같습니다 $.$ 가상 큐 평형 분포

\pi (k_{1},k_{2},\ldots,k_{m}=\display_{i}_{i}=\display_{i=1}^{m}[\rho_k_{i}(1-\rho_{i})].}

그 결과 π(k1, k2,…, km그리고 4.9초 만 m))∏ 나는 정도 1mπ 나는(k나는){\displaystyle\pi(k_{1},k_{2},\ldots ,k_{m})=\prod_{i=1}^{m}\pi _ᆮ(k_{나는})}또한 보유하고 있기 위해 M/M/c 모델 방송국과 더불지도 나쁘지도 않은 서버에서 ith{\displaystyle i^{\text{월}}}역으로 이용 요건 ρ 나는 <, 요리 나는{\di.spla $ystyle \rho$ _ ${i}$ < $c_{i$

정의.

공개 네트워크에서는 실업률 α 을과 포아송 과정 다음 밖에서,. 각각의 도착 독립적으로 확률 p와 0j≥ 0{\displaystyle p_{0j}\geq 0}일 경우 j 있는 노드와 j-1Jp0j=1{\displaystyle \sum_{j=1}^{J}p_{0j}=1∑}라우팅 됩니다. 서비스 completio에 따라 0{\displaystyle \alpha>0}도착한다.n에서 node i, 작업은 p $p_{i0}=1-\sum _{j=1}^{J}p_{ij}$ $(\$ 의 $p_{ij}$ 확률로 다른 노드 j $(\$ _ ${J}^{J}p_{ij$ 로 이동하거나 $p_{i0}=1-\sum _{j=1}^{J}p_{ij}$ 를 떠날 수 있습니다.

따라서 노드 i, § $\lambda _{i}$ \ $displaystyle \lambda$ _ ${i$ 에 대한 전체 도착률은 외부 도착과 내부 전환을 모두 포함합니다.

\displaystyle \lambda _{i}=\alpha p_{0i}+\sum _{j=1}^{J}\lambda _{ji},i=1,\ldots,J.\qquad (1)

(각 노드에서의 이용률은 1 미만이며, 장기 평균 행동 등 평형 분포를 검토하고 있기 때문에 j에서 i로의 작업 이행률은 j의 도착률의 극히 일부에 의해 제한되며, 위의 서비스 속도 $\mu _{j}$ j $(\$ _ ${j$ 는 무시된다.)

$a=(\alpha p_{0i})_{i=1}^{J}$ $a=(\alpha p_{0i})_{i=1}^{J}$ ( $a=(\alpha p_{0i})_{i=1}^{J}$ p $a=(\alpha p_{0i})_{i=1}^{J}$ i ) $a=(\alpha p_{0i})_{i=1}^{J}$ $=$ $a=(\alpha p_{0i})_{i=1}^{J}$ J (\ $displaystyle$ a=(\ $alpha p_{0i})_{i=1}^{J$ 를 정의하면 $=$ ( $\lambda =(I-P^{T})^{-1}a$ - $\lambda =(I-P^{T})^{-1}a$ ) - $\lambda =(I-P^{T})^{-1}a$ a \ $displaystyle \da$ =( $I-P^{T}^-1}a$ 를 해결할 수 있습니다.

모든 작업은 포아송 프로세스에도 따라 각 노드를 떠나며 노드 i에 $(\$ $})$ 작업이 $x_{i}$ $x_{i}$ 경우 노드 i의 서비스 환율로 $\mu _{i}(x_{i})$ i( $xi)$ 를 $\mu _{i}(x_{i})$ $\mu _{i}(x_{i})$ 합니다.

$X_{i}(t)$ i ( $X_{i}(t)$ ) $X_{i}(t)$ { $style$ X_ ${i}(t)}$ 는 $X_{i}(t)$ t시점의 노드 i에서의 작업 수를 $\mathbf {X} =(X_{i})_{i=1}^{J}$ , X $\mathbf {X} =(X_{i})_{i=1}^{J}$ ( $\mathbf {X} =(X_{i})_{i=1}^{J}$ i ) i $=$ $\mathbf {X} =(X_{i})_{i=1}^{J}$ { $displaystyle \mathbf {X} =$ ( $X_{i}_{i}^J$ 그런 다음 X $(\$ \ $mathbf$ ${X$ $\pi (\mathbf {x} )=P(\mathbf {X} =\mathbf {x} )$ ( $\pi (\mathbf {x} )=P(\mathbf {X} =\mathbf {x} )$ ) $\pi (\mathbf {x} )=P(\mathbf {X} =\mathbf {x} )$ ( $X =$ ) $= P(\mathbf {X}$ =\ $mathbf {x})$ 의 $\pi (\mathbf {x} )=P(\mathbf {X} =\mathbf {x} )$ 평형 분포는 다음과 같은 시스템 균형 방정식에 의해 결정됩니다.

{displaystyle}&\pi(\mathbf {x})\sum _{i=1}^{J}[\alpha p_{0i}+\mu _{i}(x_{i})(1-p_{i}) ] \\={}&\sum _{i=1}^{J}[\pi (\mathbf {x} -\mathbf {e} _{i})\alpha p_{0i} +\pi (\mathbf {x} +\mathbf {e} _{i} _{i})\mu} _{i} _{i} _{i}\qquad (2)\end {aligned}

$\mathbf {e} _{i}$ 서 e $(\$ 는 $\mathbf {e} _{i}$ $(\$ i $^{\text{th})$ 단위 $i^{\text{th}}$ 벡터를 나타냅니다.

정리

각 $(\$ 가 $Y_{i}$ 다음과 같은 확률 질량 함수를 갖는 독립 랜덤 변수 $Y$ 1, $(Y_{1},\ldots ,Y_{J})$ $)$ 의 벡터(Y_ ${1},\ldots,Y_{J})$ 를 $(Y_{1},\ldots ,Y_{J})$ 가정합니다.

{\displaystyle P(Y_{i}=n)=p(Y_{i}=0)\cdot {frac {\frac _{n}{M_{i}(n)},\quad (3)

여기서 Mi)∏ j=1nμ(n)나는}. 만약∑ nx1∞ λ 나는 Mi(n)<>에 담아라;∞{\displaystyle \sum_{n=1}^{\infty}{\frac{\lambda_{나는}^{n}}{M_{나는}(n)}}<>\infty}포지티브 P(Y나는 0조향 개시))(1+∑ nx1∞ λ 나의 Mi(n){\displaystyle M_{나는}(n)=\prod _{j=1}^{n}\mu _ᆳ(j)(j). ) $P(Y_{i}=0)=\left(1+\sum _{n=1}^{\infty }{\frac {\lambda _{i}^{n}}{M_{i}(n)}}\right)^{-1}$ $P(Y_{i}=0)=\left(1+\sum _{n=1}^{\infty }{\frac {\lambda _{i}^{n}}{M_{i}(n)}}\right)^{-1}$ {\ $displaystyle$ P $(Y_{i}=0$ }=\ $left(1+\sum$ _{ $n=1}^{\infty}{\frac {blac$ _ ${i}{n}}}{M_{i}}}}}{-$ 1}}이 $P(Y_{i}=0)=\left(1+\sum _{n=1}^{\infty }{\frac {\lambda _{i}^{n}}{M_{i}(n)}}\right)^{-1}$ 잘 정의되어 있으며, 오픈 잭슨 네트워크의 평형 분포는 다음과 같습니다.

\displaystyle \pi(\mathbf {x})=\display_{i=1}^{J}P(Y_{i}=x_{i}).}

$\mathbf {x} \in {\mathcal {Z}}_{+}^{J}$ x $\mathbf {x} \in {\mathcal {Z}}_{+}^{J}$ Z $\mathbf {x} \in {\mathcal {Z}}_{+}^{J}$ + $\mathbf {x} \in {\mathcal {Z}}_{+}^{J}$ \ $displaystyle$ \ $mathbf$ { $x }$ \ $in$ \ $mathcal$ { $Z$ } _ { + }^{ $J}$ $\mathbf {x} \in {\mathcal {Z}}_{+}^{J}$ 。

증명

$등식$ (2 $)(\displaystyle (2))$ 이 $(2)$ 충족되는지 확인하는 것으로 충분합니다.제품 형태 및 식 (3)에 따라 다음과 같은 것이 있습니다.

(\displaystyle \pi (\mathbf {x} +\mathbf {e} _{i} _{i} )\mu _{i} /\mathbf {x} +\mathbf {e} _{i} )_{i}\pi (\mathbf {x} +\mathbf {e} _i} _mu {i} _mu {i} )

이들을( $2)$ 의 $오른쪽$ 에 $(2)$ 대입하면 다음과 같은 결과를 얻을 수 있습니다 $.$

({displaystyle _{i=1}^{J}[\alpha p_{0i}+\mu _{i}(1-p_{i})]=\sum _{i=1}^{J}[\frac {alpha p_{i}{\mu_{i}_{i})\qquad (4)}

그런 $다음$ (1)을 사용합니다.\ $displaystyle$ ( $1)$ 에는 다음이 있습니다.

({displaystyle _{i=1}^{J}\sum _{j\neq i}{\frac {i}}{ij}=\sum _{j=1}^{J}[\sum _i\neq }{frac}{frac})}

위의 내용을 ( $4)$ {style $(4$ 로대체하면 다음과 같습니다.

\displaystyle \sum _{i=1}^{J}\alpha p_{0i}=\sum _{i=1}^{J}\lambda _{i}p_{i0}

이는 $\sum _{i=1}^{J}\alpha p_{0i}=\sum _{i=1}^{J}\lambda _{i}-\sum _{i=1}^{J}\sum _{j=1}^{J}\lambda _{j}p_{ji}=\sum _{i=1}^{J}\lambda _{i}-\sum _{j=1}^{J}\lambda _{j}(1-p_{j0})=\sum _{i=1}^{J}\lambda _{i}p_{i0}$ i $\sum _{i=1}^{J}\alpha p_{0i}=\sum _{i=1}^{J}\lambda _{i}-\sum _{i=1}^{J}\sum _{j=1}^{J}\lambda _{j}p_{ji}=\sum _{i=1}^{J}\lambda _{i}-\sum _{j=1}^{J}\lambda _{j}(1-p_{j0})=\sum _{i=1}^{J}\lambda _{i}p_{i0}$ $\sum _{i=1}^{J}\alpha p_{0i}=\sum _{i=1}^{J}\lambda _{i}-\sum _{i=1}^{J}\sum _{j=1}^{J}\lambda _{j}p_{ji}=\sum _{i=1}^{J}\lambda _{i}-\sum _{j=1}^{J}\lambda _{j}(1-p_{j0})=\sum _{i=1}^{J}\lambda _{i}p_{i0}$ J $\sum _{i=1}^{J}\alpha p_{0i}=\sum _{i=1}^{J}\lambda _{i}-\sum _{i=1}^{J}\sum _{j=1}^{J}\lambda _{j}p_{ji}=\sum _{i=1}^{J}\lambda _{i}-\sum _{j=1}^{J}\lambda _{j}(1-p_{j0})=\sum _{i=1}^{J}\lambda _{i}p_{i0}$ p $\sum _{i=1}^{J}\alpha p_{0i}=\sum _{i=1}^{J}\lambda _{i}-\sum _{i=1}^{J}\sum _{j=1}^{J}\lambda _{j}p_{ji}=\sum _{i=1}^{J}\lambda _{i}-\sum _{j=1}^{J}\lambda _{j}(1-p_{j0})=\sum _{i=1}^{J}\lambda _{i}p_{i0}$ $\sum _{i=1}^{J}\alpha p_{0i}=\sum _{i=1}^{J}\lambda _{i}-\sum _{i=1}^{J}\sum _{j=1}^{J}\lambda _{j}p_{ji}=\sum _{i=1}^{J}\lambda _{i}-\sum _{j=1}^{J}\lambda _{j}(1-p_{j0})=\sum _{i=1}^{J}\lambda _{i}p_{i0}$ $\sum _{i=1}^{J}\alpha p_{0i}=\sum _{i=1}^{J}\lambda _{i}-\sum _{i=1}^{J}\sum _{j=1}^{J}\lambda _{j}p_{ji}=\sum _{i=1}^{J}\lambda _{i}-\sum _{j=1}^{J}\lambda _{j}(1-p_{j0})=\sum _{i=1}^{J}\lambda _{i}p_{i0}$ $\sum _{i=1}^{J}\alpha p_{0i}=\sum _{i=1}^{J}\lambda _{i}-\sum _{i=1}^{J}\sum _{j=1}^{J}\lambda _{j}p_{ji}=\sum _{i=1}^{J}\lambda _{i}-\sum _{j=1}^{J}\lambda _{j}(1-p_{j0})=\sum _{i=1}^{J}\lambda _{i}p_{i0}$ i $\sum _{i=1}^{J}\alpha p_{0i}=\sum _{i=1}^{J}\lambda _{i}-\sum _{i=1}^{J}\sum _{j=1}^{J}\lambda _{j}p_{ji}=\sum _{i=1}^{J}\lambda _{i}-\sum _{j=1}^{J}\lambda _{j}(1-p_{j0})=\sum _{i=1}^{J}\lambda _{i}p_{i0}$ $\sum _{i=1}^{J}\alpha p_{0i}=\sum _{i=1}^{J}\lambda _{i}-\sum _{i=1}^{J}\sum _{j=1}^{J}\lambda _{j}p_{ji}=\sum _{i=1}^{J}\lambda _{i}-\sum _{j=1}^{J}\lambda _{j}(1-p_{j0})=\sum _{i=1}^{J}\lambda _{i}p_{i0}$ J = $\sum _{i=1}^{J}\alpha p_{0i}=\sum _{i=1}^{J}\lambda _{i}-\sum _{i=1}^{J}\sum _{j=1}^{J}\lambda _{j}p_{ji}=\sum _{i=1}^{J}\lambda _{i}-\sum _{j=1}^{J}\lambda _{j}(1-p_{j0})=\sum _{i=1}^{J}\lambda _{i}p_{i0}$ $\sum _{i=1}^{J}\alpha p_{0i}=\sum _{i=1}^{J}\lambda _{i}-\sum _{i=1}^{J}\sum _{j=1}^{J}\lambda _{j}p_{ji}=\sum _{i=1}^{J}\lambda _{i}-\sum _{j=1}^{J}\lambda _{j}(1-p_{j0})=\sum _{i=1}^{J}\lambda _{i}p_{i0}$ $\sum _{i=1}^{J}\alpha p_{0i}=\sum _{i=1}^{J}\lambda _{i}-\sum _{i=1}^{J}\sum _{j=1}^{J}\lambda _{j}p_{ji}=\sum _{i=1}^{J}\lambda _{i}-\sum _{j=1}^{J}\lambda _{j}(1-p_{j0})=\sum _{i=1}^{J}\lambda _{i}p_{i0}$ $\sum _{i=1}^{J}\alpha p_{0i}=\sum _{i=1}^{J}\lambda _{i}-\sum _{i=1}^{J}\sum _{j=1}^{J}\lambda _{j}p_{ji}=\sum _{i=1}^{J}\lambda _{i}-\sum _{j=1}^{J}\lambda _{j}(1-p_{j0})=\sum _{i=1}^{J}\lambda _{i}p_{i0}$ $\sum _{i=1}^{J}\alpha p_{0i}=\sum _{i=1}^{J}\lambda _{i}-\sum _{i=1}^{J}\sum _{j=1}^{J}\lambda _{j}p_{ji}=\sum _{i=1}^{J}\lambda _{i}-\sum _{j=1}^{J}\lambda _{j}(1-p_{j0})=\sum _{i=1}^{J}\lambda _{i}p_{i0}$ $\sum _{i=1}^{J}\alpha p_{0i}=\sum _{i=1}^{J}\lambda _{i}-\sum _{i=1}^{J}\sum _{j=1}^{J}\lambda _{j}p_{ji}=\sum _{i=1}^{J}\lambda _{i}-\sum _{j=1}^{J}\lambda _{j}(1-p_{j0})=\sum _{i=1}^{J}\lambda _{i}p_{i0}$ $\sum _{i=1}^{J}\alpha p_{0i}=\sum _{i=1}^{J}\lambda _{i}-\sum _{i=1}^{J}\sum _{j=1}^{J}\lambda _{j}p_{ji}=\sum _{i=1}^{J}\lambda _{i}-\sum _{j=1}^{J}\lambda _{j}(1-p_{j0})=\sum _{i=1}^{J}\lambda _{i}p_{i0}$ $\sum _{i=1}^{J}\alpha p_{0i}=\sum _{i=1}^{J}\lambda _{i}-\sum _{i=1}^{J}\sum _{j=1}^{J}\lambda _{j}p_{ji}=\sum _{i=1}^{J}\lambda _{i}-\sum _{j=1}^{J}\lambda _{j}(1-p_{j0})=\sum _{i=1}^{J}\lambda _{i}p_{i0}$ $\sum _{i=1}^{J}\alpha p_{0i}=\sum _{i=1}^{J}\lambda _{i}-\sum _{i=1}^{J}\sum _{j=1}^{J}\lambda _{j}p_{ji}=\sum _{i=1}^{J}\lambda _{i}-\sum _{j=1}^{J}\lambda _{j}(1-p_{j0})=\sum _{i=1}^{J}\lambda _{i}p_{i0}$ $\sum _{i=1}^{J}\alpha p_{0i}=\sum _{i=1}^{J}\lambda _{i}-\sum _{i=1}^{J}\sum _{j=1}^{J}\lambda _{j}p_{ji}=\sum _{i=1}^{J}\lambda _{i}-\sum _{j=1}^{J}\lambda _{j}(1-p_{j0})=\sum _{i=1}^{J}\lambda _{i}p_{i0}$ $\sum _{i=1}^{J}\alpha p_{0i}=\sum _{i=1}^{J}\lambda _{i}-\sum _{i=1}^{J}\sum _{j=1}^{J}\lambda _{j}p_{ji}=\sum _{i=1}^{J}\lambda _{i}-\sum _{j=1}^{J}\lambda _{j}(1-p_{j0})=\sum _{i=1}^{J}\lambda _{i}p_{i0}$ = 1 J $\sum _{i=1}^{J}\alpha p_{0i}=\sum _{i=1}^{J}\lambda _{i}-\sum _{i=1}^{J}\sum _{j=1}^{J}\lambda _{j}p_{ji}=\sum _{i=1}^{J}\lambda _{i}-\sum _{j=1}^{J}\lambda _{j}(1-p_{j0})=\sum _{i=1}^{J}\lambda _{i}p_{i0}$ $\sum _{i=1}^{J}\alpha p_{0i}=\sum _{i=1}^{J}\lambda _{i}-\sum _{i=1}^{J}\sum _{j=1}^{J}\lambda _{j}p_{ji}=\sum _{i=1}^{J}\lambda _{i}-\sum _{j=1}^{J}\lambda _{j}(1-p_{j0})=\sum _{i=1}^{J}\lambda _{i}p_{i0}$ - $\sum _{i=1}^{J}\alpha p_{0i}=\sum _{i=1}^{J}\lambda _{i}-\sum _{i=1}^{J}\sum _{j=1}^{J}\lambda _{j}p_{ji}=\sum _{i=1}^{J}\lambda _{i}-\sum _{j=1}^{J}\lambda _{j}(1-p_{j0})=\sum _{i=1}^{J}\lambda _{i}p_{i0}$ j = 1 J = 1 J $\sum _{i=1}^{J}\alpha p_{0i}=\sum _{i=1}^{J}\lambda _{i}-\sum _{i=1}^{J}\sum _{j=1}^{J}\lambda _{j}p_{ji}=\sum _{i=1}^{J}\lambda _{i}-\sum _{j=1}^{J}\lambda _{j}(1-p_{j0})=\sum _{i=1}^{J}\lambda _{i}p_{i0}$ j = 1 J $\sum _{i=1}^{J}\alpha p_{0i}=\sum _{i=1}^{J}\lambda _{i}-\sum _{i=1}^{J}\sum _{j=1}^{J}\lambda _{j}p_{ji}=\sum _{i=1}^{J}\lambda _{i}-\sum _{j=1}^{J}\lambda _{j}(1-p_{j0})=\sum _{i=1}^{J}\lambda _{i}p_{i0}$ j $\sum _{i=1}^{J}\alpha p_{0i}=\sum _{i=1}^{J}\lambda _{i}-\sum _{i=1}^{J}\sum _{j=1}^{J}\lambda _{j}p_{ji}=\sum _{i=1}^{J}\lambda _{i}-\sum _{j=1}^{J}\lambda _{j}(1-p_{j0})=\sum _{i=1}^{J}\lambda _{i}p_{i0}$ 1 J λ j $\sum _{i=1}^{J}\alpha p_{0i}=\sum _{i=1}^{J}\lambda _{i}-\sum _{i=1}^{J}\sum _{j=1}^{J}\lambda _{j}p_{ji}=\sum _{i=1}^{J}\lambda _{i}-\sum _{j=1}^{J}\lambda _{j}(1-p_{j0})=\sum _{i=1}^{J}\lambda _{i}p_{i0}$ j $\sum _{i=1}^{J}\alpha p_{0i}=\sum _{i=1}^{J}\lambda _{i}-\sum _{i=1}^{J}\sum _{j=1}^{J}\lambda _{j}p_{ji}=\sum _{i=1}^{J}\lambda _{i}-\sum _{j=1}^{J}\lambda _{j}(1-p_{j0})=\sum _{i=1}^{J}\lambda _{i}p_{i0}$ ( 1 - p 0 $\sum _{i=1}^{J}\alpha p_{0i}=\sum _{i=1}^{J}\lambda _{i}-\sum _{i=1}^{J}\sum _{j=1}^{J}\lambda _{j}p_{ji}=\sum _{i=1}^{J}\lambda _{i}-\sum _{j=1}^{J}\lambda _{j}(1-p_{j0})=\sum _{i=1}^{J}\lambda _{i}p_{i0}$ ) $\sum _{i=1}^{J}\alpha p_{0i}=\sum _{i=1}^{J}\lambda _{i}-\sum _{i=1}^{J}\sum _{j=1}^{J}\lambda _{j}p_{ji}=\sum _{i=1}^{J}\lambda _{i}-\sum _{j=1}^{J}\lambda _{j}(1-p_{j0})=\sum _{i=1}^{J}\lambda _{i}p_{i0}$ 1 $\sum _{i=1}^{J}\alpha p_{0i}=\sum _{i=1}^{J}\lambda _{i}-\sum _{i=1}^{J}\sum _{j=1}^{J}\lambda _{j}p_{ji}=\sum _{i=1}^{J}\lambda _{i}-\sum _{j=1}^{J}\lambda _{j}(1-p_{j0})=\sum _{i=1}^{J}\lambda _{i}p_{i0}$ = $\sum _{i=1}^{J}\alpha p_{0i}=\sum _{i=1}^{J}\lambda _{i}-\sum _{i=1}^{J}\sum _{j=1}^{J}\lambda _{j}p_{ji}=\sum _{i=1}^{J}\lambda _{i}-\sum _{j=1}^{J}\lambda _{j}(1-p_{j0})=\sum _{i=1}^{J}\lambda _{i}p_{i0}$ $\sum _{i=1}^{J}\alpha p_{0i}=\sum _{i=1}^{J}\lambda _{i}-\sum _{i=1}^{J}\sum _{j=1}^{J}\lambda _{j}p_{ji}=\sum _{i=1}^{J}\lambda _{i}-\sum _{j=1}^{J}\lambda _{j}(1-p_{j0})=\sum _{i=1}^{J}\lambda _{i}p_{i0}$ $\sum _{i=1}^{J}\alpha p_{0i}=\sum _{i=1}^{J}\lambda _{i}-\sum _{i=1}^{J}\sum _{j=1}^{J}\lambda _{j}p_{ji}=\sum _{i=1}^{J}\lambda _{i}-\sum _{j=1}^{J}\lambda _{j}(1-p_{j0})=\sum _{i=1}^{J}\lambda _{i}p_{i0}$ i p i p i p i p i p i p i p i p i p i p i p i p i p i p i p i p i p i $a$ _ ${j}p_{$ ji $}=\sum$ _{ $i=1}^{J}\lambda _{i}-\sum$ _{ $j=1}^{J}=\sum$ _{ $i=1}^{J}\lambda$ _{ $i}p_i0$ $따라서$ $($ 2 $)$ 의 $(2)$ 양쪽(\displaystyle $(2)$ ⟨

이 정리는 각 노드의 상태 의존 서비스 레이트를 허용함으로써 위의 정리를 확장합니다.독립 $\mathbf {Y}$ Y의 벡터에 의한 X $(\$ $displaystyle \mathbf {X$ 의 $\mathbf {X}$ 분포를 $\mathbf {X}$ $.$

예

3노드 오픈 잭슨 네트워크

그래프에 3노드의 Jackson 네트워크가 있다고 가정하면 계수는 다음과 같습니다.

\displaystyle \alpha = 5,\display p_{01}=p_{02}=0.5,\display p_{03}=0,\display }

{\displaystyle P=begin{bmatrix}0&0.5&0.5\\0&0\0&0\end{bmatrix},\mu \mu = spec{bmatrix}\mu _{1}(x_{2})\\mu _{3}\end{bmatrix}=spec{bmatrix}\1012

그런 다음 이 정리를 통해 다음을 계산할 수 있습니다.

\displaystyle \batda =(I-P^{T)^{-1}a=begin{bmatrix}1&0\-0.5&1&0\end{bmatrix}{-1}{\begin{bmatrix}0.5 곱하기 55\times 5\\0\end {bmatrix}=param {bmatrix}1&0\0.5&1&0\0.5&0&1\end{bmatrix}{\colid{bmatrix}2.5\2.5\\0\end{bmatrix}=420{bmatrix}2.5\\3.75\125\end {bmatrix}}

Y $(\$ 의 $\mathbf {Y}$ 에 따라 다음과 같은 것이 있습니다.

P(Y_{1}=0)=\left(\sum _{n=0}^{\infty}\leftfrac {2.5}{15}\right)^{n}\right)^{-1}=black {5}{6}

P(Y_{2}=0)=\left(\sum _{n=0}^{\infty}\leftfrac {3.75}{12}\right)^{n}\right)^{-1}=black {11}{16}

P(Y_{3}=0)=\left(\sum _{n=0}^{\infty}\leftfrac {1.25}{10}\right)^{n}\right)^{-1}=black {7}{8}

따라서 각 노드에 1개의 작업이 존재할 가능성은 다음과 같습니다.

(\displaystyle \pi (1,1)=cdfrac {5}{6}\cdot {frac {2.5}{15}\cdot {frac {11}{16}\cdot {frac {3.75}{12}}\cdot {8}\cdot {frac {1.25}{10}}}}\cdot 06}입니다.

여기서의 서비스 레이트는 상태에 따라 달라지지 않기 때문에 $(\$ Y_ ${i$ })는 $Y_{i}$ 단순히 기하학적 분포를 따릅니다.

범용 잭슨 네트워크

Jackson의 일반화 네트워크는 포아송 프로세스일 필요가 없는 갱신 도착 프로세스와 독립적이고 동일한 비지수 서비스 시간을 허용합니다.일반적으로 이 네트워크에는 제품 형태의 고정 분포가 없기 때문에 근사치가 ^[13]요구됩니다.

브라운 근사

오픈 범용 잭슨 네트워크의 큐 길이^{[clarification needed]} $Q(t)$ ( $Q(t)$ ) \ $displaystyle$ Q ( $t$ ) $Q(t)$ $\operatorname {RBM} _{Q(0)}(\theta ,\Gamma ;R).$ $\operatorname {RBM} _{Q(0)}(\theta ,\Gamma ;R).$ $\operatorname {RBM} _{Q(0)}(\theta ,\Gamma ;R).$ ( $\operatorname {RBM} _{Q(0)}(\theta ,\Gamma ;R).$ )로 정의된 반사된 Brownian 모션으로 근사할 수 있습니다 $.{$ $displaystyle \operatorname$ { $RBM$ $_ { Q$ ( $0 Ta )$ $\operatorname {RBM} _{Q(0)}(\theta ,\Gamma ;R).$ ( $여기서 {\$ { $displaystyle$ \theta $\theta$ }는 $\theta$ 프로세스의 드리프트, ${\$ { $displaystyle$ \ Gamma $}$ 는 $\Gamma$ 공분산 매트릭스, $R$ { $displaystyle$ R $}$ 은 반사 매트릭스 $)$ 이것은 일반적인 잭슨 네트워크와 균질 유체 네트워크와 반사된 브라운 운동 사이의 관계에 의해 얻어진 2차 근사치이다.

반사된 Brownian 프로세스의 매개변수는 다음과 같이 지정됩니다.

\displaystyle \theta =\alpha - (I-P^{T})\mu }

(\displaystyle \Gamma =(\Gamma _{k\ell}){\text{{k\ell}}=\sum _{j=1}^{J}(\sum \mu _{j})[p_{jk}(\ell}-p_{jk}^{c})

R=I-P^{T}

여기서 기호는 다음과 같이 정의됩니다.

근사 공식에서 기호의 정의
기호.	의미.
$\alpha =(\alpha _{j})_{j=1}^{J$	각 노드에 대한 도착 속도를 지정하는 J 벡터.
$\mu =(\mu)_{j=1}^{J$	각 노드의 서비스 레이트를 지정하는 J벡터.
$P$	라우팅 매트릭스
$\displaystyle \displayda _{j}$	$j^{\text{th}}$ $th$ {\ $displaystyle j^{\text{$ th $j^{\text{th}}$ }}} 노드의 $j^{\text{th}}$ 도착.
$c_{j}$	$j^{\text{th}}$ {\ $displaystyle$ j $^{\text{th}}$ 노드에서의 $j^{\text{th}}$ $j^{\text{th}}$ 시간의 변동.
$c_{0,j}$	$j^{\text{th}}$ ${\$ j $^{\text{th}}}$ 노드에서의 $j^{\text{th}}$ $j^{\text{th}}$ 간 시간 변동.
${\displaystyle_{ij}}$	계수를 사용하여 노드 간의 상관 관계를 지정합니다. 다음과 $A(t)-\alpha t{}\approx {\hat {A}}(t)$ $정의$ 됩니다. $A(t)-\alpha t{}\approx {\hat {A}}(t)$ $A(t)$ ( t $A(t)$ ) { $displaystyle$ A $($ t ) $A(t)-\alpha t{}\approx {\hat {A}}(t)$ 、 $A(t)-\alpha t{}\approx {\hat {A}}(t)$ A $A(t)-\alpha t{}\approx {\hat {A}}(t)$ ( $A(t)-\alpha t{}\approx {\hat {A}}(t)$ ) - $A(t)-\alpha t{}\approx {\hat {A}}(t)$ $t$ A $A(t)-\alpha t{}\approx {\hat {A}}(t)$ ^ ( t $A(t)-\alpha t{}\approx {\hat {A}}(t)$ ) \ $display$ { A $}$ \ $approx$ { A $A(t)-\alpha t{}\approx {\hat {A}}(t)$ （ $t$ ）。 ${\hat {A}}(t)$ 서 ${\hat {A}}(t)$ A ${\hat {A}}(t)$ ( ${\hat {A}}(t)$ ) \ $style$ { ${\hat {A}}(t)$ A （ t ） ${\hat {A}}(t)$ 。 $\Gamma ^{0}=(\Gamma _{ij}^{0})$ ( $\Gamma _{ij}^{0}=\alpha _{i}c_{0,i}^{2}\delta _{ij}$ $\Gamma _{ij}^{0}=\alpha _{i}c_{0,i}^{2}\delta _{ij}$ $\Gamma ^{0}=(\Gamma _{ij}^{0})$ j $\Gamma ^{0}=(\Gamma _{ij}^{0})$ 0 ) ( \ $displaystyle$ \ $Gamma$ ^ { 0 $\Gamma _{ij}^{0}=\alpha _{i}c_{0,i}^{2}\delta _{ij}$ } = ( \ $Gamma _$ { $\Gamma _{ij}^{0}=\alpha _{i}c_{0,i}^{2}\delta _{ij}$ $}^{$ 0 $\Gamma ^{0}=(\Gamma _{ij}^{0})$ $\Gamma ^{0}=(\Gamma _{ij}^{0})$ i $\Gamma _{ij}^{0}=\alpha _{i}c_{0,i}^{2}\delta _{ij}$ $\Gamma _{ij}^{0}=\alpha _{i}c_{0,i}^{2}\delta _{ij}$ i $j$ \ $displaystyle$ \ $Gamma _ {$ { $ij$ }^{ $0 }$ ）、 { $displaysty}$ 、 { i } } $。$

「」를 참조해 주세요.

레퍼런스

^ Walrand, J.; Varaiya, P. (1980). "Sojourn Times and the Overtaking Condition in Jacksonian Networks". Advances in Applied Probability. 12 (4): 1000–1018. doi:10.2307/1426753. JSTOR 1426753.
^ Kelly, F. P. (June 1976). "Networks of Queues". Advances in Applied Probability. 8 (2): 416–432. doi:10.2307/1425912. JSTOR 1425912.
^ Jackson, James R. (December 2004). "Comments on "Jobshop-Like Queueing Systems": The Background". Management Science. 50 (12): 1796–1802. doi:10.1287/mnsc.1040.0268. JSTOR 30046150.
^ Jackson, James R. (Oct 1963). "Jobshop-like Queueing Systems". Management Science. 10 (1): 131–142. doi:10.1287/mnsc.1040.0268. JSTOR 2627213. 1963년 1월 이후 버전은 http://www.dtic.mil/dtic/tr/fulltext/u2/296776.pdf에서 구할 수 있습니다.
^ Jackson, J. R. (1957). "Networks of Waiting Lines". Operations Research. 5 (4): 518–521. doi:10.1287/opre.5.4.518. JSTOR 167249.
^ Jackson, James R. (December 2004). "Jobshop-Like Queueing Systems". Management Science. 50 (12): 1796–1802. doi:10.1287/mnsc.1040.0268. JSTOR 30046149.
^ Reich, Edgar (September 1957). "Waiting Times When Queues are in Tandem". Annals of Mathematical Statistics. 28 (3): 768. doi:10.1214/aoms/1177706889. JSTOR 2237237.
^ Walrand, Jean (November 1983). "A Probabilistic Look at Networks of Quasi-Reversible Queues". IEEE Transactions on Information Theory. 29 (6): 825. doi:10.1109/TIT.1983.1056762.
^ Jackson, R. R. P. (1995). "Book review: Queueing networks and product forms: a systems approach". IMA Journal of Management Mathematics. 6 (4): 382–384. doi:10.1093/imaman/6.4.382.
^ Gordon, W. J.; Newell, G. F. (1967). "Closed Queuing Systems with Exponential Servers". Operations Research. 15 (2): 254. doi:10.1287/opre.15.2.254. JSTOR 168557.
^ Goodman, Jonathan B.; Massey, William A. (December 1984). "The Non-Ergodic Jackson Network". Journal of Applied Probability. 21 (4): 860–869. doi:10.2307/3213702.
^ Walrand, J.; Varaiya, P. (December 1980). "Sojourn Times and the Overtaking Condition in Jacksonian Networks". Advances in Applied Probability. 12 (4): 1000–1018. doi:10.2307/1426753.
^ Chen, Hong; Yao, David D. (2001). Fundamentals of Queueing Networks: Performance, Asymptotics, and Optimization. Springer. ISBN 0-387-95166-0.

[1] Walrand, J.; Varaiya, P. (1980). "Sojourn Times and the Overtaking Condition in Jacksonian Networks". Advances in Applied Probability. 12 (4): 1000–1018. doi:10.2307/1426753. JSTOR 1426753.

[2] Kelly, F. P. (June 1976). "Networks of Queues". Advances in Applied Probability. 8 (2): 416–432. doi:10.2307/1425912. JSTOR 1425912.

[3] Jackson, James R. (December 2004). "Comments on "Jobshop-Like Queueing Systems": The Background". Management Science. 50 (12): 1796–1802. doi:10.1287/mnsc.1040.0268. JSTOR 30046150.

[jackson-4] Jackson, James R. (Oct 1963). "Jobshop-like Queueing Systems". Management Science. 10 (1): 131–142. doi:10.1287/mnsc.1040.0268. JSTOR 2627213. 1963년 1월 이후 버전은 http://www.dtic.mil/dtic/tr/fulltext/u2/296776.pdf에서 구할 수 있습니다.

[5] Jackson, J. R. (1957). "Networks of Waiting Lines". Operations Research. 5 (4): 518–521. doi:10.1287/opre.5.4.518. JSTOR 167249.

[6] Jackson, James R. (December 2004). "Jobshop-Like Queueing Systems". Management Science. 50 (12): 1796–1802. doi:10.1287/mnsc.1040.0268. JSTOR 30046149.

[7] Reich, Edgar (September 1957). "Waiting Times When Queues are in Tandem". Annals of Mathematical Statistics. 28 (3): 768. doi:10.1214/aoms/1177706889. JSTOR 2237237.

[8] Walrand, Jean (November 1983). "A Probabilistic Look at Networks of Quasi-Reversible Queues". IEEE Transactions on Information Theory. 29 (6): 825. doi:10.1109/TIT.1983.1056762.

[9] Jackson, R. R. P. (1995). "Book review: Queueing networks and product forms: a systems approach". IMA Journal of Management Mathematics. 6 (4): 382–384. doi:10.1093/imaman/6.4.382.

[10] Gordon, W. J.; Newell, G. F. (1967). "Closed Queuing Systems with Exponential Servers". Operations Research. 15 (2): 254. doi:10.1287/opre.15.2.254. JSTOR 168557.

[11] Goodman, Jonathan B.; Massey, William A. (December 1984). "The Non-Ergodic Jackson Network". Journal of Applied Probability. 21 (4): 860–869. doi:10.2307/3213702.

[12] Walrand, J.; Varaiya, P. (December 1980). "Sojourn Times and the Overtaking Condition in Jacksonian Networks". Advances in Applied Probability. 12 (4): 1000–1018. doi:10.2307/1426753.

[13] Chen, Hong; Yao, David D. (2001). Fundamentals of Queueing Networks: Performance, Asymptotics, and Optimization. Springer. ISBN 0-387-95166-0.

[1]

[3]

[2]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

v t 큐잉 이론
단일 큐잉 노드	D/M/1 큐 M/D/1 큐 M/D/C 큐 M/M/1 큐 버크의 정리 M/M/c 큐 M/M/오브로드 큐 M/G/1 큐 폴라체크-킨차인 공식 매트릭스 분석법 M/G/k 큐 G/M/1 큐 G/G/1 큐 킹맨 공식 린들리 방정식 포크 결합 큐 벌크 큐
도착 프로세스	포아송 점 과정 마르코프 도착 과정 합리적인 도착 과정
네트워크 큐잉	잭슨 네트워크 트래픽 방정식 고든-뉴엘 정리 평균값 분석 부젠 알고리즘 켈리 네트워크 G네트워크 BCMP 네트워크
서비스 정책	선입선출 라이프 프로세서 공유 라운드 로빈 최단 시간 작업 최단 남은 시간
주요 개념	연속 시간 마르코프 연쇄 켄달 표기법 리틀의 법칙 제품형태솔루션 균형 방정식 준가역성 흐름 등가 서버 방식 도착 정리 분해법 베네시법
한계 정리	유체 한계 평균장 이론 혼잡한 트래픽의 근사치 반사 브라운 운동
내선번호	유체 큐 레이어드 큐잉 네트워크 폴링 시스템 적대 큐잉 네트워크 손실 네트워크 재심 큐
정보 시스템	데이터 버퍼 Erlang(유닛) 얼랑 분포 흐름 제어(데이터) 메시지 큐 네트워크 폭주 네트워크 스케줄러 파이프라인(소프트웨어) 서비스 품질 스케줄링(컴퓨팅) 텔레트래픽 공학
카테고리

Search

잭슨 네트워크

네임스페이스

더

목차

잭슨 네트워크에 필요한 조건

정리

정의.

정리

예

범용 잭슨 네트워크

브라운 근사

「」를 참조해 주세요.

레퍼런스

Search

잭슨 네트워크

잭슨 네트워크에 필요한 조건

정리

정의.

정리

예

범용 잭슨 네트워크

브라운 근사

「 」를 참조해 주세요.

레퍼런스

「」를 참조해 주세요.