sieć Jacksona

W teorii kolejek , dyscyplinie należącej do matematycznej teorii prawdopodobieństwa , sieć Jacksona (czasami sieć Jacksona ) jest klasą sieci kolejek, w których rozkład równowagi jest szczególnie prosty do obliczenia, ponieważ sieć ma rozwiązanie w postaci produktu . Był to pierwszy znaczący postęp w teorii sieci kolejek , a uogólnienie i zastosowanie idei twierdzenia do poszukiwania podobnych rozwiązań w postaci produktów w innych sieciach było przedmiotem wielu badań, w tym pomysłów wykorzystanych w rozwoju Internetu. Sieci zostały po raz pierwszy zidentyfikowane przez Jamesa R. Jacksona , a jego artykuł został przedrukowany w czasopiśmie Management Science „ Ten Most Influential Titles of Management Sciences First Fifty Years”.

Jackson zainspirował się pracami Burke'a i Reicha, chociaż Jean Walrand zauważa, że ​​​​„wyniki w postaci produktu… [są] znacznie mniej bezpośrednim wynikiem twierdzenia o wyjściu, niż sam Jackson wydawał się wierzyć w swoim podstawowym artykule”.

Wcześniejsze rozwiązanie w postaci produktu zostało znalezione przez RRP Jackson dla kolejek tandemowych (skończony łańcuch kolejek, w których każdy klient musi odwiedzać każdą kolejkę w kolejności) i sieci cyklicznych (pętla kolejek, w której każdy klient musi odwiedzać każdą kolejkę w kolejności).

Sieć Jacksona składa się z wielu węzłów, gdzie każdy węzeł reprezentuje kolejkę, w której stawka za usługę może być zarówno zależna od węzła (różne węzły mają różne stawki za usługę), jak i zależna od stanu (stawki za usługę zmieniają się w zależności od długości kolejki). Zadania przemieszczają się między węzłami zgodnie z ustaloną macierzą routingu. Wszystkie zadania w każdym węźle należą do jednej „klasy”, a zadania mają ten sam rozkład czasu obsługi i ten sam mechanizm routingu. W związku z tym nie ma pojęcia priorytetu w obsłudze zadań: wszystkie zadania w każdym węźle są obsługiwane na zasadzie „kto pierwszy, ten lepszy” .

Sieci Jacksona, w których skończona populacja miejsc pracy przemieszcza się po zamkniętej sieci, również mają rozwiązanie w postaci produktu opisane przez twierdzenie Gordona – Newella .

Niezbędne warunki dla sieci Jacksona

Sieć m połączonych ze sobą kolejek jest znana jako sieć Jacksona lub sieć Jacksona , jeśli spełnia następujące warunki:

1. jeśli sieć jest otwarta, wszelkie zewnętrzne przybycia do węzła i tworzą proces Poissona ,
2. Wszystkie czasy obsługi są rozłożone wykładniczo, a dyscyplina obsługi we wszystkich kolejkach to kto pierwszy, ten lepszy ,
3. klient kończący usługę w kolejce i albo przejdzie do jakiejś nowej kolejki $opuści$ , albo system z prawdopodobieństwem ${\ Displaystyle 1-\ suma _{j=1}^{m}P_{ij}}$ , która dla sieci otwartej jest różna od zera dla pewnego podzbioru kolejek,
4. wykorzystanie wszystkich kolejek jest mniejsze niż jedna .

Twierdzenie

W otwartej sieci Jacksona m M / M / 1 kolejek ${\ Displaystyle \ scriptstyle {(k_ {1}, k_ {2}, \ ldots, k_ {m})}}$ w których wykorzystanie jest mniejsze niż 1 w każdej kolejce, istnieje rozkład prawdopodobieństwa stanu równowagi i $dla$ jest określone przez iloczyn rozkładów równowagi poszczególnych kolejek

${\ Displaystyle \ pi (k_ {1}, k_ {2}, \ ldots, k_ {m}) = \ prod _ {i = 1} ^ {m} \ pi _ {i} (k_ {i}) = \prod _{i=1}^{m}[\rho _{i}^{k_{i}}(1-\rho _{i})].}$

