Matematické modely radiacich systémov na riešenie ekonomických problémov. · Pred začatím práce sa uistite, že nie je viditeľné poškodenie zariadenia a káblov

Kreslenie 0 - 2 Toky udalostí (a) a najjednoduchší tok (b)

10.5.2.1. Stacionárnosť

Tok sa nazýva stacionárny , ak je pravdepodobnosť určitého počtu udalostí vyskytujúcich sa v elementárnom časovom úseku 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.

Stacionárny tok znamená jeho rovnomernosť v čase; pravdepodobnostné charakteristiky takéhoto toku sa nemenia v závislosti od času. 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 kondenzácie a riedky. Je dôležité, aby pri stacionárnom toku tieto kondenzácie a zriedenia nemali pravidelný charakter a priemerný počet udalostí spadajúcich do jedného časového obdobia 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 medzi 12. a 13. hodinou možno považovať za pevnú linku. 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 rozšírenie tejto oblasti do nekonečna je len vhodná technika používaná na tento účel. zjednodušenia.

10.5.2.2. Žiadny následný efekt

Prúd udalostí sa nazýva prúd bez následkov , ak pre akékoľvek neprekrývajúce sa časové obdobia 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 dve sekcie).

V takýchto prúdoch sa udalosti, ktoré tvoria prúd, objavujú v po sebe nasledujúcich časových okamihoch, 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é určovali príchod jednotlivého cestujúceho v danom momente 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ásledkov.

Zoberme si napríklad tok nákladných vlakov pozdĺž železničnej trate. Ak kvôli bezpečnostným podmienkam nemôžu ísť za sebou častejšie ako v intervaloch t 0 , potom existuje závislosť medzi udalosťami v toku a podmienka žiadneho následného účinku je porušená. Ak však interval t 0 je malý v porovnaní s priemerným intervalom medzi vlakmi, potom je takéto porušenie bezvýznamné.

Kreslenie 0 - 3 Poissonovo rozdelenie

Zvážte na osi t najjednoduchší prúd 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 toku; Poďme 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žme od začiatku intervalu T (body t 0) segment t a nájdite pravdepodobnosť, že interval T bude toho menej t . K tomu je potrebné, aby pre úsek dĺžky t, susediaci s bodom t 0 , aspoň jeden zásah do udalosti toku. Vypočítajme si to pravdepodobnosť F(t) prostredníctvom pravdepodobnosti opačnej udalosti (na sekciu t nezasiahne žiadne udalosti toku):

F(t) = 1 - P 0

Pravdepodobnosť P 0 zistíme zo 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 ). Množstvo λ sa nazýva parameter demonštratívne právo.

Obrázok 0 - 4 Exponenciálne rozdelenie

Poďme nájsť číselné charakteristiky náhodnej premennej T- matematické očakávanie (priemerná hodnota) M[t]= mt , a rozptyl Dt. Máme

( 0-5)

(integrácia po častiach).

Rozptyl hodnoty T je:

(0-6)

Zobratím druhej odmocniny rozptylu nájdeme smerodajnú odchýlku náhodnej premennej T.

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

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

Príklad SMO-1 .

Ako príklad si uveďme bankový systém, ktorý funguje v reálnom čase a obsluhuje veľké množstvo klientov. Počas špičky tvoria požiadavky bankových pokladníkov pracujúcich s klientmi Poissonov tok a prichádzajú v priemere dve za 1 s (λ = 2) Tok pozostáva z požiadaviek, ktoré prichádzajú s intenzitou 2 požiadavky za sekundu.

Vypočítajme pravdepodobnosť P ( m) vzhľad m správy za 1 s. Keďže λ = 2, potom z predchádzajúceho vzorca máme

Nahradením m = 0, 1, 2, 3, dostaneme nasledujúce hodnoty (s presnosťou na štyridesatinné miesta):

Obrázok 0 - 5 Príklad jednoduchého toku

Je možné prijať viac ako 9 správ za 1 sekundu, ale pravdepodobnosť je veľmi nízka (asi 0,000046).

Výsledná distribúcia môže byť prezentovaná vo forme histogramu (zobrazeného na obrázku).

Príklad SMO-2.

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

Nech existuje zariadenie, ktoré dokáže spracovať tri správy za 1 s (µ=3). Priemerne sa prijmú dve správy za 1s a v súlade s 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 % bude doručených s určitým oneskorením. Ako vidíte, oneskorenie spracovania jednej správy o čas dlhší ako čas spracovania 3 správ sa vyskytuje len zriedka. Doba spracovania 1 správy je v priemere 1/3 s. Preto bude oneskorenie viac ako 1 s zriedkavým javom, čo je pre väčšinu systémov celkom prijateľné.

Príklad SMO- 3

· Ak je pokladník zaneprázdnený 80 % svojho pracovného času a zvyšok času trávi čakaním na zákazníkov, potom ho možno 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. za 1 s sa prenesie maximálne 2400/8 symbolov a budujeme systém, v ktorom je celkové množstvo dát 12 000 symbolov odosielané z rôznych zariadení cez komunikačný kanál za minútu najväčšieho zaťaženia (vrátane synchronizácie, symbolov konca správ, ovládania atď.), potom sa miera využitia zariadenia komunikačného kanála počas tejto minúty rovná

· Ak nástroj na prístup k súborom vykoná 9 000 prístupov k súborom počas rušnej hodiny a priemerný čas na jeden prístup je 300 ms, potom rýchlosť využitia hardvéru prístupového nástroja je

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

Pomocou predchádzajúceho vzorca môžete vytvoriť tabuľky hodnôt Poissonovej funkcie, z ktorých môžete určiť pravdepodobnosť príchodum alebo viac správ v danom časovom období. Napríklad, ak je v priemere 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

ρ ≤ 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 sekundu 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 úlohy

Ak správy prichádzajú do zariadenia náhodne, zariadenie strávi časť svojho času spracovaním alebo obsluhou každej správy, čo vedie k vytváraniu radov. Na uvoľnenie pokladníka a jeho počítača (terminálu) čaká v banke rad. 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ť na všetkých úzkych miestach v systéme.

Čí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úť uspokojivo fungujúci systém s koeficientom využitia ρ = 0,7, ale koeficient presahujúci ρ > 0,9 môže viesť k zhoršeniu kvality 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é.

Faktor využitia zariadenia sa rovná pomeru zaťaženia zariadenia k maximálnemu zaťaženiu, ktoré toto zariadenie znesie, alebo sa rovná pomeru času, keď je zariadenie obsadené, k celkovému času jeho prevádzky.

Pri navrhovaní systému je bežné odhadnúť faktor využitia pre rôzne typy zariadení; príslušné príklady budú uvedené v nasledujúcich 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 tieto typy otázok možno odpovedať pomocou teórie radenia.

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

Pre QS sú toky udalostí toky aplikácií, toky „obslužných“ aplikácií 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 viac ťažkopádne aparatúry, priviesť ju k analytickým vzorcom 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, keď je proces vyskytujúci sa v QS odlišný od markovovského, pomocou ktorého možno približne posúdiť výkonové charakteristiky QS. Je potrebné poznamenať, že čím je QS komplexnejší, čím viac obslužných kanálov má, tým presnejšie sú približné vzorce získané pomocou Markovovej teórie. Okrem toho v mnohých prípadoch na prijímanie informovaných rozhodnutí o riadení prevádzky QS nie je potrebná presná znalosť všetkých jeho charakteristík, často postačujú len približné, približné znalosti.

QS sú rozdelené do systémov s:

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

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

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

· objednané (žiadosti sa spracúvajú v poradí, v akom boli prijaté),

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

· naukladané (posledná požiadavka sa vyberie ako prvá z frontu).

· Priorita

o so statickou prioritou

o s dynamickou prioritou

(v druhom prípade skôr tet sa môže napríklad zvyšovať s dĺžkou čakania na žiadosť).

Systémy frontu 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 čase, keď nie sú k dispozícii žiadne voľné kanály, dostane do radu a „trpezlivo“ čaká, kým bude kanál dostupný a prijme ho do služby. Každá žiadosť prijatá SOT bude skôr či neskôr vybavená.

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

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

· čas, ktorý aplikácia strávila vo fronte (po určitej dobe zotrvania v rade aplikácia opustí front a systém s obmedzenou čakacou dobou opustí),

· celkový čas zotrvania aplikácie v SOT

atď.

V závislosti od typu QS môžu byť pri hodnotení jeho účinnosti použité 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 priepustnosť 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ť QS je priemerný podiel prijatých žiadostí obsluhovaných systémom (pomer priemerného počtu žiadostí obsluhovaných systémom za jednotku času k priemernému počtu žiadostí prijatých počas tohto času).

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

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

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

atď.

Úlohy s očakávaním majú mierne odlišné vlastnosti. Je zrejmé, že pre QS s neobmedzeným čakaním stráca absolútna aj relatívna priepustnosť svoj význam, pretože každá prijatá požiadavka je skoráalebo bude doručená neskôr. 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, počas ktorého aplikácia zostáva 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 toku aplikáciíλ , výkonnosť každého kanála (priemerný počet požiadaviek μ obsluhovaných kanálom za jednotku času), podmienky na vytvorenie radu (obmedzenia, ak existujú).

V závislosti od hodnôt týchto parametrov sú vyjadrené výkonnostné charakteristiky QS.

10.6.4. Vzorce na výpočet charakteristík QS pre prípad servisu 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 bodov pripojených k viacbodovému komunikačnému kanálu. Podobne sa na čerpacích staniciach tvoria rady áut. Ak však existuje viac ako jeden servisný vstup, máme rad s mnohými zariadeniami a analýza sa stáva zložitejšou.

Zoberme si prípad najjednoduchšieho toku servisných požiadaviek.

Účelom 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ž vhodné odhadnúť, ako často rad 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 zodpovedajúcich 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 návrhu výpočtového systému sa väčšina frontov tohto typu počíta pomocou daných vzorcov. variačný koeficient servisného času

Vzorec Khinchin-Polacek sa používa na výpočet dĺžky frontu pri navrhovaní informačných systémov. Používa sa v prípade exponenciálneho rozdelenia času príchodu pre ľubovoľné rozdelenie času obsluhy a akúkoľvek kontrolnú disciplínu, pokiaľ voľba nasledujúcej správy na obsluhu nezávisí od času obsluhy.

Pri navrhovaní systémov sa vyskytujú situácie, keď vznikajú fronty, keď disciplína riadenia nepochybne závisí od času obsluhy. Napríklad v niektorých prípadoch môžeme vybrať kratšie správy pre prioritnú službu, aby sme dosiahli nižší priemerný čas služby. Pri ovládaní komunikačnej linky môžete 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. Časy údržby rovné konštantnej hodnote sú zriedkavé. Dokonca ani čas prístupu na pevný disk nie je konštantný kvôli rôznym polohám 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 s pevnou dĺžkou.

Na druhej strane nie je rozptyl servisného času taký veľký ako pri jeho ľubovoľnom alebo exponenciálnom rozložení, t.j.σs málokedy dosahuje hodnotyts. Tento prípad sa niekedy považuje za „najhorší prípad“, a preto používajú vzorce týkajúce sa exponenciálneho rozdelenia servisných časov.Takýto výpočet môže poskytnúť mierne nafúknuté veľkosti frontov a čakacích dôb v nich, ale táto chyba aspoň nie je nebezpečná.

Exponenciálne rozloženie servisných časov samozrejme nie je v skutočnosti tým najhorším prípadom. Ak sa však ukáže, že servisné časy získané z výpočtov v radení sú distribuované horšie ako exponenciálne rozdelené časy, je to často varovný signál pre projektanta. Ak je štandardná odchýlka väčšia ako priemer, potom je zvyčajne potrebné upraviť 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 každého typu je rovnaký. Smerodajná odchýlka uvedených časov je o niečo vyššia ako ich priemer. Hodnota posledného servisného času je oveľa vyššia ako ostatné. To spôsobí, že správy zostanú vo fronte podstatne dlhšie, ako keby boli servisné časy rádovo rovnaké. V tomto prípade sa pri navrhovaní odporúča prijať opatrenia na zníženie dĺžky frontu. Napríklad, ak tieto čísla súvisia s dĺžkami správ, potom môže byť užitočné rozdeliť veľmi dlhé správy na časti.

10.6.6. Príklad výpočtu

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

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

Ú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á času, keď je obsadený. Ak λ je počet zákazníkov počas špičky, potom ρ pre pokladníka sa rovná

Predpokladajme, že v špičke 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 pokladničnom riadku leží medzi 1,88 a 3,0 v závislosti od štandardnej odchýlky pre ts .

Predpokladajme, že meranie štandardnej 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, t.j. v priemere budú pri pokladni čakať dvaja klienti.

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 vypočítané pomocou Khinchin-Polacekovho vzorca.

10.6.7. Faktor zisku

Analýzou kriviek zobrazených na obrázkoch vidíme, že keď je zariadenie obsluhujúce front využité 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 navrhovaní systémov prenosu dát. Ak navrhujeme systém s viac ako 80% vyťažením hardvéru, potom mierny nárast prevádzky môže spôsobiť prudký pokles výkonu systému alebo dokonca jeho pád.

Zvýšenie prichádzajúcej návštevnosti o malé číslo 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 miera využitia hardvéru 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í má za následok 25-násobné zvýšenie veľkosti frontu v porovnaní s prípadom 50% využitia zariadenia.

Podobne sa zvyšuje aj čas strávený v rade

Pri exponenciálne rozloženom čase obsluhy má táto hodnota hodnotu 4 t s 2 pre faktor využitia zariadenia rovný 50 % a 100 t s 2 pre koeficient 90 %, teda opäť 25-krát horšie.

Navyše, pre nízke miery využitia zariadení je vplyv zmien σs na veľkosť frontu zanedbateľný. Avšak pre veľké koeficienty je 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 týkajúceho sa exponenciality rozdelenia tsje najvýraznejší pri veľkých hodnotách ρ. Navyše, ak sa servisný čas 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.

Markov náhodný proces s diskrétnymi stavmi a spojitým časom, o ktorom sme hovorili v predchádzajúcej prednáške, prebieha v systémoch radenia (QS).

