Práca na kurze

„Simulácia systému radenie»

na kurze "Operačný výskum"

Úvod

V operačnom výskume sa často stretávame so systémami určenými na to opakovane použiteľné pri riešení podobných problémov. Procesy, ktoré v tomto prípade vznikajú, sa nazývajú servisné procesy a systémy sa nazývajú čakacie systémy (QS). Každý QS pozostáva z určitého počtu obslužných jednotiek (prístrojov, zariadení, bodov, staníc), ktoré sa nazývajú obslužné kanály. Kanály môžu byť komunikačné linky, operačné body, počítače, predajcovia atď. Podľa počtu kanálov sa QS delia na jednokanálové a viackanálové.

Aplikácie zvyčajne prichádzajú na QS nie pravidelne, ale náhodne, pričom tvoria takzvaný náhodný tok žiadostí (požiadaviek). Služba aplikácií tiež pokračuje nejaký náhodný čas. Náhodná povaha toku aplikácií a servisného času vedie k tomu, že QS je zaťažený nerovnomerne: v niektorých časových úsekoch je veľa veľké množstvo aplikácie (buď sa zoradia, alebo nechajú QS neobslúžené), zatiaľ čo v iných obdobiach QS pracuje s nedostatkovým zaťažením alebo je nečinný.

Predmetom teórie radenia je konštrukcia matematických modelov, ktoré spájajú dané prevádzkové podmienky QS (počet kanálov, ich výkon, charakter toku aplikácií atď.) s výkonnostnými ukazovateľmi QS, ktoré popisujú jeho schopnosť vyrovnať sa s tokom aplikácií. Nasledujúce sa používajú ako ukazovatele výkonnosti QS:

– Absolútne priepustnosť systémy ( ALE

Q

- pravdepodobnosť odmietnutia doručenia žiadosti ();

k);

- priemerný počet žiadostí vo fronte ();

QS sa delia na 2 hlavné typy: QS s poruchami a QS s čakaním (fronta). V QS s odmietnutiami žiadosť, ktorá príde v momente, keď sú všetky kanály obsadené, dostane odmietnutie, opustí QS a nezúčastňuje sa na ďalšom servisnom procese (napríklad žiadosť o telefonický rozhovor v momente, keď sú všetky kanály obsadené, dostane odmietnutie a nechá QS bez obsluhy). V QS s čakaním reklamácia, ktorá príde v čase, keď sú všetky kanály obsadené, neodíde, ale zaradí sa do radu na obsluhu.

Jednou z metód na výpočet ukazovateľov výkonnosti QS je metóda simulácie. Praktické využitie počítačového simulačného modelovania zahŕňa konštrukciu vhodného matematického modelu, ktorý zohľadňuje faktory neurčitosti, dynamické charakteristiky a celý komplex vzťahov medzi prvkami skúmaného systému. Simulačné modelovanie fungovania systému začína určitým špecifickým počiatočným stavom. V dôsledku implementácie rôznych udalostí náhodného charakteru prechádza model systému do svojich ďalších možných stavov v nasledujúcich časových okamihoch. Tento evolučný proces pokračuje až do konca plánovacieho obdobia, t.j. až do konca simulácie.

1. Hlavné charakteristiky SOT a ukazovatele ich účinnosti

1.1 Pojem Markovovho stochastického procesu

Nech existuje nejaký systém, ktorý v priebehu času náhodne mení svoj stav. V tomto prípade hovoríme, že v systéme prebieha náhodný proces.

Proces sa nazýva proces s diskrétnymi stavmi, ak je možné jeho stavy vopred vyčísliť a prechod systému z jedného stavu do druhého nastáva skokom. Proces sa nazýva kontinuálny proces, ak prechody systému zo stavu do stavu nastanú okamžite.

Proces operácie QS je náhodný proces s diskrétnymi stavmi a nepretržitým časom.

Náhodný proces sa nazýva Markov alebo náhodný proces bez následkov, ak pravdepodobnostné charakteristiky procesu v budúcnosti závisia v akomkoľvek okamihu iba od jeho súčasného stavu a nezávisia od toho, kedy a ako sa systém do tohto stavu dostal.

Pri analýze procesov prevádzky QS je vhodné použiť geometrickú schému - stavový graf. Stavy systému sú zvyčajne znázornené obdĺžnikmi a možné prechody zo stavu do stavu sú znázornené šípkami. Príklad stavového grafu je na obr. jeden.

Prúd udalostí je sled homogénnych udalostí nasledujúcich po sebe v náhodných časoch.

Prúdenie je charakterizované intenzitou λ - frekvenciou výskytu udalostí alebo priemerným počtom udalostí vstupujúcich do QS za jednotku času.

Prúd udalostí sa nazýva pravidelný, ak udalosti nasledujú za sebou v pravidelných intervaloch.

Prúd udalostí sa nazýva stacionárny, ak jeho pravdepodobnostné charakteristiky nezávisia od času. Najmä intenzita stacionárneho prúdenia je konštantná hodnota: .

Prúd udalostí sa nazýva obyčajný, ak pravdepodobnosť, že dve alebo viac udalostí zasiahne malý časový úsek, je malá v porovnaní s pravdepodobnosťou zasiahnutia jednej udalosti, t. j. ak sa v ňom udalosti vyskytujú po jednej, nie v skupinách.

Prúd udalostí sa nazýva prúd bez následkov, ak pre ľubovoľné dva nepretínajúce sa časové intervaly a počet udalostí pripadajúcich na jeden z nich nezávisí od počtu udalostí pripadajúcich na ostatné.

Prúd udalostí sa nazýva najjednoduchší (alebo stacionárny Poisson), ak je stacionárny, obyčajný a nemá žiadny následný efekt.

1.2 Kolmogorovove rovnice

Všetky prechody v systéme zo stavu do stavu sa vyskytujú v rámci určitého toku udalostí. Nech je systém v nejakom stave, z ktorého je možný prechod do stavu, potom môžeme predpokladať, že systém je ovplyvnený najjednoduchším tokom s intenzitou , ktorý ho prenáša zo stavu do . Hneď ako nastane prvá udalosť vlákna, dôjde k jeho prechodu. Kvôli prehľadnosti je na grafe stavu každá šípka zodpovedajúca prechodu označená intenzitou . Takto označený stavový graf vám umožňuje stavať matematický model proces, t.j. nájsť pravdepodobnosti všetkých stavov ako funkciu času. Pre nich sa zostavujú diferenciálne rovnice, nazývané Kolmogorovove rovnice.

Pravidlo na zostavovanie Kolmogorovových rovníc: Na ľavej strane každej rovnice je časová derivácia pravdepodobnosti daný stav. Na pravej strane je súčet súčinov všetkých stavov, z ktorých je možný prechod do daného stavu, intenzitou zodpovedajúcich tokov udalostí mínus celková intenzita všetkých tokov, ktoré vyvedú systém z tohto stavu, vynásobený pravdepodobnosť tohto stavu.

Napríklad pre stavový graf znázornený na obr. 1 majú Kolmogorovove rovnice tvar:

Pretože na pravej strane systému každý člen vstúpi raz so znamienkom a raz so znamienkom , potom pridaním všetkých rovníc dostaneme, že

,

,

Preto je možné jednu z rovníc systému zahodiť a nahradiť rovnicou (1.2.1).

Získať konkrétne riešenie treba poznať počiatočné podmienky, t.j. pravdepodobnosti v počiatočnom čase.

1.3 Konečné pravdepodobnosti a stavový graf QS

Na dostatočne dlhý čas procesov v systéme (at ) možno stanoviť pravdepodobnosti stavov, ktoré nezávisia od času, ktoré sa nazývajú konečné pravdepodobnosti, t.j. systém je v stacionárnom režime. Ak je počet stavov systému konečný a z každého z nich v konečnom počte krokov je možné prejsť do akéhokoľvek iného stavu, potom existujú konečné pravdepodobnosti, t.j.

