Kolejka M/D/1

W teorii kolejek , dyscyplinie w ramach matematycznej teorii prawdopodobieństwa , kolejka M/D/1 reprezentuje długość kolejki w systemie z jednym serwerem, gdzie przybycia są określane przez proces Poissona , a czasy obsługi zadań są ustalone (deterministyczne). Nazwa modelu jest zapisana notacją Kendalla . Agner Krarup Erlang po raz pierwszy opublikował ten model w 1909 roku, rozpoczynając temat teorii kolejek . Rozszerzeniem tego modelu o więcej niż jeden serwer jest kolejka M/D/c .

Definicja modelu

Kolejka M/D/1 to proces stochastyczny, którego przestrzenią stanów jest zbiór {0,1,2,3,...}, gdzie wartość odpowiada liczbie jednostek w systemie, włączając w to wszystkie obecnie działające.

• Przyjazdy następują z szybkością λ zgodnie z procesem Poissona i przenoszą proces ze stanu i do stanu i + 1.
• Czasy obsługi to czas deterministyczny D (obsługa z szybkością μ = 1/ D ).
• Pojedynczy serwer obsługuje jednostki pojedynczo z przodu kolejki, zgodnie z dyscypliną „kto pierwszy, ten lepszy” . Po wykonaniu usługi podmiot opuszcza kolejkę, a liczba podmiotów w systemie zmniejsza się o jeden.
• Bufor ma nieskończony rozmiar, więc nie ma ograniczeń co do liczby jednostek, które może zawierać.

Matryca przejść

Macierz prawdopodobieństwa przejścia dla kolejki M/D/1 z szybkością przybycia λ i czasem obsługi 1, tak że λ <1 (dla stabilności kolejki) jest dana przez P jak poniżej:

${\ Displaystyle P = {\ rozpocząć {pmatrix} a_ {0}& a_ {1}& a_ {2}& a_ {3}&...\\ a_ {0}& a_ {1}& a_ {2}& a_ {3}& ...\\0&a_{0}&a_{1}&a_{2}&...\\0&0&a_{0}&a_{1}&...\\...&...&...&. ..&...\\\koniec {pmacierz}}}$ ， ${\ Displaystyle a_ {n} = {\ Frac {\ lambda ^ {n}} {n!}} e ^ {- \ lambda}}$ , n = 0,1, ....

Klasyczne wskaźniki wydajności

Poniższe wyrażenia przedstawiają klasyczne metryki wydajności pojedynczego systemu kolejkowania serwera, takiego jak M/D/1, przy czym:

• wskaźnik przybycia ${\ Displaystyle = \ lambda}$ ,
• stawka za usługę ${\ displaystyle = \ mu}$ i
• wykorzystanie ${\ Displaystyle = \ rho = {\ Frac {\ lambda} {\ mu}}}$

Średnia liczba podmiotów w systemie, L jest dana wzorem:

${\ Displaystyle L = \ rho + {\ Frac {1} {2}} \ lewo ({\ Frac {\ rho ^ {2}} {1- \ rho}} \ prawo);}$

Średnia liczba podmiotów w kolejce (linii), L _Q jest dana wzorem:

${\ Displaystyle L_ {Q} = {\ Frac {1} {2}} \ lewo ({\ Frac {\ rho ^ {2}} {1- \ rho}} \ prawo);}$

Średni czas oczekiwania w systemie, ω, wyraża się wzorem:

${\ Displaystyle \ omega = {\ Frac {1} {\ mu}} + {\ Frac {\ rho} {2 \ mu (1-\ rho)}};}$

Średni czas oczekiwania w kolejce (linii), ω _Q jest określony wzorem:

${\ Displaystyle \ omega _ {Q} = {\ Frac {\ rho} {2 \ mu (1- \ rho)}}}$

Przykład

Biorąc pod uwagę system, który ma tylko jeden serwer, z szybkością nadejścia 20 jednostek na godzinę, a szybkość obsługi jest stała na poziomie 30 na godzinę.

Zatem wykorzystanie serwera wynosi: ρ=20/30=2/3. Korzystając z metryk pokazanych powyżej, wyniki są następujące: 1) Średnia liczba w linii L _Q = 0,6667; 2) Średnia liczba w systemie L = 1,333; 3) Średni czas w kolejce ω _Q = 0,033 godziny; 4) Średni czas w systemie ω = 0,067 godziny.