Systémy radenia – ide o systémy, ktoré prijímajú požiadavky na službu v náhodných časoch a prijaté požiadavky sú obsluhované pomocou servisných kanálov, ktoré má systém k dispozícii.

Príklady systémov radenia zahŕňajú:

• hotovostné zúčtovacie jednotky v bankách a podnikoch;
• osobné počítače obsluhujúce prichádzajúce aplikácie alebo požiadavky na riešenie určitých problémov;
• autoservisy; čerpacia stanica;
• audítorské firmy;
• oddelenia daňovej kontroly zodpovedné za prijímanie a overovanie aktuálnych výkazov podnikov;
• telefónne ústredne a pod.

	Uzly	Požiadavky
NEMOCNICA	sanitári	pacientov
Výroba
LETISKO	Výjazdy na pristávacie dráhy Registračné body	Cestujúci

Zoberme si operačný diagram QS (obr. 1). Systém pozostáva z generátora požiadaviek, dispečera a servisnej jednotky, jednotky poruchovej evidencie (terminátor, ničiteľ objednávok). Vo všeobecnosti môže mať obslužný uzol niekoľko obslužných kanálov.

Ryža. 1

1. Generátor aplikácií – požiadavky na generovanie objektov: ulica, dielňa s inštalovanými jednotkami. Vstup je tok aplikácií(tok zákazníkov do predajne, tok pokazených jednotiek (strojov, strojov) na opravy, tok návštevníkov do šatníka, tok áut k čerpacej stanici a pod.).
2. Dispečer – osoba alebo zariadenie, ktoré vie, čo robiť s aplikáciou. Uzol, ktorý reguluje a usmerňuje požiadavky na servisné kanály. Dispečer:

• prijíma žiadosti;
• vytvorí rad, ak sú všetky kanály obsadené;
• nasmeruje ich na servisné kanály, ak existujú bezplatné;
• odmieta žiadosti (z rôznych dôvodov);
• prijíma informácie od servisného uzla o voľných kanáloch;
• monitoruje prevádzkový čas systému.

1. Fronta – aplikačný akumulátor. Nemusí tam byť žiadny rad.
2. Servisné stredisko pozostáva z konečného počtu servisných kanálov. Každý kanál má 3 stavy: voľný, zaneprázdnený, nefunkčný. Ak sú všetky kanály obsadené, môžete prísť so stratégiou, komu preniesť požiadavku.
3. odmietnutie zo služby nastane, ak sú všetky kanály obsadené (niektoré z nich nemusia fungovať).

Okrem týchto základných prvkov v QS niektoré zdroje zdôrazňujú aj tieto komponenty:

terminátor – ničiteľ transakcií;

sklad – sklad surovín a hotových výrobkov;

účtovný účet – na vykonávanie transakcií typu „účtovanie“;

manažér – manažér zdrojov;

Klasifikácia SMO

Prvá divízia (na základe prítomnosti frontov):

• QS s poruchami;
• SMO s radom.

IN QS s poruchami aplikácia prijatá v čase, keď sú všetky kanály obsadené, je odmietnutá, opúšťa QS a v budúcnosti nebude obsluhovaná.

IN Rad s radom aplikácia, ktorá príde v čase, keď sú všetky kanály zaneprázdnené, neodíde, ale zaradí sa do radu a čaká na príležitosť na obslúženie.

QS s frontami sú rozdelené do rôznych typov v závislosti od toho, ako je usporiadaný front - obmedzené alebo neobmedzené. Obmedzenia sa môžu týkať dĺžky radu aj čakacej doby, „obslužnej disciplíny“.

Do úvahy sa teda berú napríklad tieto QS:

• CMO s netrpezlivými požiadavkami (dĺžka frontu a servisný čas sú obmedzené);
• QS s prioritným servisom, t.j. niektoré požiadavky sú obsluhované mimo poradia atď.

Typy obmedzení frontu je možné kombinovať.

Ďalšia klasifikácia rozdeľuje SOT podľa zdroja žiadostí. Aplikácie (požiadavky) môže generovať samotný systém alebo nejaké externé prostredie, ktoré existuje nezávisle od systému.

Prirodzene, tok požiadaviek generovaných samotným systémom bude závisieť od systému a jeho stavu.

Okrem toho sa SMO delia na OTVORENÉ CMO a ZATVORENÉ SMO.

V otvorenom QS charakteristiky toku aplikácií nezávisia od stavu samotného QS (koľko kanálov je obsadených). V uzavretom QS - závisia. Ak napríklad jeden pracovník obsluhuje skupinu strojov, ktoré si z času na čas vyžadujú úpravu, potom intenzita toku „požiadaviek“ zo strojov závisí od toho, koľko z nich je už v prevádzke a čaká na úpravu.

Príklad uzavretého systému: pokladník vydávajúci mzdy v podniku.

Na základe počtu kanálov sa QS delia na:

• jednokanálový;
• viackanálový.

Charakteristika systému radenia

Hlavné charakteristiky akéhokoľvek typu systému radenia sú:

• vstupný tok prichádzajúcich požiadaviek alebo žiadostí o službu;
• disciplína vo fronte;
• servisný mechanizmus.

Vstupné požiadavky Stream

Ak chcete opísať vstupný tok, musíte zadať pravdepodobnostný zákon, ktorý určuje postupnosť okamihov, kedy sú prijaté žiadosti o službu, a uveďte počet takýchto požiadaviek v každom nasledujúcom potvrdení. V tomto prípade spravidla pracujú s pojmom „pravdepodobné rozloženie momentov prijatia požiadaviek“. Tu môžu robiť nasledovné: individuálne a skupinové požiadavky (počet takýchto požiadaviek v každom pravidelnom príjme). V druhom prípade zvyčajne hovoríme o systéme radenia so servisom v paralelných skupinách.

A i– čas príchodu medzi požiadavkami – nezávislé identicky rozdelené náhodné premenné;

E(A)– priemerný (MO) čas príchodu;

λ=1/E(A)– intenzita prijímania požiadaviek;

Charakteristika vstupného toku:

1. Pravdepodobný zákon, ktorý určuje postupnosť momentov, kedy sú prijaté požiadavky na službu.
2. Počet žiadostí pri každom ďalšom príchode pre skupinové toky.

Disciplína v rade

Fronta – súbor požiadaviek čakajúcich na službu.

Poradie má názov.

Disciplína v rade definuje princíp, podľa ktorého sú požiadavky prichádzajúce na vstup obslužného systému zapojené z radu do obslužného postupu. Najčastejšie používané disciplíny fronty sú definované nasledujúcimi pravidlami:

• kto skôr príde, bude skôr obslúžený;

prvý dnu, prvý von (FIFO)

najbežnejší typ frontu.

Aká dátová štruktúra je vhodná na popis takéhoto frontu? Pole je zlé (obmedzené). Môžete použiť štruktúru LIST.

Zoznam má začiatok a koniec. Zoznam pozostáva zo záznamov. Záznam je bunka zoznamu. Aplikácia sa dostane na koniec zoznamu a na službu sa vyberie od začiatku zoznamu. Záznam pozostáva z charakteristiky aplikácie a odkazu (ukazovateľa toho, kto za ňou stojí). Okrem toho, ak má rad čakaciu dobu, musí byť uvedená aj maximálna čakacia doba.

Ako programátori by ste mali byť schopní vytvárať obojsmerné, jednosmerné zoznamy.

Zoznam akcií:

• vložte do chvosta;
• brať od začiatku;
• odstrániť zo zoznamu po uplynutí časového limitu.
• Ako posledný príde – prvý bude obsluhovaný LIFO (svorka na kazetu, slepá ulička na železničnej stanici, vošiel do preplneného auta).

Štruktúra známa ako STACK. Môže byť opísaný štruktúrou poľa alebo zoznamu;

• náhodný výber aplikácií;
• výber žiadostí na základe prioritných kritérií.

Každá žiadosť sa okrem iného vyznačuje úrovňou priority a po prijatí sa nezaradí na koniec poradia, ale na koniec svojej prioritnej skupiny. Dispečer triedi podľa priority.

Charakteristiky frontu

• obmedzeniečas čakania moment obsluhy (existuje rad s obmedzeným časom čakania na obsluhu, ktorý je spojený s pojmom „prípustná dĺžka frontu“);
• dĺžka frontu.

Servisný mechanizmus

Servisný mechanizmus určené charakteristikami samotného servisného postupu a štruktúrou servisného systému. Charakteristiky postupu údržby zahŕňajú:

• počet servisných kanálov ( N);
• trvanie servisného postupu (pravdepodobné rozloženie času pre požiadavky na servis);
• počet požiadaviek splnených v dôsledku každého takéhoto postupu (pre skupinové žiadosti);
• pravdepodobnosť zlyhania servisného kanála;
• štruktúru systému služieb.

Na analytický opis charakteristík servisného postupu sa používa pojem „pravdepodobné rozloženie času pre požiadavky na servis“.

S i- servisný čas i-tá požiadavka;

E(S)– priemerný servisný čas;

μ=1/E(S)- rýchlosť vybavenia požiadaviek.

Je potrebné poznamenať, že čas potrebný na servis aplikácie závisí od charakteru samotnej aplikácie alebo požiadaviek klienta a od stavu a možností servisného systému. V niektorých prípadoch je tiež potrebné vziať do úvahy pravdepodobnosť zlyhania servisného kanála po určitej obmedzenej dobe. Táto charakteristika môže byť modelovaná ako prúd porúch vstupujúcich do QS a majúcich prednosť pred všetkými ostatnými požiadavkami.

Miera využitia QS

N·μ – servisná rýchlosť v systéme, keď sú všetky servisné zariadenia obsadené.

ρ=λ/( Nμ) – tzv koeficient využitia QS , ukazuje, koľko systémových prostriedkov sa využíva.

Štruktúra servisného systému

Štruktúra obslužného systému je určená počtom a relatívnou polohou obslužných kanálov (mechanizmy, zariadenia atď.). V prvom rade je potrebné zdôrazniť, že systém služieb môže mať viac ako jeden servisný kanál, ale niekoľko; Tento typ systému je schopný obslúžiť viacero požiadaviek súčasne. V tomto prípade všetky servisné kanály ponúkajú rovnaké služby, a preto možno tvrdiť, že paralelná služba .

Príklad. Registračné pokladnice v predajni.

Obslužný systém môže pozostávať z niekoľkých rôznych typov obslužných kanálov, cez ktoré musí prejsť každá obsluhovaná požiadavka, t.j. v obslužnom systéme postupy údržby požiadaviek sú implementované dôsledne . Obslužný mechanizmus určuje charakteristiky odchádzajúceho (obsluhovaného) toku požiadaviek.

Príklad. Lekárska komisia.

Kombinovaná služba – obsluha vkladov v sporiteľni: najprv kontrolór, potom pokladník. Spravidla 2 kontrolóri na pokladníka.

takže, funkčnosť akéhokoľvek systému radenia je určená nasledujúcimi hlavnými faktormi :

• pravdepodobnostné rozdelenie momentov prijatia žiadostí o službu (jednotlivé alebo skupinové);
• výkon zdroja požiadaviek;
• pravdepodobnostné rozdelenie času trvania služby;
• konfigurácia systému obsluhy (paralelná, sekvenčná alebo paralelne sekvenčná služba);
• počet a produktivita servisných kanálov;
• frontová disciplína.

Hlavné kritériá efektívnosti fungovania QS

Ako hlavné kritériá účinnosti systémov radenia V závislosti od povahy riešeného problému sa môže objaviť nasledovné:

• pravdepodobnosť okamžitého servisu prichádzajúcej aplikácie (P obsl = K obs / K post);
• pravdepodobnosť odmietnutia obsluhy prichádzajúcej aplikácie (P open = K open / K post);

Je zrejmé, že P obsl + P open =1.

Toky, meškania, údržba. Vzorec Pollacheck-Khinchin

Oneskorenie – jedným z kritérií na obsluhu QS je čas, ktorý aplikácia strávi čakaním na servis.

D i– oneskorenie v rade žiadostí i;

W i = D i + S i– čas potrebný v systéme i.

(s pravdepodobnosťou 1) – zistené priemerné oneskorenie požiadavky vo fronte;

(s pravdepodobnosťou 1) – stanovený priemerný čas, počas ktorého je požiadavka v QS (čakanie).

Q(t) – počet žiadostí vo fronte naraz t;

