1
Teorie hromadné obsluhy
Teorie hromadné obsluhy zkoumá modely, v nichž do nějakého systému obsluhy, kerý může mít jeden či více linek obsluhy vstupují jednotky, které mají být těmito linkami obslouženy. Typickým příkladem může být prodejna, kam přicházejí zákazníci a ti musejí projít přes určitý počet kas, kadeřnictví, kde určitý počet kadeřnic se snaží uspokojit náhodně příchozivší zákaznice atd. Je vidět, že v těchto modelech se pracuje s prvky náhody, neboť počet vstupujících jednotek (např. zákazníků) bývá náhodný, doba, kterou stráví jednotka v systému (délka obsluhy u kasy, délka doby střihání) je náhodná. Cílem těchto úloh je často optimalizovat počet linek tak, aby zbytečně nedocházelo k frontám či opouštění systému (můžeme uvažovat, že někteří zákazníci raději odejdou, než aby čekali ve frontě) a naopak aby nebyli zbytečné náklady (vždycky bychom mohli ke kasám posadit tolik prodavaček, že by se žádné fronty netvořily). Jak jsme již poznamenali, tyto modely pracují s prvky náhody, jedná se o tzv. stochastické modely. Řešení je možné dvojího typu. Analytické – spočívá v tom, že na základě známých parametrů modelu pomocí nástrojů teorie pravděpodobnosti či jiných matematických odvětví spočteme či odhadneme ty parametry modelu, kterou nás zajímají (např. průměrný počet zákazníků ve frontě, apod.). Simulační – známých parametrů modelu využijeme k nasimulování dané situace pomocí nějakého vhodného software. Na základě těchto simulací odhadneme parametry modelu, které nás zajímají.
1.1
Parametry modelu
K vytvoření matematického medelu hromadné obsluhy, potřebujeme specifikovat: • vstup jednotek • doby obsluhy na jednotlivých linkách • siť obslužných linek • pravidla pro odchod z front do systému obsluhy • specifické rysy systému 1.1.1
Vstup jednotek
Je zřejmé, že jednou z hlavních charakteristik systému hromadné obsluhy je vstup jednotek do tohoto systému. Většinou přicházejí jednotky do systému v náhodných časech takových, že doba mezi příchody jednotlivých jednotek je náhodná veličina. Neboli tato doba je náhodná a lze určit její rozdělení. 1
(To buď známe či předpokládáme nebo ho potřebujeme určit.) Velmi často se předpokládá, že doba mezi příchody jednotlivých jednotek má exponenciální rozdělení. (Někdy se také využívá Erlangovo rozdělení, popř. obecné rozdělení náhodné veličiny.) Nemáme-li přesně stanoveno, jaké rozdělení mají intervaly mezi vstupy jednotlivých jednotek, pak mohou nastat dva případy. Buď známe rozdělení a neznáme jen jeho parametry (např. víme, že se jedná o exponenciální rozdělení, ale neznáme jeho střední hodnotu), a pak musíme využitím statistických metod tento parametr určit, anebo neznáme ani rozdělení doby příchodu, a pak musíme statickými metodami určit vhodné rozdělení včetně parametrů. Tyto metody ovšem nejsou náplní tohoto předmětu. Také se může stát, že doby mezi vstupy jednotlivých jednotek nebudou nezávislé, a potom by mohlo dojít k selhání modelu, pokud bychom opoměli tuto skutečnost do modelu zařadit. V případě, že jednotlivé vstupy nejsou nezávislé náhodné veličiny, dochází většinou ke značnému stížení řešení situace. My pouze poznamenáme, že jednou z možností, jak se této situaci vyhnout, může být rozdělení modelů do podmodelů v závislosti na době, kdy model zkoumáme (např. doba špičky).
1.2
Doba obsluhy
Stejně jako v případě příchodů jednotek do systému i zde potřebujeme znát rozdělení doby obsluhy jednotlivých jednotek v systému. Opět tyto jednotlivé doby mohou být nezávislé náhodné veličiny, jejichž rozdělení známe, či potřebujeme zjistit, viz předchozí odstavec. Ovšem může se stát, že doba obsluhy závisí na čase a stavu systému (např. únava, či jiný obsluhující), někdy také musíme uvažovat poruchovost obslužných linek. To vše opět komplikuje řešení úloh.
1.3
Síť obslužných linek
Je třeba vědět, kolik linek je v provozu a zda obsluhují paralelně, sériově, nebo je zde nějaké speciální uspořádání.
1.4
Pravidla odchodu z front do systému obsluhy
Pro výpočet doby, kterou jednotka stráví ve frontě nebo celkově v systému je nezbytné znát pravidla, podle jakých odcházejí jednotky z fronty do systému. Pro tato pravidla se vžilo následující značení: FIFO – first in, first out, LIFO – last in, first out, SIRO – selection in random order, GD – general discipline.
2
Problémy zde může způsobit například proměnný systém těchto pravidel, či případ, kdy některé jednotky mají prioritu obsluhy.
1.5
Specifické rysy systému
Někdy výše popsané charakteristiky nestačí k popsání systému, např. pokud je omezen počet míst ve frontě, ”netrpělivost” vstupních jednotek (při určité délce fronty, opustí systém), apod.
2
Klasifikace systémů hromadné obsluhy
V matematickém modelování ekonomických procesů se vždy snažíme situaci co nejvíce zjednodušit. Zjednodušit ji co nejvíce, jak je možné, abychom neopomněli nějakou podstatnou podmínku, čímž bychom vytvořili neodpovídající model. Díky zjednodušení je potom možné úlohu vyřešit, či ji vyřešit snáze. A tak se ukazuje, že přes všechny výše popsané problémy, je možné klasifikovat několik ”klasických” modelů hromadné obsluhy, které je možné využít v mnoha případech reálného života. V těchto modelech se předpokládá, že doby mezi příchody jednotlivých jednotek do systému jsou nezávislé. Typ systému obsluhy se popisuje trojicí (A/B/c), kde A udává rozdělení příchodu jednotek do systému, B udává rozdělení doby obsluhy a c počet linek obsluhy. Nejčastěji používanými symboly jsou: M – pro exponenciální rozdělení, Ek – pro Erlangovo rozdělení řádu k (tvz. Γk -rozdělení), G – pro obecné rozdělení, D – pro deterministickou dobu trvání. Příklad: Systém (M/G/2) je systém, kde doba mezi vstupy jednotlivých jednotek do systému má exponciální rozdělení, doba obsluhy jedné jednotky má obecné rozdělení a v systému jsou dvě obslužné linky.
3
Příklad
Pan Ševčík přemýšlí o zbudování mycí linky aut u svého autoservisu. Rozhoduje se, zda postavit jednu nebo dvě linky. Od expertů na teorii front si nechá pro variantu jedné i pro variantu dvou linek spočítat následující data, na základě těch se posléze rozhodne. 1. Kolik průměrně aut bude čekat ve frontě? 2. Jak dlouho v průměru bude zákazník čekat na obsluhu? 3
3. Jakou část času bude linka nevyužita? 4. Jaký je počet aut ve frontě, který nebude překročen s pravděpodobností 95%? 4
4
Výpočty
Metoda výpočtu se samozřejmě liší pro jednotlivé modely. Nejprve si uveďme značení, které je společné všem modelům. N (t) – počet jednotek přítomných v systému (ve frontě i v obslužných linkách), Tn – okamžik vstupu n-té jednotky do sytému, tn – doba mezi vstupem (n − 1). a n-té jednotky do systému, tedy zřejmě tn = Tn − Tn−1 , T – náhodná veličina vyjadřující dobu mezi vstupy dvou po sobě jdoucích jednotek, xn – doba obsluhy n-té jednotky, X – náhodná veličina udávající dobu obsluhy jedné jednotky, wn – doba čekání ve frontě n-té jednotky, sn – doba strávená v systému n-tou jednotkou, tedy sn = wn + xn . Poznámka: Jak jsme již poznamenali, A značí distribuční funkci doby mezi vstupy jednotivých jednotek, proto můžeme psát: P(tn ≤ t) = A(t). A B je distribuční funkce doby obsluhy jednotky, proto: P(xn ≤ t) = B(t). 4
4.1
Základní vztahy
Označme si: α(t) – počet příchodu do systému v době (0, t), β(t) – počet odchodů ze systému za dobu (0, t). Pokud systém začínal prázdný, tj. N (0) = 0, potom N (t) = α(t) − β(t). 4
Obecněji platí: N (t) = α(t) − β(t) + N (0). Celková doba, kterou strávili jednotky v systému (tedy počet jednotkohodin) je:
Z
t
γ(t) =
N (t)dt. 0
Potom je zřejmé, že pokud označíme průměrnou intenzitu vstupu do systému ¯ t (tedy průměrný počet jednotek vstupujících do systému na za dobu (0, t) λ jednotku času), potom ¯ t = α(t) . λ t A průměrná doba, kterou strávila jedna jednotka v systému za dobu (0, t) je γ(t) T¯t = . α(t) ¯t – průměrný počet zákazníků v systému v době (0, t), pro Dále zaveďme N který platí: ¯ (t) = γ(t) . N t A tak můžeme psát: ¯t. ¯ (t) = γ(t) = γ(t) · α(t) = T¯t · λ N t α(t) t Pokud tedy předpokládáme existenci následujících limit: ¯t lim λ
=
¯ λ,
lim T¯t
=
T¯,
¯t lim N
=
¯, N
t→+∞ t→+∞ t→+∞
potom také platí tzv. Littleův vztah: ¯ · T¯. ¯ =λ N Poznámka: Snadno nahlédneme, že pokud nebudeme do doby pobytu v systému uvažovat dobu obsluhy (tedy jednotka vystupuje ze systému v okamžiku, kdy vstupuje do obsluhy), potom tento vztah lze psát: ¯ · T¯f , ¯f = λ N ¯f je průměrný počet jednotek ve frontě a T¯f je průměrná doba čekání ve kde N frontě. 4 Ještě poznamenejme, že jistě platí: T¯ = T¯f + EX. 5
5
Jednoduchý exponenciální model (M/M/1)
Tento model předpokládá jednu obslužnou linku s dobou obsluhy, která se řídí exponenciálním rozdělením a předpokládá vstup jednotek do systému také pod exponenciálním rozdělením. Poznámka: Není-li dáno jinak, předpokládá se systém fronty FIFO a neomezený počet míst ve frontě. 4 Jak známo, exponenciální rozdělení má jeden parametr, tradičně se značí λ a λ1 udává střední hodnotu náhodné veličiny. V teorii hromadné obsluhy se vžilo značení λ – pro parametr vstupu jednotek (jedná se tedy o intenzitu vstupu jednotek), µ – pro parametr doby obsluhy (jde tedy o intenzitu výstupu). Doba mezi vstupy dvou po sobě jdoucích jednotek má exponenciální rozdělení s parametrem λ, tedy hustota náhodné veličiny T je a(t) = λ exp −λt pro t ≥ 0. A podobně hustota náhodné veličiny X udávající dobu obsluhy jedné jednotky v systému je b(t) = µ exp −µt pro t ≥ 0. Je vidět, že teď už máme celý model zadaný, a tak zřejmě všechny výsledky budou funkce pouze dvou parametrů λ a µ. Označme si pn (t) := P(N (t) = n). Naším cílem je získat hodnoty pn (t). Nejprve si odvoďme hodnoty pn (t + h), kde h je malý časový interval. Stav systému v okamžiku (t + h) je závislý na stavu systému v okamžiku t, a to následujícím způsobem (ve vztazích se využívá toho, že se jedná o exponenciální rozdělení vstupů a doby obsluhy): P(jeden vstup během (t, t + h)) P(žádný vstup během (t, t + h)) P(více vstupů během (t, t + h)) P(1 dokončená obsluha v (t, t + h), v t systém neprázdný) P(více než 1 dok. obs. v (t, t + h), v t systém neprázdný)
= λh + o(h), = 1 − λh + o(h), = o(h), = µh1 + o(h), = 1 − µh1 + o(h),
P(1 dokončená obsluha v (t, t + h), v t systém prázdný) = P(žádná dok. obs. v (t, t + h), v t systém prázdný) =
o(h), 1 − o(h).
Poznámka: Připomeňme, že řekneme, že funkce f (x) nabývá hodnot o(x) pro x → 0, pokud platí: f (x) lim = 0. x→0 x 6
Pro naše výpočty to znamená, že člen o(h) je pro „maléÿ hodnoty h tak malý, že ho můžeme zanedbat (pokládat za nulový). 4 Poznámka: Poznamenejme, že odvození výše uvedených vztahů vychází ze znalostí exponenciálního rozdělení. 4 Z uvedených vztahů je zřejmé, že pokud má být systém v čase t + h ve stavu n (ne právě s téměř nulovou pravděpodobností), potom musí v čase t být ve stavu n − 1, n nebo n + 1. Situaci nastiňuje tabulka: Stav v t n n n-1 n+1
Příchody během h 0 1 1 0
Odchody během h 0 1 0 1
A tak je snadno vidět, že pravděpodobnost, že v systému bude v čase t + h právě n jednotek lze zapsat následujícím způsobem: pn (t + h) = + + + =
pn (t)(1 − λh + o(h)) · (1 − µh + o(h)) + pn (t)(λh + o(h)) · (µh + o(h)) + pn−1 (t)(λh + o(h)) · (1 − µh + o(h)) + pn+1 (t)(1 − λh + o(h)) · (µh + o(h)) p( t) − (λ + µ)hpn (t) + λhpn−1 (t) + λhpn+1 (t) + o(h).
Poznámka: Připomeňme, že h2 je také o(h). 4 A tak získáváme (po limitním přechodu h → 0) pro n ≥ 1: 0
pn (t) = −(λ + µ)pn (t) + λpn−1 (t) + µpn+1 (t). Tento vztah neplatí pro n = 0, poněvadž v případě prázdného systému jsou pravděpodobnosti přechodu jiné. Sestavme si tabulku pro případ n = 0, resp. pro případ, kdy chceme, aby byl systém v době (t + h) prázdný. Stav v t 0 1
Příchody během h 0 0
Odchody během h 0 1.
Stejným postupem jako v předchozím případě získáme: 0
p0 (t) = −λp0 (t) + µp1 (t). Uvažujme, že řešíme tzv. stacionární systém, to znamená systém, ve kterém pravděpodobnosti jednotlivých stavů nezávisí na čase (t). Většina „rozumně 7
se chovajících systémůÿ se ustálí do takového stavu, a nás potom zajímají pravděpodobnosti pn (t), které ovšem nezávisí na čase, tudíž se jedná vlastně pouze o pravděpodobnosti pn , což jsou pravděpodobnosti, že v systému bude n jednotek (měřeno v kterém koliv čase). Kdy se jedná o stacionární a kdy nastává problém nestacionárních systémů, to je otázka pro hlubší studium. Pokud tedy předpokládáme, že máme stacionární systém, potom derivace funkcí pn jsou nuly (jedná se o konstantní funkce), a tak dvě výše odvozené rovnice můžeme přepsat: 0 = 0 =
−(λ + µ)pn + λpn−1 + µpn+1 −λp0 + µp1 .
pro n ≥ 1
(1) (2)
Což si můžeme přepsat: pn+1
=
p1
=
λ+µ λ pn − pn−1 µ µ λ p0 . µ
pro n ≥ 1
Teď je již vidět, že pokud budeme znát hodnotu p0 , potom všechny ostatní hodnoty pn získáme postupným dosazováním. A po vyzkoušení (důkaz matematickou indukcí) snadno ověříme, že lze hodnoty pn vyjádřit pomocí hodnoty p0 následovně: µ ¶n λ pn = p0 . µ Zbývá tedy jediná otázka, a to, jaká je hodnota p0 . Tedy jaká je pravděpodobnost, že systém bude prázdný? Protože hodnoty (pn , n ∈ N0 ) udávají pravdědobnosti úplné kolekce disjunktních jevů, je zřejmé, že platí: +∞ X
pn = 1.
n=0
Pokud si hodnoty pn vyjádříme pomocí p0 získáme: +∞ µ ¶n +∞ µ ¶n X X λ λ 1= p0 = p0 . µ µ n=0 n=0 A tak s využitím znalostí z matematiky získáváme (pro podmínka k tomu, aby systém byl stacionární)): p0 = 1 −
λ µ
< 1(což je také nutná
λ . µ
A tak snadno nahlédneme, že pravděpodobnost, že systém není prázdný je µλ . Tato hodnota se také nazývá využitelností systému nebo, jak plyne ze smyslu parametrů λ, µ, průměrným počtem příchodů za průměrnou dobu obsluhy.
8
5.1
Charakteristiky systému M/M/1
Je-li N náhodná veličina udávájící počet jednotek v systému, potom jistě průměrný počet jednotek ve frontě je: µ ¶n ∞ ∞ X X λ EN = npn = p0 n . µ n=0 n=0 Tuto řadu lze využitím znalostí matematické analýzy sečíst: EN =
λ . µ−λ
Připomeňme, že celou dobu požadujeme µ > λ. Průměrná délka fronty se počítá obdobně: ENf = 0 · p0 +
+∞ X
(n − 1)pn = EN − p0 =
n=1
λ2 . µ(µ − λ)
Pravděpodobnost výskytu fronty nenulové délky: µ ¶2 λ P(N ≥ 2) = 1 − p0 − p1 = . µ A obecně k délce fronty platí: P(N ≥ k) =
µ ¶k λ . µ
A tak pro průměrnou dobu pobytu v systému můžeme psát (na základě Littleova vztahu): 1 λ 1 ET = · = . λ µ−λ µ−λ A průměrná doba čekání ve frontě je ETf = ET −
1 λ = . µ µ(µ − λ)
Na základě těchto znalostí již můžeme odpovídat na otázky týkající se systému (M/M/1). Příklad: Co tedy potřebujeme vědět od pana Ševčíka, abychom mu mohli odpovědět na jeho otázky? Potřebujeme znát dva parametry λ a µ. Tedy, chce-li pan Ševčík znát odpovědi na své otázky, musí nám zdělit, jaká je střední doba, kterou auto stráví v myčce (odtud získáme µ) a kolik průměrně aut během hodiny předpokládá, že navštíví jeho myčky (tím získáme λ). Pan Ševčík ví, že auto stráví v myčce průmerně 6 minut a předpokládá, že průměrně jeho myčku využije 8 aut za hodinu. 9
Potom můžeme psát: λ = 8, µ = 10. A tedy využitelnost jedné linky je 8/10, tedy 80%. Střední délka fronty je EN =
λ 8 = = 4. µ−λ 10 − 8
Chceme-li spočítat, jaký počet aut ve frontě nebude převýšen s pravděpodobností 95%, potom hledáme takové nejmenší K pro něž platí: µ ¶K λ P(N ≥ K) = = 0, 8K ≤ 0, 05. µ Dosteneme hodnotu 14. A průměrná doba, jakou stráví zákazník u myčky je hodiny.
6
1 µ−λ
= 1/2, tedy půl
Model M/M/c
Předpokládejme model, který má stejné parametry jako předchozí, jedinou změnou je, že je zde více, resp. c, linek obsluhy. Podmínkou pro stacionaritu tohoto systému je λ < 1. cµ Jedná se vlastně o stejnou podmínku jako v předchozím případě, o podmínku, aby intenzita odchodů byla vetší než intenzita příchodů. Podobným způsobem jako v předchozím případě (rozepsáním jednotlivých situací) získáme následující vztahy pro pravděpodobnosti pn . Situace je o to komplikovanější, že pravděpodobnost odchodu jedné jednotky ze systému se v tomto případě dělí na více případů než v předchozí situace (to šlo jen o to, zda je systém prázdný či neprázdný), zde bude třeba odlišit, zda je v systému 0, 1, . . . , c − 1 či c a více jednotek. Lze tedy odvodit:
pn
=
pn
=
λn p0 pro 1 ≤ n < c, n!µn λn p0 pro n ≥ c. c!cn−c µn
A zase s využítím vzorce o úplné pravděpodobnosti odvodíme hodnotu p0 : !−1 Ã c−1 X rn crc + , p0 = n! c!(c − r) n=0 kde r =
λ µ.
Dále uveďme základní charakteristiky systému (M/M/c). 10
Průměrná délka fronty se počítá obdobně: +∞ X
1 ENf = (n − c)pn = p0 (c − 1)! n=c
µ ¶c λ λµ . µ (cµ − λ)2
Průměrná doba čekání ve frontě se vypočte ze vztahu: ETf =
ENf . λ
Průměrná doba jednotky v systému je ET = ETf +
1 . µ
Střední počet obsazených linek obsluhy EU lze spočíst ze vztahu: EU =
c X
+∞ X
npn +
n=0
cpn .
n=c+1
Po úpravách obdržíme EU =
λ . µ
Příklad: Vypočtěme pro pana Ševčíka charakteristiky systému pro případ, že by zřídil dvě mycí linky. Nejprve vypočtěme p0 , tedy pravděpodobnost, že obě linky budou prázdné. p0 = (1 + 0, 8 +
2 · 0, 82 −1 ) = 0, 428. 2 · 1, 2
Dále si spočtěme pravděpodobnost, že v systému bude jedno či dvě auta. p1
=
0, 8p0 = 0, 343,
p2
=
82 2 · 102 p0 = 0, 137.
Průměrná délka fronty bude ENf = p0 · 0, 82
80 = 0, 15. 122
Pravděpodobnost, že budou vytíženy obě linky je 1 − p0 − p1 , což je 22, 8%.
11