Význam konečných pravdepodobností je, že sa rovnajú priemernému relatívnemu času strávenému systémom v danom stave.

Pretože v stacionárnom stave sa derivácie času rovnajú nule, potom sa rovnice pre konečné pravdepodobnosti získajú z Kolmogorovových rovníc prirovnaním ich pravej strany k nule.

Stavové grafy používané v modeloch čakacích systémov sa nazývajú schéma smrti a plemena. Tento názov je spôsobený skutočnosťou, že táto schéma sa používa v biologických problémoch súvisiacich so štúdiom veľkosti populácie. Jeho zvláštnosť spočíva v tom, že všetky stavy systému možno znázorniť ako reťazec, v ktorom je každý zo stavov prepojený s predchádzajúcimi a nasledujúcimi (obr. 2).

Ryža. 2. Graf stavov v modeloch QS

Predpokladajme, že všetky toky, ktoré prenášajú systém z jedného stavu do druhého, sú tie najjednoduchšie. Podľa grafu na obr. 2 zostavíme rovnice pre konečné pravdepodobnosti sústavy. Vyzerajú takto:

Systém je získaný z ( n +1) rovnice, ktorá sa rieši eliminačnou metódou. Táto metóda spočíva v tom, že postupne všetky pravdepodobnosti systému sú vyjadrené prostredníctvom pravdepodobnosti.

,

.

Dosadením týchto výrazov do poslednej rovnice systému nájdeme , potom nájdeme zostávajúce pravdepodobnosti stavov QS.

1.4 Ukazovatele výkonnosti QS

Účelom modelovania QS je vypočítať výkon systému prostredníctvom jeho charakteristík. Nasledujúce sa používajú ako ukazovatele výkonnosti QS:

je absolútna kapacita systému ( ALE), t.j. priemerný počet doručených aplikácií za jednotku času;

je relatívna priepustnosť ( Q), t.j. priemerný podiel prijatých požiadaviek obsluhovaných systémom;

je pravdepodobnosť zlyhania (), t.j. pravdepodobnosť, že aplikácia ponechá QS neobslúžený;

je priemerný počet obsadených kanálov ( k);

- priemerný počet aplikácií v QS ();

– priemerný čas zotrvania aplikácie v systéme ();

- priemerný počet žiadostí vo fronte () - dĺžka frontu;

- priemerný počet aplikácií v systéme ();

- priemerný čas, počas ktorého aplikácia zostáva vo fronte ();

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

– stupeň zaťaženia kanála (), t.j. pravdepodobnosť, že kanál je obsadený;

je priemerný počet aplikácií obsluhovaných za jednotku času;

– priemerný čas čakania na servis;

– pravdepodobnosť, že počet žiadostí vo fronte prekročí určitú hodnotu atď.

Bolo dokázané, že pre akúkoľvek povahu toku požiadaviek, pre akúkoľvek distribúciu času služby, pre akúkoľvek disciplínu služby sa priemerný čas požiadavky v systéme (vo fronte) rovná priemernému počtu požiadaviek v systéme. (front) delené intenzitou toku požiadaviek, t.j.

(1.4.1)

Vzorce (1.4.1) a (1.4.2) sa nazývajú malé vzorce. Vyplývajú zo skutočnosti, že v obmedzujúcom stacionárnom režime sa priemerný počet škôd prichádzajúcich do systému rovná priemernému počtu škôd, ktoré z neho odchádzajú, t. oba prúdy aplikácií majú rovnakú intenzitu.

Vzorce na výpočet ukazovateľov výkonnosti sú uvedené v tabuľke. jeden.

Stôl 1.

Ukazovatele	Jednokanálový QS s obmedzený rad	Viackanálové QS s obmedzený rad
Finálny, konečný pravdepodobnosti
Pravdepodobnosť
Absolútna priepustnosť schopnosť
Relatívna priepustnosť schopnosť
Priemerný počet aplikácií na
Priemerný počet aplikácií pod služby
Priemerný počet aplikácií v systéme

1.5 Základné pojmy simulácie

Hlavným cieľom simulačného modelovania je reprodukovať správanie skúmaného systému na základe analýzy najvýznamnejších vzťahov jeho prvkov.

Počítačová simulácia by sa mala považovať za statický experiment.

Z teórie funkcií náhodných veličín je známe, že na modelovanie náhodnej premennej s akoukoľvek spojitou a monotónne rastúcou distribučnou funkciou stačí vedieť modelovať náhodnú premennú rovnomerne rozloženú na intervale . Po získaní realizácie náhodnej premennej je možné nájsť zodpovedajúcu realizáciu náhodnej premennej , pretože sú spojené rovnosťou

Predpokladajme, že v niektorom systéme radenia je čas obsluhy jedného zákazníka rozdelený podľa exponenciálneho zákona s parametrom , kde je intenzita toku služieb. Potom funkcia rozdelenia času obsluhy má tvar

Nech je realizácia náhodnej premennej , rovnomerne rozloženej na intervale , a nech je jej zodpovedajúca realizácia náhodného servisného času jednej požiadavky. Potom podľa (1.5.1)

1.6 Budovanie simulačných modelov

Prvou fázou pri vytváraní akéhokoľvek simulačného modelu je fáza popisu skutočného existujúci systém z hľadiska charakteristík hlavných udalostí. Tieto udalosti sú spravidla spojené s prechodmi skúmaného systému z jedného možného stavu do druhého a sú označené ako body na časovej osi. Na dosiahnutie hlavného cieľa modelovania stačí sledovať systém v momentoch realizácie hlavných udalostí.

Uvažujme o príklade jednokanálového systému radenia. Účelom simulačného modelovania takéhoto systému je určiť odhady jeho hlavných charakteristík, ako je priemerný čas strávený aplikáciou vo fronte, priemerná dĺžka frontu a podiel prestojov systému.

Charakteristiky samotného procesu zaraďovania môžu meniť svoje hodnoty buď v momente prijatia novej požiadavky na službu, alebo na konci obsluhy ďalšej požiadavky. QS môže začať obsluhovať nasledujúcu požiadavku okamžite (servisný kanál je voľný), ale nie je vylúčená nutnosť čakať, kedy sa požiadavka musí zaradiť do frontu (QS s frontom, obslužný kanál je obsadený). Po dokončení obsluhy ďalšej požiadavky môže QS okamžite začať obsluhovať ďalšiu požiadavku, ak existuje, ale môže tiež zostať nečinná, ak žiadna neexistuje. Potrebné informácie možno získať pozorovaním rôzne situácie vyplývajúce z realizácie hlavných podujatí. Takže, keď do QS príde reklamácia s frontom s obsadeným obslužným kanálom, dĺžka frontu sa zväčší o 1. Podobne sa dĺžka frontu zníži o 1, ak sa dokončí obsluha ďalšej reklamácie a súbor nárokov vo fronte nie je prázdny.

Pre fungovanie akéhokoľvek simulačného modelu je potrebné zvoliť jednotku času. V závislosti od charakteru modelovaného systému môže byť takouto jednotkou mikrosekunda, hodina, rok atď.

Keďže počítačová simulácia je vo svojej podstate výpočtovým experimentom, jej pozorované výsledky v súhrne musia mať vlastnosti implementácie náhodnej vzorky. Len v tomto prípade bude zabezpečená správna štatistická interpretácia simulovaného systému.

Pri počítačovom simulačnom modelovaní sú hlavným záujmom pozorovania získané po tom, ako sa skúmaný systém dostane do stacionárneho režimu prevádzky, pretože v tomto prípade sa rozptyl vzorky prudko znižuje.

Čas potrebný na to, aby systém dosiahol stacionárny režim prevádzky, je určený hodnotami jeho parametrov a počiatočným stavom.

