Teoria kolejek — modele obsługi masowej, natężenie ruchu i podstawowe wzory
Teoria kolejek pozwala opisywać systemy, w których zgłoszenia, klienci, pojazdy lub zadania pojawiają się szybciej albo wolniej, niż mogą zostać obsłużone. Dzięki niej można oszacować średnią długość kolejki, czas oczekiwania, wykorzystanie stanowisk obsługi oraz skutki zwiększenia liczby kas, konsultantów, serwerów lub innych zasobów.
Spis treści
- Czym jest teoria kolejek?
- Elementy systemu kolejkowego
- Najważniejsze oznaczenia
- Proces przybyć i proces obsługi
- Notacja Kendalla
- Prawo Little’a
- Model \(M/M/1\)
- Model wielokanałowy \(M/M/c\)
- Systemy z ograniczoną pojemnością
- Jedna kolejka czy wiele kolejek?
- Przykład \(M/M/1\)
- Przykład \(M/M/2\)
- Najczęstsze błędy
- Podsumowanie
Czym jest teoria kolejek?
Teoria kolejek, nazywana też teorią obsługi masowej, zajmuje się analizą systemów, do których napływają zgłoszenia wymagające obsługi. Zgłoszeniem może być klient przy kasie, pacjent w przychodni, samochód na bramce autostradowej, połączenie telefoniczne, zlecenie produkcyjne, paczka w sortowni albo żądanie wysłane do serwera internetowego.
Jeżeli zgłoszenie pojawia się w chwili, w której odpowiednie stanowisko jest wolne, obsługa może rozpocząć się natychmiast. Jeżeli wszystkie stanowiska są zajęte, zgłoszenie trafia do kolejki. Celem analizy nie jest zwykle całkowite wyeliminowanie oczekiwania, ponieważ mogłoby to wymagać utrzymywania zbyt dużej i kosztownej liczby stanowisk. Chodzi raczej o znalezienie rozsądnej równowagi między kosztem zasobów a poziomem obsługi.
Modele kolejkowe pomagają między innymi odpowiedzieć na pytania:
- jak długo przeciętnie klient będzie czekał na obsługę,
- ile osób przeciętnie znajduje się w kolejce,
- jak często wszystkie stanowiska będą zajęte,
- czy istniejąca liczba kas, konsultantów lub serwerów jest wystarczająca,
- jak zmieni się sytuacja po dodaniu kolejnego kanału obsługi,
- czy ograniczona pojemność systemu powoduje utratę klientów lub zgłoszeń.
Elementy systemu kolejkowego
Każdy system obsługi masowej można opisać za pomocą kilku podstawowych elementów.
| Element | Znaczenie | Przykład |
|---|---|---|
| Źródło zgłoszeń | Zbiór potencjalnych klientów, zadań lub obiektów wymagających obsługi. | Klienci sklepu, pacjenci, samochody, użytkownicy aplikacji. |
| Strumień przybyć | Sposób, w jaki zgłoszenia pojawiają się w systemie. | Średnio 18 klientów na godzinę. |
| Kolejka | Zbiór zgłoszeń oczekujących na rozpoczęcie obsługi. | Osoby stojące przed kasą. |
| Kanał obsługi | Pojedyncze stanowisko zdolne do obsługi jednego zgłoszenia w danej chwili. | Jedna kasa, konsultant, lekarz, serwer. |
| Liczba kanałów | Liczba równoległych stanowisk obsługi. | Dwie kasy lub pięciu konsultantów infolinii. |
| Pojemność systemu | Maksymalna liczba zgłoszeń mogących jednocześnie znajdować się w kolejce i obsłudze. | Parking na 30 samochodów albo infolinia z limitem połączeń. |
| Dyscyplina kolejki | Zasada określająca kolejność obsługi zgłoszeń. | FIFO, priorytety, obsługa losowa. |
Kanał obsługi i stanowisko obsługi
W praktyce określenia kanał obsługi i stanowisko obsługi często stosuje się zamiennie. Jeden kanał oznacza, że w danym momencie można obsłużyć jedno zgłoszenie. System jednokanałowy może być więc reprezentowany przez pojedynczą kasę, jedno okienko, jednego konsultanta albo jeden serwer.
System wielokanałowy ma kilka stanowisk działających równolegle. Przykładem są trzy kasy w sklepie, cztery bramki wejściowe albo zespół konsultantów odbierających połączenia.
Dyscyplina kolejki
Najczęściej stosowana jest zasada FIFO (First In, First Out), czyli „pierwszy przybył, pierwszy obsłużony”. W niektórych systemach występują jednak inne reguły:
- LIFO — ostatnie zgłoszenie jest obsługiwane jako pierwsze,
- SIRO — zgłoszenie wybierane jest losowo,
- priorytety — wybrane zgłoszenia obsługiwane są przed pozostałymi,
- obsługa według terminu — pierwszeństwo ma zgłoszenie z najbliższym terminem realizacji.
Wzory dla klasycznych modeli \(M/M/1\) i \(M/M/c\) odnoszą się zwykle do kolejki FIFO. Przy priorytetach lub innych regułach obsługi parametry oczekiwania mogą wyglądać inaczej.
Najważniejsze oznaczenia
| Symbol | Znaczenie |
|---|---|
| \(\lambda\) | Średnia stopa przybyć, czyli przeciętna liczba zgłoszeń pojawiających się w jednostce czasu. |
| \(\mu\) | Średnia stopa obsługi jednego kanału, czyli przeciętna liczba zgłoszeń obsługiwanych przez jedno stanowisko w jednostce czasu. |
| \(c\) | Liczba równoległych kanałów obsługi. |
| \(\rho\) | Współczynnik wykorzystania kanału albo systemu. |
| \(a\) | Natężenie ruchu oferowanego, najczęściej \(a=\frac{\lambda}{\mu}\). |
| \(L\) | Średnia liczba zgłoszeń w całym systemie: w kolejce i w obsłudze. |
| \(L_q\) | Średnia liczba zgłoszeń oczekujących wyłącznie w kolejce. |
| \(W\) | Średni czas przebywania zgłoszenia w systemie: od przybycia do zakończenia obsługi. |
| \(W_q\) | Średni czas oczekiwania przed rozpoczęciem obsługi. |
| \(P_n\) | Prawdopodobieństwo, że w systemie znajduje się dokładnie \(n\) zgłoszeń. |
| \(P_0\) | Prawdopodobieństwo, że system jest pusty. |
Jednostki muszą być spójne
Jeżeli \(\lambda\) i \(\mu\) podajemy w zgłoszeniach na godzinę, to czasy \(W\) i \(W_q\) otrzymamy w godzinach. Aby uzyskać minuty, wynik należy pomnożyć przez 60. Mieszanie klientów na godzinę z czasem obsługi wyrażonym w minutach jest jednym z najczęstszych błędów rachunkowych.
Proces przybyć i proces obsługi
W modelach kolejkowych istotne jest nie tylko to, ile średnio zgłoszeń pojawia się w systemie, lecz także jaki ma charakter zmienność przybyć i obsługi. Dwa systemy o takim samym średnim tempie mogą tworzyć zupełnie inne kolejki, jeżeli w jednym z nich zgłoszenia pojawiają się regularnie, a w drugim skokowo i losowo.
Przybycia typu Poissona
W wielu podstawowych modelach zakłada się, że liczba zgłoszeń pojawiających się w danym przedziale czasu ma rozkład Poissona. Oznacza to między innymi, że przybycia są losowe i niezależne, a średnia liczba zgłoszeń w jednostce czasu wynosi \(\lambda\).
Równoważnie można powiedzieć, że odstępy czasu między kolejnymi przybyciami mają rozkład wykładniczy. Średni czas między przybyciami wynosi wtedy:
Wykładniczy czas obsługi
Jeżeli czas obsługi ma rozkład wykładniczy, średnia liczba zgłoszeń obsługiwanych przez jeden kanał w jednostce czasu wynosi \(\mu\). Średni czas obsługi pojedynczego zgłoszenia to:
Przykładowo, gdy kasjer obsługuje średnio 24 klientów na godzinę, średni czas obsługi wynosi \(\frac{1}{24}\) godziny, czyli 2,5 minuty.
Notacja Kendalla
Systemy kolejkowe opisuje się skrótowo za pomocą notacji Kendalla. Najczęściej spotyka się zapis:
W rozszerzonej postaci zapis może wyglądać następująco:
| Pozycja | Znaczenie |
|---|---|
| \(A\) | Rozkład procesu przybyć. |
| \(S\) | Rozkład czasu obsługi. |
| \(c\) | Liczba kanałów obsługi. |
| \(K\) | Maksymalna liczba zgłoszeń w całym systemie. |
| \(N\) | Liczebność populacji źródłowej. |
| \(D\) | Dyscyplina kolejki, na przykład FIFO. |
Najczęściej stosowane oznaczenia rozkładów to:
- \(M\) — rozkład wykładniczy, czyli proces bez pamięci; dla przybyć oznacza zwykle proces Poissona,
- \(D\) — wartości deterministyczne, czyli stały czas między przybyciami albo stały czas obsługi,
- \(G\) — rozkład ogólny, bez szczegółowego określenia jego postaci.
Zapis \(M/M/1\) oznacza więc losowe przybycia, losowy wykładniczy czas obsługi oraz jeden kanał obsługi. Zapis \(M/M/3\) opisuje taki sam charakter przybyć i obsługi, ale z trzema równoległymi stanowiskami.
Prawo Little’a
Jedną z najważniejszych zależności w teorii kolejek jest prawo Little’a. Łączy ono średnią liczbę zgłoszeń w systemie ze średnim czasem przebywania w tym systemie:
Analogicznie dla samej kolejki:
Prawo Little’a ma bardzo szerokie zastosowanie. Nie wymaga ono wyłącznie założenia wykładniczych czasów obsługi ani przybyć typu Poissona. Wymaga jednak stabilności systemu i właściwego rozumienia stopy przybyć. Gdy system ma ograniczoną pojemność i część klientów jest odrzucana, należy stosować efektywną stopę przybyć, a nie liczbę wszystkich prób wejścia do systemu.
Interpretacja prawa Little’a
Jeżeli do systemu przybywa średnio 20 klientów na godzinę, a przeciętny klient przebywa w nim przez 12 minut, czyli 0,2 godziny, to średnia liczba klientów w systemie wynosi:
Średnio w systemie będą więc cztery osoby: część może czekać, a część może być właśnie obsługiwana.
Model jednokanałowy \(M/M/1\)
Model \(M/M/1\) jest podstawowym modelem teorii kolejek. Zakłada on, że przybycia są losowe typu Poissona, czasy obsługi mają rozkład wykładniczy, a w systemie działa jedno stanowisko obsługi. Przyjmuje się także nieograniczoną kolejkę oraz obsługę według reguły FIFO.
Warunek stabilności
System jednokanałowy ma sens w stanie ustalonym tylko wtedy, gdy średnia stopa przybyć jest mniejsza od średniej stopy obsługi:
Współczynnik wykorzystania kanału wynosi:
Warunek stabilności można więc zapisać również jako \(\rho1\). Gdy \(\rho\) zbliża się do 1, stanowisko jest niemal stale zajęte, a średni czas oczekiwania gwałtownie rośnie. Jeżeli \(\lambda\geq\mu\), kolejka ma tendencję do narastania bez ograniczeń.
Prawdopodobieństwa stanów
Prawdopodobieństwo, że system jest pusty, wynosi:
Prawdopodobieństwo, że w systemie znajduje się dokładnie \(n\) zgłoszeń, wynosi:
Wartość \(n\) obejmuje zarówno klientów oczekujących, jak i klienta obsługiwanego. Gdy \(n=0\), system jest pusty. Gdy \(n=1\), jedna osoba jest obsługiwana i nikt nie czeka. Gdy \(n=4\), jedna osoba jest obsługiwana, a trzy oczekują w kolejce.
Podstawowe wzory dla \(M/M/1\)
| Wielkość | Wzór | Interpretacja |
|---|---|---|
| Wykorzystanie kanału | \(\rho=\frac{\lambda}{\mu}\) | Udział czasu, przez który stanowisko jest przeciętnie zajęte. |
| Średnia liczba zgłoszeń w systemie | \(L=\frac{\lambda}{\mu-\lambda}=\frac{\rho}{1-\rho}\) | Obejmuje oczekujących oraz zgłoszenie aktualnie obsługiwane. |
| Średnia liczba zgłoszeń w kolejce | \(L_q=\frac{\lambda^2}{\mu(\mu-\lambda)}=\frac{\rho^2}{1-\rho}\) | Obejmuje wyłącznie oczekujących. |
| Średni czas w systemie | \(W=\frac{1}{\mu-\lambda}\) | Obejmuje czas oczekiwania i obsługi. |
| Średni czas oczekiwania | \(W_q=\frac{\lambda}{\mu(\mu-\lambda)}=\frac{\rho}{\mu(1-\rho)}\) | Czas od przybycia do rozpoczęcia obsługi. |
Warto zauważyć zależność:
Średni czas w systemie składa się zatem ze średniego czasu oczekiwania oraz średniego czasu obsługi.
Wysokie wykorzystanie nie zawsze jest korzystne
Intuicyjnie może się wydawać, że wykorzystanie stanowiska bliskie 100% jest optymalne. W systemach kolejkowych zwykle oznacza jednak bardzo długie oczekiwanie. Przy \(\rho=0{,}50\) stanowisko jest zajęte przez połowę czasu, ale przy \(\rho=0{,}95\) nawet niewielkie opóźnienia i losowe skoki liczby zgłoszeń mogą wywołać długą kolejkę.
Model wielokanałowy \(M/M/c\)
Model \(M/M/c\) opisuje system, w którym działa \(c\) identycznych kanałów obsługi. Każdy kanał ma średnią stopę obsługi \(\mu\), a całkowita potencjalna zdolność obsługowa systemu wynosi \(c\mu\).
Przykładem może być infolinia z trzema konsultantami, dział obsługi klienta z pięcioma pracownikami albo sklep z czterema równoległymi kasami.
Warunek stabilności i wykorzystanie kanałów
W systemie wielokanałowym warunek stabilności ma postać:
Przyjmuje się oznaczenia:
Wielkość \(a\) oznacza oferowane natężenie ruchu. Natomiast \(\rho\) pokazuje średnie wykorzystanie pojedynczego kanału. Wymóg stabilności oznacza, że \(\rho1\).
Wzory Erlanga C dla \(M/M/c\)
W modelu z nieograniczoną kolejką podstawą obliczeń jest prawdopodobieństwo pustego systemu:
Następnie wyznaczamy prawdopodobieństwo, że nowo przybywające zgłoszenie będzie musiało czekać. Jest to tak zwana formuła Erlanga C:
Średnia liczba zgłoszeń oczekujących w kolejce wynosi:
Pozostałe wielkości wyznaczamy za pomocą prawa Little’a:
W przypadku systemu wielokanałowego średni czas samej obsługi nadal wynosi \(\frac{1}{\mu}\), ponieważ pojedyncze zgłoszenie korzysta tylko z jednego kanału. Zwiększenie liczby kanałów nie skraca bezpośrednio obsługi, ale może znacząco skrócić czas oczekiwania.
Model \(M/D/1\) jako porównanie
Nie każdy system ma losowy czas obsługi. Jeżeli obsługa trwa zawsze tyle samo, stosuje się oznaczenie \(D\). W modelu \(M/D/1\) przybycia są losowe, ale czas obsługi jest stały.
Dla tego modelu, przy \(\rho=\frac{\lambda}{\mu}1\), średni czas oczekiwania wynosi:
W porównaniu z \(M/M/1\) oczekiwanie jest krótsze, ponieważ brak losowości czasu obsługi zmniejsza wahania kolejki. Przy tych samych wartościach \(\lambda\) i \(\mu\) model \(M/D/1\) daje średni czas oczekiwania równy połowie wartości z modelu \(M/M/1\).
Systemy z ograniczoną pojemnością
Nie każda kolejka może rosnąć bez końca. Parking ma określoną liczbę miejsc, poczekalnia ma ograniczoną pojemność, a system teleinformatyczny może przyjmować jedynie określoną liczbę równoczesnych zgłoszeń. Gdy system jest pełny, kolejne zgłoszenie może zostać odrzucone, utracone albo skierowane gdzie indziej.
Klasyczny model jednokanałowy o ograniczonej pojemności oznacza się jako \(M/M/1/K\), gdzie \(K\) jest maksymalną liczbą zgłoszeń w całym systemie, a więc łącznie w kolejce i w obsłudze.
Dla \(\rho\neq1\) prawdopodobieństwo pustego systemu wynosi:
Prawdopodobieństwo wystąpienia dokładnie \(n\) zgłoszeń w systemie wynosi:
Jeżeli system jest pełny, nowe zgłoszenie nie zostaje przyjęte. Prawdopodobieństwo utraty zgłoszenia jest zatem równe:
Efektywna stopa przybyć, czyli liczba zgłoszeń faktycznie przyjętych do systemu, wynosi:
W systemach z odrzuceniami to właśnie \(\lambda_{\text{eff}}\) należy zastosować w prawie Little’a:
Co jest kosztem pełnej kolejki?
W niektórych systemach odrzucone zgłoszenie oznacza jedynie chwilową niedogodność. W innych oznacza utracone zamówienie, nieodebrane połączenie, niezadowolenie klienta albo ryzyko operacyjne. Dlatego przy projektowaniu systemu należy analizować nie tylko średni czas oczekiwania, ale także prawdopodobieństwo blokady i koszt utraconych zgłoszeń.
Jedna kolejka czy wiele kolejek?
System wielokanałowy może działać na dwa podstawowe sposoby. W pierwszym wariancie wszyscy klienci ustawiają się w jednej wspólnej kolejce, a następnie przechodzą do pierwszego wolnego stanowiska. W drugim wariancie każde stanowisko ma własną kolejkę.
| Rozwiązanie | Zalety | Ograniczenia |
|---|---|---|
| Jedna wspólna kolejka | Lepsze równoważenie obciążenia, mniejsze ryzyko, że jedna kolejka będzie długa, a inne prawie puste, większe poczucie sprawiedliwości. | Wymaga miejsca organizacyjnego i sprawnego kierowania klientów do wolnych stanowisk. |
| Oddzielne kolejki | Prostsze do utworzenia, mogą być wygodne przy stanowiskach o różnych funkcjach. | Klienci mogą wybrać wolniejszą kolejkę, a obciążenie stanowisk może być nierównomierne. |
| Kolejki priorytetowe | Umożliwiają szybszą obsługę zgłoszeń pilnych lub szczególnie ważnych. | Mogą wydłużać oczekiwanie klientów standardowych i wymagają jasnych zasad priorytetyzacji. |
W wielu systemach jedna wspólna kolejka pozwala lepiej wykorzystać dostępne stanowiska. Nie jest to jednak bezwzględna zasada. Oddzielne kolejki mogą być uzasadnione, gdy stanowiska różnią się kompetencjami, obsługują inne typy spraw albo wymagają specjalistycznego wyposażenia.
Przykład \(M/M/1\) — jedna kasa
Rozważmy mały punkt obsługi z jedną kasą. Klienci przychodzą średnio z intensywnością 18 klientów na godzinę. Kasjer obsługuje średnio 24 klientów na godzinę. Zakładamy model \(M/M/1\).
Dane:
Najpierw sprawdzamy stabilność systemu:
System jest stabilny. Współczynnik wykorzystania kasy wynosi:
Kasa jest więc zajęta przeciętnie przez 75% czasu. Prawdopodobieństwo, że system jest pusty, wynosi:
Średnia liczba klientów w systemie:
Średnia liczba klientów oczekujących w kolejce:
Średni czas przebywania klienta w systemie:
Średni czas oczekiwania w kolejce:
Interpretacja wyniku
Klient spędza w systemie średnio 10 minut, z czego około 7,5 minuty oczekuje, a około 2,5 minuty trwa sama obsługa. W całym systemie znajduje się średnio 3 klientów, przy czym średnio 2,25 osoby czekają, a jedna jest obsługiwana.
Przykład \(M/M/2\) — dwa stanowiska obsługi
Załóżmy teraz, że do punktu obsługi przybywa średnio 30 klientów na godzinę. Działają dwa identyczne stanowiska, a każde z nich obsługuje średnio 20 klientów na godzinę. Mamy więc model \(M/M/2\).
Najpierw obliczamy natężenie ruchu oferowanego i wykorzystanie kanałów:
Każde stanowisko jest średnio wykorzystane w 75%, a system jest stabilny, ponieważ:
Wyznaczamy prawdopodobieństwo pustego systemu:
Prawdopodobieństwo, że nowy klient będzie musiał czekać, wynosi:
Średnia liczba klientów oczekujących w kolejce:
Średni czas oczekiwania wynosi:
Średni czas przebywania klienta w systemie:
Średnia liczba klientów w całym systemie:
Interpretacja wyniku
Mimo że każde stanowisko jest wykorzystane średnio tylko w 75%, około 64,3% klientów musi chwilę poczekać, ponieważ zdarzają się momenty, gdy oba stanowiska są jednocześnie zajęte. Średni czas oczekiwania wynosi jednak mniej niż 4 minuty, a średni czas całkowity w systemie niecałe 7 minut.
Najczęstsze błędy
- Mieszanie jednostek czasu. Stopy \(\lambda\) i \(\mu\) muszą odnosić się do tej samej jednostki czasu.
- Stosowanie wzorów \(M/M/1\) do systemu wielokanałowego. Dla \(c>1\) należy użyć modelu \(M/M/c\).
- Pomijanie warunku stabilności. Jeżeli \(\lambda\geq c\mu\), klasyczne wzory dla stanu ustalonego nie są właściwe.
- Mylenie \(L\) z \(L_q\). Wielkość \(L\) obejmuje także klientów aktualnie obsługiwanych.
- Mylenie \(W\) z \(W_q\). Czas \(W\) obejmuje oczekiwanie i obsługę, a \(W_q\) tylko oczekiwanie.
- Używanie \(\lambda\) zamiast \(\lambda_{\text{eff}}\) w systemie z odrzuceniami. W modelu o ograniczonej pojemności część zgłoszeń może nie wejść do systemu.
- Traktowanie wartości średnich jako maksymalnych. Średnia kolejka długości 2 osób nie oznacza, że kolejka nigdy nie będzie liczyć 5 lub 10 osób.
- Pomijanie charakteru danych. Model \(M/M/1\) jest użyteczny, ale nie zawsze dokładnie opisuje rzeczywisty system.
Podsumowanie
Teoria kolejek umożliwia ilościową analizę systemów, w których zgłoszenia konkurują o ograniczone zasoby obsługowe. Podstawowe parametry to stopa przybyć \(\lambda\), stopa obsługi \(\mu\), liczba kanałów \(c\), wykorzystanie systemu \(\rho\), średnia liczba zgłoszeń \(L\) i \(L_q\) oraz średnie czasy \(W\) i \(W_q\).
Model \(M/M/1\) opisuje jeden kanał obsługi, a \(M/M/c\) system z wieloma równoległymi stanowiskami. W obu przypadkach kluczowe jest sprawdzenie warunku stabilności. Im bardziej wykorzystanie systemu zbliża się do 100%, tym szybciej rosną przeciętne kolejki i czasy oczekiwania.
W praktyce analiza kolejek pomaga dobrać liczbę kas, konsultantów, serwerów, stanowisk produkcyjnych albo miejsc w poczekalni. Dzięki temu można równoważyć koszt utrzymywania zasobów z jakością obsługi klientów i niezawodnością całego procesu.
Powiązane artykuły
Masz problem z tym tematem?
Wszechwiedza.pl pomaga zrozumieć matematykę, statystykę, ekonometrię, badania operacyjne, analizę danych, mechanikę, rachunkowość i wiele innych przedmiotów — spokojnie, konkretnie i krok po kroku.
Zapytaj o pomoc