π ${\ Displaystyle \ pi (k_ {1}, k_ {2}, \ ldots, k_ {m$ dotyczy również stacji modelowych M / M / c z serwerami c _i na ${\ displaystyle i ^ Stacja {\text{th}}}$ z wymaganiami dotyczącymi wykorzystania ${\ Displaystyle \ rho _ {i}<c_ {i}}$ .

Definicja

W otwartej sieci zadania napływają z zewnątrz zgodnie z procesem Poissona z szybkością ${\ displaystyle \ alpha > 0}$ . Każde przybycie jest niezależnie kierowane do węzła j z prawdopodobieństwem ${\ Displaystyle p_ {0j} \ geq 0}$ i ${\ Displaystyle \ suma _ {j = 1} ^ {J} p_ {0j}=1}$ . Po zakończeniu usługi w węźle i zadanie może z prawdopodobieństwem przejść do innego węzła j ${\ Displaystyle p_ {ij}}$ lub opuścić sieć z prawdopodobieństwem ${\ Displaystyle p_ {i0} = 1- \ suma _ {j = 1} ^ { J}p_{ij}}$ .

Stąd mamy ogólny wskaźnik przybycia do węzła , w tym zarówno przyjazdy zewnętrzne, jak i przejścia wewnętrzne: ja , ${\ displaystyle \ lambda _ {i}}$

${\ Displaystyle \ lambda _ {i} = \ alfa p_ {0i} + \ suma _ {j = 1} ^ {J} \ lambda _ {j} p_ {ji}, i = 1, \ ldots, J.\qquad (1)}$

(Ponieważ wykorzystanie w każdym węźle jest mniejsze niż 1 i patrzymy na rozkład równowagi, tj. długoterminowe średnie zachowanie, tempo przechodzenia miejsc pracy z j do i jest ograniczone przez ułamek wskaźnika przybywania w j i ignorujemy stawkę za usługę $)$ powyższym

Zdefiniuj $\ Displaystyle a = (\ alfa p_ {0i}) _ {i = 1} ^ {J}}$ , wtedy możemy rozwiązać ${\ Displaystyle \ lambda = (IP ^ {T}) ^ {- 1} a}$ .

$jako szybkość$ opuszczają każdy węzeł również zgodnie z procesem Poissona i definiują węzła i , gdy $x_ {i}}$ zadań w węźle i .

Niech ${\ Displaystyle X_ {i} (t)}$ oznacza liczbę zadań w węźle i w czasie t i ${\ Displaystyle \ mathbf {X} = ( X_{i})_{i=1}^{J}}$ . Następnie rozkład równowagi , $_$$jest$ określony przez następujący układ równań bilansowych

${\ Displaystyle {\ rozpocząć {wyrównane} i \ pi (\ mathbf {x}) \ suma _ {i = 1} ^ {J} [\ alfa p_ {0i} + \ mu _ {i} (x_ {i} )(1-p_{ii})]\\={}&\sum _{i=1}^{J}[\pi (\mathbf {x} -\mathbf {e} _{i})\alfa p_{0i}+\pi (\mathbf {x} +\mathbf {e} _{i})\mu _{i}(x_{i}+1)p_{i0}]+\suma _{i= 1}^{J}\suma _{j\neq i}\pi (\mathbf {x} +\mathbf {e} _{i}-\mathbf {e} _{j})\mu _{i} (x_{i}+1)p_{ij}.\qquad (2)\end{wyrównane}}}$

gdzie $\ Displaystyle \ mathbf {e} _ {i}}$ oznacza wektor jednostkowy ja $\ displaystyle i ^ {\ tekst {th}}}$ .

Twierdzenie

$}$ że wektor niezależnych zmiennych losowych ma masę prawdopodobieństwa ${\ Displaystyle (Y_ {1}, \ ldots, Y_ {J})$ funkcjonować jako

${\ Displaystyle P (Y_ {i} = n) = p (Y_ {i} = 0) \ cdot {\frac {\lambda _{i}^{n}}{M_{i}(n)}},\quad (3)}$

gdzie ${\ Displaystyle M_ {i} (n) = \ prod _ {j = 1} ^ {n} \ mu _ {i} (j)}$ . Jeśli ${\ Displaystyle \ suma _ {n = 1} ^ {\ infty}} {\ Frac {\ lambda _ {i} ^ {n}} {M_ { i}(n)}}<\infty }$ tj. ${\ Displaystyle P (Y_ {i} = 0) = \ lewo (1 + \ suma _ {n = 1} ^ {\ infty }{\frac {\lambda _{i}^{n}}{M_{i}(n)}}\right)^{-1}} jest dobrze zdefiniowany, to rozkład równowagi otwartej sieci Jacksona$ ma następująca postać produktu:

${\ Displaystyle \ pi (\ mathbf {x}) = \ prod _ {i = 1} ^ {J} P (Y_ {i} = x_ {i}).}$

