V praktickej lekcii túto cestu zvážime a výsledky simulácie porovnáme s teoretickým riešením. Príklady riešenia problémov systémov radenia

Matematický (abstraktný) objekt, ktorého prvkami sú (obr. 2.1):

• vstupný (prichádzajúci) tok aplikácií (požiadaviek) pre službu;
• servisné zariadenia (kanály);
• rad aplikácií čakajúcich na službu;
• výstupný (odchádzajúce) tok obsluhovaných požiadaviek;
• tok žiadostí o následnú starostlivosť po prerušení služby;
• tok nevybavených požiadaviek.

Žiadosť(požiadavka, požiadavka, hovor, klient, správa, balík) - objekt vstupujúci do QS a vyžadujúci službu v zariadení. Súbor po sebe nasledujúcich aplikácií distribuovaných v časovom tvare vstupný tok aplikácií.

Ryža. 2.1.

servisné zariadenie(zariadenie, zariadenie, kanál, linka, nástroj, auto, router atď.) - QS prvok, ktorého účelom je obsluha aplikácií.

servis- oneskorenie požiadavky v obslužnom zariadení o určitý čas.

Trvanie služby- čas oneskorenia (služby) aplikácie v zariadení.

Úložné zariadenie(buffer, input buffer, output buffer) - súbor miest pre čakanie na aplikácie pred obslužným zariadením. Počet miest na čakanie - úložná kapacita.

Žiadosť prijatá SOT môže mať dva stavy:

• 1) služby(v zariadení);
• 2) očakávania(v akumulátore), ak sú všetky zariadenia zaneprázdnené vybavovaním iných požiadaviek.

Formulár pohľadávok v akumulátore a čakajúci servis otočiť aplikácie. Počet aplikácií v akumulátore čakajúcich na službu - dĺžka frontu.

Vyrovnávacia disciplína(disciplína vo fronte) - pravidlo pre zadávanie prichádzajúcich aplikácií do mechaniky (bufferu).

Servisná disciplína- pravidlo pre výber požiadaviek z frontu na službu v zariadení.

Priorita- predkupné právo (na zachytenie zdrojov) vstúpiť do akumulátora alebo vybrať z poradia na obsluhu aplikácií zariadení jednej triedy vo vzťahu k aplikáciám iných tried.

Existuje mnoho systémov radenia, ktoré sa líšia štruktúrnou a funkčnou organizáciou. Súčasne vývoj analytických metód na výpočet ukazovateľov výkonnosti QS v mnohých prípadoch zahŕňa množstvo obmedzení a predpokladov, ktoré zužujú súbor skúmaných QS. Preto neexistuje všeobecný analytický model pre ľubovoľnú komplexnú štruktúru QS.

Analytický model QS je súbor rovníc alebo vzorcov, ktoré umožňujú určiť pravdepodobnosti stavov systému v priebehu jeho prevádzky a ukazovatele výkonnosti na základe známych parametrov vstupného toku a servisných kanálov, vyrovnávacích a servisných disciplín.

Analytické modelovanie QS je značne uľahčené, ak procesy prebiehajúce v QS sú markovovské (tok aplikácií je najjednoduchší, servisné časy sú rozdelené exponenciálne). V tomto prípade môžu byť všetky procesy v QS opísané obyčajnými diferenciálnymi rovnicami a v obmedzujúcom prípade - pre stacionárne stavy - lineárnymi algebraickými rovnicami a po ich vyriešení akýmikoľvek metódami dostupnými v matematických softvérových balíkoch určiť vybrané ukazovatele výkonnosti. .

V systémoch IM sa pri implementácii QS akceptujú nasledujúce obmedzenia a predpoklady:

• aplikácia zadaná do systému okamžite spadá do prevádzky, ak vo fronte nie sú žiadne požiadavky a zariadenie je voľné;
• v zariadení na údržbu kedykoľvek môže byť len jedenžiadosť;
• po ukončení obsluhy ľubovoľnej požiadavky v zariadení sa okamžite vyberie ďalšia požiadavka z fronty na obsluhu, t.j. zariadenie nezaháľa ak je vo fronte aspoň jedna aplikácia;
• príjem žiadostí v QS a dĺžka ich služby nezávisia od počtu žiadostí, ktoré už sú v systéme, ani od iných faktorov;
• dĺžka servisných požiadaviek nezávisí od intenzity požiadaviek vstupujúcich do systému.

Pozrime sa podrobnejšie na niektoré prvky QS.

Vstupný (prichádzajúci) tok aplikácií. Tok udalostí sa nazýva sled homogénnych udalostí nasledujúcich po sebe a vyskytujúcich sa v niektorých, všeobecne povedané, náhodný bodov v čase. Ak udalosť spočíva v objavení sa nárokov, máme aplikačný tok. Na popísanie toku aplikácií vo všeobecnom prípade je potrebné nastaviť časové intervaly t = t k - t k-1 medzi susednými momentmi t k _ k a t k príjem žiadostí s poradovými číslami do - 1 a do resp (do - 1, 2, ...; t 0 - 0 - počiatočný časový okamih).

Hlavnou charakteristikou aplikačného toku je jeho X intenzita- priemerný počet aplikácií prichádzajúcich na vstup QS za jednotku času. Hodnota t = 1/X definuje priemerný časový interval medzi dvoma po sebe nasledujúcimi objednávkami.

Tok sa nazýva deterministický ak časové intervaly t to medzi susednými aplikáciami nadobúdajú určité vopred známe hodnoty. Ak sú intervaly rovnaké (x až= t pre všetkých k = 1, 2, ...), potom sa volá prúd pravidelné. Pre úplný popis pravidelného toku požiadaviek stačí nastaviť intenzitu toku X alebo hodnotu intervalu t = 1/X.

Prúd, v ktorom sú časové intervaly x k medzi susednými aplikáciami sú náhodné premenné, tzv náhodný. Pre úplný popis náhodného toku aplikácií vo všeobecnom prípade je potrebné nastaviť distribučné zákony F fc (x fc) pre každý z časových intervalov x k, k = 1,2,....

Náhodný stream, v ktorom sú všetky časové intervaly x b x 2,... medzi susediacimi po sebe nasledujúcimi zákazníkmi sú nezávislé náhodné premenné opísané distribučnými funkciami FjCij), F 2 (x 2), ... sa nazýva tok s obmedzený následný efekt.

Náhodný prúd je tzv opakujúci, ak všetky časové intervaly xb t 2 , ... distribuované medzi aplikáciami podľa toho istého zákona F(t). Existuje veľa opakujúcich sa prúdov. Každý distribučný zákon generuje svoj vlastný opakujúci sa tok. Opakujúce sa prúdy sú inak známe ako Palmové prúdy.

Ak intenzita X a distribučný zákon F(t) intervalov medzi po sebe nasledujúcimi požiadavkami sa časom nemení, potom sa tok požiadaviek nazýva stacionárne V opačnom prípade je tok aplikácie nestacionárne.

Ak v každom okamihu t k na vstupe QS sa môže objaviť len jeden zákazník, potom sa volá tok zákazníkov obyčajný. Ak sa môže kedykoľvek zobraziť viac ako jedna aplikácia, potom je tok aplikácií mimoriadny, alebo skupina.

Tok požiadaviek sa nazýva tok žiadny následný efekt, ak budú prijaté žiadosti bez ohľadu na to od seba, t.j. okamih prijatia ďalšej žiadosti nezávisí od toho, kedy a koľko žiadostí bolo doručených pred týmto okamihom.

Stacionárne obyčajné prúdenie bez následného účinku sa nazýva najjednoduchšie.

Časové intervaly t medzi požiadavkami v najjednoduchšom toku sú rozdelené podľa exponenciálny (ukážkový) zákon: s distribučnou funkciou F(t) = 1 - e~ m; hustota distribúcie/(f) = Heh~"l, kde X > 0 - distribučný parameter - intenzita toku aplikácií.

Najjednoduchší tok sa často nazýva Jed. Názov pochádza zo skutočnosti, že pre tento tok je pravdepodobnosť presne P fc (At). do požiadavky na určitý časový interval At je určený Poissonov zákon:

Treba poznamenať, že Poissonov tok, na rozdiel od najjednoduchšieho, môže byť:

• stacionárny, ak intenzita X sa časom nemení;
• nestacionárny, ak prietok závisí od času: X= >.(t).

Zároveň je najjednoduchší tok podľa definície vždy stacionárny.

Analytické štúdie modelov radenia sa často vykonávajú za predpokladu najjednoduchšieho toku požiadaviek, čo je spôsobené množstvom pozoruhodných vlastností, ktoré sú im vlastné.

1. Sumácia (zjednotenie) tokov. Najjednoduchší tok v teórii QS je podobný zákonu normálneho rozdelenia v teórii pravdepodobnosti: prechod na limit pre tok, ktorý je súčtom tokov s ľubovoľnými charakteristikami s nekonečným nárastom počtu členov a znížením ich intenzity vedie k najjednoduchšiemu toku.

Sum N nezávislé stacionárne obyčajné toky s intenzitami x x x 2 ,..., XN tvorí najjednoduchší tok s intenzitou

X=Y,^i za predpokladu, že pridané toky majú viac resp

menej rovnako malý vplyv na celkový prietok. V praxi sa celkový prietok blíži k najjednoduchšiemu at N > 5. Takže pri sčítaní nezávislých najjednoduchších prietokov bude najjednoduchší celkový prietok za akúkoľvek hodnotu N.

• 2. Pravdepodobné riedenie toku. pravdepodobnostný(ale nedeterministický) riedenie najjednoduchší tok aplikácie, v ktorých je ľubovoľná aplikácia náhodne s určitou pravdepodobnosťou R je vylúčený z toku bez ohľadu na to, či sú alebo nie sú vylúčené iné aplikácie, vedie k vzniku najjednoduchší tok s intenzitou X* = pX, kde X- intenzita počiatočného toku. Tok vylúčených aplikácií s intenzitou X** = (1 - p)X- tiež prvok tok.
• 3. Účinnosť. Ak sú obslužné kanály (zariadenia) navrhnuté pre čo najjednoduchší tok požiadaviek s intenzitou X, potom bude obsluha iných typov tokov (s rovnakou intenzitou) zabezpečená rovnako efektívne.
• 4. Jednoduchosť. Predpoklad najjednoduchšieho toku aplikácií umožňuje mnohým matematickým modelom získať explicitnou formou závislosť indikátorov QS od parametrov. Najväčší počet analytických výsledkov bol získaný pre najjednoduchší tok požiadaviek.

Analýza modelov s aplikačnými tokmi, ktoré sa líšia od najjednoduchších, zvyčajne komplikuje matematické výpočty a nie vždy umožňuje získať jednoznačné analytické riešenie. „Najjednoduchší“ tok dostal svoje meno práve kvôli tejto vlastnosti.