L(t)– počet požiadaviek v systéme naraz t(Q(t) plus počet požiadaviek, ktoré sú súčasne obsluhované t.

Potom ukazovatele (ak existujú)

(s pravdepodobnosťou 1) – ustálený priemerný počet požiadaviek vo fronte v priebehu času;

(s pravdepodobnosťou 1) – ustálený priemerný počet požiadaviek v systéme v čase.

Všimnite si, že ρ<1 – обязательное условие существования d, w, Q A L v systéme poradia.

Ak si pamätáme, že ρ= λ/( Nμ), potom je zrejmé, že ak je intenzita prijímania žiadostí väčšia ako Nμ, potom ρ>1 a je prirodzené, že systém takýto tok aplikácií nezvládne, a preto nemôžeme hovoriť o množstvách d, w, Q A L.

Najvšeobecnejšie a potrebné výsledky pre systémy radenia zahŕňajú rovnice zachovania

Treba poznamenať, že vyššie uvedené kritériá na hodnotenie výkonnosti systému možno analyticky vypočítať pre systémy zaraďovania M/M/N(N>1), teda systémy s Markovovými tokmi požiadaviek a služieb. Pre M/G/ l pre akúkoľvek distribúciu G a pre niektoré ďalšie systémy. Vo všeobecnosti platí, že distribúcia medzipríchodového času, distribúcia času služby alebo oboje musia byť exponenciálne (alebo nejaký druh exponenciálneho Erlangovho rozdelenia k-tého rádu), aby bolo možné analytické riešenie.

Okrem toho môžeme hovoriť aj o vlastnostiach, ako sú:

• absolútna kapacita systému – А=Р obsl *λ;
• relatívna kapacita systému –

Ďalší zaujímavý (a názorný) príklad analytického riešenia – výpočet priemerného oneskorenia v ustálenom stave vo fronte pre systém zaraďovania M/G/ 1 podľa vzorca:

.

V Rusku je tento vzorec známy ako Pollacekov vzorec – Khinchin, v zahraničí sa tento vzorec spája s menom Ross.

Teda ak E(S) je väčšie, potom preťaženie (v tomto prípade merané ako d) bude väčší; čo sa dá očakávať. Vzorec tiež odhaľuje menej zrejmú skutočnosť: preťaženie sa tiež zvyšuje, keď sa zvyšuje variabilita rozloženia servisného času, aj keď priemerný servisný čas zostáva rovnaký. Intuitívne sa to dá vysvetliť takto: rozptyl náhodnej veličiny servisného času môže nadobudnúť veľkú hodnotu (keďže musí byť kladný), t. j. jediné servisné zariadenie bude dlho zaneprázdnené, čo povedie k nárast v rade.

Predmet teórie radenia je vytvoriť vzťah medzi faktormi, ktoré určujú funkčnosť systému radenia a efektívnosť jeho prevádzky. Vo väčšine prípadov sú všetky parametre popisujúce systémy radenia náhodné premenné alebo funkcie, preto tieto systémy patria medzi stochastické systémy.

Náhodná povaha toku aplikácií (požiadaviek), ako aj vo všeobecnom prípade trvanie služby vedie k tomu, že v systéme zaraďovania dochádza k náhodnému procesu. Podľa povahy náhodného procesu , vyskytujúce sa v systéme radenia (QS), sú rozlíšené Markovské a nemarkovské systémy . V systémoch Markov je vstupný tok požiadaviek a výstupný tok obsluhovaných požiadaviek (aplikácií) Poisson. Poissonove toky uľahčujú popis a zostavenie matematického modelu systému radenia. Tieto modely majú pomerne jednoduché riešenia, takže väčšina známych aplikácií teórie radenia používa Markovovu schému. V prípade nemarkovských procesov sa problematika štúdia systémov radenia výrazne komplikuje a vyžaduje použitie štatistického modelovania a numerických metód pomocou počítača.

Veľká trieda systémov, ktoré je ťažké študovať analytickými metódami, ale ktoré sú dobre študované metódami štatistického modelovania, sa týka systémov radenia (QS).

QS znamená, že existuje typické cesty(servisné kanály), ktorými prechádzajú počas procesu spracovania aplikácie. Bežne sa hovorí, že aplikácie slúžil kanály. Kanály sa môžu líšiť účelom, charakteristikami, môžu sa kombinovať v rôznych kombináciách; aplikácie môžu byť v rade a čakajú na servis. Niektoré aplikácie môžu byť obsluhované kanálmi, zatiaľ čo iné to môžu odmietnuť. Je dôležité, aby požiadavky z hľadiska systému boli abstraktné: sú niečím, čo chce byť obsluhované, teda ísť určitým spôsobom v systéme. Kanály sú tiež abstrakciou: slúžia na požiadavky.

Požiadavky môžu prichádzať nerovnomerne, kanály môžu obsluhovať rôzne požiadavky v rôznych časoch a tak ďalej, počet žiadostí je vždy veľmi veľký. To všetko sťažuje štúdium a riadenie takýchto systémov a nie je možné v nich vysledovať všetky vzťahy príčin a následkov. Preto sa všeobecne uznáva, že údržba v zložitých systémoch je náhodná.

Príklady SOT (pozri tabuľku 30.1) zahŕňajú: autobusové linky a osobnú dopravu; Výrobný dopravník na spracovanie dielov; letka lietadiel letiacich na cudzie územie, ktorá je „obsluhovaná“ protilietadlovými delami protivzdušnej obrany; hlaveň a roh guľometu, ktoré „slúžia“ nábojom; elektrické náboje pohybujúce sa v niektorom zariadení atď.

Tabuľka 30.1. Príklady radiacich systémov

Aplikácie Kanály Autobusová a osobná doprava Cestujúci Autobusy Výrobný dopravník na spracovanie dielov Diely, komponenty Obrábacie stroje, sklady Letka lietadiel letiacich na cudzie územie, ktorej „slúžia“ protilietadlové delá protivzdušnej obrany Lietadlá Protilietadlové delá, radary, šípy, náboje Hlaveň a roh guľometu, ktoré „slúžia“ nábojom Hlaveň, roh Elektrické náboje pohybujúce sa v niektorom zariadení Kaskády technických zariadení

Všetky tieto systémy sú však spojené do jednej triedy QS, pretože prístup k ich štúdiu je rovnaký. Spočíva v tom, že po prvé, pomocou generátora náhodných čísel sa vyžrebujú náhodné čísla, ktoré simulujú NÁHODNÉ momenty výskytu objednávok a čas ich obsluhy v kanáloch. Ale spolu, tieto náhodné čísla sú, samozrejme, podriadené štatistické vzory.

Povedzme napríklad: „Priemerne aplikácie prichádzajú v množstve 5 kusov za hodinu“. To znamená, že časy medzi príchodom dvoch susedných požiadaviek sú náhodné, napríklad: 0,1; 0,3; 0,1; 0,4; 0,2, ako je znázornené na obr. 30,1, ale celkovo dávajú priemer 1 (všimnite si, že v príklade to nie je presne 1, ale 1,1 - ale v inú hodinu sa tento súčet môže napríklad rovnať 0,9); ale len na dosť dlhú dobu priemer týchto čísel sa priblíži k jednej hodine.

Výsledkom (napríklad priepustnosť systému) bude samozrejme aj náhodná veličina v jednotlivých časových intervaloch. Ale meraná počas dlhého časového obdobia bude táto hodnota v priemere zodpovedať presnému riešeniu. To znamená, že na charakterizáciu QS ich zaujímajú odpovede v štatistickom zmysle.

Systém sa teda testuje s náhodnými vstupnými signálmi podľa daného štatistického zákona a výsledkom sú štatistické ukazovatele spriemerované za čas zvažovania alebo za počet experimentov. Predtým v prednášky 21(cm. ryža. 21.1), schému takéhoto štatistického experimentu sme už vypracovali (pozri obr. 30.2).

Po druhé, všetky modely QS sú zostavené štandardným spôsobom z malej množiny prvkov (kanál, zdroj požiadaviek, front, požiadavka, servisná disciplína, zásobník, kruh atď.), čo umožňuje simulovať tieto úlohy typický spôsobom. Na tento účel sa z konštruktéra takýchto prvkov zostaví model systému. Nezáleží na tom, aký konkrétny systém sa študuje, dôležité je, aby bol systémový diagram zostavený z rovnakých prvkov. Samozrejme, štruktúra okruhu bude vždy iná.

Uveďme niekoľko základných pojmov QS.

Kanály sú to, čo slúži; Existujú horúce (začnú obsluhovať požiadavku v momente, keď vstúpi do kanála) a studené (kanál potrebuje čas na prípravu pred začatím servisu). Zdroje objednávok – generujú objednávky v náhodných časoch, podľa štatistického zákona určeného používateľom. Aplikácie, známe aj ako klienti, vstupujú do systému (generovaného zdrojmi aplikácií), prechádzajú jeho prvkami (sú obsluhované) a opúšťajú ho obsluhovaný alebo nespokojný. Existujú netrpezlivé žiadosti – tí, ktorých už nebaví čakať alebo byť v systéme a ktorí z vlastnej vôle odchádzajú z CMO. Toky formulárov žiadostí - tok žiadostí na vstupe systému, tok obsluhovaných aplikácií, tok zamietnutých žiadostí. Tok je charakterizovaný počtom aplikácií určitého typu pozorovaných na určitom mieste QS za jednotku času (hodina, deň, mesiac), to znamená, že tok je štatistická veličina.

Fronty sú charakterizované pravidlami poradia (disciplína služieb), počtom miest v rade (maximálny počet klientov, ktorí môžu byť v rade), a štruktúrou poradia (vzťah medzi miestami v rade). Existujú obmedzené a neobmedzené fronty. Uveďme si najdôležitejšie disciplíny údržby. FIFO (First In, First Out - first in, first out): ak je požiadavka prvá, ktorá dorazí do frontu, potom bude prvá, ktorá pôjde na obsluhu. LIFO (Last In, First Out - last in, first out): ak bola požiadavka posledná, ktorá prišla v rade, potom bude prvá, ktorá pôjde do servisu (príklad - náboje v rohu guľometu). SF (Short Forward): tie požiadavky z frontu, ktoré majú kratší čas obsluhy, sú obsluhované ako prvé.

Uveďme nápadný príklad, ktorý ukazuje, ako vám správny výber tej či onej servisnej disciplíny umožňuje dosiahnuť výraznú úsporu času.

Nech sú dva obchody. V predajni č. 1 sa obsluhuje podľa poradia príchodu, čiže je tu implementovaná disciplína FIFO (pozri obr. 30.3).

Servisný čas t služby na obr. 30.3 uvádza, koľko času strávi predávajúci obsluhou jedného kupujúceho. Je jasné, že pri nákupe kusového produktu strávi predajca obsluhou menej času ako pri nákupe povedzme hromadných produktov, ktoré si vyžadujú ďalšie manipulácie (vyberanie, váženie, výpočet ceny atď.). Čas čakania t očakávané ukazuje, ako dlho bude trvať, kým predajca obslúži ďalšieho kupujúceho.

V predajni č. 2 je implementovaná disciplína SF (viď obr. 30.4), čo znamená, že kusový tovar je možné dokúpiť aj mimo poradia, od servisnej doby t služby taký nákup je malý.

Ako vidno z oboch obrázkov, posledný (piaty) kupujúci bude kupovať kusový produkt, takže jeho servisný čas je krátky - 0,5 minúty. Ak tento zákazník príde do predajne č.1, bude nútený stáť v rade celých 8 minút, pričom v predajni č.2 bude obslúžený okamžite, mimo radu. Priemerný čas obsluhy každého zákazníka v predajni s disciplínou FIFO bude teda 4 minúty a v predajni s disciplínou HF iba 2,8 minúty. A sociálna dávka, úspora času bude: (1 – 2,8/4) · 100 % = 30 percent! Čiže 30% ušetreného času pre spoločnosť – a to len vďaka správnemu výberu služobnej disciplíny.

Systémový špecialista musí dôkladne rozumieť zdrojom výkonu a efektívnosti systémov, ktoré navrhuje, ktoré sú skryté v optimalizácii parametrov, štruktúr a disciplín údržby. Modelovanie pomáha identifikovať tieto skryté rezervy.

Pri analýze výsledkov modelovania je tiež dôležité uviesť záujmy a rozsah, v akom sú naplnené. Rozlišuje sa medzi záujmami klienta a záujmami vlastníka systému. Upozorňujeme, že tieto záujmy sa nie vždy zhodujú.

Výkonnosť QS možno posudzovať podľa ukazovateľov. Najpopulárnejšie z nich:

pravdepodobnosť zákazníckeho servisu systémom;

priepustnosť systému;

pravdepodobnosť odmietnutia služby zákazníkovi;

pravdepodobnosť zamestnania každého kanála a všetkých spolu;

priemerný čas obsadenosti každého kanála;

pravdepodobnosť obsadenosti všetkých kanálov;

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

pravdepodobnosť výpadkov pre každý kanál;

pravdepodobnosť výpadku celého systému;

priemerný počet žiadostí vo fronte;

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

priemerný čas na obsluhu aplikácie;

priemerný čas, počas ktorého aplikácia zostáva v systéme.

Kvalita výsledného systému sa musí posudzovať podľa súhrnu hodnôt ukazovateľov. Pri analýze výsledkov modelovania (ukazovateľov) je tiež dôležité venovať pozornosť záujmom klienta a záujmom vlastníka systému, to znamená, že jeden alebo druhý ukazovateľ musí byť minimalizovaný alebo maximalizovaný, ako aj stupeň ich implementácie. . Všimnite si, že najčastejšie záujmy klienta a majiteľa sa navzájom nezhodujú alebo sa nie vždy zhodujú. Nižšie označíme ukazovatele H = { h 1 , h 2 , …} .

Parametre QS môžu byť: intenzita toku požiadaviek, intenzita toku služieb, priemerný čas, počas ktorého je požiadavka pripravená čakať na službu vo fronte, počet obslužných kanálov, disciplína služby atď. . Parametre ovplyvňujú výkon systému. Nižšie uvedené parametre označíme ako R = { r 1 , r 2 , …} .

Príklad. Čerpacia stanica (čerpacia stanica).

1. Vyjadrenie problému. Na obr. Obrázok 30.5 zobrazuje usporiadanie čerpacej stanice. Uvažujme o metóde modelovania QS na jej príklade a pláne jej výskumu. Vodiči prechádzajúci cez čerpacie stanice môžu chcieť natankovať svoje vozidlo. Nie všetci motoristi chcú získať servis (natankovať do auta benzín); Predpokladajme, že z celého toku áut príde na čerpaciu stanicu v priemere 5 áut za hodinu.

Na čerpacej stanici sú dva identické stĺpce, štatistická výkonnosť každého z nich je známa. Prvý stĺpec obsluhuje v priemere 1 auto za hodinu, druhý v priemere 3 autá za hodinu. Majiteľ čerpacej stanice vydláždil pre autá miesto, kde môžu čakať na obsluhu. Ak sú pumpy obsadené, tak na tomto mieste môžu čakať na obsluhu aj iné autá, maximálne však dve naraz. Poradie budeme považovať za všeobecné. Akonáhle je jedna z kolón voľná, prvé auto v poradí môže zaujať svoje miesto v kolóne (zatiaľ čo druhé auto sa posunie na prvé miesto v rade). Ak sa objaví tretie auto a všetky miesta (sú dve) v rade sú obsadené, je odmietnutá služba, pretože státie na ceste je zakázané (pozri dopravné značky pri čerpacej stanici). Takéto auto navždy opustí systém a ako potenciálny klient je pre majiteľa čerpacej stanice stratené. Úlohu môžete skomplikovať zvážením pokladne (ďalší servisný kanál, kam sa musíte dostať po obsluhe v jednom zo stĺpcov) a frontu k nej atď. Ale v najjednoduchšej verzii je zrejmé, že tokové cesty aplikácií cez QS môžu byť znázornené vo forme ekvivalentného diagramu a pridaním hodnôt a označení charakteristík každého prvku QS nakoniec získajte schému znázornenú na obr. 30.6.

2. Metóda výskumu SMO. V našom príklade uplatníme princíp postupného účtovania objednávok (podrobnosti o princípoch modelovania viď. prednáška 32). Ide o to, že aplikácia prechádza celým systémom od vstupu až po výstup a až potom sa modeluje ďalšia aplikácia.

Pre prehľadnosť zostavme časový diagram operácie QS, ktorý sa odráža na každom riadku (časová os t) stav jednotlivého prvku systému. Časových línií je toľko, koľko je rôznych miest v QS a tokoch. V našom príklade je ich 7 (tok požiadaviek, čakacie vlákno na prvom mieste vo fronte, čakajúce vlákno na druhom mieste vo fronte, tok služieb v kanáli 1, tok služieb v kanáli 2 tok žiadostí obsluhovaných systémom, tok odmietnutých žiadostí).

Na generovanie času príchodu žiadostí používame vzorec na výpočet intervalu medzi časmi príchodu dvoch náhodných udalostí (pozri. prednáška 28):

V tomto vzorci hodnota prietoku λ musí byť špecifikovaný (predtým musí byť stanovený experimentálne na zariadení ako štatistický priemer), r- náhodné rovnomerne rozdelené číslo od 0 do 1 z RNG resp tabuľky, v ktorom je potrebné brať náhodné čísla za sebou (bez špeciálneho výberu).

Úloha. Vytvorte stream 10 náhodných udalostí s frekvenciou udalostí 5 ks/hod.

Riešenie problému. Zoberme si náhodné čísla rovnomerne rozdelené v rozsahu od 0 do 1 (pozri. tabuľky) a vypočítajte ich prirodzené logaritmy (pozri tabuľku 30.2).

Tabuľka 30.2. Fragment tabuľky náhodných čísel a ich logaritmy

r pp ln(r pp )

Poissonov vzorec toku určuje vzdialenosť medzi dvoma náhodnými udalosťami takto: t= –Ln(r рр)/ λ . Potom, vzhľadom na to λ = 5, máme vzdialenosti medzi dvoma náhodnými susednými udalosťami: 0,68, 0,21, 0,31, 0,12 hodín. To znamená, že udalosti sa dejú: po prvé - v čase t= 0, druhý - v čase t= 0,68, tretí - v čase t= 0,89, štvrtý - v čase t= 1,20, piaty - v čase t= 1,32 a tak ďalej. Udalosti - príchod objednávok sa prejaví na prvom riadku (viď obr. 30.7).

Ryža. 30.7. Časový diagram prevádzky QS

Prijme sa prvá požiadavka a keďže v tomto momente sú kanály voľné, je nastavený na obsluhu prvého kanálu. Aplikácia 1 sa prenesie do riadku „1 kanál“.

Čas služby v kanáli je tiež náhodný a vypočítava sa pomocou podobného vzorca:

kde úlohu intenzity zohráva veľkosť toku služieb μ 1 alebo μ 2, v závislosti od toho, ktorý kanál obsluhuje požiadavku. Na diagrame nájdeme moment ukončenia služby, čím odložíme vygenerovaný čas služby od začiatku služby a znížime požiadavku na riadok „Obsluhované“.

Žiadosť sa dostala až na CMO. Teraz je možné podľa princípu sekvenčného účtovania objednávok simulovať aj cestu druhej objednávky.

Ak sa v určitom okamihu ukáže, že obidva kanály sú zaneprázdnené, požiadavka by mala byť zaradená do frontu. Na obr. 30.7 je požiadavka s číslom 3. Všimnite si, že podľa podmienok problému, na rozdiel od kanálov, požiadavky nie sú vo fronte náhodne, ale čakajú, kým sa jeden z kanálov uvoľní. Po uvoľnení kanála je požiadavka vznesená na riadok príslušného kanála a tam je organizovaná jeho obsluha.

Ak sú všetky miesta vo fronte v čase príchodu ďalšej žiadosti obsadené, žiadosť by sa mala odoslať na riadok „Odmietnuté“. Na obr. 30.7 je prihláška číslo 6.

Procedúra na simuláciu servisu aplikácie pokračuje určitý čas pozorovania. T n. Čím je tento čas dlhší, tým presnejšie budú výsledky simulácie v budúcnosti. V skutočnosti si vyberajú jednoduché systémy T n, rovná 50-100 alebo viac hodinám, hoci niekedy je lepšie merať túto hodnotu počtom kontrolovaných aplikácií.

Analytický výskum systémov radenia (QS) je alternatívou k simulačnému modelovaniu a pozostáva zo získania vzorcov na výpočet výstupných parametrov QS a následného dosadenia hodnôt argumentov do týchto vzorcov v každom jednotlivom experimente.

Modely QS berú do úvahy nasledujúce objekty:

1) servisné požiadavky (transakcie);