Keďže hlavným cieľom je získať pozorovacie údaje s najmenšou možnou chybou, na dosiahnutie tohto cieľa môžete:

1) zvýšiť trvanie simulačného modelovania procesu fungovania skúmaného systému. V tomto prípade sa zvyšuje nielen pravdepodobnosť, že systém dosiahne stacionárny režim prevádzky, ale zvyšuje sa aj počet použitých pseudonáhodných čísel, čo tiež pozitívne ovplyvňuje kvalitu získaných výsledkov.

2) na dobu určitú T simulačné modelovanie N výpočtové experimenty, nazývané aj modelové chody, s rôznymi súbormi pseudonáhodných čísel, z ktorých každý poskytuje jedno pozorovanie. Všetky behy začínajú s rovnakým počiatočným stavom simulovaného systému, ale s použitím rôznych súborov pseudonáhodných čísel. Výhodou tejto metódy je nezávislosť získaných pozorovaní, ukazovateľov účinnosti systému. Ak číslo N model je dostatočne veľký, potom hranice symetrické interval spoľahlivosti pre parameter sú definované takto:

, , t.j. , kde

korigovaný rozptyl, ,

N– počet spustení programu, – spoľahlivosť, .

2. Analytické modelovanie QS

2.1 Stavový graf sústavy a Kolmogorovova rovnica

Zvážte dvojkanálový systém zaraďovania do frontu (n = 2) s obmedzeným radom rovným šiestim (m = 4). QS prijíma najjednoduchší tok aplikácií s priemernou intenzitou λ = 4,8 a exponenciálnym zákonom rozloženia času medzi príchodom aplikácií. Tok požiadaviek obsluhovaných v systéme je najjednoduchší s priemernou intenzitou μ = 2 a exponenciálnym zákonom rozloženia času obsluhy.

Tento systém má 7 stavov, označujeme ich:

S 0 - systém je bezplatný, neexistujú žiadne požiadavky;

S 1 - 1 servisná požiadavka, front je prázdny;

S 2 - 2 požiadavky na službu, rad je prázdny;

S 3 - 2 požiadavky na službu, 1 požiadavka vo fronte;

S 4 - 2 požiadavky na obsluhu, 2 požiadavky v rade;

S 5 - 2 požiadavky na službu, 3 požiadavky v rade;

S 6 - 2 požiadavky na obsluhu, 4 požiadavky v rade;

Pravdepodobnosti vstupu systému do stavov S 0 , S 1 , S 2 , …, S 6 sú v tomto poradí rovné Р 0 , Р 1 , Р 2 , …, Р 6 .

Stavový graf systému zaraďovania je schéma smrti a reprodukcie. Všetky stavy systému možno znázorniť ako reťazec, v ktorom je každý zo stavov spojený s predchádzajúcim a nasledujúcim.

Ryža. 3. Graf stavov dvojkanálového QS

Pre zostrojený graf napíšeme Kolmogorovove rovnice:

Na vyriešenie tohto systému nastavíme počiatočné podmienky:

Kolmogorovov systém rovníc (systém diferenciálne rovnice) riešime numerickou Eulerovou metódou pomocou programového balíka Maple 11 (pozri prílohu 1).

Eulerova metóda

kde - v našom prípade sú to správne časti Kolmogorovových rovníc, n=6.

Vyberme si časový krok. Predpokladajme kde T je čas, ktorý systém potrebuje na dosiahnutie ustáleného stavu. Odtiaľ dostaneme počet krokov . Dôsledne N po výpočte podľa vzorca (1) získame závislosti pravdepodobnosti stavov sústavy od času, znázornené na obr. štyri.

Hodnoty pravdepodobnosti QS sa rovnajú:

Ryža. 4. Závislosti pravdepodobnosti stavov sústavy na čase

P0

P5

P4

P3

P2

P1

2.2 Konečné pravdepodobnosti systému

Pri dostatočne dlhom čase pre procesy v systéme () možno stanoviť pravdepodobnosti stavov, ktoré nezávisia od času, ktoré sa nazývajú konečné pravdepodobnosti, t.j. systém je v stacionárnom režime. Ak je počet stavov sústavy konečný a z každého z nich je možné v konečnom počte krokov prejsť do akéhokoľvek iného stavu, potom existujú konečné pravdepodobnosti, t.j.

Pretože v stacionárnom stave sú časové derivácie rovné 0, potom rovnice pre konečné pravdepodobnosti získame z Kolmogorovových rovníc rovnaním pravej strany k 0. Napíšme rovnice pre konečné pravdepodobnosti pre naše QS.

Poďme vyriešiť tento systém lineárne rovnice pomocou softvérového balíka Maple 11 (pozri prílohu 1).

Dostaneme konečné pravdepodobnosti systému:

Porovnanie pravdepodobností získaných zo systému Kolmogorovových rovníc pre , s konečnými pravdepodobnosťami ukazuje, že chyby sú si rovné:

Tie. dostatočne malý. To potvrdzuje správnosť získaných výsledkov.

2.3 Výpočet ukazovateľov výkonnosti systému podľa konečných pravdepodobností

Poďme nájsť ukazovatele výkonnosti systému radenia.

Najprv vypočítame zníženú intenzitu toku aplikácií:

1) Pravdepodobnosť odmietnutia doručenia aplikácie, t.j. pravdepodobnosť, že zákazník opustí systém bez obsluhy V našom prípade je zákazníkovi odmietnutá služba, ak sú všetky 2 kanály obsadené a front je maximálne plný (t.j. 4 ľudia vo fronte), to zodpovedá stavu systému S 6 . Pretože pravdepodobnosť, že systém vstúpi do stavu S 6 je P 6 , potom

4) Priemerná dĺžka frontu, t.j. priemerný počet požiadaviek vo fronte sa rovná súčtu súčinov počtu požiadaviek vo fronte a pravdepodobnosti zodpovedajúceho stavu.

5) Priemerný čas, ktorý aplikácia strávi vo fronte, je určený Littleovým vzorcom:

3. Simulačné modelovanie QS

3.1 Algoritmus simulačnej metódy QS (prístup krok za krokom)

Zvážte dvojkanálový systém zaraďovania do frontu (n = 2) s maximálnou dĺžkou frontu šesť (m = 4). QS prijíma najjednoduchší tok aplikácií s priemernou intenzitou λ = 4,8 a exponenciálnym zákonom rozloženia času medzi príchodom aplikácií. Tok požiadaviek obsluhovaných v systéme je najjednoduchší s priemernou intenzitou μ = 2 a exponenciálnym zákonom rozloženia času obsluhy.

Na simuláciu QS použijeme jednu z metód štatistického modelovania - simulačné modelovanie. Použijeme postup krok za krokom. Podstatou tohto prístupu je, že stavy systému sa zvažujú v nasledujúcich časových okamihoch, pričom krok medzi nimi je dostatočne malý na to, aby v jeho čase nenastala viac ako jedna udalosť.

Vyberieme si časový krok (). Mala by byť oveľa menšia ako priemerný čas prijatia žiadosti () a priemerný čas jej doručenia (), t.j.

Kde (3.1.1)

Na základe podmienky (3.1.1) určíme časový krok .

Čas prijatia žiadosti v QS a čas jej doručenia sú náhodné premenné. Preto sa pri simulácii QS počítajú pomocou náhodných čísel.

Zvážte prijatie žiadosti v SOT. Pravdepodobnosť, že objednávka príde do QS počas intervalu, sa rovná: . Vygenerujme náhodné číslo a ak , potom budeme uvažovať, že požiadavka v tomto kroku vstúpila do systému, ak , potom nevstúpil.

Toto sa robí v programe isRequested () . Vezmeme časový interval konštantný a rovný 0,0001, potom bude pomer rovný 10000. Ak je požiadavka prijatá, potom nadobudne hodnotu "true", inak je hodnota "false".