dla wszystkich ${\ Displaystyle \ mathbf {x} \ in {\ mathcal {Z}} _ {+} ^ {J}}$ .⟩

Dowód

Wystarczy sprawdzić, $czy$ . Według formy produktu i wzoru (3) mamy:

${\ Displaystyle \ pi (\ mathbf {x}) = \ pi (\ mathbf {x} + \ mathbf {e} _ {i}) \ mu _ {i} (x_ {i} + 1) / \ lambda _{i}=\pi (\mathbf {x} +\mathbf {e} _{i}-\mathbf {e} _{j})\mu _{i}(x_{i}+1)\ lambda _{j}/[\lambda _{i}\mu _{j}(x_{j})]}$

Zastępując je po prawej stronie otrzymujemy: ${\ Displaystyle (2)}$

${\ Displaystyle \ suma _ {i = 1} ^ {J} [\ alfa p_ {0i} + \ mu _ {i} (x_ {i}) (1-p_ {ii})] = \ suma _{i=1}^{J}[{\frac {\alpha p_{0i}}{\lambda _{i}}}\mu _{i}(x_{i})+\lambda _{i} p_{i0}]+\sum _{i=1}^{J}\sum _{j\neq i}{\frac {\lambda _{i}}{\lambda _{j}}}p_{ij }\mu _{j}(x_{j}).\qquad (4)}$

Następnie użyj , mamy: ${\ Displaystyle (1)}$

${\ Displaystyle \ suma _ {i = 1} ^ {J} \ suma _ {j \ neq i} {\ Frac {\ lambda _ {i}}} {\ lambda _ {j}}} p_ {ij} \ mu _{j}(x_{j})=\sum _{j=1}^{J}[\sum _{i\neq j}{\frac {\lambda _{i}}{\lambda _{j }}}p_{ij}]\mu _{j}(x_{j})=\suma _{j=1}^{J}[1-p_{jj}-{\frac {\alpha p_{0j }}{\lambda _{j}}}]\mu _{j}(x_{j}).}$

Zastępując powyższe w , mamy: ${\ Displaystyle (4)}$

${\ Displaystyle \ suma _ {i = 1} ^ {J} \ alfa p_ {0i} = \ suma _ {i = 1} ^ { J}\lambda _{i}p_{i0}}$

Można to zweryfikować przez ${\ Displaystyle \ suma _ {i = 1} ^ {J} \ alfa p_ {0i} = \ suma _ {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}}$ . Stąd obie strony ${\ Displaystyle (2)}$ są równe.⟨

To twierdzenie rozszerza twierdzenie pokazane powyżej, dopuszczając zależną od stanu szybkość obsługi każdego węzła. Odnosi się ${\ displaystyle \ mathbf {Y}$ rozkładu przez wektor zmiennej niezależnej $}$ .

Przykład

Otwarta sieć Jacksona z trzema węzłami

Załóżmy, że mamy trójwęzłową sieć Jacksona pokazaną na wykresie, współczynniki to:

${\ Displaystyle \ alfa = 5, \ quad p_ {01} = p_ {02} = 0,5, \ quad p_ {03} = 0, \ quad}$

${\ Displaystyle P = {\ rozpocząć {bmatrix} 0 i 0,5 i 0,5 \\ 0 i 0 i 0 \\ 0 i 0 i 0 \ koniec {bmatrix}}, \ quad \ mu = {\ rozpocząć {bmatrix} \mu _{1}(x_{1})\\\mu _{2}(x_{2})\\\mu _{3}(x_{3})\end{bmatrix}}={\begin {bmatrix}15\\12\\10\end{bmatrix}}{\text{ dla wszystkich }}x_{i}>0}$

Następnie z twierdzenia możemy obliczyć:

${\ Displaystyle \ lambda = (IP ^ {T}) ^ {-1} a = {\ rozpocząć {bmatrix} 1 i 0 i 0 \\ -0,5 i 1 i 0 \\ -0,5 i 0 i 1 \ koniec {bmatrix}} ^ {- 1} {\ begin{bmatrix}0,5\times 5\\0,5\times 5\\0\end{bmatrix}}={\begin{bmatrix}1&0&0\\0,5&1&0\\0,5&0&1\end{bmatrix}}{\begin{bmatrix }2,5\\2,5\\0\koniec{bmacierzy}}={\rozpoczęcie{bmacierzy}2,5\\3,75\\1,25\koniec{bmacierzy}}}$

Zgodnie z definicją mamy: ${\ displaystyle \ mathbf {Y}}$