Relacje dla średniego czasu oczekiwania w kolejkach M/M/1 i M/D/1

Dla równowagowej kolejki M/G/1 oczekiwana wartość czasu W spędzonego przez klienta w kolejce jest określona wzorem Pollaczka-Khintchine’a jak poniżej:

${\ Displaystyle E (W) = {\ Frac {\ rho \ tau} {2 (1- \ rho)}} \ lewo (1+ {\ frac {\ sigma ^ {2}} {\ tau ^ {2}}} \ prawo)}$

gdzie τ to średni czas obsługi; σ ² to wariancja czasu obsługi; oraz ρ=λτ < 1, gdzie λ oznacza wskaźnik przybycia klientów.

Dla kolejki M/M/1 czasy obsługi rozkładają się wykładniczo, wtedy σ ² = τ ² , a średni czas oczekiwania w kolejce oznaczony jako W _M wyraża się następującym równaniem:

${\ Displaystyle {W_ {M}} = {\ Frac {\ rho \ tau} {1- \ rho}}}$

Korzystając z tego, można wyprowadzić odpowiednie równanie dla kolejki M/D/1, zakładając stałe czasy obsługi. Wówczas wariancja czasu obsługi wynosi zero, czyli σ ² = 0. Średni czas oczekiwania w kolejce M/D/1 oznaczony jako W _D wyraża się wzorem:

${\ Displaystyle {W_ {D}} = {\ Frac {\ rho \ tau} {2 (1- \ rho)}}}$

Z dwóch powyższych równań możemy wywnioskować, że średnia długość kolejki w kolejce M/M/1 jest dwa razy większa niż w kolejce M/D/1.

Dystrybucja stacjonarna

Liczbę zadań w kolejce można zapisać jako łańcuch Markowa typu M/G/1 i znaleźć rozkład stacjonarny dla stanu i (zapisany π _i ) w przypadku D = 1

${\ Displaystyle {\ rozpocząć {wyrównane} \ pi _ {0} & = 1- \ lambda \\\ pi _ {1} & = (1- \ lambda) (e ^ {\ lambda} -1) \\\ pi _{n}&=(1-\lambda )\left(e^{n\lambda }+\suma _{k=1}^{n-1}e^{k\lambda }(-1)^ {nk}\left[{\frac {(k\lambda)^{nk}}{(nk)!}}+{\frac {(k\lambda)^{nk-1}}{(nk-1) !}}\right]\right)\quad (n\geq 2).\end{wyrównane}}}$

Opóźnienie

Zdefiniuj ρ = λ / μ jako wykorzystanie; wtedy średnie opóźnienie w systemie w kolejce M/D/1 wynosi

${\ Displaystyle {\ Frac {1} {2 \ mu}} \ cdot {\ Frac {2- \ rho} {1- \ rho}}.}$

a w kolejce:

${\ Displaystyle {\ Frac {1} {2 \ mu}} \ cdot {\ Frac {\ rho} {1-\ rho}}.}$

Zajęty okres

Okres zajętości to czas mierzony od momentu pojawienia się pierwszego klienta w pustej kolejce do czasu, gdy kolejka jest ponownie pusta. Ten okres czasu jest równy D razy liczba obsługiwanych klientów. Jeżeli ρ < 1, to liczba klientów obsłużonych w okresie największego ruchu w kolejce ma rozkład Borela z parametrem ρ .

Skończona pojemność

Dystrybucja stacjonarna

Rozkład stacjonarny dla liczby klientów w kolejce i średniej długości kolejki można obliczyć za pomocą funkcji generujących prawdopodobieństwo .

Rozwiązanie przejściowe

Rozwiązanie przejściowe kolejki M/D/1 o skończonej pojemności N, często zapisywane jako M/D/1/N, zostało opublikowane przez Garcię i in. w 2002.

Aplikacja

projektowania sieci rozległych , w których pojedynczy centralny procesor odczytuje nagłówki pakietów przychodzących w sposób wykładniczy, a następnie oblicza następny adapter, do którego powinien trafić każdy pakiet, i odpowiednio wysyła pakiety. Tutaj czas usługi to przetwarzanie nagłówka pakietu i cykliczna kontrola redundancji, które są niezależne od długości każdego przybywającego pakietu. W związku z tym można ją modelować jako kolejkę M/D/1.