bool isRequested()

double r = R.NextDouble();

ak (r< (timeStep * lambda))

Uvažujme teraz o službe aplikácie v QS. Čas obsluhy aplikácie v systéme je určený výrazom , kde je náhodné číslo. V programe je čas obsluhy určený pomocou funkcie GetServiceTime () .

double GetServiceTime()

double r = R.NextDouble();

return(-1/mu*Math. Log(1-r, Math.E));

Algoritmus simulačnej metódy možno formulovať nasledovne. Prevádzkové hodiny QS ( T) je rozdelená do časových krokov dt, každý z nich vykoná sériu akcií. Najprv sa určia stavy systému (obsadené kanály, dĺžka frontu), potom pomocou funkcie isRequested () , zisťuje sa, či bola žiadosť v tomto kroku prijatá alebo nie.

Ak sú prijaté a zároveň sú k dispozícii voľné kanály, použite funkciu GetServiceTime () vygenerujeme čas spracovania žiadosti a uvedieme ju do prevádzky. Ak sú všetky kanály obsadené a dĺžka frontu je menšia ako 4, potom zaradíme požiadavku do frontu; ak je dĺžka frontu 4, potom bude žiadosť zamietnutá.

V prípade, že v tomto kroku nebola požiadavka prijatá a servisný kanál bol voľný, skontrolujeme, či existuje fronta. Ak existuje, zaradíme požiadavku z frontu na servis na bezplatný kanál. Po vykonaných operáciách sa servisný čas pre obsadené kanály zníži o hodnotu kroku dt .

Po uplynutí času T t.j. po namodelovaní prevádzky QS sa vypočítajú ukazovatele výkonu systému a výsledky sa zobrazia na obrazovke.

3.2 Vývojový diagram programu

Bloková schéma programu, ktorý implementuje opísaný algoritmus, je znázornená na obr. 5.

Ryža. 5. Vývojový diagram programu

Napíšme si niektoré bloky podrobnejšie.

Blok 1. Nastavenie počiatočných hodnôt parametrov.

Náhodné R; // Generátor náhodných čísel

public uint maxQueueLength; // Maximálna dĺžka frontu

počet kanálov verejnej jednotky; // Počet kanálov v systéme

verejná dvojitá lambda; // Intenzita toku prichádzajúcich požiadaviek

verejné dvojité mu; // Intenzita toku obsluhy požiadaviek

verejný dvojitý časKrok; // Časový krok

public double timeOfFinishProcessingReq; // Čas ukončenia obsluhy požiadavky vo všetkých kanáloch

verejný dvojitý timeInQueue; // Čas strávený QS v štátoch s frontom

verejné dvojité spracovanieČas; // Čas behu systému

public double totalProcessingTime; // Celkový čas na servisné požiadavky

public uint requestEntryCount; // Počet prijatých žiadostí

public uint odmietnutýPočet žiadostí; // Počet zamietnutých žiadostí

public uint prijatýPočet žiadostí; // Počet obsluhovaných žiadostí

uint queueLength; // Dĺžka fronty //

Typ popisujúci stavy QS

enum SysCondition(SO, S1, S2, S3, S4, S5, S6);

SysCondition currentSystemCondition; // Aktuálny stav systému

Nastavenie stavov systému. Vyberme 7 rôznych stavov pre tento 2-kanálový systém: S 0 , S 1 . S 6. QS je v stave S 0, keď je systém voľný; S 1 – aspoň jeden kanál je voľný; v stave S2, keď sú všetky kanály obsadené a vo fronte je miesto; v stave S 6 sú všetky kanály obsadené a front dosiahol maximálnu dĺžku (dĺžka frontu = 4).

Pomocou funkcie zisťujeme aktuálny stav systému GetCondition()

SysCondition GetCondition()

SysCondition p_currentCondit = SysCondition.S0;

int busyChannelCount = 0;

pre (int i = 0; i< channelCount; i++)

if (timeOfFinishProcessingReq[i] > 0)

busyChannelCount++;

p_currentCondit += k * (i + 1);

if (busyChannelCount > 1)

(p_currentCondit++;)

return p_currentCondit + (int) QueueLength;

Zmena času pobytu QS v štátoch s dĺžkou frontu 1, 2, 3, 4. Toto je implementované nasledujúcim kódom:

if (dĺžka frontu > 0)

timeInQueue += timeStep;

if (dĺžka frontu > 1)

(timeInQueue += timeStep;)

Existuje taká operácia ako umiestnenie požiadavky na službu na bezplatný kanál. Všetky kanály sa prehľadajú, počnúc prvým, keď je splnená podmienka timeOfFinishProcessingReq [ i ] <= 0 (kanál je bezplatný), odošle sa naň prihláška, t.j. vygeneruje sa čas ukončenia spracovania požiadavky.

pre (int i = 0; i< channelCount; i++)

if (timeOfFinishProcessingReq[i]<= 0)

timeOfFinishProcessingReq[i] = GetServiceTime();

totalProcessingTime+= timeOfFinishProcessingReq[i];

Obsluha aplikácií v kanáloch je modelovaná kódom:

pre (int i = 0; i< channelCount; i++)

if (timeOfFinishProcessingReq[i] > 0)

timeOfFinishProcessingReq[i] -= timeStep;

Algoritmus simulačnej metódy je implementovaný v programovacom jazyku C#.

3.3 Výpočet QS ukazovatele výkonnosti založené na výsledky jeho simulácie

Najdôležitejšie ukazovatele sú:

1) Pravdepodobnosť odmietnutia doručenia žiadosti, t.j. pravdepodobnosť, že zákazník opustí systém neobslúžený. V našom prípade je zákazníkovi odmietnutá služba, ak sú všetky 2 kanály obsadené a front je maximálne zaplnený (t. j. 4 ľudia vo fronte). Na zistenie pravdepodobnosti zlyhania vydelíme čas, počas ktorého QS zostane v stave s frontom 4, celkovým časom systému.

2) Relatívna priepustnosť je priemerný podiel prichádzajúcich požiadaviek obsluhovaných systémom.

3) Absolútna priepustnosť je priemerný počet aplikácií obsluhovaných za jednotku času.

4) Dĺžka frontu, t.j. priemerný počet aplikácií vo fronte. Dĺžka frontu sa rovná súčtu súčinov počtu ľudí vo fronte a pravdepodobnosti zodpovedajúceho stavu. Pravdepodobnosti stavov nájdeme ako pomer času QS v tomto stave k celkovému času prevádzky systému.

5) Priemerný čas, ktorý aplikácia strávi vo fronte, je určený Littleovým vzorcom

6) Priemerný počet obsadených kanálov je definovaný takto:

7) Percento aplikácií, ktorým bola služba odmietnutá, sa zistí podľa vzorca

8) Percento obsluhovaných požiadaviek sa zistí podľa vzorca

3.4 Štatistické spracovanie výsledkov a ich porovnanie s výsledkami analytického modelovania

Pretože ukazovatele výkonnosti sa získavajú ako výsledok modelovania QS na konečný čas, obsahujú náhodnú zložku. Pre získanie spoľahlivejších výsledkov je preto potrebné vykonať ich štatistické spracovanie. Na tento účel im odhadujeme interval spoľahlivosti na základe výsledkov 20 spustení programu.

Hodnota spadá do intervalu spoľahlivosti, ak je nerovnosť

, kde

matematické očakávanie (priemerná hodnota), sa zistí podľa vzorca

korigovaný rozptyl,

,

N =20 - počet jázd

- spoľahlivosť. Pri a N =20 .

Výsledok programu je znázornený na obr. 6.

Ryža. 6. Typ programu

Pre uľahčenie porovnania výsledkov získaných rôznymi metódami modelovania ich uvádzame vo forme tabuľky.

Tabuľka 2

