Systémy radenia. Cvičenie: Modelovanie systémov radenia

ukazovatele výkonnosti QS

• absolútna a relatívna kapacita systému;
• faktory zaťaženia a voľnobehu;
• priemerný čas úplného spustenia systému;
• priemerný čas strávený požiadavkou v systéme.

Ukazovatele charakterizujúce systém z pohľadu spotrebiteľov:

• P obs - pravdepodobnosť servisu aplikácie,
• t syst je čas, počas ktorého požiadavka zostáva v systéme.

Indikátory charakterizujúce systém z hľadiska jeho prevádzkových vlastností:

• λ b je absolútna priepustnosť systému (priemerný počet žiadostí obsluhovaných za jednotku času),
• P obs je relatívna priepustnosť systému,
• k z - faktor zaťaženia systému.

pozri tiež Parametre nákladovej efektívnosti HMO

Úloha . Výpočtové centrum pre kolektívne použitie s tromi počítačmi prijíma objednávky od podnikov na výpočtovú prácu. Ak všetky tri počítače fungujú, potom novo prichádzajúca objednávka nie je akceptovaná a podnik je nútený obrátiť sa na iné počítačové centrum. Priemerný čas práce s jednou zákazkou sú 3 hodiny Intenzita toku aplikácií je 0,25 (1/h). Nájdite limitujúce pravdepodobnosti stavov a ukazovatele výkonnosti výpočtového strediska.
Riešenie. Pri podmienkach n=3, λ=0,25 (1/h), t rev. = 3 (h). Intenzita toku služieb μ=1/t obj. = 1/3 = 0,33. Intenzita zaťaženia počítača podľa vzorca (24) ρ=0,25/0,33=0,75. Nájdite limitujúce pravdepodobnosti stavov:
podľa vzorca (25) p 0 \u003d (1 + 0,75 + 0,75 2 / 2! + 0,75 3 / 3!) -1 \u003d 0,476;
podľa vzorca (26) p1=0,75∙0,476=0,357; p 2 \u003d (0,75 2 / 2!) ∙ 0,476 \u003d 0,134; p 3 \u003d (0,75 3 / 3!) ∙ 0,476 \u003d 0,033 t.j. v stacionárnom režime výpočtového strediska v priemere 47,6 % času nie je ani jedna aplikácia, 35,7 % - jedna aplikácia (jeden počítač je obsadený), 13,4 % - dve aplikácie (dva počítače), 3,3 % času - tri aplikácie (obsadené sú tri počítače).
Pravdepodobnosť zlyhania (keď sú obsadené všetky tri počítače), teda P otk. \u003d p 3 \u003d 0,033.
Podľa vzorca (28) je relatívna priepustnosť centra Q = 1-0,033 = 0,967, t.j. v priemere z každých 100 požiadaviek obslúži výpočtové stredisko 96,7 požiadaviek.
Podľa vzorca (29) je absolútna priepustnosť centra A= 0,25∙0,967 = 0,242, t.j. Priemerne sa za hodinu vybaví 0,242 aplikácií.
Podľa vzorca (30) je priemerný počet zamestnaných počítačov k = 0,242/0,33 = 0,725, t.j. každý z troch počítačov bude obsluhovanými aplikáciami vyťažený v priemere len na 72,5/3 = 24,2 %.
Pri hodnotení efektívnosti výpočtového strediska je potrebné porovnať príjmy z realizácie požiadaviek so stratami z prestojov drahých počítačov (na jednej strane máme vysokú priepustnosť QS a na druhej strane , výrazný výpadok servisných kanálov) a zvoliť kompromisné riešenie.

Úloha . Prístav má jedno kotvisko na vykladanie lodí. Intenzita prietoku ciev je 0,4 (ciev za deň). Priemerná doba vykládky jedného plavidla sú 2 dni. Predpokladá sa, že rad môže mať neobmedzenú dĺžku. Nájdite ukazovatele výkonnosti kotviska, ako aj pravdepodobnosť, že na vyloženie nečakajú viac ako 2 plavidlá.
Riešenie. Máme ρ = λ/μ = μt obj. =0,4∙2 = 0,8. Pretože ρ = 0,8 < 1, potom sa rad na vykládku nemôže zvyšovať donekonečna a sú obmedzené pravdepodobnosti. Poďme ich nájsť.
Pravdepodobnosť, že je kotvisko voľné, podľa (33) p 0 = 1 - 0,8 = 0,2 a pravdepodobnosť, že je obsadené, P zan. = 1-0,2 = 0,8. Podľa vzorca (34) sa pravdepodobnosť, že 1, 2, 3 lode sú v kotvisku (t. j. 0, 1, 2 lode čakajú na vykládku), rovnajú p 1 = 0,8 (1 – 0,8) = 0, 16 ; p 2 \u003d 0,8 2 ∙ (1-0,8) \u003d 0,128; p 3 \u003d 0,8 3 ∙ (1-0,8) \u003d 0,1024.
Pravdepodobnosť, že na vyloženie nečakajú viac ako 2 lode, je

