Teoria kolejek: Formuła Erlanga-C i dlaczego rho bliskie 1 to klif

Kolejka, której przewidywanie może jedynie teoria

Obserwując kolej, wydaje się ona nieprzewidywalna -- czasami jest pusta, czasami nagle długotrwała, nawet gdy średnia prędkość przybywania ludzi i średnia prędkość obsługi pozostają stałe. Teoria kolejek wyjaśnia to wydaje się przypadkowe zachowanie dwoma założeniami, które okazują się modelować ogromny zakres rzeczywistych systemów: przybywania są procesem Poissona (niezależne, bez pamięci, o jakiejś średniej prędkości lambda) a czasy obsługi są rozłożone wykładniczo (średnia prędkość mu na każdym otwartym serwerze). System oparty na tych dwóch założeniach z c równoległymi serwerami nazywany jest w notacji Kendall'a M/M/c kolejką -- dwie M'y oznaczają 'Markowian', skrótem dla bez pamięci.

Bez pamięci to nieoczekiwane, podstawowe założenie: czas obsługi wykładniczy nie ma pojęcia o 'przebiegającym się' – prawdopodobieństwo zakończenia zadania w kolejnych 30 sekund jest takie samo, czyli od chwili rozpoczęcia zadania 10 sekund temu lub 10 minut temu. Ta jedna właściwość sprawia, że cała system jest ciągiem Markowa z prosto obliczalną formułą zamkniętą, a nie system, dla którego musi być śledzone jego przeszłe historie.

Użycie i mur dla ρ = 1

Definiujemy intensywność ruchu ρ = λ / (c · μ) – ułamka całkowitego zasobu usługi rzeczywistego użytkowania. Dopóki ρ pozostaje poniżej 1, kolejka osiąga stabilny równowagowy stan, w którym średnia długość i czekanie fluctuuje wokół pewnej wartości ograniczonej. Gdy ρ zbliża się do 1 z przeciwnego kierunku, długość kolejki i czas oczekiwania obie wybuchają, nie liniowo, ale około jak 1 / (1 - ρ): kolejka przy użyciu 80% jest w żadnym razie dwukrotnie gorsza niż ta przy użyciu 40%, jest dramatycznie gorsza, a kolejka przy użyciu 95% jest znacznie gorsza jeszcze bardziej. To niewspółliniowe klif powoduje, że centra telefoniczne, kliniki i routerzy sieci są zawsze celowo prowadzone poniżej pełnej pojemności – 100% użycie wygląda na efektywne na papierze, ale w praktyce jest katastrofą kolejkowania.

rho = lambda / (c · mu)              traffic intensity (utilisation), must stay < 1
Lq  ~ rho / (1 - rho)   for a single-server queue -- diverges as rho -> 1

Erlang-C: dokładna forma założona pod kątem personelu centrum dzwonkowego

Dla c serwerów, dokładna prawdopodobieństwo, że przybywający klient znajdzie wszystkie serwery zajęte i będzie musiał czekać — zamiast powyższego przybliżenia dla jednego serwera — jest podane przez formułę Erlanga-C, opublikowaną w 1917 roku przez Agnera Krarupa Erlanga do oceny wymaganych rozmiarów przystrojów telefonicznych w Danii i nadal stanowiącą podstawę oprogramowania personelu centrum dzwonkowego. Ze względu na to prawdopodobieństwo czekania, standardowe relacje (wspólnie z Zakonem Little’a, L = λ · W) przekształcają się prosto w średnią liczbę klientów czekających Lq oraz średni czas czekania Wq.

Zasada Little'a: jedna formuła nie wymagająca żadnych założeń

Niezależnie od przybywania zgodnego z rozkładem Poisona, wyjazdu eksponencjalnego lub jakiegokolwiek innego rozkładu, Zasada Little'a stawia na tym, że długoterminowy średni liczebny stan systemu L równa się średniej prędkości przybywania lambdy pomnożonej przez średni czas przebywania przedmiotu w systemie W: L = lambda · W. Ta zasada jest prawdziwa dla kasjerów w sklepie, oddziałów szpitalnych lub pakietów w buforze routera, a jej moc polega na tym, że nie wymaga modelowania mechanicznych szczegółów wewnętrznego działania systemu – wystarczy liczyć, ile wejdzie i jak długo pozostanie.

Dlaczego więcej, mniejszych kolejek jest gorsze niż jedna wspólna kolejka

Klasyczny i przeciwny do intuicji wynik: dla tej samej całościowej zdolności usługi, jedna wspólna kolejka dostarczająca c serwerów (jak w większości współczesnych centrów telefonicznych i linii bezpieczeństwa w lotniskach) zawsze daje krótszy średni czas oczekiwania niż c oddzielnych jednoserverowych kolejek (jak stare systemy kasjerowe w sklepach). To jest dokładnie powód, dla którego banki, pocztówki i lotniska przeniosły się od wielu równoległych linii do jednej serpentinowej kolejki dostarczającej kasjera, który wolny będzie nastąpić następnym.

Często zadawane pytania

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz Queueing Theory i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.