Aplikácie môžu mať rôzne práva na spustenie služby. V tomto prípade sa hovorí o aplikáciách heterogénne. Výhody niektorých tokov aplikácií oproti iným na začiatku služby sú dané prioritami.

Dôležitou charakteristikou vstupného toku je variačný koeficient

kde t int - matematické očakávanie dĺžky intervalu; o- smerodajná odchýlka dĺžky intervalu x int (náhodná premenná) .

Pre najjednoduchší tok (a = -, m = -) máme v = 1. Pre väčšinu

skutočné toky 0

Servisné kanály (zariadenia). Hlavnou charakteristikou kanála je trvanie služby.

Trvanie služby- čas strávený aplikáciou v zariadení - vo všeobecnom prípade je hodnota náhodná. V prípade nerovnomerného zaťaženia QS sa môžu časy obsluhy požiadaviek rôznych tried líšiť podľa distribučných zákonov alebo len priemernými hodnotami. V tomto prípade sa zvyčajne predpokladá, že servisné časy pre požiadavky každej triedy sú nezávislé.

Odborníci často predpokladajú, že trvanie servisných požiadaviek je rozdelené exponenciálny zákončo výrazne zjednodušuje analytické výpočty. Je to spôsobené tým, že procesy prebiehajúce v systémoch s exponenciálnym rozložením časových intervalov sú Markov procesy:

kde c - intenzita služieb, tu p = _--; t 0 bsl - matematika-

čas čakania na službu.

Okrem exponenciálneho rozdelenia existujú Erlang /c-rozdelenia, hyperexponenciálne rozdelenia, trojuholníkové rozdelenia a niektoré ďalšie. To by nás nemalo zmiasť, pretože sa ukazuje, že hodnota kritérií účinnosti QS len málo závisí od formy zákona o rozdelení času služby.

Pri štúdiu QS podstata služby, kvalita služby, neprichádza do úvahy.

Kanály môžu byť absolútne spoľahlivé tie. nezlyhať. Skôr sa dá akceptovať v štúdiu. Kanály môžu mať maximálna spoľahlivosť. V tomto prípade je model QS oveľa komplikovanejší.

Účinnosť QS závisí nielen od parametrov vstupných tokov a obslužných kanálov, ale aj od poradia, v ktorom sú prichádzajúce požiadavky obsluhované, t.j. od spôsobov, ako riadiť tok aplikácií, keď vstúpia do systému a sú odoslané do servisu.

Spôsoby riadenia toku aplikácií sú určené disciplínami:

• vyrovnávanie;
• služby.

Disciplíny vyrovnávania a údržby možno klasifikovať podľa nasledujúcich kritérií:

• dostupnosť priorít medzi aplikáciami rôznych tried;
• spôsob vytláčania aplikácií z radu (pre disciplíny ukladania do vyrovnávacej pamäte) a priraďovanie požiadaviek na služby (pre disciplíny služieb);
• pravidlo pre zabránenie alebo výber servisných požiadaviek;
• schopnosť meniť priority.

Variant klasifikácie bufferingových disciplín (čakanie v rade) podľa uvedených znakov je znázornený na obr. 2.2.

Záležiac ​​na dostupnosť alebo nedostatok priorít medzi aplikáciami rôznych tried možno všetky vyrovnávacie disciplíny rozdeliť do dvoch skupín: neprioritné a prioritné.

Autor: spôsob vytláčania aplikácií z úložiska možno rozlíšiť tieto triedy vyrovnávacích disciplín:

• bez vytlačenia požiadaviek - požiadavky, ktoré vstúpili do systému a zistili, že disk je úplne vyplnený, sa stratia;
• s posunom aplikácie tejto triedy, t.j. rovnakej triedy ako prijatá žiadosť;
• s posunutím aplikácie z triedy s najnižšou prioritou;
• s vytesnením aplikácie zo skupiny tried s nízkou prioritou.

Ryža. 2.2.

Ukladacie disciplíny môžu používať nasledovné pravidlá pre vyradenie žiadostí z akumulátora:

• náhodné premiestnenie;
• vylúčenie poslednej objednávky, t.j. vstúpil do systému neskôr ako všetky;
• vytesnenie „dlhej“ objednávky, t.j. nachádza v akumulátore dlhšie ako všetky predtým prijaté žiadosti.

Na obr. 2.3 je znázornená klasifikácia disciplín pre servisné aplikácie v súlade s rovnakými znakmi ako pre disciplíny buffering.

Niekedy sa úložná kapacita v modeloch považuje za neobmedzenú, hoci v skutočnom systéme je obmedzená. Takýto predpoklad je opodstatnený, keď je pravdepodobnosť straty objednávky v reálnom systéme v dôsledku preplnenia skladovacej kapacity menšia ako 10_3. V tomto prípade nemá disciplína prakticky žiadny vplyv na plnenie požiadaviek.

Záležiac ​​na dostupnosť alebo nedostatok priorít medzi požiadavkami rôznych tried možno všetky služobné disciplíny, ako aj vyrovnávacie disciplíny rozdeliť do dvoch skupín: neprioritné a prioritné.

Autor: ako sa prideľujú servisné lístky služobné disciplíny možno rozdeliť na disciplíny:

• jeden režim;
• skupinový režim;
• kombinovaný režim.

Ryža. 2.3.

V služobných disciplínach jeden režim servis zakaždým len jeden pridelený požiadavku, pre ktorú sa fronty skenujú po ukončení obsluhy predchádzajúcej požiadavky.

V služobných disciplínach skupinový režim servis zakaždým je priradená skupina aplikácií jeden front, pre ktorý sa fronty skenujú až po obslúžení všetkých požiadaviek z predtým priradenej skupiny. Novo priradená skupina lístkov môže obsahovať všetky lístky daného radu. Priradené skupinové žiadosti postupne vybrané z frontu a sú obsluhované zariadením, po ktorom je v súlade so stanovenou servisnou disciplínou pridelená ďalšia skupina aplikácií iného radu na obsluhu.

Kombinovaný režim- kombinácia jednoduchého a skupinového režimu, keď sa časť frontov žiadostí spracováva v jedinom režime a druhá časť - v skupinovom režime.

Servisné disciplíny môžu používať nasledujúce pravidlá výberu servisných požiadaviek.

Neprioritné(aplikácie nemajú privilégiá skorej služby - zachytávanie prostriedkov):

• služba kto prv príde, ten prv melie FIFO (prvý v - prvý von, prvý dnu prvý von)
• spätná služba- aplikácia sa vyberie z frontu v režime LIFO (posledný v - prvý von, posledný dovnútra, prvý von)
• náhodná služba- aplikácia sa vyberie z frontu v režime RAND (náhodný- náhodne);
• cyklická služba- aplikácie sa vyberajú v procese cyklického dotazovania pohonov v poradí 1, 2, H OD H- počet jednotiek), po ktorých sa zopakuje špecifikovaná sekvencia;

Priorita(aplikácie majú privilégiá na skorú službu – zachytávanie prostriedkov):

• s relatívne priority- ak v priebehu aktuálneho vybavovania požiadavky vstúpia do systému požiadavky s vyššou prioritou, potom sa obsluha aktuálnej požiadavky aj bez priority nepreruší a prijaté požiadavky sa zaradia do fronty; relatívne priority hrajú rolu až na konci aktuálnej služby aplikácie, keď je z frontu vybraná nová požiadavka na službu.
• s absolútne priority- pri prijatí požiadavky s vysokou prioritou sa obsluha požiadavky s nízkou prioritou preruší a prijatá požiadavka sa odošle na obsluhu; prerušená aplikácia môže byť vrátená do frontu alebo odstránená zo systému; ak je žiadosť vrátená do poradia, môže sa jej ďalšia obsluha vykonať z miesta prerušenia alebo nanovo;
• spol zmiešané priority- prísne obmedzenia čakacej doby v rade na obsluhu jednotlivých žiadostí si vyžadujú pridelenie absolútnych priorít; v dôsledku toho sa môže čakacia doba na žiadosti s nízkou prioritou ukázať ako neprijateľne dlhá, hoci jednotlivé žiadosti majú určitú rezervu; na splnenie obmedzení na všetky typy žiadostí spolu s absolútnymi prioritami možno niektorým žiadostiam priradiť relatívne priority a zvyšok možno obsluhovať v neprioritnom režime;
• s striedanie priorít- analógia relatívnych priorít, priorita sa berie do úvahy až v momente ukončenia aktuálnej obsluhy skupiny požiadaviek jedného frontu a pridelenia novej skupiny na obsluhu;
• plánovaná služba- nároky rôznych tried (umiestnené v rôznych úložiskách) sa vyberajú pre službu podľa určitého harmonogramu, ktorý špecifikuje postupnosť dotazovania vo frontoch aplikácií, napríklad v prípade troch tried aplikácií (obchodov) môže plán vyzerať ako (2, 1, 3, 3, 1, 2) alebo (1, 2, 3, 3, 2, 1).

V počítačových systémoch IM je disciplína spravidla implementovaná štandardne FIFO. Majú však nástroje, ktoré používateľovi poskytujú možnosť organizovať si potrebné disciplíny služieb, a to aj podľa harmonogramu.

Žiadosti prijaté CMO sú rozdelené do tried. V QS, čo je abstraktný matematický model, aplikácie patria do rôznych tried v prípade, že sa líšia v simulovanom reálnom systéme aspoň jednou z nasledujúcich vlastností:

• trvanie služby;
• priority.

Ak sa aplikácie nelíšia v trvaní služby a prioritách, môžu byť reprezentované aplikáciami rovnakej triedy, vrátane prípadov, keď pochádzajú z rôznych zdrojov.

Pre matematický popis služobných disciplín so zmiešanými prioritami používame matica priorít,čo je štvorcová matica Q = (q, ;), ja, j - 1,..., I, I - počet tried aplikácií vstupujúcich do systému.

Prvok q(j matica nastavuje prioritu požiadaviek triedy i v súvislosti s triednymi aplikáciami; a môže nadobudnúť nasledujúce hodnoty:

• 0 - žiadna priorita;
• 1 - relatívna priorita;
• 2 - absolútna priorita.

Prvky matice priorít musia spĺňať nasledovné požiadavky:

• q n= 0, pretože medzi požiadavkami rovnakej triedy nemožno nastaviť žiadne priority;
• ak q (j = potom 1 alebo 2 q^ = 0, pretože aplikácie triedy if i majú prednosť pred triednymi požiadavkami j, potom tieto nemôžu mať prednosť pred triednymi nárokmi i (i,j = 1, ..., I).

Záležiac ​​na príležitosti na zmenu priorít Počas prevádzky systému sú prioritné disciplíny vyrovnávacej pamäte a servisu rozdelené do dvoch tried:

• 1) s statické priority, ktoré sa časom nemenia;
• 2) s dynamické priority, ktorá sa môže počas prevádzky systému meniť v závislosti od rôznych faktorov, napríklad keď sa dosiahne určitá kritická hodnota dĺžky frontu žiadostí triedy, ktorá nemá prioritu alebo má nízku prioritu, možno jej priradiť vyššiu prioritou.

