Teorie hromadné obsluhy

4.12.2015

Teorie hromadné obsluhy Radim Farana Podklady pro výuku pro akademický rok 2013/2014

Obsah

Teorie hromadné obsluhy Klasifikace systémů hromadné obsluhy Systém hromadné obsluhy M/M/1/∞/∞/FIFO Systém hromadné obsluhy M/M/1/1/∞

Systém hromadné obsluhy M/M/n/n/∞  Literatura: JABLONSKÝ, Josef. Operační výzkum: kvantitativní metody pro ekonomické rozhodování. 3. vyd. Praha: Professional Publishing, 2007, 323 s. ISBN 978-80-86946-44-3.  Šeda, Miroslav. Modely hromadné obsluhy. Acta logistica Moravica, 2011, č. 2, ISSN: 1804 – 8315.Dostupný z webu:

Teorie hromadné obsluhy  Základy teorie hromadné obsluhy položil dánský George Kendall matematik Agner Krarup Erlang, který pracoval pro David * 5. 1. 1918, Ripon, UK + 23. 10. 2007, Cambridge, UK společnost provozující telefonickou síť v Kodani a v r. 1909 popsal aplikaci teorie pravděpodobnosti na problémy telefonního provozu.  O další rozvoj teorie se zasloužil zejména ruský matematik Andrej Nikolajevič Kolmogorov.  Klasifikaci systémů hromadné obsluhy tak, jak ji používáme dnes, zavedl v 50. letech minulého století anglický matematik David George Kendall.  Dnes jde již o klasickou část logistiky, popsanou v řadě monografií (Bose, 2001; Cooper, 1981; Gross et al., 2008) i vysokoškolských textů (Hrubina, Jadlovská, Hrehová, 2005; Jablonský, 2001; Klvaňa, 2005; Peltan, Májek, 2008; Virtamo, 2005). http://www-history.mcs.st-andrews.ac.uk/ Mathematicians/Kendall.html

1

4.12.2015

Systém hromadné obsluhy (SHO) je systém, který poskytuje služby přicházejícím zákazníkům. Pokud nemohou poskytnout službu ihned, shromažďují se neuspokojení zákazníci do fronty (proto také Teorie front). Např. auta přijíždějící na křižovatku, telefonující účastníci spojovaní centrálou, zákazníci přicházející do obchodu, …

Systém hromadné obsluhy obslužný systém

vstupní proud požadavků

fronta požadavků …

výstupní proud obsloužených požadavků

proud neobsloužených (odmítnutých) požadavků

Organizace fronty  Pokud se týče fronty, intuitivně ji chápeme tak, jak ji sami známe, tj. kdo dříve přijde do systému, dříve bude obsloužen (FIFO – first in, first out).  Možná je však i obsluha LIFO (last in, first out), kde naopak je první obsluhován požadavek, který do systému vstoupil poslední. Někdy bývá strategie LIFO označována i zkratkou LCFS (last come, first served). Příkladem obsluhy LIFO je odběr zboží ze skladu, kdy zboží (např. tabule skla, krabice s televizory), které bylo na sklad dodáno jako první, je v zadní části skladu, resp. naspodu hromady, a tedy jako poslední je přístupné.  Vedle obsluhy FIFO a LIFO se setkáme i s náhodným výběrem požadavku z fronty do obslužného systému (SIRO – selection in random order) a obsluhou řízenou prioritou požadavků (PRI – priority).

2

4.12.2015

Délka fronty  Délka fronty může být omezená, při dosažení určitého (předem definovaného) počtu požadavků do fronty se již další požadavky odmítnou, např. počet rezervací na knihu v knihovně, která je aktuálně vypůjčena; resp. neomezená, ve skutečnosti tím chápeme případ, kdy maximální možný počet požadavků ve frontě je velmi vysoký.  Požadavky ve frontě mohou mít omezenou nebo neomezenou trpělivost. V případě neomezené trpělivosti požadavky čekají na obsluhu tak dlouho, dokud na ně nepřijde řada, v systému s omezenou trpělivostí je zařazení do fronty do značné míry závislé na délce fronty. Místo délky fronty se také můžeme setkat s pojmem kapacita systému, kterým se míní maximální počet požadavků, který může být v systému přítomen.