Ukazovatele Účinnosť QS	výsledky analytické modelovanie	výsledky simulačné modelovanie (posledný krok)	Výsledky simulácie
			Spodná čiara zverenec interval	Horná hranica zverenec interval
Pravdepodobnosť zlyhania		0,174698253017626	0,158495148639101	0,246483801571923
Relatívna šírka pásma		0,825301746982374	0,753516198428077	0,841504851360899
Absolútna šírka pásma		3,96144838551539	3,61687775245477	4,03922328653232
Priemerná dĺžka frontu		1,68655313447018	1,62655862750852	2,10148609204869
Priemerný čas, ktorý aplikácia strávi vo fronte	0,4242558575	0,351365236347954	0,338866380730942	0,437809602510145
Priemerne obsadené kanály		1,9807241927577	1,80843887622738	2,01961164326616

Z tabuľky. Obrázok 2 ukazuje, že výsledky získané pri analytickom modelovaní QS spadajú do intervalu spoľahlivosti získaného z výsledkov simulácie. To znamená, že výsledky získané rôznymi metódami sú konzistentné.

Záver

V tomto článku sú zvažované hlavné metódy modelovania QS a výpočtu ich výkonnostných ukazovateľov.

Simulácia dvojkanálového QS s maximálnou dĺžkou frontu 4 bola vykonaná pomocou Kolmogorovových rovníc a boli zistené konečné pravdepodobnosti stavov systému. Vypočítajú sa ukazovatele jeho účinnosti.

Uskutočnila sa simulácia činnosti takéhoto QS. V programovacom jazyku C# bol zostavený program, ktorý simuluje jeho činnosť. Bola vykonaná séria výpočtov, na základe ktorých boli zistené hodnoty ukazovateľov efektívnosti systému a bolo vykonané ich štatistické spracovanie.

Výsledky získané počas simulačného modelovania sú v súlade s výsledkami analytického modelovania.

Literatúra

1. Wentzel E.S. Operačný výskum. – M.: Drop, 2004. – 208 s.

2. Volkov I.K., Zagoruiko E.A. Operačný výskum. - M .: Vydavateľstvo MSTU im. N.E. Bauman, 2002. - 435 s.

3. Volkov I.K., Zuev S.M., Tsvetkova G.M. náhodné procesy. - M .: Vydavateľstvo MSTU im. N.E. Bauman, 2000. - 447 s.

4. Gmurman V.E. Sprievodca riešením problémov v teórii pravdepodobnosti a matematickej štatistike. - M.: Vyššia škola, 1979. - 400 s.

5. Ivnitsky V.L. Teória radiacich sietí. – M.: Fizmatlit, 2004. – 772 s.

6. Výskumné operácie v hospodárstve / vyd. N.Sh. Kremer. - M.: Jednota, 2004. - 407 s.

7. Takha H.A. Úvod do operačného výskumu. - M.: Vydavateľstvo "Williams", 2005. - 902 s.

8. Kharin Yu.S., Malyugin V.I., Kirlitsa V.P. et al Základy simulácie a štatistického modelovania. - Minsk: Design PRO, 1997. - 288 s.

Analytická štúdia systémov radenia (QS) je alternatívnym prístupom k simulačnému modelovaniu a spočíva v získaní vzorcov na výpočet výstupných parametrov QS s následným dosadením hodnôt argumentov do týchto vzorcov v každom jednotlivom experimente.

V modeloch QS sa berú do úvahy tieto objekty:

1) servisné požiadavky (transakcie);

2) servisné zariadenia (OA) alebo zariadenia.

Praktická úloha teórie radenia súvisí so štúdiom operácií týchto objektov a pozostáva zo samostatných prvkov, ktoré sú ovplyvnené náhodnými faktormi.

Ako príklad problémov uvažovaných v teórii radenia možno uviesť: zosúladenie priepustnosti 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ť buď v stave služby alebo v stave čakajúcej na službu.

Servisné zariadenie môže byť obsadené službou alebo voľné.

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

Modely QS sa používajú na štúdium procesov vyskytujúcich sa v systéme pri aplikácii na vstupy aplikačných tokov. 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áciou môžu byť zákazky na výrobu produktov, úlohy riešené v počítačovom systéme, zákazníci v bankách, tovar prichádzajúci na prepravu a pod. Je zrejmé, že parametre aplikácií vstupujúcich do systému sú náhodné veličiny a iba ich parametre môžu byť známe počas výskum alebo dizajn.distribučné zákony.

V tomto smere má analýza fungovania na úrovni systému spravidla štatistický charakter. Je vhodné brať teóriu radenia ako nástroj matematického modelovania a používať systémy radenia ako modely systémov na tejto úrovni.

Najjednoduchšie modely QS

V najjednoduchšom prípade je QS zariadením nazývaným servisné zariadenie (OA), s frontami aplikácií na vstupoch.

P o d e l o n s e r e n t e r e s s e n k a t i e (obr. 5.1)

Ryža. 5.1. Model QS s poruchami:

0 – zdroj požiadavky;

1 - servisné zariadenie;

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

v je výstupný tok obsluhovaných požiadaviek;

s je výstupný tok neobslúžených požiadaviek.

V tomto modeli nie je na vstupe OA žiadny reklamačný akumulátor. Ak reklamácia príde zo zdroja 0 v momente, keď je AA zaneprázdnený vybavovaním predchádzajúcej reklamácie, potom novo prijatá reklamácia opustí systém (pretože jej služba bola odmietnutá) a stratí sa (tok s).

M o d e l o k a n é n e k r i 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 akumulátora

Tento model má na vstupe OA akumulátor reklamácie. Ak zákazník príde zo zdroja 0 v momente, keď je CA zaneprázdnená obsluhou predchádzajúceho zákazníka, tak novo prichádzajúci zákazník vstúpi do akumulátora, kde čaká neobmedzene dlho, kým sa CA uvoľní.

MODEL OBMEDZENEJ SLUŽBY