Podľa vzorca (40) priemerný počet lodí čakajúcich na vykládku

a priemerný čas čakania na vykládku podľa vzorca (15.42)
(deň).
Podľa vzorca (36) sa priemerný počet lodí v kotvisku L syst. = 0,8/(1-0,8) = 4 (dni) (alebo jednoduchšie podľa (37) L systém = 3,2+0,8 = 4 (dni), a priemerný čas pobytu lode v kotvisku podľa vzorca ( 41) T syst = 4/0,8 = 5 (dní).
Je zrejmé, že efektivita vykladania lodí je nízka. Na jej zvýšenie je potrebné skrátiť priemerný čas vykládky plavidla t o alebo zvýšiť počet lôžok n.

Úloha . V supermarkete prichádza do uzla sídliska tok zákazníkov s intenzitou λ = 81 osôb. o jednej hodine. Priemerné trvanie služby kontrolóra-pokladníka jedného kupujúceho t asi \u003d 2 min. Definuj:
A. Minimálny počet kontrolórov-pokladníkov p min, pri ktorej nebude rad narastať do nekonečna a zodpovedajúce charakteristiky služby pre n=n min .
b. Optimálny počet n opt. kontrolórov-pokladníkov, pri ktorých je relatívna hodnota nákladov C rel., spojených s nákladmi na údržbu obslužných kanálov a zotrvanie v rade kupujúcich, daná napr. , bude minimálny a porovnajte charakteristiky služby pri n=n min a n=n opt.
V. Pravdepodobnosť, že v rade nebudú viac ako traja kupujúci.
Riešenie.
A. Podľa podmienok l = 81 (1/h) = 81/60 = 1,35 (1/min). Podľa vzorca (24) r = l / m = lt rev = 1,35 × 2 = 2,7. Pod podmienkou r/n nebude rad rásť donekonečna< 1, т.е. при n >r = 2,7. teda minimálne množstvo kontrolóri-pokladníci n min = 3.
Poďme nájsť charakteristiky služby QS pre P= 3.
Pravdepodobnosť, že v uzle vyrovnania nie sú žiadni kupci podľa vzorca (45) p 0 = (1+2,7+2,7 2 /2!+2,7 3 /3!+2,7 4 /3!(3 -2,7)) - 1 = 0,025, t.j. v priemere 2,5 % časoví kontrolóri-pokladníci budú nečinní.
Pravdepodobnosť, že vo výpočtovom uzle bude rad podľa (48) P och. = (2,7 4 /3! (3-2,7)) 0,025 = 0,735
Priemerný počet kupujúcich v rade o (50) L b. \u003d (2,7 4 / 3 3! (1-2,7 / 3) 2) 0,025 \u003d 7,35.
Priemerná doba čakania v rade podľa (42) T b. = 7,35/1,35 = 5,44 (min).
Priemerný počet kupujúcich vo výpočtovom uzle podľa (51) L syst. = 7,35 + 2,7 = 10,05.
Priemerný čas strávený kupujúcimi vo výpočtovom uzle podľa (41) T syst. = 10,05/1,35 = 7,44 (min).
stôl 1

Charakteristika služby	Počet kontrolórov-pokladníkov
	3	4	5	6	7
Pravdepodobnosť nečinných pokladníkov p 0	0,025	0,057	0,065	0,067	0,067
Priemerný počet kupujúcich v rade T och.	5,44	0,60	0,15	0,03	0,01
Relatívna hodnota nákladov С rel.	18,54	4,77	4,14	4,53	5,22

Priemerný počet kontrolórov-pokladníkov zapojených do služieb zákazníkom podľa (49) k = 2,7.
Pomer (podiel) kontrolórov pokladne zamestnaných pri obsluhe
= p/n = 2,7/3 = 0,9.
Absolútna priepustnosť výpočtového uzla A = 1,35 (1/min), alebo 81 (1/h), t.j. 81 kupujúcich za hodinu.
Analýza charakteristík služieb poukazuje na výrazné preťaženie zúčtovacieho uzla v prítomnosti troch kontrolórov-pokladníkov.
b. Relatívna cena pre n = 3
C rel. = = 3/1,35 + 3∙5,44 = 18,54.
Vypočítajte relatívnu výšku nákladov pre ostatné hodnoty P(Stôl 1).
Ako je možné vidieť z tabuľky. 2, minimálne náklady získané pri n = n opt. = 5 kontrolórov-pokladníkov.
Stanovme charakteristiky služby výpočtového uzla pre n = n opt. =5. Dostávame P och. = 0,091; L = 0,198; T och. = 0,146 (min); L systém = 2,90; T snst. = 2,15 (min); k = 2,7; k 3 \u003d 0,54.
Ako vidíte, pri n = 5 v porovnaní s n = 3 je pravdepodobnosť frontu P och. , dĺžka frontu L b. a priemerný čas strávený vo fronte T och. a podľa toho aj priemerný počet kupujúcich L systém. a priemerný čas strávený vo výpočtovom uzle T sist., ako aj podiel kontrolórov zamestnaných pri obsluhe k 3. Ale priemerný počet kontrolórov-pokladníkov zamestnaných pri obsluhe k a absolútna priepustnosť výpočtového uzla A sa prirodzene nezhodovali. zmeniť.
V. Pravdepodobnosť, že v rade nebudú viac ako 3 zákazníci, je definovaná ako
= 1-P och. + p 5+1 + p 5+2 + p 5+3 , kde každý člen sa nachádza podľa vzorcov (45) – (48). Dostaneme pre n=5:

(Všimnite si, že v prípade n=3 kontrolórov-pokladníkov je rovnaká pravdepodobnosť podstatne menšia: P(r ≤ 3) =0,464).

Aplikácia rôznych matematické metódy k formalizácii. Dôraz na zložitý systém – nepredvídateľný. Nosič neistota je človek.

Typickým príkladom stochastických (náhodných, pravdepodobnostných) problémov sú modely systémov radenie.

SMO sú všadeprítomné. Ide o telefónne siete, čerpacie stanice, spotrebiteľské služby, pokladne, obchodné akcie a pod.

Z pozície modelovania procesu radenia vznikajú situácie, kedy sa tvoria rady požiadaviek (požiadaviek) na obsluhu nasledovne. Po vstupe do systému poskytovania sa požiadavka zaradí do radu iných (predtým prijatých) požiadaviek. Servisný kanál vyberie požiadavku z tých, ktoré sú vo fronte, aby ho mohol začať obsluhovať. Po dokončení procedúry na obsluhu ďalšej požiadavky začne obslužný kanál obsluhovať ďalšiu požiadavku, ak je v bloku čakania nejaká. Cyklus fungovania QS tohto druhu sa mnohokrát opakuje počas celej doby prevádzky obslužného systému. Predpokladá sa, že prechod systému na obsluhu ďalšej požiadavky po dokončení obsluhy predchádzajúcej požiadavky nastáva okamžite, v náhodných časoch.

Príklady SMO sú:

miesta na údržbu automobilov;

stĺpiky na opravu áut;

audítorské firmy atď.

Zakladateľom teórie radenia, najmä teórie radov, je slávny dánsky vedec A.K. Erlang (1878-1929), ktorý študoval procesy obsluhy na telefónnych ústredniach.

Systémy, v ktorých prebiehajú servisné procesy, sa nazývajú queuing systems (QS).

Ak chcete opísať systém radenia, musíte zadať:

- vstupný tok aplikácií;

- služobná disciplína;

- servisný čas

- počet servisných kanálov.

vstupný prúd požiadavky (aplikácie) je popísaná identifikáciou oboch pravdepodobnostných distribučný zákon momenty prijatia požiadaviek do systému, a počet požiadaviek v každom vstupe.

Na otázku služobné disciplíny(DO) je potrebné popísať pravidlá pre požiadavky na radenie a ich obsluhu v systéme. Dĺžka fronty môže byť obmedzená aj neobmedzená. V prípade obmedzení dĺžky frontu sa žiadosť prijatá na vstupe do QS zamietne. Najčastejšie používané DO sú definované nasledujúcimi pravidlami:

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

prišiel posledný - slúžil ako prvý; (box na tenisové loptičky, stohovanie v technike)

náhodný výber aplikácií;

výber žiadostí podľa prioritného kritéria.

Servisný čas aplikácie v QS je náhodná premenná. Najbežnejším distribučným zákonom je exponenciálny zákon.  - rýchlosť obsluhy. =počet servisných požiadaviek/jednotiek. čas.

Servisné kanály, môžu byť umiestnené paralelne alebo sériovo. Pri sekvenčnom usporiadaní kanálov je každá aplikácia obsluhovaná na všetkých kanáloch postupne. Pri paralelnom usporiadaní kanálov sa služba vykonáva na všetkých kanáloch súčasne, keď sa uvoľnia.

Zovšeobecnená štruktúra QS je znázornená na obr.

Predmet teória radenia je stanoviť vzťah medzi faktormi, ktoré určujú funkčnosť QS, a efektívnosťou jeho fungovania.

Problémy s dizajnom QS.

Úlohy určovania charakteristík štruktúry QS zahŕňajú problém výberu počtu obslužných kanálov (základné prvky (F i)), problém určenia spôsobu spájania kanálov (súbor spojovacích prvkov (Hj)), ako aj problém určovania priepustnosti kanálov.

1). Výber štruktúry. Ak kanály fungujú paralelne, potom sa problém výberu Str redukuje na určenie počtu kanálov v servisnej časti na základe podmienky zabezpečenia prevádzkyschopnosti QS. (Pokiaľ sa front nekonečne nezväčšuje).