2) servisné zariadenia (OA) alebo zariadenia.

Praktická úloha teórie radenia je spojená so štúdiom operácií týmito objektmi a pozostáva z jednotlivých prvkov, ktoré sú ovplyvnené náhodnými faktormi.

Príklady problémov zvažovaných v teórii radenia zahŕňajú: zosúladenie kapacity zdroja správ s kanálom prenosu údajov, analýza optimálneho toku mestskej dopravy, výpočet kapacity čakárne pre cestujúcich na letisku atď.

Požiadavka môže byť v stave služby alebo v stave čakajúcej služby.

Servisné zariadenie môže byť zaneprázdnené servisom alebo voľné.

Stav QS je charakterizovaný množinou stavov servisných zariadení a požiadaviek. Zmena stavu v QS sa nazýva udalosť.

Modely QS sa používajú na štúdium procesov vyskytujúcich sa v systéme, keď sa toky požiadaviek predkladajú na vstupy. Tieto procesy sú sledom udalostí.

Najdôležitejšie výstupné parametre QS

Výkon

Šírka pásma

Pravdepodobnosť odmietnutia služby

Priemerný servisný čas;

Faktor zaťaženia zariadenia (OA).

Aplikáciami môžu byť zákazky na výrobu produktov, problémy riešené v počítačovom systéme, klienti v bankách, tovar prijatý na prepravu a pod. Je zrejmé, že parametre aplikácií vstupujúcich do systému sú náhodné veličiny a pri výskume alebo návrhu len ich zákony distribúcie .

V tomto ohľade má analýza fungovania na úrovni systému spravidla štatistický charakter. Je vhodné osvojiť si teóriu radenia ako matematický modelovací aparát a na tejto úrovni používať systémy radenia ako modely systémov.

Najjednoduchšie modely QS

V najjednoduchšom prípade je QS zariadenie nazývané servisné zariadenie (SA), s radmi požiadaviek na vstupoch.

MODEL SLUŽBY ZÁKAZNÍKOV (obr. 5.1)

Ryža. 5.1. Model QS s poruchami:

0 – zdroj požiadaviek;

1 – obslužné zariadenie;

A– vstupný tok žiadostí o službu;

V– výstupný tok obsluhovaných požiadaviek;

s– výstupný tok nespracovaných požiadaviek.

V tomto modeli nie je na vstupe OA žiadny dopytový akumulátor. Ak požiadavka príde zo zdroja 0 v čase, keď je OA zaneprázdnený obsluhou predchádzajúcej požiadavky, potom novoprijatá požiadavka opustí systém (keďže je jej odmietnutá služba) a stratí sa (tok s).

M o d e l o f o r m e n e (obr. 5.2)

Ryža. 5.2. Model QS s očakávaním

(N– 1) – počet aplikácií, ktoré sa zmestia do úložiska

V tomto modeli je na vstupe OA odberový akumulátor. Ak príde požiadavka zo zdroja 0 v čase, keď je OA zaneprázdnený obsluhou predchádzajúcej požiadavky, tak novo prichádzajúca požiadavka skončí v úložnej jednotke, kde nekonečne dlho čaká, kým sa OA uvoľní.

SERVISNÝ MODEL S OBMEDZENÍM ČASU

o w i d a n i a (obr. 5.3)

Ryža. 5.4. Viackanálový model QS s poruchami:

n– počet rovnakých servisných zariadení (zariadení)

V tomto modeli nie je jeden OA, ale niekoľko. Žiadosti, pokiaľ nie je výslovne uvedené inak, môžu byť predložené ktorejkoľvek OA bez služby. Neexistuje žiadne úložné zariadenie, takže tento model obsahuje vlastnosti modelu znázorneného na obr. 5.1: odmietnutie doručenia žiadosti znamená jej nenahraditeľnú stratu (k tomu dôjde iba vtedy, ak v čase doručenia tejto žiadosti Všetky OA sú zaneprázdnení).

Čakacia doba (obr. 5.5)

Ryža. 5.6. Viackanálový model SMO s očakávaním a obnovou OA:

e– servisné zariadenia, ktoré sú mimo prevádzky;

f- repasované servisné zariadenia

Tento model má vlastnosti modelov znázornených na obr. 5.2 a 5.4, a navyše vlastnosti, ktoré umožňujú zohľadniť možné náhodné poruchy OA, ktoré sa v tomto prípade dostanú do opravárenskej jednotky 2, kde zostanú náhodne dlhý čas strávený na ich obnove a potom sa vrátia späť opäť do servisnej jednotky 1.

MULTI-KANÁLOVÝ MODEL SMO S OBMEDZENÍM

DOBA ČAKANIA A OBNOVENIA OA (obr. 5.7)

Ryža. 5.7. Viackanálový model QS s obmedzenou latenciou a obnovou OA

Tento model je pomerne zložitý, keďže súčasne zohľadňuje vlastnosti dvoch nie veľmi jednoduchých modelov (obr. 5.5 a 5.6).

Odoslanie dobrej práce do databázy znalostí je jednoduché. Použite nižšie uvedený formulár

Študenti, postgraduálni študenti, mladí vedci, ktorí pri štúdiu a práci využívajú vedomostnú základňu, vám budú veľmi vďační.

Uverejnené dňa http://allbest.ru

ÚVOD

KAPITOLA 1. TEORETICKÁ ČASŤ

1.1 Systémy radenia s poruchami

1.2 Modelovanie systémov radenia

1.3 Najjednoduchší QS s poruchami

1.4 Jednokanálový QS s poruchami

1.5 Viackanálový QS s poruchami

1.6 Jednokanálový QS s obmedzenou dĺžkou frontu

1.7 Jednokanálový QS s neobmedzeným frontom

1.8 Viackanálové QS s obmedzenou dĺžkou frontu

1.9 Viackanálové QS s neobmedzeným frontom

1.10 Algoritmus modelovania QS

KAPITOLA 2. PRAKTICKÁ ČASŤ

KAPITOLA 3. BEZPEČNOSTNÉ PRAVIDLÁ

ZÁVER

ZOZNAM POUŽITÝCH REFERENCIÍ

ÚVOD

V poslednej dobe sa v rôznych oblastiach praxe objavila potreba riešiť rôzne pravdepodobnostné problémy súvisiace s prevádzkou takzvaných systémov radenia (QS).

Príklady takýchto systémov zahŕňajú: telefónne ústredne, opravovne, pokladne, stanovištia taxíkov, kaderníctva atď.

Témou tohto projektu kurzu je práve riešenie takéhoto problému.

V navrhovanom probléme sa však bude študovať QS, v ktorom sa zvažujú 2 prúdy žiadostí, z ktorých jeden má prioritu.

Taktiež uvažované procesy sú nemarkovské, pretože Dôležitý je faktor času.

Preto riešenie tohto problému nie je založené na analytickom popise systému, ale na štatistickom modelovaní.

Cieľom práce v kurze je modelovať výrobný proces na základe reprezentácie hlavného zariadenia ako systému radenia.

Na dosiahnutie cieľa boli stanovené nasledovné úlohy: - analyzovať vlastnosti riadenia výrobného procesu; - Zvážte organizáciu výrobného procesu v čase; - Poskytnúť hlavné možnosti skrátenia trvania výrobného cyklu;

Vykonať analýzu metód riadenia výrobného procesu v podniku;

Zvážte vlastnosti modelovania výrobného procesu pomocou teórie QMS;

Vypracovať model výrobného procesu a zhodnotiť hlavné charakteristiky QS a poskytnúť vyhliadky na jeho ďalšiu softvérovú implementáciu.

Upevňovanie teoretických vedomostí a získavanie zručností pri ich praktickej aplikácii;

Správa obsahuje úvod, tri kapitoly, záver, zoznam použitej literatúry a prílohy.

Druhá kapitola pojednáva o teoretických materiáloch systému radenia. A v treťom počítame problém systémov radenia.

KAPITOLA 1. TEORETICKÁ ČASŤ

1.1 Systémy radeniaczlyhania

Systém radenia (QS) je akýkoľvek systém navrhnutý tak, aby obsluhoval akékoľvek aplikácie (požiadavky), ktoré k nemu prichádzajú v náhodných časoch. Každé zariadenie priamo zapojené do servisných požiadaviek sa nazýva servisný kanál (alebo „zariadenie“). SMO môžu byť jedno- alebo viackanálové.

Existujú QS s poruchami a QS s frontom. V QS s odmietnutiami aplikácia, ktorá príde v čase, keď sú všetky kanály obsadené, dostane odmietnutie, opustí QS a následne sa nezúčastňuje na jej práci. V QS s frontom požiadavka, ktorá príde, keď sú všetky kanály obsadené, neopustí QS, ale dostane sa do frontu a čaká, kým sa niektorý kanál neuvoľní. Počet miest v rade m môže byť obmedzený alebo neobmedzený. Pri m=0 sa QS s frontom zmení na QS s poruchami. Front môže mať obmedzenia nielen v počte žiadostí, ktoré v ňom stoja (dĺžka frontu), ale aj v čakacej dobe (takéto QS sa nazývajú „systémy s netrpezlivými klientmi“).