w i d a n y (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 uvedené inak, môžu byť predložené ktorémukoľvek AB, ktorý nemá služby. Neexistuje žiadne úložisko, takže tento model obsahuje vlastnosti modelu znázorneného na obr. 5.1: odmietnutie doručenia žiadosti znamená jej nenahraditeľnú stratu (stane sa tak iba vtedy, ak v čase doručenia tejto žiadosti všetky OA sú zaneprázdnení).

v ý h o m (obr. 5.5)

Ryža. 5.6. Viackanálový model QS s čakaním a obnovou OA:

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

f– obnovené servisné vozidlá

Tento model má vlastnosti modelov znázornených na obr. 5.2 a 5.4, ako aj vlastnosti, ktoré umožňujú zohľadniť možné náhodné poruchy OA, ktoré v tomto prípade vstupujú do bloku opráv 2, kde zostanú náhodne po určitú dobu strávenú na ich obnove a potom sa vrátia do opäť servisný blok 1.

M i n o n a l m o l l Q O

Čakacia doba a zotavenie OA (obr. 5.7)

Ryža. 5.7. Viackanálový model QS s obmedzenou čakacou dobou a obnovou OA

Tento model je pomerne zložitý, pretože súčasne zohľadňuje vlastnosti dvoch nie najjednoduchších modelov (obrázky 5.5 a 5.6).

Klasifikácia, základné pojmy, prvky modelu, výpočet hlavných charakteristík.

Pri riešení problémov racionálnej organizácie obchodu, spotrebiteľských služieb, skladovania a pod. veľmi užitočný je výklad činností výrobnej štruktúry ako systémy radenia, t.j. systém, v ktorom na jednej strane neustále vznikajú požiadavky na výkon akejkoľvek práce a na druhej strane sú tieto požiadavky neustále uspokojované.

Súčasťou každého SMO je štyri prvky: prichádzajúci prúd, front, server, odchádzajúci prúd.

požiadavka(klient, žiadosť) v QS je každá jednotlivá požiadavka na vykonanie akejkoľvek práce.

servis je vykonanie práce na uspokojenie prichádzajúceho dopytu. Objekt, ktorý vykonáva údržbu požiadaviek, sa nazýva servisné zariadenie (zariadenie) alebo servisný kanál.

Čas služby je obdobie, počas ktorého je splnená požiadavka na službu, t.j. obdobie od začiatku poskytovania služby do jej ukončenia. Obdobie od okamihu, keď požiadavka vstúpi do systému, až po začiatok služby, sa nazýva čakacia doba služby. Čakacia doba na obsluhu je spolu s dobou obsluhy dobou zotrvania požiadavky v systéme.

SMO sú klasifikované podľa rôznych kritérií..

1. Podľa počtu obslužných kanálov sa QS delia na jednokanálové a viackanálové.

2. V závislosti od podmienok čakania požiadavka na spustenie služby rozlišuje QS so stratami (poruchy) a QS s čakaním.

AT QS so stratou dopytu, prijaté v momente, keď sú všetky zariadenia zaneprázdnené údržbou, sú odmietnuté, sú pre tento systém stratené a nemajú žiadny vplyv na ďalší proces údržby. Klasickým príkladom zlyhania systému je telefónna ústredňa – požiadavka na spojenie je odmietnutá, ak je volaný účastník obsadený.

Pre systém s poruchami je hlavnou charakteristikou efektívnosti fungovania pravdepodobnosť zlyhania alebo priemerný podiel požiadaviek, ktoré zostanú nevybavené.

AT CMO s čakaním na dopyt, prijatý v momente, keď sú všetky zariadenia zaneprázdnené servisom, neopustí systém, ale zaradí sa do frontu a čaká, kým sa jeden z kanálov neuvoľní. Keď sa uvoľní ďalšie zariadenie, jedna z aplikácií vo fronte je okamžite prijatá do servisu.

Pre QS s čakaním sú hlavnými charakteristikami matematické očakávania dĺžky frontu a čakacej doby.

Príkladom vyčkávacieho systému je proces obnovy televízorov v opravovni.

Existujú systémy, ktoré ležia medzi týmito dvoma skupinami ( zmiešané CMO). Vyznačujú sa prítomnosťou niektorých prechodných podmienok: obmedzeniami môžu byť obmedzenia čakacej doby na začiatok služby, dĺžky frontu atď.

Ako výkonnostné charakteristiky možno použiť pravdepodobnosť poruchy tak v systémoch so stratami (alebo charakteristikami čakacej doby), ako aj v systémoch s čakaním.

3. Podľa služobnej disciplíny sa QS delia na systémy s prioritou služby a systémy bez priority služby.

Požiadavky môžu byť vybavované v poradí, v akom boli prijaté, buď náhodne, alebo na základe stanovených priorít.

4. QS môže byť jednofázové a viacfázové.

AT jednofázový systémy, požiadavky sú uspokojované kanálmi rovnakého typu (napríklad pracovníci rovnakej profesie) bez ich prenosu z jedného kanála do druhého, v viacfázový systémy takéto prevody sú možné.

5. Podľa umiestnenia zdroja požiadaviek sa QS delia na otvorené (keď je zdroj požiadavky mimo systému) a uzavreté (keď je zdroj v samotnom systéme).

Komu ZATVORENÉ zahŕňajú systémy, v ktorých je vstupný tok požiadaviek obmedzený. Napríklad majster, ktorého úlohou je nastavovať stroje v dielni, ich musí pravidelne vykonávať. Každý nastavený stroj sa v budúcnosti stáva potenciálnym zdrojom požiadaviek na nastavenie. V takýchto systémoch je celkový počet obežných nárokov konečný a najčastejšie konštantný.

Ak má zdroj napájania nekonečný počet požiadaviek, potom sa volajú systémy OTVORENÉ. Príkladmi takýchto systémov sú obchody, pokladne staníc, prístavov atď. Pri týchto systémoch možno vstupný tok požiadaviek považovať za neobmedzený.

Metódy a modely na štúdium QS možno podmienečne rozdeliť na analytické a štatistické (simulačné modelovanie procesov radenia).

Analytické metódy umožňujú získať charakteristiky systému ako niektoré funkcie parametrov jeho fungovania. To umožňuje vykonať kvalitatívnu analýzu vplyvu jednotlivých faktorov na efektívnosť QS.

Bohužiaľ, len pomerne obmedzený okruh problémov v teórii radenia sa dá vyriešiť analyticky. Napriek neustálemu vývoju analytických metód je v mnohých reálnych prípadoch buď nemožné získať analytické riešenie, alebo sa výsledné závislosti ukážu ako také zložité, že ich analýza sa stáva samostatnou náročnou úlohou. Preto, aby bolo možné aplikovať analytické metódy riešenia, je potrebné uchýliť sa k rôznym zjednodušujúcim predpokladom, čo je do istej miery kompenzované možnosťou aplikácie kvalitatívnej analýzy výsledných závislostí (v tomto prípade samozrejme je potrebné, aby vytvorené predpoklady neskresľovali skutočný obraz procesu).

V súčasnosti sú teoreticky najrozvinutejšie a najpohodlnejšie v praktických aplikáciách metódy riešenia takých problémov s radením, pri ktorých je tok požiadaviek najjednoduchší ( jed).

Pre najjednoduchší tok sa frekvencia prijímania požiadaviek do systému riadi Poissonovým zákonom, to znamená, že pravdepodobnosť príchodu v čase t rovnajúca sa k požiadavkám je daná vzorcom:

kde λ je parameter prietoku (pozri nižšie).

Najjednoduchší tok má tri hlavné vlastnosti: obyčajný, stacionárny a bez následkov.

Obyčajnosť tok znamená praktickú nemožnosť súčasného prijatia dvoch alebo viacerých požiadaviek. Napríklad pravdepodobnosť, že niekoľko strojov zo skupiny strojov obsluhovaných tímom opravárov naraz zlyhá, je dosť malá.

Stacionárne volal tok, pre ktoré sa matematické očakávanie počtu nárokov vstupujúcich do systému za jednotku času (označuje sa λ) v čase nemení. Pravdepodobnosť vstupu určitého počtu poistných udalostí do systému počas daného časového intervalu Δt teda závisí od jeho hodnoty a nezávisí od jeho vzniku na časovej osi.

Žiadny následný efekt znamená, že počet zákazníkov vstupujúcich do systému pred časom t neurčuje, koľko zákazníkov vstúpi do systému za čas t + Δt.

Ak sa napríklad na tkáčskom stave v danom momente vyskytne pretrhnutie nite a tkáč ho odstráni, nerozhoduje to o tom, či na tomto stave v nasledujúcom okamihu dôjde k novému pretrhnutiu nite alebo nie, o to viac. neovplyvní pravdepodobnosť poruchy na iných strojoch.

Dôležitou charakteristikou QS je doba obsluhy požiadaviek v systéme. Obslužný čas je spravidla náhodná veličina, a preto môže byť opísaná distribučným zákonom. Exponenciálny zákon získal najväčšie rozšírenie v teórii a najmä v praktických aplikáciách. Pre tento zákon má funkcia rozdelenia pravdepodobnosti tvar:

F(t) \u003d 1 - e -μt,

tie. pravdepodobnosť, že doba obsluhy nepresiahne určitú hodnotu t, je určená vzorcom (1 - e -μt), kde μ je parameter exponenciálneho zákona doby obsluhy požiadaviek v systéme - prevrátená priemerná hodnota. servisný čas, t.j. .

Zvážte analytické modely QS s očakávaním(najbežnejší QS, v ktorom sú požiadavky prijaté v momente, keď sú všetky obslužné jednotky obsadené, radené do frontu a obsluhované, keď sa obslužné jednotky uvoľňujú).

Úlohy s frontami sú typické vo výrobných podmienkach, napríklad pri organizovaní nastavovacích a opravárenských prác, pri údržbe viacerých strojov atď.

Všeobecné vyhlásenie o probléme je nasledovné.

Systém pozostáva z n obslužných kanálov. Každý z nich môže naraz obsluhovať iba jednu požiadavku. Systém dostáva najjednoduchší (Poissonov) tok požiadaviek s parametrom λ. Ak je v momente príchodu ďalšej požiadavky do systému už v prevádzke aspoň n požiadaviek (t.j. všetky kanály sú obsadené), potom táto požiadavka vstúpi do frontu a čaká na spustenie služby.

Obslužný čas každej požiadavky t asi je náhodná premenná, ktorá sa riadi zákonom exponenciálneho rozdelenia s parametrom μ.

Ako je uvedené vyššie, QS s očakávaním možno rozdeliť do dvoch veľkých skupín: uzavreté a otvorené.

Vlastnosti fungovania každého z týchto dvoch typov systémov vnucujú použitému matematickému aparátu svoj vlastný odtieň. Výpočet charakteristík prevádzky QS rôznych typov sa môže uskutočniť na základe výpočtu pravdepodobnosti stavov QS (Erlangove vzorce).

Keďže je systém uzavretý, do problémového vyhlásenia by sa mala pridať podmienka: tok prichádzajúcich požiadaviek je obmedzený, t.j. systém zaraďovania nemôže mať súčasne viac ako m požiadaviek (m je počet obsluhovaných objektov).

Ako hlavné kritérium charakterizujúce kvalitu fungovania posudzovaného systému zvolíme: 1) pomer priemernej dĺžky frontu k najväčšiemu počtu požiadaviek, ktoré sú súčasne v systéme obsluhy - koeficient prestojov obsluhovaného objektu; 2) pomer priemerného počtu nečinných obslužných kanálov k ich celkovému počtu je pomer nečinnosti obsluhovaného kanála.