V počítačových systémoch IM nevyhnutne existuje jeden prvok (objekt), cez ktorý a len cez neho sa do modelu zadávajú požiadavky. Štandardne sú všetky zadané aplikácie bez priority. Existujú však možnosti priradenia priorít v poradí 1, 2, ..., a to aj počas vykonávania modelu, t.j. v dynamike.

Odchádzajúci prúd je tok obsluhovaných požiadaviek opúšťajúcich QS. V reálnych systémoch prechádzajú aplikácie niekoľkými QS: tranzitná komunikácia, produkčné potrubie atď. V tomto prípade je odchádzajúci tok prichádzajúci tok pre nasledujúci QS.

Prichádzajúci tok prvého QS, ktorý prešiel nasledujúcimi QS, je skreslený a to komplikuje analytické modelovanie. Treba však mať na pamäti, že s najjednoduchším vstupným tokom a exponenciálnou službou(tie. v Markovových systémoch) je výstupný tok tiež najjednoduchší. Ak má čas služby neexponenciálnu distribúciu, potom odchádzajúci tok nielenže nie je jednoduchý, ale ani sa neopakuje.

Upozorňujeme, že časové intervaly medzi odchádzajúcimi požiadavkami nie sú rovnaké ako servisné intervaly. Môže sa totiž ukázať, že po skončení ďalšej služby je QS nejaký čas nečinný pre nedostatok aplikácií. V tomto prípade interval odchádzajúceho toku pozostáva z času nečinnosti QS a servisného intervalu prvej požiadavky, ktorá prišla po prestoji.

V QS môže byť okrem odchádzajúceho toku obsluhovaných požiadaviek tok nevybavených požiadaviek. Ak takýto QS dostane opakujúci sa tok a služba je exponenciálna, potom tok neobsluhovaných zákazníkov je tiež opakujúci sa.

Bezplatné fronty kanálov. Vo viackanálovom QS sa môžu vytvárať rady voľných kanálov. Počet voľných kanálov je náhodná hodnota. Výskumníkov môžu zaujímať rôzne charakteristiky tejto náhodnej premennej. Typicky je to priemerný počet kanálov obsadených službou na interval prieskumu a ich koeficienty zaťaženia.

Ako sme už uviedli, v reálnych objektoch sú požiadavky postupne obsluhované v niekoľkých QS.

Nazýva sa konečná množina sekvenčne prepojených QS, ktoré spracovávajú aplikácie, ktoré v nich cirkulujú čakacia sieť (Semo) (obr. 2.4, a).

Ryža. 2.4.

SEMO sa tiež nazýva viacfázové QS.

Príklad konštrukcie QEMO IM zvážime neskôr.

Hlavnými prvkami QS sú uzly (U) a zdroje (generátory) požiadaviek (G).

Uzol siete sú systémom radenia.

Zdroj- generátor aplikácií vstupujúcich do siete a vyžadujúcich určité stupne služby v uzloch siete.

Pre zjednodušený obraz QEMO sa používa graf.

Gróf Semo- orientovaný graf (digraf), ktorého vrcholy zodpovedajú uzlom QEM a oblúky predstavujú prechody aplikácií medzi uzlami (obr. 2.4, b).

Takže sme zvážili základné koncepty QS. No pri vývoji počítačových systémov pre IM a ich zdokonaľovaní sa nevyhnutne využíva aj obrovský tvorivý potenciál v súčasnosti obsiahnutý v analytickom modelovaní QS.

Pre lepšie vnímanie tohto tvorivého potenciálu sa ako prvé priblíženie zastavme pri klasifikácii modelov QS.

Obrázok 0 - 2 Streamy udalostí (a) a najjednoduchší stream (b)

10.5.2.1. stacionárnosť

Tok sa nazýva stacionárny , ak pravdepodobnosť zasiahnutia jedného alebo druhého počtu udalostí v elementárnom časovom období dĺžka τ (

Obrázok 0-2 , a) závisí len od dĺžky úseku a nezávisí od toho, kde presne na osi t táto oblasť sa nachádza.

Stacionarita toku znamená jeho rovnomernosť v čase; pravdepodobnostné charakteristiky takéhoto toku sa časom nemenia. Najmä takzvaná intenzita (alebo "hustota") toku udalostí, priemerný počet udalostí za jednotku času pre stacionárny tok, musí zostať konštantná. To, samozrejme, neznamená, že skutočný počet udalostí vyskytujúcich sa za jednotku času je konštantný; tok môže mať lokálne koncentrácie a riedky. Je dôležité, aby pri stacionárnom toku tieto koncentrácie a zriedenie nemali pravidelný charakter a priemerný počet udalostí pripadajúcich na jeden časový interval zostal konštantný počas celého posudzovaného obdobia.

V praxi často dochádza k tokom udalostí, ktoré (aspoň na obmedzený čas) možno považovať za stacionárne. Napríklad tok hovorov prichádzajúci do telefónnej ústredne povedzme v intervale od 12 do 13 hodín možno považovať za stacionárny. Rovnaký tok už nebude stáť celý deň (v noci je intenzita toku hovorov oveľa menšia ako cez deň). Všimnite si, že to isté je prípad väčšiny fyzikálnych procesov, ktoré nazývame „stacionárne“, v skutočnosti sú stacionárne iba počas obmedzeného časového obdobia a predĺženie tohto obdobia do nekonečna je len pohodlným trikom používaným na zjednodušenie.

10.5.2.2. Žiadny následný efekt

Tok udalostí sa nazýva tok bez následkov , ak pre akékoľvek neprekrývajúce sa časové intervaly počet udalostí pripadajúcich na jeden z nich nezávisí od toho, koľko udalostí pripadá na druhý (alebo iné, ak sa berú do úvahy viac ako dva úseky).

V takýchto prúdoch sa udalosti, ktoré tvoria prúd, objavujú v po sebe nasledujúcich časových bodoch nezávisle od seba. Napríklad tok cestujúcich vstupujúcich do stanice metra možno považovať za tok bez následkov, pretože dôvody, ktoré spôsobili príchod jednotlivého cestujúceho v tomto konkrétnom okamihu a nie v inom, spravidla nesúvisia s podobnými dôvodmi. pre ostatných cestujúcich. Ak sa takáto závislosť objaví, je porušená podmienka neprítomnosti následného účinku.

Zoberme si napríklad tok nákladných vlakov idúcich po železničnej trati. Ak z bezpečnostných dôvodov nemôžu ísť za sebou častejšie ako v určitých časových intervaloch t0 , potom existuje závislosť medzi udalosťami v streame a je porušená podmienka bez následkov. Ak však interval t0 je malý v porovnaní s priemerným intervalom medzi vlakmi, potom je takéto porušenie bezvýznamné.

Obrázok 0 - 3 Poissonovo rozdelenie

Zvážte na osi t najjednoduchší tok dejov s intenzitou λ. (Obrázok 0-2 b) . Nás bude zaujímať náhodný časový interval T medzi susednými udalosťami v tomto prúde; nájsť jeho distribučný zákon. Najprv nájdime distribučnú funkciu:

F(t) = P(T ( 0-2)

t.j. pravdepodobnosť, že hodnota T bude mať hodnotu menšiu akot. Odložte od začiatku intervalu T (body t0) segment t a nájdite pravdepodobnosť, že interval T bude menej t . K tomu je potrebné, aby pre úsek dĺžky t , susediaci s bodom t0 , zásah do udalosti aspoň jedného vlákna. Vypočítajme si to pravdepodobnosť F(t) prostredníctvom pravdepodobnosti opačnej udalosti (na segment t nezasiahnu žiadne udalosti streamu):

F (t) \u003d 1 – P 0

Pravdepodobnosť P 0 nájdeme podľa vzorca (1), za predpokladum = 0:

odkiaľ bude distribučná funkcia hodnoty T:

(0-3)

Na zistenie hustoty distribúcie f(t) náhodná premenná T, je potrebné rozlišovať výraz (0‑1) ot:

0-4)

Distribučný zákon s hustotou (0-4) sa nazýva exponenciálny (alebo exponenciálne ). Hodnota λ sa nazýva parameter vzorový zákon.

Obrázok 0 - 4 Exponenciálna distribúcia

Nájdite číselné charakteristiky náhodnej premennej T- matematické očakávanie (priemerná hodnota) M[t] = mt , a disperzia Dt. Máme

( 0-5)

(integrácia po častiach).

Rozptyl hodnoty T je:

(0-6)

Po extrakcii druhej odmocniny rozptylu nájdeme smerodajnú odchýlku náhodnej premennej T.

Takže pre exponenciálne rozdelenie sú matematické očakávania a smerodajná odchýlka navzájom rovnaké a sú inverzné k parametru λ, kde λ. intenzita prúdenia.

Teda vzhľad m udalosti v danom časovom intervale zodpovedajú Poissonovmu rozdeleniu a pravdepodobnosť, že časové intervaly medzi udalosťami budú menšie ako nejaké vopred určené číslo, zodpovedá exponenciálnemu rozdeleniu. Toto všetko sú len rôzne opisy toho istého stochastického procesu.

Príklad QS-1 .

Ako príklad si predstavte bankový systém v reálnom čase, ktorý slúži veľkému počtu zákazníkov. V čase špičky tvoria požiadavky bankových pokladníkov, ktorí pracujú s klientmi, Poissonov tok a prichádzajú v priemere dve za 1 s (λ = 2).Tok pozostáva z požiadaviek, ktoré prichádzajú rýchlosťou 2 požiadavky za sekundu.

Vypočítajte pravdepodobnosť P ( m ) výskyty m správy za 1 s. Keďže λ = 2, z predchádzajúceho vzorca máme

Nahradením m = 0, 1, 2, 3, získame nasledujúce hodnoty (až štyridesatinné miesta):

Obrázok 0 - 5 Najjednoduchší príklad toku

Je tiež možných viac ako 9 správ za 1 s, ale pravdepodobnosť je veľmi malá (asi 0,000046).

Výsledné rozdelenie možno znázorniť ako histogram (zobrazený na obrázku).

Príklad CMO-2.

Zariadenie (server), ktoré spracuje tri správy za 1 s.

Nech existuje zariadenie, ktoré dokáže spracovať tri správy za 1 s (µ=3). V priemere sú dve správy prijaté za 1 s a v súlade c Poissonovo rozdelenie. Aký podiel týchto správ sa spracuje ihneď po prijatí?

Pravdepodobnosť, že rýchlosť príchodu bude menšia alebo rovná 3 s, je daná

Ak systém dokáže spracovať maximálne 3 správy za 1 s, potom je pravdepodobnosť, že nebude preťažený

Inými slovami, 85,71 % správ bude doručených okamžite a 14,29 % s určitým oneskorením. Ako vidíte, oneskorenie pri spracovaní jednej správy o čas dlhší ako čas spracovania 3 správ sa vyskytne len zriedka. Doba spracovania 1 správy je v priemere 1/3 s. Preto bude oneskorenie väčšie ako 1 s zriedkavé, čo je pre väčšinu systémov celkom prijateľné.

