Teorie fronty je matematické studium čekajících front, neboli front. Teorie umožňuje matematickou analýzu několika souvisejících procesů, včetně příchodu do (zadní části) fronty, čekání ve frontě (v podstatě proces ukládání) a obsloužení v přední části fronty. Teorie umožňuje odvození a výpočet několika výkonnostních měr včetně průměrné čekací doby ve frontě nebo systému, očekávaného počtu čekajících nebo přijímajících služeb a pravděpodobnosti setkání se systémem v určitých stavech, jako je prázdný, plný, s dostupným serverem nebo nutnost čekat určitou dobu na obsloužení.
Teorie queueingu má aplikace v různých oborech, včetně telekomunikací, výpočetní techniky
a designu továren, obchodů, kanceláří a nemocnic.
Slovo fronta pochází, přes francouzštinu, z latinského cauda, což znamená ocas. S pravopisem „queueing“ přes „queuing“ se obvykle setkáváme v akademickém výzkumu v oboru. Ve skutečnosti, jeden z vlajkových deníků této profese se jmenuje „Queueing Systems“. „Queueing“ – správný pravopis – je jediné slovo v anglickém jazyce s pěti po sobě jdoucími samohláskami.
Označení pro popis charakteristik modelu řazení do fronty poprvé navrhl David G. Kendall v roce 1953. Kendallova notace zavedla A/B/C zápis řazení do fronty, který lze nalézt ve všech standardních moderních pracích o teorii řazení, například Tijms.
Zápis A/B/C označuje frontový systém, který má A jako mezihvězdné rozložení času, B jako rozložení servisního času a C jako počet serverů. Například „G/D/1“ by označovalo obecný (může to být cokoliv) proces příchodu, deterministický (konstantní čas) servisní proces a jeden server. Více podrobností o tomto zápisu je uvedeno v článku o modelech frontování.
Agner Krarup Erlang, dánský inženýr kteří pracovali pro Kodaň Telefonní burza, publikoval první knihu o queueing teorie v roce 1909.
David G. Kendall zavedl A/B/C queueing notaci v roce 1953. Důležitou práci na teorii queueingu používanou v moderních sítích pro přepojování paketů provedl počátkem 60. let Leonard Kleinrock.
Sítě front jsou systémy, které obsahují libovolný, ale konečný počet m front. Zákazníci, někdy různých tříd, cestují sítí a jsou obslouženi v uzlech. Stav sítě lze popsat vektorem , kde ki je počet zákazníků ve frontě i. V otevřených sítích se mohou zákazníci připojit a opustit systém, zatímco v uzavřených sítích zůstává celkový počet zákazníků v systému pevný.
Prvním významným výsledkem v této oblasti byly Jacksonovy sítě, pro které existuje efektivní rovnovážná distribuce produktové formy.
Role Poissonova procesu, exponenciální rozdělení
Užitečný model fronty představuje reálný systém s dostatečnou přesností a je analyticky poddajný. Model fronty založený na Poissonově procesu a jeho průvodním exponenciálním rozdělení pravděpodobnosti často splňuje tyto dva požadavky. Poissonův proces modeluje náhodné události (například příchod zákazníka, žádost o akci z webového serveru nebo dokončení požadovaných akcí z webového serveru) jako události vycházející z procesu bez paměti. To znamená, že délka časového intervalu od aktuálního času do výskytu další události nezávisí na čase výskytu poslední události. V Poissonově rozdělení pravděpodobnosti pozorovatel zaznamenává počet událostí, které se vyskytnou v časovém intervalu pevné délky. V (záporném) exponenciálním rozdělení pravděpodobnosti pozorovatel zaznamenává délku časového intervalu mezi po sobě jdoucími událostmi. V obou případech je základním fyzikálním procesem memoryless.
Modely založené na Poissonově procesu často reagují na vstupy z prostředí způsobem, který napodobuje odezvu modelovaného systému na stejné vstupy. Analyticky traktovatelné modely, které jsou výsledkem, přinášejí jak informace o modelovaném systému, tak o formě jejich řešení. I model řazení do front založený na Poissonově procesu, který odvádí relativně špatnou práci při napodobování detailního výkonu systému, může být užitečný. Skutečnost, že takové modely často poskytují hodnocení „nejhoršího scénáře“, se zamlouvá návrhářům systému, kteří do svých návrhů raději zahrnují faktor bezpečnosti. Forma řešení modelů založených na Poissonově procesu také často poskytuje vhled do formy řešení problému řazení do front, jehož detailní chování je špatně napodobováno. V důsledku toho jsou modely řazení do front často modelovány tak, jak Poisson zpracovává pomocí exponenciálního rozdělení.
Omezení matematického přístupu
Klasická teorie fronty je často příliš matematicky omezující na to, aby byla schopna přesně modelovat situace v reálném světě. Toto omezení vzniká proto, že základní předpoklady teorie ne vždy platí v reálném světě. Složitost výrobních linek s vlastnostmi specifickými pro daný produkt nelze zvládnout pomocí matematických modelů. Proto byly vyvinuty speciální nástroje jako Plant Simulation, které simulují, analyzují, vizualizují a optimalizují chování linky dynamické fronty v čase.
Například matematické modely často předpokládají nekonečný počet zákazníků, nekonečnou kapacitu fronty nebo nulové hranice mezipříjezdových nebo servisních časů, když je zcela zřejmé, že tyto hranice musí existovat ve skutečnosti. Často, i když hranice existují, mohou být bezpečně ignorovány, protože rozdíly mezi reálným světem a teorií nejsou statisticky významné, protože pravděpodobnost, že by k takovým hraničním situacím mohlo dojít, je ve srovnání s očekávanou normální situací mizivá. V jiných případech se teoretické řešení může ukázat jako neřešitelné nebo nedostatečně informativní, aby bylo užitečné.
Byly tedy navrženy alternativní analytické prostředky s cílem poskytnout určitý vhled do problémů, které nespadají do oblasti teorie front, i když jsou často specifické pro jednotlivé scénáře, protože se obvykle skládají z počítačových simulací nebo analýzy experimentálních dat. Viz simulace síťového provozu.