Algorytm Buzena

W teorii kolejek , dyscyplinie należącej do matematycznej teorii prawdopodobieństwa , algorytm Buzena (lub algorytm splotu ) jest algorytmem obliczania stałej normalizacji G ( N ) w twierdzeniu Gordona – Newella . Metoda ta została po raz pierwszy zaproponowana przez Jeffreya P. Buzena w 1973 roku. Obliczenie G( N ) jest wymagane do obliczenia stacjonarnego rozkładu prawdopodobieństwa zamkniętej sieci kolejkowej.

Wykonanie naiwnego obliczenia stałej normalizującej wymaga wyliczenia wszystkich stanów. Dla systemu z N zadaniami i stanami M istnieją kombinacje ${\ Displaystyle {\ tbinom {N + M-1} {M-1}}}$ Algorytm Buzena „oblicza G(1), G(2),…, G( N ) przy użyciu sumy mnożeń NM i dodatków NM ”. Jest to znacząca poprawa i pozwala na wykonywanie obliczeń w znacznie większych sieciach.

Konfiguracja problemu

Rozważmy zamkniętą sieć kolejek z M obiektami usługowymi i N krążącymi klientami. Napisz n _ja ( t ) dla liczby klientów obecnych w i- tym obiekcie w czasie t , tak że ${\ Displaystyle \ scriptstyle \ suma _ {i = 1} ^ {M} n_ {i}=N}$ . Zakładamy, że czas obsługi klienta w i- _tej placówce jest dany zmienną losową o rozkładzie wykładniczym o parametrze μi oraz że po zakończeniu obsługi w i- tej placówce klient uda się do j- tej placówki z prawdopodobieństwem p _ij .

twierdzenia Gordona-Newella wynika, że ​​rozkład równowagi tego modelu jest

${\ Displaystyle \ mathbb {P} (n_ {1}, n_ {2}, \ cdots ,n_{M})={\frac {1}{{\text{G}}(N)}}\prod _{i=1}^{M}\left(X_{i}\right)^ {n_{i}}}$

gdzie X _i można znaleźć rozwiązując

${\ Displaystyle \ mu _ {j} X_ {j} = \ suma _ {i = 1} ^ {M} \ mu _ {i} X_ {i} p_ {ij} \ quad {\ tekst {dla}} j =1,\ldkropki ,M.}$

a G ( N ) jest stałą normalizującą wybraną tak, że powyższe prawdopodobieństwa sumują się do 1.

Algorytm Buzena jest wydajną metodą obliczania G( N ).

Opis algorytmu

Zapisz g( N , M ) dla stałej normalizującej zamkniętej sieci kolejkowej z N klientami i M stacjami paliw. Algorytm rozpoczyna się od odnotowania rozwiązania powyższych zależności dla X _i , a następnie ustalenia warunków początkowych

${\ Displaystyle g (0, m) = 1 {\ tekst {dla}} m = 1,2, \ cdots, M}$

${\ Displaystyle g (n, 1) = (X_ {1}) ^ {n} {\ tekst {dla}} n = 0,1, \ cdots, N.}$

Relacja powtarzalności

${\ Displaystyle g (n, m) = g (n, m-1) + X_ {m} g (n-1, m).}$

służy do obliczania siatki wartości. Szukana wartość G( N ) = g( N , M ).

Rozkłady krańcowe, oczekiwana liczba klientów

Współczynniki g( n , m ), obliczone za pomocą algorytmu Buzena, można również wykorzystać do obliczenia rozkładów krańcowych i oczekiwanej liczby klientów w każdym węźle.

${\ Displaystyle \ mathbb {P} (n_{i}=k)={\frac {X_{i}^{k}}{G(N)}}[G(Nk)-X_{i}G(Nk-1)] \quad {\text{dla }}k=0,1,\ldots ,N-1,}$

${\ Displaystyle \ mathbb {P} (n_ {i} = N) = {\ Frac {X_ {i} ^ {N}} {G (N)}} [G (0)].}$

przewidywana liczba klientów w obiekcie i wg

${\ Displaystyle \ mathbb {E} (n_ {i}) = \ suma _ {k = 1} ^ {N} X_ {i} ^ {k} {\ Frac {G (Nk)} {G (N)} }.}$

Realizacja

Zakładamy, że X _m zostało obliczone poprzez rozwiązanie odpowiednich równań i jest dostępne jako dane wejściowe do naszej procedury. Chociaż g jest w zasadzie macierzą dwuwymiarową, można ją obliczyć kolumna po kolumnie, zaczynając od skrajnej lewej kolumny. Procedura używa jednokolumnowego wektora C do reprezentowania bieżącej kolumny g .

0  
        
     0

        
          
          C  [  ]  :=  1  dla  n  :=  1  krok  1  do  N  do  C  [  n  ]  :=  ;  dla  m  :=  1  krok  1  do  M  do  dla  n  :=  1  krok  1  do  N  do  C  [  n  ]  :=  C  [  n  ]  +  X  [  m  ]  *  C  [  n  -  1  ]  ; 

Po zakończeniu C zawiera żądane wartości G(0), G(1) do G(N) .

• Jain: The Convolution Algorithm (materiały klasowe)
• Menasce: Konwolucyjne podejście do algorytmów kolejkowania (prezentacja)