Klasifikace SHO  r. 1951 Kendall navrhl klasifikaci SHO podle tří hlavních hledisek ve tvaru A/B/C, kde: A – charakterizuje typ pravděpodobnostního rozdělení náhodné veličiny doba (interval) mezi příchody požadavků do systému, B – charakterizuje typ pravděpodobnostního rozdělení náhodné veličiny doba obsluhy požadavku, C – je počet paralelně uspořádaných obslužných linek (nebo také počet kanálů), tj. jde o přirozené číslo, v případě „neomezeného“ (tj. velmi velkého počtu linek) je obvyklé parametr C vyjadřovat číslem ∞.

Klasifikace SHO Kendallova klasifikace dále rozšířena na tvar A/B/C/D/E/F, další parametry jsou: D – přirozené číslo udávající max. počet požadavků v systému (tj. kapacitu systému), není-li explicitně omezen, je vyjádřen ∞, E – přirozené číslo vyjadřující maximální počet požadavků ve vstupním proudu (nebo také ve zdroji požadavků), pokud je neomezen, opět se použije ∞, F – typ fronty (FIFO/LIFO/SIRO/PRI)..

3

4.12.2015

Parametr A  M – intervaly mezi příchody požadavků jsou navzájem stochasticky nezávislé a mají exponenciální rozdělení, to znamená, že vstupní proud reprezentuje Poissonův (Markovovův) proces,  Ek – Erlangovo rozdělení s parametry λ a k,  Kn – rozdělení χ2 s n stupni volnosti,  N – normální (Gaussovo) rozdělení,  U – rovnoměrné rozdělení,  G – obecný případ, doba mezi příchody požadavků je dána svou distribuční funkcí,  D – intervaly mezi příchody požadavků jsou konstantní (mají deterministický charakter). Pro parametr B se používá stejné označení pro dobu obsluhy požadavku

Poissonův (Markovovův) proces  Poissonův proces je proud jevů, který splňuje následující vlastnosti: 1. Stacionárnost (homogenita v čase) – počet jevů ve stejně dlouhých časových intervalech je konstantní. 2. Regulárnost (ordinárnost) – pravděpodobnost výskytu více než jednoho jevu v dostatečně malém intervalu délky Δt je zanedbatelně malá. To znamená, že v intervalu (t, t + Δt) se buď vyskytne právě jeden jev s pravděpodobností λ Δt anebo s pravděpodobností 1 – λ Δt se v tomto intervalu žádný jev nevyskytne. Jinak řečeno v Poissonově procesu je možný jen přechod systému do nejbližšího „vyššího“ stavu anebo setrvání v témže stavu. 3. Nezávislost přírůstků – počet jevů, které se vyskytnou v jednom časovém intervalu, nezávisí na počtu jevů v jiných intervalech,

Systém hromadné obsluhy M/M/1/∞/∞/FIFO  Uvažujeme nejdříve situaci na vstupu systému izolovaně od procesu obsluhy a zavedeme náhodnou veličinu počet požadavků, které přišly do systému během intervalu 〈t0, t0 + Δt〉, kde t  0,  Vzhledem ke stacionárnosti Poissonova procesu počet požadavků nezávisí na volbě počátečního okamžiku t0 a význam má pouze délka uvažovaného intervalu Δt.  Nechť pk(t) označuje pravděpodobnost toho, že v čase t je v systému právě k požadavků. Z regulárnosti Poissonova procesu vyplývá, že pravděpodobnost, že v čase t+Δt bude v systému k požadavků je rovna pravděpodobnosti toho, že v čase t bylo v systému k–1 požadavků a během doby Δt vstoupil do systému jeden požadavek s pravděpodobností λ Δt anebo v čase t bylo v systému k požadavků a během doby Δt s pravděpodobností 1–λ Δt do systému žádný nový požadavek nevstoupil. Z pravidel pro výpočet . pravděpodobnosti konjunkce a disjunkce nezávislých jevů odtud plyne vztah:

