Analiza wartości średniej

W teorii kolejek , dyscyplinie należącej do matematycznej teorii prawdopodobieństwa , analiza wartości średniej ( MVA ) jest rekurencyjną techniką obliczania oczekiwanych długości kolejek, czasu oczekiwania w węzłach kolejkowania i przepustowości w równowadze dla zamkniętego, rozdzielnego systemu kolejek. Pierwsze przybliżone techniki zostały opublikowane niezależnie przez Schweitzera i Barda, a później dokładna wersja Lavenberga i Reisera opublikowana w 1980 roku.

Opiera się na twierdzeniu o przybyciu , które mówi, że gdy jeden klient w zamkniętym systemie M -klientów przybywa do obiektu usługowego, obserwuje, że reszta systemu jest w stanie równowagi dla systemu z M -1 klientami.

Konfiguracja problemu

Rozważmy zamkniętą sieć kolejek K M/M/1 kolejek z M klientami krążącymi w systemie. Załóżmy, że klienci są nie do odróżnienia od siebie, więc sieć ma jedną klasę klientów. Aby obliczyć średnią długość kolejki i czas oczekiwania w każdym z węzłów oraz przepustowość systemu, używamy algorytmu iteracyjnego rozpoczynającego się od sieci z 0 klientami.

Zapisz μ _i dla szybkości obsługi w węźle i oraz P dla macierzy kierowania klientów, gdzie element pij oznacza prawdopodobieństwo, że klient kończący usługę w węźle i przesunie się do węzła j w celu wykonania usługi _. Aby użyć algorytmu, najpierw obliczamy wektor wierszowy wskaźnika odwiedzin v , wektor taki, że v = v P.

Teraz napisz L _i ( n ) dla średniej liczby klientów w kolejce i , gdy w systemie jest łącznie n klientów (wliczając w to zadanie aktualnie obsługiwane w kolejce i ) oraz W _j ( n ) dla średniego czasu spędzonego przez klienta w kolejce i, gdy w systemie jest łącznie n klientów. Oznacz przepustowość systemu z m klientami przez λ _m .

Algorytm

Algorytm rozpoczyna się od pustej sieci (zero klientów), a następnie zwiększa liczbę klientów o 1 w każdej iteracji, aż do uzyskania wymaganej liczby ( M ) klientów w systemie.

Aby zainicjować, ustaw L _k (0) = 0 dla k = 1,..., K . (To ustawia średnią długość kolejki w systemie bez klientów na zero we wszystkich węzłach).

Powtórz dla m = 1,..., M :

1. Dla k = 1, ..., K oblicz czas oczekiwania w każdym węźle, korzystając z twierdzenia o przybyciu

${\ Displaystyle W_ {k} (m) = {\ Frac {1 + L_ {k} \ lewo (m-1 \ prawo)} {\ mu _ {k}}}.} 2. Następnie oblicz przepustowość systemu za$

pomocą Prawo Little'a

${\ Displaystyle \ lambda _ {m} = {\ Frac {m} {\ suma _ {k = 1} ^ {K} W_ {k} (m) v_ {k}}}.} 3. Na koniec użyj Little$

's prawo zastosowane do każdej kolejki w celu obliczenia średniej długości kolejki dla k = 1, ..., K

${\ Displaystyle L_ {k} (m) = v_ {k} \ lambda _ {m} W_ {k} (m).}$

Zakończ powtórkę.

Metoda Barda-Schweitzera

Przybliżenie Barda-Schweitzera szacuje, że średnia liczba zadań w węźle k wynosi

${\ Displaystyle L_ {k} (m-1) \ około {\ Frac {m-1} {m}} L_ {k} (m) }$

co jest interpolacją liniową. Z powyższych wzorów to przybliżenie daje relacje punktu stałego , które można rozwiązać numerycznie. To podejście iteracyjne często nosi nazwę przybliżonej MVA (AMVA) i jest zazwyczaj szybsze niż podejście rekurencyjne MVA.

Pseudo kod