Zvážte výpočet potrebných pravdepodobnostných charakteristík (ukazovatele výkonnosti) uzavretého QS.

1. Pravdepodobnosť, že v systéme existuje k požiadaviek za predpokladu, že ich počet nepresiahne počet servisných zariadení n:

Pk = α kP 0, (1 ≤ k ≤ n),

kde

λ je frekvencia (intenzita) prijímania požiadaviek do systému z jedného zdroja;

Priemerné trvanie služby jednej požiadavky;

m - najväčší možný počet požiadaviek, ktoré sú súčasne v systéme obsluhy;

n je počet servisných zariadení;

P 0 - pravdepodobnosť, že všetky servisné zariadenia sú voľné.

2. Pravdepodobnosť, že v systéme existuje k požiadaviek za predpokladu, že ich počet je väčší ako počet servisných zariadení:

Pk = α kP 0, (n ≤ k ≤ m),

kde

3. Pravdepodobnosť, že všetky servery sú voľné, je určená z podmienky

v dôsledku toho

4. Priemerný počet žiadostí čakajúcich na spustenie služby (priemerná dĺžka frontu):

5. Pomer prestojov dopytu pri čakaní na službu:

6. Pravdepodobnosť, že všetky servisné zariadenia sú obsadené:

7. Priemerný počet požiadaviek v systéme služieb (obsluhované a čakajúce na servis):

8. Pomer celkových prestojov požiadaviek na servis a čakania na servis:

9. Priemerný čas nečinnosti nároku vo fronte služieb:

10. Priemerný počet voľných účastníkov:

11. Pomer prestojov servisných vozidiel:

12. Pravdepodobnosť, že počet zákazníkov čakajúcich na obsluhu je väčší ako nejaké číslo B (pravdepodobnosť, že v servisnom rade je viac ako B zákazníkov):

V praxi ľudskej činnosti zaujímajú veľké miesto procesy radenia, ktoré sa vyskytujú v systémoch určených na opakované použitie pri riešení rovnakého typu problémov. Takéto systémy sa nazývajú systémy radenia (QS). Príkladmi takýchto systémov sú telefónne systémy, počítačové systémy, automobilový priemysel, letectvo, systémy údržby, obchody, predajne lístkov a podobne.

Každý systém pozostáva z určitého počtu obslužných jednotiek (prístroje, prístroje, prístroje „body, stanice), ktoré sa nazývajú servisné kanály. Podľa počtu kanálov sa QS delí na jednokanálové a viackanálové. jednokanálového systému radenia je znázornené na obr. 6.2.

Aplikácie zvyčajne nevstupujú do systému pravidelne, ale náhodne a tvoria náhodný tok aplikácií (požiadaviek). Samotné vybavenie každej požiadavky môže trvať buď určitý čas, alebo častejšie neurčitý čas. Náhodná povaha vedie k tomu, že QS je zaťažený nerovnomerne: v niektorých časových obdobiach sa nahromadí veľmi veľký počet aplikácií (buď sa dostanú do radu, alebo nechajú QS neobslúžený), zatiaľ čo v iných obdobiach QS pracuje s nedostatočným zaťažením. alebo je nečinný.

Ryža. 6.2.

Účelom štúdia systémov radenia je analyzovať kvalitu ich fungovania a identifikovať príležitosti na jej zlepšenie. Zároveň bude mať pojem „kvalita fungovania“ v každom jednotlivom prípade svoj špecifický význam a bude vyjadrený rôznymi kvantitatívnymi ukazovateľmi. Napríklad také kvantitatívne ukazovatele, ako je veľkosť frontu na obsluhu, priemerný čas obsluhy, čakanie na obsluhu alebo nájdenie požiadavky v servisnom systéme, doba nečinnosti servisných zariadení; dôveru, že všetky požiadavky prijaté systémom budú vybavené.

Pod kvalitou fungovania systému radenia sa teda rozumie nie kvalita vykonania konkrétnej práce, na ktorú bola prijatá požiadavka, ale miera uspokojenia potreby služby.

Predmetom teórie radenia je konštrukcia matematických modelov, ktoré spájajú dané prevádzkové podmienky QS (počet kanálov, ich výkon, charakter toku aplikácií atď.) s výkonnostnými ukazovateľmi QS, ktoré popisujú jeho schopnosť vyrovnať sa s tokom aplikácií.

Klasifikácia systémov radenia

Prvou vlastnosťou, ktorá umožňuje klasifikovať úlohy vo fronte, je správanie sa požiadaviek prijatých obslužným systémom v momente, keď sú všetky stroje zaneprázdnené.

V niektorých prípadoch reklamácia, ktorá vstúpi do systému v čase, keď sú všetky stroje vyťažené, nemôže čakať na ich uvoľnenie a ponecháva systém neobslúžený, t.j. pohľadávka pre daný systém podávania je stratená. Takéto systémy služieb sa nazývajú systémy so stratami a problémy formulované na ich základe sa nazývajú problémy služieb pre systémy so stratami.

Ak na druhej strane dopyt po vstupe do systému vstúpi do frontu a čaká na uvoľnenie zariadenia, potom sa takéto systémy nazývajú systémy s čakaním a zodpovedajúce úlohy sa nazývajú servisné úlohy v systémoch s čakaním. QS s čakaním sa delí na rôzne typy v závislosti od toho, ako je rad organizovaný: s obmedzenou alebo neobmedzenou dĺžkou frontu, s obmedzenou dobou čakania atď.

QS sa tiež líšia v počte požiadaviek, ktoré môžu byť súčasne v systéme obsluhy. Prideliť:

• 1) systémy s obmedzeným tokom požiadaviek;
• 2) systémy s neobmedzeným tokom požiadaviek.

V závislosti od foriem vnútornej organizácie služieb v systéme existujú:

• 1) systémy s objednaným servisom;
• 2) systémy s neusporiadanou službou.

