Difference between revisions of "Queueing theory/cs"
(→Úvod) |
(→Úvod) |
||
| Line 6: | Line 6: | ||
{| class="wikitable" border="1" | {| class="wikitable" border="1" | ||
| − | |+ Příklady SHO | + | |+ Příklady SHO <ref>JABLONSKÝ, Josef. <i>Operační výzkum: kvantitativní modely pro ekonomické rozhodování</i>. 1. vyd. Praha: Professional Publishing, 2002, 323 s. ISBN 80-864-1923-1.</ref> |
! systém !! obslužné linky !! požadavky | ! systém !! obslužné linky !! požadavky | ||
|- | |- | ||
| Line 21: | Line 21: | ||
| samoobsluha || pokladny, nákupní vozíky || zákazníci | | samoobsluha || pokladny, nákupní vozíky || zákazníci | ||
|} | |} | ||
| − | + | ||
| Line 47: | Line 47: | ||
{| class="wikitable" align=right width="225" | {| class="wikitable" align=right width="225" | ||
| − | ! scope="col" width="50px" | Profesor David George Kendall | + | ! scope="col" width="50px" | Profesor David George Kendall <ref>Divergiendo: 23 de octubre: David Kendall. <i>Divergiendo</i> [online]. 2012 [cit. 2015-06-16]. Dostupné z: https://divergiendo.wordpress.com/2012/10/23/23-de-octubre-david-kendall/</ref> |
[[File:Xblal26 kendalldg.png|240 px|D.G.Kendall]] | [[File:Xblal26 kendalldg.png|240 px|D.G.Kendall]] | ||
| Line 68: | Line 68: | ||
1980 Senior Whitehead Prize, | 1980 Senior Whitehead Prize, | ||
1989 De Morgan Medal | 1989 De Morgan Medal | ||
| − | |||
| − | |||
|} | |} | ||
| Line 103: | Line 101: | ||
* požadavky přichází s Poissonovým rozdělením | * požadavky přichází s Poissonovým rozdělením | ||
* počet požadavků přicházející do systému v intervalu <0;T>, p(n) = <math>$\frac{(\lambda T)^n}{n!}$ $e^{({-}\lambda T)}$</math> | * počet požadavků přicházející do systému v intervalu <0;T>, p(n) = <math>$\frac{(\lambda T)^n}{n!}$ $e^{({-}\lambda T)}$</math> | ||
| + | |||
==Reference== | ==Reference== | ||
<references /> | <references /> | ||
Revision as of 11:55, 16 June 2015
Contents
Teorie hromadné obsluhy (Teorie front)
Jednou z podskupin diskrétních simulací je teorie hromadné obsluhy, v češtině často nazývaná jako "Teorie front".
Úvod
Teorie front zkoumá systémy, na které opakovaně přicházejí sekvence požadavků a jejich výskyt je náhodný. Zjišťujeme tak například potřebnou kapacitu zdrojů, nebo optimální využití výrobních linek. Tato chování se dají nasimulovat do tzv. stochastických modelů. Cílem těchto modelů je analýza stávajících systémů a nalezení nejvhodnějšího způsobu optimalizace. Zároveň se musí optimalizovat množství lidí čekajících ve frontě a vytížení obslužných linek. Pro simulování frontových systémů potřebujeme informace o vstupním toku (např. jak často přijde nový požadavek na server), o frontovém systému, který se vytvoří, pokud požadavek nemůže být ihned vyřízen a organizace obsluhy - počet volných jednotek vykonávající proces obsluhy a jejich popis. Pokud mluvíme o vstupu jako o zákazníkovi, nejedná se o zákazníka v striktním slova smyslu, ale může to být proces, služba, člověk ale i jakýkoliv požadavek čekající na vyřízení.
| systém | obslužné linky | požadavky |
|---|---|---|
| banka | úředníci u přepážky | klienti |
| výrobní linka | místa na výrobní lince | výrobky |
| ordinace u lékaře | lékař | pacienti |
| lyžařské středisko | vleky | lyžaři |
| benzínová pumpa | čerpací stojany | vozidla |
| samoobsluha | pokladny, nákupní vozíky | zákazníci |
Schéma teorie front
- Objekty vyžadující obsluhu (zákazníci, jednotky, požadavky)
- Množina jednotek přicházející v úvahu pro hromadnou obsluhu
- Časová posloupnost vstupu jednotek
- Množina jednotek čekajících na obsluhu
- Systém realizující obsluhu
- Časová posloupnost výstupu
Základní informace nutné k řešení
Pro návrh systémů hromadné obsluhy je nutné znát základní parametry:
- Vstupní tok
"zákazníci" mohou do systému vstupovat jednotlivě nebo hromadně
- Frontový režim
systém, jakým jsou zákazníci čekající na obsluhu řazeni do systému - FIFO (First-in-First-out), LIFO (Last-in-First-out), SIRO (Service in Random Order), PRI (Priority queue)
- Organizace obsluhy
zda je k dispozici jeden obslužný systém, paralelní či sériové zapojení systémů
Kendallova klasifikace
D.G. Kendall byl anglický statistik a matematik, v 50. letech zavedl notaci pro jednotnou charakteristiku systémů hromadné obsluhy. Jelikož jsou systémy hromadné obsluhy velmi komplexní, je nutné standardizovat jejich značení pro zjednodušení následných výpočtů.
| Profesor David George Kendall [2]
15 January 1918 – 23 October 2007 člen the Royal Society (1964) |
|---|
|
Anglický statistik a matematik Zasadil se o rozvoj teorie pravděpodobnosti, statistické analýzy tvarů a vzhledu Vyučoval v Oxfordu a Cambridge Ocenění * Royal Statistical Society 1955 the Guy Medal in Silver, 1981 the Guy Medal in Gold * London Mathematical Society 1980 Senior Whitehead Prize, 1989 De Morgan Medal |
Jelikož tyto informace nejsou v praxi dostačující, rozšířil se model o další 3 klasifikační třídy.
Na jednotlivé pozice se do modelu dosazují kódy (výsledný model může mít až šestimístný kód - A/B/C/D/E/F)
- A
Pravděpodobností rozdělení intervalů mezi příchody požadavků, nejčastěji: N - normální rozdělení M - exponenciální rozdělení U - rovnoměrné rozdělení G - obecné rozdělení
- B
pravděpodobnostní rozdělení doby obsluhy, stejné jako A
- C
počet paralelně zapojených obslužných linek
- D
kapacita obslužného systému (neuvedeno = nekonečno)
- E
zdroje požadavků (neuvedeno = nekonečno)
- F
systém fronty (FIFO, LIFO, ...)
např. zápis systému M/M/1/ Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \infty} / Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \infty} /FIFO se zjednodušeně zapíše M/M/1
Vzorce
Pro jednoobslužný systém
* požadavky přichází s Poissonovým rozdělením
* počet požadavků přicházející do systému v intervalu <0;T>, p(n) = Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle $\frac{(\lambda T)^n}{n!}$ $e^{({-}\lambda T)}$}
Reference
- ↑ JABLONSKÝ, Josef. Operační výzkum: kvantitativní modely pro ekonomické rozhodování. 1. vyd. Praha: Professional Publishing, 2002, 323 s. ISBN 80-864-1923-1.
- ↑ Divergiendo: 23 de octubre: David Kendall. Divergiendo [online]. 2012 [cit. 2015-06-16]. Dostupné z: https://divergiendo.wordpress.com/2012/10/23/23-de-octubre-david-kendall/
