Domov
Uvažujme o jednokanálovom systéme radenia s čakaním.
Budeme predpokladať, že prichádzajúci tok požiadaviek na službu je najjednoduchší tok s intenzitou λ.
Intenzita servisného toku je μ. Trvanie služby je náhodná premenná, ktorá podlieha zákonu o exponenciálnom rozdelení. Tok služieb je najjednoduchší Poissonov tok udalostí. Požiadavka prijatá, keď je kanál zaneprázdnený, je zaradená do frontu a čaká na službu. Budeme predpokladať, že veľkosť frontu je obmedzená a nemôže pojať viac ako m aplikácie, t.j. žiadosť, ktorá sa ocitla v momente svojho príchodu na SOT m +1 žiadostí (m
čaká v rade a jeden je obsluhovaný) opúšťa SOT.
(0‑1)
Systém rovníc popisujúcich proces v tomto systéme má riešenie:
Menovateľ prvého výrazu je geometrická postupnosť s prvým členom 1 a menovateľom ρ, odkiaľ dostaneme Pri ρ
(0‑8)
= 1 sa môžete uchýliť k priamemu výpočtu
Priemerný počet aplikácií v systéme.
(0‑9)
Keďže priemerný počet aplikácií v systémekde je priemerný počet aplikácií v prevádzke, potom vedieť, že zostáva nájsť. Pretože existuje len jeden kanál, potom počet obsluhovaných požiadaviek môže byť 0 alebo 1 s pravdepodobnosťou P° a P1 = 1 - P°
(0‑10)
podľa toho odkiaľ
(0‑11)
a priemerný počet aplikácií v systéme je.
Priemerná doba čakania na žiadosť vo fronte
t.j. priemerná doba čakania na aplikáciu vo fronte sa rovná priemernému počtu žiadostí vo fronte vydelenému intenzitou toku aplikácií.
Čas, počas ktorého aplikácia zostane v systéme, je súčtom času čakania aplikácie vo fronte a času služby. Ak je zaťaženie systému 100 %, potom =1/μ, inak = q/μ. Odtiaľto
(0‑13)
Obsah práce.
Príprava experimentálnych prístrojov .
Vykonáva sa podobne v súlade so všeobecnými pravidlami.
Výpočet pomocou analytického modelu.
1. Pripravte si nasledujúcu tabuľku v programe Microsoft Excel.
2. Do stĺpcov pre parametre QS tabuľky zapíšte počiatočné údaje, ktoré sú určené podľa pravidla:
m=1,2,3
(maximálna dĺžka frontu).
Pre každú hodnotu Požiadavka prijatá, keď je kanál zaneprázdnený, je zaradená do frontu a čaká na službu. Budeme predpokladať, že veľkosť frontu je obmedzená a nemôže pojať viac ako je potrebné nájsť teoretické a experimentálne hodnoty indikátorov QS pre nasledujúce dvojice hodnôt:
= <порядковый номер в списке группы>
3. Zadajte príslušné vzorce do stĺpcov s indikátormi analytického modelu.
Experimentujte na simulačnom modeli.
1. Nastavte režim spustenia s exponenciálne rozdeleným servisným časom nastavením hodnoty zodpovedajúceho parametra na 1.
2. Pre každú kombináciu Požiadavka prijatá, keď je kanál zaneprázdnený, je zaradená do frontu a čaká na službu. Budeme predpokladať, že veľkosť frontu je obmedzená a nemôže pojať viac ako a spustite model.
3. Výsledky jázd zapíšte do tabuľky.
4. Zadajte vzorce na výpočet priemernej hodnoty ukazovateľa do príslušných stĺpcov tabuľky P otvorené, q a A.
Analýza výsledkov .
1. Analyzujte výsledky získané teoretickými a experimentálnymi metódami a porovnávajte výsledky navzájom.
2. Pre m=3 nakreslite závislosti do jedného diagramu P otvorené z teoreticky a experimentálne získaných údajov.
Optimalizácia parametrov QS .
Vyriešte problém s optimalizáciou veľkosti počtu miest v rade Požiadavka prijatá, keď je kanál zaneprázdnený, je zaradená do frontu a čaká na službu. Budeme predpokladať, že veľkosť frontu je obmedzená a nemôže pojať viac ako pre zariadenie s priemernou dobou obsluhy = z pohľadu dosiahnutia maximálneho zisku. Ako podmienky problému vezmite:
- príjem z obsluhy jednej aplikácie rovný 80 USD/hod.,
- náklady na údržbu jedného zariadenia sa rovnajú 1 cu/hod.
1. Pre výpočty je vhodné vytvoriť tabuľku:
Prvý stĺpec je vyplnený hodnotami čísel v prirodzenom rade (1,2,3...).
Všetky bunky v druhom a treťom stĺpci sú vyplnené hodnotami a .
Vzorce pre stĺpce tabuľky v sekcii 0 sa prenesú do buniek stĺpcov od štvrtého do deviateho.
Do stĺpcov s počiatočnými údajmi sekcií Príjmy, Výdavky, Zisk zadajte hodnoty (pozri vyššie).
Do stĺpcov s vypočítanými hodnotami sekcií Príjmy, Výdavky, Zisk zapíšte vzorce výpočtu:
- počet aplikácií za jednotku času
Nr = A
- celkový príjem za jednotku času
I S = I r *N r
- celková spotreba za jednotku času
E S = E s + E q * (n-1)
- zisk za jednotku času
P = I S - E S
Kde
Ir - príjem z jednej aplikácie,
E s - prevádzkové náklady jedného zariadenia,
Eq - náklady na prevádzku jedného miesta v rade.
Grafy pre P otvorené,
- tabuľku s údajmi, aby ste našli to najlepšie m a hodnotu m opt,
- graf zisku za jednotku času oproti m.
Bezpečnostné otázky :
1) Uveďte stručný popis jednokanálového modelu QS s obmedzeným frontom.
2) Aké ukazovatele charakterizujú fungovanie jednokanálového QS s poruchami?
3) Ako sa vypočíta pravdepodobnosť p 0 ?
4) Ako sa vypočítavajú pravdepodobnosti p ja
5) Ako zistiť pravdepodobnosť zlyhania služby aplikácie?
6) Ako nájsť relatívnu šírku pásma?
7) Aká je absolútna priepustnosť?
8) Ako sa vypočíta priemerný počet aplikácií v systéme?
9) Uveďte príklady QS s obmedzeným frontom.
Úlohy.
1) Prístav má jedno nákladné kotvisko na vykladanie lodí. Prietok je 0,5 návštevy za deň. Priemerná doba vykládky jedného plavidla sú 2 dni. Ak sú v rade na vyloženie 3 plavidlá, prichádzajúce plavidlo je poslané do iného kotviska na vyloženie. Nájdite ukazovatele výkonnosti kotviska.
2) Informačná prepážka železničnej stanice prijíma telefonické požiadavky v intenzite 80 požiadaviek za hodinu. Operátor help desk odpovie na prichádzajúci hovor v priemere za 0,7 minúty. Ak je operátor zaneprázdnený, klient dostane správu „Počkajte na odpoveď“; požiadavka je zaradená do fronty, ktorej dĺžka nepresahuje 4 požiadavky. Uveďte hodnotenie práce help desku a možnosť jeho reorganizácie
Federálna agentúra pre vzdelávanie Ruskej federácie
FGOU SPO "Perevozsky stavebná vysoká škola"
Kurzy
v disciplíne "Matematické metódy"
na tému „SMO s obmedzenou čakacou dobou. Uzavreté QS"
Úvod................................................................. ....................................................... .............. 2
1. Základy teórie radenia ................................................... ...................... 3
1.1 Pojem náhodného procesu ................................................ ............................. 3
1.2 Markov náhodný proces............................................................ ...................... 4
1.3 Prúdy udalostí................................................................ ...................................................................... ............. 6
1.4 Kolmogorovove rovnice pre pravdepodobnosti stavu. Konečné pravdepodobnosti stavov ................................................................ .................................................................... .............. 9
1.5 Problémy teórie radenia ............................................................ ....... 13
1.6 Klasifikácia systémov radenia................................................................ ..... 15
2. Systémy radenia s čakaním................................................ ....... 16
2.1 Jednokanálový QS s čakaním............................................ ........... 16
2.2 Viackanálové QS s čakaním.................................................. .......... 25
3. Uzavreté QS............................................................ ...................................................... ... 37
Riešenie problému ................................................. ...................................................... 45
Záver................................................................ ...................................................... ...... .50
Referencie ................................................................ ...................................................... 51
V tomto kurze sa pozrieme na rôzne systémy radenia (QS) a siete radenia (Queuing).
Systém radenia (QS) je chápaný ako dynamický systém navrhnutý tak, aby efektívne obsluhoval tok požiadaviek (servisných požiadaviek) pri obmedzeniach systémových zdrojov.
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 podsystémov, ktorých interakcia je pravdepodobnostná. 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.
Súbor vzájomne prepojených QS sa nazýva čakacia sieť (stochastická sieť).
Na začiatok sa pozrieme na základy teórie QS, potom prejdeme k podrobnému oboznámeniu sa s QS s očakávaním a uzavretým QS. Súčasťou kurzu je aj praktická časť, v ktorej sa podrobne naučíme aplikovať teóriu v praxi.
Teória radenia je jedným z odvetví teórie pravdepodobnosti. Táto teória uvažuje pravdepodobnostný problémy a matematické modely (predtým sme uvažovali o deterministických matematických modeloch). Pripomeňme, že:
Deterministický matematický model odráža správanie objektu (systému, procesu) z perspektívy plná istota v prítomnosti a budúcnosti.
Pravdepodobný matematický model berie do úvahy vplyv náhodných faktorov na správanie objektu (systému, procesu), a preto hodnotí budúcnosť z hľadiska pravdepodobnosti určitých udalostí.
Tie. tu, ako napríklad v teórii hier, sa uvažuje o problémoch v podmienkach neistota .
Uvažujme najskôr o niektorých pojmoch, ktoré charakterizujú „stochastickú neistotu“, keď neisté faktory zahrnuté v probléme sú náhodné premenné (alebo náhodné funkcie), ktorých pravdepodobnostné charakteristiky sú buď známe, alebo sa dajú získať zo skúsenosti. Takáto neistota sa tiež nazýva „priaznivá“, „benígna“.
Presne povedané, náhodné poruchy sú vlastné každému procesu. Je jednoduchšie uviesť príklady náhodného procesu ako „nenáhodného“ procesu. Aj napríklad proces chodu hodín (zdá sa, že ide o prísne kalibrované dielo – „funguje ako hodiny“) podlieha náhodným zmenám (pohyb vpred, zaostávanie, zastavenie). Ale pokiaľ sú tieto poruchy nevýznamné a majú malý vplyv na parametre, ktoré nás zaujímajú, môžeme ich zanedbať a považovať proces za deterministický, nenáhodný.
Nech existuje nejaký systém S(technické zariadenie, skupina takýchto zariadení, technologický systém - stroj, areál, dielňa, podnik, priemysel a pod.). V systéme Súniky náhodný proces, ak v priebehu času mení svoj stav (prechádza z jedného stavu do druhého), navyše dovtedy neznámym náhodným spôsobom.
Príklady:
1. Systém S– technologický systém (strojová časť). Stroje sa z času na čas pokazia a sú opravené. Proces prebiehajúci v tomto systéme je náhodný.
2. Systém S- lietadlo letiace v danej nadmorskej výške po určitej trase. Rušivé faktory - poveternostné podmienky, chyby posádky atď., následky - hrboľatosť, porušenie letového poriadku atď.
Náhodný proces vyskytujúci sa v systéme sa nazýva Markovského, ak na akúkoľvek chvíľu t 0 pravdepodobnostných charakteristík procesu v budúcnosti závisí len od jeho momentálneho stavu t 0 a nezávisia od toho, kedy a ako systém tento stav dosiahol.
Nech je systém v určitom stave v momente t 0 S 0 Poznáme charakteristiku stavu systému v súčasnosti a všetko, čo sa počas neho udialo t <t 0 (história procesu). Vieme predpovedať (predpovedať) budúcnosť, t.j. čo sa stane keď t >t 0 ? Nie presne, ale niektoré pravdepodobnostné charakteristiky procesu možno nájsť v budúcnosti. Napríklad pravdepodobnosť, že po určitom čase systém S bude môcť S 1 alebo zostane v stave S 0 atď.
Príklad. Systém S- skupina lietadiel zúčastňujúca sa vzdušného boja. Nechaj x– počet „červených“ lietadiel, r– počet „modrých“ lietadiel. Podľa času t 0 počet preživších (nezostrelených) lietadiel, resp. x 0 , r 0 Zaujíma nás pravdepodobnosť, že v určitom okamihu bude početná prevaha na strane „červených“. Táto pravdepodobnosť závisí od toho, v akom stave sa systém v danom čase nachádzal t 0, a nie o tom, kedy a v akom poradí zostrelení zomreli až do momentu t 0 lietadiel.
V praxi sa s Markovovými procesmi v čistej forme zvyčajne nestretneme. Existujú však procesy, pri ktorých možno vplyv „praveku“ zanedbať. A pri štúdiu takýchto procesov možno použiť Markovove modely (teória radenia neuvažuje o Markovových systémoch radenia, ale matematický aparát, ktorý ich popisuje, je oveľa zložitejší).
V operačnom výskume majú veľký význam Markovove náhodné procesy s diskrétnymi stavmi a spojitým časom.
Proces sa nazýva proces diskrétneho stavu, ak sú jeho možné stavy S 1 , S 2, ... je možné určiť vopred a prechod systému zo stavu do stavu nastáva „skokom“ takmer okamžite.
Proces sa nazýva nepretržitý časový proces, ak momenty možných prechodov zo stavu do stavu nie sú vopred pevne dané, ale sú neisté, náhodné a môžu nastať kedykoľvek.
Príklad. Technologický systém (sekcia) S pozostáva z dvoch strojov, z ktorých každý môže zlyhať (zlyhať) v náhodnom časovom okamihu, po čom okamžite začne oprava jednotky, ktorá tiež pokračuje neznámy, náhodný čas. Možné sú nasledujúce stavy systému:
S 0 - oba stroje fungujú;
S 1 - prvý stroj sa opravuje, druhý pracuje;
S 2 - druhý stroj sa opravuje, prvý funguje;
S 3 - oba stroje sú v oprave.
Systémové prechody S zo stavu do stavu sa vyskytujú takmer okamžite, v náhodných okamihoch, keď konkrétny stroj zlyhá alebo je dokončená oprava.
Pri analýze náhodných procesov s diskrétnymi stavmi je vhodné použiť geometrickú schému - stavový graf. Vrcholy grafu sú stavy systému. Oblúky grafu predstavujú možné prechody zo stavu do stavu. Pre náš príklad je stavový graf znázornený na obr. 1.
Ryža. 1. Graf stavu systému
Poznámka. Prechod zo stavu S 0 palcov S 3 nie je na obrázku vyznačená, pretože predpokladá sa, že stroje zlyhajú nezávisle od seba. Zanedbávame možnosť súčasného zlyhania oboch strojov.
Stream udalosti– sled homogénnych udalostí, ktoré nasledujú za sebou v určitých náhodných časových okamihoch.
V predchádzajúcom príklade ide o tok porúch a tok obnovy. Ďalšie príklady: tok hovorov na telefónnej ústredni, tok zákazníkov v obchode atď.
Tok udalostí môže byť vizuálne znázornený sériou bodov na časovej osi O t- ryža. 2.
Ryža. 2. Obraz toku udalostí na časovej osi
Poloha každého bodu je náhodná a je tu znázornená iba jedna implementácia toku.
Intenzita toku udalosti ( ) je priemerný počet udalostí za jednotku času.
Pozrime sa na niektoré vlastnosti (typy) tokov udalostí.
Prúd udalostí je tzv stacionárne, ak jeho pravdepodobnostné charakteristiky nezávisia od času.
Konštantná je najmä intenzita stacionárneho prúdenia. Tok udalostí má nevyhnutne kondenzácie alebo zriedkavosti, ale nie sú pravidelného charakteru a priemerný počet udalostí za jednotku času je konštantný a nezávisí od času.
Prúd udalostí je tzv plynúť bez následkov, ak pre akékoľvek dva neprekrývajúce sa časové úseky a (pozri obr. 2) počet udalostí, ktoré pripadajú na jeden z nich, nezávisí od toho, koľko udalostí pripadá na druhý. Inými slovami to znamená, že udalosti, ktoré tvoria tok, sa objavujú v určitých časových bodoch nezávisle od seba a každý je spôsobený svojimi vlastnými príčinami.
Prúd udalostí je tzv obyčajný, ak sa v ňom udalosti objavujú po jednej, a nie v skupinách po viacerých naraz.
Prúd udalostí je tzv najjednoduchšie (alebo stacionárne Poisson), ak má tri vlastnosti naraz:
1) stacionárne;
2) obyčajný;
3) nemá žiadne následky.
Najjednoduchší tok má najjednoduchší matematický popis. Medzi tokmi hrá rovnakú zvláštnu úlohu ako zákon normálneho rozdelenia medzi inými distribučnými zákonmi. Totiž pri superponovaní dostatočne veľkého počtu nezávislých, stacionárnych a obyčajných tokov (vzájomne porovnateľných v intenzite) sa získa tok blízky najjednoduchšiemu.
Pre najjednoduchšie prúdenie s intervalom intenzity T medzi susednými podujatiami má tzv exponenciálne rozdelenie s hustotou:
kde je parameter exponenciálneho zákona.
Pre náhodnú premennú T, ktorá má exponenciálne rozdelenie, matematické očakávanie je prevrátená hodnota parametra a štandardná odchýlka sa rovná matematickému očakávaniu:
Vzhľadom na Markovove procesy s diskrétnymi stavmi a spojitým časom sa predpokladá, že všetky prechody systému S zo stavu do stavu sa vyskytujú pod vplyvom jednoduchých tokov udalostí (toky hovorov, toky porúch, toky obnovy atď.). Ak všetky toky udalostí prenášajú systém S od stavu k stavu najjednoduchšieho, potom proces vyskytujúci sa v systéme bude markovovský.
Takže systém v stave je ovplyvnený jednoduchým tokom udalostí. Hneď ako sa objaví prvá udalosť tohto toku, systém „preskočí“ zo stavu do stavu (na grafe stavu pozdĺž šípky).
Kvôli prehľadnosti je na grafe stavu systému pre každý oblúk označená intenzita toku udalostí, ktoré posúvajú systém pozdĺž tohto oblúka (šípka). - intenzita toku udalostí, ktorá prenáša systém zo stavu do . Takýto graf je tzv označené. Pre náš príklad je označený graf znázornený na obr. 3.
Ryža. 3. Označený graf stavu systému
Na tomto obrázku - intenzita toku zlyhania; - intenzita regeneračného toku.
Predpokladáme, že priemerný čas opravy stroja nezávisí od toho, či sa opravuje jeden stroj alebo oba naraz. Tie. Každý stroj opravuje samostatný špecialista.
Nech je systém v stave S 0 V stave S 1 je preložený tokom porúch prvého stroja. Jeho intenzita sa rovná:
kde je priemerný čas bezporuchovej prevádzky prvého stroja.
Od štátu S 1 palec S 0 sa systém prenesie tokom „dokončení opráv“ prvého stroja. Jeho intenzita sa rovná:
kde je priemerný čas opravy prvého stroja.
Intenzity tokov udalostí, ktoré prenášajú systém pozdĺž všetkých oblúkov grafu, sa vypočítajú podobným spôsobom. Keď máme k dispozícii označený stavový graf systému, skonštruujeme matematický model tohto procesu.
Nechajte zvažovaný systém S má -možné stavy. Pravdepodobnosť tého stavu je pravdepodobnosť, že v danom čase bude systém v stave. Je zrejmé, že v každom okamihu je súčet všetkých pravdepodobností stavov rovný jednej:
Nájsť všetky pravdepodobnosti stavov ako funkcie času, skladať a riešiť Kolmogorovove rovnice– špeciálny typ rovnice, v ktorej sú neznáme funkcie pravdepodobnosti stavov. Pravidlo na zostavovanie týchto rovníc je tu uvedené bez dôkazu. Ale predtým, ako to predstavíme, vysvetlíme si tento koncept konečná pravdepodobnosť stavu .
Čo sa stane s pravdepodobnosťou stavu pri ? Budú sa snažiť o nejaké limity? Ak tieto limity existujú a nezávisia od počiatočného stavu systému, potom sa volajú pravdepodobnosti konečného stavu .
kde je konečný počet stavov systému.
Pravdepodobnosti konečného stavu– to už nie sú premenné veličiny (funkcie času), ale konštantné čísla. Je zrejmé, že:
Pravdepodobnosť konečného stavu je v podstate priemerný relatívny čas, počas ktorého systém zostáva v tomto stave.
Napríklad systém S má tri štáty S 1 , S 2 a S 3. Ich konečná pravdepodobnosť je 0,2; 0,3 a 0,5. To znamená, že systém v obmedzujúcom stacionárnom stave strávi v tomto stave v priemere 2/10 svojho času S 1, 3/10 – schopný S 2 a 5/10 – schopný S 3 .
Pravidlo pre zostavenie Kolmogorovovej sústavy rovníc: v každej rovnici systému na ľavej strane je konečná pravdepodobnosť daného stavu vynásobená celkovou intenzitou všetkých tokov, vedúci z tohto stavu, A v jeho pravici časti- súčet súčinov intenzít všetkých tokov, zahrnuté v -tý štát, o pravdepodobnostiach štátov, z ktorých tieto toky pochádzajú.
Pomocou tohto pravidla napíšeme sústavu rovníc pre náš príklad :
.
Zdá sa, že tento systém štyroch rovníc so štyrmi neznámymi sa dá úplne vyriešiť. Ale tieto rovnice sú homogénne (nemajú voľný člen), a preto určujú neznáme len do ľubovoľného faktora. Môžete však použiť podmienku normalizácie: 
a použiť ho na riešenie systému. V tomto prípade môže byť jedna (ktorákoľvek) z rovníc vyradená (nasleduje ako dôsledok ostatných).
Pokračovanie príkladu. Nech sa intenzity prúdenia rovnajú: .
Zahodíme štvrtú rovnicu a namiesto toho pridáme podmienku normalizácie:
.
Tie. v obmedzujúcom, stacionárnom režime systému S v priemere 40 % času strávite v stave S 0 (oba stroje sú funkčné), 20% - v dobrom stave S 1 (prvý stroj sa opravuje, druhý funguje), 27% - v stave S 2 (druhý stroj je v oprave, prvý funguje), 13% - v stave S 3 (oba stroje sú v oprave). Poznanie týchto konečných pravdepodobností môže pomôcť odhadnúť priemernú účinnosť systému a pracovné zaťaženie opravných orgánov.
Nechajte systém S schopný S 0 (plná prevádzka) prináša príjem 8 konvenčných jednotiek za jednotku času, schopný S 1 – príjem 3 konvenčné jednotky, schopný S 2 – príjem 5 konvenčných jednotiek, schopný S 3 – negeneruje príjem. Potom sa v obmedzujúcom, stacionárnom režime bude priemerný príjem za jednotku času rovnať: konvenčným jednotkám.
Stroj 1 je opravený za zlomok času, ktorý sa rovná: . Stroj 2 je opravený za zlomok času, ktorý sa rovná: . Vyvstáva optimalizačný problém. Aj keď môžeme znížiť priemerný čas opravy prvého alebo druhého stroja (alebo oboch), bude nás to stáť určitú sumu. Otázkou je, či zvýšené príjmy spojené s rýchlejšími opravami preplatia zvýšené náklady na opravy? Budete musieť vyriešiť systém štyroch rovníc so štyrmi neznámymi.
Príklady zaraďovacích systémov (QS): telefónne ústredne, opravovne, pokladne, informačné pulty, obrábacie stroje a iné technologické systémy, riadiace systémy flexibilných výrobných systémov atď.
Každý QS pozostáva z určitého počtu servisných jednotiek, ktoré sa volajú servisné kanály(sú to stroje, transportné vozíky, roboty, komunikačné linky, pokladníci, predajcovia a pod.). Každý QS je navrhnutý tak, aby slúžil nejakému druhu tok aplikácií(požiadavky) prichádzajúce v niektorých náhodných okamihoch v čase.
Obsluha požiadavky pokračuje nejaký, všeobecne povedané, náhodný čas, po ktorom sa kanál uvoľní a je pripravený prijať ďalšiu požiadavku. Náhodná povaha toku aplikácií a servisného času vedie k tomu, že počas určitých časových období sa na vstupe QS nahromadí nadmerne veľký počet aplikácií (buď sa zaradia do frontu, alebo nechajú QS neobslúžený). V ostatných obdobiach bude systém pracovať s nedostatočným zaťažením alebo bude úplne nečinný.
Proces operácie QS je náhodný proces s diskrétnymi stavmi a nepretržitým časom. Stav QS sa náhle zmení, keď nastanú určité udalosti (príchod novej aplikácie, ukončenie služby, moment, keď z radu odíde aplikácia, ktorá je unavená z čakania).
Predmet teórie radenia– konštrukcia matematických modelov, ktoré spájajú dané prevádzkové podmienky QS (počet kanálov, ich produktivita, prevádzkové pravidlá, charakter toku požiadaviek) s charakteristikami, ktoré nás zaujímajú – ukazovatele efektívnosti QS. Tieto ukazovatele opisujú schopnosť SOT vyrovnať sa s tokom žiadostí. Môžu to byť: priemerný počet aplikácií obsluhovaných QS za jednotku času; priemerný počet obsadených kanálov; priemerný počet žiadostí vo fronte; priemerná doba čakania na obsluhu atď.
Matematická analýza práce QS je značne uľahčená, ak je proces tejto práce markovovský, t.j. prúdy udalostí, ktoré prenášajú systém zo stavu do stavu, sú najjednoduchšie. V opačnom prípade sa matematický popis procesu veľmi skomplikuje a len zriedka je možné priviesť ho do špecifických analytických závislostí. V praxi sa nemarkovské procesy redukujú na markovovské procesy s aproximáciou. Nasledujúci matematický aparát popisuje Markovove procesy.
Prvá divízia (na základe prítomnosti frontov):
1. QS s poruchami;
2. Poradie s radom.
V 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á.
V SMO 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 poradie usporiadané - 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 prednostnou službou, t.j. niektoré žiadosti sú spracovávané mimo poradia atď.
Okrem toho sa QS delia na otvorené QS a uzavreté QS.
V otvorenom QS charakteristiky toku požiadaviek nezávisia od stavu samotného QS (koľko kanálov je obsadených). V uzavretom QS– závisieť. 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.
Klasifikácia SMO sa zďaleka neobmedzuje na vyššie uvedené odrody, ale to stačí.
Uvažujme o najjednoduchšom QS s čakaním - jednokanálový systém (n - 1), ktorý prijíma tok požiadaviek s intenzitou ; intenzita služby (t.j. v priemere nepretržite obsadený kanál bude vydávať obsluhované požiadavky na jednotku (času). Požiadavka prijatá v čase, keď je kanál zaneprázdnený, je zaradená do frontu a čaká na obsluhu.
Systém s obmedzenou dĺžkou frontu. Predpokladajme najskôr, že počet miest v rade je obmedzený počtom m, t.j. ak aplikácia príde v čase, keď už sú vo fronte m-aplikácie, nechá systém bez obsluhy. V budúcnosti nasmerovaním m do nekonečna získame charakteristiky jednokanálového QS bez obmedzenia dĺžky frontu.
Stavy QS očíslujeme podľa počtu aplikácií v systéme (obsluhovaných aj čakajúcich na obsluhu):
Kanál je bezplatný;
Kanál je zaneprázdnený, nie je tam žiadny front;
Kanál je zaneprázdnený, jedna aplikácia je vo fronte;
Kanál je zaneprázdnený, k-1 aplikácií je vo fronte;
Kanál je zaneprázdnený, aplikácie sú vo fronte.
GSP je znázornený na obr. 4. Všetky intenzity tokov udalostí pohybujúcich sa do systému pozdĺž šípok zľava doprava sú rovné a sprava doľava - . Tok požiadaviek skutočne posúva systém pozdĺž šípok zľava doprava (akonáhle príde požiadavka, systém prejde do ďalšieho stavu), sprava doľava - tok „uvoľnení“ rušného kanála, ktorý má intenzitu (akonáhle je obsluhovaná ďalšia požiadavka, kanál sa buď uvoľní, alebo zníži počet aplikácií v rade).
Ryža. 4. Jednokanálové QS s čakaním
Na obr. 4 diagram je diagram reprodukcie a smrti. Napíšme výrazy pre limitné pravdepodobnosti stavov:
(5)
alebo pomocou: :
(6)
Posledný riadok v (6) obsahuje geometrickú postupnosť s prvým členom 1 a menovateľom p, z čoho dostaneme:
(7)
v súvislosti s ktorými majú obmedzujúce pravdepodobnosti formu:
(8).
Výraz (7) platí len pre< 1 (при = 1 она дает неопределенность вида 0/0). Сумма геометрической прогрессии со знаменателем = 1 равна m+2, и в этом случае:
Stanovme charakteristiky QS: pravdepodobnosť zlyhania, relatívna priepustnosť q, absolútna priepustnosť A, priemerná dĺžka frontu, priemerný počet aplikácií spojených so systémom, priemerný čas čakania vo fronte, priemerný čas strávený aplikáciou v QS .
Pravdepodobnosť zlyhania. Je zrejmé, že žiadosť je odmietnutá iba vtedy, ak je kanál obsadený a všetky t-miesta vo fronte sú tiež obsadené:
(9).
Relatívna šírka pásma:
(10).
Priemerná dĺžka frontu. Nájdite priemerný počet žiadostí vo fronte ako matematické očakávanie diskrétnej náhodnej premennej R-počet žiadostí vo fronte:
S pravdepodobnosťou je jedna aplikácia vo fronte, s pravdepodobnosťou sú dve aplikácie, vo všeobecnosti s pravdepodobnosťou je vo fronte k-1 aplikácií atď., z ktorých:
(11).
Keďže súčet v (11) možno interpretovať ako deriváciu súčtu geometrickej progresie:
Nahradením tohto výrazu do (11) a použitím z (8) nakoniec dostaneme:
(12).
Priemerný počet aplikácií v systéme. Ďalej získame vzorec pre priemerný počet požiadaviek spojených so systémom (stojí vo fronte a sú obsluhované). Keďže , kde je priemerný počet aplikácií v prevádzke, ak je známe k, zostáva určiť . Keďže existuje len jeden kanál, počet obsluhovaných požiadaviek môže byť 0 (s pravdepodobnosťou ) alebo 1 (s pravdepodobnosťou 1 - ), z čoho:
.
a priemerný počet aplikácií spojených s QS je:
(13).
Priemerná doba čakania na žiadosť vo fronte. Označme to ; ak požiadavka príde do systému v určitom okamihu, potom s pravdepodobnosťou servisný kanál nebude obsadený a nebude musieť čakať v rade (čakacia doba je nula). S najväčšou pravdepodobnosťou príde do systému v čase, keď sa vybavuje nejaká požiadavka, ale nebude pred ňou žiadny rad a žiadosť počká na začiatok svojej obsluhy určitý čas (priemerný čas vybavovania jedného žiadosť). Existuje pravdepodobnosť, že pred posudzovanou aplikáciou bude v poradí ďalšia aplikácia a priemerná doba čakania sa bude rovnať , atď.
Ak k=m+1, t.j. keď novo prichádzajúca požiadavka nájde obslužný kanál zaneprázdnený a m-požiadavky vo fronte (pravdepodobnosť toho), tak v tomto prípade sa požiadavka nezaradí do radu (a nie je doručená), takže čakacia doba je nulová. Priemerná čakacia doba bude:
ak tu dosadíme výrazy za pravdepodobnosti (8), dostaneme:
(14).
Tu používame vzťahy (11), (12) (derivácia geometrickej postupnosti), ako aj z (8). Pri porovnaní tohto výrazu s (12) si všimneme, že inými slovami, priemerný čas čakania sa rovná priemernému počtu žiadostí vo fronte vydelenému intenzitou toku žiadostí.
(15).
Priemerný čas, počas ktorého aplikácia zostáva v systéme. Označme matematické očakávanie náhodnej premennej ako čas zotrvania požiadavky v QS, čo je súčet priemerného času čakania v rade a priemerného času obsluhy. Ak je zaťaženie systému 100 %, samozrejme, inak:
.
Príklad 1. Čerpacia stanica (čerpacia stanica) je čerpacia stanica s jedným servisným kanálom (jedno čerpadlo).
Priestor na stanici umožňuje, aby v rade na tankovanie boli naraz maximálne tri autá (m = 3). Ak sú v rade už tri autá, ďalšie auto prichádzajúce na stanicu sa do radu nezaradí. Tok áut prichádzajúcich na tankovanie má intenzitu = 1 (auto za minútu). Proces tankovania trvá v priemere 1,25 minúty.
Definuj:
pravdepodobnosť zlyhania;
relatívna a absolútna kapacita čerpacích staníc;
priemerný počet áut čakajúcich na doplnenie paliva;
priemerný počet áut na čerpacej stanici (vrátane tých, ktoré sú v servise);
priemerná doba čakania na auto v rade;
priemerný čas, ktorý auto strávi na čerpacej stanici (vrátane servisu).
Inými slovami, priemerná doba čakania sa rovná priemernému počtu žiadostí vo fronte vydelenému intenzitou toku žiadostí.
Najprv zistíme zníženú intenzitu toku aplikácií: =1/1,25=0,8; = 1/0,8 = 1,25.
Podľa vzorcov (8):
Pravdepodobnosť zlyhania je 0,297.
Relatívna kapacita QS: q=1-=0,703.
Absolútna priepustnosť QS: A==0,703 auta za minútu.
Priemerný počet áut v rade zistíme pomocou vzorca (12):
tie. Priemerný počet áut čakajúcich v rade na naplnenie čerpacej stanice je 1,56.
K tejto hodnote sa pripočíta priemerný počet vozidiel v prevádzke:
dostaneme priemerný počet áut spojených s čerpacou stanicou.
Priemerná doba čakania na auto v rade podľa vzorca (15):
Pripočítaním tejto hodnoty dostaneme priemerný čas, ktorý auto strávi na čerpacej stanici:
Systémy s neobmedzeným čakaním. V takýchto systémoch nie je hodnota m obmedzená, a preto hlavné charakteristiky možno získať prechodom na limit v predtým získaných výrazoch (5), (6) atď.
Všimnite si, že menovateľ v poslednom vzorci (6) je súčtom nekonečného počtu členov geometrickej postupnosti. Tento súčet konverguje, keď progresia nekonečne klesá, t.j. pri<1.
Dá sa to dokázať<1 есть условие, при котором в СМО с ожиданием существует предельный установившийся режим, иначе такого режима не существует, и очередь при будет неограниченно возрастать. Поэтому в дальнейшем здесь предполагается, что <1.
Ak, potom vzťahy (8) majú tvar:
(16).
Ak neexistujú žiadne obmedzenia týkajúce sa dĺžky frontu, každá aplikácia, ktorá príde do systému, bude obsluhovaná, preto q=1, 
.
Priemerný počet žiadostí vo fronte získame z (12) na:
Priemerný počet aplikácií v systéme podľa vzorca (13) pri:
.
Priemerný čas čakania sa získa zo vzorca (14) s:
.
Napokon, priemerný čas, počas ktorého aplikácia zostáva v QS, je:
Systém s obmedzenou dĺžkou frontu. Uvažujme kanál QS s čakaním, ktorý prijíma tok požiadaviek s intenzitou ; intenzita služby (pre jeden kanál); počet miest v rade.
Stavy systému sú očíslované podľa počtu požiadaviek spojených so systémom:
žiadny rad:
Všetky kanály sú bezplatné;
Jeden kanál je obsadený, zvyšok je voľný;
-kanály sú obsadené, ostatné nie;
Všetky kanály sú obsadené, neexistujú žiadne voľné kanály;
je tam rad:
Všetky n-kanály sú obsadené; jedna aplikácia je vo fronte;
Všetky n-kanály, r-požiadavky vo fronte sú obsadené;
Všetky n-kanály, r-požiadavky vo fronte sú obsadené.
GSP je znázornený na obr. 17. Každá šípka je označená zodpovedajúcimi intenzitami tokov udalostí. Po šípkach zľava doprava sa systém prenáša vždy rovnakým tokom požiadaviek s intenzitou od
Ryža. 17. Viackanálové QS s čakaním
Graf je typický pre procesy reprodukcie a smrti, pre ktoré bolo predtým získané riešenie. Výrazy pre limitné pravdepodobnosti stavov napíšme pomocou zápisu: (tu používame výraz pre súčet geometrickej postupnosti s menovateľom).
Boli teda nájdené všetky pravdepodobnosti stavu.
Poďme určiť výkonové charakteristiky systému.
Pravdepodobnosť zlyhania. Prichádzajúca požiadavka je odmietnutá, ak sú všetky n-kanály a všetky m-miesta vo fronte obsadené:
(18)
Relatívna priepustnosť dopĺňa pravdepodobnosť zlyhania na jednu:
Absolútna priepustnosť QS:
(19)
Priemerný počet obsadených kanálov. Pre QS s odmietnutiami sa zhodoval s priemerným počtom žiadostí v systéme. Pre QS s frontom sa priemerný počet obsadených kanálov nezhoduje s priemerným počtom aplikácií v systéme: posledná hodnota sa líši od prvej o priemerný počet aplikácií vo fronte.
Priemerný počet obsadených kanálov označme . Každý obsadený kanál slúži priemerne A-nároky za jednotku času a QS ako celok slúži priemerne A-nároky za jednotku času. Rozdelením jedného druhým dostaneme:
Priemerný počet požiadaviek vo fronte možno vypočítať priamo ako matematické očakávanie diskrétnej náhodnej premennej:
(20)
Aj tu (výraz v zátvorkách) nastáva derivácia súčtu geometrickej postupnosti (pozri vyššie (11), (12) - (14)), pomocou vzťahu pre ňu dostaneme:
Priemerný počet aplikácií v systéme:
Priemerná doba čakania na žiadosť vo fronte. Zoberme si niekoľko situácií, ktoré sa líšia v tom, v akom stave nájde systém novo prichádzajúca požiadavka a ako dlho bude musieť čakať na obsluhu.
Ak požiadavka nenájde všetky kanály obsadené, nebude musieť vôbec čakať (zodpovedajúce výrazy v matematickom očakávaní sú rovné nule). Ak požiadavka príde v čase, keď sú všetky n-kanály zaneprázdnené a nie je tam žiadny front, bude musieť čakať v priemere dobu rovnú (pretože „tok uvoľnenia“ -kanálov má intenzitu ). Ak požiadavka zistí, že všetky kanály sú zaneprázdnené a jedna požiadavka pred ňou vo fronte, bude musieť čakať v priemere určitý čas (na každú požiadavku vpredu) atď. Ak sa požiadavka ocitne vo fronte - bude musieť v priemere počkať Ak novoprijatá požiadavka nájde m-žiadosti už vo fronte, nebude vôbec čakať (ale nebude doručená). Priemerný čas čakania zistíme vynásobením každej z týchto hodnôt zodpovedajúcimi pravdepodobnosťami:
(21)
Rovnako ako v prípade jednokanálového QS s čakaním poznamenávame, že tento výraz sa od výrazu pre priemernú dĺžku frontu (20) líši len faktorom , t.j.
.
Priemerný čas, počas ktorého požiadavka zostáva v systéme, ako aj pre jednokanálový QS, sa líši od priemerného času čakania priemerným časom služby vynásobeným relatívnou priepustnosťou:
.
Systémy s neobmedzenou dĺžkou frontu. Uvažovali sme o kanálovom QS s čakaním, kedy v rade nemôže byť súčasne viac ako m-požiadaviek.
Rovnako ako predtým, pri analýze systémov bez obmedzení je potrebné uvažovať získané vzťahy pre .
Pravdepodobnosti stavov získame zo vzorcov prechodom k limite (v ). Všimnite si, že súčet zodpovedajúcej geometrickej progresie konverguje a diverguje pri >1. Za predpokladu, že<1 и устремив в формулах величину m к бесконечности, получим выражения для предельных вероятностей состояний:
(22)
Pravdepodobnosť poruchy, relatívna a absolútna priepustnosť. Keďže každá požiadavka bude skôr či neskôr obsluhovaná, charakteristiky priepustnosti QS budú:
Priemerný počet žiadostí vo fronte sa získa z (20):
,
a priemerná doba čakania je od (21):
.
Priemerný počet obsadených kanálov, ako predtým, sa určuje prostredníctvom absolútnej priepustnosti:
.
Priemerný počet aplikácií spojených s QS je definovaný ako priemerný počet aplikácií vo fronte plus priemerný počet aplikácií v prevádzke (priemerný počet obsadených kanálov):
Príklad 2. Čerpacia stanica s dvoma čerpadlami (n = 2) obsluhuje prúd áut s intenzitou =0,8 (aut za minútu). Priemerný servisný čas na stroj:
Iná čerpacia stanica sa v okolí nenachádza, a tak sa rad áut pred čerpacou stanicou môže rozrastať takmer neobmedzene. Nájdite vlastnosti QS.
Od r<1, очередь не растет безгранично и имеет смысл говорить о предельном стационарном режиме работы СМО. По формулам (22) находим вероятности состояний:
atď.
Priemerný počet obsadených kanálov zistíme vydelením absolútnej kapacity QS A = = 0,8 intenzitou služby = 0,5:
Pravdepodobnosť, že sa na čerpacej stanici nebude stáť v rade, bude:
Priemerný počet áut v rade:
Priemerný počet áut na čerpacích staniciach:
Priemerná doba čakania v rade:
Priemerný čas, ktorý auto strávi na čerpacej stanici:
QS s obmedzenou čakacou dobou. Predtým sme uvažovali o systémoch s čakaním obmedzeným len dĺžkou frontu (počet m-požiadaviek súčasne vo fronte). V takomto QS aplikácia, ktorá narástla vo fronte, ho neopustí, kým nečaká na službu. V praxi existujú aj iné typy QS, pri ktorých môže aplikácia po určitom čase opustiť front (tzv. „netrpezlivé“ aplikácie).
Uvažujme QS tohto typu za predpokladu, že obmedzenie čakacej doby je náhodná premenná.
Predpokladajme, že existuje n-kanálový čakací QS, v ktorom je počet miest vo fronte neobmedzený, ale čas, keď požiadavka zostáva vo fronte, je náhodná premenná so strednou hodnotou, takže každá požiadavka vo fronte je podlieha istému Poissonovmu „toku starostlivosti“ s intenzitou:
Ak je tento tok Poisson, potom proces vyskytujúci sa v QS bude markovovský. Nájdite na to pravdepodobnosti stavu. Číslovanie stavov systému je spojené s počtom aplikácií v systéme – obsluhovaných aj stojacich vo fronte:
žiadny rad:
Všetky kanály sú bezplatné;
Jeden kanál je obsadený;
Dva kanály sú obsadené;
Všetky n-kanály sú obsadené;
je tam rad:
Všetky n-kanály sú obsadené, jedna požiadavka je vo fronte;
Všetky n-kanály sú obsadené, r-požiadavky sú vo fronte atď.
Graf stavov a prechodov sústavy je na obr. 23.
Ryža. 23. QS s obmedzenou čakacou dobou
Označme tento graf ako predtým; všetky šípky vedúce zľava doprava budú indikovať intenzitu toku aplikácií. Pre stavy bez frontu budú šípky vedúce z nich sprava doľava, ako predtým, indikovať celkovú intenzitu toku obsluhujúceho všetky obsadené kanály. Čo sa týka štátov s radom, šípky vedúce z nich sprava doľava budú mať celkovú intenzitu toku služieb všetkých n-kanálov plus zodpovedajúcu intenzitu toku odchodov z radu. Ak sú vo fronte r-aplikácie, potom sa celková intenzita toku odchodov bude rovnať .
Ako je možné vidieť z grafu, existuje vzor reprodukcie a smrti; pomocou všeobecných výrazov pre obmedzujúce pravdepodobnosti stavov v tejto schéme (pomocou skrátených zápisov píšeme:
(24)
Všimnime si niektoré vlastnosti QS s obmedzeným čakaním v porovnaní s predtým zvažovanými QS so žiadosťami „pacientov“.
Ak dĺžka fronty nie je obmedzená a požiadavky sú „trpezlivé“ (neopúšťajte front), potom režim stacionárneho limitu existuje iba v prípade (v , sa príslušná nekonečná geometrická progresia rozchádza, čo fyzicky zodpovedá neobmedzenému rastu z radu na ).
Naopak, pri QS s „netrpezlivými“ požiadavkami, ktoré skôr či neskôr opustia front, sa vždy dosiahne zavedený servisný režim na, bez ohľadu na zníženú intenzitu toku požiadaviek. Vyplýva to zo skutočnosti, že rad pre v menovateli vzorca (24) konverguje pre akékoľvek kladné hodnoty a .
Pre QS s „netrpezlivými“ požiadavkami pojem „pravdepodobnosť zlyhania“ nedáva zmysel – každá požiadavka sa dostane do radu, ale nemusí čakať na službu a odíde v predstihu.
Relatívna priepustnosť, priemerný počet požiadaviek vo fronte. Relatívna kapacita q takéhoto QS sa môže vypočítať nasledovne. Je zrejmé, že všetky aplikácie budú obsluhované, okrem tých, ktoré opustia front v predstihu. Vypočítajme si priemerný počet aplikácií, ktoré predčasne opustia front. Na tento účel vypočítame priemerný počet žiadostí vo fronte:
Každá z týchto aplikácií podlieha „toku odchodov“ s intenzitou . To znamená, že z priemerného počtu -aplikácií vo fronte v priemere -aplikácie odídu bez čakania na obsluhu, -aplikácie za jednotku času a celkovo za jednotku času sa v priemere -aplikácie obslúžia. Relatívna kapacita QS bude:
Stále získavame priemerný počet obsadených kanálov vydelením absolútnej šírky pásma A:
(26)
Priemerný počet aplikácií vo fronte. Vzťah (26) vám umožňuje vypočítať priemerný počet aplikácií vo fronte bez sčítania nekonečných sérií (25). Z (26) získame:
a priemerný počet obsadených kanálov zahrnutých v tomto vzorci možno nájsť ako matematické očakávanie náhodnej premennej Z s hodnotami 0, 1, 2,..., n s pravdepodobnosťami,:
Na záver poznamenávame, že ak vo vzorcoch (24) prejdeme na limit pri (alebo, čo je to isté, pri ), získajú sa vzorce (22), t. j. „netrpezlivé“ aplikácie sa stanú „trpezlivými“.
Doteraz sme uvažovali o systémoch, v ktorých vstupný tok nie je nijako spojený s výstupným tokom. Takéto systémy sa nazývajú open-loop. V niektorých prípadoch sú obsluhované požiadavky opäť prijaté na vstupe s oneskorením. Takéto QS sa nazývajú uzavreté. Príkladom uzavretých systémov je klinika obsluhujúca danú oblasť, tím pracovníkov priradených k skupine strojov.
V uzavretom QS cirkuluje rovnaký konečný počet potenciálnych požiadaviek. Kým sa potenciálna požiadavka nerealizuje ako servisná požiadavka, považuje sa za v oneskorenom bloku. V momente implementácie vstupuje do samotného systému. Napríklad pracovníci udržiavajú skupinu strojov. Každý stroj je potenciálnou požiadavkou, ktorá sa v momente poruchy mení na reálnu. Kým stroj pracuje, je v bloku oneskorenia a od okamihu poruchy až do konca opravy je v samotnom systéme. Každý pracovník je servisným kanálom.
Nechaj n- počet servisných kanálov, s- počet potenciálnych aplikácií, n <s , - intenzita toku aplikácií pre každú potenciálnu požiadavku, μ - intenzita služby:
Pravdepodobnosť výpadku systému je určená vzorcom
R
0
= 
.
Konečné pravdepodobnosti stavov systému:
Pk= pri k
Priemerný počet obsadených kanálov je vyjadrený prostredníctvom týchto pravdepodobností
=P 1 + 2P 2 +…+n(P n + P n+ 1 +…+P s) alebo
=P 1 + 2P 2 +…+(n- 1)P n- 1 +n( 1-P 0 -P 1 -…-P n-1 ).
Pomocou toho zistíme absolútnu priepustnosť systému:
ako aj priemerný počet aplikácií v systéme
M=s- =s- .
Príklad 1. Vstup trojkanálového QS s poruchami prijíma tok požiadaviek s intenzitou =4 požiadavky za minútu, čas na obsluhu požiadavky jedným kanálom t obs = 1/μ = 0,5 min. Je z hľadiska kapacity QS výhodné prinútiť všetky tri kanály obsluhovať požiadavky naraz a priemerný čas obsluhy sa skráti trojnásobne? Ako to ovplyvní priemerný čas, ktorý aplikácia strávi v SOT?
Riešenie. Pravdepodobnosť výpadku trojkanálového QS zistíme pomocou vzorca
ρ = /μ = 4/2 = 2, n = 3,
P 0 = = = 0,158.
Pravdepodobnosť zlyhania je určená vzorcom:
P otvorené = P n ==
P otvorené = 0,21.
Relatívna priepustnosť systému:
R obsl = 1-R otvorené 1-0,21=0,79.
Absolútna priepustnosť systému:
A= P obsl 3,16.
Priemerný počet obsadených kanálov je určený vzorcom:
1,58, podiel kanálov obsadených servisom,
q = 0,53.
Priemerný čas, počas ktorého aplikácia zostane v QS, sa zistí ako pravdepodobnosť, že žiadosť bude prijatá do služby, vynásobená priemerným časom služby: t SMO 0,395 min.
Spojením všetkých troch kanálov do jedného dostaneme jednokanálový systém s parametrami μ= 6, ρ= 2/3. V prípade jednokanálového systému je pravdepodobnosť výpadku:
R 0 = = =0,6,
pravdepodobnosť zlyhania:
P otvorené =ρ P 0 = = 0,4,
relatívna priepustnosť:
R obsl = 1-R otvorené =0,6,
absolútna priepustnosť:
A = P obs = 2,4.
t SMO =P obsl= = 0,1 min.
V dôsledku spojenia kanálov do jedného sa priepustnosť systému znížila so zvyšujúcou sa pravdepodobnosťou zlyhania. Priemerný čas, ktorý aplikácia strávi v systéme, sa znížil.
Príklad 2. Vstup trojkanálového QS s neobmedzeným frontom prijíma tok požiadaviek s intenzitou = 4 aplikácie za hodinu, priemerný čas na obsluhu jednej aplikácie t=1/μ=0,5 h Nájdite ukazovatele výkonu systému.
Pre uvažovaný systém n =3, = 4, μ=1/0,5=2, p= /μ=2, ρ/ n =2/3<1. Определяем вероятность простоя по формуле:
P= 
.
P
0
= 
=1/9.
Priemerný počet žiadostí vo fronte zistíme pomocou vzorca:
L
=
.
L = = .
Priemerný čas čakania na aplikáciu vo fronte vypočítame pomocou vzorca:
t= = 0,22 hodiny.
Priemerný čas, počas ktorého aplikácia zostáva v systéme:
T = t+ 0,22+0,5=0,72.
Príklad 3. V kaderníctve pracujú 3 kaderníčky, v čakárni sú 3 kreslá. Tok klientov má intenzitu = 12 klientov za hodinu. Priemerný servisný čas t obsl = 20 min. Určte relatívnu a absolútnu priepustnosť systému, priemerný počet obsadených stoličiek, priemernú dĺžku radu, priemerný čas, ktorý klient strávi v kaderníctve.
Pre túto úlohu n =3, Požiadavka prijatá, keď je kanál zaneprázdnený, je zaradená do frontu a čaká na službu. Budeme predpokladať, že veľkosť frontu je obmedzená a nemôže pojať viac ako =3, =12, μ =3, ρ =4, ρ/n= 4/3. Pravdepodobnosť prestojov je určená vzorcom:
R
0
=
.
P
0
= 
0,012.
Pravdepodobnosť odmietnutia služby je určená vzorcom
P otvorené =P n+m = .
P OTVORENÉ =Pn + m 0,307.
Relatívna kapacita systému, t.j. servisná pravdepodobnosť:
P obsl =1-P otvorené 1-0,307=0,693.
Absolútna priepustnosť:
A= P obsl 12 .
Priemerný počet obsadených kanálov:
.
Priemerná dĺžka frontu je určená vzorcom:
L
=
L= 
1,56.
Priemerná doba čakania na službu vo fronte:
t= h.
Priemerný počet žiadostí o SOT:
M=L + .
Priemerný čas, počas ktorého aplikácia zostáva v SOT:
T=M/ 0,36 hodiny
Príklad 4. Pracovník obsluhuje 4 stroje. Každý stroj zlyhá s intenzitou =0,5 poruchy za hodinu, priemerný čas opravy t rem=1/μ=0,8 h Určte priepustnosť systému.
Tento problém sa týka uzavretého QS, μ = 1,25, p = 0,5/1,25 = 0,4. Pravdepodobnosť prestojov pracovníka je určená vzorcom:
R
0
=
.
P
0
= 
.
Pravdepodobnosť zamestnania pracovníka R zan = 1-P 0 . A=( 1-P 0 )μ =0,85μ stroja za hodinu.
Úloha:
Dvaja pracovníci obsluhujú skupinu štyroch strojov. Zastavenie pracovného stroja nastáva v priemere po 30 minútach. Priemerný čas nastavenia je 15 minút. Prevádzkový čas a čas nastavenia sú rozdelené podľa exponenciálneho zákona.
Zistite priemerný podiel voľného času každého pracovníka a priemerný čas prevádzky stroja.
Nájdite rovnaké charakteristiky pre systém, v ktorom:
a) každý pracovník má pridelené dva stroje;
b) dvaja pracovníci vždy obsluhujú stroj spoločne a s dvojnásobnou intenzitou;
c) jediný chybný stroj obsluhujú obaja pracovníci naraz (s dvojnásobnou intenzitou), a keď sa objaví ešte aspoň jeden chybný stroj, začnú pracovať samostatne, každý obsluhuje jeden stroj (najskôr popíšte systém z hľadiska procesov smrť a narodenie).
Riešenie:
Možné sú nasledujúce stavy systému S:
S 0 – všetky stroje sú funkčné;
Stroj S 1 – 1 sa opravuje, ostatné sú v dobrom prevádzkovom stave;
Stroj S 2 – 2 sa opravuje, zvyšok je v prevádzkyschopnom stave;
Stroj S 3 – 3 sa opravuje, zvyšok je v prevádzkovom stave;
Stroj S 4 – 4 sa opravuje, zvyšok je v dobrom prevádzkovom stave;
S 5 – (1, 2) stroje sa opravujú, ostatné sú v dobrom prevádzkovom stave;
S 6 – (1, 3) stroje sa opravujú, ostatné sú v prevádzkyschopnom stave;
S 7 – (1, 4) stroje sa opravujú, ostatné sú v dobrom prevádzkovom stave;
S 8 – (2, 3) stroje sa opravujú, ostatné sú v dobrom prevádzkovom stave;
S 9 – (2, 4) stroje sa opravujú, ostatné sú v dobrom prevádzkovom stave;
S 10 – (3, 4) stroje sa opravujú, ostatné sú v dobrom prevádzkovom stave;
S 11 – (1, 2, 3) stroje sa opravujú, 4 stroje sú v prevádzke;
S 12 – (1, 2, 4) stroje sa opravujú, 3 stroje sú v prevádzke;
S 13 – (1, 3, 4) stroje sa opravujú, stroj 2 je v prevádzke;
S 14 – (2, 3, 4) stroje sa opravujú, 1 stroj je v prevádzke;
S 15 – všetky stroje sú opravené.
Graf stavu systému...
Tento systém S je príkladom uzavretého systému, keďže každý stroj je potenciálnou požiadavkou, ktorá sa v momente poruchy mení na reálnu. Kým stroj pracuje, je v bloku oneskorenia a od okamihu poruchy až do konca opravy je v samotnom systéme. Každý pracovník je servisným kanálom.
Ak je pracovník zaneprázdnený, nastaví μ-stroje za jednotku času, kapacita systému:
odpoveď:
Priemerný podiel voľného času na každého pracovníka je ≈ 0,09.
Priemerná doba prevádzky stroja ≈ 3,64.
a) Každý pracovník má pridelené dva stroje.
Pravdepodobnosť prestojov pracovníka je určená vzorcom:
Pravdepodobnosť zamestnania pracovníka:
Ak je pracovník zaneprázdnený, nastaví μ-stroje za jednotku času, kapacita systému:
odpoveď:
Priemerný podiel voľného času na každého pracovníka je ≈ 0,62.
Priemerná doba prevádzky stroja ≈ 1,52.
b) Dvaja pracovníci obsluhujú stroj vždy spoločne a s dvojnásobnou intenzitou.
c) Jediný chybný stroj obsluhujú obaja pracovníci naraz (s dvojnásobnou intenzitou), a keď sa objaví ešte aspoň jeden chybný stroj, začnú pracovať samostatne, každý obsluhuje jeden stroj (najskôr popíšte systém z hľadiska procesov smrť a narodenie).
Porovnanie 5 odpovedí:
Najúčinnejším spôsobom organizácie pracovníkov pri strojoch bude počiatočná verzia úlohy.
Príklady najjednoduchších systémov radenia (QS) boli diskutované vyššie. Výraz „prvoci“ neznamená „elementárny“. Matematické modely týchto systémov sú použiteľné a úspešne používané v praktických výpočtoch.
Možnosť aplikácie teórie rozhodovania v systémoch radenia je určená nasledujúcimi faktormi:
1. Počet aplikácií v systéme (ktorý sa považuje za QS) musí byť dosť veľký (masívne).
2. Všetky žiadosti prijaté na vstupe QS musia byť rovnakého typu.
3. Na výpočet pomocou vzorcov potrebujete poznať zákony, ktoré určujú príjem žiadostí a intenzitu ich spracovania. Okrem toho toky objednávok musia byť Poisson.
4. Štruktúra QS, t.j. súbor prichádzajúcich požiadaviek a postupnosť spracovania žiadostí musia byť prísne stanovené.
5. Subjekty je potrebné vylúčiť zo systému alebo ich popísať ako požiadavky s konštantnou intenzitou spracovania.
K vyššie uvedeným obmedzeniam môžeme pridať ešte jedno, ktoré má silný vplyv na rozmer a zložitosť matematického modelu.
6. Počet použitých priorít by mal byť minimálny. Priority žiadostí musia byť konštantné, t.j. nemôžu sa počas spracovania v rámci QS meniť.
V priebehu práce bol dosiahnutý hlavný cieľ - bol preštudovaný hlavný materiál „QS s obmedzenou čakacou dobou“ a „Closed QS“, ktorý stanovil učiteľ akademickej disciplíny. Oboznámili sme sa aj s aplikáciou získaných poznatkov v praxi, t.j. skonsolidoval pokrytý materiál.
1) http://www.5ballov.ru.
2) http://www.studentport.ru.
3) http://vse5ki.ru.
4) http://revolution..
5) Fomin G.P. Matematické metódy a modely v komerčnej činnosti. M: Financie a štatistika, 2001.
6) Gmurman V.E. Teória pravdepodobnosti a matematická štatistika. M: Vyššia škola, 2001.
7) Sovetov B.A., Yakovlev S.A. Modelovanie systémov. M: Vyššia škola, 1985.
8) Lifshits A.L. Štatistické modelovanie QS. M., 1978.
9) Ventzel E.S. Operačný výskum. M: Nauka, 1980.
10) Ventzel E.S., Ovcharov L.A. Teória pravdepodobnosti a jej inžinierske aplikácie. M: Nauka, 1988.
Operácie alebo efektívnosť systému radenia sú nasledovné.Pre QS s poruchami:
Pre SMO s neobmedzeným čakaním absolútna aj relatívna priepustnosť strácajú zmysel, pretože každá prichádzajúca požiadavka bude skôr či neskôr obsluhovaná. Pre takýto QS sú dôležité ukazovatele:
Pre Zmiešaný typ QS používajú sa obe skupiny ukazovateľov: relatívne aj absolútna priepustnosť a charakteristiky očakávania.
V závislosti od účelu operácie zaraďovania do fronty je možné zvoliť ktorýkoľvek z daných indikátorov (alebo súbor indikátorov) ako kritérium účinnosti.
Analytický model QS je súbor rovníc alebo vzorcov, ktoré umožňujú určiť pravdepodobnosti stavov systému počas jeho prevádzky a vypočítať ukazovatele výkonnosti na základe známych charakteristík vstupného toku a servisných kanálov.
Neexistuje žiadny všeobecný analytický model pre ľubovoľný QS. Analytické modely boli vyvinuté pre obmedzený počet špeciálnych prípadov QS. Analytické modely, ktoré viac či menej presne odrážajú skutočné systémy, sú zvyčajne zložité a ťažko vizualizovateľné.
Analytické modelovanie QS je značne uľahčené, ak procesy prebiehajúce v QS sú markovovské (toky požiadaviek sú jednoduché, servisné časy sú distribuované exponenciálne). V tomto prípade možno všetky procesy v QS opísať obyčajnými diferenciálnymi rovnicami a v obmedzujúcom prípade pre stacionárne stavy lineárnymi algebraickými rovnicami a po ich vyriešení určiť vybrané ukazovatele účinnosti.
Pozrime sa na príklady niektorých QS.
2.5.1. Viackanálové QS s poruchami
Príklad 2.5. Traja dopravní inšpektori kontrolujú nákladné listy vodičov kamiónov. Ak je aspoň jeden revízor voľný, prechádzajúci kamión je zastavený. Ak sú všetci inšpektori zaneprázdnení, kamión prejde bez zastavenia. Tok kamiónov je jednoduchý, čas kontroly je náhodný s exponenciálnym rozložením.
Táto situácia môže byť modelovaná trojkanálovým QS s poruchami (bez frontu). Systém je otvorený, s homogénnymi požiadavkami, jednofázový, s absolútne spoľahlivými kanálmi.
Popis stavov:
Všetci inšpektori sú slobodní;
Jeden inšpektor je zaneprázdnený;
Dvaja inšpektori sú zaneprázdnení;
Traja inšpektori sú zaneprázdnení.
Graf stavu systému je znázornený na obr. 2.11.
Ryža. 2.11.
Na grafe: - intenzita prúdu nákladných vozidiel; - intenzita kontrol dokladov jedným dopravným inšpektorom.
Simulácia sa vykonáva na určenie časti vozidiel, ktoré nebudú testované.
Riešenie
Požadovaná časť pravdepodobnosti je pravdepodobnosť zamestnania všetkých troch inšpektorov. Keďže stavový graf predstavuje typickú schému „smrť a reprodukcia“, nájdeme pomocou závislostí (2.2).
Priepustnú kapacitu tohto miesta dopravného inšpektora možno charakterizovať relatívna priepustnosť:
Príklad 2.6. Na prijímanie a spracovanie hlásení z prieskumnej skupiny bola na spravodajskom oddelení spolku určená skupina troch dôstojníkov. Predpokladaná intenzita toku hlásení je 15 hlásení za hodinu. Priemerný čas na spracovanie jedného hlásenia jedným úradníkom je . Každý dôstojník môže prijímať hlásenia od ktorejkoľvek prieskumnej skupiny. Prepustený dôstojník spracuje posledné z prijatých hlásení. Prichádzajúce hlásenia musia byť spracované s pravdepodobnosťou minimálne 95 %.
Zistite, či pridelený tím troch dôstojníkov postačuje na splnenie pridelenej úlohy.
Riešenie
Skupina dôstojníkov funguje ako CMO s poruchami, ktorá pozostáva z troch kanálov.
Tok správ s intenzitou 
možno považovať za najjednoduchšie, keďže ide o súčet niekoľkých prieskumných skupín. Intenzita obsluhy 
. Distribučný zákon je neznámy, ale to nie je dôležité, pretože sa ukázalo, že pre systémy s poruchami môže byť ľubovoľné.
Popis stavov a stavový graf QS bude podobný ako v príklade 2.5.
Keďže stavový graf je schéma „smrť a reprodukcia“, existujú preň hotové výrazy pre obmedzujúce pravdepodobnosti stavu:
Postoj je tzv danej intenzite toku aplikácií. Jeho fyzikálny význam je nasledovný: hodnota predstavuje priemerný počet požiadaviek prichádzajúcich na QS počas priemerného času obsluhy jednej požiadavky.
V príklade 
.
V uvažovanom QS dôjde k zlyhaniu, keď sú všetky tri kanály obsadené, to znamená. potom:
Pretože pravdepodobnosť zlyhania pri spracovaní výkazov je viac ako 34% (), potom je potrebné personálne zvýšiť skupinu. Zdvojnásobme zloženie skupiny, to znamená, že CMO bude mať teraz šesť kanálov, a vypočítajme:
Prichádzajúce hlásenia tak bude môcť s 95% pravdepodobnosťou spracovať len skupina šiestich policajtov.
2.5.2. Viackanálové QS s čakaním
Príklad 2.7. Na úseku prechodu cez rieku sa nachádza 15 podobných prechodových zariadení. Tok techniky prichádzajúcej na priecestie je v priemere 1 jednotka/min, priemerný čas prechodu jednej jednotky techniky je 10 minút (vrátane návratu prejazdového vozidla).
Posúdiť hlavné charakteristiky prechodu, vrátane pravdepodobnosti okamžitého prechodu ihneď po príchode jednotky techniky.
Riešenie
Absolútna priepustnosť, teda všetko, čo sa blíži k priecestiu, je prakticky okamžite prejdené.
Priemerný počet prevádzkovaných prechodových zariadení:
Využitie trajektov a miery prestojov:
Bol vyvinutý aj program na riešenie príkladu. Predpokladá sa, že časové intervaly príchodu zariadenia na križovatku a čas prechodu sú rozdelené podľa exponenciálneho zákona.
Miera využitia križovatky po 50 jazdách je takmer rovnaká: 
.
Maximálna dĺžka frontu je 15 jednotiek, priemerný čas strávený vo fronte je asi 10 minút.
Účel služby QS. Online kalkulačka je určená na výpočet nasledujúcich ukazovateľov jednokanálového QS:- pravdepodobnosť zlyhania kanála, pravdepodobnosť voľného kanála, absolútna priepustnosť;
- relatívna priepustnosť, priemerný servisný čas, priemerný prestoj kanála.
Pokyny. Ak chcete takéto problémy vyriešiť online, vyberte model QS. Uveďte intenzita toku dopytu λ A intenzita obslužného toku μ. Pre jednokanálový QS s obmedzenou dĺžkou frontu môžete zadať dĺžka frontu m a pre jednokanálový QS s neobmedzeným frontom - počet aplikácií vo fronte (na výpočet pravdepodobnosti, že tieto aplikácie budú vo fronte). pozri príklad riešenia. . Výsledné riešenie sa uloží do súboru programu Word.
Klasifikácia jednokanálových čakacích systémov
Príklad č.1. Auto čerpacia stanica má jedenčerpacej stanici. Predpokladá sa, že najjednoduchší prúd áut vchádza do stanice s intenzitou λ=11 vozňov/hod. Čas obsluhy požiadavky je náhodná veličina, ktorá sa riadi exponenciálnym zákonom s parametrom μ=14 vozidiel/hod. Určte priemerný počet áut na stanici.
Príklad č.2. Existuje bod pre vykonávanie preventívnej kontroly strojov s jednou kontrolnou skupinou. Kontrola a identifikácia chýb každého stroja trvá v priemere 0,4 hodiny. Priemerne sa denne dostane na kontrolu 328 áut. Toky požiadaviek a služieb sú najjednoduchšie. Ak vozidlo prichádzajúce na kontrolný bod nenájde voľný ani jeden kanál, ponechá kontrolný bod bez obsluhy. Určte limitné pravdepodobnosti podmienok a charakteristík údržby miesta preventívnej prehliadky.
Riešenie. Tu α = 328/24 ≈ = 13,67, t = 0,4. Tieto údaje je potrebné zadať do kalkulačky.
V praxi sú celkom bežné jednokanálové QS s frontom (lekár obsluhujúci pacientov, procesor vykonávajúci strojové príkazy). Preto je potrebné podrobnejšie zvážiť jednokanálové QS s frontom.
Nech existuje jednokanálový QS s radom, na ktorý nie sú kladené žiadne obmedzenia (ani na dĺžku radu, ani na čakaciu dobu). Tento QS prijíma tok aplikácií s intenzitou l; tok služieb má intenzitu m, ktorá je inverzná k priemernému času obsluhy požiadavky t asi. Je potrebné nájsť konečné pravdepodobnosti stavov QS, ako aj charakteristiky jeho účinnosti:
L SYST– priemerný počet aplikácií v systéme;
W SYST– priemerný čas, počas ktorého žiadosť zostáva v systéme;
L VEĽMI– priemerný počet žiadostí vo fronte;
W VEĽMI– priemerný čas, počas ktorého aplikácia zostáva vo fronte;
P ZAN- pravdepodobnosť, že kanál je obsadený (stupeň zaťaženia kanála).
Pokiaľ ide o absolútnu priepustnosť A a relatívnu Q, nie je potrebné ich počítať: vzhľadom na skutočnosť, že front je neobmedzený, každá požiadavka bude skôr či neskôr obsluhovaná z rovnakého dôvodu.
Riešenie. Stav systému, ako predtým, bude očíslovaný počtom aplikácií v QS:
-S 0 – kanál je voľný;
-S 1 – kanál je zaneprázdnený (vybavuje požiadavku), nie je žiadny front;
-S 2 – kanál je obsadený, jedna požiadavka je vo fronte;
-S k – kanál je obsadený, k-1 aplikácie sú v rade.
Teoreticky je počet stavov neobmedzený (nekonečný). Vzorce pre konečné pravdepodobnosti v schéme smrti a reprodukcie boli odvodené len pre prípad konečného počtu stavov, ale budeme predpokladať, že ich použijeme pre nekonečný počet stavov. Potom bude počet členov vo vzorci nekonečný. Získame výraz pre p o:
Séria vo vzorci (17) je geometrická postupnosť. Vieme, že rad konverguje - je to nekonečne klesajúca progresia s menovateľom r. Keď sa séria rozchádza (čo je nepriamy, aj keď nie striktný dôkaz, že konečné pravdepodobnosti stavov p o, p 1, …, p k,...existujú len vtedy, keď ). potom:
Poďme zistiť priemerný počet žiadostí do CMO L SYST. Náhodná premenná Z - počet aplikácií v systéme - má možné hodnoty 0, 1, 2, ..., k, ... s pravdepodobnosťou p o, p 1, …, p k,... Jeho matematické očakávanie sa rovná:
Použitím Littleovho vzorca (9) zistíme priemerný čas, počas ktorého žiadosť zostáva v systéme:
Poďme zistiť priemerný počet žiadostí vo fronte. Budeme uvažovať takto: počet aplikácií vo fronte sa rovná počtu aplikácií v systéme mínus počet aplikácií v službe. To znamená (podľa pravidla pridávania matematických očakávaní) priemerný počet žiadostí vo fronte L VEĽMI rovná priemernému počtu aplikácií v systéme L SYST mínus priemerný počet aplikácií v službe. Počet žiadostí v rámci služby môže byť buď nula (ak je kanál voľný) alebo jedna (ak je obsadený). Matematické očakávanie takejto náhodnej premennej sa rovná pravdepodobnosti, že kanál je obsadený P ZAN. Je zrejmé, že:
Preto je priemerný počet žiadostí v rámci služby:
Pomocou Littleovho vzorca (9) zistíme priemerný čas, počas ktorého aplikácia zostáva vo fronte.
Načítava sa...