Upozorňujeme, že pri určovaní počtu systémových kanálov v prípade ich paralelného usporiadania je potrebné dodržať zdravotný stav systému. Označte:  - priemerný počet žiadostí prijatých za jednotku času, t.j. intenzita vstupného toku;  - priemerný počet žiadostí uspokojených za jednotku času, t.j. intenzita služby; S - počet servisných kanálov. Potom sa napíše podmienka prevádzkyschopnosti QS

alebo
. Splnenie tejto podmienky nám umožňuje vypočítať spodnú hranicu počtu kanálov.

Ak
, systém nemôže spracovať front. Fronta narastá donekonečna.

2). Je potrebné určiť kritérium efektívnosti fungovania QS, berúc do úvahy náklady na časové straty tak na strane aplikácií, ako aj na strane servisnej časti.

Za ukazovatele efektívnosti fungovania QS sa považujú tieto tri hlavné skupiny ukazovateľov:

1. Ukazovatele efektívnosti využívania QS.

Absolútna priepustnosť QS je priemerný počet aplikácií, ktoré QS dokáže obslúžiť za jednotku času.

Relatívna priepustnosť QS je pomer priemerného počtu aplikácií obsluhovaných QS za jednotku času k priemernému počtu žiadostí prijatých počas tohto času.

Priemerná dĺžka doby zamestnania SMO.

Miera využitia QS je priemerný podiel času, počas ktorého je QS zaneprázdnený servisom aplikácií.

2. Ukazovatele kvality aplikácií služieb.

Priemerná doba čakania na žiadosť vo fronte.

Priemerný čas zotrvania žiadosti v SOT.

Pravdepodobnosť odmietnutia služby žiadosti bez čakania.

Pravdepodobnosť, že prichádzajúca požiadavka bude okamžite prijatá na službu.

Zákon o rozdelení čakacej doby na žiadosť vo fronte.

Zákon o rozdelení času stráveného aplikáciou v QS.

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

Priemerný počet žiadostí v SOT.

3. Ukazovatele efektívnosti fungovania dvojice „QS – spotrebiteľ“.

Pri výbere kritéria efektívnosti fungovania QS je potrebné brať do úvahy duálny prístup pri posudzovaní systémov radenia. Napríklad na prácu supermarketu, podobne ako CMO, sa možno pozerať z opačných strán. Na jednej strane, tradične akceptovaný, kupujúci, čakajúci v rade pri pokladni, je požiadavka na službu a pokladník je servisný kanál. Na druhej strane pokladník, ktorý čaká na zákazníkov, možno považovať za požiadavku na službu a zákazník je obslužné zariadenie schopné požiadavku uspokojiť, t.j. choďte k pokladni a zastavte nútenú odstávku pokladníka. (tradične - kupci > ako pokladníci, ak pokladníci > ako kupci, čakajú na kupcov).

S
S ohľadom na to je účelné minimalizovať obe časti QS súčasne.

Použitie takéhoto duálneho prístupu znamená potrebu zohľadniť pri tvorbe kritéria efektívnosti nielen vyššie uvedené ukazovatele samostatne, ale aj viacero ukazovateľov súčasne, odrážajúcich záujmy obsluhujúceho aj obsluhovaného subsystému QS. Napríklad sa ukazuje, že najviac dôležité kritérium efektívnosť pri zaraďovaní úloh do frontu je celkový čas strávený klientom vo fronte na jednej strane a prestoje servisných kanálov na strane druhej.

Klasifikácia systémov radenia

1. Podľa charakteru služby sa rozlišujú tieto typy QS:

1.1. Čakacie systémy alebo systémy radenia. Požiadavky, ktoré vstúpili do systému a nie sú okamžite prijaté do služby, sa hromadia vo fronte. Ak sú kanály voľné, požiadavka je doručená. Ak sú všetky kanály v čase prijatia požiadavky obsadené, ďalšia požiadavka bude obsluhovaná po dokončení obsluhy predchádzajúcej. Takýto systém sa nazýva plne prístupný (s neobmedzeným frontom).

Existujú systémy s autonómnou službou, keď služba začína v určitých časových bodoch;

Systémy s obmedzenou frontou. (oprava garáže)

Systémy s poruchami. Všetky žiadosti, ktoré prišli v čase vybavovania žiadosti, sú zamietnuté. (GTS)

Systémy so skupinovým vstupným tokom a skupinovou službou. V takýchto systémoch aplikácie prichádzajú v skupinách v časových bodoch a servis sa tiež vyskytuje v skupinách.

2. Podľa počtu obslužných kanálov sú QS rozdelené do nasledujúcich skupín.

Jednokanálový QS.

Viackanálové QS. Doručovanie ďalšej žiadosti môže začať pred ukončením doručenia predchádzajúcej žiadosti. Každý kanál funguje ako nezávislý server.

3. Podľa rozsahu obsluhovaných objektov sa rozlišujú dva typy.

Uzavreté QS. Systém radenia s uzavretým okruhom je systém radenia, v ktorom sa obsluhovaní zákazníci môžu vrátiť do systému a byť znova obsluhovaní. Príkladom uzavretého SMO sú opravovne, sporiteľne.

Otvorte CMO.

4. Podľa počtu servisných stupňov sa rozlišujú jednofázové a viacfázové QS.

jednofázový SMO je homogénne systémy ktoré vykonávajú rovnakú údržbu.

Polyfáza QS sú systémy, v ktorých sú servisné kanály usporiadané v sérii a vykonávajú rôzne servisné operácie. Stanice sú príkladom viacfázového QS Údržba autá.

Vyššie uvedená klasifikácia QS je podmienená. V praxi CMO najčastejšie vystupujú ako zmiešané systémy. Napríklad požiadavky čakajú na spustenie služby do určitého momentu, po ktorom systém začne pracovať ako systém s poruchami.

V praxi ľudskej činnosti je veľké miesto obsadené procesmi radenia, ktoré sa vyskytujú v systémoch určených na to opakovane použiteľné pri riešení podobných 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 veľmi hromadí 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ý.

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, spájajúci 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 očakávaním sa delí na odlišné typy v závislosti od toho, ako je rad usporiadaný: s obmedzenou alebo neobmedzenou dĺžkou frontu, s limitovaný čas očakávania 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útorná organizácia služby v systéme sú:

• 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.

V operačnom výskume sa často stretávame so systémami určenými na opakované použitie pri riešení rovnakého typu problémov. Výsledné procesy sú tzv servisné procesy a systémy systémy radenia (QS). Príkladmi takýchto systémov sú telefónne systémy, opravovne, počítačové systémy, pokladne, obchody, kaderníctva a podobne.

Každý QS pozostáva z určitého počtu obslužných jednotiek (prístrojov, prístrojov, výhybiek, staníc), ktoré budeme nazývať servisné 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ý.

Žiadosti zvyčajne prichádzajú na CMO nie pravidelne, ale náhodne, pričom tvoria tzv náhodný tok aplikácií (požiadavky). Servisné požiadavky vo všeobecnosti tiež pokračujú nejaký náhodný čas. Náhodná povaha toku aplikácií a servisného času vedie k tomu, že QS sa načítava nerovnomerne: v niektorých časových úsekoch sa hromadí veľmi veľké množstvo aplikácií (buď sa zaraďujú do fronty, alebo nechávajú QS neobslúžené), zatiaľ čo v iných periódy, QS pracuje s nedostatočným zaťažením alebo je nečinný.

Predmet 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 tok aplikácií.

