6.1 Systémy hromadné obsluhy Proces uspokojování náhodně i hromadně vznikajících požadavků na obsluhu se nazývá proces hromadné obsluhy. Předmětem teorie hromadné obsluhy, někdy také označované jako teorie front (z anglických slov queueing theory), je matematické rozpracování a analyzování systémů poskytujících hromadnou obsluhu nějakých zařízení. Systém hromadné obsluhy je obsluhové zařízení, poskytující obsluhu určitého druhu. Do tohoto zařízení vstupují zákazníci, požadující konkrétní obsluhu. Zde je nutné podotknout, že pod pojmem zákazníci se rozumí nejen lidé, ale i neživé věci. Proto se také někdy místo pojmu zákazníci používá termín požadavky na obsluhu. Po obsloužení zákazníci opouštějí systém hromadné obsluhy. Obsluhové zařízení se může skládat z jednoho nebo více míst, na kterých se poskytuje konkrétní obsluha. Tato místa se nazývají linky obsluhy. Systém hromadné obsluhy (SHO) je základní teoretický model pro realizaci obslužných procesů. SHO je tvořený obslužnými kanály, které poskytují obsluhu požadavkům, přicházejícím ve vstupním proudu. po ukončení obsluhy trvající stanovenou dobu se kanál uvolňuje a realizovaný požadavek odchází ve výstupním proudu. Pokud v okamžiku příchodu požadavku není volný žádný kanál, řadí se požadavek do fronty.
Obr. 6.1: Systém hromadné obsluhy (A – vstup požadavků do systému, B – odmítnuté požadavky, C – realizované položky)
Systém hromadné dopravy je vždy tvořen následujícími prvky: •
vstupní proud;
• • •
fronta; obslužné kanály; výstupní proud.
A) Podle vstupního proudu dělíme SHO následovně: 1) podle počtu požadavků: a) omezený b) neomezený
2) podle povahy: a) deterministický b) stochastický 3) podle druhu obsluhy: a) stejnorodý – všechny požadavky požadují stejný druh obsluhy; b) různorodý – požadavky požadují různé druhy obsluhy; 4) podle příchodu: a) jednotlivě b) skupinově 5) podle intenzity vstupu: a) konstantní b) proměnlivá B) Podle druhu obsluhy: 1) podle fronty: a) ohraničené b) neohraničené 2) podle doby zdržení: a) omezený b) neomezený
3) podle způsobu odchodu z fronty: a) b) c) d) e)
FIFO – prvý příjde, prvý odejde LIFO – poslední přijde, prvý odejde SIFO – náhodné pořadí odchode PRI – podle priorit (atributů) GE – obecné řazení fronty
4) podle přednosti položek: a) slabé b) silné
C) Vzhledem na síť SHO se dělí: a) paralelní řazení b) sériové řazení c) kombinované řazení
D) Vzhledem na obsluhu se SHO dělí: 1) podle povahy doby obsluhy: a) deterministický b) stochastický 2) podle intenzity obsluhy: a) konstantní b) proměnné 3) podle počtu kanálů: a) proměnný b) konstantní Při návrhu SHO na sebe narážejí dva protichůdné požadavky: • •
zákazník chce čekat co nejkratší dobu, což znamená co největší kapacitu; snaha redukovat náklady a minimalizovat počet obslužných kanálů.
6.1.1 Možnosti analytického řešení stochastického systému hromadné obsluhy Předpokládá se, že pravděpodobnost výskytu více než jednoho požadavku na obsluhu je v daném okamžiku nulová. Takové proudy požadavků se označují jako ordinární. Přitom se zavádí tzv. parametr proudu požadavků λ(t). Proud požadavků je stacionární, je-li λ=konst. Tzn., že pravděpodobnost výskytu určitého počtu požadavků v intervalu
nezávisí na t, ale pouze na délce časového intervalu ∆t. Dále budeme uvažovat pouze se stacionárními Markovovými procesy. Pro matematický popis systému hromadné obsluhy potřebujeme znát následující informace:
-
informace o příchodu zákazníků informace o době obsluhy informace o počtu obsluhových linek informace o zákaznících, kteří nemohou být v době svého příchodu okamžitě obslouženi
Podle výše uvedených kritérií lze systémy hromadné obsluhy klasifikovat do několika kategorií. Nejpoužívanější je tzv. Kendallova klasifikace systémů hromadné obsluhy.
6.1.2 Kendallova klasifikace systémů hromadné obsluhy V této klasifikaci jsou systémy tříděny podle tří hlavních hledisek:
-
typu stochastického procesu popisujícího příchod požadavků k obsluze zákona rozložení délky obsluhy počtu obsluhových linek, jenž jsou zákazníkům k dispozici
Informace o těchto třech charakteristikách je zakódována ve tvaru
X/Y/n, kde na místě X a Y jsou velká písmena a n je přirozené číslo (popř. symbol ∞), značící počet linek obsluhy. Význam písmen X a Y je vysvětlen v následující Tabulce 1. Tab. 6.1: Charakteristiky Kandallovy klasifikace. Význam, dosazeno za
Písmeno X
Poissonův proces příchodů, tj. exponenciální rozložení (navzájem nezávislých) intervalů mezi příchody Erlangovo rozložení intervalů mezi příchody (s parametry λ a k) Rozložení χ2 intervalů mezi příchody (n stupňů volnosti) Pravidelné deterministické příchody Obecný případ – žádné předpoklady o procesu příchodů Rekurentní proces příchodů
M EK KN D G GI
Y Exponenciální rozložení doby obsluhy Erlangovo rozložení doby obsluhy (s parametry λ a k) Rozložení χ2 doby obsluhy Konstantní doba obsluhy Obecné, tj. jakékoliv rozložení doby obsluhy -
Dále se budeme zabývat pouze systémem M/M/n, neboť tento systém odpovídá nejčastěji řešenému problému - požadavky na obsluhu tvoří Poissonův proces, doba obsluhy má exponenciální rozdělení a počet linek je n.
6.1.3 Řešení jednoduchého systému hromadné obsluhy tytu M/M/n Pro řešení příkladu předpokládejme, že máme k dispozici jednu frontu pro shromažďování požadavků obsluhy a dva obslužné kanály s náhodnými událostmi na vstupu a výstupu. Předpokládejme, že doba obsluhy je nezávislá na počtu čekajících požadavků. Čekající požadavky jsou zpracovávané v pořadí v jakém přicházejí (FIFO). Pro řešení těchto systémů používáme běžně teorie Markovovských přechodů, které podrobně řeší například [Linda, 1991], [Piatka, 1981]. Nejčastěji se příchod řídí exponenciálním rozdělením pravděpodobnosti s hustotou pravděpodobnosti:
f (t ) = λ ⋅ e − λ ⋅t
pro t > 0
Pro další výpočet zavedeme další označení a potřebné vztahy z [Linda,1991]: n – počet obslužných kanálů k – počet požadavků v systému λ - střední intenzita příchodu požadavku a je to střední počet významných událostí, které nastanou za časovou jednotku λ∆t – pravděpodobnost, že v době t až t+∆t vstoupí do fronty nový požadavek, µ - střední intenzita obsluhy je střední počet zákazníků, které je linka schopna obsloužit za časovou jednotku µ∆t – pravděpodobnost, že obsluhovaný požadavek bude obsloužený v době t až t+∆t.
Podíl intenzity příchodu požadavku a intenzity obsluhy označíme β.
β=
λ . µ
(6.1)
Dopravní intenzitu můžeme vyjádřit vztahem:
ρ=
λ n⋅µ
(6.2)
Pokud ρ < 1 je střední doba příchodu větší než střední doba obsluhy a neporoste počet požadavků ve frontě, o takovémto systému můžeme říci že je stabilizovaný. Pro další výpočty je nutno stanovit pravděpodobnost, že v systému není žádný požadavek (k = 0):
p0 =
1 β nn ∞ k + ∑ ∑ρ n! k = n k = 0 k! n −1
(6.3)
k
Pravděpodobnost, že v systému je k požadavků, kdy platí k ≥ n , je možno stanovit
pk = ρ (k −n ) p n =
βk . p0 n!n ( k − n )
(6.4)
v případě, že v systému je právě n požadavků (k=n) je pravděpodobnost tohoto stavu: ∞
∞
k =n
k =n
pk =n = ∑ pk = ∑ pn ρ k −n = p n
1 1− ρ
(6.5)
Tento stav je možno charakterizovat jako pravděpodobnost toho, že příchozí požadavek nebude muset čekat ve frontě. Pak můžeme vyjádřit základní statistické parametry systému hromadné obsluhy M/M/n. Střední počet obsazených linek obsluhy:
ν =β =
λ µ
(6.6)
Průměrný počet požadavků ve frontě:
Q = pn ⋅
ρ (1 − ρ )2
(6.7)
Průměrný počet požadavků v systému:
L = Q +ν
(6.8)
Průměrná doba čekání ve frontě:
EW =
p nµ − λ
(6.9)
Průměrná doba pobytu v systému:
ER = EW +
1 µ
(6.10)
6.1.4 Příklad řešení stochastického systému hromadné obsluhy typu M/M/n Zadání: K čerpací stanici pohonných hmot se dvěmi stojany přijíždí každých 80 sekund jeden automobil. Doba obsluhy jednoho automobilu trvá průměrně 2,5 minuty. Za předpokladu, že příchody zákazníků tvoří Poissonův proces, vypočtěte:
-
pravděpodobnost, že u čerpací stanice nebude žádný automobil, pravděpodobnost, že u čerpací stanice budou právě 2 automobily, střední počet automobilů čekajících ve frontě, střední počet obsazených stojanů, střední prostoj jednoho automobilu ve frontě, střední dobu, kterou stráví řidič jednoho automobilu u čerpací stanice,
Vypočtěte všechny uvedené veličiny pro případ zdvojnásobení počtu stojanů ze 2 na 4 a výsledky navzájem porovnejte. Řešení: Určení λ: λ. střední počet automobilů za 1 hodinu
λ=
60.60 = 45 80
Určení µ: µ. střední počet zákazníků, které je linka schopna obsloužit za 1 hodinu
1 1 60 = = = 24 ⇒ µ = 24 µ 2,5 2,5 60
[1]
Určení β:
β=
λ 45 = µ 24
[1]
Určení ρ:
λ 45 45 = = = 0,9375 〈 1 n.µ 2.24 48 ρ 〈 1....vyhovuje podmínce stabilizace systému
ρ=
Pravděpodobnost, že u čerpací stanice nebude žádný automobil, vypočteme podle (6.3):
p0 =
1 β nn + ∑ n! k = 0 k! n −1
k
∞
∑ρ k =n
= k
1 2
45 2 2 45 1 1+ + 45 24 2! 48 1− 48
= 0,0323
[1]
Pravděpodobnost, že u čerpací stanice budou dva automobily, vypočteme podle (6.4):
2
45 k β 24 pk = . po = ⋅ 0,0323 = 0,0567 k! 2!
[1]
Pravděpodobnost, že automobil, který přijede k čerpací stanici, bude muset čekat, vypočteme podle (6.5):
p = p2
1 = 0,0567. 1− ρ
1 = 0,907 45 1− 48
[1]
Střední počet automobilů, čekajících ve frontě vypočteme podle (6.7):
Q = p2
0,9375 ρ = 0,0498 = 13,61 2 (1 − ρ ) (1 − 0,9375)2
[1]
Střední počet obsazených stojanů u čerpací stanice (tj. počtu obsluhovaných) vypočteme podle (6.6):
ν =β =
45 = 1,87 24
[1]
Střední počet automobilů u čerpací stanice celkem vypočteme podle (6.8):
L = γ + ν = 13,61 + 1,87 = 15,48
[1]
Střední prostoj jednoho automobilu ve frontě se vypočte podle (6.9):
EW =
p 0,907 = = 0,302 h nµ − λ 2.24 − 45
Střední doba ER, kterou stráví jeden zákazník v systému, se vypočte podle (6.10):
ER = EW +
1 1 = 0,302 + = 0,344 h µ 24
Výsledky pro případ zdvojnásobení počtu stojanů u čerpací stanice jsou v následující tabulce Tab. 6.2, kde n je počet stojanů (tj. obsluhových linek).
Tab. 6.2: Výsledky příkladu. n
ρ
p0
p2
Q
ν
L
EW
ER
2
0,94
0,032
0,057
13,6
1,88
15,5
0,302
0,344
4
0,47
0,149
0,193
0,1
1,88
2
0,003
0,045
K obdobným výsledků je možno dospět pomocí hodnot, které jsou výsledkem simulačního experimentu, který je postaven na modelu systému hromadné obsluhy se stejnými parametry a s postupy popsanými v následujícím textu.
