Teoria kolejek

Wygląd przypnij ukryj

Ten artykuł od 2022-11 wymaga zweryfikowania podanych informacji.Należy podać wiarygodne źródła w formie przypisów bibliograficznych.
Część lub nawet wszystkie informacje w artykule mogą być nieprawdziwe. Jako pozbawione źródeł mogą zostać zakwestionowane i usunięte.
Sprawdź w źródłach: Encyklopedia PWN • Google Books • Google Scholar • Federacja Bibliotek Cyfrowych • BazHum • BazTech • RCIN • Internet Archive (texts / inlibrary)
Po wyeliminowaniu niedoskonałości należy usunąć szablon {{Dopracować}} z tego artykułu.

Teoria kolejek – dziedzina matematyki zajmująca się analizowaniem systemów, w których powstają kolejki. Teoria kolejek jest dziedziną związaną z badaniami operacyjnymi, rachunkiem prawdopodobieństwa, matematyką stosowaną, jak również telekomunikacją i informatyką.

Systemy kolejkowe

W systemach którymi zajmuje się teoria kolejek, zlecenia (np. klienci w supermarkecie) napływają do punktów obsługi (kasy) i czekają na obsłużenie w poczekalni (kolejka do kasy). Zwykle przyjmuje się, że tempo napływu klientów jest zmienną losową, co powoduje, że nawet jeżeli punkty obsługi teoretycznie obsługują klientów szybciej niż oni napływają, w systemie powstają kolejki. Kolejki wynikają z tego, że w jednej chwili klienci w ogóle nie pojawiają się przy kasie, natomiast w innej chwili pojawia się „podwójna porcja” klientów.

System kolejkowy opisują dwie zmienne losowe:

τ 1 {\displaystyle \tau _{1}} $\tau _{1}$ – czas między kolejnymi zgłoszeniami,
τ 2 {\displaystyle \tau _{2}} $\tau _{2}$ – czas obsługi pojedynczego zgłoszenia.

W teorii kolejek wykorzystywane jest m.in. prawo Little’a (1961).

Oznaczenia

Prekursorem w dziedzinie teorii kolejek był duński inżynier Agner Krarup Erlang pracujący w firmie telekomunikacyjnej. W 1909 roku opublikował on swoją pierwszą pracę dotyczącą systemów kolejkowych. Kolejna ważna praca na ten temat, napisana przez Davida G. Kendalla powstała w 1953 roku i dotyczyła notacji, jaką należy stosować przy opisywaniu systemów kolejkowych. Zaproponowana przez Kendala notacja wyglądała następująco: A / B / c / L / N . {\displaystyle A/B/c/L/N.} $A/B/c/L/N.$ Poszczególne składowe tej notacji miały następujące znaczenie:

A {\displaystyle A} – rozkład zmiennej losowej τ 1 {\displaystyle \tau _{1}} (czas między kolejnymi zgłoszeniami),
- M {\displaystyle M} $M$ – rozkład wykładniczy,
- D {\displaystyle D} $D$ – rozkład deterministyczny (o stałych odstępach czasu),
- E k {\displaystyle E_{k}} $E_{k}$ – rozkład Erlanga rzędu k , {\displaystyle k,} $k,$
- G {\displaystyle G} $G$ – rozkład ogólny (od General) zdefiniowany przez użytkownika,
B {\displaystyle B} $B$ – algorytm obsługi zgłoszeń (rozkład zmiennej losowej τ 2 {\displaystyle \tau _{2}} $\tau _{2}$ ),
c {\displaystyle c} $c$ – liczba równoległych stanowisk obsługi,
L {\displaystyle L} $L$ – wielkość poczekalni (jeśli nie podane, to L = ∞ {\displaystyle L=\infty } $L=\infty$ ),
N {\displaystyle N} $N$ – wymiar źródła zgłoszeń (jeśli nie podane, to N = ∞ {\displaystyle N=\infty } $N=\infty$ ).

Parametry systemu kolejkowego

N ( t ) {\displaystyle N(t)} $N(t)$ – zmienna losowa – liczba zgłoszeń w momencie t {\displaystyle t} $t$
c + L + 1 {\displaystyle c+L+1} $c+L+1$ – liczba stanów systemu
λ {\displaystyle \lambda } $\lambda$ – intensywność napływu zgłoszeń
μ {\displaystyle \mu } $\mu$ – intensywność obsługi zgłoszeń
1 λ {\displaystyle {\frac {1}{\lambda }}} ${\frac {1}{\lambda }}$ – średni czas między kolejnymi zgłoszeniami
1 μ {\displaystyle {\frac {1}{\mu }}} ${\frac {1}{\mu }}$ – średni czas obsługi pojedynczego zgłoszenia
ρ = λ μ {\displaystyle \rho ={\frac {\lambda }{\mu }}} $\rho ={\frac {\lambda }{\mu }}$ – obciążenie systemu

Najpopularniejsze typy systemów kolejkowych

Zastosowania

Już na pierwszy rzut oka widać, że notacja zaproponowana przez Kendalla jest bardzo sztywna i trudno przy jej pomocy modelować prawdziwe zjawiska. Przykładowo, przy pomocy tej notacji nie da się uwzględnić, że klienci mogą się różnić między sobą (klienci, którzy przychodzą zrobić duże zakupy na weekend różnią się od klientów, którzy przyszli rano tylko po bułki).

Pierwotnym założeniem było także to, że systemy kolejkowe będą analizowane przy pomocy technik analitycznych. W praktyce okazuje się to jednak bardzo trudne, a często wręcz niemożliwe, ponieważ systemy są zbyt skomplikowane bądź charakteryzujące je zmienne losowe nie dają się w łatwy sposób analizować matematycznie. Dlatego obecnie najwygodniejszą i najczęściej stosowaną techniką są symulacje komputerowe.

Symulacje komputerowe można wykorzystać do analizy systemów kolejkowych w wielu dziedzinach:

kolejki w supermarketach, stacjach obsługi samochodów, lotniskach,
logistyka i procesy produkcyjne (linie produkcyjne),
telekomunikacja – zgłoszenia do centrali, call centers,
sieci komputerowe i obsługa systemów z wieloma terminalami,
obwody elektryczne i pamięci komputerowe (tworzenie tzw. stosów).

Narzędzia stosowane do analizy systemów kolejkowych

język programowania GPSS
programy komputerowe (np. Matlab)

Zobacz też

Teoria systemów

Bibliografia

Walenty Oniszczuk: Metody modelowania. Białystok: Wydawnictwo Politechniki Białostockiej, 1995. ISBN 83-86272-18-X.brak strony w książce

Linki zewnętrzne

Queueing theory (ang.), Encyclopedia of Mathematics, encyclopediaofmath.org, .

Działy matematyki

działy
ogólne

według trudności	matematyka elementarna matematyka wyższa
według celu	matematyka czysta matematyka stosowana
inne	matematyka doświadczalna matematyka parakonsystentna supermatematyka

działy
czyste

algebra	elementarna liniowa i wieloliniowa abstrakcyjna algebra przemienna algebra lokalna teoria Galois różniczkowa teoria Galois teoria grup geometryczna teoria grup teoria Liego homologiczna różniczkowa uniwersalna teoria reprezentacji
analiza matematyczna	analiza algebraiczna analiza funkcjonalna teoria spektralna analiza geometryczna analiza globalna analiza harmoniczna analiza mikrolokalna analiza na rozmaitościach analiza niestandardowa analiza numeryczna nomografia analiza p-adyczna analiza rzeczywista analiza wektorowa analiza wielowymiarowa analiza wypukła analiza zespolona rachunek różniczkowy i całkowy rachunek wariacyjny teoria dystrybucji teoria miary teoria potencjału
arytmetyka	elementarna teoretyczna lub wyższa, in. teoria liczb algebraiczna algorytmiczna analityczna elementarna geometryczna teoria sit
geometria	absolutna afiniczna algebraiczna analityczna arytmetyczna diofantyczna dyskretna euklidesowa planimetria stereometria fraktalna inwersyjna kombinatoryczna konforemna metryczna nieeuklidesowa eliptyczna hiperboliczna sferyczna nieprzemienna obliczeniowa różniczkowa symplektyczna rzutowa skończona syntetyczna tropikalna uporządkowania wykreślna zespolona trygonometria sferyczna
matematyka dyskretna	kombinatoryka teoria Ramseya teoria grafów algebraiczna geometryczna spektralna topologiczna
podstawy	logika matematyczna algebraiczna mereologia rachunek zdań teoria dowodu teoria modeli teoria rekursji teoria typów metamatematyka metalogika teoria kategorii teoria mnogości opisowa arytmetyka liczb kardynalnych arytmetyka liczb porządkowych teoria PCF teoria obliczeń teoria obliczalności teoria złożoności
teoria układów dynamicznych	teoria chaosu teoria katastrof teoria ergodyczna
topologia	algebraiczna teoria homotopii geometryczna mnogościowa ogólna różniczkowa teoria Morse’a teoria położenia teoria węzłów teoria warkoczy teoria wymiaru
pozostałe	K-teoria probabilistyka rachunek różnicowy teoria osobliwości teoria porządku teoria punktu stałego

działy
stosowane

nauki przyrodnicze	biomatematyka chemia matematyczna fizyka matematyczna
nauki społeczne	ekonomia matematyczna lingwistyka matematyczna matematyka finansowa matematyka ubezpieczeniowa psychologia matematyczna socjologia matematyczna teoria głosowań
nauki techniczne	kryptologia teoria informacji teoria kolejek teoria sterowania
statystyka matematyczna	rachunek wyrównawczy statystyka nieparametryczna teoria estymacji
inne	teoria gier teoria decyzji

powiązane
dyscypliny

ściśle naukowe	dydaktyka matematyki historia matematyki
inne	filozofia matematyki matematyka rekreacyjna numerologia pseudomatematyka

Kontrola autorytatywna (teoria):

Encyklopedia internetowa: