2.2 Vícekanálové QS s čekáním
Systém s omezenou délkou fronty. Uvažujme kanál QS s čekáním, který přijímá tok požadavků s intenzitou ; intenzita služby (pro jeden kanál); počet míst ve frontě.
Stavy systému jsou číslovány podle počtu požadavků spojených se systémem:
žádná fronta:
Všechny kanály jsou zdarma;
Jeden kanál je obsazený, zbytek je volný;
-kanály jsou obsazené, zbytek ne;
Všechny kanály jsou obsazené, nejsou žádné volné kanály;
je tam fronta:
Všechny n-kanály jsou obsazeny; jedna aplikace je ve frontě;
Všechny n-kanály, r-požadavky ve frontě jsou obsazeny;
Všechny n-kanály, r-požadavky ve frontě jsou obsazeny.
GSP je znázorněno na obr. 17. Každá šipka je označena odpovídajícími intenzitami toků událostí. Podél šipek zleva doprava je systém přenášen vždy stejným tokem požadavků o intenzitě
Rýže. 17. Vícekanálové QS s čekáním
Graf je typický pro procesy reprodukce a smrti, pro které bylo dříve získáno řešení. Zapišme výrazy pro mezní pravděpodobnosti stavů pomocí zápisu: (zde použijeme výraz pro součet geometrická progrese se jmenovatelem).
Tak byly nalezeny všechny pravděpodobnosti stavu.
Pojďme určit výkonnostní charakteristiky systému.
Pravděpodobnost selhání. Příchozí požadavek je odmítnut, pokud jsou obsazeny všechny n-kanály a všechna m-místa ve frontě:
(18)
Relativní propustnost doplňuje pravděpodobnost selhání na jednu:
Absolutní propustnost QS:
(19)
Průměrný počet obsazených kanálů. U QS s odmítnutím se shodoval s průměrným počtem žádostí v systému. U QS s frontou se průměrný počet obsazených kanálů neshoduje s průměrným počtem aplikací v systému: druhá hodnota se liší od první o průměrný počet aplikací ve frontě.
Označme průměrný počet obsazených kanálů . Každý obsazený kanál obsluhuje průměrně A-nároky za jednotku času a QS jako celek obsluhuje průměrně A-nároky za jednotku času. Když jeden vydělíme, dostaneme:
Průměrný počet aplikací ve frontě lze vypočítat přímo jako matematické očekávání diskrétního náhodná proměnná:
(20)
Zde opět (výraz v závorce) dochází k derivaci součtu geometrické posloupnosti (viz výše (11), (12) - (14)), pomocí vztahu pro ni získáme:
Průměrný počet aplikací v systému:
Průměrná doba čekání na aplikaci ve frontě. Podívejme se na řadu situací, které se liší stavem, ve kterém nově příchozí požadavek systém najde a jak dlouho bude muset čekat na obsluhu.
Pokud požadavek nenajde všechny kanály obsazené, nebude muset vůbec čekat (odpovídající členové v matematické očekávání se rovnají nule). Pokud požadavek dorazí v době, kdy je všech n-kanálů zaneprázdněno a není zde žádná fronta, bude muset čekat v průměru po dobu rovnající se (protože „tok uvolnění“ -kanálů má intenzitu ). Pokud požadavek najde ve frontě všechny kanály obsazené a jeden požadavek před ním, bude muset čekat v průměru určitou dobu (na každý požadavek vpředu) atd. Pokud se požadavek ocitne ve frontě - žádostí, bude muset v průměru nějakou dobu čekat Pokud nově příchozí požadavek najde m-požadavky již ve frontě, pak vůbec nepočká (nebude však obsluhován). Průměrnou dobu čekání zjistíme vynásobením každé z těchto hodnot odpovídajícími pravděpodobnostmi:
(21)
Stejně jako v případě jednokanálového QS s čekáním podotýkáme, že tento výraz se od výrazu pro průměrnou délku fronty (20) liší pouze faktorem , tzn.
.
Průměrná doba zdržení požadavku v systému, stejně jako u jednokanálového QS, se liší od průměrné doby čekání průměrnou dobou služby vynásobenou relativní propustností:
.
Systémy s neomezenou délkou fronty. Uvažovali jsme o kanálovém QS s čekáním, kdy ve frontě nemůže být současně více než m-požadavků.
Stejně jako dříve je při analýze systémů bez omezení nutné uvažovat získané vztahy pro .
Pravděpodobnosti stavů získáme ze vzorců přechodem k limitě (v ). Všimněte si, že součet odpovídající geometrické progrese konverguje a diverguje při >1. Za předpokladu, že<1 и устремив в формулах величину m к бесконечности, получим выражения для предельных вероятностей состояний:
(22)
Pravděpodobnost poruchy, relativní a absolutní propustnost. Vzhledem k tomu, že každý požadavek bude dříve nebo později obsluhován, vlastnosti propustnosti QS budou:
Průměrný počet aplikací ve frontě se získá z (20):
,
a průměrná čekací doba je od (21):
.
Průměrný počet obsazených kanálů, jako dříve, je určen absolutní propustností:
.
Průměrný počet aplikací spojených s QS je definován jako průměrný počet aplikací ve frontě plus průměrný počet aplikací v provozu (průměrný počet obsazených kanálů):
Příklad 2. Čerpací stanice se dvěma čerpadly (n = 2) obsluhuje proud automobilů o intenzitě =0,8 (vozů za minutu). Průměrná doba servisu na stroj:
Žádná jiná čerpací stanice v okolí není, takže se fronta aut před čerpací stanicí může rozrůstat téměř neomezeně. Najděte vlastnosti QS.
Protože<1, очередь не растет безгранично и имеет смысл говорить о предельном стационарном режиме работы СМО. По формулам (22) находим вероятности состояний:
atd.
Průměrný počet obsazených kanálů zjistíme vydělením absolutní kapacity QS A = = 0,8 intenzitou služby = 0,5:
Pravděpodobnost, že na čerpací stanici nebude fronta, bude:
Průměrný počet aut ve frontě:
Průměrný počet aut na čerpacích stanicích:
Průměrná doba čekání ve frontě:
Průměrná doba, kterou auto stráví na čerpací stanici:
QS s omezenou čekací dobou. Dříve jsme uvažovali o systémech s čekáním omezeným pouze délkou fronty (počet m-požadavků současně ve frontě). V takovém QS aplikace, která vyrostla ve frontě, ji neopustí, dokud nečeká na službu. V praxi existují i jiné typy QS, ve kterých může aplikace po určité době opustit frontu (tzv. „netrpělivé“ aplikace).
Uvažujme QS tohoto typu za předpokladu, že omezení doby čekání je náhodná veličina.
Předpokládejme, že existuje n-kanálový QS s čekáním, ve kterém je počet míst ve frontě neomezený, ale doba, po kterou požadavek zůstane ve frontě, je nějaká náhodná veličina se střední hodnotou, tedy každý požadavek ve frontě fronta podléhá jakémusi Poissonovu „toku péče“ s intenzitou:
Pokud je tento tok Poissonův, pak proces vyskytující se v QS bude Markovovský. Najděte pro to pravděpodobnosti stavu. Číslování stavů systému je spojeno s počtem aplikací v systému – obsluhovaných i stojících ve frontě:
žádná fronta:
Všechny kanály jsou zdarma;
Jeden kanál je obsazený;
Dva kanály jsou obsazené;
Všechny n-kanály jsou obsazeny;
je tam fronta:
Všech n kanálů je obsazeno, jeden požadavek je ve frontě;
Všech n-kanálů je obsazeno, r-požadavky jsou ve frontě atd.
Graf stavů a přechodů soustavy je na Obr. 23.
Rýže. 23. QS s omezenou čekací dobou
Označme tento graf jako dříve; všechny šipky vedoucí zleva doprava označují intenzitu toku aplikací. U stavů bez fronty budou šipky vedoucí z nich zprava doleva, stejně jako dříve, označovat celkovou intenzitu toku obsluhujícího všechny obsazené kanály. Pokud jde o stavy s frontou, šipky vedoucí z nich zprava doleva budou mít celkovou intenzitu toku služeb všech n-kanálů plus odpovídající intenzitu toku odchodů z fronty. Pokud jsou ve frontě r-aplikace, pak bude celková intenzita toku odchodů rovna .
Jak je vidět z grafu, existuje vzorec reprodukce a smrti; pomocí obecných výrazů pro omezující pravděpodobnosti stavů v tomto schématu (pomocí zkrácených zápisů píšeme:
(24)
Všimněme si některých vlastností QS s omezeným čekáním ve srovnání s dříve zvažovanými QS s požadavky „pacientů“.
Není-li délka fronty omezena a požadavky jsou „trpělivé“ (neopouštět frontu), pak režim stacionárního limitu existuje pouze v případě (při , se příslušná nekonečná geometrická progrese rozchází, což fyzicky odpovídá neomezenému růstu z fronty na ).
Naopak u QS s „netrpělivými“ požadavky opouštějícími frontu dříve či později je vždy dosaženo nastaveného servisního režimu at, bez ohledu na sníženou intenzitu toku požadavků. Vyplývá to ze skutečnosti, že řada for ve jmenovateli vzorce (24) konverguje pro jakékoli kladné hodnoty a .
Pro QS s „netrpělivými“ požadavky nedává pojem „pravděpodobnost selhání“ smysl – každý požadavek se dostane do fronty, ale nemusí čekat na službu a odchází s předstihem.
Relativní propustnost, průměrný počet požadavků ve frontě. Relativní kapacitu q takového QS lze vypočítat následovně. Je zřejmé, že všechny aplikace budou obsluhovány, kromě těch, které opustí frontu s předstihem. Spočítejme si průměrný počet aplikací, které brzy opustí frontu. Za tímto účelem vypočítáme průměrný počet aplikací ve frontě:
Každá z těchto aplikací podléhá „toku odchodů“ s intenzitou . To znamená, že z průměrného počtu -aplikací ve frontě v průměru odejdou -aplikace bez čekání na obsluhu, -aplikace za jednotku času a celkem za jednotku času budou v průměru obslouženy -aplikace. Relativní kapacita QS bude:
Stále získáme průměrný počet obsazených kanálů vydělením absolutní šířky pásma A:
(26)
Průměrný počet aplikací ve frontě. Vztah (26) umožňuje vypočítat průměrný počet aplikací ve frontě bez sčítání nekonečné řady (25). Z (26) získáme:
a průměrný počet obsazených kanálů zahrnutý v tomto vzorci lze nalézt jako matematické očekávání náhodné veličiny Z, nabývající hodnot 0, 1, 2,..., n s pravděpodobnostmi ,:
Na závěr si všimneme, že pokud ve vzorcích (24) jdeme na limitu v (nebo, co je stejné, v ), pak v 
Fronta délky k v ní zůstává s pravděpodobností Pk a nezařazuje se do fronty s pravděpodobností gk=1 - Pk." Přesně tak se lidé ve frontách obvykle chovají. Ve frontových systémech, což jsou matematické modely výrobních procesů, je možné délka fronty je omezena konstantní velikostí (např. kapacita bunkru). Toto je samozřejmě speciální případ obecného nastavení.
V této části se podíváme na některé z nejjednodušších QS a odvodíme výrazy pro jejich charakteristiky (ukazatele výkonnosti). Zároveň předvedeme hlavní metodologické postupy charakteristické pro elementární, „Markovovu“ teorii front. Nebudeme se honit množstvím vzorků QS, pro které budou odvozeny konečné vyjádření charakteristik; Tato kniha není referenční knihou o teorii fronty (tuto roli mnohem lépe plní speciální příručky). Naším cílem je seznámit čtenáře s některými „malými triky“, které usnadňují cestu teorií fronty, která se v řadě existujících (i vydávajících se za populární) knih může jevit jako nesouvislý soubor příkladů.
V této části budeme považovat všechny toky událostí, které přenášejí QS ze stavu do stavu, za nejjednodušší (aniž bychom to pokaždé konkrétně stanovili). Mezi nimi bude takzvaný „tok služeb“. Týká se toku požadavků obsluhovaných jedním nepřetržitě obsazeným kanálem.
V tomto toku má interval mezi událostmi, jako vždy v nejjednodušším toku, exponenciální rozdělení (v mnoha příručkách místo toho říkají: „doba služby je exponenciální“; my sami budeme tento termín používat v budoucnu). V této části bude exponenciální rozdělení doby provozu samozřejmostí, jako vždy pro „nejjednodušší“ systém.
V průběhu uvedeme výkonnostní charakteristiky uvažovaného QS.
1. n-kanálový QS s poruchami (Erlang problém).
Zde se budeme zabývat jedním z prvních, „klasických“ problémů teorie front; tento problém vyvstal z praktických potřeb telefonie a na počátku tohoto století jej vyřešil dánský matematik Erlang. Problém je formulován následovně: existují kanály (komunikační linky), které přijímají tok požadavků s intenzitou K. Tok služeb má intenzitu (převrácená hodnota průměrné doby služby). Najděte konečné pravděpodobnosti stavů QS a také charakteristiky jeho účinnosti:
A - absolutní propustnost, tj. průměrný počet aplikací obsluhovaných za jednotku času;
Relativní propustnost, tj. průměrný podíl příchozích aplikací obsluhovaných systémem;
Rotk je pravděpodobnost odmítnutí, tj. že aplikace ponechá QS neobslouženou;
k je průměrný počet obsazených kanálů.
Řešení. Stavy systému S (SMO) očíslujeme podle počtu požadavků umístěných v systému (v tomto případě se shoduje s počtem obsazených kanálů):
V SOT není jediná aplikace,
V QS je jeden požadavek (jeden kanál je obsazený, zbytek je volný),
V systému QS jsou požadavky na kanály obsazeny, zbytek je volný),
V QS jsou požadavky (všechny kanály jsou obsazené).
Stavový graf QS odpovídá vzorci smrti a reprodukce (obr. 20.1). Označme tento graf - k šipkám dejte intenzitu toků událostí Tok aplikací s intenzitou X je přenesen ze systému (jakmile dorazí aplikace, systém skočí z ).
Stejný tok požadavků přenese systém z libovolného levého stavu do sousedního pravého (viz horní šipky na obr. 20.1).
Intenzity dáme na spodní šipky. Nechte systém být ve stavu (jeden kanál funguje). Provádí údržbu za jednotku času. Označíme intenzitu šipky. Nyní si představme, že systém je ve stavu (fungují dva kanály). Aby to šlo, musí první nebo druhý kanál dokončit servis; celková intenzita jejich servisních toků je rovna odpovídající šipce. Celkový tok služeb poskytovaných třemi kanály má intenzitu rovnou kanálům - tyto intenzity uvádíme na spodní šipky na obr. 20.1.
A nyní, když známe všechny intenzity, použijeme hotové vzorce (19.7), (19.8) pro konečné pravděpodobnosti ve schématu smrti a rozmnožování. Pomocí vzorce (19.8) dostaneme:
Členy expanze budou koeficienty ve výrazech pro
Všimněte si, že ve vzorcích (20.1), (20.2) jsou intenzity Vejce zahrnuty nikoli jednotlivě, ale pouze ve formě poměru.
a hodnotu budeme nazývat „snížená intenzita toku aplikací“. Jeho význam je průměrný počet přijatých požadavků za průměrnou dobu obsluhy jednoho požadavku. Pomocí tohoto zápisu přepíšeme vzorce (20.1), (20.2) do tvaru:
Vzorce (20.4), (20.5) pro konečné pravděpodobnosti stavů se nazývají Erlangovy vzorce - na počest zakladatele teorie front. Většina ostatních vzorců této teorie (dnes je jich víc než hub v lese) nenese žádná zvláštní jména.
Tím byly nalezeny konečné pravděpodobnosti. Pomocí nich vypočítáme výkonnostní charakteristiky QS. Nejprve najdeme pravděpodobnost, že příchozí aplikace bude zamítnuta (nebude obsluhována). K tomu musí být všechny kanály obsazené, což znamená
Odtud zjistíme relativní propustnost - pravděpodobnost, že bude požadavek obsloužen:
Absolutní propustnost získáme tak, že intenzitu toku aplikací X vynásobíme
Zbývá pouze najít průměrný počet obsazených kanálů k. Tuto hodnotu lze zjistit „přímo“, jako matematické očekávání diskrétní náhodné veličiny s možnými hodnotami a pravděpodobnostmi těchto hodnot
Dosazením výrazů (20.5) za zde a provedením odpovídajících transformací bychom nakonec získali správný vzorec pro k. Ale odvodíme ho mnohem jednodušeji (tady je to jeden z „malých triků“!) Ve skutečnosti víme, absolutní propustnost A. Nejde o nic jiného než o intenzitu toku aplikací obsluhovaných systémem. Každý obsazený kanál obsluhuje průměr požadavků za jednotku času. To znamená, že průměrný počet obsazených kanálů je
A jaký podíl kanálů bude nečinný?
Již zde je vidět nějaký náznak optimalizace. Ve skutečnosti údržba každého kanálu za jednotku času stojí určitou částku. Každá obsluhovaná aplikace přitom generuje nějaký příjem. Vynásobením tohoto příjmu průměrným počtem aplikací A obsluhovaných za jednotku času získáme průměrný příjem z QS za jednotku času. S rostoucím počtem kanálů se tento příjem přirozeně zvyšuje, ale zvyšují se i náklady spojené s údržbou kanálů. Co převáží - zvýšení příjmů nebo výdajů? Záleží na podmínkách provozu, „poplatku za obsluhu aplikace“ a nákladech na údržbu kanálu. Znáte-li tyto hodnoty, můžete najít optimální počet kanálů, které jsou cenově nejefektivnější. Takový problém nevyřešíme a necháme na stejném „nelíném, zvědavém čtenáři“, aby přišel s příkladem a vyřešil jej. Obecně platí, že vymýšlení problémů se rozvíjí více než řešení těch, které již někdo položil.
Systémy ML jsou součástí širší třídy dynamických systémů, které se někdy nazývají průtokové systémy. Závitový systém je systém, ve kterém se určité objekty pohybují jedním nebo více kanály s omezenou kapacitou za účelem přesunu z jednoho bodu do druhého. Při analýze průtokových systémů jsou rozděleny do dvou hlavních tříd:
pravidelné systémy, tj. systémy, ve kterých se toky chovají předvídatelným způsobem (velikost toku a doba jeho výskytu v korytě jsou známé). V případě, že existuje pouze jeden kanál, je výpočet systému triviální. Je zřejmé, že mezi intenzitou proudění λ a rychlost obsluhy S existuje poměr λ < C;
nepravidelné systémy, tj. systémy, ve kterých se vlákna chovají nepředvídatelným způsobem.
Zajímavější je případ pravidelného toku, který je distribuován přes síť kanálů. Je zřejmé, že stav λ < C uloženy pro každý kanál. Vzniká tak složitý kombinatorický problém.
Existuje sedm cest:
A→B→D→E→F
A→C→B→E→F
A→C→B→D→E→F
A→C→B→D→F
Je nutné přepravit náklad z A PROTI F. Kapacita každého kanálu je známá. Jaká je kapacita sítě a jakou cestou by se měl tok ubírat? Tento problém lze vyřešit pomocí věty o maximálním toku, kterou jsme uvažovali dříve (obr. 6).
Druhá třída zahrnuje náhodné pravděpodobné toky, ve kterých není určena doba přijetí požadavku a počet požadavků je nepředvídatelný. Řešením takových problémů se zabývá teorie front.
Obecně lze systém řazení znázornit na obrázku 7.
Rýže. 7.
Předmět teorie front je stanovit vztah mezi povahou toku požadavků, počtem kanálů, produktivitou, správným provozem a účinností.
Tak jako výkonnostní charakteristiky Lze použít následující veličiny a funkce:
průměrný počet aplikací, které může QS obsloužit za jednotku času;
průměrný počet žádostí, které byly zamítnuty a opustily SOT;
pravděpodobnost, že přijatá žádost bude okamžitě vyřízena;
průměrná doba čekání ve frontě;
průměrný počet aplikací ve frontě;
průměrný příjem SMO za jednotku času a další ekonomické ukazatele SMO.
Analýza QS se zjednoduší, pokud v systému nastane Markovův proces, pak lze systém popsat obyčejnými diferenciálními rovnicemi a limitními pravděpodobnostmi - lineárními algebraickými rovnicemi.
Markovův proces vyžaduje, aby všechny toky byly Poissonovy (bez následných efektů), ale aparát Markovových procesů se používá i tehdy, když je proces odlišný od Markova. V tomto případě lze charakteristiky QS odhadnout přibližně: čím složitější QS, tím přesnější aproximace.
Klasifikace systémů hromadné obsluhy
QS může být dvou typů:
QS s poruchami;
QS s čekáním (tedy s frontou).
Služba v systémech s frontou může mít různou povahu:
službu lze zefektivnit;
náhodná služba;
služba s prioritou, zatímco priorita může být s přerušením nebo bez přerušení.
Systémy front se dělí na:
systémy s neomezeným čekáním a úkol přijatý QS se zařadí do fronty a čeká na službu. Dříve nebo později bude obsloužena;
systémy s omezeným očekáváním, zatímco na aplikaci ve frontě jsou uvalena omezení, například omezená doba strávená ve frontě, délka fronty, celkový čas strávený v QS. V závislosti na typu QS lze k hodnocení účinnosti použít různé ukazatele.
Pro QS s poruchami se používají následující ukazatele výkonnosti:
absolutní propustnost A– průměrný počet aplikací, které lze obsluhovat za jednotku času;
relativní propustnost Q– relativní průměrný počet aplikací. V tomto případě lze relativní propustnost zjistit pomocí vzorce
Kde λ je intenzita požadavků přijatých QS.
Pro SMO s očekáváním absolutní propustnost A A relativní propustnost Q ztrácejí svůj význam, ale důležité se stávají jiné vlastnosti:
jednotka čekací doby ve frontě;
průměrný počet aplikací ve frontě;
průměrný čas strávený v systému.
Pro QS s omezenou frontou jsou zajímavé obě skupiny charakteristik.
Zvažte n - systém řazení kanálů s čekáním.
Intenzita servisního toku je μ. Doba trvání služby je náhodná veličina podléhající zákonu o exponenciálním rozdělení. Tok služeb je nejjednodušší Poissonův tok událostí.
Velikost fronty umožňuje lidem být v ní m aplikací.
K nalezení mezních pravděpodobností můžete použít následující výrazy.
(0‑1)
Kde.
Pravděpodobnost odmítnutí služby aplikace(k selhání dojde, pokud jsou všechny kanály obsazené a existují m požadavků):
(0‑2)
Relativní šířka pásma.
(0‑3)
Absolutní propustnost.
(0‑4)
Průměrný počet obsazených kanálů.
U QS s frontou se průměrný počet obsazených kanálů neshoduje (na rozdíl od QS s poruchami) s průměrným počtem požadavků v systému. Rozdíl je roven počtu aplikací čekajících ve frontě.
Označme průměrný počet obsazených kanálů. Každý obsazený kanál obsluhuje v průměru μ nároků za jednotku času a QS jako celek obsluhuje A nároků za jednotku času. Vydělením A μ dostaneme
(0‑5)
Průměrný počet aplikací ve frontě.
Chcete-li zjistit průměrný počet aplikací čekajících ve frontě, pokud χ≠1, můžete použít výraz:
(0‑6)
(0‑7)
kde = .
Průměrný počet aplikací v systému.
(0‑8)
Průměrná doba čekání na žádost ve frontě.
Průměrnou dobu čekání na aplikaci ve frontě lze zjistit z výrazu (χ≠1).
(0‑9)
Průměrná doba, po kterou aplikace zůstává v systému.
Stejně jako v případě jednokanálového QS máme:
(0‑10)
Obsah práce.
Příprava experimentálních přístrojů .
Provádí se v souladu s obecnými pravidly.
Výpočet pomocí analytického modelu .
1. Připravte si následující tabulku v aplikaci Microsoft Excel.
|
Možnosti |
Analytická |
Imitace |
|||||||||||||||
|
n |
m |
TA |
Ts |
ρ |
χ |
P0 |
P1 |
p2 |
Rotk |
W |
nozh |
q |
A |
Rotk |
W |
q |
A |
2. Do sloupců pro parametry QS tabulky zapište své počáteční údaje, které jsou určeny podle pravidla:
n = 1,2,3
m=1,3,5
Pro každou kombinaci ( n, m) je nutné najít teoretické a experimentální hodnoty indikátorů QS pro následující dvojice hodnot:
= <порядковый номер в списке группы>
3. Zadejte příslušné vzorce do sloupců s indikátory analytického modelu.
Experiment na simulačním modelu.
1. Nastavte režim spouštění s exponenciálně distribuovaným časem služby nastavením hodnoty odpovídajícího parametru na 1.
2. Pro každou kombinaci n, m a spusťte model.
Výsledky běhů zapište do tabulky.
3. Do odpovídajících sloupců tabulky zadejte vzorce pro výpočet průměrné hodnoty ukazatele Ptk, q a A.
Analýza výsledků .
1. Analyzujte výsledky získané teoretickými a experimentálními metodami a porovnejte výsledky mezi sebou.
2. Pro jednu z kombinací (n,m) vyneste do jednoho diagramu závislost Ptk na teoreticky a experimentálně získaných datech.
Optimalizace parametrů QS .
Vyřešte problém s optimalizací velikosti počtu míst ve frontě m pro dvě zařízení s průměrnou dobou obsluhy = z hlediska získání maximálního zisku. Jako podmínky problému vezměte:
- příjem z obsluhy jedné aplikace ve výši 80 USD/hod,
- náklady na údržbu jednoho zařízení jsou 1 $/hod,
- náklady na udržení jednoho místa ve frontě jsou 0,2 USD/hod.
1. Pro výpočty je vhodné vytvořit tabulku:
První sloupec je vyplněn počtem zařízení n = 1.
Druhý sloupec je vyplněn hodnotami čísel v přirozené řadě (1,2,3...).
Všechny buňky ve třetím a čtvrtém sloupci jsou vyplněny hodnotami.
Vzorce pro sloupce tabulky v sekci 0 se přenesou do buněk sloupců od pěti do čtrnácti.
Do sloupců s počátečními údaji sekcí Příjmy, Výdaje, Zisk zadejte hodnoty (viz výše).
Do sloupců s vypočtenými hodnotami částí Příjmy, Výdaje, Zisk zapište kalkulační vzorce:
- počet aplikací za jednotku času
Nr =A
- celkový příjem za jednotku času
I S = I r *N r
- celková spotřeba za jednotku času
ES =Es*n + Eq*m
- zisk za jednotku času
P = I S - E S
Kde
Ir - příjem z jedné žádosti,
E s - spotřeba na zařízení,
Eq - cena za místo v řadě
2. Vyplňte řádky tabulky pro n=2 an=3.
Najděte m opt pro n =1,2,3.
3. Nakreslete do jednoho diagramu grafy závislosti C(m) pro n=1,2,3.
pracovní zpráva:
Pracovní zpráva by měla obsahovat:
- počáteční údaje,
- výsledky výpočtů a experimentů se softwarovým modelem,
Grafy pro P otevřené,
- tabulka s údaji, abyste našli to nejlepší ma hodnotu m opt,
- grafy zisku za jednotku času v závislosti na m pro n=1,2,3.
Kontrolní otázky :
1) Uveďte stručný popis vícekanálového modelu QS s omezenou frontou.
2) Jaké indikátory charakterizují fungování vícekanálového QS s omezenou frontou?
3) Jak se počítají mezní pravděpodobnosti vícekanálového QS s omezenou frontou?
4) Jak zjistit pravděpodobnost selhání obsluhy aplikace?
5) Jak zjistit relativní šířku pásma?
6) Jaká je absolutní propustnost?
7) Jak se počítá průměrný počet aplikací v systému?
8) Uveďte příklady vícekanálového QS s omezenou frontou.
Úkoly.
1) Čerpací stanice má 3 pumpy a plošinu pro 3 auta na čekání na tankování. V průměru každé 4 minuty přijede na nádraží jedno auto. Průměrná doba údržby jednoho stroje je 2,8 minuty. Určete provozní vlastnosti čerpací stanice.
2) Stanice technické kontroly vozidel, která má 3 kontrolní stanoviště, přijme v průměru 1 vozidlo za 0,4 hodiny. Parkování ve dvoře pojme 3 auta. Průměrná doba provozu jednoho sloupku je 0,5 hodiny. Určete vlastnosti čerpací stanice.
3) Zboží je na prodejnu dopravováno vozidly. Během dne přijede v průměru 6 aut. Technické místnosti pro přípravu zboží k prodeji umožňují zpracovávat a skladovat zboží přivezené dvěma vozidly. Prodejna zaměstnává tři baliče produktů na směny, z nichž každý v průměru zpracuje zboží jednoho stroje do 5 hodin. Pracovní den baličů je 12 hodin. Určete provozní vlastnosti prodejny a také to, jaká by měla být kapacita technických místností, aby pravděpodobnost úplného zpracování zboží byla větší než 0,96.
4) Prodejna má tři pokladny. Průměrná doba obsluhy jednoho zákazníka je 3 minuty. Intenzita zákaznického toku je 7 osob za minutu. Počet zákazníků stojících ve frontě u pokladny nesmí přesáhnout 5 osob. Kupující, který přijde do prodejny, ve které je 5 lidí v každé řadě u pokladny, nečeká, ale prodejnu opouští. Určete vlastnosti obchodu.
5) Velkoobchodní sklad vydává zboží zákazníkům. Nakládání vozidla provádějí tři týmy nakladačů, z nichž každý tvoří 4 osoby. Sklad pojme současně 5 vozidel a pokud v tuto dobu přijede nové vozidlo, není obsluhováno. Intenzita příchozího proudu je 5 aut za hodinu. Rychlost nakládky je 2 vozidla za hodinu. Uveďte zhodnocení skladového provozu a možnost jeho reorganizace.
6) Celní úřad má tři terminály. Intenzita toku vozidel přepravujících zboží a podléhajících celní kontrole je 30 jednotek. denně. Průměrná doba celního odbavení na terminálu pro jedno vozidlo je 3 hodiny. Pokud je ve frontě na celní kontrolu 5 aut, pak přijíždějící auta jdou na jiný celní úřad. Najděte ukazatele celní výkonnosti.
7) Vozidla se stavebním materiálem dorazí na stavbu v průměru do 40 minut. Průměrná doba vykládky jednoho vozidla je 1,8 hodiny. Vykládky se účastní dva týmy nakladačů. Ve frontě na vykládku na staveništi nesmí být více než 5 vozidel. Stanovte ukazatele výkonnosti staveniště.
8) Do myčky se třemi pracovními stanicemi přijede v průměru 12 aut za hodinu. Pokud je ve frontě již 6 vozů, nově přijíždějící vozy se do fronty nezařazují, ale mytí opouštějí. Průměrná doba mytí auta je 20 minut, průměrné náklady na mytí aut jsou 150 rublů. Určete výkonnostní ukazatele myčky a průměrnou ztrátu tržeb během pracovního dne (od 9:00 do 19:00).
9) Intenzita toku vozidel přepravujících zboží a podléhajících celní kontrole je 50 jednotek. denně. Průměrná doba celního odbavení na terminálu pro jedno vozidlo je 2,8 hodiny. Maximální fronta na celní kontrolu by neměla být větší než 8 vozů. Určete, kolik terminálů je třeba otevřít na celnici, aby byla pravděpodobnost odstávky vozidla minimální.
Systém s omezenou délkou fronty. Uvažujme kanál QS s čekáním, který přijímá tok požadavků s intenzitou ; intenzita služby (pro jeden kanál); počet míst ve frontě.
Stavy systému jsou číslovány podle počtu požadavků spojených se systémem:
žádná fronta:
Všechny kanály jsou zdarma;
Jeden kanál je obsazený, zbytek je volný;
Kanály jsou obsazené, ostatní ne;
Všechny kanály jsou obsazené, nejsou žádné volné kanály;
je tam fronta:
Všech n kanálů je obsazeno; jedna aplikace je ve frontě;
Všech n kanálů je zaneprázdněných, r aplikací je ve frontě;
Všech n kanálů je obsazeno, m aplikace ve frontě.
GSP je znázorněno na obr. 5.9. Každá šipka je označena odpovídajícími intenzitami toků událostí. Podél šipek zleva doprava je systém přenášen vždy stejným tokem požadavků o intenzitě
Vícekanálová exponenciální SMO se liší od jednokanálového následovně. Je v něm více než jeden kanál. Příchozí požadavek se zařadí do fronty, pokud jsou všechny kanály obsazeny. Jinak požadavek zabírá volný kanál. 
(5.56)
Zapišme výrazy pro omezující pravděpodobnosti stavů pomocí zápisu: (viz 5.45)
Pravděpodobnost selhání. Přijatá přihláška je zamítnuta, pokud jsou všichni obsazeni n kanály a všechno m místa v řadě:
(5.57)
Relativní propustnost doplňuje pravděpodobnost selhání na jednu:
Absolutní propustnost QS:
(5.58)
Průměrný počet obsazených kanálů. Pro SMO s odmítnutím se shodoval s průměrným počtem žádostí v systému. Pro SMO u fronty se průměrný počet obsazených kanálů neshoduje s průměrným počtem aplikací v systému: druhá hodnota se liší od první o průměrný počet aplikací ve frontě.
Označme průměrný počet obsazených kanálů . Každý obsazený kanál obsluhuje v průměru požadavky za jednotku času a SMO celková služba je průměrná A aplikací za jednotku času. Když jeden vydělíme, dostaneme:
Průměrný počet požadavků ve frontě lze vypočítat přímo jako matematické očekávání diskrétní náhodné proměnné:
(5.59)
Zde opět (výraz v závorce) dochází k derivaci součtu geometrické posloupnosti (viz výše (5.50), (5.51)-(5.53)), pomocí vztahu pro ni dostaneme:
Průměrný počet aplikací v systému:
Průměrná doba čekání na žádost ve frontě. Podívejme se na řadu situací, které se liší stavem, ve kterém nově příchozí požadavek systém najde a jak dlouho bude muset čekat na obsluhu.
Pokud požadavek nenajde všechny kanály obsazené, nebude muset vůbec čekat (odpovídající členy v matematickém očekávání jsou rovny nule). Pokud přihláška dorazí v době, kdy jsou všichni zaneprázdněni P kanálů, ale není tam žádná fronta, bude muset čekat v průměru po dobu rovnající se (protože „tok uvolnění“ kanálů má intenzitu ). Pokud aplikace zjistí, že jsou všechny kanály obsazené a jedna aplikace před ní ve frontě, bude muset čekat v průměru určitou dobu (na každou aplikaci vpředu) atd. Pokud se aplikace ocitne ve frontě aplikací bude muset v průměru nějakou dobu počkat. Pokud se nově příchozí aplikace ocitne ve frontě m aplikací, pak nebude čekat vůbec (ale nebude obsloužena).
Průměrná čekací doba zjistíme vynásobením každé z těchto hodnot odpovídajícími pravděpodobnostmi:
(5.60)
Stejně jako v případě jednokanálového QS s čekáním podotýkáme, že tento výraz se od výrazu pro průměrnou délku fronty (5,59) liší pouze faktorem , tzn.
Průměrná doba, po kterou aplikace zůstává v systému, stejně jako u jednokanálového SMO, se liší od průměrné doby čekání průměrnou dobou obsluhy vynásobenou relativní propustností:
Systémy s neomezenou délkou fronty.
Zvažovali jsme kanál QS s čekáním, kdy ne více než m aplikací.
Stejně jako dříve je při analýze systémů bez omezení nutné uvažovat získané vztahy pro .
Pravděpodobnosti stavů získáme ze vzorců (5.56) přechodem k limitě (v ). Všimněte si, že součet odpovídající geometrické progrese konverguje a diverguje při > 1. Za předpokladu, že< 1 и устремив в формулах (5.56) величину m do nekonečna získáme výrazy pro limitní pravděpodobnosti stavů:
(5.61)
Pravděpodobnost poruchy, relativní a absolutní propustnost. Vzhledem k tomu, že každý požadavek bude dříve nebo později obsluhován, vlastnosti propustnosti QS budou:
Průměrný počet aplikací ve frontě získáme od (5,59):
a průměrná čekací doba je od (5,60):
Průměrný počet obsazených kanálů, jako dříve, je určen absolutní propustností:
Průměrný počet aplikací spojených s QS je definován jako průměrný počet aplikací ve frontě plus průměrný počet aplikací v provozu (průměrný počet obsazených kanálů):
Rostoucí složitost struktur a režimů reálných systémů komplikuje použití klasických metod teorie hromadné obsluhy vzhledem k rostoucímu rozměru řešených problémů, což je typické zejména pro systémy se síťovou strukturou. Jedním z možných způsobů, jak překonat dimenzionalitu, je použití modelů ve formě frontových sítí (Queuing).
SeMO je soubor konečného počtu obslužných uzlů, ve kterých požadavky obíhají a pohybují se v souladu se směrovací maticí z jednoho uzlu do druhého. Uzel je vždy otevřený SMO. Zároveň se oddělte SMO SMO− struktura systému a požadavky, které jím procházejí SeMO, − složky materiálových toků (zprávy (pakety) v komunikační síti, úkoly v multiprocesorových systémech, kontejnery toků nákladu atd.).
ve svém pořadí, SeMO slouží k určení nejdůležitějších systémových charakteristik informačních systémů: produktivita; doba doručení balíku; pravděpodobnost ztráty zprávy a zablokování v uzlech; oblasti přípustných hodnot zatížení, při kterých je zajištěna požadovaná kvalita služby atd.
Teoreticky SeMO Koncept stavu sítě je zásadní. Nejdůležitější charakteristika sítí MO− pravděpodobnosti jejich stavů. Určit pravděpodobnosti stavů SeMO zkoumat náhodný proces vyskytující se v síti. Jako modely proudící dovnitř SeMO Nejčastěji se také používají markovské a semimarkovské procesy.
3.3. Systém front jako model
1.5. Sítě řazení do fronty
Markovův proces se spojitým časem popisuje fungování exponenciály SeMO.
Síť je volána exponenciální pokud příchozí toky požadavků v každém SMO Poisson a časy každé fáze služby implementované v kterékoli SMO sítě mají exponenciální rozdělení. To nám umožňuje předpokládat, že obslužné stupně jsou na sobě nezávislé a nezávisí ani na parametrech příchozího toku, ani na stavu sítě, ani na trasách požadavků.
Teorie exponenciál SeMO nejrozvinutější a je široce používán jak pro studium sítí PD, tak pro studium multiprocesorů výpočetní systémy (CS). Byly vyvinuty praktické vzorce pro výpočet pravděpodobnostně-časových charakteristik (PTC) takových sítí a systémů.
Pokusy o hloubkovou analýzu nemarkovských modelů síťových systémů narážejí na značné potíže, které jsou způsobeny zejména nesamostatností doby trvání požadavků v různých uzlech modelů síťových systémů s nestandardními obory. Takže například za poměrně realistického předpokladu, že délka požadavku zůstává konstantní během jeho přenosu přes uzly sítě, je nutné sledovat cestu každého požadavku, což znemožňuje analyticky vypočítat charakteristiky pro síť s počet uzlů M>2.
Analýza prací věnovaných studiu nebo výpočtu neMarkovových modelů ukazuje, že řešení jsou zpravidla získávána algoritmicky pomocí složitých numerických výpočtů pomocí Laplaceových-Stieltjesových transformací, jsou implementována v softwaru, jsou vysoce pracná nebo mají významné chyby při posuzování výkonnostních ukazatelů informačních systémů (IS) v oblasti střední a velké zátěže. Proto pro modelování SeMO, opouštějí třídu multiplikativních, používají přibližné metody.
Srovnávací analýza metod přibližného modelování SeMO a příklady uvedené v ukazují, že je nutné používat přibližné metody pro výpočet SeMO s velkou opatrností, že při výpočtu konkrétního SeMO se v procesu řešení různých aplikovaných problémů jeví jako nezbytné provést výzkum za účelem posouzení přesnosti a citlivosti použité metody a také provést simulační experiment původního SeMO pro dostatečně velký soubor hodnot různých parametrů.
Analytické metody výpočtu charakteristik IS jsou založeny zpravidla na analýze exponenciálního CeMO. Pomocí tohoto matematického aparátu je možné získat analytické modely pro řešení široké škály problémů při studiu systémů. SeMO je především soubor vzájemně propojených systémů hromadné obsluhy. Proto je nutné připomenout hlavní vlastnosti těchto systémů.
Síť řazení do fronty představuje sbírku konečných čísel N obslužné uzly, ve kterých obíhají požadavky a pohybují se v souladu se směrovací maticí z jednoho uzlu do druhého. Uzel je vždy otevřený QS (a QS může být jakékoli třídy). Zároveň se oddělte SMO zobrazit funkčně nezávislé části reálného systému, souvislosti mezi SMO- struktura systému a požadavky, které jím procházejí SeMO,- složky materiálových toků (zprávy (pakety) v komunikační síti, úlohy v multiprocesorových systémech, kontejnery nákladních toků atd.).
Pro vizuální reprezentaci SeMO používá se graf, jehož vrcholy (uzly) odpovídají jednotlivým SMO a oblouky zobrazují spojení mezi uzly.
K přechodu aplikací mezi uzly dochází okamžitě v souladu s pravděpodobnostmi přechodu 
, p ij- pravděpodobnost, že požadavek po obsloužení v uzlu i půjde do uzlu j. Přirozeně, pokud uzly nejsou přímo propojeny navzájem, pak p ij= 0. Pokud od já- přechod uzlu pouze do jednoho uzlu j, Že p ij= 1.
SeMO klasifikovány podle několika kritérií (obr. 4).
Síť je volána lineární, pokud jsou intenzity aplikačních toků v uzlech propojeny lineárním vztahem
l j=a ij l i,
kde ij- koeficient úměrnosti, nebo relativní ke zdroji
l j=a j l 0 ,.
Koeficient a j přenosový koeficient charakterizuje podíl žádostí přijatých v j- uzel ze zdroje aplikací nebo - průměrný počet průchodů aplikace tímto uzlem během doby, kdy je aplikace v síti.
Pokud jsou intenzity aplikačních toků v uzlech sítě spojeny nelineárním vztahem (např. 
), pak se zavolá síť nelineární..
Síť je vždy lineární, pokud se v ní neztratí nebo nezmnoží aplikace.
OTEVŘENO Síť je otevřená síť, do které přicházejí požadavky z vnějšího prostředí a po obsloužení ze sítě odcházejí do vnějšího prostředí. Jinými slovy, vlastnost otevřené smyčky SeMO(RSeMO) je přítomnost jednoho nebo více nezávislých externích zdrojů, které generují aplikace vstupující do sítě, bez ohledu na to, kolik aplikací je již v síti. Kdykoli v RSeMO může existovat libovolný počet aplikací (od 0 do ¥).
Rýže. 4. Klasifikace frontových sítí
V uzavřené SeMO (ZSeMO) obíhá pevný počet aplikací a neexistuje žádný externí nezávislý zdroj. Na základě fyzikálních úvah, in ZSeM Je vybráno O vnějším oblouku, na kterém je vyznačeno pseudonula bod, ke kterému lze měřit charakteristiky časování.
Kombinovaný síť je síť, ve které neustále obíhá určitý počet aplikací a existují aplikace pocházející z externích nezávislých zdrojů.
V homogenní v síti cirkulují aplikace stejné třídy. A naopak v heterogenní sítě mohou obsahovat aplikace několika tříd. Aplikace patří do různých tříd, pokud se liší alespoň v jednom z následujících atributů:
Zákon rozdělení doby trvání služby v uzlech;
priority;
Trasy (cesty pohybu požadavků v síti).
V exponenciální sítě s dobou trvání služby ve všech uzlech jsou distribuovány podle exponenciálního zákona a toky vstupující do sítě s otevřenou smyčkou jsou jednoduché (Poisson). Ve všech ostatních případech je síť neexponenciální.
Pokud je prioritní služba poskytována alespoň v jednom uzlu, pak je to - přednost síť. Priorita je znak, který určuje pořadí služby. Pokud se obsluha požadavků v uzlech provádí v pořadí příjmu, pak taková síť žádná priorita.
Budeme tedy nazývat exponenciální SeMO, splňující požadavky:
Vstupní proudy SeMO Jed;
Celkově N SMO doba obsluhy požadavků má funkci exponenciálního rozdělení pravděpodobnosti a požadavky jsou obsluhovány v pořadí příchodu;
Přenos aplikace z výstupu i SMO u vchodu j- je nezávislá náhodná událost s pravděpodobností p ij ; p i0- pravděpodobnost, že aplikace opustí CeMO.
Pokud aplikace přijdou do sítě a opustí ji, pak se síť nazývá otevřená. Pokud aplikace nevstoupí do sítě nebo ji neopustí, síť se nazývá uzavřená. Počet aplikací v uzavřené síti je konstantní.