pk (t  t )  pk 1 (t ).t  pk (t ).1  t , k  1, 2, ...

4

4.12.2015

Systém hromadné obsluhy M/M/1/∞/∞/FIFO  Pravděpodobnost, že v čase t + Δt v systému není žádný požadavek je dána pravděpodobností toho, že tam žádný požadavek nebyl a ani během doby Δt žádný nevstoupil, tj.

p0 (t  t )  p0 (t ).1  t 

 Po snadné úpravě ze předchozích vztahů dostaneme vztahy:

pk (t  t )  pk (t )  . pk 1 (t )  . pk (t ), k  1, 2, ... t p0 (t  t )  p0 (t )  . p0 (t ) t

 Nyní v těchto vztazích provedeme limitní přechod pro . t  0. Dostáváme:

pk (t  t )  pk (t )  lim . pk 1 (t )  . pk (t ), k  1, 2, ... t 0 t p0 (t  t )  p0 (t ) lim  lim  . p0 (t )  t 0 t 0 t lim

t 0

Systém hromadné obsluhy M/M/1/∞/∞/FIFO  Výrazy na levé straně předchozích dvou vztahů jsou derivacemi funkcí pk(t) a p0(t) v bodě t, tj. pk’(t) a p0’(t), zatímco na jejich pravé strany nemá limitní přechod vliv. Odtud tedy dostáváme rekurentní vztahy:

pk, t   . pk 1 (t )  . pk (t ), k  1, 2, ...

p0, t   . p0 (t )  Tyto rekurentní vztahy představují soustavu nekonečně mnoha obyčejných diferenciálních rovnic 1. řádu. Pro jejich řešení potřebujeme znát počáteční podmínky. Je však zřejmé, že v čase 0 se žádné požadavky v systému ještě nenachází, a tedy

pk (0)  0, k  1, 2, ...

p0 (0)  1

Systém hromadné obsluhy M/M/1/∞/∞/FIFO  Z teorie obyčejných diferenciálních rovnic je známo, že řešením předchozí soustavy rovnic s uvedenými počátečními podmínkami je soustava funkcí: 2   t t  pk t  e

k!

, k  0, 1, 2, ...

 čili pro k = 0: p0 t   e  t

5

4.12.2015

Systém hromadné obsluhy M/M/1/∞/∞/FIFO Grafické zobrazení funkcí p k (t ) pro k = 0,1, … , 5 a λ = 2. 1,2

1

0,8 k=0 k=1 k=2

0,4

k=3 k=4 k=5

pk (t )

0,6

0,2

0 0

1

2

3

4

5

6

7

-0,2 t

Systém hromadné obsluhy M/M/1/∞/∞/FIFO  Je vidět, že v systému M/M/1 náhodná veličina počet požadavků, které přišly do systému za časový interval délky t, má Poissonovo rozdělení s parametrem λ t.  Střední hodnota této náhodné veličiny je λ t a speciálně pro t = 1 je střední hodnota náhodné veličiny počet požadavků, které přišly do systému za časovou jednotku rovna λ. t 2 , k  0, 1, 2, ... pk t   e t  k!  Říkáme, že λ je střední intenzita vstupu nebo krátce intenzita vstupu a vyjadřuje průměrný počet požadavků, které do systému vstoupily za časovou jednotku. p0 t   e  t

Systém hromadné obsluhy M/M/1/∞/∞/FIFO  Náhodná veličina interval mezi příchody požadavků má exponenciální rozdělení.  Označíme tuto veličinu T. Pak pravděpodobnost toho, že po vstupu jednoho požadavku žádný další požadavek po celou dobu intervalu t do systému nevstoupil, je rovna p0(t), a tedy: PT  t   p0 t   e t  Odtud dostáváme distribuční funkci F(t) exponenciálního rozdělení s parametrem λ. F (t )  PT  t   1  PT  t   1  et

