6. Základní pojmy teorie hromadné obsluhy (THO) 6.1. Motivace THO je matematická disciplína, která se zabývá matematickým modelováním činnosti systému hromadné obsluhy (SHO), tj. systému zákazník – obslužná linka – obsluha. THO se používá pro modelování komunikačních, dopravních, obchodních a zdravotnických systémů a výrobních procesů. Počátky THO spadají do 30. let 20. století a jsou spjaty především s modelováním provozu telefonních ústředen. 6.2. Základní pojmy Základní jednotkou SHO je trojice zákazník – obslužná linka – obsluha. Zákazník je subjekt, který vyžaduje vyřízení svého požadavku. Např. zákazník je telefonní účastník, který vyžaduje uskutečnění telefonního spojení. Obslužná linka je osoba nebo zařízení, které zpracovává požadavky zákazníků, např. to může být telefonní ústředna. Obsluha je činnost, která vede k uspokojení požadavku zákazníka, např. spojení s volaným účastníkem. Do SHO přicházejí zákazníci ve vstupním proudu, což je posloupnost okamžiků příchodů zákazníků do SHO. Okamžiky příchodů mohou být deterministické nebo náhodné a počet zákazníků může být omezený nebo neomezený. Zdroj zákazníků může být prakticky neomezený (řádově tisíce – klienti banky, auta, která jezdí k benzínové čerpací stanici, registrovaní pacienti lékaře, klienti mobilního operátora) nebo omezený (stroje ve výrobní hale, které je nutné udržovat a opravovat). Pokud zákazníci nemohou být po svém příchodu do SHO okamžitě obslouženi, řadí se do fronty. Způsob řazení zákazníků do fronty a výběr zákazníků k obsluze se nazývá frontový režim. Nejznámější frontové režimy jsou: FIFO (první vstupuje, první je obsloužen) LIFO (poslední vstupuje, první je obsloužen) SIRO (obsluhy v náhodném pořadí) PRI (obsluha podle priorit). Doba obsluhy může být: pevná (tj. stejná pro všechny zákazníky) závislá na typu zákazníka náhodná Výstupní proud je posloupnost okamžiků výstupů zákazníků ze SHO. Vlastnosti výstupního proudu jsou závislé na vlastnostech vstupního proudu a na době obsluhy. Základní struktura SHO Úloha THO: najít funkční závislost veličin, které charakterizují kvalitu činnosti SHO na charakteristikách vstupního proudu, linek obsluhy a na způsobu organizace SHO jako celku. Příklady SHO systém obslužné linky zákazníci banka úředníci klienti banky samoobsluha pokladny nakupující poliklinika lékaři pacienti benzínová čerpací stanice čerpadla vozidla dopravní systém křižovatky se semafory vozidla 6.3. Dělení SHO podle různých kritérií a) Podle typu matematického modelu - markovské modely (doby mezi příchody zákazníků se řídí exponenciálním rozložením) - semimarkovské modely (doby mezi příchody zákazníků se řídí Erlangovým rozložením) - nemarkovské modely b) Podle počtu zákazníků - systém s ohraničeným počtem zákazníků - systém s neohraničeným počtem zákazníků c) Podle čekání zákazníků na obsluhu - systém bez čekání (zákazník, který se nedostane k obsluze hned po příchodu, nečeká a odchází) - systém s čekáním (zákazník nemůže odejít bez obsloužení. Jsou-li všechny linky obsazené, čeká ve frontě, která je buď ohraničená nebo neohraničená) - systém smíšený (zákazník čeká ve frontě jen tehdy, je-li splněna nějaká dodatečná podmínka) 6.4. Kendallova klasifikace SHO David Georg Kendall (1918 – 2007): britský statistik, působil na univerzitách v Oxfordu a Cambridge. Patřil ke světové špičce v oblasti teorie pravděpodobnosti a analýzy dat a byl jedním ze zakladatelů stochastické geometrie. Při Kendallově klasifikaci se SHO dělí podle: - rozložení doby mezi příchody zákazníků - rozložení doby obsluhy - počtu linek obsluhy - kapacity systému - frontového režimu. Používá se označení X/Y/n nebo X/Y/n/m/z X … označuje rozložení doby mezi příchody zákazníků Y … označuje rozložení doby obsluhy n … počet linek obsluhy m … kapacita systému z … frontový režim Na místě X a Y mohou být tyto symboly: M pro exponenciální rozložení Ek pro Erlangovo rozložení s parametrem k D pro degenerované rozložení G pro obecné rozložení Na místě n a m: čísla 1, 2, … Na místě z: FIFO, LIFO, SIRO, PRI Např. M/D/2/∞/FIFO je systém, kde vstupní proud tvoří Poissonův proces, doba obsluhy je konstantní, v systému jsou dvě linky, systém má neomezenou kapacitu a frontový režim je „první vstoupí, první je obsloužen“. 6.5. Používaná označení v SHO λ … intenzita vstupního proudu (průměrný počet zákazníků, kteří vstoupí do SHO za jednotku času) µ … intenzita obsluhy (průměrný počet zákazníků, které linka obslouží za jednotku času) µ λ =β ρ … intenzita provozu (základní charakteristika systému, často se udává v %) Časové charakteristiky W … doba pobytu zákazníka v systému WS … doba obsluhy WQ … doba čekání zákazníka v systému Je zřejmé, že W = WS + WQ. Charakteristiky týkající se počtu zákazníků N … počet zákazníků ve stabilizovaném systému – nezávisí již na čase t NS … počet obsluhovaných zákazníků NQ … počet zákazníků ve frontě Je zřejmé, že N = NS + NQ. Pravděpodobnostní charakteristiky a0 … pravděpodobnost, že systém je prázdný aj … pravděpodobnost, že v systému je právě j zákazníků PQ … pravděpodobnost, že přicházející zákazník bude čekat ve frontě PZ … pravděpodobnost, že přicházející zákazník bude odmítnut Nákladové charakteristiky Pokud je uživatel schopen ohodnotit náklady na čekání zákazníka, náklady na prostoj či provoz linek obsluhy, je možno systém optimalizovat vzhledem na jeho nákladovou efektivnost. Je možno určit např. optimální intenzitu obsluhy nebo optimální počet obslužných linek. 6.6. Littleův vzorec V systémech s neomezeným zdrojem zákazníků platí, že střední hodnota počtu zákazníku v systému (resp. ve frontě resp. u obsluhy) je rovna součinu intenzity vstupního proudu a střední hodnoty doby pobytu zákazníka v systému (resp. ve frontě resp. u obsluhy): ( ) ( )WENE λ= ( ) ( )QQ WENE λ= ( ) ( )SS WENE λ= Za předpokladu, že známe intenzity µλ, , lze ze znalosti aspoň jedné charakteristiky E(N), E(NQ), E(NS), E(W), E(WQ), E(WS) ostatní charakteristiky dopočítat. 6.7. Metody zkoumání SHO Existují dvě různé metody zkoumání SHO. Analytická metoda: Analytik zná nebo je schopen odvodit vzorce pro výpočet jednotlivých charakteristik systému. Pak stačí jenom dosadit do těchto vzorců konkrétní parametry systému. Nevýhoda: analytické řešení je známé jenom u několika nejjednodušších modelů. Simulační metoda: Systém nahradíme simulačním modelem a jeho činnost mnohonásobně nezávisle simulujeme na počítači. Jednotlivé výstupní charakteristiky systému pak nahradíme jejich odhady, např. střední hodnotu průměrem, pravděpodobnost relativní četností apod. Takto lze analyzovat i velmi složité systémy. 6.8. Intenzita provozu v SHO s jednou linkou obsluhy V tomto případě je intenzita provozu µ λ =ρ . Mohou nastat tři různé situace: a) Intenzita vstupu = intenzita obsluhy: ρ = 1 Ideální situace, netvoří se fronta a linka obsluhy je využita na 100 %. b) Intenzita vstupu < intenzita obsluhy: ρ < 1 Nově příchozí zákazník je obsloužen bez čekání, ale linka obsluhy je po určitou dobu nevyužita. Využití linky je 100* ρ %. c) Intenzita vstupu > intenzita obsluhy: ρ > 1 Nestabilní systém, začínají se postupně hromadit zákazníci, i když linka obsluhy pracuje nepřetržitě. Pokud zákazníci nečekají na obsluhu a odcházejí, jde o systém se ztrátami.