Järjekorravõrgud ja nende rakendused. Suni modelleerimine järjekorrasüsteemide ja võrkude alusel. QS-i kasutustegur

4 – Põhiteooria järjekorras seismine.

Definitsioon 1. Olgu mingi füüsiline süsteemS, mis muudab oma olekut ajas (üleminek ühest olekust teise), pealegi senitundmatul, juhuslikul viisil. Siis me ütleme seda süsteemisStoimub juhuslik protsess.

“Füüsilise süsteemina” võib mõista kõike: tehnilist seadet, ettevõtet, elusorganismi jne.

Näide. S – tehniline seade, mis koosneb paljudest sõlmedest, mis aeg-ajalt ebaõnnestuvad, asendatakse või taastatakse. Süsteemi protsess on juhuslik. Üldiselt, kui järele mõelda, on keerulisem tuua näidet "mittejuhuslikust" protsessist kui juhuslikust. Isegi kella protsess - klassikaline näide täpsest, rangelt kohandatud tööst ("töö nagu kell") allub juhuslikele muutustele (edasi minemine, mahajäämine, peatumine).

2. definitsioon. Juhuslikku protsessi süsteemis nimetatakse Markovi protsessiks, kui see toimub mis tahes ajahetkelt 0 protsessi tõenäosuslikud omadused tulevikus sõltuvad ainult selle hetkeseisustt 0 ja ei sõltu sellest, millal ja kuidas süsteem sellesse olekusse jõudis.

Lase hetkelt 0 süsteem on teatud olekusS 0 . Me jälgime protsessi kõrvalt ja hetkelt 0 teavad süsteemi seisukordaS 0 ja kogu protsessi ajalugu, kõike, mis selle käigus juhtust< t 0 . Meie, loomulikult. Tulevikust huvitatud:t> t 0 . Kas me suudame seda ennustada? Täpselt – ei. Meie protsess on juhuslik, seega ettearvamatu. Kuid tulevikus võime leida protsessile mõningaid tõenäosuslikke omadusi. Näiteks tõenäosus, et mõne aja pärastt süsteem SsuudabS 1 või päästa riikS 0 jne.

Kui protsess on Markov, siis on võimalik ennustada ainult süsteemi hetkeseisu arvestadesS 0 ja unustades selle "eelajaloo" (süsteemi käitumine, kuit< t 0 ). Riik iseS 0 , oleneb muidugi minevikust, aga kui selleni jõutakse, võib mineviku unustada. Need. Markovi protsessis "tulevik sõltub minevikust ainult oleviku kaudu".

Näide. Süsteem S– Geigeri loendur, mida aeg-ajalt tabavad kosmilised osakesed; süsteemi olek ajahetkeltmida iseloomustavad loenduri näidud - kuni selle hetkeni saabunud osakeste arv. Lase hetkelt 0 loendur näitabS 0 . Tõenäosus, et hetkelt> t 0 loendur näitab seda või teist osakeste arvuS 1 (või vähem S 1 ) sõltub S 0 , kuid see ei sõltu täpsetest hetkedest, mil osakesed enne hetke saabusidt 0 .

Praktikas on sageli protsesse, mida, kui mitte täpselt markovis, võib mõnes lähenduses pidada Markoviks. Näiteks,S ­ - õhuvõitluses osalev lennukite rühm. Süsteemi olekut iseloomustab "punaste" lennukite arv -x ja "sinine" y, säilinud (mitte maha lastud) mingil hetkel. Hetkelt 0 teame pidude arvux 0 ja y 0 . Meid huvitab tõenäosus, et mingil ajahetkelt 0 + tarvuline ülekaal on "punaste" poolel. Millest see tõenäosus sõltub? Esiteks, millises olekus süsteem antud ajahetkel ont 0 , ja mitte selle kohta, millal ja millises järjestuses allatulistatud surid kuni ajahetkenit 0 lennukid.

Sisuliselt võib Markovi protsessiks pidada mis tahes protsessi, kui kõik "minevikust" pärit parameetrid, millest "tulevik" sõltub, viiakse üle "olevikku". Näiteks lase me räägime mõne töö kohta tehniline seade; mingil ajahetkelt 0 see on endiselt töökorras ja meid huvitab tõenäosus, et see veel mõnda aega töötabt. Kui praegu mõelda lihtsalt "süsteem töötab", siis protsess ei ole kindlasti Markov, sest tõenäosus, et see õigel ajal ebaõnnestubt, oleneb üldiselt sellest, kui kaua see on juba töötanud ja millal viimati remont tehti. Kui mõlemad need parameetrid (kogu tööaeg ja remondist järgnev aeg) sisalduvad süsteemi hetkeseisus. Seda protsessi võib pidada Markoviks.

3. määratlus. Protsessi nimetatakse diskreetseks olekuks, kui sellel on võimalikud olekudS 1 , S 2 ,... saab eelnevalt loetleda (ümber nummerdada) ja süsteemi üleminek olekust olekusse toimub "hüppes", peaaegu silmapilkselt.

4. määratlus. Protsessi nimetatakse pideva ajaga protsessiks, kui võimalike olekust olekusse üleminekute hetked ei ole eelnevalt fikseeritud, vaid on ebakindlad, juhuslikud, kui üleminek võib toimuda põhimõtteliselt igal hetkel.

Vaatleme ainult diskreetsete olekutega protsesse.

Näide. Tehniline seadeSkoosneb kahest sõlmest. Igaüks neist võib juhuslikul ajahetkel ebaõnnestuda (ebaõnnestumine), misjärel algab koheselt sõlme remont, mis jätkub ka teadmata juhusliku aja jooksul.

Joon.4.1

Võimalikud süsteemi olekud:

S 0 - mõlemad sõlmed töötavad;

S 1 - esimene sõlm on remondis, teine ​​on töökorras;

S 2 - teine ​​sõlm on remondis, esimene on töökorras;

S 3 Mõlemad üksused on remondis.

Nool osutabS 0 sisse S 1 tähendab esimese sõlme rikkemomenti jne. Joonisel puudub oleku noolS 0 olekusse S 3 , kuna tõenäosus, et kaks seadet korraga rikki lähevad, kipub olema null.

Definitsioon 5. Sündmuste voog on homogeensete sündmuste jada, mis järgneb üksteisele mingil juhuslikul ajal (näiteks rikete voog arvutis, kõnede voog telefonijaamas).

Sündmuste voo kõige olulisem omadus on selle intensiivsus.lon sündmuste keskmine arv ajaühikus. voolukiirus võib olla konstantne (l= konst), samuti ajast sõltuv muutuja. Näiteks tänaval liikuvate autode voog on päeval intensiivsem kui öösel ning kella 14-15 autode voolu võib pidada konstantseks.

Definitsioon 6. Sündmuste voogu nimetatakse regulaarseks, kui sündmused järgnevad üksteise järel korrapäraste võrdsete ajavahemike järel.

Definitsioon 7. Sündmuste voogu nimetatakse statsionaarseks, kui selle tõenäosuslikud omadused ei sõltu ajast. Eelkõige intensiivsuslstatsionaarne vool peab olema konstantne. See ei tähenda sugugi, et tegelik sündmuste arv, mis ajaühikus ilmneb, on konstantne – ei, voos on paratamatult (kui see pole regulaarne) mõningaid juhuslikke kontsentratsioone ja haruldusi. On oluline, et statsionaarse voolu puhul ei oleks need kontsentratsioonid ja haruldased korrapärased: ühes pikkusega 1 segmendis võib olla rohkem sündmusi ja teises võib olla vähem sündmusi, kuid sündmuste keskmine arv ajaühikus on konstantne. ei sõltu ajast.

Näiteks kella 13.00-14.00 PBX-i saabuvate kõnede voog. See on praktiliselt paigal, kuid sama vool päevasel ajal ei ole enam paigal.

Definitsioon 8. Sündmuste voogu nimetatakse ilma järelmõjuta vooks, kui tegemist on kahe mittekattuva ajaintervalligat 1 ja t 2 ühte neist tabanud sündmuste arv ei sõltu sellest, kui palju sündmusi teist tabab. Sisuliselt tähendab see seda, et voolu moodustavad sündmused ilmnevad teatud hetkedel üksteisest sõltumatult, millest igaüks on põhjustatud oma põhjustest.

Näiteks metroosse sisenevate reisijate voolul pole peaaegu mingit järelmõju. Ostetud kaubaga letilt lahkuvate klientide vooga on aga juba järelmõju (kasvõi juba sellepärast, et üksikute klientide vaheline ajavahemik ei saa olla väiksem kui iga kliendi minimaalne teenindusaeg).

Definitsioon 9. Sündmuste voogu nimetatakse tavaliseks, kui sündmused selles ilmuvad ükshaaval, mitte rühmadena korraga.

Näiteks klientide vool hambaarsti juurde on tavaliselt tavaline. Jaamale lähenevate rongide voog on tavaline, vagunite voog aga erakordne.

Definitsioon 10. Sündmuste voogu nimetatakse lihtsaimaks (või statsionaarseks Poissoniks), kui sellel on kolm omadust korraga: see on statsionaarne, tavaline ja sellel pole järelmõju ning sisendvoog ise on jaotatud vastavalt Poissoni seadusele ( ).

Kirjelduseks juhuslik protsess, mis voolab diskreetsete olekutega süsteemisS 1 , S 2 , ..., S nkasutavad sageli olekutõenäosusilk 1 ( t),..., p n( t) , kus p k( t) on tõenäosus, et hetkeltsüsteem on seisukorrasSk. Tõenäosused p k( t) vastama tingimusele: .

Kui diskreetsete olekute ja pideva ajaga süsteemis toimuv protsess on Markovi, siis olekutõenäosuste puhullk 1 ( t), ..., p n( t) saab koostada lineaarsete diferentsiaalvõrrandi süsteemi. Nende võrrandite koostamisel on mugav kasutada süsteemi olekugraafikut, millel iga olekust olekusse suunduva noole vastu on kinnitatud sündmuste voo intensiivsus, kandes süsteemi mööda noolt (joon. 4.2). :

Joon.4.2 lijon sündmuste voo intensiivsus, mis kannab süsteemi olekust üleSi olekusse S j. Loomise reegel lineaarsete diferentsiaalvõrrandite süsteemid olekute tõenäosuste leidmiseks. Igal osariigil on oma võrrand. Iga võrrandi vasakus servas on tuletis ja paremal pool on nii palju termineid, kui palju nooled on antud olekuga otseselt seotud; kui nool viib antud olekusse, siis on terminil "+" märk, vastasel juhul on sellel märk "-". Iga liige on võrdne sündmuste voo intensiivsusega, mis viib süsteemi mööda antud noolt, korrutatuna selle oleku tõenäosusega, millest nool väljub. See. lineaarsete diferentsiaalvõrrandite süsteem on meie puhul järgmine:

Sellise süsteemi integreerimise algtingimused peegeldavad süsteemi esialgset seisukorda. Kui näiteks süsteemt=0 suutisSk, siis. Neid võrrandeid saab lahendada analüütiliselt, kuid see on mugav ainult siis, kui võrrandite arv ei ületa kahte (mõnikord kolme). Kui võrrandeid on rohkem, kasutatakse numbrilisi meetodeid.

Mis juhtub olekute tõenäosustega kell ? Willlk 1 ( t), ..., p n( t) püüdlema mingite piiride poole? Kui need piirid on olemas ja ei sõltu süsteemi algolekust, nimetatakse neid lõppseisu tõenäosusteks: . pion süsteemi keskmine suhteline viibimisaegi- riik.

Kuidas leida lõplikke tõenäosusi? Kuna kõikpi= konst, siis on iga võrrandi vasakpoolsed tuletised võrdsed nulliga. See. oleme saanud lineaarsete algebraliste võrrandite süsteemi. Kuna selles süsteemis pole ühelgi võrrandil vaba liiget, on süsteem degenereerunud (st kõik muutujad väljendatakse ühe kaudu). Selle vältimiseks on vaja kasutada normaliseerimistingimust (), samas kui mis tahes võrrandist saab loobuda.

Järjekorrasüsteemide klassifikatsioon

Vastavalt teenindusseadmete arvule jagunevad QS-id ühe- ja mitmekanalilisteks. Mitme kanaliga QS koosneb mitmest seadmest ja igaüks neist saab esitada päringu.

Ka QS on jaotatud süsteemideks ilma ootamiseta ja ootamisega. Esiteks lahkub päring järjekorrast, kui selle saabumise ajaks ei ole vähemalt ühte kanalit, mis suudaks seda päringut kohe teenindada. Viimased jagunevad omakorda piiranguteta ja järjekorra pikkuse piirangutega süsteemideks.

QS jaguneb ka prioriteetidega ja prioriteetideta süsteemideks. Omakorda jagatakse prioriteediga süsteemid katkestusteta ja katkestusteta QS-ideks.

Ühe kanaliga QS koos piiramatu järjekord

Joon.4.3

Leiame tõenäosusedp k:

Riigi jaoks S 0 : , seega ;

Riigi jaoks S 1 n: , asendame saadud väärtuse väärtusegalk 1 : . Samamoodi,.

Tõenäosus lk 0 leiame normaliseerimistingimusest:

, on geomeetriline progressioonr<1 koondub. - tõenäosus, et rakendusi pole.

on tõenäosus, et seade on päringu teenindamisega hõivatud.r= l/ mon ühe kanaliga QS-i koormuse mõõt.

Praegusel ajal võib süsteemis olla 0, 1, 2, ...,k, ... tõenäosustega rakendusedlk 0 , lk 1 lk 2 , ... Taotluste arvu matemaatiline ootus:

arvestades seda , saame:

Järjekorra keskmine pikkus võrdub süsteemis olevate rakenduste keskmise arvu ja teenuses olevate rakenduste keskmise arvu vahega: .

Väikesed valemid

Joon.4.4

Little'i esimene valem võimaldab määrata QS-i reaktsiooniaja (aeg, mil rakendus süsteemis viibib).

Lase X( t) on QS-ile kuni ajahetkeni laekunud taotluste arvt, Y( t) – need, kes varem ühisest turukorraldusest lahkusid t . Mõlemad funktsioonid on juhuslikud ja suurenevad klientide saabumise ja lahkumise hetkel ühe võrra. Siis korraga süsteemis olevate rakenduste arvtvõib määratleda järgmiselt: . Mõelge väga pikale ajavahemikuleT ja arvutage keskmine taotluste arv süsteemis:

.

Integraal on võrdne funktsioonidega piiratud astmelise kujundi pindalagaX( t) ja Y( t) , koosneb see summa ristkülikutest, mille laius on võrdne ühega ja pikkus on viibimisaegi-s rakendus süsteemis. Summa kehtib kõikidele aja jooksul süsteemi laekunud taotlusteleT. Korrutage parem pool ja jagagel: . Tl– aja jooksul laekunud taotluste keskmine arvT. Kõigi aegade summa jagaminet ikeskmise taotluste arvu kohta saame taotluse keskmise süsteemis viibimise aja: .

Üsna samamoodi saate rakenduse keskmise järjekorras viibimise aja: .

Mitme kanaliga QS piiramatu järjekorraga

Joon.4.5

Leiame tõenäosusedp k:

Riigi jaoks S 0 : ;

Osariikide jaoks S 1 – S n: ;

Sest S n +1 : ; ...

Sest Sn+s-1: ;

Sest Sn+s: .

Alates esimesest n +1 võrrandid saame:

Viimasest võrrandist väljendame: ja asendage eelviimases: , . Siis .

Analoogiat jätkates: .

Nüüd leiame lk 0 , asendades saadud avaldised normaliseerimistingimustega (): . Siit .

QS tulemusnäitajad

– Nõudekaotuse tõenäosus QS-is. Eriti sageli kasutatakse seda sõjaliste küsimuste uurimisel. Näiteks objekti õhutõrje efektiivsuse hindamisel iseloomustab see õhusihtmärkide läbimurdmise tõenäosust objektile. Kaotusega QS-i puhul on see võrdne tõenäosusega, et kõik nõuded on teenindusega hõivatudnsüsteemi seadmed. Enamasti on see tõenäosusp n või lkavatud.

– Tõenäosus, et süsteemi nõuded on hõivatudk seadmed, on võrdne p k.

– Keskmine hõivatud seadmete arv: iseloomustab serveerimissüsteemi laadimisastet.

– Keskmine teenuseta seadmete arv: .

– Seadme seisakutegur: .

– Seadmete täituvus: .

- Keskmine järjekorra pikkus: , p kon tõenäosus, et süsteem onk nõuded.

– Keskmine taotluste arv teenindussektoris: .

– tõenäosus, et teenuse käivitamist ootavate taotluste arv järjekorras on suurem kui teatud arvm: . See näitaja on eriti kasulik piiratud ooteajaga nõuete esitamise võimaluse hindamisel.

Lisaks loetletud kriteeriumidele saab QS-i efektiivsuse hindamisel kasutada kulunäitajaid:

qumbes– süsteemi iga nõude teenindamise kulud;

qoh– järjekorras seisvate tühiste päringutega seotud kadude kulu ajaühiku kohta;

qjuures– taotlussüsteemist lahkumisega seotud kahjud;

q k- iga seadme töökulu ajaühiku kohta;

q kjne- seisakute maksumus ajaühiku kohtaksüsteemi seade.

Majandusnäitajate järgi QS-i optimaalsete parameetrite valimisel saame kasutada süsteemi kadude maksumuse funktsiooni (ootusega QS-i puhul):T- ajavahemik.

Tõrgetega QS-i jaoks: .

Segatud jaoks:.

QS-i majandusliku efektiivsuse kriteerium: , Koos- iga rakenduse teenindamisel saavutatav majanduslik efekt.

QS suletud tüüp

Näide. C1, C2, C3 - masinad; NC - kesksalvestus; B - manipulaator. Transpordikäru (manipulaator) transpordib kasutatud detaili masinast poodi ja paneb sinna, korjab uue detaili (tooriku), transpordib masinasse ja seab tööasendisse kinnitamiseks. Kogu maha- ja pealelaadimiseks vajaliku perioodi jooksul on masin tühikäigul. AegThtooriku vahetus ja hooldusaeg.

Masinate hoolduse intensiivsus on määratletud kui , - masina keskmine hooldusaeg, mis arvutatakse , kusn- taotluste arv. Masina teenindustaotluse esitamise intensiivsus on määratletud kui (kus on keskmine aeg, mille jooksul masin on osa töötlemiseks kulunud).

Ühe käepidemega manipulaatoriga tööpinkide süsteem on sisemise korraldusega ootesüsteem FIFO : rahuldatakse iga masina taotlus hoolduseks, juhul kui manipulaator on hõivatud, on taotlus järjekorda ja masin ootab manipulaatori vabanemist. See protsess on Markovian, st. teenusepäringu juhuslik väljastamine teatud ajahetkelt 0 ei sõltu eelnevatest rakendustest, s.t. protsessi käigust eelmisel perioodil. Taotluse täitmise kestus võib olla erinev ja on juhuslik suurus, mis ei sõltu esitatud taotluste arvust. Kogu protsess ei sõltu sellest, mis juhtus enne teatud ajahetket 0 .

Tööpingisüsteemis võib teenindustaotluste arv olla 0, 1, 2, ...m, kus mon masinate koguarv. Siis on võimalikud järgmised seisundid:

S 0 - kõik masinad töötavad, manipulaator seisab.

S 1 - kõik masinad peale ühe töötavad, manipulaator teenindab masinat, millelt tooriku vahetamise avaldus saadi.

S 2 - töö m-2 masin, üks masin vahetab töödeldavat detaili, teine ​​ootab.

S 3 - töö m-2 masin, üks masin on manipulaatoriga, kaks masinat ootavad järjekorras.

Sm- kõik masinad seisavad, ühte hooldab manipulaator, ülejäänud ootavad tellimuse täitmist.

Joon.4.6.

Oleku ülemineku tõenäosusSkühest võimalikust olekustS 1 , S 2 , ... Smsõltub teenusepäringute juhuslikust saabumisest ja arvutatakse järgmiselt:

lk 0 on tõenäosus, et kõik masinad töötavad.

Manipulaator töötab süsteemi olekutes alatesS 1 enne Sm­ . Siis on selle laadimise tõenäosus võrdne: .

Järjekorras olevate masinate arv on seotud olekutegaS 2 , – Sm, samal ajal kui ühte masinat hooldatakse ja ( k -1) - ootan. Seejärel keskmine masinate arv järjekorras: .

Ühe masina seisaku suhe (mitme masina hoolduse ootamise tõttu): .

Keskmine kasutus masina kohta:

Monte Carlo meetodi rakendamine probleemide lahendamisel,

seotud järjekorra teooriaga

Homogeensete sündmuste kulgemise kirjeldamiseks piisab ajahetkede jaotumise seaduse tundmisest t 1 , t 2 , ..., t k, ... millele sündmusi laekub.

Edasiste kaalutluste mugavuse huvides on soovitatav kasutada väärtusit 1 , t 2 , ..., lülituda juhuslikele muutujatelez 1 , z 2 , ..., zm, ... , nii et:

juhuslikud muutujadzkon ajavahemike pikkused järjestikuste hetkede vahelt k.

Juhuslike muutujate kogumziloetakse antuks, kui ühisjaotusfunktsioon on määratletud: . Tavaliselt võetakse arvesse ainult pidevaid juhuslikke muutujaidzk, seega kasutatakse sageli vastavat tihedusfunktsioonif( z 1 , z 2 ,..., z k) .

Tavaliselt arvestab QS-teooria homogeensete sündmuste voogusid ilma järelmõjuta, mille puhul juhuslikud muutujadzksõltumatu. Sellepärast . Funktsioonidfi( z i) juures i>1 on tiheduse tingimuslikud funktsioonid, eeldusel, et intervalli alghetkelzk ( i>1) avaldus on laekunud. Seevastu funktsioonf 1 ( z 1 ) on tingimusteta tihedusfunktsioon, kuna nõude ilmnemise või mitteilmumise kohta esialgsel ajahetkel eeldusi ei tehta.

Laialdaselt on kasutusel nn statsionaarsed voolud, mille tõenäosuslik režiim ajas ei muutu (st esinemise tõenäosusktaotlusi teatud perioodiks (t 0 , t 0 + t) ei sõltu t 0 , kuid sõltub ainult sellestt ja k). Sest statsionaarsed voolud ilma järelmõjuta tekivad järgmised seosed:

kus l on statsionaarse voolu tihedus.

Süsteemi sisestatud tellimus võib hõivata ainult vabad read. Ridade hõivamise järjekorra kohta saab teha erinevaid oletusi:

a) read on hõivatud nende arvude järjekorras. Suurema numbriga liini ei saa rakenduse teenindamisega kaasata, kui on vaba liin väiksema numbriga;

b) read on hõivatud kordamööda. Vabanenud liin siseneb järjekorda ja ei alusta rakenduste teenindamist enne, kui kõik varem vabastatud read on ära kasutatud;

c) read on hõivatud juhuslikus järjekorras vastavalt antud tõenäosused. Kui järgmise avalduse laekumise hetkel onnSt.vabad read, siis võib lihtsaimal juhul teatud rea hõivamise tõenäosuse võtta võrdseks . Keerulisematel juhtudel tõenäosusedpeetakse sõltuvaks ridade arvust, nende vabastamise hetkedest ja muudest parameetritest.

Sarnaseid oletusi saab teha ka teenusetaotluste vastuvõtmise järjekorra kohta juhul, kui süsteemis on moodustatud päringute järjekord:

a) Taotlusi võetakse kätte kes saab, see mees. Vabanenud liin alustab teise poolt varem süsteemi sisestatud päringu teenindamist;

b) taotlused võetakse kättetoimetamiseks vastu keeldumise saamise minimaalse aja järgi. Vabanenud liin alustab rakenduste teenindamist, mille saab tagasi lükata võimalikult lühikese aja jooksul;

c) avaldusi võetakse kätte juhuslikus järjekorras vastavalt etteantud tõenäosustele. Kui rea vabastamise ajal onmpäringud järjekorras, siis võib lihtsaimal juhul võtta mõne konkreetse teenindussoovi valimise tõenäosuse võrdseksq=1/ m. Keerulisematel juhtudel tõenäosusedq 1 , q 2 ,..., qmloetakse sõltuvaks rakenduse süsteemis viibimise ajast, keeldumise saamiseni jäänud ajast ja muudest parameetritest.

· Mitmete rakendusprobleemide lahendamiseks on vaja arvestada sellise olulise teguriga nagu teenindussüsteemi elementide usaldusväärsus. Eeldame, et töökindluse seisukohalt võib iga liin teatud ajahetkel olla kas töökorras või vigane. Liini töökindluse määrab rikkevaba töö tõenäosusR= R( t) , antud aja funktsioonina. Samuti eeldame, et ebatäieliku töökindluse tõttu ebaõnnestunud liini saab kasutusele võtta (remontida), mis nõuab aegatlk. väärtust tlkkäsitleme antud jaotusseadusega juhuslikku muutujat.

Taotluse saatuse kohta, mille teenindamisel liin katkeb, võib teha erinevaid oletusi, teha erinevaid oletusi: taotlus lükatakse tagasi; rakendus jääb süsteemi (koos aeg kokkuära jää enam süsteemitn) korraväliselt kättetoimetamise taotlejana; rakendus satub järjekorda ja teenindatakse üldiselt jne.

Järjekorraprobleemidele rakendatava statistilise katsemeetodi olemus on järgmine. Konstrueeritakse algoritme, mille abil on võimalik välja töötada antud homogeensete sündmuste voogude juhuslikke realisatsioone, samuti "simuleerida" teenindussüsteemide toimimisprotsesse. Neid algoritme kasutatakse juhusliku teenindusprotsessi rakenduste korduvaks reprodutseerimiseks probleemi fikseeritud tingimustes. Saadud informatsiooni protsessi olekute kohta töödeldakse hindamise eesmärgil statistiliselt, mis on teenuse kvaliteedi näitajad.

Statistiliste testide meetod võimaldab meil põhjalikumalt, võrreldes asümptootiliste valemitega, uurida teenuse kvaliteedi sõltuvust päringute voo omadustest ja teenindava süsteemi parameetritest.

See saavutatakse kahe asjaolu tõttu. Esiteks saab järjekorra teoorias statistiliste testide meetodil ülesandeid lahendades kasutada protsessi kohta ulatuslikumat informatsiooni, kui seda tavaliselt analüütiliste meetoditega teha saab.

Teisest küljest viitavad asümptootilistest valemitest saadud teenuse kvaliteedinäitajate väärtused rangelt võttes ajapunktidele, mis on protsessi algusest piisavalt kaugel. Tegelikkuses erinevad protsessi algusele lähedased hetked, mil statsionaarne režiim pole veel sisse lülitatud, teenuse kvaliteedinäitajate väärtused üldiselt oluliselt asümptootilistest väärtustest. Statistiliste testide meetod võimaldab piisavalt üksikasjalikult uurida siirderežiime.

Paljude rakendusprobleemide puhul osutuvad eeldused, mille alusel analüütilised valemid kehtivad, liiga piiravaks. Ülesannete lahendamisel statistiliste testide meetodil võivad mõned eeldused oluliselt nõrgeneda.

Esiteks puudutab see mitmefaasilist teenust (st käsitletakse teenindussüsteeme, mis koosnevad mitmest järjestikku töötavast, üldjuhul heterogeensest üksusest).

Probleemi teine ​​oluline üldistus on eeldus teenindusse saabuvate päringute voo olemuse kohta. Homogeensete sündmuste vooge on lubatud käsitleda praktiliselt meelevaldse jaotusseadusega. Viimane asjaolu on oluline kahel järgmisel põhjusel. Esiteks erinevad rakenduste tegelikud vood mõnel juhul märkimisväärselt lihtsaimast. Teise põhjuse selgitamiseks oletame, et algset päringute voogu on kõige lihtsama vooga ligikaudne. Samal ajal ei ole esimeses etapis kättetoimetatavate rakenduste voog rangelt võttes kõige lihtsam. Kuna esimese faasi väljundiks olev voog on teises faasis päringuid teenindava agregaadi sisendvoog, jõuame taas probleemini voogude teenindamiseks, mis pole kõige lihtsamad.

· Algoritmi modelleerimise struktuur

rakendusteenuse protsess

Mõelge ühefaasilisele QS-ilenread, mille kohta päringuid võetakse vastu juhuslikel aegadelt i. Kui taotluse vastuvõtmise ajal on vabu ridu (nende numbernSt.), hõivab rakendus mõnda aega ühte neisttlk. Vastasel juhul on rakendus süsteemis hetkenit nootab kättetoimetamist. Aastal t t ooteaeg, võivad mõned liinid vabaks muutuda (nende numberm) ja sel juhul on võimalik taotlust kätte toimetada. Kui kuni ajanit nükski rida pole vabastatud (m=0 ), lükatakse taotlus tagasi.

Eeldame, et süsteemi ebapiisavalt kõrge töökindluse tõttu võivad rakendust teenindavad liinid ebaõnnestuda, seejärel lükatakse rakendus tagasi ja liini saab parandada ka mõne aja pärast. t pem kasutusele võtta.

Teenusetaotluste kvaliteedi uurimiseks pakutakse sedaN * süsteemi toimimisprotsessi mitmekordne modelleerimine intervallis (0, T) . Modelleerimise käigus märgitakse uuritud teostuste arv tähegaN.

Algoritm:

1. Hetk on määratudt ijärgmise avalduse saamine süsteemi.

2. Kui t i< T, seejärel jätkake 3. sammuga, muul juhul jätkake 11. sammuga.

3. Sissetuleva päringu teenindamise võime kontrollimine: kuinSt.>0 , seejärel minge 4. sammu juurde, muul juhul jätkake sammuga 12. (Taotluse saabumisaja väärtust i võrreldes tosvkõikidele liinidele, st. ilmuvad vabad read.)

4. Kui nSt.>1 , seejärel jätkake 5. sammuga, muul juhul jätkake 6. sammuga.

5. Vaba liini number valitakse vastavalt erireeglitele.

6. Valitud rida määratakse.

7. Kontrollige: kas teenus on katkenud töökindluse puudumise tõttu? Kui jah, siis jätkake sammuga 8, muul juhul jätkake sammuga 10.

8. Ajastustremkatkenud liini parandaminetremon teatud jaotusseadus).

9. Navatud= Navatud+1 . Minge 1. sammu juurde.

10. Kiire aja määraminethrida, mis on määratud päringu teenindamiseks (mõni juhuslik muutuja teatud jaotusseadusega) ja rea ​​vabastamise aeg:tosv= t i+ th. Üleminek järgmisele rakendusele (samm 1).

11. Kontrollige: kuiN< N * , siis N= N+1 ja minge 1. sammu juurde, vastasel juhul - katse tulemuste töötlemine ja lõpp.

12. Määratlege:

Aeg t nrakenduse püsimine süsteemis;

B) vabade kanalite arvm ajal t n.

13. Kui m>0 , seejärel minge 14. sammu juurde, muul juhul jätkake 9. sammuga.

14. Kui m>1 , seejärel minge 15. sammu juurde, muul juhul jätkake 6. sammuga.

15. Valitakse teatud rida vastavalt aktsepteeritud reeglitele ja minge 6. sammu juurde.

Paljudes majanduse, rahanduse, tootmise ja igapäevaelu valdkondades on oluline roll järjekorra süsteemid(SMO), st. sellised süsteemid, milles ühelt poolt esitatakse massiliselt mis tahes teenuste osutamise taotlusi (nõudeid) ja teiselt poolt need taotlused rahuldatakse.

Finants- ja majandussfääri QS-i näidetena võib tuua süsteemid, milleks on: erinevat tüüpi pangad, kindlustusorganisatsioonid, maksuinspektsioonid, audititeenused, erinevad sidesüsteemid (sh telefonijaamad), peale- ja mahalaadimiskompleksid (kaubajaamad), bensiinijaamad, erinevad teenindussektori ettevõtted ja organisatsioonid (poed, toitlustusasutused, infolauad, juuksurid, piletikassad, valuutavahetuspunktid, remonditöökojad, haiglad).

Süsteemid nagu arvutivõrgud, teabe kogumise, salvestamise ja töötlemise süsteemid, transpordisüsteemid, automatiseeritud tootmiskohti, tootmisliine võib pidada ka omamoodi QS-iks.

Kaubanduses tehakse kaubamassi tootmissfäärist tarbimissfääri viimise protsessis palju toiminguid. Sellised toimingud on: kaupade peale- ja mahalaadimine, transport, pakendamine, pakendamine, ladustamine, väljapanek, müük jne. kaubandustegevus mida iseloomustab massiline kauba-, rahavoog, massiline klienditeenindus jne, samuti vastavate toimingute sooritamine, mis on oma olemuselt juhuslikud. Kõik see tekitab töös ebaühtlust. kaubandusorganisatsioonid ja ettevõtetele, tekitab alakoormusi, seisakuid ja ülekoormust. Järjekorrad võtavad palju aega näiteks ostjatelt kauplustes, autode juhtidelt kaubaladudes, maha- või pealelaadimise ootel.

Sellega seoses tekivad ülesanded analüüsida näiteks kaubandusosakonna, kaubandusettevõtte või sektsiooni tööd, et hinnata nende tegevust, tuvastada puudused, reservid ja lõpuks võtta meetmeid selle tõhususe suurendamiseks. Lisaks on probleeme säästlikumate toimingute loomise ja rakendamisega sektsioonis, osakonnas, kaubandusettevõttes, juurviljabaasi, kaubandusosakonna jne piires. Seetõttu on kaubanduse korraldamisel järjekorrateooria meetodid. võimalik määrata optimaalne kogus müügikohad selle profiili kohta, müüjate arv, kaupade impordi sagedus ja muud parameetrid.

Järjekorrasüsteemide teine ​​tüüpiline näide võib olla tarne- ja turundusorganisatsioonide laod või baasid ning järjekorrateooria ülesandeks on luua baasi saabuvate teenindusnõuete ja teenindavate seadmete arvu optimaalne suhe. hoolduskulud ja transpordiseisakutest tulenevad kaod oleksid minimaalsed. Järjekorra teooria võib rakendust leida ka pindala arvutamisel laoruumid, samas kui hoiuala käsitletakse teenindusseadmena, ja saabumine Sõiduk mahalaadimiseks - nõudena.

QS-i peamised omadused

QS sisaldab järgmist elemendid: nõuete allikas, sissetulev voog nõuded, järjekord, teenindusseade (teenusekanal), väljaminev nõuete voog (teenindatud päringud).

Iga QS on loodud teenindama (käivitama) teatud süsteemi sisenevate rakenduste (nõuete) voogu, peamiselt mitte regulaarselt, vaid juhuslikel aegadel. Samuti ei kesta rakenduste teenus mitte konstantset ettemääratud aega, vaid juhuslikult, mis sõltub paljudest juhuslikest põhjustest. Pärast päringu teenindamist kanal vabastatakse ja on järgmise päringu vastuvõtmiseks valmis.

Päringute voo ja nende teenindamise aja juhuslik iseloom põhjustab QS-i ebaühtlase töökoormuse: teatud ajavahemike järel võivad QS-i sisendisse koguneda teenindamata päringud, mis põhjustab QS-i ülekoormuse, samal ajal kui mõned muud ajaintervallid, vabade kanalitega QS sisendis, päringud puuduvad, mis toob kaasa QS alakoormamise, st. selle kanalite jõudeolekusse. QS-i sissepääsu juurde kogunevad rakendused kas "saavad" järjekorda või ei saa mingil põhjusel järjest enam edasi viibida, jätavad QS-i teenindamata.

QS-skeem on näidatud joonisel 5.1.

Joonis 5.1 - Järjekorrasüsteemi skeem

Iga QS sisaldab oma struktuuris teatud arvu teenindusseadmeid, mida kutsutakse teeninduskanalid. Kanalite rolli võivad täita erinevad seadmed, teatud toiminguid tegevad isikud (kassapidajad, operaatorid, müüjad), sideliinid, sõidukid jne.

Igal QS-il on olenevalt selle parameetritest: rakenduste voo olemus, teeninduskanalite arv ja nende jõudlus, samuti töö korraldamise reeglid teatud tööefektiivsus (läbilaskvus), mis võimaldab enam-vähem edukalt toime tulla rakenduste vooluga.

QS on õppeaine järjekorra teooria.

Järjekorrateooria eesmärk- soovituste väljatöötamine QS-i ratsionaalseks ehitamiseks, nende töö ratsionaalseks korraldamiseks ja rakenduste voo reguleerimiseks, et tagada QS-i kõrge efektiivsus.

Selle eesmärgi saavutamiseks püstitatakse järjekorrateooria ülesanded, mis seisnevad QS-i toimimise efektiivsuse sõltuvuste väljaselgitamises selle organisatsioonist (parameetritest).

Nagu QS toimimise tõhususe tunnused Valida saab kolme peamise (tavaliselt keskmiste) näitajate rühma vahel:

1. QS-i kasutamise tõhususe näitajad:

1.1. QS-i absoluutne läbilaskevõime on keskmine päringute arv, mida QS saab ajaühikus teenindada.

1.2. QS-i suhteline läbilaskevõime on QS-i poolt ajaühikus teenindatavate rakenduste keskmise arvu ja sama aja jooksul saadud päringute keskmise arvu suhe.

1.3. SMO tööperioodi keskmine kestus.

1.4. QS-i kasutusmäär on keskmine ajaosa, mille jooksul QS on hõivatud taotluste teenindamisega.

2. Rakendusteenuse kvaliteedi näitajad:

2.1. Keskmine ooteaeg taotlusele järjekorras.

2.2. Taotluse keskmine ühises turukorralduses viibimise aeg.

2.3. Tõenäosus, et taotlus lükatakse teenusesse ilma ootamata.

2.4. Tõenäosus, et laekunud taotlus võetakse kohe kättetoimetamiseks vastu.

2.5. Järjekorras avalduse ooteaja jaotumise seadus.

2.6. QS-is rakendusele kulutatud aja jaotusseadus.

2.7. Keskmine taotluste arv järjekorras.

2.8. Keskmine taotluste arv QS-is jne.

3. Paari "SMO - tarbija" jõudlusnäitajad, kus "tarbija" tähendab kogu rakenduste komplekti või mõnda nende allikat (näiteks QS-i keskmine sissetulek ajaühiku kohta jne).

QS-is genereeritakse rakenduste voo juhuslikkus ja nende teenuse kestus juhuslik protsess. Sest ajahetked T i ja taotluste vastuvõtmise ajavahemikud T, teenindustoimingute kestus T obs, seistes järjekorras T och, järjekorra pikkus l och on juhuslikud muutujad, siis on järjekorrasüsteemide oleku tunnused tõenäosuslikud. Seetõttu on järjekorra teooria ülesannete lahendamiseks vaja uurida seda juhuslikku protsessi, s.o. ehitada ja analüüsida seda matemaatiline mudel.

QS-i toimimise matemaatiline uurimine on oluliselt lihtsustatud, kui selles toimuv juhuslik protsess on olemas Markovian. Et juhuslik protsess oleks Markovilik, on vajalik ja piisav, et kõik sündmuste vood, mille mõjul süsteem siirdub olekust olekusse, oleksid (kõige lihtsamad) Poisson.

Kõige lihtsamal voolul on kolm peamist omadust: tavaline, paigal ja ilma järelmõjuta.

Tavaline vool tähendab 2 või enama nõude samaaegse vastuvõtmise praktilist võimatust. Näiteks tõenäosus, et iseteeninduspoes mitu kassaaparaati korraga rikki läheb, on üsna väike.

Statsionaarne on voog, mille matemaatiline ootus süsteemi sisenevate nõuete arvu kohta ajaühikus (tähistame λ ) aja jooksul ei muutu. Seega tõenäosus, et teatud aja jooksul süsteemi siseneb teatud arv nõudeid ?T sõltub selle väärtusest ja ei sõltu selle viite lähtepunktist ajateljel.

Ei mingit järelmõju tähendab, et süsteemi saabunud nõuete arv enne hetke T, ei määra, mitu päringut aja jooksul süsteemi siseneb (T + ?T). Näiteks kui sisse kassaaparaat hetkel on paus kassa lint ja selle likvideerib kassapidaja, see ei mõjuta järgmisel hetkel selles kassas uue pausi tekkimise võimalust ja veel enam teiste kassade katkemise tõenäosust.

Lihtsaima voo korral järgib nõuete süsteemi laekumise sagedus Poissoni seadusele, st aja jooksul saabumise tõenäosusele T sile k nõuded on antud valemiga

kus λ — rakenduse voolu intensiivsus, st QS-i saabunud taotluste keskmine arv ajaühiku kohta,

kus τ - kahe naaberrakenduse vahelise ajaintervalli keskmine väärtus.

Sellise päringute voo korral jaotatakse aeg kahe naaberpäringu vahel eksponentsiaalselt tõenäosustihedusega

Juhuslikku ooteaega teenuse algusjärjekorras võib pidada ka eksponentsiaalselt jaotatuks:

kus ν — järjekorra liikluse intensiivsus, st keskmine teenusesse saabunud taotluste arv ajaühiku kohta,

kus T och on keskmine ooteaeg järjekorras.

Päringute väljundvoog on seotud teenuse vooga kanalis, kus teenuse kestus T obs on juhuslik suurus ja paljudel juhtudel järgib tihedusega eksponentsiaalse jaotuse seadust

kus μ — teenuse voolukiirus, st keskmine taotluste arv ajaühikus,

QS-i oluline omadus, mis ühendab näitajaid λ ja μ , on koormuse intensiivsus, mis näitab kindlaksmääratud rakenduste voogude koordineerimise astet:

Loetletud näitajad k, τ, λ, l och, T och, ν, T obs, μ, ρ, Р k on QS-i puhul kõige levinumad.

Järjekorravõrk (QN) on võrk, mis teenindab sissetulevaid päringuid. Nõuete hooldust QS-is teostavad teenindusseadmed. Klassikaline QS sisaldab ühte kuni lõpmatu arvu seadmeid. Sõltuvalt sellest, kas sissetulevatel päringutel on võimalik teenuse algust oodata, jaotatakse QS-id: kadudega süsteemid, milles lähevad kaotsi päringud, mis ei leidnud saabumise hetkel ühtegi vaba serverit; ootamisega süsteemid, milles sissetulevate päringute puhverdamiseks on olemas lõpmatu võimsusega draiv, kusjuures sel juhul moodustavad ootel olevad päringud järjekorra; süsteemid, mille draiv on piiratud (ootamine ja piirangud), milles järjekorra pikkus ei saa ületada sõita; sellisel juhul läheb ülerahvastatud QS-i (vabu kohti ootamiseks pole) saabunud nõue kaotatud.

Iga QS on loodud teenindama (käivitama) teatud rakenduste voogu (või nõudeid), mis süsteemi sisenevad enamasti mitte regulaarselt, vaid juhuslikel aegadel. Ka taotluste teenindamine ei kesta üldiselt mitte konstantset, ette teada, vaid juhuslikku aega. Pärast päringu teenindamist kanal vabastatakse ja on järgmise päringu vastuvõtmiseks valmis. Voo juhuslik iseloom ja nende teenindamise aeg põhjustavad QS-i ebaühtlase töökoormuse: teatud ajavahemike järel võivad QS-i sisendisse koguneda esitamata päringud (need satuvad järjekorda või jätavad QS-i teenindamata), samas kui muudel perioodidel, kui QS-i sisendis on vabad kanalid, taotlusi ei esitata, mis toob kaasa QS-i alakoormamise, st. jõudeolevatele kanalitele.

Seega saab mis tahes QS-is eristada järgmisi põhielemente:

) sissetulev rakenduste voog;

) pööre;

) teeninduskanalid;

) teenindatavate päringute väljuv voog.

Igal QS-il, olenevalt selle parameetritest: rakenduste voo olemusest, teeninduskanalite arvust ja nende jõudlusest, samuti töö korraldamise reeglitest, on teatav toimimise efektiivsus (võimsus), mis võimaldab rohkem või rohkem vähem edukalt toime tulla rakenduste vooluga.

Järjekorrateooria õppeaineks on QS.

Järjekorrateooria eesmärk on välja töötada soovitused QS-i ratsionaalseks ehitamiseks, nende töö ratsionaalseks korraldamiseks ja rakenduste voo reguleerimiseks, et tagada QS-i kõrge efektiivsus.

Selle eesmärgi saavutamiseks on püstitatud järjekorra teooria ülesanded, mis seisnevad QS-i toimimise efektiivsuse sõltuvuste väljaselgitamises selle organisatsioonist (parameetritest): rakenduste voo olemus, kanalite arv ja nende jõudlust ja QS-i reegleid.

Päringute voo juhuslik iseloom ja nende teenuse kestus loovad QS-is juhusliku protsessi.

Definitsioon: juhuslik protsess (või juhuslik funktsioon) on vastavus, milles argumendi iga väärtus (in sel juhul- hetk katse ajaintervallist) määratakse juhuslikuks muutujaks (antud juhul QS-i olekuks). järjekorras seismine

Eelmises loengus vaagituna toimub järjekorrasüsteemides (QS) diskreetsete olekute ja pideva ajaga Markovi juhuslik protsess.

Järjekorrasüsteemid - need on süsteemid, milles teenusepäringuid võetakse vastu juhuslikel aegadel, samal ajal kui vastuvõetud päringuid teenindatakse süsteemi käsutuses olevate teenusekanalite kaudu.

Järjekorrasüsteemide näited on järgmised:

• arveldus- ja sularahasõlmed pankades, ettevõtetes;
• personaalarvutid, teenindavad sissetulevaid rakendusi või nõudeid teatud probleemide lahendamiseks;
• jaamad Hooldus autod; Bensiinijaam;
• audiitorfirmad;
• ettevõtete jooksvate aruannete vastuvõtmise ja kontrollimisega tegelevad maksuinspektsiooni osakonnad;
• telefonikeskjaamad jne.

	Sõlmed	Nõuded
Haigla	Tellijad	Patsiendid
Tootmine
Lennujaam	Raja väljapääsud Registreerimispunktid	Reisijad

Vaatleme QS-i töö skeemi (joonis 1). Süsteem koosneb päringu generaatorist, dispetšer- ja teenindussõlmest, rikete arvestussõlmest (terminaator, päringu hävitaja). Teenindussõlmel võib üldjuhul olla mitu teeninduskanalit.

Riis. üks

1. Rakenduste generaator – rakendusi genereeriv objekt: tänav, paigaldatud üksustega töökoda. Sisend on rakenduste voog(klientide voog kauplusesse, katkiste sõlmede (autod, tööpingid) vool remondiks, garderoobi külastajate voog, autode vool tanklatesse jne).
2. Dispetšer – inimene või seade, mis teab, mida piletiga peale hakata. Sõlm, mis reguleerib ja suunab päringuid teeninduskanalitesse. Dispetšer:

• võtab taotlusi vastu;
• moodustab järjekorra, kui kõik kanalid on hõivatud;
• suunab need teeninduskanalitesse, kui neid on;
• keeldub taotlustest (erinevatel põhjustel);
• saab teenindussõlmelt teavet tasuta kanalite kohta;
• jälgib süsteemi aega.

1. Pöörake - nõuda akumulaatorit. Järjekorda ei pruugi olla.
2. Teenindussõlm koosneb piiratud arvust teeninduskanalitest. Igal kanalil on 3 olekut: vaba, hõivatud, jõude. Kui kõik kanalid on hõivatud, saate välja mõelda strateegia, kellele rakendus edastada.
3. Keeldumine teenusest, kui kõik kanalid on hõivatud (mõned neist ei pruugi töötada).

Lisaks nendele QS-i põhielementidele eristavad mõned allikad ka järgmisi komponente:

terminaator - tehingute hävitaja;

ladu - ressursside ja valmistoodete ladustamine;

Kontrollima raamatupidamine- teha "postitus" tüüpi toiminguid;

manager – ressursside juht;

Ühise turukorralduse klassifikatsioon

Esimene jaotus (järjekordade olemasolu järgi):

• Ühine turukorraldus tõrgetega;
• Ühine turukorraldus järjekorraga.

AT Ühine turukorraldus tõrgetega päring, mis saabub hetkel, kui kõik kanalid on hõivatud, lükatakse tagasi, lahkub QS-ist ja seda enam ei teenindata.

AT Ühine turukorraldus järjekorraga rakendus, mis saabub ajal, mil kõik kanalid on hõivatud, ei lahku, vaid seab järjekorda ja ootab võimalust teenindada.

QS järjekordadega alajaotatud erinevad tüübid sõltuvalt sellest, kuidas järjekord on korraldatud - piiratud või piiramata. Piirangud võivad puudutada nii järjekorra pikkust kui ka ooteaega, "teenindusdistsipliini".

Seega võetakse arvesse näiteks järgmisi QS-i:

• QS kannatamatute päringutega (järjekorra pikkus ja teenindusaeg on piiratud);
• QS prioriteediteenusega ehk mõnda rakendust serveeritakse järjekorraväliselt jne.

Järjekorrapiirangu tüüpe saab kombineerida.

Teine klassifikatsioon jagab ühise turukorralduse taotluste allika järgi. Rakendusi (nõudeid) saab genereerida süsteem ise või mõni süsteemist sõltumatult eksisteeriv väliskeskkond.

Loomulikult sõltub süsteemi enda genereeritud päringute voog süsteemist ja selle olekust.

Lisaks jagunevad SMOd avatud CMO ja suletud SMO.

Avatud QS-is ei sõltu rakenduste voo omadused QS-i enda olekust (kui palju kanaleid on hõivatud). Suletud QS-is sõltuvad need. Näiteks kui üks töötaja teenindab aeg-ajalt gruppi masinaid, mis vajavad aeg-ajalt reguleerimist, siis masinatest lähtuvate "nõuete" voo intensiivsus sõltub sellest, kui paljud neist on juba korras ja ootavad reguleerimist.

Näide suletud süsteemist: palga väljastamine ettevõtte kassapidaja poolt.

Kanalite arvu järgi jagunevad QS-id järgmisteks osadeks:

• ühe kanaliga;
• mitme kanaliga.

Järjekorrasüsteemi omadused

Mis tahes järjekorrasüsteemi peamised omadused on järgmised:

• sissetulevate nõuete või teenusepäringute sisendvoog;
• järjekorra distsipliin;
• teenindusmehhanism.

Nõuded sisendvoog

Sisendvoo kirjeldamiseks peate määrama tõenäosusseadus, mis määrab teenusenõuete kättesaamise hetkede järjestuse, ja märkige igas tavakviitungis selliste nõuete arv. Sel juhul toimivad nad reeglina mõistega "nõuete laekumise hetkede tõenäosuslik jaotus". Siin saate käituda nagu üksik- ja rühmanõuded (selliste nõuete arv igas järjestikuses kviitungis). Viimasel juhul räägime tavaliselt paralleelrühmateenusega järjekorrasüsteemist.

A i– nõuete vaheline saabumisaeg – sõltumatud identselt jaotatud juhuslikud suurused;

E(A) on keskmine (MO) saabumisaeg;

λ=1/E(A)- nõuete laekumise intensiivsus;

Sisendvoo omadused:

1. Tõenäosusseadus, mis määrab teenusenõuete laekumise hetkede järjestuse.
2. Päringute arv iga järgmise saabumise korral multiedastusvoogude jaoks.

Järjekorra distsipliin

Pöörake - nõuete kogum, mis ootab hooldust.

Järjekorral on nimi.

Järjekorra distsipliin määrab põhimõtte, mille järgi teenindussüsteemi sisendisse saabuvad päringud seotakse järjekorrast teenindusprotseduuriga. Kõige sagedamini kasutatavad järjekorrad on määratletud järgmiste reeglitega.

• kes ees – see mees;

esimene sisse esimene välja (FIFO)

kõige levinum järjekorra tüüp.

Milline andmestruktuur sobib sellise järjekorra kirjeldamiseks? Massiiv on halb (piiratud). Võite kasutada LIST-struktuuri.

Nimekirjal on algus ja lõpp. Nimekiri koosneb kirjetest. Kirje on loendilahter. Rakendus jõuab loendi lõppu ja valitakse teenuseks loendi algusest. Kirje koosneb rakenduse kirjeldusest ja lingist (indeks selle kohta, kes on selle taga). Lisaks, kui järjekorras on ajalimiit, siis tuleb ka tähtaeg täpsustada.

Teie kui programmeerijad peaksite suutma teha loendeid kahepoolseid, ühepoolseid.

Toimingute loend:

• sisestage sabasse;
• võtta algusest peale;
• eemaldage loendist pärast aegumist.
• viimane tuli, see mees LIFO (kassetiklamber, tupik sees raudteejaam, läks pakitud autosse).

Struktuur, mida nimetatakse STACKiks. Saab kirjeldada massiivi või loendi struktuuriga;

• rakenduste juhuslik valik;
• taotluste valik prioriteetsuse kriteeriumi alusel.

Iga taotlust iseloomustab muuhulgas prioriteeditase ja see paigutatakse saabumisel mitte järjekorra lõppu, vaid selle prioriteetide rühma lõppu. Dispetšer sorteerib prioriteedi järgi.

Järjekorra omadused

• piirangooteaeg teenindamise hetk (seal on järjekord piiratud aeg teenus ootab, mis on seotud mõistega "lubatav järjekorra pikkus");
• järjekorra pikkus.

Teenindusmehhanism

Teenindusmehhanism selle määravad teenusprotseduuri enda omadused ja teenindussüsteemi struktuur. Hooldusprotseduurid hõlmavad järgmist:

• teeninduskanalite arv ( N);
• teenindamisprotseduuri kestus (nõuete teenindamise aja tõenäosuslik jaotus);
• iga sellise menetluse rakendamise tulemusena täidetud nõuete arv (rühmataotluste puhul);
• teenindava kanali rikke tõenäosus;
• teenindussüsteemi struktuur.

Teenindusprotseduuri omaduste analüütiliseks kirjeldamiseks kasutatakse mõistet "nõuete teenindamise aja tõenäosuslik jaotus".

Si- teenindusaeg i th nõue;

E(S)– keskmine teenindusaeg;

μ=1/E(S)- teenindusnõuete täitmise kiirus.

Tuleb märkida, et rakenduse teenindamise aeg sõltub rakenduse enda olemusest või kliendi nõudmistest ning teenindussüsteemi olekust ja võimalustest. Mõnel juhul tuleb arvestada ka teeninduskanali rikke tõenäosus pärast teatud piiratud ajavahemikku. Seda omadust saab modelleerida QS-i sisenevate rikete voona, millel on kõigi teiste päringute ees prioriteet.

QS-i kasutustegur

Nμ – teenindusmäär süsteemis, kui kõik teenindusseadmed on hõivatud.

ρ=λ/( Nμ) nimetatakse QS-i kasutustegur , näitab, kui palju süsteemiressursse kasutatakse.

Teenindussüsteemi struktuur

Teenindussüsteemi struktuuri määrab teeninduskanalite (mehhanismid, seadmed jne) arv ja vastastikune paigutus. Esiteks tuleb rõhutada, et teenindussüsteemil võib olla mitte üks teeninduskanal, vaid mitu; seda tüüpi süsteem suudab korraga täita mitut nõuet. Sel juhul pakuvad kõik teeninduskanalid samu teenuseid ja seetõttu võib väita, et see on olemas paralleelteenus .

Näide. Kaupluses kassaaparaadid.

Teenindussüsteem võib koosneda mitmest erinevat tüüpi teeninduskanalist, mille kaudu peab läbima iga teenindatav nõue, st teenindussüsteemis nõuete hooldusprotseduure rakendatakse järjestikku . Teenindusmehhanism määratleb väljuva (teenitava) päringute voo omadused.

Näide. Arstlik komisjon.

Kombineeritud teenus - hoiuste teenindamine hoiupangas: kõigepealt kontrolör, seejärel kassapidaja. Reeglina 2 kontrollerit kassa kohta.

Niisiis, funktsionaalsust mis tahes järjekorrasüsteemi määravad järgmised peamised tegurid :

• teenusepäringute laekumise hetkede tõenäosuslik jaotus (üksik või rühm);
• nõuded allika võimsus;
• teenistusaja kestuse tõenäosuslik jaotus;
• teenindussüsteemi konfiguratsioon (paralleel-, jada- või paralleeljadateenus);
• teenindavate kanalite arv ja jõudlus;
• järjekorra distsipliin.

QS-i toimimise tõhususe peamised kriteeriumid

Nagu järjekorrasüsteemide toimimise efektiivsuse peamised kriteeriumid Sõltuvalt lahendatava probleemi olemusest võib olla:

• vastuvõetud taotluse kohese kättetoimetamise tõenäosus (P teenus =K obs /K post);
• laekunud avalduse kättetoimetamisest keeldumise tõenäosus (P otk =K otk /K post);

On ilmne, et R obl + P otk =1.

Vood, viivitused, teenindus. Pollacek-Khinchin valem

Viivitus – üks QS-i teenuse kriteeriumidest, aeg, mis kulub päringule teenuse ootele.

D i– päringujärjekorras viibimine i;

W i \u003d D i + S i– nõudesüsteemis veedetud aeg i.

(tõenäosusega 1) on päringu määratud keskmine viivitus järjekorras;

(tõenäosusega 1) on püsiseisundi keskmine aeg, mille nõue QS-is kulutab (ootamine).

Q(t) - korraga järjekorras olevate päringute arv t;

L(t)– klientide arv süsteemis korraga t(Q(t) pluss sel ajal kasutusel olevate nõuete arv t.

Seejärel eksponendid (kui neid on)

(tõenäosusega 1) on püsiseisundi aeg-keskmine päringute arv järjekorras;

(tõenäosusega 1) on püsiseisundi ajakeskmine päringute arv süsteemis.

Pange tähele, et ρ<1 – обязательное условие существования d, w, Q ja L järjekorrasüsteemis.

Kui me mäletame, et ρ= λ/( Nμ), siis on selge, et kui päringute vastuvõtmise intensiivsus on suurem kui Nμ, siis ρ>1 ja on loomulik, et süsteem ei tule sellise rakenduste vooga toime ning seetõttu ei saa rääkida d, w, Q ja L.

Kõige üldisemad ja vajalikumad tulemused järjekorrasüsteemide jaoks hõlmavad säilivusvõrrandeid

Tuleb märkida, et ülaltoodud kriteeriume süsteemi toimivuse hindamiseks saab järjekorrasüsteemide jaoks analüütiliselt arvutada M/M/N(N>1), st Markovi kliendi- ja teenindusvoogudega süsteemid. Sest M/G/ l igasuguse levitamise jaoks G ja mõnede muude süsteemide jaoks. Üldiselt peab analüütilise lahenduse leidmiseks ajajaotus saabujate, teenindusaja jaotus või mõlemad olema eksponentsiaalne (või omamoodi k-ndat järku eksponentsiaalne Erlangi jaotus).

Lisaks võite rääkida ka sellistest omadustest nagu:

• süsteemi absoluutne läbilaskevõime – А=Р teenus *λ;
• süsteemi suhteline läbilaskevõime -

Veel üks huvitav (ja illustreeriv) näide analüütiline lahendus – järjekorrasüsteemi püsiseisundi keskmise järjekorra viivituse arvutamine M/G/ 1 vastavalt valemile:

.

Venemaal tuntakse seda valemit Pollaceki valemina. – Khinchin, välismaal on see valem seotud Rossi nimega.

Seega, kui E(S) Sellel on suurem väärtus, siis ülekoormus (antud juhul mõõdetuna kui d) on suurem; mida on oodata. Valem paljastab ka vähem ilmse fakti: ummikud suurenevad ka siis, kui teenindusaja jaotuse varieeruvus suureneb, isegi kui keskmine teenindusaeg jääb samaks. Intuitiivselt saab seda seletada järgmiselt: teenindusaja juhusliku suuruse dispersioon võib omandada suure väärtuse (kuna see peab olema positiivne), st ainuke teenindusseade on pikka aega hõivatud, mis toob kaasa tõusu järjekorras.

Järjekorrateooria teema eesmärk on luua seos järjekorrasüsteemi funktsionaalsust määravate tegurite ja selle toimimise tõhususe vahel. Enamasti on kõik järjekorrasüsteeme kirjeldavad parameetrid juhuslikud muutujad või funktsioonid, mistõttu neid süsteeme nimetatakse stohhastilisteks süsteemideks.

Rakenduste (nõuete) voo juhuslik iseloom, aga ka üldiselt teenuse kestus viib selleni, et järjekorrasüsteemis toimub juhuslik protsess. Juhusliku protsessi olemuse järgi eristatakse järjekorrasüsteemis (QS) esinevaid Markovi ja mitte-Markovi süsteemid . Markovi süsteemides on sissetulev päringute voog ja teenindatud päringute (nõuete) väljaminev voog Poisson. Poissoni vood muudavad järjekorrasüsteemi matemaatilise mudeli kirjeldamise ja koostamise lihtsaks. Nendel mudelitel on üsna lihtsad lahendused, nii et enamik järjekorrateooria tuntud rakendusi kasutab Markovi skeemi. Mitte-Markovi protsesside puhul muutuvad järjekorrasüsteemide uurimise probleemid palju keerulisemaks ja nõuavad statistilise modelleerimise, arvuliste meetodite kasutamist arvuti abil.

Järjekorravõrk on lõplike arvude kogum N teenindavad sõlmed, milles ringlevad päringud, mis liiguvad vastavalt marsruutimismaatriksile ühest sõlmest teise.

Sõlm on alati avatud QS (pealegi võib QS olla mis tahes klassist). Eraldi QS-id kuvavad reaalse süsteemi funktsionaalselt sõltumatuid osi, ühendused vahel QS - süsteemi struktuur ja nõuded, mis ringlevad QEMO-s, on materjalivoogude komponendid.

SeMOsid klassifitseeritakse mitme kriteeriumi järgi (joonis 2.5).

Võrku nimetatakse lineaarseks, kui päringuvoogude intensiivsused sõlmedes on omavahel seotud lineaarse sõltuvusega , kus on proportsionaalsuskoefitsient või allika suhtes.

Koefitsient (ülekandekoefitsient) iseloomustab aastal laekunud avalduste osakaalu j-th sõlm päringute allikast või päringu keskmine läbimiste arv selle sõlme kaudu võrgus viibimise ajal.

Kui päringuvoogude intensiivsused võrgu sõlmedes on omavahel seotud mittelineaarse seosega (näiteks ), siis nimetatakse võrku mittelineaarseks.

Võrk on alati lineaarne, kui päringud ei lähe kaduma ega paljune selles.

Riis. 2.5. Ühise turukorralduse klassifikatsioon

avatud võrk- see on nii avatud võrk, kust rakendused pärinevad väliskeskkond ja kust nad pärast väliskeskkonda teenindamist lahkuvad. Avatud ahelaga QEMO (OSMO) tunnuseks on ühe või mitme sõltumatu välise allika olemasolu, mis genereerivad võrku sisenevaid nõudeid, olenemata sellest, kui palju nõudeid võrgus juba on. Igal ajal võib RSEM-is olla suvaline arv rakendusi (0 kuni ).

AT suletud QEMO(ZSEMO) levitab kindlat arvu rakendusi ja sõltumatut välist allikat pole. Füüsikalistest kaalutlustest lähtuvalt valitakse ZSMO-s välja väline kaar, millele on märgitud pseudo-nullpunkt, mille suhtes saab mõõta ajalisi omadusi. Päringute arv suletud võrgus on konstantne.

Kombineeritud võrk on võrk, milles ringleb pidevalt teatud arv rakendusi ja seal on rakendusi, mis tulevad välistest sõltumatutest allikatest.

AT homogeenne võrgud levitavad sama klassi nõudeid. AT heterogeenne Võrgustikus võivad nõuded olla mitmest klassist. Rakendused kuuluvad erinevatesse klassidesse, kui need erinevad vähemalt ühe järgmistest atribuutidest:

– teenuse kestuse sõlmedes jaotamise seadus;

- prioriteedid;

– marsruudid (rakenduste liikumise teed võrgus).

AT eksponentsiaalne teenuse kestusega võrgud kõigis sõlmedes on jaotatud vastavalt eksponentsiaalseadusele ja avatud võrku sisenevad vood on kõige lihtsamad (Poisson). Kõigil muudel juhtudel on võrk mitteeksponentsiaalne.

Kui vähemalt üks sõlm pakub prioriteetset teenust, on see - prioriteet net. Prioriteet on funktsioon, mis määrab teenuse järjekorra. Kui päringuid sõlmedes teenindatakse saabumise järjekorras, kutsutakse selline võrk välja mitteprioriteetne.

Sellel viisil, eksponentsiaalne kutsume välja ühise turukorralduse, mis vastab järgmistele nõuetele:

on Poissoni sisend QEM-vood;

- kõik N Rakenduste QS teenindusajal on eksponentsiaalne tõenäosusjaotuse funktsioon, rakendusi teenindatakse saabumise järjekorras;

– rakenduse üleminek väljumisest i- sissepääsuni j Kolmas QS on sõltumatu juhuslik sündmus, millel on tõenäosus

QS-i visuaalseks esituseks kasutatakse graafikut, mille tipud (sõlmed) vastavad üksikutele QS-idele ja kaared näitavad sõlmede vahelisi seoseid.