Analytické štúdium QS je najjednoduchšie, ak všetky toky udalostí, ktoré ho prenášajú zo stavu do stavu, sú najjednoduchšie (stacionárny Poisson). To znamená, že časové intervaly medzi udalosťami v tokoch majú exponenciálne rozdelenie s parametrom rovným intenzite zodpovedajúceho toku. Pre QS tento predpoklad znamená, že tok požiadaviek aj tok služieb sú najjednoduchšie. Tok služieb je chápaný ako tok požiadaviek obsluhovaných jedna po druhej jedným nepretržite obsadeným kanálom. Tento tok sa ukáže ako najjednoduchší, len ak je čas obsluhy požiadavky tobsl náhodná premenná s exponenciálnym rozložením. Parameter tohto rozdelenia m je prevrátená hodnota priemerného servisného času:

Namiesto frázy „tok služieb je najjednoduchší“ často hovoria „čas služby je orientačný“. Akýkoľvek QS, v ktorom sú všetky toky najjednoduchšie, sa nazýva najjednoduchší QS.

Ak sú všetky toky udalostí najjednoduchšie, potom proces vyskytujúci sa v QS je Markovov náhodný proces s diskrétnymi stavmi a nepretržitým časom. Ak sú pre tento proces splnené určité podmienky, existuje konečný stacionárny režim, v ktorom pravdepodobnosti stavov a ďalšie charakteristiky procesu nezávisia od času.

Modely QS sú vhodné na popis jednotlivých podsystémov moderných výpočtových systémov, ako je procesorový podsystém – hlavná pamäť, vstupno-výstupný kanál atď.

Výpočtový systém ako celok je súborom vzájomne prepojených subsystémov, ktorých interakcia má pravdepodobnostný charakter. Aplikácia na riešenie určitého problému vstupujúca do výpočtového systému prechádza sekvenciou etáp počítania, prístupu k externým pamäťovým zariadeniam a vstupno-výstupným zariadeniam.

Po dokončení určitej postupnosti takýchto etáp, ktorých počet a trvanie závisí od zložitosti programu, sa požiadavka považuje za obslúženú a opúšťa počítačový systém.

Výpočtový systém ako celok teda môže byť reprezentovaný súborom QS, z ktorých každý odráža proces fungovania jednotlivého zariadenia alebo skupiny podobných zariadení, ktoré sú súčasťou systému.

Úlohou teórie radenia je nájsť pravdepodobnosti rôznych stavov QS, ako aj stanoviť vzťah medzi danými parametrami (počet kanálov n, intenzita toku požiadaviek n, rozloženie servisného času atď.). .) a výkonnostné charakteristiky QS. Za takéto vlastnosti možno považovať napríklad tieto:

Priemerný počet požiadaviek A obsluhovaných QS za jednotku času alebo absolútna kapacita QS;

Pravdepodobnosť obsluhy prichádzajúcej požiadavky Q alebo relatívna kapacita QS; Q = A/l;

Pravdepodobnosť poruchy Rotku, t.j. pravdepodobnosť, že prijatá žiadosť nebude doručená a bude zamietnutá; Rotk = 1 - Q;

Priemerný počet žiadostí v QS (vybavených alebo čakajúcich vo fronte);

Priemerný počet žiadostí vo fronte;

Priemerný čas, počas ktorého aplikácia zostáva v QS (vo fronte alebo v službe);

Priemerný čas, ktorý aplikácia strávi vo fronte;

Priemerný počet obsadených kanálov.

Vo všeobecnosti všetky tieto charakteristiky závisia od času. Ale mnohé samoobslužné systémy fungujú v konštantných podmienkach pomerne dlho, a preto sa im darí nastoliť režim blízky stacionárnemu.

Sme tu po celú dobu, bez toho, aby sme to zakaždým špecificky stanovovali, vypočítame konečné pravdepodobnosti stavov a konečné charakteristiky účinnosti QS súvisiace s obmedzujúcim stacionárnym režimom jeho prevádzky.

QS sa nazýva otvorený, ak intenzita toku aplikácií, ktoré k nemu prichádzajú, nezávisí od stavu samotného QS.

Pre každý otvorený QS v obmedzujúcom stacionárnom režime je priemerný čas zotrvania nároku v systéme vyjadrený prostredníctvom priemerného počtu nárokov v systéme pomocou Littleovho vzorca:

kde l je intenzita toku aplikácií.

Podobný vzorec (tiež nazývaný Littleov vzorec) spája priemerný čas, ktorý aplikácia strávi vo fronte, a priemerný počet aplikácií vo fronte:

Littleove vzorce sú veľmi užitočné, pretože umožňujú vypočítať nie obe charakteristiky účinnosti (priemerný čas zdržania a priemerný počet aplikácií), ale iba jednu z nich.

Zvlášť zdôrazňujeme, že vzorce (1) a (2) sú platné pre všetky otvorené QS (jednokanálové, viackanálové, pre všetky typy tokov požiadaviek a tokov služieb); jedinou požiadavkou na aplikačné toky a služby je, aby boli stacionárne.

Podobne vzorec vyjadrujúci priemerný počet obsadených kanálov cez absolútnu kapacitu A má univerzálny význam pre otvorené QS:

kde je intenzita toku služieb.

Mnohé problémy teórie radenia týkajúce sa najjednoduchších QS sa riešia pomocou schémy smrti a reprodukcie.

Konečné pravdepodobnosti stavov sú vyjadrené vzorcami:

Posúvajte sa Charakteristiky systémov radenia možno znázorniť takto:

· priemerný servisný čas;

· priemerná doba čakania v rade;

· priemerný čas pobytu v zdravotnej službe;

priemerná dĺžka frontu;

· priemerný počet žiadostí o SOT;

· počet servisných kanálov;

· intenzita vstupného toku aplikácií;

· intenzita služby;

· intenzita zaťaženia;

· vyťaženosť;

· relatívna priepustnosť;

· absolútna priepustnosť;

· podiel prestojov QS;

· podiel doručených aplikácií;

· podiel stratených aplikácií;

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

· priemerný počet voľných kanálov;

· koeficient zaťaženia kanála;

· priemerné prestoje kanálov.

1 . 2 Modelovanie systémov radenia

Prechody QS z jedného stavu do druhého sa vyskytujú pod vplyvom veľmi špecifických udalostí - prijímania žiadostí a ich obsluhy. Postupnosť udalostí vyskytujúcich sa jedna po druhej v náhodných časoch tvorí takzvaný tok udalostí. Príkladom takýchto tokov v obchodných činnostiach sú toky rôzneho charakteru – tovar, peniaze, doklady, doprava, klienti, kupujúci, telefonáty, rokovania. Správanie systému zvyčajne neurčuje jeden, ale niekoľko prúdov udalostí. Napríklad zákaznícky servis v obchode je určený tokom zákazníkov a tokom služieb; v týchto tokoch sú chvíle, keď sa objavia zákazníci, čas čakania v rade a čas strávený obsluhou každého zákazníka náhodné.

V tomto prípade je hlavnou charakteristickou črtou tokov pravdepodobnostné rozloženie času medzi susednými udalosťami. Existujú rôzne prúdy, ktoré sa líšia svojimi vlastnosťami.

Tok udalostí sa nazýva pravidelný, ak udalosti nasledujú po sebe vo vopred určených a presne definovaných intervaloch. Tento tok je ideálny a v praxi sa s ním stretávame veľmi zriedka. Častejšie sa vyskytujú nepravidelné toky, ktoré nemajú vlastnosť pravidelnosti.

Tok udalostí sa nazýva stacionárny, ak pravdepodobnosť ľubovoľného počtu udalostí spadajúcich do časového intervalu závisí iba od dĺžky tohto intervalu a nezávisí od toho, ako ďaleko sa tento interval nachádza od začiatku času. Stacionarita toku znamená, že jeho pravdepodobnostné charakteristiky sú nezávislé od času, najmä intenzita takéhoto toku je priemerný počet udalostí za jednotku času a zostáva konštantná. V praxi možno toky zvyčajne považovať za stacionárne iba počas určitého obmedzeného časového obdobia. Tok zákazníkov, napríklad v obchode, sa zvyčajne počas pracovného dňa výrazne mení. Je však možné identifikovať určité časové intervaly, v rámci ktorých možno tento prúd považovať za stacionárny, s konštantnou intenzitou.

Tok udalostí sa nazýva tok bez následkov, ak počet udalostí spadajúcich do jedného z ľubovoľne zvolených časových intervalov nezávisí od počtu udalostí spadajúcich do iného, ​​tiež ľubovoľne zvoleného intervalu, za predpokladu, že sa tieto intervaly navzájom nepretínajú. . V toku bez následkov sa udalosti vyskytujú v po sebe nasledujúcich časoch nezávisle od seba. Napríklad tok zákazníkov vstupujúcich do obchodu možno považovať za tok bez následkov, pretože dôvody, ktoré určili príchod každého z nich, nesúvisia s podobnými dôvodmi pre iných zákazníkov.

Tok udalostí sa nazýva obyčajný, ak pravdepodobnosť výskytu dvoch alebo viacerých udalostí naraz vo veľmi krátkom časovom období je zanedbateľná v porovnaní s pravdepodobnosťou výskytu iba jednej udalosti. V bežnom toku sa udalosti vyskytujú po jednej, a nie dvakrát alebo viackrát. Ak má tok súčasne vlastnosti stacionárnosti, obyčajnosti a absencie dôsledkov, potom sa takýto tok nazýva najjednoduchší (alebo Poissonov) tok udalostí. Matematický popis vplyvu takéhoto toku na systémy sa ukazuje ako najjednoduchší. Preto najmä najjednoduchší tok zohráva osobitnú úlohu medzi ostatnými existujúcimi tokmi.

Uvažujme určitý časový interval t na časovej osi. Predpokladajme, že pravdepodobnosť náhodnej udalosti spadajúcej do tohto intervalu je p a celkový počet možných udalostí je n. Za prítomnosti vlastnosti obyčajného toku udalostí by mala byť pravdepodobnosť p dostatočne malá hodnota, a i by malo byť dostatočne veľké číslo, pretože sa uvažuje o hromadných javoch.

Za týchto podmienok na výpočet pravdepodobnosti určitého počtu udalostí m, ktoré nastanú v časovom období t, môžete použiť Poissonov vzorec:

Pm, n= am_e-a; (m=0,n),

kde hodnota a = pr je priemerný počet udalostí spadajúcich do časového úseku t, ktorý možno určiť pomocou intenzity toku udalostí X takto: a = l f

Dimenzia intenzity toku X je priemerný počet udalostí za jednotku času. Medzi p a l, p a f existuje nasledujúca súvislosť:

n=lt; p = f/t

kde t je celé časové obdobie, počas ktorého sa uvažuje o pôsobení toku udalostí.

Je potrebné určiť rozdelenie časového intervalu T medzi udalosti v takomto toku. Keďže ide o náhodnú premennú, nájdime jej distribučnú funkciu. Ako je známe z teórie pravdepodobnosti, kumulatívna distribučná funkcia F(t) je pravdepodobnosť, že hodnota T bude menšia ako čas t.