6

4.12.2015

Systém hromadné obsluhy M/M/1/∞/∞/FIFO  Střední hodnota náhodné veličiny T vyjadřující průměrný čas mezi dvěma po sobě jdoucími požadavky je E T  

1



Systém hromadné obsluhy M/M/1/∞/∞/FIFO  Analogicky můžeme nyní zkoumat proces obsluhy. Předpokládáme, že náhodná veličina doba obsluhy jednoho požadavku (krátce doba obsluhy) má exponenciální rozdělení.  Parametr tohoto rozdělení označme μ, přičemž obecně platí, že    . Střední hodnota náhodné veličiny doba 1 obsluhy TO je E TO     a parametr μ udává střední hodnotu počtu požadavků obsloužených za časovou jednotku doby práce kanálu, stručněji střední intenzitu obsluhy, krátce intenzitu obsluhy.

Systém hromadné obsluhy M/M/1/∞/∞/FIFO  Pro popis chování systému je důležitá intenzita zatížení systému (anebo také intenzita provozu kanálu): 

 

průměrný počet příchodů zákazníků za jednotku času průměrný počet obsloužených zákazníků za jednotku času

 pro konvergenci systému je nutné, aby platilo:  1    

7

4.12.2015

Systém hromadné obsluhy M/M/1/∞/∞/FIFO  Pokud systém se stejnými parametry pracuje dostatečně dlouho, dojde k ustálení systému ve stacionárním stavu.  Pak můžeme určit následující charakteristiky systému.  Stacionární pravděpodobnost počtu požadavků v systému: Pk  1   k , k  0, 1, 2, ...

Systém hromadné obsluhy M/M/1/∞/∞/FIFO  Průměrný počet požadavků v systému: E N s   ns 

 1 



  

rozptyl:

D N s  



1  2

 Průměrný počet požadavků ve frontě: E N f   n f 

2 1 

  .ns

rozptyl:

DN f  

 2 1   2  1  2

 Vidíme, že průměrná délka fronty se od průměrného počtu požadavků v systému liší o ψ a ne o 1, jak bychom čekali.

Systém hromadné obsluhy M/M/1/∞/∞/FIFO  Střední doba setrvání požadavku v systému: E Ts   t s 

ns

E T f   t f 

nf





 1   1     

rozptyl:

DTs  

1

   2  Střední doba čekání požadavku ve frontě: 



2    1    1  

rozptyl:

DT f  

 2      2

 Střední doba obsluhy: E TO  

1



8

4.12.2015

Systém hromadné obsluhy M/M/1/∞/∞/FIFO  Koeficient prostoje obslužného kanálu: K0  p0  1 

 Koeficient využití (zatížení) obslužného kanálu: K1  1  p0  1  1    

Příklad: SHO M/M/1/∞/∞/FIFO Použijeme zjednodušený model M/M/1 na vyšetření chování menzy. Bylo zjištěno, že do menzy přijde během 117 minut 650 strávníků. Průměrná doba výdeje oběda je 5 minut. E T  

1



E TO  





650 117    0,18 min 1 117 650

1

 5 [min]    0,2 min





1







 0,18   0,9  0,2

Příklad: SHO M/M/1/∞/∞/FIFO  Průměrný počet požadavků v systému: E N s   ns 

0,9 9 1  0,9

rozptyl:

D N s  



1  2



0,9  90 0,12

 Průměrný počet požadavků ve frontě: E N f   n f  rozptyl:

2 1 

DN f  

  .ns  8,1

 2 1   2   88,29 1  2

9

4.12.2015

Příklad: SHO M/M/1/∞/∞/FIFO  Střední doba setrvání požadavku v systému: E Ts   t s 

ns





9  50[min] 0,18

rozptyl:

DTs  

