Teorie front. Systém hromadné obsluhy

Teorie front Pokouší se analyzovat a řešit procesy, ve kterých se vyskytují proudy objektů procházejících určitými zařízeními, od nichž vyžadují obsluhu. Vlivem omezené kapacity obsluhy může docházet k hromadění (čekání) jednotek s následným uspokojením požadavku nebo odmítnutím obsluhy. Pro teorii front se používá také název Teorie hromadné obsluhy.

Systém hromadné obsluhy stanice obsluhy

příchod

...

do systému

výstup ze ...

Zdroj jednotek vstupujících do systému

systému

fronta

čekací systém

1

Otázky vznikající při řešení problémů čekacích jevů  Jaký je střední počet jednotek čekajících ve frontě?

 Jaký je střední počet jednotek nacházejících se v čekacím systému?  Jaká je střední doba, kterou jednotka stráví v systému?  Jaká je střední doba, kterou jednotka ztrácí čekáním ve frontě?  Jaký je střední počet nevyužitých kanálů obsluhy?

Vstupní proud Proces, při němž vznikají požadavky na obsluhující jednotku. Vstupy mohou být:  determinované – prvky přicházejí k místu obsluhy v přesně stanovených a předem známých intervalech,  náhodné – okamžiky příchodu jsou náhodné veličiny,  smíšené.

2

Typy vstupů

 jednoduchý – všechny prvky vstupního proudu

zachovávají stejnou disciplínu.  složený – některé vstupující prvky jsou obsluhovány podle jiného čekacího režimu.

Řád fronty Určuje způsob přechodu prvků z fronty do obsluhy.  FIFO – kdo přijde první, je nejdříve obsloužen (samoobsluha, banka, benzínová stanice),  LIFO – nejdříve je obsloužen ten, kdo přijde poslední (ukládání polotovarů na sebe),  PRI – podle priorit (po uvolnění kanálu obsluhy je vybírán požadavek s nejvyšší prioritou, např. oprava důležitého zařízení),  SIRO – v náhodném pořadí.

3

Doba obsluhy

 konstantní,  náhodná.

Disciplina fronty  absolutně netrpělivá – prvek do systému, jehož

všechna zařízení obsluhy jsou obsazena nevstoupí a rezignuje na obsluhu,  bez netrpělivosti – prvky čekají bez ohledu na čas tak dlouho, dokud není obsluha realizována,  částečně netrpělivá – prvek čeká ve frontě po určitou dobu a pak opouští systém, nezačala-li ještě jeho obsluha.

4

Zdroj jednotek Pramen potenciálního souboru jednotek, které mohou vstoupit do systému.  uzavřený systém – prvky po obsloužení se vracejí zpět na vstup do zdroje,  otevřený systém – prvky se po obsloužení nevracejí zpět do zdroje.

Čekací prostor Místo mezi zdrojem jednotek a obsluhující stanicí. Může být:  nulový – prvek, který nemůže být ihned obsloužen, je odmítnut,  nenulový – lze ještě upřesnit:  neomezený – provozní situace dovoluje čekací systém jakékoliv délky,  omezený – vstoupí-li prvek v době, kdy má systém maximální přípustnou délku, je odmítnut.

5

Uspořádání kanálů Podle počtu kanálů ve stanici obsluhy rozlišujeme:  jednokanálové systémy,  vícekanálové systémy. Kanály mohou být uspořádány:  paralelně – stačí, aby prvek byl obsloužen jedním, libovolným kanálem obsluhy,  sériově – prvek musí projít postupně všemi kanály.

Paralelně uspořádaný tříkanálový systém hromadné obsluhy s jednou frontou stanice obsluhy

příchod

...

výstup ze systému

do systému fronta

6

Paralelně uspořádaný dvoukanálový systém hromadné obsluhy se dvěma frontami

stanice obsluhy ... výstup ze

příchod

systému

do systému ... fronty

Sériově uspořádaný systém hromadné obsluhy

stanice obsluhy příchod

výstup ze ...

do systému

systému fronta

7

Klasifikace systémů hromadné obsluhy dle D. G. Kendalla A/B/X/Y/Z A

typ pravděpodobnostního rozdělení popisující intervaly mezi příchody požadavků do systému. Používané symboly: M exponenciální rozdělení, D konstantní intervaly mezi příchody, Ek Erlangovo rozdělení, N normální rozdělení, G nespecifikované rozdělení.