${\ Displaystyle P (Y_ {1} = 0) = \ lewo (\ suma _ {n = 0} ^ {\ infty }\left({\frac {2.5}{15}}\right)^{n}\right)^{-1}={\frac {5}{6}}}$

${\ Displaystyle P (Y_ {2} = 0) = \ lewo (\ suma _ {n = 0} ^ {\ infty} \ lewo ({\ Frac {3,75} {12}} \ prawo) ^ { n} \ prawej) ^ {-1} = {\ Frac {11} {16}}}$

${\ Displaystyle P ( Y_{3}=0)=\left(\suma _{n=0}^{\infty}\left({\frac {1.25}{10}}\right)^{n}\right)^{- 1}={\frac {7}{8}}}$

Stąd prawdopodobieństwo, że w każdym węźle jest jedno zadanie, wynosi:

${\ Displaystyle \ pi (1,1,1) = {\ Frac {5} {6} }\cdot {\frac {2.5}{15}}\cdot {\frac {11}{16}}\cdot {\frac {3.75}{12}}\cdot {\frac {7}{8}}\ cdot {\frac {1.25}{10}}\około 0.00326}$

$Ponieważ$ stawka za usługę nie zależy tutaj od stanu, prostu mają rozkład geometryczny .

Uogólniona sieć Jacksona

Uogólniona sieć Jacksona umożliwia procesy przybycia odnowienia , które nie muszą być procesami Poissona, oraz niezależne, identycznie rozłożone niewykładnicze czasy obsługi. Ogólnie rzecz biorąc, ta sieć nie ma stacjonarnego rozkładu w postaci iloczynu , dlatego poszukuje się przybliżeń.

Przybliżenie Browna

, where $\operatorname {RBM} _{Q(0)}(\theta ,\Gamma ;R).$ łagodnych warunkach proces długości kolejki $uogólnionej sieci Jacksona$ przybliżyć za pomocą odbitego ruchu Browna zdefiniowanego jako $\ operatorname {RBM} _ {Q ($ is the drift of the process, $Gamma}$$.$ to macierz kowariancji, a to macierz odbicia Jest to przybliżenie dwurzędowe otrzymane z relacji między ogólną siecią Jacksona a jednorodną siecią płynu i odbitym ruchem Browna.

Parametry odbitego procesu Browna są określone następująco:

${\ Displaystyle \ theta = \ alfa - (IP ^ {T}) \ mu }$

$\ Displaystyle \ Gamma = (\ Gamma _ {k \ ell}) {\ text{ with }}\Gamma _{k\ell }=\suma _{j=1}^{J}(\lambda _{j}\klin \mu _{j})[p_{jk}(\delta _{k\ell }-p_{j\ell })+c_{j}^{2}(p_{jk}-\delta _{jk})(p_{j\ell }-\delta _{j\ ell })]+\alpha _{k}c_{0,k}^{2}\delta _{k\ell }}$

${\ Displaystyle R = IP ^ {T}}$

gdzie symbole są zdefiniowane jako:

Definicje symboli we wzorze aproksymacyjnym

symbol	Oznaczający
${\ Displaystyle \ alfa = (\ alfa _ {j}) _ {j = 1} ^ {J}}$	wektor J określający współczynniki przybycia do każdego węzła.
${\ Displaystyle \ mu = (\ mu) _ {j = 1} ^ {J}}$	wektor J określający stawki usług dla każdego węzła.
${\ displaystyle P.}$	macierz routingu.
${\ Displaystyle \ lambda _ {j}}$	efektywne przybycie węzła ${\ displaystyle j ^ {\ text {th}}}$ .
${j}}$	zmienność czasu obsługi w węźle ${\ displaystyle j ^ {\ tekst {th}}} .$
${\ displaystyle c_ {0, j}}$	zmienność czasu między przyjazdami w węźle ${\ displaystyle j ^ {\ tekst {th}}}$ .
${\ Displaystyle \ delta _ {ij}}$	współczynniki określające korelację między węzłami. $}$ one zdefiniowane w ten sposób: Niech $-$ α $- \ alfa t$$bezdryfowym$ w rozkładzie, gdzie procesem Browna z macierzą współzmiennych ${\ Displaystyle \ Gamma ^ {0} = (\ Gamma _ {ij} ^ {0})}$ z ${\ Displaystyle \ Gamma _ {ij} ^ {0} = \ alfa _ {i} c_ {0, i} ^ {2} \ delta _ {ij}}$ dla każdego ${\ Displaystyle i, j \ w \ {1,\kropki ,J\}}$

Zobacz też

• Sieć Gordona-Newella
• Sieć BCMP
• Sieć G
• Prawo Little'a