Ako ukazovatele výkonnosti QS použité: priemerný počet aplikácií obsluhovaných za jednotku času; priemerný počet žiadostí vo fronte; priemerná doba čakania na službu; pravdepodobnosť odmietnutia služby bez čakania; pravdepodobnosť, že počet aplikácií vo fronte prekročí určitú hodnotu atď.

QS sú rozdelené do dvoch hlavných typov (tried): CMO s poruchami A QS s čakaním (front). 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.

QS s čakaním sa delia na rôzne typy podľa toho, ako je rad organizovaný: s obmedzenou alebo neobmedzenou dĺžkou frontu, s obmedzenou dobou čakania atď.

Na klasifikáciu QS dôležitosti Má služobná disciplína, ktorý určuje poradie výberu požiadaviek spomedzi prijatých a poradie ich distribúcie medzi voľné kanály. Na tomto základe môže byť obsluha aplikácie organizovaná podľa princípu „kto prv príde, ten prv melie“, „kto prv príde, ten prv melie“ (toto poradie je možné použiť napr. pri vyskladnení položiek zo skladu na údržbu, pretože posledné z nich sú často dostupnejšie) alebo prioritná služba (kde sú najdôležitejšie požiadavky doručené ako prvé). Priorita môže byť buď absolútna, keď dôležitejšia aplikácia „vytlačí“ normálnu aplikáciu zo služby (napr. núdzový plánovaná práca opravárenských tímov je prerušená až do odstránenia havárie) a relatívna, keď dôležitejšia aplikácia dostane len to „najlepšie“ miesto v poradí.

Koncept Markovovho stochastického procesu

Pracovný postup SMO je náhodný proces.

Pod náhodný (pravdepodobnostný alebo stochastický) proces označuje proces zmeny stavu systému v čase v súlade s pravdepodobnostnými zákonmi.

Proces sa nazýva proces diskrétneho stavu, ak je možné vopred vypísať jeho možné stavy a prechod systému zo stavu do stavu nastane okamžite (skok). Proces sa nazýva nepretržitý časový proces, ak momenty možných prechodov systému zo stavu do stavu nie sú vopred pevne dané, ale sú náhodné.

Proces operácie QS je náhodný proces s diskrétnymi stavmi a nepretržitým časom. To znamená, že stav QS sa náhle zmení v náhodných okamihoch výskytu niektorých udalostí (napríklad príchod novej požiadavky, ukončenie služby atď.).

Matematická analýza práce QS je značne zjednodušená, ak procesom tejto práce je Markov. Náhodný proces sa nazýva Markovian alebo náhodný proces bez následkov, ak v ktorýkoľvek moment pravdepodobnostné charakteristiky procesu v budúcnosti závisia len od jeho momentálneho stavu a nezávisia od toho, kedy a ako sa systém do tohto stavu dostal.

Príklad Markovovho procesu: systém je počítadlo v taxíku. Momentálny stav systému je charakterizovaný počtom kilometrov (desatín kilometrov), ktoré vozidlo do daného momentu najazdilo. Nech momentálne počítadlo ukazuje . Pravdepodobnosť, že glukomer v súčasnosti ukáže jeden alebo iný počet kilometrov (presnejšie zodpovedajúci počet rubľov), závisí od , ale nezávisí od času, v ktorom sa hodnoty merača doteraz zmenili.

Mnohé procesy možno považovať za približne markovovské. Napríklad proces hrania šachu; systém – skupina šachové figúrky. Stav systému je charakterizovaný počtom súperových figúrok, ktoré momentálne zostávajú na hracej ploche. Pravdepodobnosť, že materiálna výhoda bude momentálne na strane jedného zo súperov, závisí predovšetkým od aktuálneho stavu systému a nie od toho, kedy a v akom poradí figúrky z hracej plochy zmizli až do momentu.

V niektorých prípadoch možno prehistóriu uvažovaných procesov jednoducho zanedbať a na ich štúdium použiť Markovove modely.

Pri analýze náhodných procesov s diskrétnymi stavmi je vhodné použiť geometrickú schému - tzv stavový graf. Zvyčajne sú stavy systému reprezentované obdĺžnikmi (kruhmi) a možné prechody zo stavu do stavu sú znázornené šípkami (orientovanými oblúkmi) spájajúcimi stavy.

Príklad 1 Vytvorte graf stavov nasledujúceho náhodného procesu: zariadenie pozostáva z dvoch uzlov, z ktorých každý môže zlyhať v náhodnom časovom okamihu, po ktorom okamžite začnete opravovať uzol, pričom budete pokračovať dovtedy neznámy náhodný čas.

Riešenie. Možné stavy systému: - oba uzly sú funkčné; - prvý uzol sa opravuje, druhý je prevádzkyschopný; - druhý uzol sa opravuje, prvý funguje; Obe jednotky sú v oprave. Graf systému je znázornený na obr. 1.

Šípka smerujúca napríklad z do znamená prechod systému v momente poruchy prvého uzla, z na - prechod v momente dokončenia opravy tohto uzla.

Na grafe nie sú žiadne šípky od do a z do. Vysvetľuje sa to tým, že sa predpokladá, že poruchy uzlov sú od seba nezávislé a napríklad pravdepodobnosť, že dva uzly zlyhajú súčasne (prechod z do ) alebo súčasné ukončenie opráv dvoch uzlov (prechod z do ), možno zanedbať. .

Pre matematický popis Markovovho náhodného procesu s diskrétnymi stavmi a spojitým časom, plynúcim v QS, sa zoznámime s jedným z dôležitých konceptov teórie pravdepodobnosti – konceptom prúdu udalostí.

Streamy udalostí

Pod tok udalostí označuje sled homogénnych udalostí, ktoré nasledujú za sebou v určitom náhodnom čase (napríklad tok hovorov v telefónnej ústredni, tok porúch počítača, tok zákazníkov atď.).

Charakteristický je prietok intenzita- frekvencia výskytu udalostí alebo priemerný počet udalostí vstupujúcich do QS za jednotku času.

Prúd udalostí je tzv pravidelné, ak udalosti nasledujú za sebou v určitých rovnakých časových intervaloch. Napríklad tok výrobkov na montážnej linke (pri konštantnej rýchlosti) je pravidelný.

Prúd udalostí je tzv stacionárne, ak jeho pravdepodobnostné charakteristiky nezávisia od času. Najmä intenzita stacionárneho prúdenia je konštantná hodnota: . Napríklad tok áut na mestskej triede nie je počas dňa stacionárny, ale tento tok možno považovať za stacionárny počas dňa, povedzme, počas špičiek. Upozorňujeme na skutočnosť, že v druhom prípade sa skutočný počet prechádzajúcich áut za jednotku času (napríklad každú minútu) môže od seba výrazne líšiť, ale ich priemerný počet bude konštantný a nebude závislý od času.

Prúd udalostí je tzv tok bez následných efektov, ak pre ktorékoľvek 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é. Napríklad prúd cestujúcich vstupujúcich do metra nemá takmer žiadne následky. A, povedzme, tok zákazníkov, ktorí odchádzajú z pultu so svojimi nákupmi, už má svoj následný efekt (už len preto, že časový interval medzi jednotlivými zákazníkmi nemôže byť kratší ako minimálny čas obsluhy každého z nich).

Prúd udalostí je tzv obyčajný, ak je pravdepodobnosť zasiahnutia malého (elementárneho) časového intervalu dvoch alebo viacerých udalostí zanedbateľne malá v porovnaní s pravdepodobnosťou zasiahnutia jednej udalosti. Inými slovami, prúd udalostí je obyčajný, ak sa v ňom udalosti objavujú jedna po druhej, a nie v skupinách. Napríklad prúd vlakov prichádzajúcich k stanici je obyčajný, ale prúd vagónov nie je obyčajný.

Tok udalostí sa nazýva najjednoduchší (resp stacionárny Poisson) ak je súčasne stacionárny, obyčajný a nemá žiadne následné účinky. Názov „najjednoduchší“ sa vysvetľuje tým, že QS s najjednoduchšími tokmi má najjednoduchší matematický popis. Všimnite si, že bežný tok nie je „najjednoduchší“ tok, pretože má následný efekt: momenty výskytu udalostí v takomto toku sú pevne stanovené.

Najjednoduchší tok ako limitujúci vzniká v teórii náhodných procesov rovnako prirodzene ako v teórii pravdepodobnosti normálne rozdelenie sa získa ako limit pre súčet náhodných premenných: keď postačí superponovanie (superpozícia). Vysoké číslo nezávislé, stacionárne a bežné toky (v intenzitách sú navzájom porovnateľné, získa sa tok blízky najjednoduchšiemu s intenzitou rovnajúcou sa súčtu intenzít prichádzajúcich tokov, t. j. uvažujme najjednoduchší tok udalostí v čase os (obr. 1) ako neobmedzenú postupnosť náhodných bodov.

Dá sa ukázať, že pre najjednoduchší tok je počet m udalostí (bodov) spadajúcich do ľubovoľného časového intervalu rozdelený na Poissonov zákon

pre ktoré očakávaná hodnota náhodná premenná rovná jeho rozptylu: .

Najmä pravdepodobnosť, že v danom čase nenastane žiadna udalosť, sa rovná

Nájdite rozdelenie časového intervalu medzi ľubovoľné dve susediace udalosti najjednoduchšieho toku.

V súlade s (2) je pravdepodobnosť, že sa v časovom intervale neobjaví žiadna z nasledujúcich udalostí, rovná

a pravdepodobnosť opačnej udalosti, t.j. distribučná funkcia náhodnej premennej, je

Hustota pravdepodobnosti náhodnej premennej je deriváciou jej distribučnej funkcie (obr. 3), t.j.

Volá sa rozdelenie dané hustotou pravdepodobnosti (5) alebo distribučnou funkciou (4). odhaľujúce(alebo exponenciálny). Časový interval medzi dvoma susednými ľubovoľnými udalosťami má teda exponenciálne rozdelenie, pre ktoré sa matematické očakávanie rovná priemeru smerodajná odchýlka náhodná premenná

a naopak podľa veľkosti intenzity prúdenia .

Najdôležitejšia vlastnosť exponenciálne rozdelenie (vlastné iba exponenciálnemu rozdeleniu) je nasledovné: ak časový interval rozdelený podľa exponenciálneho zákona už nejaký čas trvá, potom to nemá vplyv na zákon rozdelenia zostávajúcej časti intervalu: bude to rovnaký ako distribučný zákon celého intervalu.

Inými slovami, pre časový interval medzi dvoma po sebe nasledujúcimi susednými udalosťami toku, ktorý má exponenciálne rozdelenie, akákoľvek informácia o tom, ako dlho tento interval uplynul, neovplyvní rozdelenie zvyšku. Táto vlastnosť exponenciálneho zákona je v podstate ďalšou formuláciou pre „nedostatok následného účinku“ – hlavnej vlastnosti najjednoduchšieho toku.

Pre najjednoduchší tok s intenzitou, pravdepodobnosť zasiahnutia

(Všimnite si, že tento približný vzorec získaný nahradením funkcie iba prvými dvoma členmi jej rozšírenia do radu v mocninách , je tým presnejší, čím menší ).

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

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

Je jasné, že cieľom systémová analýza v tomto prípade je určiť nejaký pomer medzi stratou príjmu v dôsledku frontoch a straty v dôsledku iba ja staníc.

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

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

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

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

Hlavnou črtou problémov tejto triedy je explicitná závislosť výsledkov analýzy a prijatých odporúčaní na dvoch vonkajšie faktory: frekvencia prijímania a zložitosť objednávok (a teda čas ich realizácie).

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

Ako Vlastnosti QS zvážiť:

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

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

3.1 Modely systémov radenia.

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

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

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

c – konfigurácia servisného mechanizmu;

d – disciplína v rade;

e – čakací blok;

f je kapacita zdroja.

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

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

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

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

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

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

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

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

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

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

Dĺžka frontu Možno

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

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

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

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

3.2 Vstupný tok požiadaviek.

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

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

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

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

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

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

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

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

Zvážte PRÍKLAD .

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

Riešenie.

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

^

3.3 Stav systému. Matica a graf prechodov.

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

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

E 1 – jeden kanál je obsadený;

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

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

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

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

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

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

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

Obrázok 3.1 - graf prechodu

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

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

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

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

3.4 Jednokanálový QS.

3.4.1 Jednokanálový QS s poruchami.

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

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

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

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

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

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

Tak dostaneme prechodovú maticu:

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

Pravdepodobnosť výpadku a zlyhania systému.

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

Asymptota grafu je priamka
.

Samozrejme, od istého bodu t,

1

Obrázok 3.2

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

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

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

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

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

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

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

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

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

Priemerné charakteristiky systému.

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

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

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

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

je priemerná dĺžka frontu.

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

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

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

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

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

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

Pravdepodobnosť výpadku systému je
,

a pravdepodobnosť zlyhania systému je
.

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

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

3.5 Viackanálové QS.

3.5.1 Viackanálové QS s poruchami.

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

, k = 0, 1, …

nákladová funkcia.

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

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

Obrázok 3.3

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

PRÍKLAD .

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

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

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

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

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

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

3.5.2 Viackanálové QS s radom.

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

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

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

PRÍKLAD .

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

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

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

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

3.6 Otázky na sebaovládanie

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

3.7 Cvičenia na samostatnú prácu

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