F(t)=P(T

Podľa podmienky by v čase T nemala nastať žiadna udalosť a v časovom intervale t by sa mala objaviť aspoň jedna udalosť. Táto pravdepodobnosť sa vypočíta pomocou pravdepodobnosti opačnej udalosti v časovom intervale (0; t), kde nenastala žiadna udalosť, t.j. m = 0, potom

F(t)=1-P0=1-(a0*e-a)0!=1-e-Xt,t?0

Pre malé?t možno získať približný vzorec získaný nahradením funkcie e-Xt iba dvoma členmi expanzie v mocninách?t, potom je pravdepodobnosť, že aspoň jedna udalosť nastane v krátkom časovom období?t

P(T

Hustotu rozdelenia časového intervalu medzi dvoma po sebe nasledujúcimi udalosťami získame diferenciáciou F(t) vzhľadom na čas,

f(t)= le-lt,t?0

Pomocou získanej funkcie hustoty rozdelenia môžete získať číselné charakteristiky náhodnej premennej T: matematické očakávanie M (T), rozptyl D (T) a smerodajnú odchýlku y (T).

M(T) = 100 t*e-It*dt=l/l; D(T) = 1/12; y(T) = 1/1.

Z toho môžeme vyvodiť nasledujúci záver: priemerný časový interval T medzi akýmikoľvek dvoma susednými udalosťami v najjednoduchšom toku je v priemere rovný 1/l a jeho štandardná odchýlka je tiež rovná 1/l, l kde, je intenzita toku, t.j. priemerný počet udalostí vyskytujúcich sa za jednotku času. Zákon rozdelenia náhodnej premennej s takými vlastnosťami M(T) = T sa nazýva exponenciálny (alebo exponenciálny) a hodnota l je parametrom tohto exponenciálneho zákona. Pre najjednoduchší tok sa teda matematické očakávanie časového intervalu medzi susednými udalosťami rovná jeho štandardnej odchýlke. V tomto prípade pravdepodobnosť, že počet prijatých žiadostí o službu počas časového obdobia t sa rovná k, je určená Poissonovým zákonom:

Pk(t)=(лt)k/ k! *e-l t,

kde l je intenzita toku požiadaviek, priemerný počet udalostí v QS za jednotku času, napríklad [osoba/min; rub./hod.; kontroly/hodina; dokument/deň; kg/hod.; t./rok].

Pre takýto tok požiadaviek je čas medzi dvoma susednými požiadavkami T rozdelený exponenciálne s hustotou pravdepodobnosti:

ѓ(t)= l e-l t.

Náhodný čas čakania t vo fronte spustenia služby možno tiež považovať za exponenciálne rozdelený:

? (toch)=V*e-v toch,

kde v je intenzita toku prechodu frontu určená priemerným počtom žiadostí prechádzajúcich na službu za jednotku času:

v=1/bod,

kde Toch je priemerný čas čakania na službu vo fronte.

Výstupný tok požiadaviek je spojený s tokom služieb v kanáli, kde trvanie služby tobs je tiež náhodná premenná a v mnohých prípadoch sa riadi zákonom exponenciálneho rozdelenia s hustotou pravdepodobnosti:

?(t obs)=µ*e µt obs,

kde µ je intenzita servisného toku, t.j. priemerný počet žiadostí obsluhovaných za jednotku času:

u = 1/ t obs[osoba/min; rub./hod.; kontroly/hodina; dokument/deň; kg/hod.; t./rok] ,

kde t obs je priemerný čas na obsluhu požiadaviek.

Dôležitou charakteristikou QS, ktorá kombinuje ukazovatele l a µ, je intenzita zaťaženia: c = l/ µ, ktorá ukazuje stupeň koordinácie vstupných a výstupných tokov požiadaviek obslužného kanála a určuje stabilitu systému radenia. .

Okrem konceptu najjednoduchšieho prúdu udalostí je často potrebné použiť aj koncepty prúdov iných typov. Prúd udalostí sa nazýva Palma prúd, keď v tomto prúde sú časové intervaly medzi po sebe nasledujúcimi udalosťami T1, T2, ..., Tk ..., Tn nezávislé, identicky rozdelené, náhodné premenné, ale na rozdiel od najjednoduchšieho prúdu sú nemusia byť nevyhnutne rozdelené podľa exponenciálneho zákona. Najjednoduchší tok je špeciálny prípad toku Palm.

Dôležitým špeciálnym prípadom Palmového prúdu je takzvaný Erlangov prúd.

Tento tok sa získa „zriedením“ najjednoduchšieho toku. Toto „preriedenie“ sa vykonáva výberom udalostí z najjednoduchšieho toku podľa určitého pravidla.

Napríklad, ak sme súhlasili s tým, že budeme brať do úvahy iba každú druhú udalosť tvoriacu najjednoduchší tok, získame Erlangov tok druhého rádu. Ak vezmeme len každú tretiu udalosť, potom sa vytvorí Erlangov tok tretieho rádu atď.

Je možné získať prúdy Erlang akéhokoľvek k-tého rádu. Je zrejmé, že najjednoduchší tok je Erlangov tok prvého rádu.

Akákoľvek štúdia systému radenia začína štúdiom toho, čo je potrebné obsluhovať, teda štúdiom prichádzajúcich aplikácií a ich charakteristík.

Keďže časové momenty t a časové intervaly prijatia požiadaviek f, potom trvanie servisných operácií t obs a čakacia doba vo fronte toch, ako aj dĺžka frontu loch sú náhodné premenné, potom sú charakteristiky stavy QS majú pravdepodobnostný charakter a na ich popis je potrebné použiť metódy a modely teórie radenia.

Charakteristiky uvedené vyššie k, f, l, Loch, Toch, v, tobs, µ, p, Pk sú najčastejšie pre QS, ktoré sú zvyčajne len časťou účelovej funkcie, pretože je potrebné vziať do úvahy aj ukazovatele obchodnej činnosti.

1 . 3 Najjednoduchšie QS s poruchami

n-kanálový QS s poruchami prijíma najjednoduchší tok požiadaviek s intenzitou n; doba prevádzky je orientačná pre parameter. Stavy QS sú očíslované podľa počtu požiadaviek nachádzajúcich sa v QS (kvôli absencii frontu sa zhoduje s počtom obsadených kanálov):

S0 - QS je zadarmo;

S1 - jeden kanál je obsadený, zvyšok je voľný;

...;

S k- zaneprázdnený k kanály, ostatné sú zadarmo (1 kn);

…;

S n- všetci sú zaneprázdnení n kanály.

Konečné pravdepodobnosti stavov vyjadrujú Erlangove vzorce:

kde s=l/m.

Charakteristiky účinnosti:

A=(1-p n); Q = 1 p n; Ptk= str n; =(1-p n).

Pre veľké hodnoty P pravdepodobnosti stavu (1*) sa pohodlne vypočítavajú pomocou tabuľkových funkcií:

(Poissonovo rozdelenie) a

,

z ktorých prvé možno vyjadriť prostredníctvom druhého:

Pomocou týchto funkcií je možné do formulára prepísať vzorce Erlang (1*).

.

1.4 Jednokanálový QS s poruchami

Analyzujme jednoduchý jednokanálový QS s poruchami služby, ktorý prijíma Poissonov tok požiadaviek s intenzitou l a servis prebieha pod vplyvom Poissonovho toku s intenzitou m.

Činnosť jednokanálového QS n=1 možno znázorniť vo forme označeného stavového grafu (3.1).

Prechody QS z jedného stavu S0 do druhého S1 nastávajú vplyvom vstupného toku požiadaviek s intenzitou l a spätný prechod nastáva vplyvom obslužného toku s intenzitou m.

Zapíšme si systém Kolmogorovových diferenciálnych rovníc pre pravdepodobnosti stavu podľa vyššie uvedených pravidiel:

Kde získame diferenciálnu rovnicu na určenie pravdepodobnosti p0(t) stavu S0:

Túto rovnicu je možné riešiť za počiatočných podmienok za predpokladu, že systém v momente t=0 bol v stave S0, potom p0(0)=1, p1(0)=0.

V tomto prípade nám riešenie diferenciálnej rovnice umožňuje určiť pravdepodobnosť, že kanál je voľný a nie je zaneprázdnený službou:

Potom je ľahké získať výraz pre pravdepodobnosť určenia pravdepodobnosti obsadenosti kanála:

Pravdepodobnosť p0(t) klesá v čase a v limite pri t>? inklinuje k hodnote

a pravdepodobnosť p1(t) sa súčasne zvyšuje z 0, pričom smeruje k limitu pri t>? na veľkosť

Tieto limity pravdepodobnosti možno získať priamo z Kolmogorovových rovníc

Funkcie р0(t) a р1(t) definujú prechodový proces v jednokanálovom QS a popisujú proces exponenciálneho približovania sa QS k jeho medznému stavu s časovou konštantou charakteristikou posudzovaného systému.

S dostatočnou presnosťou pre prax môžeme predpokladať, že proces prechodu v QS skončí v čase rovnajúcom sa 3f.

Pravdepodobnosť p0(t) určuje relatívnu kapacitu QS, ktorá určuje podiel obsluhovaných aplikácií vo vzťahu k celkovému počtu prichádzajúcich aplikácií za jednotku času.

V skutočnosti p0(t) je pravdepodobnosť, že požiadavka prichádzajúca v čase t bude prijatá na službu. Celkovo príde priemerne l aplikácií za jednotku času a obslúži sa lr0 aplikácií.

Potom bude podiel obsluhovaných aplikácií vo vzťahu k celému toku aplikácií určený hodnotou

V limite pri t>? prakticky už pri t>3ph bude hodnota relatívnej priepustnosti rovná

Absolútna priepustnosť, ktorá určuje počet obsluhovaných požiadaviek za jednotku času v limite t>?, sa rovná:

Podiel žiadostí, ktoré boli zamietnuté, je teda za rovnakých obmedzujúcich podmienok:

a celkový počet neobsluhovaných aplikácií sa rovná

Príklady jednokanálových QS s odmietnutiami služby sú: objednávkový pult v predajni, dispečing podniku motorovej dopravy, skladová kancelária, kancelária vedenia obchodnej spoločnosti, s ktorou je komunikácia nadviazaná telefonicky.

1.5 Viackanálové QS s poruchami

V komerčných činnostiach sú príkladmi viackanálového QS kancelárie obchodných podnikov s niekoľkými telefónnymi kanálmi; bezplatná asistenčná služba pre dostupnosť najlacnejších automobilov v predajniach automobilov v Moskve má 7 telefónnych čísel, a ako je známe, je to je veľmi ťažké zavolať a získať pomoc.

V dôsledku toho strácajú predajne áut zákazníkov, možnosť zvýšiť počet predaných áut a tržby z predaja, obrat a zisk.

Cestovné spoločnosti, ktoré predávajú zájazdy, majú dva, tri, štyri alebo viac kanálov, ako napríklad Express-Line.

Uvažujme viackanálový QS s poruchami služby, ktorého vstup prijíma Poissonov tok požiadaviek s intenzitou l.

Obslužný tok v každom kanáli má intenzitu m. Na základe počtu požiadaviek QS sa určia jeho stavy Sk, prezentované vo forme označeného grafu:

S0 - všetky kanály sú voľné k=0,

S1 - iba jeden kanál je obsadený, k=1,

S2 - obsadené sú len dva kanály, k=2,

Sk - k kanály sú obsadené,

Sn - všetkých n kanálov je obsadených, k= n.

Stavy viackanálového QS sa menia náhle v náhodných časoch. Prechod z jedného stavu, napríklad S0 do S1, nastáva pod vplyvom vstupného toku požiadaviek s intenzitou l a naopak - pod vplyvom toku servisných požiadaviek s intenzitou m.

Pre prechod sústavy zo stavu Sk na Sk-1 nezáleží na tom, ktorý kanál sa uvoľní, preto tok udalostí, ktorý prenáša QS má intenzitu km, preto tok udalostí, ktorý prenáša systém zo Sn. do Sn-1 má intenzitu nm.

Takto je formulovaný klasický Erlangov problém, pomenovaný po dánskom inžinierovi a matematikovi, ktorý založil teóriu radenia.

Náhodný proces vyskytujúci sa v QS je špeciálnym prípadom procesu „narodenie-smrť“ a je opísaný systémom Erlangových diferenciálnych rovníc, ktoré umožňujú získať vyjadrenia pre limitné pravdepodobnosti stavu posudzovaného systému, nazývané Erlangove vzorce:

.

Výpočtom všetkých pravdepodobností stavov n-kanálového QS s poruchami p0, p1, p2, ..., pk,..., pn môžeme nájsť charakteristiky servisného systému.

Pravdepodobnosť odmietnutia služby je určená pravdepodobnosťou, že prichádzajúca požiadavka na službu nájde všetkých n kanálov obsadených, systém bude v stave Sn:

k=n.

V systémoch s poruchami tvoria poruchy a udalosti údržby kompletnú skupinu udalostí, preto:

Rotk + Robs = 1

Na tomto základe je relatívna priepustnosť určená vzorcom

Q = Pobs = 1-Rotk = 1-Pn

Absolútnu kapacitu QS možno určiť podľa vzorca

A=l*Robs

Pravdepodobnosť služby alebo podiel obsluhovaných požiadaviek určuje relatívnu kapacitu QS, ktorú možno určiť pomocou iného vzorca:

Z tohto výrazu môžete určiť priemerný počet žiadostí v rámci služby alebo, čo je rovnaké, priemerný počet kanálov obsadených službou

Miera obsadenosti kanálov službou je určená pomerom priemerného počtu obsadených kanálov k ich celkovému počtu

Pravdepodobnosť obsadenia kanálov službou, ktorá berie do úvahy priemerný čas obsadenosti tobsadené a nečinnosti tpr kanálov, sa určuje takto:

Z tohto výrazu môžete určiť priemerné prestoje kanálov

Priemerný čas, počas ktorého požiadavka zostáva v systéme v ustálenom stave, je určený Littleovým vzorcom

Tsmo= nz/l.

1.6 Jednokanálový QS s obmedzenou dĺžkou frontu

V komerčných činnostiach je bežnejší QS s čakaním (poradie).

Uvažujme jednoduchý jednokanálový QS s obmedzeným frontom, v ktorom je počet miest v rade m pevnou hodnotou. V dôsledku toho žiadosť prijatá v čase, keď sú všetky miesta v rade obsadené, nie je prijatá na obsluhu, nezaradí sa do radu a opustí systém.

Graf tohto QS je znázornený na obr. 3.4 a zhoduje sa s grafom na obr. 2.1 popisujúci proces „narodenie-smrť“, s tým rozdielom, že v prítomnosti iba jedného kanála.

Označený graf procesu „narodenie - smrť“ služby, všetky intenzity tokov služieb sú rovnaké

Stavy QS možno znázorniť takto:

S0 - servisný kanál je bezplatný,

S, - servisný kanál je zaneprázdnený, ale nie je tam žiadny front,

S2 - servisný kanál je zaneprázdnený, vo fronte je jedna požiadavka,

S3 - servisný kanál je zaneprázdnený, vo fronte sú dve požiadavky,

Sm+1 - obslužný kanál je obsadený, všetkých m miest vo fronte je obsadených, akákoľvek následná požiadavka je zamietnutá.

Na opísanie náhodného procesu QS môžete použiť vyššie uvedené pravidlá a vzorce. Napíšme výrazy, ktoré určujú limitné pravdepodobnosti stavov:

Výraz pre p0 možno v tomto prípade zapísať jednoduchším spôsobom s využitím skutočnosti, že menovateľ obsahuje geometrickú postupnosť vzhľadom na p, potom po príslušných transformáciách dostaneme:

c= (1- s)

Tento vzorec platí pre všetky p iné ako 1, ale ak p = 1, potom p0 = 1/(m + 2) a všetky ostatné pravdepodobnosti sa tiež rovnajú 1/(m + 2).

Ak predpokladáme m = 0, prejdeme od uvažovania jednokanálového QS s čakaním k už uvažovanému jednokanálovému QS s odmietnutím služby.

Skutočne, výraz pre hraničnú pravdepodobnosť p0 v prípade m = 0 má tvar:

po = m / (l+m)

A v prípade l = m má hodnotu p0 = 1 / 2.

Stanovme hlavné charakteristiky jednokanálového QS s čakaním: relatívna a absolútna priepustnosť, pravdepodobnosť zlyhania, ako aj priemerná dĺžka frontu a priemerný čas čakania na aplikáciu vo fronte.

Žiadosť je odmietnutá, ak príde v čase, keď je QS už v stave Sm+1, a teda všetky miesta vo fronte sú obsadené a jeden kanál obsluhuje

Pravdepodobnosť poruchy je teda určená pravdepodobnosťou výskytu

Sm+1 uvádza:

Ptk = pm+1 = сm+1 * p0

Relatívna priepustnosť alebo podiel obsluhovaných požiadaviek prichádzajúcich za jednotku času je určený výrazom

Q = 1- rotk = 1- cm+1 * p0

absolútna priepustnosť je:

Priemerný počet žiadostí L vo fronte na službu je určený matematickým očakávaním náhodnej premennej k - počtu žiadostí vo fronte

Náhodná premenná k nadobúda iba nasledujúce celočíselné hodnoty:

1 - vo fronte je jedna aplikácia,

2 - vo fronte sú dve aplikácie,

t-všetky miesta v poradí sú obsadené

Pravdepodobnosti týchto hodnôt sú určené zodpovedajúcimi pravdepodobnosťami stavov, počnúc stavom S2. Distribučný zákon diskrétnej náhodnej premennej k je znázornený takto:

Tabuľka 1. Distribučný zákon diskrétnej náhodnej premennej

Matematické očakávanie tejto náhodnej premennej je:

Loch = 1* p2 +2* p3 +...+ m* pm+1

Vo všeobecnom prípade pre p < 1 možno tento súčet transformovať pomocou modelov geometrickej postupnosti na vhodnejšiu formu:

Loch = p2 * 13:00 * (m-m*p+1)* p0

V špeciálnom prípade, keď p = 1, keď sú všetky pravdepodobnosti pk rovnaké, môžete použiť výraz pre súčet členov číselného radu

1+2+3+ m = m(m+1)

Potom dostaneme vzorec

L"och= m(m+1)* p0 = m(m+1)(p=1).

Použitím podobných úvah a transformácií je možné ukázať, že priemerný čas čakania na vybavenie požiadavky vo fronte je určený Littleovými vzorcami

Bod = Loch/A (pri p = 1) a T1och = L"och/A (pri p = 1).

Tento výsledok, keď sa ukáže, že Toc ~ 1/l, sa môže zdať zvláštny: so zvyšujúcou sa intenzitou toku aplikácií sa zdá, že dĺžka frontu sa zvyšuje a priemerná čakacia doba sa znižuje. Treba však mať na pamäti, že po prvé, hodnota Loch je funkciou lam a po druhé, uvažovaný QS má obmedzenú dĺžku frontu na maximálne m aplikácií.

Žiadosť prijatá QS v čase, keď sú všetky kanály obsadené, je odmietnutá, a preto je jej „čakací“ čas v QS nulový. To vedie vo všeobecnom prípade (pre p? 1) k poklesu Tochromostu l, keďže podiel takýchto žiadostí stúpa so zvyšujúcim sa l.

Ak upustíme od obmedzenia dĺžky frontu, t.j. priamy m--> >?, potom prípady p< 1 и р?1 начинают существенно различаться. Записанные выше формулы для вероятностей состояний преобразуются в случае р < 1 к виду

Keď je k dostatočne veľké, pravdepodobnosť pk má tendenciu k nule. Preto bude relatívna priepustnosť Q = 1 a absolútna priepustnosť sa bude rovnať A --l Q -- l Všetky prichádzajúce požiadavky sú teda obsluhované a priemerná dĺžka frontu sa bude rovnať:

Loch = p2 1-p

a priemerná doba čakania podľa Littleovho vzorca

Bod = Loch/A

V limite p<< 1 получаем Точ = с / м т.е. среднее время ожидания быстро уменьшается с увеличением интенсивности потока обслуживания. В противном случае при р? 1 оказывается, что в СМО отсутствует установившийся режим. Обслуживание не успевает за потоком заявок, и очередь неограниченно растет со временем (при t >?). Limitné pravdepodobnosti stavov teda nemožno určiť: pre Q = 1 sa rovnajú nule. V skutočnosti QS neplní svoje funkcie, pretože nie je schopný obsluhovať všetky prichádzajúce aplikácie.

Nie je ťažké určiť, že podiel obsluhovaných aplikácií a absolútna priepustnosť sú v priemere c a m, avšak neobmedzený nárast fronty, a teda čakacej doby v nej vedie k tomu, že po určitom čase časové aplikácie sa začnú hromadiť vo fronte na nekonečne dlhý čas.

Ako jedna z charakteristík QS sa používa priemerný čas Tsmo zotrvania aplikácie v QS vrátane priemerného času stráveného vo fronte a priemerného času služby. Táto hodnota sa vypočíta pomocou Littleových vzorcov: ak je dĺžka frontu obmedzená, priemerný počet aplikácií vo fronte sa rovná:

Lsmo= m+1 ;2

Tsmo= Lsmo; na p?1

A potom sa priemerný čas, počas ktorého požiadavka zostane v systéme zaraďovania (vo fronte aj v rámci služby), rovná:

Tsmo= m+1 pri p < 1 2 m

1.7 Jednokanálový QS s neobmedzeným frontom

V obchodných činnostiach napríklad obchodný riaditeľ vystupuje ako jednokanálový CMO s neobmedzeným čakaním, pretože je spravidla nútený vybavovať žiadosti rôzneho charakteru: dokumenty, telefonické rozhovory, stretnutia a rozhovory s podriadenými, zástupcami daňová inšpekcia, polícia, komoditní experti, marketéri, dodávatelia produktov a riešiť problémy v komoditno-finančnej sfére s vysokou mierou finančnej zodpovednosti, ktorá je spojená s povinným plnením požiadaviek, ktoré niekedy netrpezlivo čakajú na splnenie svojich požiadaviek, chyby nesprávnej obsluhy sú spravidla ekonomicky veľmi významné. Model údržby Markovovho zlyhania

Zároveň tovar dovážaný na predaj (služba) v sklade tvorí rad na obsluhu (predaj).

Dĺžka frontu je počet tovaru určeného na predaj. V tejto situácii predajcovia vystupujú ako kanály obsluhujúce tovar.

Ak je množstvo tovaru určeného na predaj veľké, tak v tomto prípade máme do činenia s typickým prípadom QS s čakaním.

Uvažujme najjednoduchší jednokanálový QS s čakaním na obsluhu, ktorý prijíma Poissonov tok požiadaviek s intenzitou l a intenzitou obsluhy?.

Okrem toho sa požiadavka prijatá v čase, keď je kanál zaneprázdnený obsluhou, zaradí do frontu a čaká na obsluhu.

Označený stavový graf takéhoto systému je znázornený na obr. 3.5

Počet možných stavov je nekonečný:

Kanál je voľný, nie je tam žiadny front, ;

Kanál je zaneprázdnený službou, nie je tam žiadny front, ;

Kanál je obsadený, jedna požiadavka vo fronte, ;

Kanál je zaneprázdnený, aplikácia je vo fronte.

Modely na odhad pravdepodobnosti stavov QS s neobmedzeným frontom je možné získať zo vzorcov pridelených pre QS s neobmedzeným frontom prechodom na limit pri m>?:

Treba poznamenať, že pre QS s obmedzenou dĺžkou frontu vo vzorci

existuje geometrická postupnosť s prvým členom 1 a menovateľom.

Takáto postupnosť je súčtom nekonečného počtu členov at.

Tento súčet konverguje, ak progresia, ktorá nekonečne klesá pri, ktorý určuje prevádzkový režim QS v ustálenom stave, s frontom pri môže časom rásť do nekonečna.

Keďže v uvažovanom QS neexistuje žiadne obmedzenie na dĺžku frontu, môže byť obsluhovaná akákoľvek požiadavka, teda relatívna priepustnosť a absolútna priepustnosť

Pravdepodobnosť, že k aplikácií je vo fronte, je:

Priemerný počet aplikácií vo fronte -

Priemerný počet aplikácií v systéme -

Priemerný čas, počas ktorého aplikácia zostáva v systéme -

Priemerný čas, počas ktorého aplikácia zostáva v systéme -

Ak v jednokanálovom QS s čakaním je intenzita prijatých požiadaviek väčšia ako intenzita služby, potom sa front neustále zvyšuje. V tomto ohľade analýza stabilných systémov QS pracujúcich v stacionárnom režime pri.

1.8 Viackanálové QS s obmedzenou dĺžkou frontu

Uvažujme viackanálový QS, ktorého vstup prijíma Poissonov tok požiadaviek s intenzitou a intenzita obsluhy každého kanála je, maximálny možný počet miest vo fronte je obmedzený m. Diskrétne stavy QS sú určené počtom žiadostí prijatých systémom, ktoré je možné zaznamenať.

Všetky kanály sú bezplatné;

Len jeden kanál (akýkoľvek) je obsadený;

Len dva kanály (akékoľvek) sú obsadené;

Všetky kanály sú obsadené.

Kým je QS v ktoromkoľvek z týchto stavov, nie je tam žiadny front. Po obsadení všetkých obslužných kanálov tvoria nasledujúce požiadavky front, čím sa určí ďalší stav systému:

Všetky kanály sú zaneprázdnené a jedna aplikácia je vo fronte,

Všetky kanály sú zaneprázdnené a dve požiadavky sú vo fronte,

Všetky kanály a všetky miesta vo fronte sú obsadené,

Prechod QS do stavu s veľkými číslami je určený tokom prichádzajúcich požiadaviek s intenzitou, pričom podľa podmienok sa na obsluhe týchto požiadaviek podieľajú identické kanály s rovnakou intenzitou obslužného toku pre každý kanál. V tomto prípade sa celková intenzita toku služieb zvyšuje s pripájaním nových kanálov až do stavu, keď je všetkých n kanálov obsadených. S objavením sa frontu sa intenzita služby ďalej zvyšuje, pretože už dosiahla maximálnu hodnotu rovnajúcu sa.

Zapíšme si výrazy pre limitné pravdepodobnosti stavov:

Výraz pre možno transformovať pomocou vzorca geometrickej postupnosti pre súčet členov s menovateľom:

Vytvorenie frontu je možné vtedy, keď novoprijatá žiadosť nájde v systéme aspoň požiadavky, t.j. keď sú v systéme požiadavky.

Tieto udalosti sú nezávislé, takže pravdepodobnosť, že všetky kanály sú obsadené, sa rovná súčtu zodpovedajúcich pravdepodobností

Pravdepodobnosť, že sa vytvorí rad, je teda:

Pravdepodobnosť odmietnutia služby nastane, keď sú obsadené všetky kanály a všetky miesta vo fronte:

Relatívna priepustnosť sa bude rovnať:

Absolútna priepustnosť -

Priemerný počet obsadených kanálov -

Priemerný počet nečinných kanálov -

Faktor obsadenosti (využívania) kanála -

Pomer prestojov kanála -

Priemerný počet žiadostí vo fronte -

Ak má tento vzorec inú formu -

Priemerná doba čakania vo fronte je určená Littleovým vzorcom -

Priemerný čas zotrvania aplikácie v QS, ako v prípade jednokanálového QS, je väčší ako priemerný čas čakania vo fronte o priemerný čas služby, ktorý je rovnaký, pretože aplikácia je vždy obsluhovaná iba jedným kanálom:

1.9 Viackanálové QS s neobmedzeným frontom

Uvažujme viackanálový QS s čakaním a neobmedzenou dĺžkou frontu, ktorý prijíma tok požiadaviek s intenzitou a ktorý má intenzitu obsluhy každého kanála.

Označený graf stavu je znázornený na obrázku 3.7. Má nekonečný počet stavov:

S - všetky kanály sú voľné, k=0;

S - jeden kanál je obsadený, zvyšok je voľný, k=1;

S - dva kanály sú obsadené, zvyšok je voľný, k=2;

S - všetkých n kanálov je obsadených, k=n, žiadny front;

S - všetkých n kanálov je obsadených, jedna požiadavka je vo fronte, k=n+1,

S - všetkých n kanálov je obsadených, r aplikácií je vo fronte, k=n+r,

Pravdepodobnosti stavu získame zo vzorcov pre viackanálový QS s obmedzeným frontom pri prechode na limit pri m.

Treba poznamenať, že súčet geometrickej progresie vo výraze pre p sa rozchádza pri úrovni zaťaženia p/n>1, front sa bude zvyšovať donekonečna a pri p/n<1 ряд сходится, что определяет установившийся стационарный режим работы СМО.

Žiadny rad

Keďže v takýchto systémoch nemôže dôjsť k odmietnutiu služby, charakteristiky priepustnosti sa rovnajú:

priemerný počet žiadostí vo fronte -

priemerná doba čakania v rade -

priemerný počet žiadostí o SOT -

Pravdepodobnosť, že QS je v stave, v ktorom nie sú žiadne požiadavky a nie sú obsadené žiadne kanály, je určená výrazom

Táto pravdepodobnosť určuje priemerné percento prestojov servisného kanála. Pravdepodobnosť, že budete zaneprázdnení obsluhou k žiadostí -

Na tomto základe je možné určiť pravdepodobnosť alebo podiel času, počas ktorého sú všetky kanály obsadené službou

Ak sú všetky kanály už obsadené servisom, pravdepodobnosť stavu je určená výrazom

Pravdepodobnosť, že budete vo fronte, sa rovná pravdepodobnosti nájdenia všetkých kanálov, ktoré sú už obsadené službou

Priemerný počet aplikácií vo fronte a čakajúcich na službu je:

Priemerná doba čakania na žiadosť vo fronte podľa Littleovho vzorca:

a v systéme

priemerný počet kanálov obsadených službou:

priemerný počet bezplatných kanálov:

pomer obsadenosti servisných kanálov:

Je dôležité poznamenať, že parameter charakterizuje mieru koordinácie vstupného toku, napríklad zákazníkov v predajni s intenzitou toku služieb. Servisný proces bude stabilný, ak sa však v systéme predĺži priemerná dĺžka frontu a priemerná doba čakania na začatie služby zákazníkom, a preto bude systém služieb pracovať nestabilne.

1.10 Algoritmus modelovania QS

QS uvažovaný v tomto probléme je QS s:

Dvojkanálová služba;

Dvojkanálový vstupný tok (má 2 vstupy, z ktorých jeden prijíma náhodný tok príkazov I, druhý vstup prijíma tok príkazov II).

Určenie časov prijímania a obsluhy žiadostí:

· Časy prijatia a obsluhy požiadaviek sa generujú náhodne s daným zákonom o exponenciálnom rozdelení;

· Sadzby za príjem a obsluhu žiadostí sú špecifikované;

Fungovanie uvažovaného QS:

Každý kanál obsluhuje jednu požiadavku naraz;

Ak je v čase prijatia novej požiadavky aspoň jeden kanál voľný, potom je prichádzajúca požiadavka prijatá na službu;

Ak neexistujú žiadne aplikácie, systém je nečinný.

Servisná disciplína:

Priorita príkazov I: ak je systém zaneprázdnený (oba kanály obsluhujú príkazy) a jeden z kanálov je obsadený príkazom II, príkaz I predíde príkazu II; Požiadavka II ponechá systém neobslúžený;

Ak v čase príchodu požiadavky II sú obidva kanály obsadené, požiadavka II nie je obsluhovaná;

Ak v čase, keď príde Objednávka I, oba kanály obsluhujú Objednávky I, prijatá Objednávka I zostane zo systému neobslúžená;

Úloha modelovania: poznať parametre vstupných tokov požiadaviek, simulovať správanie systému a vypočítať jeho hlavné charakteristiky jeho účinnosti. Zmenou hodnoty T z menších hodnôt na väčšie (časový interval, počas ktorého dochádza k náhodnému procesu prijímania žiadostí 1. a 2. toku v QS do servisu), môžete nájsť zmeny v kritériu prevádzkovej efektívnosti. a vyberte tú optimálnu.

Kritériá efektívnosti fungovania QS:

· Pravdepodobnosť zlyhania;

· Relatívna priepustnosť;

· Absolútna priepustnosť;

Princíp modelovania:

Zavádzame počiatočné podmienky: celkový prevádzkový čas systému, hodnoty intenzity aplikačných tokov; počet implementácií systému;

Generujeme časové body, v ktorých prichádzajú požiadavky, postupnosť príchodu Žiadostí I, Žiadostí II, čas obsluhy každej prichádzajúcej požiadavky;

Počítame, koľko žiadostí bolo obsluhovaných a koľko bolo zamietnutých;

Vypočítame kritérium účinnosti QS;

KAPITOLA2 . PRAKTICKÁ ČASŤ

Obrázok 1. Závislosť OPSS od času

PROGRAM CAN_SMO;

CHANNAL = (ZADARMO, NÁROK1, NÁROK2);

INTENZITA = slovo;

ŠTATISTIKA = slovo;

CHANNAL1, CHANNAL2: CHANNAL;(Kanály)

T_, t, tc1, tc2: TIME; (čas)

l1, l2, n1, n2: INTENZITA; (Intenzita)

slúžil1, neslúžil1,

slúžil2, neslúžil2,

S: ŠTATISTIKA; (štatistika)

M,N:INTEGER;(počet implementácií)

FUNKCIA W(t: ČAS; l: INTENZITA) : boolean; (určuje, či sa objednávka objavila)

Začať (podľa intenzity prietoku l)

ak náhodne< l/60 then W:= TRUE else W:= FALSE;

FUNKCIA F(t: ČAS; n: INTENZITA) : ČAS; (Určuje, ako dlho bude žiadosť spracovávaná)

Začať (podľa intenzity servisných požiadaviek n)

F:= t+okrúhle(60/(n));

Obrázok 2. Závislosť OPPS od času

WRITELN("ZADAJ POČET IMPLEMENTÁCIÍ SMO");

writeln(M, "tá implementácia");

CHANNAL1:= ZDARMA; CHANNAL2:= ZDARMA;

11:= 3; 12:= 1; n1:= 2; n2:= 1;

slúžil1:= 0; not_served1:= 0;

slúžil2:= 0; not_served2:= 0;

write("Zadajte čas štúdia SMO - T: "); readln(_T_);

ak CHANNAL1 = CLAIM1 then inc(served1) else inc(served2);

CHANNAL1:= ZDARMA;

writeln("Kanál1 dokončil požiadavku");

ak CHANNAL2 = CLAIM1 then inc(served1) else inc(served2);

CHANNAL2:= ZDARMA;

writeln("Kanál2 dokončil požiadavku");

Obrázok 3. Graf pravdepodobnosti zlyhania systému v závislosti od času

writeln("Prijatá požiadavka1");

ak CHANNAL1 = ZDARMA, potom

begin CHANNAL1:= CLAIM1; tcl:= F(t,n1); writeln("Kanál1 akceptovaná požiadavka1"); koniec

inak, ak CHANNAL2 = ZADARMO

begin CHANNAL2:= CLAIM1; tc2:= F(t,n1); writeln("Kanál2 akceptovaná požiadavka1"); koniec

inak, ak CHANNAL1 = CLAIM2 potom

begin CHANNAL1:= CLAIM1; tcl:= F(t,n1); inc(not_served2); writeln("Kanál1 akceptoval požiadavku1 namiesto požiadavky2"); koniec

inak, ak CHANNAL2 = CLAIM2 potom

begin CHANNAL2:= CLAIM1; tc2:= F(t,n1); inc(not_served2); writeln("Kanál2 akceptoval požiadavku1 namiesto požiadavky2"); koniec

else begin inc(not_served1); writeln("požiadavka 1 nie je obsluhovaná"); koniec;

Obrázok 4. Závislosť počtu aplikácií od času

writeln("Žiadosť2 prijatá");

ak CHANNAL1 = ZDARMA, potom

begin CHANNAL1:= CLAIM2; tcl:= F(t,n2); writeln("Kanál1 akceptovaná požiadavka2");koniec

inak, ak CHANNAL2 = ZADARMO

begin CHANNAL2:= CLAIM2; tc2:= F(t,n2); writeln("Kanál2 akceptovaná požiadavka2");koniec

else begin inc(not_served2); writeln("požiadavka2 nie je obsluhovaná"); koniec;

S:= obsluhované1 + neservírované1 + obsluhované2 + neservírované2;

writeln("doba prevádzky SMO ",_T_);

writeln("obsluha kanalom1: " ,obsluha1);

writeln("obsluhovane channel2: ",served2);

writeln("Prijaté požiadavky: ",S);

writeln("Požiadavky doručené: ",served1+served2);

writeln("Požiadavky neboli doručené: ",not_served1+not_service2);

(writeln("Intenzita požiadaviek vstupujúcich do systému: ",(obsluhované1+obsluhované2)/_T_:2:3);)

writeln("Absolútna priepustnosť systému: ",(obsluhované1+obsluhované2)/T:2:3);

writeln("Pravdepodobnosť zlyhania: ",(neobsluhované1+neobsluhované2)/S*100:2:1,"%");

writeln("Relatívna priepustnosť systému: ",(obsluhované1+obsluhované2)/S:2:3);

writeln("simulácia dokončená");

Tabuľka 2. Výsledky práce QS

Charakteristika fungovania QS

Prevádzková doba SMO

Prijaté prihlášky

Prihlášky doručené

Neboli doručené žiadne žiadosti

Absolútna priepustnosť systému

Relatívna priepustnosť systému

KAPITOLA 3.BEZPEČNOSTNÉ PREDPISY

Všeobecné ustanovenia

· V počítačovej učebni môžu pracovať osoby, ktoré sú oboznámené s bezpečnostnými pokynmi a pravidlami správania.

· V prípade porušenia pokynov je študent pozastavený z práce a môže študovať len s písomným súhlasom vyučujúceho.

· Práca študentov v počítačovej učebni je povolená len v prítomnosti vyučujúceho (inžinier, laborant).

· Pamätajte, že každý žiak je zodpovedný za stav svojho pracoviska a bezpečnosť zariadení na ňom umiestnených.

Pred začatím práce:

· Pred začatím práce sa uistite, že nie je viditeľné poškodenie zariadenia a káblov. Počítače a periférne zariadenia musia byť umiestnené v stabilnej polohe na stoloch.

· Žiakom je vstup do zariadení prísne zakázaný. Zariadenia môžete zapnúť iba so súhlasom učiteľa.

Pri práci v počítačovej triede je zakázané:

1. Vstup a odchod do triedy bez súhlasu učiteľa.

2. Príďte neskoro na hodinu.

3. V chladnom období vstupujte do triedy v špinavých a mokrých topánkach, zaprášenom oblečení a vrchnom oblečení.

4. Pracujte na počítači s mokrými rukami.

5. Umiestnite cudzie predmety na pracovisko.

6. Pri práci vstaňte, otočte sa, porozprávajte sa so susedom.

7. Zapnite a vypnite zariadenie bez súhlasu učiteľa.

8. Porušte postup zapínania a vypínania zariadenia.

9. Dotknite sa klávesnice a myši, keď je počítač vypnutý, premiestnite nábytok a vybavenie.

10. Dotknite sa obrazovky displeja, káblov, spojovacích vodičov, konektorov, zástrčiek a zásuviek.

11. Bez povolenia sa približujte na pracovisko učiteľa

Hlavnou hrozbou pre ľudské zdravie pri práci s PC je hrozba úrazu elektrickým prúdom. Preto je zakázané:

1. Pracujte na zariadení, ktoré má viditeľné chyby. Otvorte systémovú jednotku.

2. Pripojte alebo odpojte káble, dotykové konektory spojovacích káblov, vodičov a zásuviek, uzemňovacie zariadenia.

3. Dotknite sa obrazovky a zadnej strany monitora a klávesnice.

4. Pokúste sa sami odstrániť poruchy zariadenia.

5. Pracujte vo vlhkom oblečení a mokrých rukách

6. Spĺňať požiadavky učiteľa a laboranta; Udržujte ticho a poriadok;

7. V režime online pracujte iba pod svojím menom a heslom;

8. Dodržujte prevádzkový režim (v súlade s hygienickými predpismi a normami);

9. Začať a ukončiť prácu len s povolením vyučujúceho.

10. Ak dôjde k prudkému zhoršeniu zdravotného stavu (bolestivosť očí, prudké zhoršenie viditeľnosti, nemožnosť zaostrenia alebo zbystrenia pohľadu, bolesť prstov a rúk, zvýšený tep), okamžite opustite pracovisko, udalosť nahláste na učiteľa a poraďte sa s lekárom;

11. Udržujte pracovisko čisté.

12. Dokončite prácu so súhlasom učiteľa.

13. Odovzdajte hotové dielo.

14. Ukončite všetky aktívne programy a správne vypnite počítač.

15. Urobte poriadok na pracovisku.

16. Služobný úradník by mal skontrolovať pripravenosť kancelárie na ďalšiu vyučovaciu hodinu.

Pri prevádzke zariadenia si musíte dávať pozor na: - zásah elektrickým prúdom;

- mechanické poškodenie, poranenia

V prípade núdze:

1. Ak sa zistí iskrenie, objaví sa zápach spáleniny alebo sa zistia iné problémy, mali by ste okamžite prestať pracovať a informovať učiteľa.

2. Ak niekoho zasiahne elektrický šok, je potrebné: zastaviť prácu a presunúť sa do bezpečnej vzdialenosti; vypnite napätie (na skriňovom rozvádzači); informovať učiteľa; Pokračujte v prvej pomoci a privolajte lekára.

3. V prípade požiaru je potrebné: zastaviť práce a začať evakuáciu; informovať učiteľa a zavolať hasičov (tel. 01); vypnite napätie (na skriňovom rozvádzači); Pokračujte v hasení požiaru hasiacim prístrojom (hasenie vodou je zakázané).

Podobné dokumenty

Matematická teória radenia ako odvetvie teórie náhodných procesov. Systémy radenia pre požiadavky prichádzajúce v intervaloch. Otvorená Markovova sieť, jej nemarkovský prípad, hľadanie stacionárnych pravdepodobností.

kurzová práca, pridané 09.07.2009


Pojem čakacieho systému, jeho podstata a vlastnosti. Teória radenia ako jedna z oblastí teórie pravdepodobnosti, problematika, o ktorej sa uvažuje. Pojem a charakteristika náhodného procesu, jeho typy a modely. Čakajúca služba.

kurzová práca, pridané 15.02.2009


Optimalizácia riadenia toku požiadaviek vo frontových sieťach. Metódy na stanovenie závislostí medzi charakterom požiadaviek, počtom servisných kanálov, ich produktivitou a efektívnosťou. Teória grafov; Kolmogorovova rovnica, toky udalostí.

test, pridané 01.07.2015


Teória radenia je oblasť aplikovanej matematiky, ktorá analyzuje procesy vo výrobných systémoch, v ktorých sa homogénne deje mnohokrát opakujú. Stanovenie parametrov systému radenia s konštantnými charakteristikami.

kurzová práca, pridané 01.08.2009


Definícia náhodného procesu a jeho charakteristiky. Základné pojmy teórie radenia. Koncept Markovovho náhodného procesu. Streamy udalostí. Kolmogorovove rovnice. Obmedzujúce pravdepodobnosti stavov. Procesy smrti a reprodukcie.

abstrakt, pridaný 01.08.2013


Stacionárne rozdelenie pravdepodobnosti. Konštrukcia matematických modelov, prechodové grafy. Získanie rovnovážnej rovnice pre systémy radenia s rôznym počtom zariadení, požiadavkami rôznych typov a obmedzenými radmi zariadení.

práca, pridané 23.12.2012


Analýza efektívnosti najjednoduchších systémov radenia, výpočet ich technicko-ekonomických ukazovateľov. Porovnanie výkonu systému s poruchami so zodpovedajúcim zmiešaným systémom. Výhody prechodu na systém so zmiešanými vlastnosťami.

kurzová práca, pridané 25.02.2012


Zostavenie simulačného modelu a výpočet výkonnostných ukazovateľov systému radenia na základe daných parametrov. Porovnanie ukazovateľov účinnosti s ukazovateľmi získanými numerickým riešením Kolmogorovových rovníc pre pravdepodobnosti stavov sústavy.

kurzová práca, pridané 17.12.2009


Príklady procesov reprodukcie a smrti v prípade najjednoduchších systémov radenia. Matematické očakávania pre systém radenia. Dodatočný prietok a nekonečné množstvo zariadení. Systém s obmedzením trvania aplikácie.

kurzová práca, pridané 26.01.2014


Niektoré matematické problémy v teórii obsluhy zložitých systémov. Organizácia údržby s obmedzenými informáciami o spoľahlivosti systému. Algoritmy pre bezproblémovú prevádzku systému a nájdenie času na plánovanú preventívnu údržbu systémov.