🎫 Teoria kolejek

M/M/c to notacja Kendalla dla systemu kolejkowego z napływami markowowskimi (Poissona), markowowskimi (wykładniczymi) czasami obsługi oraz c równoległymi serwerami. Pierwsze M oznacza, że czas między przybyciami ma rozkład wykładniczy, drugie M oznacza, że czas obsługi każdego serwera ma rozkład wykładniczy, a c to liczba identycznych serwerów pracujących równolegle. Ta symulacja implementuje dokładnie ten model, uruchamiając przybycia i odejścia jako dyskretne zdarzenia losowe na symulowanym zegarze.

Obciążenie ρ = λ/(cμ) to część całkowitej zdolności obsługowej, która jest wykorzystywana, gdzie λ to tempo napływu, a cμ to łączne tempo obsługi wszystkich c serwerów. Gdy ρ jest wyraźnie poniżej 1, serwery nadążają, a kolejka pozostaje krótka. Gdy ρ zbliża się do 1, serwery są niemal zawsze zajęte, więc każdy losowy wzrost liczby przybyć nie ma dokąd trafić i kolejka oczekujących rośnie coraz bardziej. Przy ρ ≥ 1 przybycia całkowicie przewyższają zdolność obsługową i kolejka rośnie bez ograniczeń.

Erlang-C to wzór w postaci zamkniętej, obliczający dokładne statystyki stanu ustalonego dla kolejki M/M/c bezpośrednio na podstawie λ, μ i c, bez konieczności uruchamiania symulacji. Podaje prawdopodobieństwo, że przybywający klient będzie musiał czekać, a na tej podstawie wyznacza oczekiwaną liczbę oczekujących, oczekiwaną liczbę w całym systemie, oczekiwany czas oczekiwania oraz oczekiwany całkowity czas w systemie (poprzez prawo Little'a). Ta strona pokazuje teoretyczne wartości Erlang-C obok pomiarów z bieżącej symulacji, dzięki czemu widać, jak blisko losowa symulacja odpowiada matematycznej predykcji.

Statystyki bieżące to średnie ważone czasem, zgromadzone z rzeczywistych zdarzeń losowych — wykładniczych czasów między przybyciami i czasów obsługi losowanych za każdym razem od nowa — więc zawierają szum statystyczny, zwłaszcza tuż po resecie lub zmianie ustawień. Wartości Erlang-C to dokładne matematyczne średnie stanu ustalonego, do których system dążyłby przy nieskończonym czasie. Im dłużej symulacja działa przy stałych λ, μ i c, tym bliżej wartości bieżące zbiegają się do teoretycznych, co jest żywą demonstracją prawa wielkich liczb.

FIFO (pierwszy na wejściu, pierwszy na wyjściu) obsługuje klientów w kolejności ich przybycia, jak typowa kolejka do kasy, i jest to dyscyplina zakładana przez klasyczny wzór Erlang-C. LIFO (ostatni na wejściu, pierwszy na wyjściu) obsługuje natomiast klienta, który dołączył do kolejki najpóźniej, co przy dużym obciążeniu może sprawić, że wcześni klienci będą czekać w nieskończoność, mimo że średni czas oczekiwania pozostaje taki sam jak w FIFO. Zmiana dyscypliny nie zmienia żadnej ze średnich Erlang-C, ale zmienia to, kto doświadcza najdłuższego indywidualnego oczekiwania.