1

 2500

   2  Střední doba čekání požadavku ve frontě: nf 8,1  2   E T f   t f    45[min]  2475 rozptyl: DT f    0,18    2  Střední doba obsluhy: E TO  

1



 5[min] Kontrolní otázka: Platí vždy E(Ts) = E(Tf) + E(TO)?

Systém hromadné obsluhy M/M/1  Jiné systémy správy fronty.  Průměrná doba strávená v systému se nemění, ale zvětší se rozptyl. Pro frontu LIFO:  Střední doba setrvání požadavku v systému: E Ts   t s 

ns





 1   1     

rozptyl:

DTs   DT f  

1

2

 Střední doba čekání požadavku ve frontě: E T f   t f 

nf





2    1    1  

rozptyl:

DT f  

 2   2     3

SHO M/M/1/1/∞  Jde o systém bez čekání a fronta se nevytváří.  V systému jsou možné jen dva stavy: p0  p1 

  

p0  p1  1



10

4.12.2015

SHO M/M/n/n/∞ Charakteristiky systému. Pravděpodobnost ztráty (odmítnutí) požadavku (pravděpodobnost, že v systému je jeden požadavek a jediná obslužná linka je obsazena)  pzt  p1 



Relativní kapacita systému (pravděpodobnost obsluhy požadavku) (pravděpodobnost obsluhy požadavku) K r  pobsl  p0 

 

SHO M/M/n/n/∞ Absolutní kapacita systému (počet obsloužených požadavků za časovou jednotku) K a  K r .

Nominální kapacita systému (maximální počet požadavků, které je systém schopen obsloužit za časovou jednotku) K nom  

SHO M/M/n/n/∞ Koeficient prostoje obslužného kanálu K 0  p0

Koeficient využití (zatížení) obslužného kanálu K z  1  p0  p1

11

4.12.2015

SHO M/M/n/n/∞  Pokud systém M/M/1 nevyhovuje požadavkům, je několik cest ke zdokonalení (zkrácení front) 1. Byrokratický – omezení příchodu zákazníků (zmenšení parametru příchodů λ). 2. Intenzívní – zrychlení obsluhy (zvýšení hodnoty parametru obsluhy μ). 3. Extenzívní – zvýšení počtu obslužných míst.

SHO M/M/n/n/∞  Předpokládáme, že všechny obslužné linky pracují se stejným parametrem obsluhy μ.  Pro stabilizaci systému musí platit λ < n.μ.   Označíme parametr   

SHO M/M/n/n/∞ Pravděpodobnost jednotlivých stavů p0 

1 n



k

k 0

k!

p1   .p0 p2 

2 2!

. p0

pk 

k k!

. p0 , k  1, 2, ...

12

4.12.2015

SHO M/M/n/n/∞ Charakteristiky systému. Pravděpodobnost ztráty (odmítnutí) požadavku (pravděpodobnost, že všechny obslužné jsou obsazeny) pzt  pn 

n

p0

n!

Relativní kapacita systému (pravděpodobnost obsluhy požadavku) (pravděpodobnost toho, že alespoň jedna z obslužných linek je volná) K r  1  pzt

SHO M/M/n/n/∞ Absolutní kapacita systému (počet obsloužených požadavků za časovou jednotku) K a  K r .

Střední hodnota počtu obsazených obslužných linek: n

E N obs   nobs   k . pk k 0

SHO M/M/n/n/∞ Střední hodnota počtu volných obslužných linek E N   n   n  k  p   n. p  k . p    n. p    k . p   n

0

0

k 0

n

n

k 0

k 0

n

k

k 0

n

k

k

k 0

n

k

k 0

k

 n pk  k  pk  n  nobs

Nominální kapacita systému (maximální počet požadavků, které je systém schopen obsloužit za časovou jednotku) K nom  n.

13

4.12.2015

SHO M/M/n/n/∞ Koeficient prostoje obslužného kanálu K0 

n0 n

Koeficient využití (zatížení) obslužného kanálu K z  1  K0 

nz n

14