Dôležitým krokom pri štúdiu QS je výber kritérií charakterizujúcich skúmaný proces. Výber závisí od typu skúmaných problémov, od cieľa, ktorý riešenie sleduje.

V praxi sa najčastejšie vyskytujú systémy, v ktorých je tok požiadaviek blízky najjednoduchším a prevádzkový čas sa riadi exponenciálnym distribučným zákonom. Tieto systémy sú najviac rozvinuté v teórii radenia.

V podmienkach podniku sú typické úlohy s čakaním, s konečným počtom obslužných zariadení, s obmedzeným tokom požiadaviek a s neusporiadanou obsluhou.

23. októbra 2013 o 14:22 hod

Squeak: Modeling Queuing Systems

• programovanie,
• OOP,
• Paralelné programovanie

O takom programovacom jazyku ako je Squeak je na Habrém veľmi málo informácií. Pokúsim sa o tom hovoriť v kontexte modelovania systémov radenia. Ukážem, ako napísať jednoduchú triedu, opísať jej štruktúru a použiť ju v programe, ktorý bude obsluhovať požiadavky cez niekoľko kanálov.

Pár slov o Squeakovi

Squeak je otvorená multiplatformová implementácia programovacieho jazyka Smalltalk-80 s dynamickým písaním a zberačom odpadu. Rozhranie je dosť špecifické, ale celkom vhodné na ladenie a analýzu. Squeak plne vyhovuje konceptu OOP. Všetko sa skladá z predmetov, dokonca aj zo štruktúr if-then-others, for, while s ich pomocou. Celá syntax sa scvrkáva na odoslanie správy objektu v tvare:

<объект> <сообщение>

Akákoľvek metóda vždy vráti objekt a možno naň poslať novú správu.
Squeak sa často používa na modelovanie procesov, ale môže sa použiť aj ako nástroj na vytváranie multimediálnych aplikácií a rôznych vzdelávacích platforiem.

Systémy radenia

Systémy radenia (QS) obsahujú jeden alebo viac kanálov, ktoré spracúvajú aplikácie z viacerých zdrojov. Čas na vybavenie každej požiadavky môže byť pevný alebo ľubovoľný, ako aj intervaly medzi ich príchodom. Môže to byť telefónna ústredňa, práčovňa, pokladne v obchode, písacia kancelária atď. Vyzerá to asi takto:

QS obsahuje niekoľko zdrojov, ktoré vstupujú do spoločného frontu a sú odosielané do servisu, keď sa kanály spracovania uvoľnia. V závislosti od špecifických vlastností reálnych systémov môže model obsahovať rôzny počet zdrojov požiadaviek a obslužných kanálov a mať rôzne obmedzenia na dĺžku fronty a s tým spojenú možnosť straty požiadaviek (zlyhaní).

Pri modelovaní QS sa zvyčajne riešia úlohy odhadu priemernej a maximálnej dĺžky frontu, frekvencie odmietnutia služby, priemerného zaťaženia kanála a určenia ich počtu. V závislosti od úlohy model obsahuje softvérové ​​bloky na zber, akumuláciu a spracovanie potrebných štatistických údajov o správaní procesov. Najbežnejšie používané modely toku udalostí v analýze QS sú regular a Poisson. Pravidelné sa vyznačujú rovnakým časom medzi výskytom udalostí, zatiaľ čo Poissonove sú náhodné.

Trochu matematiky

Pre Poissonov tok počet udalostí X spadajúce do dĺžkového intervalu τ (tau) susediaci s bodom t, distribuované podľa Poissonovho zákona:
kde a (t, τ)- priemerný počet udalostí vyskytujúcich sa v časovom intervale τ .
Priemerný počet udalostí vyskytujúcich sa za jednotku času sa rovná λ(t). Preto priemerný počet udalostí za časový interval τ , priliehajúce k časovému okamihu t, sa bude rovnať:

Čas T medzi dvoma udalosťami λ(t) = const = λ distribuované podľa zákona:
Hustota distribúcie náhodnej premennej T vyzerá ako:
Získať pseudonáhodné Poissonove postupnosti časových intervalov t i vyriešiť rovnicu:
kde RI je náhodné číslo rovnomerne rozložené v intervale.
V našom prípade to dáva výraz:

Generovaním náhodných čísel môžete písať celé zväzky. Tu, aby sme vygenerovali celé čísla rovnomerne rozložené v intervale, používame nasledujúci algoritmus:
kde RI- ďalšie náhodné celé číslo;
R- nejaké veľké prvočíslo (napr. 2311);
Q- celé číslo - horná hranica intervalu, napríklad 2 21 = 2097152;
rem- operácia získania zvyšku z delenia celých čísel.

Pôvodná hodnota R0 zvyčajne sa nastavuje ľubovoľne, napríklad pomocou hodnôt časovača:
Celkový čas sekúnd
Na získanie čísel rovnomerne rozložených v intervale používame operátor jazyka:

trieda Rand

Aby sme získali náhodné čísla rovnomerne rozdelené v intervale, vytvoríme triedu - generátor reálnych čísel:

Pohyblivá premennáWordSubclass: #Rand "názov triedy" instanceVariableNames: "" "premenné inštancie" classVariableNames: "R" "premenné triedy" poolDictionaries: "" "bežné slovníky" kategória: "Ukážka" "názov kategórie"
Metódy:

"Inicializácia" init R:= Celkový časSeconds.next "Ďalšie pseudonáhodné číslo" ďalej R:= (R * 2311 + 1) rem: 2097152. ^(R/2097152) asFloat
Ak chcete nastaviť počiatočný stav snímača, odošlite správu Rand init.
Ak chcete získať ďalšie náhodné číslo, odošlite Ďalší Rand.

Program na spracovanie žiadostí

Takže, ako jednoduchý príklad, urobme nasledovné. Predpokladajme, že potrebujeme simulovať udržiavanie pravidelného toku požiadaviek z jedného zdroja s náhodným časovým intervalom medzi požiadavkami. Existujú dva kanály rôzneho výkonu, ktoré umožňujú servis aplikácií v 2 a 7 časových jednotkách. Je potrebné evidovať počet požiadaviek obsluhovaných každým kanálom v intervale 100 časových jednotiek.

Squeak Code

"Deklarovanie dočasných premenných" | proc1 proc2 t1 t2 s1 s2 sysPrioritný front pokračovať r | "Počiatočné nastavenia premenných" Rand init. SysTime:= 0. s1:= 0. s2:= 0. t1:= -1. t2:= -1. pokračovať:=pravda. sysPriority:= Priorita aktívneho procesora. Front "Aktuálna priorita":= Nový semafor. "Model fronty nárokov" "Vytváranie procesu – model kanála 1" s1:= s1 + 1. proc1 pozastavenie."Pozastaviť proces čakajúce na ukončenie služby" ].proc1:= nula."Odstrániť odkaz na proces 1" ]priorita: (sysPriority + 1)) pokračovať. "Nová priorita je väčšia ako pozadie" "Vytvoriť proces - model kanála 2" .proc2:= nula.] priorita: (sysPriority + 1)) pokračovať. "Pokračujúci popis hlavného procesu a zdrojového modelu" pričom Pravda: [ r:= (Rand next * 10) zaokrúhlené. (r = 0) ifTrue: . ((SysTime rem: r) = 0) ifTrue: . "Odoslať požiadavku" "Prepínač servisného procesu" (t1 = SysTime) ifTrue: . (t2 = SysTime) ifTrue: . SysTime:= SysTime + 1. "Čas modelu tiká" ]. "Zobraziť stav počítadla požiadaviek" PopUpMenu informuje: "proc1: ",(s1 printString),", proc2: ",(s2 printString). pokračovať:= nepravda.

Pri spustení vidíme, že proces 1 dokázal spracovať 31 žiadostí a proces 2 iba 11: