Matematické modely najjednoduchších systémov radenia. Funkcie p0(t) a p1(t) určujú prechodový proces v jednokanálovom QS a popisujú proces, pri ktorom sa QS exponenciálne približuje k medznému stavu s charakteristickou časovou konštantou d

23. októbra 2013 o 14:22 hod

Squeak: Modeling Queuing Systems

• programovanie,
• OOP,
• Paralelné programovanie

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

Pár slov o Squeakovi

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

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

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

Systémy radenia

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

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

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

Trochu matematiky

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

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

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

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

trieda Rand

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

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

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

Program na spracovanie žiadostí

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

Squeak Code

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Stacionárne volal tok, pre ktoré sa matematické očakávanie počtu nárokov vstupujúcich do systému za jednotku času (označuje sa λ) v čase nemení. Pravdepodobnosť, že v danom časovom intervale Δt vstúpi do systému určitý počet zákazníkov, teda závisí od jeho hodnoty a nezávisí od jeho pôvodu na časovej osi.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Kde

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

Priemerné trvanie služby jednej požiadavky;

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

n je počet servisných zariadení;

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

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

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

Kde

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

teda,

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

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

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

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

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

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

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

11. Pomer prestojov servisných vozidiel:

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

V mnohých oblastiach ekonomiky, financií, výroby a každodenného života hrajú dôležitú úlohu systémy, ktoré realizujú opakované vykonávanie úloh rovnakého typu. Takéto systémy sú tzv systémy radenia ( CMO ). Príkladmi SMO sú: banky rôznych typov, poisťovne, daňové inšpektoráty, audítorské služby, rôzne komunikačné systémy, nakladacie a vykladacie komplexy, čerpacie stanice, rôzne podniky a organizácie v sektore služieb.

3.1.1 Všeobecné informácie o systémoch radenia

Každý QS je navrhnutý tak, aby slúžil (vykonával) určitý tok aplikácií (požiadaviek), ktoré prichádzajú na vstup systému väčšinou nie pravidelne, ale v náhodných časoch. Služba aplikácií tiež netrvá konštantný, vopred určený čas, ale náhodne, čo závisí od mnohých náhodných, niekedy nám neznámych príčin. Po obsluhe požiadavky sa kanál uvoľní a je pripravený prijať ďalšiu požiadavku. Náhodný charakter toku aplikácií a času ich obsluhy vedie k nerovnomernému zaťaženiu QS. V určitých časových intervaloch sa môžu na vstupe QS hromadiť požiadavky, čo vedie k preťaženiu QS, zatiaľ čo v niektorých iných časových intervaloch s voľnými kanálmi (servisnými zariadeniami) nebudú na vstupe QS žiadne požiadavky, čo vedie k nedostatočnému zaťaženiu QS, t.j. na nečinnosť svojich kanálov. Aplikácie, ktoré sa nahromadia na vstupe QS, sa buď „dostanú“ do frontu, alebo z nejakého dôvodu nemožnosť ďalšieho zotrvania v rade, nechajú QS neobslúžený.

Obrázok 3.1 ukazuje diagram QS.

Hlavné prvky (funkcie) systémov radenia sú:

Servisný uzol (blok),

aplikačný tok,

Frontačakanie na obsluhu (disciplína v rade).

Servisný blok navrhnuté tak, aby vykonávali činnosti v súlade s požiadavkami vstupného systému aplikácie.

Ryža. 3.1 Schéma systému radenia

Druhou zložkou čakacích systémov je vstup aplikačný tok. Aplikácie vstupujú do systému náhodne. Zvyčajne sa predpokladá, že vstupný tok sa riadi určitým zákonom pravdepodobnosti počas trvania intervalov medzi dvoma po sebe prichádzajúcimi požiadavkami a distribučný zákon sa považuje za nezmenený po určitú dostatočne dlhú dobu. Zdroj aplikácií je neobmedzený.

Tretia zložka je frontová disciplína. Táto charakteristika popisuje poradie obsluhy požiadaviek prichádzajúcich na vstup systému. Keďže obslužný blok má zvyčajne obmedzenú kapacitu a požiadavky prichádzajú nepravidelne, periodicky sa vytvára rad požiadaviek čakajúcich na obsluhu a niekedy obsluhujúci systém nečinne čaká na požiadavky.