B

typ pravděpodobnostního rozdělení popisující dobu trvání obsluhy. Používají se stejné symboly jako u A.

X

počet paralelně uspořádaných kanálů

Y

číslo udávající kapacitu systému hromadné obsluhy

Z

řád fronty (FIFO, LIFO, SIRO, PRI).

Jednoduchý systém hromadné obsluhy bez priorit

Nejjednodušší model hromadné obsluhy. Vstupy i výstupy mají pravděpodobnostní charakter s Poissonovým rozdělením.

8

Předpoklady použití Poissonova rozdělení  střední intenzita vstupů (výstupů) je konstantní

během určitého, dostatečně dlouhého časového období,

 počet vstupů (výstupů) v následujícím časovém intervalu nezávisí na počtu vstupů (výstupů) realizovaných v předchozím intervalu,  pravděpodobnost dvou a více vstupů (výstupů) v témže časovém intervalu délky t je prakticky nulová, je-li tento interval t dostatečně malý,  pravděpodobnost, že jednotka vstoupí do systému (vystoupí ze systému) během malého časového intervalu délky t je přímo úměrná délce tohoto intervalu.

Označení použitých veličin 

střední intenzita vstupu (střední počet jednotek, které vstoupí do systému během dané časové jednotky),



střední intenzita výstupu (střední počet obsloužených jednotek během dané časové jednotky).

Nemá-li fronta narůstat nade všechny meze, musí platit > , resp.:



 1 

střední intenzita provozu (koeficient čekacího systému).

9

Další charakteristiky  t

pravděpodobnost, že během intervalu t vstoupí do systému jedna jednotka,

 t

pravděpodobnost, že během intervalu t vystoupí ze systému jedna jednotka,

  t

pravděpodobnost, že do systému během intervalu t nevstoupí žádná jednotka,

  t

pravděpodobnost, že ze systému během intervalu t nevystoupí žádná jednotka.

Další veličiny n

počet jednotek v systému,

ns

střední počet jednotek v systému,

nf

střední počet jednotek ve frontě,

ts

střední doba, kterou jednotka stráví v systému,

tf

střední doba, kterou jednotka čeká ve frontě.

10

Konstrukce modelu Nalezení vztahů mezi veličinami:

ns

nf

ts

tf

charakterizujícími čekací systém a parametry systému , . Jde o nalezení pravděpodobností p0, p1, p2, …, že v systému je v daném okamžiku právě 0, 1, 2, … jednotek.

Varianty změny stavu systému během intervalu t, t + t za předpokladu n > 0

Stav systému v okamžiku t En-1 En+1 En En

Stav systému Změna během intervalu t Počet vstupů Počet výstupů v okamžiku t + t 1 0 En 0 1 En 0 0 En 1 1 En

pn = P{En} pravděpodobnost, že systém je v daném okamžiku ve stavu E n

11

Pravděpodobnosti změny stavu systému za t

En-1  En:

pn-1 . t . (1 - t)

En+1  En:

pn+1 . t . (1 - t)

En  En:

pn . (1 - t) . (1 - t)

En  En:

pn . t . t

Pravděpodobnost, že se systém nachází v některém okamžiku ve stavu En

pn = pn-1 . t . (1 - t) + pn+1 . t . (1 - t) + + pn . (1 - t) . (1 - t) + pn . t . t = = pn-1 . t – pn-1 . t)2 + pn+1 . t - pn+1 . t)2 + + pn – pn . t – pn . t + pn . t)2 + pn . t)2 = = pn + t . [pn-1 .  pn+1 .  pn .  pn . ] + t)2. [2pn - pn-1 - pn+1]

12

Pravděpodobnostní rozdělení počtu jednotek v čekacím systému

pn = n (1 - )

n = 0, 1, 2, …

Střední počet jednotek v systému Určíme ze vztahu: 

ns   n . pn n 0

Po úpravách:

 ns  

13

Střední počet jednotek ve frontě Určíme ze vztahu: 

n f   (n  1) . p n n 1

Po úpravách:

2 nf   . ( - )

Střední doba, kterou jednotka stráví v systému Určíme ze vztahu:

 . ts  ns Po úpravách:

1 ts  

14

Střední doba, kterou jednotka čeká ve frontě Určíme ze vztahu:

 . tf  nf Po úpravách:

 tf  (   )

15