Príklad CMO 3

· Ak je bankový pokladník zaneprázdnený počas 80 % svojho pracovného času a zvyšok času trávi čakaním na zákazníkov, možno ho považovať za zariadenie s faktorom využitia 0,8.

· Ak sa komunikačný kanál používa na prenos 8-bitových symbolov rýchlosťou 2400 bps, t.j. maximálne 2400/8 symbolov sa prenesie za 1 s a budujeme systém, v ktorom je celkové množstvo odoslaných údajov 12 000 symbolov z rôznych zariadení cez kanál za rušnú minútu (vrátane synchronizácie, znakov konca správy, riadiacich znakov atď.), potom sa miera využitia vybavenia komunikačného kanála počas tejto minúty rovná

· Ak motor prístupu k súboru v rušných hodinách vykoná 9 000 prístupov k súborom a čas na jeden prístup je v priemere 300 ms, potom je využitie hardvéru nástroja na prístup k súborom v rušných hodinách

Pojem využitie zariadenia sa bude používať pomerne často. Čím je využitie zariadenia bližšie k 100 %, tým je oneskorenie väčšie a rad dlhší.

Pomocou predchádzajúceho vzorca môžete zostaviť tabuľky hodnôt Poissonovej funkcie, z ktorých môžete určiť pravdepodobnosť prijatiam alebo viac správ v danom časovom období. Napríklad, ak priemerne 3,1 správy za sekundu [t.j. λ = 3.1], potom pravdepodobnosť prijatia 5 alebo viacerých správ za danú sekundu je 0,2018 (napr.m = 5 v tabuľke). Alebo v analytickej forme

Pomocou tohto výrazu môže systémový analytik vypočítať pravdepodobnosť, že systém nesplní dané kritérium zaťaženia.

Často je možné vykonať počiatočné výpočty pre hodnoty zaťaženia zariadenia.

p ≤ 0,9

Tieto hodnoty je možné získať pomocou Poissonových tabuliek.

Nech je opäť priemerná rýchlosť prijatia správy λ = 3,1 správy/s. Z tabuliek vyplýva, že pravdepodobnosť prijatia 6 a viac správ za 1 s je 0,0943. Preto sa toto číslo môže považovať za kritérium zaťaženia pre počiatočné výpočty.

10.6.2. Dizajnérske výzvy

Vzhľadom na náhodný charakter príchodu správ do zariadenia, zariadenie trávi časť času spracovaním alebo obsluhou každej správy, čo vedie k vytváraniu radov. Fronta v banke čaká na uvoľnenie pokladníka a jeho počítača (terminálu). Front správ vo vstupnej vyrovnávacej pamäti počítača čaká na spracovanie procesorom. Fronta požiadaviek na dátové polia čaká na uvoľnenie kanálov atď. Fronty sa môžu tvoriť vo všetkých úzkych miestach systému.

Čím vyššia je miera využitia zariadenia, tým dlhšie budú výsledné fronty. Ako bude ukázané nižšie, je možné navrhnúť systém, ktorý uspokojivo funguje s faktorom využitia ρ = 0,7, ale faktor väčší ako ρ > 0,9 môže mať za následok zlú kvalitu služby. Inými slovami, ak je hromadný dátový odkaz zaťažený 20 %, je nepravdepodobné, že na ňom bude fronta. Ak sa načítava; je 0,9, potom sa spravidla budú tvoriť rady, niekedy veľmi veľké.

Koeficient využitia zariadenia sa rovná pomeru zaťaženia zariadenia k maximálnemu zaťaženiu, ktoré toto zariadenie znesie, alebo sa rovná pomeru doby obsadenia zariadenia k celkovej dobe jeho prevádzky.

Pri navrhovaní systému je bežné odhadnúť faktor využitia pre rôzne typy zariadení; relevantné príklady budú uvedené v ďalších kapitolách. Znalosť týchto koeficientov vám umožňuje vypočítať fronty pre príslušné vybavenie.

· Aká je dĺžka frontu?

· Koľko času to bude trvať?

Na otázky tohto typu možno odpovedať pomocou teórie radenia.

10.6.3. Systémy radenia, ich triedy a hlavné charakteristiky

Pre QS sú toky udalostí toky požiadaviek, toky „obslužných“ požiadaviek atď. Ak tieto toky nie sú Poisson (Markovov proces), matematický popis procesov vyskytujúcich sa v QS sa stáva neporovnateľne zložitejším a vyžaduje si ťažkopádnejší aparát. priviesť ho do analytických vzorcov je možné len v najjednoduchších prípadoch.

Aparatúra „markovskej“ teórie radenia však môže byť užitočná aj v prípade, že proces prebiehajúci v QS je odlišný od Markovovho, pomocou ktorého možno približne odhadnúť charakteristiky účinnosti QS. Je potrebné poznamenať, že čím je QS komplexnejší, čím viac obslužných kanálov obsahuje, tým presnejšie sú približné vzorce získané pomocou Markovovej teórie. Navyše v mnohých prípadoch nie je na prijímanie informovaných rozhodnutí o riadení prevádzky QS vôbec potrebné mať presné znalosti o všetkých jeho charakteristikách, často celkom približné, orientačné.

QS sú rozdelené do systémov s:

zlyhania (so stratami). V takýchto systémoch žiadosť, ktorá príde v momente, keď sú všetky kanály obsadené, dostane „odmietnutie“, opustí QS a nezúčastňuje sa na ďalšom procese obsluhy.

čakanie (s radom). V takýchto systémoch sa požiadavka, ktorá príde, keď sú všetky kanály obsadené, zaradí do frontu a čaká, kým sa jeden z kanálov neuvoľní. Keď je kanál voľný, jedna z aplikácií vo fronte je prijatá na službu.

Služba (disciplína v rade) v čakacom systéme môže byť

usporiadaný (žiadosti sa doručujú v poradí prijatia),

· neusporiadaný(žiadosti sa doručujú v náhodnom poradí) príp

stoh (posledná aplikácia sa vyberie ako prvá z poradia).

Priorita

o so statickou prioritou

o s dynamickou prioritou

(v druhom prípade a priori tet sa môže napríklad zvyšovať s časom čakania na žiadosť).

Systémy s frontom sa delia na systémy

· s neobmedzeným čakaním a

· s obmedzeným čakanie.

V systémoch s neobmedzeným čakaním sa každá požiadavka, ktorá príde v momente, keď nie sú voľné kanály, dostane do frontu a „trpezlivo“ čaká na uvoľnenie kanálu, ktorý ju prijme do služby. Každá žiadosť prijatá SOT bude skôr či neskôr doručená.

V systémoch s obmedzeným čakaním sú stanovené určité obmedzenia na zotrvanie aplikácie v rade. Môžu platiť tieto obmedzenia

· dĺžka frontu (počet aplikácií súčasne vo frontovom systéme s obmedzenou dĺžkou frontu),

· čas zotrvania aplikácie v rade (po určitej dobe zotrvania v rade aplikácia opustí poradie a systém odchádza s obmedzenou čakacou dobou),

· celkový čas strávený aplikáciou v QS

atď.

V závislosti od typu QS sa pri hodnotení jeho účinnosti môžu použiť určité hodnoty (ukazovatele výkonnosti). Napríklad pre QS s poruchami je jednou z najdôležitejších charakteristík jeho produktivity tzv absolútna šírka pásma priemerný počet požiadaviek, ktoré môže systém obslúžiť za jednotku času.

Spolu s absolútnym sa často uvažuje relatívna priepustnosť CMO je priemerný podiel prichádzajúcich požiadaviek obsluhovaných systémom (pomer priemerného počtu požiadaviek obsluhovaných systémom za jednotku času k priemernému počtu požiadaviek prijatých počas tohto času).

Okrem absolútnej a relatívnej priepustnosti pri analýze QS s poruchami nás môžu v závislosti od úlohy štúdie zaujímať aj ďalšie charakteristiky, napr.

· priemerný počet obsadených kanálov;

· priemerné relatívne prestoje systému ako celku a jednotlivého kanála

atď.

Očakávané QS majú mierne odlišné charakteristiky. Je zrejmé, že pre QS s neobmedzenou dobou čakania stráca absolútna aj relatívna priepustnosť svoj význam, pretože každý nárok príde skoro.alebo neskôr budú doručené. Pre takýto QS sú dôležité vlastnosti:

· priemerný počet žiadostí vo fronte;

· priemerný počet aplikácií v systéme (vo fronte a v prevádzke);

· priemerná doba čakania na žiadosť vo fronte;

· priemerný čas strávený aplikáciou v systéme (vo fronte a v prevádzke);

ako aj ďalšie charakteristiky očakávania.

Pre QS s obmedzeným čakaním sú zaujímavé obe skupiny charakteristík: absolútna aj relatívna priepustnosť a čakacie charakteristiky.

Na analýzu procesu vyskytujúceho sa v QS je nevyhnutné poznať hlavné parametre systému: počet kanálov P, intenzita aplikačného tokuλ , výkonnosť každého kanála (priemerný počet požiadaviek μ obsluhovaných kanálom za jednotku času), podmienky pre vytvorenie frontu (obmedzenia, ak existujú).

V závislosti od hodnôt týchto parametrov sú vyjadrené charakteristiky účinnosti prevádzky QS.

10.6.4. Vzorce na výpočet charakteristík QS pre prípad prevádzky s jedným zariadením

Obrázok 0 - 6 Model systému radenia s radom

Takéto fronty môžu byť vytvorené správami na vstupe procesora, ktoré čakajú na spracovanie. Môžu sa vyskytnúť počas prevádzky účastníckych staníc pripojených k viacbodovému komunikačnému kanálu. Podobne sa na čerpacích staniciach tvoria rady áut. Ak je však k službe viac ako jeden vstup, máme rad s mnohými zariadeniami a analýza sa stáva zložitejšou.

Zvážte prípad najjednoduchšieho toku servisných požiadaviek.

Účelom tu prezentovanej teórie radenia je priblížiť priemernú veľkosť frontu, ako aj priemerný čas strávený správami čakajúcimi vo frontoch. Je tiež žiaduce odhadnúť, ako často front prekročí určitú dĺžku. Tieto informácie nám umožnia vypočítať napríklad potrebné množstvo vyrovnávacej pamäte na ukladanie front správ a súvisiacich programov, požadovaný počet komunikačných liniek, požadované veľkosti vyrovnávacej pamäte pre huby atď. Bude možné odhadnúť časy odozvy.

Každá z charakteristík sa líši v závislosti od použitých prostriedkov.

Zvážte front s jedným serverom. Pri navrhovaní výpočtového systému sa väčšina frontov tohto typu počíta pomocou vyššie uvedených vzorcov. variačný faktor servisného času