Hlavnou črtou procesov zaraďovania do frontu je náhodnosť. V tomto prípade existujú dve interagujúce strany: obsluhované a obsluhované. Náhodné správanie aspoň jednej zo strán vedie k náhodnému charakteru toku servisného procesu ako celku. Zdrojmi náhodnosti v interakcii týchto dvoch strán sú náhodné udalosti dvoch typov.

1. Vzhľad aplikácie (požiadavka) na službu. Dôvodom náhodnosti tejto udalosti je často masívny charakter potreby služby.

2. Koniec vybavovania ďalšej požiadavky. Dôvody náhodnosti tejto udalosti sú tak náhodnosť spustenia služby, ako aj náhodné trvanie samotnej služby.

Tieto náhodné udalosti tvoria systém dvoch tokov v QS: vstupný tok servisných požiadaviek a výstupný tok obsluhovaných požiadaviek.

Výsledkom interakcie týchto tokov náhodných udalostí je momentálne počet aplikácií v QS, ktorý sa zvyčajne nazýva stav systému.

Každý QS, v závislosti od jeho parametrov charakteru toku aplikácií, počtu servisných kanálov a ich výkonu, na pravidlách organizácie práce, má určitú efektivitu fungovania (kapacitu), ktorá mu umožňuje úspešne zvládnuť tok aplikácií.

Špeciálna oblasť aplikovanej matematiky teória hmotnostislužba (TMO)– zaoberá sa analýzou procesov v systémoch radenia. Predmetom štúdia teórie radenia je QS.

Účelom teórie radenia je vypracovať odporúčania pre racionálnu konštrukciu QS, racionálnu organizáciu ich práce a reguláciu toku aplikácií pre zabezpečenie vysokej účinnosti QS. Na dosiahnutie tohto cieľa sú stanovené úlohy teórie radenia, ktoré spočívajú v stanovení závislostí efektívnosti fungovania QS od jeho organizácie.

Úlohy teórie radenia sú optimalizačného charakteru a v konečnom dôsledku sú zamerané na určenie takého variantu systému, ktorý zabezpečí minimálne celkové náklady z čakania na obsluhu, straty času a zdrojov na obsluhu a z nečinnosti obslužnej jednotky. . Znalosť týchto charakteristík poskytuje manažérovi informácie na vytvorenie priameho vplyvu na tieto charakteristiky na riadenie efektívnosti procesov zaraďovania do frontu.

Ako charakteristiky efektívnosti fungovania QS sa zvyčajne vyberajú tieto tri hlavné skupiny (zvyčajne priemerných) ukazovateľov:

Ukazovatele účinnosti používania QS:

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

Relatívna priepustnosť QS je pomer priemerného počtu žiadostí obsluhovaných QS za jednotku času k priemernému počtu žiadostí prijatých v rovnakom čase.

Priemerná dĺžka doby zamestnania SMO.

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

Indikátory kvality služieb aplikácie:

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 distribúcie času, počas ktorého aplikácia zostáva v rade.

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

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

Priemerný počet aplikácií v QS atď.

Výkonnostné ukazovatele dvojice „QS – spotrebiteľ“, kde „spotrebiteľ“ znamená celú sadu aplikácií alebo niektoré z nich

prevádzka alebo účinnosť systému radenia sú nasledovné.

Pre CMO s poruchami:

Pre CMO s neobmedzeným čakaním absolútna aj relatívna priepustnosť strácajú svoj význam, pretože každá prichádzajúca požiadavka bude skôr či neskôr vybavená. Pre takýto QS sú dôležité ukazovatele:

Pre SOT zmiešaného typu používajú sa obe skupiny ukazovateľov: relatívne aj absolútna šírka pásma a očakávané charakteristiky.

V závislosti od účelu operácie zaraďovania do fronty možno ako výkonnostné kritérium vybrať ktorýkoľvek z vyššie uvedených ukazovateľov (alebo súbor ukazovateľov).

analytický model QS je súbor rovníc alebo vzorcov, ktoré umožňujú určiť pravdepodobnosti stavov systému v priebehu jeho prevádzky a 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 reprezentujú reálne systémy, sú spravidla zložité a ťažko viditeľ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ú exponenciálne rozdelené). V tomto prípade môžu byť všetky procesy v QS popísané obyčajnými diferenciálnymi rovnicami a v obmedzujúcom prípade pre stacionárne stavy lineárnymi algebraickými rovnicami a po ich vyriešení určiť vybrané ukazovatele výkonnosti.

Uvažujme o príkladoch 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 najjednoduchší, čas kontroly je náhodný s exponenciálnym rozložením.