zestaw L _k ( m ) = M / K

powtarzaj aż do zbieżności:

${\ Displaystyle \ lambda _ {m} = {\ Frac {m} {\ suma _ {k = 1} ^ {K}{\frac {{\frac {m-1}{m}}L_{k}(m)+1}{\mu _{k}}}v_{k}}}}$

${\ Displaystyle L_ {k} (m) = v_ {k} \ lambda _ {m} {\ Frac {{\ Frac {m-1} {m}} L_ {k} (m) + 1} {\mu _{k}}}}$

Sieci wieloklasowe

W przypadku sieci wieloklasowych z R klasami klientów, każda kolejka k może charakteryzować się różnymi stawkami usług μ _k,r dla każdej klasy zadań r=1,...,R , chociaż istnieją pewne ograniczenia w przypadku kolejności zgłoszeń -obsługiwane stacje ze względu na założenia twierdzenia BCMP w przypadku wieloklasowym.

Czas oczekiwania W _k,r doświadczany przez zadania klasy r w kolejce k nadal może być powiązany z całkowitą średnią długością kolejki w węźle k za pomocą uogólnienia twierdzenia o przybyciu

${\ Displaystyle W_ {k, r} (\ mathbb {m.}) = {\ Frac {1 + L_ {k} \ lewo (\ mathbb {m} -1_ {r} \ prawej)}} {\ mu _ {k ,R}}}.}$

gdzie ${\ Displaystyle \ mathbb {m} = (m_ {1}, \ ldots, m_ {R})}$ jest wektorem populacji klientów dla klas R i ${ \displaystyle 1_ {r}}$ odejmuje jeden od r -tego elementu , zakładając, że $geq 1}$$displaystyle m_ {r}$ .

Dla sieci z jedną klasą klientów algorytm MVA jest bardzo szybki, a czas rośnie liniowo wraz z liczbą klientów i liczbą kolejek. Jednak w modelach wieloklasowych liczba mnożeń i dodawań oraz wymagania dotyczące przechowywania MVA rosną wykładniczo wraz z liczbą klas klientów. W praktyce algorytm działa dobrze dla 3-4 klas klientów, chociaż generalnie zależy to od implementacji i struktury modelu. Na przykład metodę Tree-MVA można skalować do większych modeli, jeśli macierz routingu jest rzadka.

Dokładne wartości średnich metryk wydajności można uzyskać w dużych modelach za pomocą metody momentów , która wymaga czasu logarytmiczno-kwadratowego. Metoda momentów może w praktyce rozwiązywać modele z maksymalnie 10 klasami klientów lub czasami większymi, które są zwykle niedostępne za pomocą dokładnej MVA. Technika ta jednak nie wykorzystuje twierdzenia o przybyciu i polega na rozwiązywaniu układów równań liniowych z udziałem stałej normalizującej prawdopodobieństw stanu dla sieci kolejkowej.

Przybliżone algorytmy MVA (AMVA), takie jak metoda Barda-Schweitzera, oferują zamiast tego alternatywną technikę rozwiązania, która zapewnia niską złożoność również w sieciach wieloklasowych i zazwyczaj dostarcza bardzo dokładne wyniki.

Rozszerzenia

Algorytm analizy wartości średniej został zastosowany do klasy modeli PEPA opisujących sieci kolejkowe i wydajność kluczowego centrum dystrybucji .

Oprogramowanie

• JMVA , narzędzie napisane w Javie , które implementuje MVA.
• queuing , biblioteka dla GNU Octave , która zawiera MVA.
• Line , zestaw narzędzi MATLAB, który zawiera dokładne i przybliżone algorytmy MVA.

Zobacz też

• Teoria kolejek

Linki zewnętrzne

• J. Virtamo: Sieci kolejkowe . Materiały informacyjne z Helsinki Tech dają dobry przegląd twierdzenia Jacksona i MVA.
• Simon Lam: Proste wyprowadzenie algorytmu MVA . Pokazuje związek między algorytmem Buzena a MVA.