Vzorec Khinchin-Polachek sa používa na výpočet dĺžky frontu pri návrhu informačných systémov. Uplatňuje sa v prípade exponenciálneho rozdelenia času príchodu pre ľubovoľné rozdelenie času obsluhy a akúkoľvek kontrolnú disciplínu, pokiaľ výber ďalšej správy na obsluhu nezávisí od času obsluhy.

Pri projektovaní systémov dochádza k situáciám, keď vznikajú fronty, keď disciplína kontroly nepochybne závisí od času obsluhy. V niektorých prípadoch sa napríklad môžeme rozhodnúť použiť najskôr kratšie správy, aby sme dosiahli rýchlejší priemerný čas služby. Pri riadení komunikačnej linky je možné priradiť vyššiu prioritu vstupným správam ako výstupným, pretože prvé sú kratšie. V takýchto prípadoch už nie je potrebné používať Khinchinovu rovnicu

Väčšina servisných časov v informačných systémoch leží niekde medzi týmito dvoma prípadmi. Konštantné servisné časy sú zriedkavé. Ani čas prístupu na pevný disk nie je konštantný kvôli rozdielnej polohe dátových polí na povrchu. Jedným príkladom ilustrujúcim prípad konštantného servisného času je obsadenie komunikačnej linky na prenos správ pevnej dĺžky.

Na druhej strane rozptyl servisného času nie je taký veľký ako v prípade ľubovoľného alebo exponenciálneho rozdelenia, t.j.σs málokedy dosahuje hodnotyt s. Tento prípad sa niekedy považuje za „najhorší prípad“, a preto sa používajú vzorce, ktoré odkazujú na exponenciálne rozdelenie servisných časov.Takýto výpočet môže poskytnúť trochu nadhodnotené veľkosti frontu a čakacie doby, ale táto chyba aspoň nie je nebezpečná.

Exponenciálne rozloženie servisných časov určite nie je tým najhorším prípadom, s ktorým sa človek musí reálne vysporiadať. Ak sa však časy obsluhy získané z výpočtu frontov ukážu ako horšie rozložené ako exponenciálne rozložené časy, je to pre vývojára často varovný signál. Ak je štandardná odchýlka väčšia ako stredná hodnota, potom je zvyčajne potrebné opraviť výpočty.

Zvážte nasledujúci príklad. Existuje šesť typov správ so servisnými časmi 15, 20, 25, 30, 35 a 300. Počet správ pre každý typ je rovnaký. Štandardná odchýlka týchto časov je o niečo vyššia ako ich priemer. Hodnota posledného servisného času je oveľa väčšia ako ostatné. To spôsobí, že správy budú vo fronte oveľa dlhšie, ako keby boli servisné časy v rovnakom poradí. V tomto prípade je pri navrhovaní vhodné prijať opatrenia na zníženie dĺžky frontu. Napríklad, ak tieto čísla súvisia s dĺžkami správ, potom by sa možno veľmi dlhé správy mali rozdeliť na časti.

10.6.6. Príklad výpočtu

Pri návrhu bankového systému je žiaduce poznať počet zákazníkov, ktorí budú musieť čakať v rade na jedného pokladníka počas špičiek.

Čas odozvy systému a jeho štandardná odchýlka sú vypočítané s prihliadnutím na čas zadávania údajov z pracovnej stanice, tlače a spracovania dokumentov.

Úkony pokladníka boli načasované. Obslužný čas ts sa rovná celkovému času strávenému pokladníkom u klienta. Miera využitia pokladníka ρ je úmerná dobe jeho zamestnania. Ak λ je počet zákazníkov počas špičky, potom ρ pre pokladníka je

Povedzme, že počas špičky je 30 zákazníkov za hodinu. V priemere strávi pokladník 1,5 minúty na zákazníka. Potom

ρ = (1,5 x 30) / 60 = 0,75

t.j. pokladňa je využívaná na 75 %.

Počet ľudí v rade sa dá rýchlo odhadnúť pomocou grafov. Z nich vyplýva, že ak ρ = 0,75, tak priemerný počet nq osôbv rade pri pokladni leží medzi 1,88 a 3,0 v závislosti od štandardnej odchýlky pre t s .

Predpokladajme, že meranie smerodajnej odchýlky pre ts dáva hodnotu 0,5 min. Potom

σ s = 0,33 t s

Z grafu na prvom obrázku zistíme, že nq = 2,0, teda v priemere budú pri pokladni čakať dvaja zákazníci.

Celkový čas, ktorý zákazník strávi pri pokladni, nájdete ako

t ∑ = t q + t s = 2,5 min + 1,5 min = 4 min

kde t s sa vypočíta pomocou Khinchin-Polachekovho vzorca.

10.6.7. faktor zisku

Analýzou kriviek na obrázkoch vidíme, že keď sa zariadenie obsluhujúce front využije na viac ako 80 %, krivky začnú rásť alarmujúcou rýchlosťou. Táto skutočnosť je veľmi dôležitá pri návrhu systémov prenosu dát. Ak navrhujeme systém s viac ako 80% využitím hardvéru, potom môže mierny nárast prevádzky viesť k drastickému poklesu výkonu systému alebo dokonca spôsobiť jeho zrútenie.

Nárast prichádzajúcej návštevnosti o malý počet x %. vedie k zvýšeniu veľkosti frontu približne o

Ak je miera využitia zariadenia 50 %, potom sa toto zvýšenie rovná 4 ts % pre exponenciálnu distribúciu servisného času. Ale ak je využitie zariadenia 90%, potom nárast veľkosti fronty je 100 ts%, čo je 25-krát viac. Mierne zvýšenie záťaže pri 90% využití zariadení vedie k 25-násobnému zvýšeniu veľkosti frontu v porovnaní s prípadom 50% využitia zariadenia.

Podobne sa zvyšuje aj čas v rade

Pri exponenciálne rozloženom prevádzkovom čase má táto hodnota hodnotu 4 t s2 pri vyťažení zariadení 50 % a 100 t s2 pre koeficient 90 %, teda opäť 25-krát horšie.

Okrem toho pre malé faktory využitia zariadení je vplyv zmien σs na veľkosť frontu nevýznamný. Pri veľkých koeficientoch je však zmena σ s výrazne ovplyvňuje veľkosť frontu. Preto pri navrhovaní systémov s vysokým využitím zariadení je žiaduce získať presné informácie o parametriσ s. Nepresnosť predpokladu ohľadom exponenciality rozdelenia tsje najvýraznejší pri veľkých hodnotách ρ. Navyše, ak sa čas služby náhle zvýši, čo je možné v komunikačných kanáloch pri prenose dlhých správ, potom sa v prípade veľkého ρ vytvorí významný rad.

Pomerne často sa pri analýze ekonomických systémov musia riešiť takzvané problémy s radovaním, ktoré vznikajú v nasledujúcej situácii. Nechajte analyzovať systém údržby auta pozostávajúci z určitého počtu staníc rôznych kapacít. Na každej stanici (prvku systému) môžu nastať aspoň dve typické situácie:

1. počet žiadostí je pre túto stanicu príliš vysoký, sú tu rady a musíte platiť za meškanie služby;
2. stanica dostáva príliš málo požiadaviek a teraz je už potrebné počítať so stratami spôsobenými prestojmi stanice.

Je zrejmé, že cieľom systémovej analýzy je v tomto prípade určiť nejaký vzťah medzi stratou príjmov v dôsledku frontoch a straty v dôsledku iba ja staníc.

Teória radenia– špeciálna časť teórie systémov je časť teórie pravdepodobnosti, v ktorej sa študujú systémy radenia pomocou matematických modelov.

Systém radenia (QS)- ide o model, ktorý zahŕňa: 1) náhodný tok požiadaviek, hovorov alebo zákazníkov, ktorí potrebujú službu; 2) algoritmus na implementáciu tejto služby; 3) kanály (zariadenia) na údržbu.

Príkladmi SOT sú pokladne, čerpacie stanice, letiská, predajcovia, kaderníctva, lekári, telefónne ústredne a iné zariadenia, ktoré obsluhujú určité aplikácie.

Problém teórie radenia spočíva vo vypracovaní odporúčaní pre racionálnu výstavbu QS a racionálnej organizácii ich práce s cieľom zabezpečiť vysokú efektivitu služby pri optimálnych nákladoch.

Hlavnou črtou problémov tejto triedy je jasná závislosť výsledkov analýzy a prijatých odporúčaní od dvoch vonkajších faktorov: frekvencia prijatia a zložitosť objednávok (a teda čas ich vykonania).

Predmetom teórie radenia je stanovenie vzťahu medzi charakterom toku aplikácií, výkonom samostatného obslužného kanála, počtom kanálov a efektívnosťou služby.

Ako Vlastnosti QS zvážiť:

• priemerné percento žiadostí, ktoré sú zamietnuté a ponechajú systém neobslúžený;
• priemerné prestoje jednotlivých kanálov a systému ako celku;
• priemerná doba čakania vo fronte;
• pravdepodobnosť, že prijatá žiadosť bude okamžite obsluhovaná;
• zákon o distribúcii dĺžky frontu a iné.

Dodávame, že požiadavky (požiadavky) vstupujú do QS náhodne (v náhodných časoch), s bodmi kondenzácie a zriedenia. Obslužný čas každej požiadavky je tiež náhodný, po ktorom je servisný kanál uvoľnený a pripravený splniť ďalšiu požiadavku. Každý QS má v závislosti od počtu kanálov a ich výkonu určitú kapacitu. Priepustnosť SMO možno absolútne(priemerný počet aplikácií obsluhovaných za jednotku času) a príbuzný(priemerný pomer počtu doručených žiadostí k počtu podaných).

3.1 Modely systémov radenia.

Každý QS možno charakterizovať výrazom: (A b c d e f) , kde

a - distribúcia vstupného toku aplikácií;

b - distribúcia výstupného toku aplikácií;

c – konfigurácia servisného mechanizmu;

d – disciplína v rade;

e – čakací blok;

f je kapacita zdroja.

Teraz sa pozrime bližšie na jednotlivé funkcie.

Vstupný prúd aplikácií- počet žiadostí prijatých systémom. Charakterizované intenzitou vstupného toku l.

Výstupný prúd aplikácií– počet aplikácií obsluhovaných systémom. Charakterizované intenzitou výstupného toku m.

konfigurácia systému znamená celkový počet kanálov a servisných uzlov. SMO môže obsahovať:

1. jeden kanál služby (jedna dráha, jeden predajca);
2. jeden kanál služby vrátane viacero sériových uzlov(jedáleň, poliklinika, dopravník);
3. niekoľko podobných kanálov paralelne zapojené služby (čerpacie stanice, infopult, železničná stanica).

Takto možno rozlíšiť jedno- a viackanálové QS.

Na druhej strane, ak sú všetky obslužné kanály v QS obsadené, potom môže pristúpená aplikácia zostať v rade alebo môže opustiť systém (napríklad sporiteľňa a telefónna ústredňa). V tomto prípade hovoríme o systémoch s frontom (čakaním) a systémoch s poruchami.

Otočte sa je súbor aplikácií, ktoré vstúpili do systému na servis a čakajú na servis. Front je charakterizovaný dĺžkou frontu a jeho disciplínou.

Disciplína v rade je pravidlo pre obsluhu požiadaviek z frontu. Medzi hlavné typy frontov patria:

1. PERPPO (kto prv príde, ten prv melie) je najbežnejší typ;
2. POSPPO (posledný príde - prvý melie);
3. SOP (náhodný výber aplikácií) - z databanky.
4. PR - prioritná služba.

Dĺžka frontu možno

• neobmedzený - potom sa hovorí o systéme s čistým očakávaním;
• rovná nule - potom hovoria o systéme s poruchami;
• obmedzená na dĺžku (systém zmiešaného typu).

čakací blok– „kapacita“ systému – celkový počet aplikácií v systéme (vo fronte a v prevádzke). Touto cestou, e=c+d.

Kapacita zdroja ktorý generuje požiadavky na službu, je maximálny počet požiadaviek, ktoré môžu vstúpiť do QS. Napríklad na letisku je zdrojová kapacita obmedzená počtom všetkých existujúcich lietadiel a zdrojová kapacita telefónnej ústredne sa rovná počtu obyvateľov Zeme, t.j. možno ho považovať za neobmedzený.

Počet modelov QS zodpovedá počtu možných kombinácií týchto komponentov.

3.2 Vstupný tok požiadaviek.

S každým časovým úsekom a, a+ T ], priraďme náhodnú premennú X, ktorý sa rovná počtu žiadostí prijatých systémom v danom čase T.

Tok požiadaviek sa nazýva stacionárne, ak distribučný zákon nezávisí od počiatočného bodu intervalu a, ale závisí len od dĺžky daného intervalu T. Napríklad tok žiadostí do telefónnej ústredne počas dňa ( T\u003d 24 hodín) nemožno považovať za stacionárne, ale od 13 do 14 hodín ( T\u003d 60 minút) - môžete.

Tok sa nazýva žiadny následný efekt, ak história toku neovplyvní príjem požiadaviek v budúcnosti, t.j. požiadavky sú na sebe nezávislé.

Tok sa nazýva obyčajný, ak do systému nemôže vstúpiť za veľmi krátky čas viac ako jedna požiadavka. Napríklad tok do kaderníka je bežný, ale nie do matriky. Ale ak ako náhodná veličina X zvážte dvojice žiadostí vstupujúcich do podateľne, potom bude takýto tok obyčajný (t. j. niekedy môže byť mimoriadny tok zredukovaný na obyčajný).

Tok sa nazýva najjednoduchšie, ak je stacionárny, bez následkov a obyčajný.

Hlavná veta. Ak je prietok najjednoduchší, tak r.v. X [ a . a + T] sa rozdeľuje podľa Poissonovho zákona, t.j. .

Dôsledok 1. Najjednoduchšie prúdenie sa nazýva aj Poissonovo prúdenie.

Dôsledok 2. M(X)= M(X [ a , a + T ] )= lT, t.j. počas T lT aplikácie. Preto za jednu jednotku času systém dostane v priemere l aplikácie. Táto hodnota sa nazýva intenzita vstupný prúd.

Zvážte PRÍKLAD .

Štúdio dostane v priemere 3 žiadosti denne. Za predpokladu, že tok je najjednoduchší, nájdite pravdepodobnosť, že počet žiadostí bude v priebehu nasledujúcich dvoch dní aspoň 5.

Riešenie.

Podľa zadania, l=3, T=2 dni, vstupný prúd Poisson, n ³5. pri riešení je vhodné zaviesť opačný dej, ktorý spočíva v tom, že počas čas T bude prijatých menej ako 5 žiadostí. Preto podľa Poissonovho vzorca dostaneme

^

3.3 Stav systému. Matica a graf prechodov.

V náhodnom časovom okamihu QS prechádza z jedného stavu do druhého: mení sa počet obsadených kanálov, počet požiadaviek a front atď. n kanály a dĺžka frontu rovná m, môže byť v jednom z nasledujúcich stavov:

E 0 – všetky kanály sú bezplatné;

E 1 – jeden kanál je obsadený;

E n– všetky kanály sú obsadené;

E n +1 – všetky kanály sú obsadené a jedna požiadavka je vo fronte;

E n + m– všetky kanály a všetky miesta vo fronte sú obsadené.

Podobný systém s poruchami môže byť v stavoch E 0 – E n .

Pre QS s čistým očakávaním existuje nekonečná množina stavov. Touto cestou, stave E n QS v čase t je množstvo n aplikácie (požiadavky), ktoré sú v danom čase v systéme, t.j. n= n(t) - náhodná hodnota, E n (t) sú výsledky tejto náhodnej premennej a P n (t) je pravdepodobnosť, že systém je v stave E n .

Už sme oboznámení so stavom systému. Upozorňujeme, že nie všetky stavy systému sú ekvivalentné. Stav systému je tzv zdroj ak systém môže opustiť tento stav, ale nemôže sa doň vrátiť. Stav systému je tzv izolovaný, ak systém nemôže opustiť tento stav alebo vstúpiť do tohto stavu.

Na vizualizáciu obrazov stavov systému sa používajú diagramy (tzv. prechodové grafy), v ktorých šípky označujú možné prechody systému z jedného stavu do druhého, ako aj pravdepodobnosti takýchto prechodov.

Obrázok 3.1 - graf prechodu

Comp.	E 0	E 1	E 2
E 0	P 0,0	P 0,1	P 0,2
E 1	P 1,0	R 1.1	R 1.2
E 2	R 2,0	R 2.2	R 2.2

Niekedy je tiež vhodné použiť prechodovú maticu. V tomto prípade prvý stĺpec znamená počiatočné stavy systému (aktuálne) a potom sú uvedené pravdepodobnosti prechodu z týchto stavov do iných.

Keďže systém nevyhnutne prejde z jedného

stavu k inému, potom sa súčet pravdepodobností v každom riadku vždy rovná jednej.

3.4 Jednokanálový QS.

3.4.1 Jednokanálový QS s poruchami.

Budeme brať do úvahy systémy, ktoré spĺňajú požiadavky:

(P/E/1):(–/1/¥) . Predpokladajme tiež, že čas obsluhy zákazníka nezávisí od počtu zákazníkov vstupujúcich do systému. Tu a nižšie „P“ znamená, že vstupný tok je rozdelený podľa Poissonovho zákona, t.j. najjednoduchšie „E“ znamená, že výstupný tok je distribuovaný exponenciálne. Aj tu a nižšie sú hlavné vzorce uvedené bez dôkazu.

Pre takýto systém sú možné dva stavy: E 0 - systém je bezplatný a E 1 – systém je zaneprázdnený. Vytvorme prechodovú maticu. Vezmime Dt je nekonečne malé množstvo času. Nech udalosť A spočíva v tom, že v systéme počas doby Dt dostal jednu žiadosť. Udalosť B spočíva v tom, že počas doby Dt bola doručená jedna žiadosť. Udalosť ALE i , k- počas Dt systém prejde zo stavu E i do stavu E k. Pretože l je intenzita vstupného toku, potom počas doby Dt vstupuje do systému v priemere l*Dt požiadavky. Teda pravdepodobnosť prijatia jedného nároku P(A)=l* Dt a pravdepodobnosť opačnej udalosti Р(А)=1-l*Dt.P(B)=F(Dt)= P(b< D t)=1- e - m D t = m Dt- pravdepodobnosť včasného vybavenia požiadavky Dt. Potom A 00 - žiadosť nebude prijatá alebo bude prijatá, ale bude doručená. A 00 \u003d À + A * V. R 00 \u003d 1 - l*Dt. (to sme brali do úvahy (Dt) 2 je nekonečne malá hodnota)

A 01 - žiadosť bude prijatá, ale nebude doručená. A 01 = A * . R 01 = l*Dt.

A 10 - žiadosť bude doručená a nebude žiadna nová. A 10 \u003d B * a. R 10 = m*Dt.

A 11 - žiadosť nebude doručená alebo príde nová, ktorá ešte nebola doručená. A 11 = +V * A. R 01 = 1- m*Dt.

Tak dostaneme prechodovú maticu:

Comp.	E 0	E 1
E 0	1-l * Dt	l * Dt
E 1	m * Dt	1-m * Dt

Pravdepodobnosť výpadku a zlyhania systému.

Nájdime teraz pravdepodobnosť, že systém je v stave E 0 v ktoromkoľvek okamihu t(tie. R 0 ( t) ). Graf funkcií
znázornené na obrázku 3.2.

Asymptota grafu je priamka
.

Samozrejme, od istého bodu t,

1

Obrázok 3.2

Konečne to chápeme
a
, kde R 1 (t) je pravdepodobnosť, že v čase t systém je zaneprázdnený (t. j. je v stave E 1 ).

Je zrejmé, že na začiatku prevádzky QS nebude prebiehajúci proces stacionárny: bude to „prechodný“, nestacionárny režim. Po určitom čase (ktorý závisí od intenzít vstupných a výstupných tokov) tento proces zanikne a systém prejde do stacionárneho, ustáleného stavu prevádzky a pravdepodobnostné charakteristiky už nebudú závisieť od času.

Stacionárny režim prevádzky a faktor zaťaženia systému.

Ak je pravdepodobnosť, že systém je v stave E k, t.j. R k (t), nezávisí od času t, potom povedia, že QS sa zaviedol stacionárny režim práca. Zároveň hodnota
volal faktor zaťaženia systému(alebo znížená hustota toku aplikácií). Potom k pravdepodobnostiam R 0 (t) a R 1 (t) dostaneme nasledujúce vzorce:
,
. Môžete tiež uzavrieť: čím väčší je faktor zaťaženia systému, tým je pravdepodobnejšie, že systém zlyhá (t. j. pravdepodobnosť, že je systém zaneprázdnený).

Autoumyváreň má jednu jednotku na údržbu. Autá prichádzajú v Poissonovej distribúcii s rýchlosťou 5 áut/hod. Priemerný servisný čas na jedno auto je 10 minút. Nájdite pravdepodobnosť, že blížiace sa auto zistí, že systém je zaneprázdnený, ak je QS v stacionárnom režime.

Riešenie. Podľa zadania, l=5, m r = 5/6. Musíme nájsť pravdepodobnosť R 1 je pravdepodobnosť zlyhania systému.
.

3.4.2 Jednokanálové QS s neobmedzenou dĺžkou frontu.

Budeme brať do úvahy systémy, ktoré spĺňajú požiadavky: (Р/Е/1):(d/¥/¥). Systém môže byť v jednom zo stavov E 0 , …, E k, … Analýza ukazuje, že po určitom čase takýto systém začne pracovať v stacionárnom režime, ak intenzita výstupného toku prekročí intenzitu vstupného toku (t. j. faktor zaťaženia systému je menší ako jedna). Ak vezmeme do úvahy túto podmienku, dostaneme sústavu rovníc

riešenie, ktoré zistíme, že . Teda za predpokladu, že r<1, получим
nakoniec
a
je pravdepodobnosť, že QS je v stave E k v náhodnom časovom bode.

Priemerné charakteristiky systému.

V dôsledku nerovnomerného prijímania požiadaviek v systéme a kolísania servisného času sa v systéme vytvára rad. Pre takýto systém môžete preskúmať:

• n – počet požiadaviek v QS (vo fronte av prevádzke);
• v - dĺžka frontu;
• w – čas čakania na spustenie služby;
• w 0 je celkový čas strávený v systéme.

Budeme mať záujem priemerné vlastnosti(t. j. vezmeme matematické očakávania uvažovaných náhodných premenných a zapamätáme si to r<1).

je priemerný počet aplikácií v systéme.

je priemerná dĺžka frontu.

je priemerná doba čakania na začiatok služby, t.j. čakacia doba v rade.

- priemerný čas, ktorý aplikácia strávi v systéme - vo fronte a na obsluhu.

V autoumyvárni je jeden blok pre obsluhu a je tam miesto pre rad. Autá prichádzajú v Poissonovej distribúcii s rýchlosťou 5 áut/hod. Priemerný servisný čas na jedno auto je 10 minút. Nájdite všetky priemerné charakteristiky QS.

Riešenie. l=5, m=60min/10min = 6. Faktor zaťaženia r = 5/6. Potom priemerný počet áut v systéme
, priemerná dĺžka frontu
, priemerný čas čakania na spustenie služby
hodiny = 50 minút a nakoniec priemerný čas strávený v systéme
hodina.

3.4.3 Jednokanálové QS zmiešaného typu.

Predpokladajme, že dĺžka frontu je m požiadavky. Potom pre akékoľvek s£ m, pravdepodobnosť nájdenia QS v štáte E 1+ s, sa vypočíta podľa vzorca
, t.j. jedna žiadosť sa podáva a druhá s aplikácie sú v poradí.

Pravdepodobnosť výpadku systému je
,

a pravdepodobnosť zlyhania systému je
.

Pre každý sú uvedené tri jednokanálové systémy l=5, m =6. Ale prvý systém je s poruchami, druhý je s čistým čakaním a tretí je s obmedzenou dĺžkou frontu, m=2. Nájdite a porovnajte pravdepodobnosť prestojov týchto troch systémov.

Riešenie. Pre všetky systémy faktor zaťaženia r= 5/6. Pre systém s poruchami
. Pre systém s čistým očakávaním
. Pre systém s obmedzenou dĺžkou frontu
. Záver je zrejmý: čím viac aplikácií je vo fronte, tým menšia je pravdepodobnosť výpadku systému.

3.5 Viackanálové QS.

3.5.1 Viackanálové QS s poruchami.

Budeme uvažovať o systémoch (Р/Е/s):(-/s/¥) za predpokladu, že čas obsluhy nezávisí od vstupného toku a všetky linky pracujú nezávisle. Viackanálové systémy možno okrem faktora zaťaženia charakterizovať aj koeficientom
, kde s– počet servisných kanálov. Pri skúmaní viackanálového QS získame nasledujúce vzorce (Erlangove vzorce) pre pravdepodobnosť, že systém bude v stave E k v náhodnom čase:

, k = 0, 1, …

nákladová funkcia.

Rovnako ako u jednokanálových systémov, zvýšenie faktora zaťaženia vedie k zvýšeniu pravdepodobnosti zlyhania systému. Na druhej strane zvýšenie počtu servisných liniek vedie k zvýšeniu pravdepodobnosti výpadku systému alebo jednotlivých kanálov. Preto je potrebné nájsť optimálny počet obslužných kanálov pre tento QS. Priemerný počet bezplatných servisných liniek zistíte podľa vzorca
. Predstavme si C( s) – nákladová funkcia QS v závislosti od s 1 – náklady na jedno odmietnutie (pokuta za nevybavenú žiadosť) a od s 2 - náklady na prestoje jednej linky za jednotku času.

Ak chcete nájsť optimálnu možnosť, musíte nájsť (a to sa dá urobiť) minimálnu hodnotu nákladovej funkcie: OD(s) = s 1* l * p s +c 2*, ktorej graf je znázornený na obrázku 3.3:

Obrázok 3.3

Hľadanie minimálnej hodnoty nákladovej funkcie spočíva v tom, že najprv nájdeme jej hodnoty s = 1, potom pre s =2, potom pre s =3 atď. až v určitom kroku hodnota funkcie С( s) nebude väčšia ako predchádzajúca. To znamená, že funkcia dosiahla svoje minimum a začala rásť. Odpoveďou je počet servisných kanálov (hodnota s), pre ktoré je nákladová funkcia minimálna.

PRÍKLAD .

Koľko servisných liniek by malo obsahovať QS s poruchami, ak l\u003d 2 reb / ​​hod., m\u003d 1reb / ​​hodina, pokuta za každé zlyhanie je 7 000 rubľov, náklady na prestoje na jednom riadku sú 2 000 rubľov. za hodinu?

Riešenie. r = 2/1=2. s 1 =7, s 2 =2.

Predpokladajme, že QS má dva servisné kanály, t.j. s =2. Potom
. v dôsledku toho C(2) = c 1 *l*p 2 +c 2 *(2- y*(1-r 2 )) = =7*2*0.4+2*(2-2*0.6)=7.2.

Predstierajme to s =3. Potom
, C(3) = c 1 *l*p 3 +c 2 *
=5.79.

Predpokladajme, že existujú štyri kanály, t.j. s =4. Potom
,
, C(4) = c 1 *l*p 4 +c 2 *
=5.71.

Predpokladajme, že QS má päť obslužných kanálov, t.j. s =5. Potom
, C(5) = 6,7 - viac ako predchádzajúca hodnota. Optimálny počet servisných kanálov je preto štyri.

3.5.2 Viackanálové QS s radom.

Budeme uvažovať o systémoch (Р/Е/s):(d/d+s/¥) za predpokladu, že čas obsluhy nezávisí od vstupného toku a všetky linky pracujú nezávisle. Povieme, že systém je nainštalovaný stacionárna prevádzka, ak je priemerný počet prichádzajúcich reklamácií menší ako priemerný počet doručených reklamácií na všetkých linkách systému, t.j. l

P(w>0) je pravdepodobnosť čakania na spustenie služby,
.

Posledná charakteristika umožňuje vyriešiť problém určenia optimálneho počtu obslužných kanálov takým spôsobom, že pravdepodobnosť čakania na začiatok služby je menšia ako daný počet. Na to stačí vypočítať pravdepodobnosť očakávania postupne pre s =1, s =2, s=3 atď.

PRÍKLAD .

SMO - ambulancia malého mikrodistriktu. l= 3 hovory za hodinu a m= 4 hovory za hodinu pre jeden tím. Koľko posádok musí byť na stanici, aby pravdepodobnosť čakania na výjazd bola menšia ako 0,01?

Riešenie. Faktor zaťaženia systému r = 0,75. Predpokladajme, že sú k dispozícii dva tímy. Nájdite pravdepodobnosť čakania na spustenie služby s =2.
,
.

Predpokladajme, že sú tri brigády, t.j. s=3. Podľa vzorcov to dostaneme R 0 =8/17, P(w>0)=0.04>0.01 .

Predpokladajme, že na stanici sú štyri posádky, t.j. s=4. Potom to dostaneme R 0 =416/881, P(w>0)=0.0077<0.01 . Na stanici by preto mali byť štyri brigády.

3.6 Otázky na sebaovládanie

1. Predmet a úlohy teórie radenia.
2. QS, ich modely a označenia.
3. Vstupný tok požiadaviek. Intenzita vstupného prúdu.
4. Stav systému. Matica a graf prechodov.
5. Jednokanálový QS s poruchami.
6. Jednokanálové QS s frontom. Charakteristika.
7. Stacionárny režim prevádzky. Faktor zaťaženia systému.
8. Viackanálové QS s poruchami.
9. Optimalizácia nákladovej funkcie.
10. Viackanálové QS s frontom. Charakteristika.

3.7 Cvičenia na samostatnú prácu

1. Občerstvenie na čerpacej stanici má jeden pult. Autá prichádzajú podľa Poissonovho rozdelenia, v priemere 2 autá za 5 minút. Na dokončenie objednávky stačí v priemere 1,5 minúty, hoci trvanie služby je rozdelené podľa exponenciálneho zákona. Nájdite: a) pravdepodobnosť nečinnosti prerušenia; b) priemerný výkon; c) pravdepodobnosť, že počet prichádzajúcich áut bude aspoň 10.
2. Röntgen vám umožní vyšetriť v priemere 7 osôb za hodinu. Intenzita návštevnosti je 5 osôb za hodinu. Za predpokladu stacionárnej prevádzky určite priemerné charakteristiky.
3. Servisný čas v QS sa riadi exponenciálnym zákonom,
   m = 7 požiadaviek za hodinu. Nájdite pravdepodobnosť, že a) servisný čas je medzi 3 a 30 minútami; b) reklamácia bude doručená do jednej hodiny. Použite tabuľku hodnôt funkcií e X .
4. V riečnom prístave je jedno kotvisko, intenzita vstupného prúdu je 5 plavidiel denne. Intenzita nakládky a vykládky je 6 plavidiel za deň. Berúc do úvahy stacionárny režim prevádzky, určite všetky priemerné charakteristiky systému.
5. l=3, m=2, pokuta za každé zlyhanie je 5 a náklady na prestoje na linku sú 2?
6. Aký je optimálny počet servisných kanálov, ktoré by mal mať QS, ak l=3, m = 1, pokuta za každé zlyhanie je 7 a náklady na prestoje na linku sú 3?
7. Aký je optimálny počet servisných kanálov, ktoré by mal mať QS, ak l=4, m=2, pokuta za každé zlyhanie je 5 a náklady na prestoje na linku sú 1?
8. Určte počet vzletových a pristávacích dráh pre lietadlá za predpokladu, že pravdepodobnosť čakania musí byť menšia ako 0,05. Intenzita vstupného toku je zároveň 27 lietadiel denne a intenzita ich obsluhy je 30 lietadiel denne.
9. Koľko ekvivalentných nezávislých dopravníkových liniek by mala mať dielňa, aby bol zabezpečený pracovný rytmus, pri ktorom musí byť pravdepodobnosť čakania na spracovanie produktov menšia ako 0,03 (každý produkt vyrába jedna linka). Je známe, že intenzita príjmu objednávok je 30 produktov za hodinu a intenzita spracovania produktu v jednej linke je 36 produktov za hodinu.
10. Spojitá náhodná premenná X je rozdelená podľa exponenciálneho zákona s parametrom l=5. Nájdite distribučnú funkciu, charakteristiku a pravdepodobnosť zasiahnutia r.v. X v rozsahu od 0,17 do 0,28.
11. Priemerný počet hovorov prichádzajúcich do PBX za jednu minútu je 3. Za predpokladu, že tok je Poisson, nájdite pravdepodobnosť, že za 2 minúty budú: a) dva hovory; b) menej ako dva hovory; c) najmenej dve výzvy.
12. V krabici je 17 dielov, z toho 4 chybné. Montážnik náhodne vyžrebuje 5 kusov. Nájdite pravdepodobnosť, že a) všetky extrahované časti sú vysokej kvality; b) medzi vyťaženými časťami 3 chybné.
13. Koľko kanálov by mal mať QS s poruchami, ak l\u003d 2 reb / ​​hod., m\u003d 1reb / ​​hodina, pokuta za každé zlyhanie je 8 000 rubľov, náklady na prestoje na jednom riadku sú 2 000 rubľov. za hodinu?

1. Jednokanálový QS s poruchami.

Príklad. Nech jednokanálový QS s poruchami predstavuje jednu dennú čerpaciu stanicu (OD) na umývanie áut. Aplikácia – auto, ktoré prišlo v čase, keď je pošta obsadená – je odmietnutá.

Prietok vozidla = 1,0 (vozidlo za hodinu).

Priemerný servisný čas je 1,8 hodiny.

Tok áut a tok služieb sú najjednoduchšie.

Vyžaduje sa definovanie v medzných hodnotách v ustálenom stave:

Relatívna šírka pásma q;

Absolútna šírka pásma ALE ;

Pravdepodobnosť zlyhania P otvorené.

Treba porovnávať skutočné Priepustnosť QS s nominálny, čo by bolo, keby každý vozeň slúžil presne 1,8 hodiny a vozne by išli za sebou bez prestávky.

2. Jednokanálové QS s čakaním

Charakteristika systému

Ø SMO má jeden kanál.

Ø Prichádzajúci tok požiadaviek na službu je najjednoduchší tok s intenzitou.

Ø Intenzita toku služieb sa rovná m (t. j. v priemere nepretržite obsadený kanál vydá m obsluhovaných požiadaviek).

Ø Trvanie služby je náhodná premenná, ktorá podlieha zákonu o exponenciálnom rozdelení.

Ø Tok služieb je najjednoduchší Poissonov tok udalostí.

Ø Požiadavka prijatá v momente, keď je kanál obsadený, sa dostane do frontu a čaká na službu.

Stavový graf

Stavy QS majú nasledujúci výklad:

S 0 - "kanál je voľný";

S 1 - "kanál je zaneprázdnený" (neexistuje žiadny front);

S 2 - "kanál je zaneprázdnený" (jedna aplikácia je vo fronte);

…………………………………………………….

sn- "kanál je zaneprázdnený" ( n-1 prihláška je vo fronte);

SN- "kanál je zaneprázdnený" ( N- 1 prihláška je v poradí).

Stacionárny proces v tomto systéme je opísaný nasledujúcim systémom algebraických rovníc:

Riešenie sústavy rovníc je:

3. Jednokanálový QS s obmedzeným frontom.

Dĺžka fronty :( N - 1)

Vlastnosti systému:

1. Pravdepodobnosť odmietnutia služby systému:

2. Relatívna priepustnosť systému:

3. Absolútna priepustnosť systému:

4. Priemerný počet aplikácií v systéme:

5. Priemerný čas zotrvania aplikácie v systéme:

6. Priemerná dĺžka pobytu klienta (aplikácie) v rade:

7. Priemerný počet aplikácií (klientov) vo fronte (dĺžka frontu):

Príklad.

Špecializovaný diagnostický post je jednokanálový QS.

Počet parkovísk pre autá čakajúce na diagnostiku je obmedzený a rovná sa 3 [( N-1) = 3]. Ak sú všetky parkoviská obsadené, t.j. v rade sú už tri autá, ďalšie auto, ktoré prišlo na diagnostiku, sa do servisného radu nedostane.

Tok áut prichádzajúcich na diagnostiku je rozdelený podľa Poissonovho zákona a má intenzitu 0,85 (auta za hodinu).

Čas diagnostiky auta je rozdelený podľa exponenciálneho zákona a rovná sa v priemere 1,05 hodiny.

4. Jednokanálové QS s čakaním

bez obmedzenia dĺžky frontu

Podmienky fungovania QS zostávajú nezmenené, berúc do úvahy skutočnosť, že N .

Stacionárny režim prevádzky takéhoto QS existuje:

pre hocikoho n= 0, 1, 2, ... a kedy λ < μ .

Systém rovníc popisujúcich činnosť QS:

Riešenie sústavy rovníc má tvar:

2. Priemerná dĺžka pobytu klienta v systéme:

3. Priemerný počet klientov v poradí služieb:

4. Priemerná dĺžka pobytu klienta v rade:

Príklad.

Špecializovaný diagnostický post je jednokanálový QS. Počet parkovísk pre autá čakajúce na diagnostiku nie je obmedzený. Tok áut prichádzajúcich na diagnostiku je rozdelený podľa Poissonovho zákona a má intenzitu λ = 0,85 (aut za hodinu). Čas diagnostiky auta je rozdelený podľa exponenciálneho zákona a rovná sa v priemere 1,05 hodiny.

Je potrebné určiť pravdepodobnostné charakteristiky diagnostického stanovišťa pracujúceho v stacionárnom režime.

V dôsledku riešenia problému je potrebné určiť konečné hodnoty nasledujúcich pravdepodobnostných charakteristík:

ü pravdepodobnosti stavov systému (diagnostický post);

ü priemerný počet áut v systéme (v prevádzke a v rade);

ü priemerné trvanie zotrvania vozidla v systéme (v prevádzke a v rade);

ü priemerný počet áut v servisnom rade;

priemerný čas, ktorý auto strávi v rade.

1. Parameter obslužného prúdu a znížená intenzita automobilového prúdu:

μ = 0,952; ψ = 0,893.

2. Obmedzujúce pravdepodobnosti stavu systému:

P 0 (t) určuje podiel času, počas ktorého je diagnostický príspevok nútený byť neaktívny (nečinný). V príklade je tento podiel 10,7 %, od r P 0 (t) = 0,107.

3. Priemerný počet áut v systéme

(v prevádzke a v rade):

4. Priemerná dĺžka pobytu klienta v systéme

5. Priemerný počet áut v servisnom rade:

6. Priemerná dĺžka pobytu auta v rade:

7. Relatívna priepustnosť systému:

q= 1, t.j. každá požiadavka, ktorá vstúpi do systému, bude obsluhovaná.

8. Absolútna šírka pásma:

Prezentačný návrh materiálu je uvedený v súbore "TMO"

Otázky a úlohy

(podľa Afanasieva M.Yu.)

Otázka 1. Jeden pracovník udržiava tridsať tkáčskych stavov a zabezpečuje ich spustenie po pretrhnutí nite. Model takéhoto systému radenia možno charakterizovať ako:

1) viackanálový jednofázový s obmedzeným počtom obyvateľov;

2) jednokanálový jednofázový s neobmedzeným počtom obyvateľov;

3) jednokanálový viacfázový s obmedzeným počtom obyvateľov;

4) jednokanálový jednofázový s obmedzeným počtom obyvateľov;

5) viackanálový jednofázový s neobmedzeným počtom obyvateľov.

Otázka 2. V teórii radenia sa na opísanie najjednoduchšieho toku požiadaviek prichádzajúcich na vstup systému používa rozdelenie pravdepodobnosti:

1) normálne;

2) exponenciálny;

3) Poisson;

4) binomický;

Otázka 3. V teórii radenia sa predpokladá, že počet zákazníkov v populácii je:

1) fixné alebo variabilné;

2) obmedzené alebo neobmedzené;

3) známy alebo neznámy;

4) náhodné alebo deterministické;

5) nič z vyššie uvedeného nie je pravda.

Otázka 4. Dva hlavné parametre, ktoré určujú konfiguráciu systému radenia sú:

1) rýchlosť príjmu a rýchlosť služby;

2) dĺžka frontu a pravidlo služby;

3) rozdelenie času medzi aplikácie a rozdelenie času služby;

4) počet kanálov a počet fáz služby;

5) nič z vyššie uvedeného nie je pravda.

Otázka 5. V teórii radenia sa pravdepodobnostná distribúcia zvyčajne používa na opis času stráveného obsluhou požiadaviek:

1) normálne;

2) exponenciálny;

3) Poisson;

4) binomický;

5) nič z vyššie uvedeného nie je pravda.

Otázka 6. Opravy pokazených počítačov na Ekonomickej fakulte vykonávajú traja špecialisti pracujúci súčasne a nezávisle na sebe. Model takéhoto systému radenia možno charakterizovať ako:

1) viackanálový s obmedzeným počtom obyvateľov;

2) jednokanálový s neobmedzeným počtom obyvateľov;

3) jednokanálový s obmedzeným počtom obyvateľov;

4) jednokanálový s obmedzeným frontom;

5) viackanálový s neobmedzeným počtom obyvateľov.

Odpovede na otázky: 1 -4, 2 - 3, 3 -2, 4 -4, 5 -2, 6 -1.

PLÁNOVANIE A RIADENIE SIETE

Systémy plánovania a riadenia siete (SPU) sú špeciálnym druhom organizovaných riadiacich systémov určených na reguláciu produkčných činností tímov. Rovnako ako v iných systémoch tejto triedy, aj v systémoch STC je „objektom kontroly“ tím výkonných pracovníkov, ktorí majú určité zdroje: ľudské, materiálne, finančné. Tieto systémy však majú množstvo znakov, keďže ich metodologickým základom sú metódy operačného výskumu, teória orientovaných grafov a niektoré časti teórie pravdepodobnosti a matematickej štatistiky. Nevyhnutnou vlastnosťou systému plánovania a riadenia je aj schopnosť posúdiť aktuálny stav, predvídať ďalší priebeh prác a tým ovplyvniť priebeh prípravy a výroby tak, aby bol celý rozsah prác dokončený včas a s čo najnižšími nákladmi. .

V súčasnosti sú modely a metódy STC široko používané pri plánovaní a realizácii stavebných a inštalačných prác, plánovaní obchodných aktivít, zostavovaní účtovných výkazov, vypracovaní obchodného a finančného plánu atď.

Rozsah použitia ŠPM je veľmi široký: od úloh súvisiacich s činnosťou jednotlivcov až po projekty, do ktorých sú zapojené stovky organizácií a desaťtisíce ľudí (napríklad rozvoj a vytvorenie veľkého územno-priemyselného komplexu).

Aby bolo možné zostaviť pracovný plán na realizáciu veľkých a zložitých projektov, pozostávajúcich z tisícok samostatných štúdií a operácií, je potrebné ho opísať pomocou nejakého matematického modelu. Takýmto nástrojom na popis projektov (komplexov) je sieťový model.