Takáto situácia môže byť simulovaná trojkanálovým QS s poruchami (bez frontu). Systém je otvorený, s homogénnymi aplikáciami, 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 stavov systému je znázornený na obr. 2.11.

Ryža. 2.11.

Na grafe: - intenzita prúdu kamiónov; - intenzita kontrol dokladov jedným dopravným inšpektorom.

Simulácia sa vykonáva s cieľom určiť časť automobilov, ktoré sa nebudú testovať.

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

Dá sa charakterizovať priepustnosť tohto postu dopravných inšpektorov relatívna priepustnosť:

Príklad 2.6. Na prijímanie a spracovanie hlásení z prieskumnej skupiny bola na prieskumnom oddelení spolku pridelená skupina troch dôstojníkov. Predpokladaná rýchlosť podávania správ je 15 správ za hodinu. Priemerný čas spracovania jednej správy 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á skupina troch dôstojníkov postačuje na splnenie pridelenej úlohy.

Riešenie

Skupina dôstojníkov pracuje ako CMO s poruchami, 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 údržby . Distribučný zákon nie je známy, ale to nie je podstatné, pretože sa ukazuje, ž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émou „smrť a reprodukcia“, existujú preň hotové výrazy pre pravdepodobnosti obmedzujúcich stavov:

Vzťah sa nazýva znížená intenzita toku aplikácií. Jeho fyzický význam je nasledovný: hodnota je priemerný počet požiadaviek prichádzajúcich do QS za priemerný čas 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 QS bude mať teraz šesť kanálov a vypočítame:

Prichádzajúce hlásenia tak bude môcť spracovať len skupina šiestich policajtov s pravdepodobnosťou 95 %.

2.5.2. Viackanálové QS s čakaním

Príklad 2.7. V riečnom úseku je 15 prechodových zariadení rovnakého typu. Prúd vozidiel prichádzajúcich na priecestie je v priemere 1 jednotka/min, priemerný čas prejazdu jednej jednotky techniky je 10 minút (s prihliadnutím na návrat priecestného zariadenia).

Vyhodnoťte hlavné charakteristiky prechodu, vrátane pravdepodobnosti okamžitého prechodu ihneď po príchode zariadenia.

Riešenie

Absolútna šírka pásma, teda všetko, čo príde na prechod, je takmer okamžite prejdené.

Priemerný počet prevádzkovaných prechodových zariadení:

Pomery využitia kríženia a prestojov:

Bol vyvinutý aj program na riešenie príkladu. Časové intervaly príchodu techniky na priecestie, čas prechodu sa berú tak, že sa rozdelia podľa exponenciálneho zákona.

Koeficienty využitia trajektu po 50 jazdách sú prakticky rovnaké: .

ÚVOD

KAPITOLA I. FORMULÁCIA PROBLÉMOV PORADNEJ SLUŽBY

1.1 Všeobecná koncepcia teórie radenia

1.2 Modelovanie systémov radenia

1.3 Stavové grafy QS

1.4 Stochastické procesy

Kapitola II. ROVNICE OPISUJÚCE SYSTÉMY RADY

2.1 Kolmogorovove rovnice

2.2 Procesy "narodenie - smrť"

2.3 Ekonomická a matematická formulácia úloh radenia

Kapitola III. MODELY SYSTÉMOV RADY

3.1 Jednokanálový QS s odmietnutím služby

3.2 Viackanálové QS s odmietnutím služby

3.3 Model viacfázového systému služieb cestovného ruchu

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

3.5 Jednokanálový QS s neobmedzeným frontom

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

3.7 Viackanálové QS s neobmedzeným frontom

3.8 Analýza systému radenia supermarketov

ZÁVER

Úvod

V súčasnosti sa objavilo veľké množstvo literatúry, ktorá sa priamo venuje teórii radenia, vývoju jeho matematických aspektov, ako aj rôznym oblastiam jeho aplikácie – vojenské, medicínske, dopravné, obchodné, letecké atď.

Teória radenia je založená na teórii pravdepodobnosti a matematickej štatistike. Počiatočný vývoj teórie radenia sa spája s menom dánskeho vedca A.K. Erlang (1878-1929), svojimi prácami v oblasti projektovania a prevádzky telefónnych ústrední.

Teória radenia je oblasť aplikovanej matematiky, ktorá sa zaoberá analýzou procesov vo výrobe, službách a riadiacich systémoch, v ktorých sa homogénne udalosti mnohokrát opakujú, napríklad v podnikoch spotrebiteľských služieb; v systémoch na príjem, spracovanie a prenos informácií; automatické výrobné linky atď. Veľký prínos k rozvoju tejto teórie mali ruskí matematici A.Ya. Khinchin, B.V. Gnedenko, A.N. Kolmogorov, E.S. Wentzel a ďalší.

Predmetom teórie radenia je vytvoriť vzťahy medzi povahou toku požiadaviek, počtom obslužných kanálov, výkonom jedného kanála a efektívnou službou s cieľom nájsť najlepšie spôsoby riadenia týchto procesov. Úlohy teórie radenia sú optimalizačného charakteru a v konečnom dôsledku zahŕňajú ekonomické hľadisko stanovenia takého variantu systému, ktorý zabezpečí minimálne celkové náklady z čakania na obsluhu, straty času a prostriedkov na obsluhu a z prestojov. servisných kanálov.

V komerčných aktivitách aplikácia teórie radenia zatiaľ nenašla želanú distribúciu.

Je to spôsobené najmä náročnosťou stanovenia cieľov, potrebou hlbokého porozumenia obsahu komerčných aktivít, ako aj spoľahlivými a presnými nástrojmi, ktoré umožňujú vypočítať rôzne možnosti dôsledkov manažérskych rozhodnutí v komerčných aktivitách.

kapitola ja . Nastavenie úloh vo fronte

1.1 Všeobecný koncept teórie radenia

Povaha radenia v rôznych oblastiach je veľmi jemná a zložitá. Obchodná činnosť je spojená s vykonávaním mnohých operácií v štádiách pohybu, napríklad množstva komodít zo sféry výroby do sféry spotreby. Takýmito operáciami sú nakladanie tovaru, preprava, vykladanie, skladovanie, spracovanie, balenie, predaj. Okrem takýchto základných operácií je proces pohybu tovaru sprevádzaný veľkým množstvom predbežných, prípravných, sprievodných, paralelných a následných operácií s platobnými dokladmi, kontajnermi, peniazmi, automobilmi, zákazníkmi atď.

Uvedené fragmenty obchodnej činnosti sa vyznačujú hromadným príjmom tovaru, peňazí, návštevníkov v náhodných časoch, následne ich dôslednou obsluhou (uspokojovanie požiadaviek, požiadaviek, požiadaviek) vykonávaním príslušných operácií, ktorých čas realizácie je tiež náhodný. To všetko vytvára nerovnomernosť v práci, generuje nedostatočné zaťaženie, prestoje a preťaženia v obchodných prevádzkach. Fronty spôsobujú veľa problémov napríklad návštevníkom kaviarní, jedální, reštaurácií alebo vodičom áut v skladoch komodít, ktorí čakajú na vykládku, nakládku či papierovanie. V tomto ohľade existujú úlohy analyzovať existujúce možnosti vykonávania celého súboru operácií, napríklad obchodného poschodia supermarketu, reštaurácie alebo dielní na výrobu vlastných výrobkov s cieľom zhodnotiť ich prácu, identifikovať slabé väzby a rezervy a v konečnom dôsledku vypracovať odporúčania zamerané na zvýšenie efektívnosti obchodných operácií.

Okrem toho vyvstávajú ďalšie úlohy súvisiace s vytvorením, organizáciou a plánovaním novej ekonomickej, racionálnej možnosti vykonávania mnohých operácií v rámci obchodného priestoru, cukrárne, všetkých úrovní služieb reštaurácie, kaviarne, jedálne, plánovacieho oddelenia, účtovného oddelenia, personálne oddelenie a pod.

Úlohy organizácie radenia vznikajú takmer vo všetkých sférach ľudskej činnosti, napríklad obsluha kupujúcich v obchodoch predávajúcimi, obsluha návštevníkov v zariadeniach verejného stravovania, obsluha zákazníkov v podnikoch spotrebiteľských služieb, poskytovanie telefonických rozhovorov na telefónnej ústredni, poskytovanie lekárskej starostlivosti pacienti na klinike atď. Vo všetkých vyššie uvedených príkladoch existuje potreba uspokojiť potreby veľkého počtu spotrebiteľov.

Uvedené úlohy je možné úspešne riešiť pomocou metód a modelov teórie radenia (QMT) špeciálne vytvorených pre tieto účely. Táto teória vysvetľuje, že je potrebné niekomu alebo niečomu slúžiť, čo je definované pojmom „aplikácia (požiadavka) na službu“ a servisné operácie vykonáva niekto alebo niečo, čo sa nazýva obslužné kanály (uzly). Úlohu aplikácií v obchodných aktivitách zohrávajú tovar, návštevníci, peniaze, audítori, doklady a úlohu obslužných kanálov zohrávajú predajcovia, správcovia, kuchári, cukrári, čašníci, pokladníci, obchodníci, vrátnici, obchodné vybavenie atď. Je dôležité poznamenať, že v jednom variante je napríklad kuchár v procese prípravy jedál obslužným kanálom a v inom pôsobí ako požiadavka na obsluhu, napríklad vedúcemu výroby na príjem tovaru.

Žiadosti vzhľadom na hromadný charakter príchodu do servisu tvoria toky, ktoré sa nazývajú došlé pred vykonaním servisných operácií a po prípadnom čakaní na začiatok servisu, t.j. prestoje vo fronte, toky služieb formulára v kanáloch a potom sa vytvorí odchádzajúci tok požiadaviek. Vo všeobecnosti súbor prvkov vstupného toku aplikácií, front, obslužné kanály a výstupný tok aplikácií tvorí najjednoduchší jednokanálový čakací systém - QS.

Systém je súbor vzájomne prepojených a. účelovo interagujúce časti (prvky). Príkladom takýchto jednoduchých QS v obchodných činnostiach sú miesta príjmu a spracovania tovaru, zúčtovacie strediská so zákazníkmi v obchodoch, kaviarňach, jedálňach, zamestnania ekonóma, účtovníka, obchodníka, kuchára na distribúcii a pod.

Servisný postup sa považuje za ukončený, keď servisná požiadavka opustí systém. Trvanie časového intervalu potrebného na implementáciu servisnej procedúry závisí hlavne od charakteru požiadavky na službu, stavu samotného servisného systému a servisného kanála.

Trvanie pobytu kupujúceho v supermarkete skutočne závisí na jednej strane od osobných vlastností kupujúceho, jeho požiadaviek, od sortimentu tovaru, ktorý sa chystá kúpiť, a na druhej strane od formy organizácie obsluhy a obsluhy, čo môže výrazne ovplyvniť čas strávený kupujúcim v supermarkete a intenzitu obsluhy. Napríklad pokladníci ovládajúci „slepú“ metódu práce na pokladnici umožnili 1,3-násobne zvýšiť priepustnosť zúčtovacích uzlov a ušetriť čas strávený zúčtovaním so zákazníkmi na každej pokladnici o viac ako 1,5 hodiny denne. . Zavedenie jediného uzla vysporiadania v supermarkete poskytuje kupujúcemu hmatateľné výhody. Takže ak pri tradičnej forme zúčtovania bol čas obsluhy pre jedného zákazníka v priemere 1,5 minúty, potom so zavedením jediného zúčtovacieho uzla - 67 sekúnd. Z toho 44 sekúnd pripadá na nákup v sekcii a 23 sekúnd priamo na platby za nákup. Ak kupujúci uskutoční niekoľko nákupov v rôznych sekciách, strata času sa zníži nákupom dvoch nákupov 1,4-krát, troch - 1,9-krát, päť - 2,9-krát.

Pod obsluhou požiadaviek rozumieme proces uspokojovania potreby. Služba má iný charakter. Vo všetkých príkladoch však prijaté požiadavky musí obsluhovať nejaké zariadenie. Obsluhu v niektorých prípadoch vykonáva jedna osoba (obsluha zákazníka jedným predajcom, niekde skupina osôb (obsluha pacienta lekárskou komisiou v poliklinike), v niektorých prípadoch technické zariadenia (predaj sódovej vody). , sendviče predajnými automatmi). Súbor nástrojov, ktoré obsluhujú aplikácie , sa nazýva servisný kanál.

Ak sú obslužné kanály schopné uspokojiť rovnaké požiadavky, potom sa obslužné kanály nazývajú homogénne. Súbor homogénnych servisných kanálov sa nazýva servisný systém.

Systém radenia prijíma veľké množstvo požiadaviek v náhodných časoch, ktorých trvanie služby je tiež náhodnou premennou. Postupný príchod zákazníkov do systému zaraďovania sa nazýva prichádzajúci prúd zákazníkov a postupnosť zákazníkov opúšťajúcich systém zaraďovania sa nazýva výstupný prúd.