Kursuse töö

"Järjekorrasüsteemi simulatsioon"

kursusel "Operatsiooniuuringud"

Sissejuhatus

Operatsiooniuuringutes kohtab sageli süsteeme, mis on mõeldud korduvkasutuseks sama tüüpi probleemide lahendamisel. Sel juhul tekkivaid protsesse nimetatakse teenindusprotsessideks ja süsteeme järjekorrasüsteemideks (QS). Iga QS koosneb teatud arvust teenindusüksustest (instrumendid, seadmed, punktid, jaamad), mida nimetatakse teeninduskanaliteks. Kanaliteks võivad olla sideliinid, tööpunktid, arvutid, müüjad jne. Kanalite arvu järgi jagunevad QS-id ühe- ja mitmekanalilisteks.

Tavaliselt jõuavad rakendused QS-i mitte regulaarselt, vaid juhuslikult, moodustades nn juhusliku rakenduste voo (nõuded). Ka rakenduste teenus jätkub mõnda aega juhuslikult. Rakenduste voo ja teenindusaja juhuslik iseloom toob kaasa asjaolu, et QS laaditakse ebaühtlaselt: mõnel ajaperioodil koguneb väga palju rakendusi (nad kas satuvad järjekorda või jätavad QS-i teenindamata), samal ajal kui mõnel ajaperioodil. perioodidel, mil QS töötab alakoormuse või tühikäiguga.

Järjekorrateooria aineks on matemaatiliste mudelite konstrueerimine, mis seovad QS etteantud töötingimused (kanalite arv, nende jõudlus, rakenduste voo iseloom jne) QS jõudlusnäitajatega, mis kirjeldavad. selle võimet tulla toime rakenduste vooluga. QS-i tulemusnäitajatena kasutatakse järgmisi näitajaid:

- süsteemi absoluutne läbilaskevõime ( AGA

K

- taotluse kättetoimetamisest keeldumise tõenäosus ();

k);

- keskmine taotluste arv järjekorras ();

QS jaguneb 2 põhitüüpi: tõrgetega QS ja ootamisega (järjekorraga) QS. Keeldumisega QS-is lükatakse tagasi päring, mis saabub ajal, mil kõik kanalid on hõivatud, lahkub QS-ist ega osale edasises teenindusprotsessis (näiteks telefonivestluse taotlus ajal, mil kõik kanalid on hõivatud hõivatud saab keeldumise ja jätab QS-i teenindamata) . Ootava QS-is ei lahku nõue, mis saabub ajal, mil kõik kanalid on hõivatud, vaid läheb teenuse saamiseks järjekorda.

Üks QS tulemusnäitajate arvutamise meetodeid on simulatsioonimeetod. Arvutisimulatsiooni modelleerimise praktiline kasutamine hõlmab sobiva matemaatilise mudeli konstrueerimist, mis võtab arvesse määramatuse tegureid, dünaamilisi omadusi ja kogu uuritava süsteemi elementide vaheliste seoste kompleksi. Süsteemi töö simulatsioonimodelleerimine algab mingi kindla algolekuga. Erinevate juhuslike sündmuste realiseerumise tõttu läheb süsteemi mudel järgmistel ajahetkedel oma teistesse võimalikesse olekutesse. See evolutsiooniline protsess kestab kuni planeerimisperioodi lõpuni, s.o. kuni simulatsiooni lõpuni.

1. Ühise turukorralduse peamised omadused ja nende tõhususe näitajad

1.1 Markovi stohhastilise protsessi kontseptsioon

Olgu mingi süsteem, mis aja jooksul suvaliselt oma olekut muudab. Sel juhul ütleme, et süsteemis toimub juhuslik protsess.

Protsessi nimetatakse diskreetsete olekutega protsessiks, kui selle olekuid saab eelnevalt loendada ja süsteemi üleminek ühest olekust teise toimub hüppeliselt. Protsessi nimetatakse pideva aja protsessiks, kui süsteemi üleminekud olekust olekusse toimuvad silmapilkselt.

QS-i tööprotsess on diskreetsete olekute ja pideva ajaga juhuslik protsess.

Juhuslikku protsessi nimetatakse Markovi või järelmõjuta juhuslikuks protsessiks, kui mingil ajahetkel sõltuvad protsessi tõenäosuslikud omadused tulevikus ainult selle hetkeseisust ega sõltu sellest, millal ja kuidas süsteem sellesse olekusse jõudis.

QS-i tööprotsesside analüüsimisel on mugav kasutada geomeetrilist skeemi - oleku graafik. Tavaliselt kujutatakse süsteemi olekuid ristkülikutega ja võimalikke üleminekuid olekust olekusse nooltega. Olekugraafiku näide on näidatud joonisel fig. üks.

Sündmuste voog on homogeensete sündmuste jada, mis järgneb juhuslikul ajal üksteise järel.

Voogu iseloomustab intensiivsus λ – sündmuste esinemissagedus või QS-i sisenevate sündmuste keskmine arv ajaühikus.

Sündmuste voogu nimetatakse regulaarseks, kui sündmused järgnevad üksteise järel kindlate ajavahemike järel.

Sündmuste voogu nimetatakse statsionaarseks, kui selle tõenäosuslikud omadused ei sõltu ajast. Eelkõige on statsionaarse voolu intensiivsus konstantne väärtus: .

Sündmuste voogu nimetatakse tavaliseks, kui tõenäosus, et kaks või enam sündmust tabavad väikest ajavahemikku, on väike võrreldes ühe sündmuse tabamise tõenäosusega, st kui sündmused esinevad selles ükshaaval, mitte rühmadena.

Sündmuste voogu nimetatakse järelmõjuta vooks, kui mis tahes kahe mittekattuva ajaintervalli puhul ja ühele neist langevate sündmuste arv ei sõltu teistele langevate sündmuste arvust.

Sündmuste voogu nimetatakse lihtsaimaks (või statsionaarseks Poissoniks), kui see on ühtaegu statsionaarne, tavaline ja sellel pole järelmõju.

1.2 Kolmogorovi võrrandid

Kõik üleminekud süsteemis olekust olekusse toimuvad mingi sündmuste voo käigus. Olgu süsteem mingis olekus , millest on võimalik üleminek olekusse, siis võime eeldada, et süsteemi mõjutab kõige lihtsam voog intensiivsusega , viies selle olekust üle . Niipea, kui toimub lõime esimene sündmus, toimub selle üleminek. Selguse huvides on olekugraafikul iga üleminekule vastav nool tähistatud intensiivsusega . Selline märgistatud olekugraafik võimaldab koostada protsessi matemaatilise mudeli, s.t. leida kõigi olekute tõenäosused aja funktsioonina. Nende jaoks koostatakse diferentsiaalvõrrandid, mida nimetatakse Kolmogorovi võrranditeks.

Kolmogorovi võrrandite koostamise reegel: Iga võrrandi vasakul küljel on antud oleku tõenäosuse aja tuletis. Paremal pool on kõigi olekute korrutiste summa, millest on võimalik üleminek antud olekusse, vastavate sündmuste voogude intensiivsusega miinus kõigi süsteemi sellest olekust välja viivate voogude summaarne intensiivsus, korrutatuna selle oleku tõenäosusega.

Näiteks olekugraafiku jaoks, mis on näidatud joonisel fig. 1, Kolmogorovi võrrandid on kujul:

Sest süsteemi paremal küljel sisestatakse iga liige 1 kord märgiga ja 1 kord märgiga , seejärel kõik võrrandid liites saame, et

,

,

Seetõttu võib süsteemi ühe võrrandi kõrvale jätta ja asendada võrrandiga (1.2.1).

Konkreetse lahenduse saamiseks on vaja teada algtingimusi, s.t. tõenäosused esialgsel ajahetkel.

1.3 QS lõplikud tõenäosused ja olekugraafik

Süsteemis toimuvate protsesside piisavalt pikaks ajaks (at ) saab määrata ajast mittesõltuvate olekute tõenäosused, mida nimetatakse lõplikeks tõenäosusteks, s.o. süsteem on statsionaarses režiimis. Kui süsteemi olekute arv on lõplik ja igast neist on lõpliku arvu sammudega võimalik minna mis tahes teise olekusse, siis on olemas lõplikud tõenäosused, s.t.

Lõplike tõenäosuste tähendus on see, et need on võrdsed keskmise suhtelise ajaga, mille süsteem antud olekus kulutab.

Sest statsionaarses olekus on aja tuletised võrdsed nulliga, siis saadakse lõpptõenäosuste võrrandid Kolmogorovi võrranditest, võrdsustades nende parempoolsed küljed nulliga.

Järjekorrasüsteemide mudelites kasutatavaid olekugraafikuid nimetatakse surma ja aretuse skeemiks. See nimi on tingitud asjaolust, et seda skeemi kasutatakse populatsiooni suuruse uurimisega seotud bioloogilistes probleemides. Selle eripära seisneb selles, et süsteemi kõiki olekuid saab esitada ahelana, milles iga olek on seotud eelneva ja järgnevaga (joonis 2).

Riis. 2. QS mudelite olekute graafik

Oletame, et kõik vood, mis viivad süsteemi ühest olekust teise, on kõige lihtsamad. Vastavalt joonisel fig. 2, koostame süsteemi lõplike tõenäosuste võrrandid. Need näevad välja sellised:

Süsteem on saadud ( n +1) võrrand, mis lahendatakse eliminatsioonimeetodiga. See meetod seisneb selles, et järjestikku kõik süsteemi tõenäosused väljendatakse tõenäosuse kaudu.

,

.

Asendades need avaldised süsteemi viimasesse võrrandisse, leiame , siis leiame ülejäänud QS olekute tõenäosused.

1.4 QS tulemusnäitajad

QS-modelleerimise eesmärk on arvutada süsteemi jõudlust selle omaduste kaudu. QS-i tulemusnäitajatena kasutatakse järgmisi näitajaid:

on süsteemi absoluutne võimsus ( AGA), st. keskmine kättetoimetatud taotluste arv ajaühikus;

on suhteline läbilaskevõime ( K), st. süsteemi teenindatavate saabunud päringute keskmine osakaal;

on ebaõnnestumise tõenäosus (), st. tõenäosus, et rakendus jätab QS-i teenindamata;

on hõivatud kanalite keskmine arv ( k);

- keskmine taotluste arv QS-is ();

– taotluse keskmine süsteemis viibimise aeg ();

- keskmine taotluste arv järjekorras () - järjekorra pikkus;

- keskmine rakenduste arv süsteemis ();

- keskmine aeg, mil rakendus on järjekorras ();

- rakenduse keskmine süsteemis viibimise aeg ()

– kanali koormuse aste (), st. tõenäosus, et kanal on hõivatud;

on keskmine kättetoimetatud taotluste arv ajaühiku kohta;

– keskmine teeninduse ooteaeg;

– tõenäosus, et järjekorras olevate rakenduste arv ületab teatud väärtuse jne.

On tõestatud, et mis tahes rakenduste voo, mis tahes teenindusaja jaotuse, mis tahes teenindusdistsipliini puhul on rakenduse keskmine viibimisaeg süsteemis (järjekorras) võrdne keskmise rakenduste arvuga süsteemis. (järjekord) jagatud rakenduste voo intensiivsusega, s.o.

(1.4.1)

Valemeid (1.4.1) ja (1.4.2) nimetatakse väikesteks valemiteks. Need tulenevad asjaolust, et piiravas statsionaarses režiimis võrdub keskmine süsteemi saabuvate nõuete arv sellest väljuvate nõuete keskmise arvuga, s.o. mõlemad rakenduste vood on sama intensiivsusega.

Tulemusnäitajate arvutamise valemid on toodud tabelis. üks.

Tabel 1.

Näitajad	Ühe kanaliga QS koos piiratud järjekord	Mitmekanaliline QS koos piiratud järjekord
Lõplik tõenäosused
Tõenäosus
Absoluutne läbilaskevõime võime
Suhteline läbilaskevõime võime
Keskmine taotluste arv per
Keskmine taotluste arv alla teenust
Keskmine rakenduste arv süsteemis

1.5 Simulatsiooni põhimõisted

Simulatsioonimodelleerimise põhieesmärk on reprodutseerida uuritava süsteemi käitumist selle elementide olulisemate seoste analüüsi põhjal.

Arvutisimulatsiooni tuleks käsitleda staatilise katsena.

Juhuslike suuruste funktsioonide teooriast on teada, et juhusliku suuruse modelleerimiseks mis tahes pideva ja monotoonselt kasvava jaotusfunktsiooniga piisab, kui on võimalik modelleerida juhuslikku suurust, mis on ühtlaselt jaotunud intervallil . Saanud juhusliku suuruse realisatsiooni, võib leida juhusliku suuruse vastava realisatsiooni, kuna need on seotud võrdsusega

Oletame, et mõnes järjekorrasüsteemis jaotatakse ühe kliendi teenindusaeg eksponentsiaalseaduse järgi parameetriga , kus on teenusevoo intensiivsus. Siis on teenindusaja jaotuse funktsioonil vorm

Olgu see segmendil ühtlaselt jaotatud juhusliku suuruse realisatsioon ja olgu ühe päringu teenindamise juhusliku aja vastav realisatsioon. Seejärel vastavalt (1.5.1)

1.6 Simulatsioonimudelite ehitamine

Iga simulatsioonimudeli loomise esimene etapp on reaalse elu süsteemi kirjeldamise etapp põhisündmuste tunnuste järgi. Need sündmused on reeglina seotud uuritava süsteemi üleminekutega ühest võimalikust olekust teise ja on määratud ajateljel olevate punktidena. Modelleerimise põhieesmärgi saavutamiseks piisab süsteemi jälgimisest põhisündmuste elluviimise hetkedel.

Vaatleme ühe kanaliga järjekorrasüsteemi näidet. Sellise süsteemi simulatsioonimodelleerimise eesmärk on määrata hinnangud selle põhiomaduste kohta, nagu rakenduse keskmine järjekorras viibimise aeg, järjekorra keskmine pikkus ja süsteemi seisakute osakaal.

Järjekorraprotsessi iseärasused võivad oma väärtusi muuta kas uue teenusetaotluse saamise hetkel või järgmise päringu teenindamise lõpus. QS saab hakata koheselt teenindama järgmist päringut (teeninduskanal on vaba), kuid pole välistatud vajadus oodata, millal päring peab järjekorras koha sisse võtma (QS järjekorraga, teeninduskanal on hõivatud). Pärast järgmise päringu teenindamise lõpetamist saab QS kohe hakata teenindama järgmist päringut, kui see on olemas, kuid võib ka jõude seista, kui seda pole. Vajalikku infot saab, jälgides erinevaid olukordi, mis põhisündmuste elluviimisel ette tulevad. Seega, kui nõue saabub QS-i hõivatud teeninduskanaliga järjekorraga, suureneb järjekorra pikkus 1 võrra. Samamoodi väheneb järjekorra pikkus 1 võrra, kui järgmise nõude teenindamine on lõpetatud ja nõuete kogum on järjekorras. ei ole tühi.

Mis tahes simulatsioonimudeli tööks on vaja valida ajaühik. Olenevalt modelleeritava süsteemi olemusest võib selline ühik olla mikrosekund, tund, aasta jne.

Kuna arvutisimulatsioon on oma olemuselt arvutuslik eksperiment, peavad selle vaadeldud tulemused agregaadis olema juhusliku valimi realiseerimise omadustega. Ainult sel juhul on tagatud simuleeritud süsteemi õige statistiline tõlgendus.

Arvutisimulatsiooni modelleerimisel on põhihuvi pärast uuritava süsteemi statsionaarsesse töörežiimi jõudmist saadud vaatlused, kuna sel juhul valimi dispersioon järsult väheneb.

Aeg, mis kulub süsteemi jõudmiseks statsionaarsesse töörežiimi, määratakse selle parameetrite väärtuste ja algoleku järgi.

Kuna peamine eesmärk on saada vaatlusandmeid võimalikult väikese veaga, siis selle eesmärgi saavutamiseks saate:

1) pikendada uuritava süsteemi toimimisprotsessi simulatsioonimodelleerimise kestust. Sel juhul ei suurene mitte ainult tõenäosus, et süsteem jõuab statsionaarsesse töörežiimi, vaid suureneb ka kasutatavate pseudojuhuslike arvude arv, mis samuti mõjutab positiivselt saadud tulemuste kvaliteeti.

2) määratud ajaks T simulatsiooni modelleerimine N arvutuslikud katsed, mida nimetatakse ka mudelikäibeteks, erinevate pseudojuhuslike arvude komplektidega, millest igaüks annab ühe vaatluse. Kõik käitused algavad simuleeritud süsteemi sama algolekuga, kuid kasutades erinevaid pseudojuhuslike arvude komplekte. Selle meetodi eeliseks on saadud vaatluste sõltumatus, süsteemi efektiivsuse näitajad. Kui number N Kui mudel on piisavalt suur, siis määratakse parameetri sümmeetrilise usaldusvahemiku piirid järgmiselt:

, , st. , kus

korrigeeritud dispersioon, ,

N– programmi käitamiste arv, – töökindlus, .

2. QS analüütiline modelleerimine

2.1 Süsteemi olekugraafik ja Kolmogorovi võrrand

Vaatleme kahe kanaliga järjekorrasüsteemi (n = 2), mille piiratud järjekord on võrdne kuuega (m = 4). QS võtab vastu lihtsaima rakenduste voo keskmise intensiivsusega λ = 4,8 ja eksponentsiaalse ajajaotuse seadusega rakenduste saabumise vahel. Süsteemis teenindatavate päringute voog on lihtsaim, keskmise intensiivsusega μ = 2 ja teenindusaja jaotuse eksponentsiaalse seadusega.

Sellel süsteemil on 7 olekut, me tähistame neid:

S 0 - süsteem on tasuta, taotlusi pole;

S 1 - 1 teenusepäring, järjekord on tühi;

S 2 - 2 teenusetaotlust, järjekord on tühi;

S 3 - 2 teenindustaotlust, 1 päring järjekorras;

S 4 - 2 hooldustaotlust, 2 päringut järjekorras;

S 5 - 2 teenindustaotlust, 3 päringut järjekorras;

S 6 - 2 teenindustaotlust, 4 päringut järjekorras;

Tõenäosused, et süsteem siseneb olekutesse S 0, S 1, S 2, …, S 6, on vastavalt võrdsed Р 0, Р 1, Р 2, …, Р 6.

Järjekorrasüsteemi olekugraafik on surma ja paljunemise skeem. Süsteemi kõiki olekuid saab kujutada ahelana, milles iga olek on seotud eelmise ja järgmisega.

Riis. 3. Kahe kanaliga QS olekute graafik

Konstrueeritud graafiku jaoks kirjutame Kolmogorovi võrrandid:

Selle süsteemi lahendamiseks seadsime algtingimused:

Kolmogorovi võrrandisüsteemi (diferentsiaalvõrrandi süsteemi) lahendame numbrilise Euleri meetodil, kasutades tarkvarapaketti Maple 11 (vt lisa 1).

Euleri meetod

kus - meie puhul on need Kolmogorovi võrrandite õiged osad, n=6.

Valime aja sammu. Oletame, kus T on aeg, mis kulub süsteemil püsiolekuni jõudmiseks. Siit saame sammude arvu . Järjepidevalt N valemiga (1) arvutatuna saame süsteemi olekute tõenäosuste sõltuvused ajast, mis on näidatud joonisel fig. neli.

QS-i tõenäosuste väärtused on võrdsed:

Riis. 4. Süsteemi olekute tõenäosuste sõltuvused ajast

P0

P5

P4

P3

P2

P1

2.2 Süsteemi lõplikud tõenäosused

Piisavalt pika ajaga süsteemis toimuvate protsesside jaoks () saab määrata ajast mittesõltuvate olekute tõenäosused, mida nimetatakse lõplikeks tõenäosusteks, s.t. süsteem on statsionaarses režiimis. Kui süsteemi olekute arv on lõplik ja igast neist on võimalik lõpliku arvu sammudega üle minna mis tahes teise olekusse, siis on olemas lõplikud tõenäosused, s.t.

Sest statsionaarses olekus on aja tuletised võrdsed 0-ga, siis saadakse lõpptõenäosuste võrrandid Kolmogorovi võrranditest, võrdsustades parempoolsed küljed 0-ga. Kirjutame üles meie QS-i lõpptõenäosuste võrrandid.

Selle lineaarvõrrandi süsteemi lahendame Maple 11 tarkvarapaketi abil (vt lisa 1).

Saame süsteemi lõplikud tõenäosused:

Kolmogorovi võrrandite süsteemist saadud tõenäosuste võrdlemine lõpptõenäosustega näitab, et vead on võrdsed:

Need. piisavalt väike. See kinnitab saadud tulemuste õigsust.

2.3 Süsteemi jõudlusnäitajate arvutamine lõplike tõenäosuste järgi

Leiame järjekorrasüsteemi toimivusnäitajad.

Esiteks arvutame päringute voo vähendatud intensiivsuse:

1) Taotluse teenindamisest keeldumise tõenäosus, s.o. tõenäosus, et klient jätab süsteemi teenindamata Meie puhul keeldutakse kliendi teenindamisest, kui kõik 2 kanalit on hõivatud ja järjekord on maksimaalselt täis (st järjekorras 4 inimest), see vastab süsteemi olekule S 6 . Sest süsteemi olekusse S 6 sisenemise tõenäosus on P 6, siis

4) Keskmine järjekorra pikkus, s.o. keskmine päringute arv järjekorras on võrdne järjekorras olevate päringute arvu ja vastava oleku tõenäosuse korrutistega.

5) Keskmine aeg, mille rakendus järjekorras veedab, määratakse Little'i valemiga:

3. QS-i simulatsioonmodelleerimine

3.1 QS-i simulatsioonimeetodi algoritm (samm-sammult lähenemine)

Vaatleme kahe kanaliga järjekorrasüsteemi (n = 2), mille järjekorra maksimaalne pikkus on kuus (m = 4). QS võtab vastu lihtsaima rakenduste voo keskmise intensiivsusega λ = 4,8 ja eksponentsiaalse ajajaotuse seadusega rakenduste saabumise vahel. Süsteemis teenindatavate päringute voog on lihtsaim, keskmise intensiivsusega μ = 2 ja teenindusaja jaotuse eksponentsiaalse seadusega.

QS-i simuleerimiseks kasutame üht statistilise modelleerimise meetodit – simulatsioonimodelleerimist. Kasutame samm-sammult lähenemist. Selle lähenemisviisi olemus seisneb selles, et süsteemi olekuid võetakse arvesse järgmistel ajahetkedel, mille vaheline samm on piisavalt väike, et selle aja jooksul ei toimuks rohkem kui üks sündmus.

Valime aja sammu (). See peaks olema palju lühem kui taotluse keskmine kättesaamise aeg () ja keskmine kättetoimetamise aeg (), s.o.

Kus (3.1.1)

Tingimuse (3.1.1) põhjal määrame aja sammu .

Taotluse QS-i saabumise aeg ja selle teenindamise aeg on juhuslikud suurused. Seetõttu arvutatakse need QS-i simuleerimisel juhuslike arvude abil.

Kaaluge taotluse kättesaamist ühises turukorralduses. Tõenäosus, et tellimus saabub intervalli jooksul QS-i, on võrdne: . Loome juhusliku arvu , ja kui , siis loeme, et selles etapis esitatud päring sisenes süsteemi, kui , siis ei sisenenud.

Seda tehakse programmis isRequested () . Me võtame ajaintervalli konstantse ja võrduvad 0,0001-ga, siis on suhe 10000. Kui päring on vastu võetud, võtab see väärtuse "true", vastasel juhul on väärtus "false".

bool isRequested()

double r = R.NextDouble();

kui (r< (timeStep * lambda))

Vaatleme nüüd rakenduse teenust QS-is. Rakenduse teenindusaeg süsteemis määratakse avaldisega , kus on juhuslik arv. Programmis määratakse teenindusaeg funktsiooni abil GetServiceTime () .

double GetServiceTime()

double r = R.NextDouble();

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

Simulatsioonimeetodi algoritmi saab sõnastada järgmiselt. QS lahtiolekuajad ( T) on jagatud ajaastmeteks dt, igaüks neist sooritab rea toiminguid. Esiteks määratakse süsteemi olekud (hõivatud kanalid, järjekorra pikkus), seejärel funktsiooni abil isRequested () , tehakse kindlaks, kas taotlus saadi selles etapis või mitte.

Kui vastu võetakse ja samal ajal on tasuta kanaleid, kasutage funktsiooni GetServiceTime () genereerime taotluse töötlemise aja ja paneme selle teenust. Kui kõik kanalid on hõivatud ja järjekorra pikkus on alla 4, siis asetame päringu järjekorda; kui järjekorra pikkus on 4, siis keeldutakse päringu teenindamisest.

Juhul, kui selles etapis taotlust ei saadud ja teeninduskanal oli vaba, kontrollime järjekorda. Kui on, siis paneme palve teenindusjärjekorrast tasuta kanalisse. Pärast sooritatud toiminguid vähendatakse hõivatud kanalite teenindusaega sammu väärtuse võrra dt .

Pärast aja möödumist T, st pärast QS-i töö modelleerimist arvutatakse välja süsteemi jõudlusnäitajad ja tulemused kuvatakse ekraanile.

3.2 Programmi vooskeem

Kirjeldatud algoritmi rakendava programmi plokkskeem on näidatud joonisel fig. 5.

Riis. 5. Programmi vooskeem

Kirjutame mõned plokid üksikasjalikumalt.

Plokk 1. Parameetrite algväärtuste määramine.

juhuslik R; // Juhuslike arvude generaator

public uint maxQueueLength; // Järjekorra maksimaalne pikkus

public uint channelCount; // Kanalite arv süsteemis

avalik kahekordne lambda; // Sissetulevate päringute voo intensiivsus

avalik kahekordne mu; // Päringu teenindamise voo intensiivsus

avalik topeltaegStep; // Ajasamm

public double timeOfFinishProcessingReq; // Päringu teenindamise lõppaeg kõigis kanalites

public double timeInQueue; // QS-i järjekorraga olekutes veedetud aeg

avalik topelttöötlusTime; // Süsteemi tööaeg

public double totalProcessingTime; // Teenindustaotluste koguaeg

public uint requestEntryCount; // Saabunud taotluste arv

avalik uint tagasi lükatudRequestCount; // Tagasilükatud taotluste arv

avalik uint aktsepteeritudRequestCount; // Esitatud taotluste arv

uint queueLength; // Järjekorra pikkus //

QS-i olekuid kirjeldav tüüp

loend SysCondition(S0, S1, S2, S3, S4, S5, S6);

SysCondition currentSystemCondition; // Süsteemi praegune olek

Süsteemi olekute seadistamine. Toome selle 2-kanalilise süsteemi jaoks välja 7 erinevat olekut: S 0 , S 1 . S 6 . QS on olekus S 0, kui süsteem on vaba; S 1 – vähemalt üks kanal on vaba; olekus S 2, kui kõik kanalid on hõivatud ja järjekorras on ruumi; olekus S 6 on kõik kanalid hõivatud ja järjekord on saavutanud maksimaalse pikkuse (queueLength = 4).

Määrame funktsiooni abil süsteemi hetkeseisu Hangi tingimus()

SysCondition GetCondition()

SysCondition p_currentCondit = SysCondition.S0;

int busyChannelCount = 0;

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

if (TimeOfFinishProcessingReq[i] > 0)

busyChannelCount++;

p_currentCondit += k * (i + 1);

kui (busyChannelCount > 1)

(p_praegune seisukord++;)

return p_currentCondit + (int) QueueLength;

QS viibimisaja muutus osariikides, mille järjekorra pikkus on 1, 2, 3, 4. Seda rakendatakse järgmise koodiga:

if (queueLength > 0)

timeInQueue += timeStep;

if (queueLength > 1)

(timeInQueue += timeStep;)

On olemas selline toiming nagu teenusetaotluse esitamine tasuta kanalile. Kõiki kanaleid skannitakse alates esimesest, kui timeOfFinishProcessingReq tingimus on täidetud [ i ] <= 0 (kanal on tasuta), esitatakse sellele avaldus, s.o. päringu teenindamise lõpuaeg genereeritakse.

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

if (timeOfFinishProcessingReq[i]<= 0)

timeOfFinishProcessingReq[i] = GetServiceTime();

totalProcessingTime+= timeOfFinishProcessingReq[i];

Rakenduste teenindamine kanalites on modelleeritud koodiga:

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

if (TimeOfFinishProcessingReq[i] > 0)

timeOfFinishProcessingReq[i] -= timeStep;

Simulatsioonimeetodi algoritm on realiseeritud C# programmeerimiskeeles.

3.3 Arvutamine QS tulemusnäitajad, mis põhinevad selle simulatsiooni tulemused

Kõige olulisemad näitajad on:

1) Taotluse kättetoimetamisest keeldumise tõenäosus, s.o. tõenäosus, et klient jätab süsteemi teenindamata Meie puhul keelatakse klient teenuse osutamisest, kui kõik 2 kanalit on hõivatud ja järjekord on võimalikult täis (st järjekorras 4 inimest). Rikke tõenäosuse leidmiseks jagame QS-i järjekorra 4 olekus viibimise aja süsteemi koguajaga.

2) Suhteline läbilaskevõime on süsteemi poolt teenindatavate sissetulevate päringute keskmine osakaal.

3) Absoluutne läbilaskevõime on ajaühikus teenindatud rakenduste keskmine arv.

4) Järjekorra pikkus, st. keskmine taotluste arv järjekorras. Järjekorra pikkus võrdub järjekorras olevate inimeste arvu ja vastava oleku tõenäosuse korrutistega. Olekute tõenäosused leiame selles olekus QS-aja ja süsteemi kogu tööaja suhtena.

5) Keskmine aeg, mille rakendus järjekorras veedab, määratakse Little'i valemiga

6) Hõivatud kanalite keskmine arv on määratletud järgmiselt:

7) Nende rakenduste protsent, mille teenuse osutamisest keelduti, leitakse valemiga

8) Teenindatud päringute protsent leitakse valemiga

3.4 Tulemuste statistiline töötlemine ja nende võrdlemine analüütilise modelleerimise tulemustega

Sest jõudlusnäitajad saadakse QS modelleerimise tulemusena piiratud aja jooksul, need sisaldavad juhuslikku komponenti. Seetõttu on usaldusväärsemate tulemuste saamiseks vaja läbi viia nende statistiline töötlemine. Selleks hindame nende usaldusvahemikku programmi 20 käitamise tulemuste põhjal.

Väärtus jääb ebavõrdsuse korral usaldusvahemikku

, kus

matemaatiline ootus (keskmine väärtus), leitakse valemiga

korrigeeritud dispersioon,

,

N =20 - jooksude arv

- usaldusväärsus. Kell ja N =20 .

Programmi tulemus on näidatud joonisel fig. 6.

Riis. 6. Programmi tüüp

Erinevate modelleerimismeetoditega saadud tulemuste võrdlemise mugavuse huvides esitame need tabeli kujul.

Tabel 2.

Näitajad QS tõhusus	tulemused analüütiline modelleerimine	tulemused simulatsiooni modelleerimine (viimane samm)	Simulatsiooni tulemused
			Alumine joon usaldusisik intervall	Ülemine piir usaldusisik intervall
Ebaõnnestumise tõenäosus		0,174698253017626	0,158495148639101	0,246483801571923
Suhteline ribalaius		0,825301746982374	0,753516198428077	0,841504851360899
Absoluutne ribalaius		3,96144838551539	3,61687775245477	4,03922328653232
Keskmine järjekorra pikkus		1,68655313447018	1,62655862750852	2,10148609204869
Keskmine aeg, mille rakendus järjekorras veedab	0,4242558575	0,351365236347954	0,338866380730942	0,437809602510145
Keskmiselt hõivatud kanalid		1,9807241927577	1,80843887622738	2,01961164326616

Tabelist. Jooniselt 2 on näha, et QS-i analüütilise modelleerimisel saadud tulemused jäävad simulatsiooni tulemustest saadud usaldusvahemikku. See tähendab, et erinevate meetoditega saadud tulemused on järjepidevad.

Järeldus

Käesolevas töös käsitletakse peamisi QS-i modelleerimise ja nende tulemusnäitajate arvutamise meetodeid.

Kolmogorovi võrrandite abil viidi läbi kahe kanaliga QS, mille järjekorra pikkus on 4, modelleerimine ja leiti süsteemi olekute lõplikud tõenäosused. Arvutatakse selle tõhususe näitajad.

Sellise QS-i toimimise simulatsioon on läbi viidud. C# programmeerimiskeeles on koostatud programm, mis simuleerib selle tööd. Viidi läbi rida arvutusi, mille tulemuste põhjal leiti süsteemi efektiivsusnäitajate väärtused ja viidi läbi nende statistiline töötlemine.

Simulatsioonimodelleerimisel saadud tulemused on kooskõlas analüütilise modelleerimise tulemustega.

Kirjandus

1. Wentzel E.S. Operatsiooniuuringud. – M.: Bustard, 2004. – 208 lk.

2. Volkov I.K., Zagoruiko E.A. Operatsiooniuuringud. - M .: MSTU kirjastus im. N.E. Bauman, 2002. - 435 lk.

3. Volkov I.K., Zuev S.M., Tsvetkova G.M. juhuslikud protsessid. - M .: MSTU kirjastus im. N.E. Bauman, 2000. - 447 lk.

4. Gmurman V.E. Juhend tõenäosusteooria ja matemaatilise statistika probleemide lahendamiseks. - M.: Kõrgkool, 1979. - 400 lk.

5. Ivnitski V.L. Järjekordade võrkude teooria. – M.: Fizmatlit, 2004. – 772 lk.

6. Uurimistoimingud majanduses / toim. N.Sh. Kremer. - M.: Ühtsus, 2004. - 407 lk.

7. Takha H.A. Sissejuhatus operatsiooniuuringutesse. - M.: Kirjastus "Williams", 2005. - 902 lk.

8. Kharin Yu.S., Maljugin V.I., Kirlitsa V.P. jt Simulatsiooni ja statistilise modelleerimise alused. - Minsk: Disain PRO, 1997. - 288 lk.

Järjekorrasüsteemide (QS) analüütiline uurimine on alternatiivne lähenemine simulatsioonimodelleerimisele ja seisneb QS-i väljundparameetrite arvutamise valemite hankimises, millele järgneb argumentide väärtuste asendamine nendesse valemitesse igas individuaalses katses.

QS-mudelites võetakse arvesse järgmisi objekte:

1) teenusepäringud (tehingud);

2) teenindusseadmed (OA) või seadmed.

Järjekorrateooria praktiline ülesanne on seotud nende objektide tehte uurimisega ja koosneb eraldiseisvatest elementidest, mida mõjutavad juhuslikud tegurid.

Näitena järjekorra teoorias käsitletud probleemidest võib tuua: sõnumiallika läbilaskevõime sobitamine andmeedastuskanaliga, linnatranspordi optimaalse voo analüüsimine, lennujaama reisijate ooteruumi mahutavuse arvutamine. , jne.

Taotlus võib olla kas teenindusolekus või teenuse ootel olekus.

Teenindusseade võib olla kas teenusega hõivatud või vaba.

QS-i olekut iseloomustab teenindusseadmete ja rakenduste olekute komplekt. QS-i olekute muutumist nimetatakse sündmuseks.

QS-mudeleid kasutatakse süsteemis toimuvate protsesside uurimiseks, rakendades rakendusvoogude sisenditele. Need protsessid on sündmuste jada.

QS-i olulisemad väljundparameetrid

Esitus

Ribalaius

Teenuse keelamise tõenäosus

Keskmine teenindusaeg;

Seadmete koormustegur (OA).

Rakendused võivad olla tellimused toodete valmistamiseks, arvutisüsteemis lahendatavad ülesanded, kliendid pankades, transpordile saabuvad kaubad jne. On ilmne, et süsteemi sisenevate rakenduste parameetrid on juhuslikud muutujad ja nende parameetrid on teada ainult nende parameetrid uurimistöö või projekteerimine.levitamise seadused.

Sellega seoses on toimimise analüüs süsteemi tasandil reeglina statistilise iseloomuga. Matemaatilise modelleerimisvahendina on mugav võtta järjekorra teooriat ja sellel tasemel süsteemide mudelitena kasutada järjekorrasüsteeme.

Lihtsamad QS mudelid

Kõige lihtsamal juhul on QS seade, mida nimetatakse teenindusseadmeks (OA), mille sisendites on rakenduste järjekorrad.

M o d e l o n s e r e n t e r e s e s e n k a t i o n (joonis 5.1)

Riis. 5.1. QS-mudel tõrgetega:

0 – päringu allikas;

1 - teenindusseade;

a– teenusetaotluste sisendvoog;

sisse on teenindatud päringute väljundvoog;

Koos on teenindamata päringute väljundvoog.

Selles mudelis ei ole OA sisendis nõuete akumulaatorit. Kui nõue saabub allikast 0 hetkel, mil AA on hõivatud eelmise nõude teenindamisega, siis äsja saabunud nõue väljub süsteemist (kuna selle teenuse osutamisest keelduti) ja kaob (voog Koos).

M o d e l o f C a n d i n s e k r i o n s (joonis 5.2)

Riis. 5.2. QS-mudel ootustega

(N– 1) - rakenduste arv, mis mahub akumulaatorisse

Sellel mudelil on OA sisendis nõuete akumulaator. Kui klient saabub allikast 0 hetkel, mil CA on hõivatud eelmise kliendi teenindamisega, siis siseneb äsja saabunud klient akumulaatorisse, kus ta ootab lõputult kuni CA vabaneb.

PIIRATUD AJAGA TEENUSMUDEL

w i d a n y (joonis 5.3)

Riis. 5.4. Mitmekanaliline QS-mudel tõrgetega:

n- identsete teenindusseadmete (seadmete) arv

Selles mudelis ei ole mitte üks OA, vaid mitu. Taotlusi võib esitada igale mitteteenivale AB-le, kui pole märgitud teisiti. Salvestusruumi pole, seega sisaldab see mudel joonisel fig. 5.1: rakenduse kättetoimetamisest keeldumine tähendab selle pöördumatut kadumist (see juhtub ainult siis, kui selle rakenduse saabumise ajal kõik OA on hõivatud).

w a t h i n t h o m e (joonis 5.5)

Riis. 5.6. Mitme kanaliga QS-mudel koos ootamise ja taastamise OA-ga:

e- rikkis olevad hooldusseadmed;

f– taastatud teenindussõidukid

Sellel mudelil on joonistel fig. 5.2 ja 5.4, samuti omadused, mis võimaldavad arvestada EA võimalikke juhuslikke tõrkeid, mis sel juhul sisenevad remondiplokki 2, kus nad jäävad juhuslikeks taastamiseks kuluvateks perioodideks ja naasevad seejärel teenindusse. uuesti plokk 1.

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

OA ooteaeg ja taastumine (joonis 5.7)

Riis. 5.7. Piiratud ooteajaga ja OA taastamisega mitmekanaliline QS-mudel

See mudel on üsna keeruline, kuna võtab korraga arvesse kahe mitte kõige lihtsama mudeli omadusi (joonised 5.5 ja 5.6).

Klassifikatsioon, põhimõisted, mudeli elemendid, põhitunnuste arvutamine.

Kaubanduse, tarbijateenuste, laonduse jms ratsionaalse korraldamise probleemide lahendamisel. väga kasulik on tootmisstruktuuri tegevuste tõlgendamine kui järjekorra süsteemid, st. süsteem, kus ühelt poolt tekivad pidevalt nõudmised mis tahes töö tegemiseks, teiselt poolt aga neid taotlusi pidevalt rahuldatakse.

Iga SMO sisaldab neli elementi: sissetulev voog, järjekord, server, väljaminev voog.

nõue(klient, rakendus) on QS-is iga individuaalne taotlus mis tahes töö tegemiseks.

Teenindus on tööde teostamine sissetuleva nõudluse rahuldamiseks. Objekti, mis teostab nõuete hooldust, nimetatakse teenindusseadmeks (seadmeks) või teeninduskanaliks.

Teenindusaeg on ajavahemik, mille jooksul on teenindusnõue rahuldatud, s.o. ajavahemik teenuse algusest kuni selle lõpetamiseni. Ajavahemikku päringu süsteemi sisenemisest kuni teenuse alguseni nimetatakse teenuse ooteajaks. Teenuse ooteaeg koos teenindusajaga on nõude viibimise aeg süsteemis.

SMOd klassifitseeritakse erinevate kriteeriumide alusel..

1. Teeninduskanalite arvu järgi jagunevad QS-id ühe- ja mitmekanalilisteks.

2. Sõltuvalt ootetingimustest eristab teenuse käivitamise nõue QS-i kadudega (tõrgetega) ja QS-i ootamisega.

AT QS nõudluse vähenemisega, mis saabusid hetkel, kui kõik seadmed on hooldusega hõivatud, on tagasi lükatud, on selle süsteemi jaoks kadunud ja ei mõjuta edasist hooldusprotsessi. Klassikaline rikkesüsteemi näide on telefonikeskjaam – ühendustaotlus lükatakse tagasi, kui helistaja on hõivatud.

Riketega süsteemi puhul on toimimise efektiivsuse põhitunnuseks rikke tõenäosus või teenindamata jäänud päringute keskmine osakaal.

AT Ühine turukorraldus koos nõudluse ootamisega, mis on vastu võetud hetkel, kui kõik seadmed on hõivatud teenindusega, ei lahku süsteemist, vaid seab järjekorda ja ootab, kuni üks kanal vabaneb. Kui järgmine seade vabastatakse, võetakse üks järjekorras olevatest rakendustest kohe hoolduseks vastu.

Ootava QS-i puhul on peamised omadused matemaatilised ootused järjekorra pikkuse ja ooteaja kohta.

Ootava süsteemi näide on telerite taastamise protsess remonditöökojas.

Nende kahe rühma vahel on süsteeme ( kombineeritud ühised turukorraldused). Neid iseloomustab mõningate vahetingimuste olemasolu: piirangud võivad olla piirangud teenuse alguse ooteajale, järjekorra pikkusele jne.

Toimivusnäitajatena saab rikke tõenäosust kasutada nii kadudega (või ooteaja tunnustega) kui ka ootamisega süsteemides.

3. Vastavalt teenindusdistsipliinile jagunevad QS-id teenuseprioriteediga süsteemideks ja teenuseprioriteedita süsteemideks.

Taotlusi saab teenindada nende laekumise järjekorras, kas juhuslikult või kehtestatud prioriteetide alusel.

4. QS võib olla ühefaasiline ja mitmefaasiline.

AT üksik faas süsteemid, nõudeid teenindavad sama tüüpi kanalid (näiteks sama kutseala töötajad), ilma neid ühest kanalist teise üle kandmata, mitmefaasiline sellised ülekanded on võimalikud.

5. Nõuete allika asukoha järgi jagunevad QS-id avatud (kui nõude allikas on väljaspool süsteemi) ja suletud (kui allikas on süsteemis endas).

To suletud hõlmata süsteeme, mille sissetulev nõuete voog on piiratud. Näiteks töödejuhataja, kelle ülesandeks on töökojas masinaid seadistada, peab neid perioodiliselt hooldama. Iga seadistatud masin saab tulevikus potentsiaalseks seadistusnõuete allikaks. Sellistes süsteemides on ringlevate nõuete koguarv piiratud ja enamasti konstantne.

Kui toiteallikal on lõpmatu arv nõudeid, kutsutakse süsteeme avatud. Sellised süsteemid on näiteks poed, jaamade piletikassad, sadamad jne. Nende süsteemide puhul võib sissetulevate päringute voogu pidada piiramatuks.

QS-i uurimise meetodid ja mudelid võib tinglikult jagada analüütilisteks ja statistilisteks (järjekorraprotsesside simulatsioonimodelleerimine).

Analüütilised meetodid võimaldavad saada süsteemi karakteristikud kui selle funktsioneerimise parameetrite mõned funktsioonid. See võimaldab kvalitatiivselt analüüsida üksikute tegurite mõju QS-i efektiivsusele.

Kahjuks on analüütiliselt lahendatav vaid üsna piiratud hulk järjekorrateooria probleeme. Vaatamata analüütiliste meetodite jätkuvale arendamisele on paljudel reaalsetel juhtudel analüütilist lahendust kas võimatu saada või osutuvad sellest tulenevad sõltuvused nii keeruliseks, et nende analüüsist saab iseseisev raske ülesanne. Seetõttu tuleb analüütiliste lahendusmeetodite rakendamiseks kasutada erinevaid lihtsustavaid eeldusi, mida mingil määral kompenseerib võimalus rakendada lõppsõltuvuste kvalitatiivset analüüsi (antud juhul on see muidugi vajalik, et tehtud eeldused ei moonutaks protsessi tegelikku pilti).

Praegu on teoreetiliselt kõige arenenumad ja praktilistes rakendustes mugavamad meetodid selliste järjekorraprobleemide lahendamiseks, kus nõuete voog on kõige lihtsam ( Poisson).

Lihtsaima voo korral järgib nõuete süsteemi laekumise sagedus Poissoni seadust, see tähendab, et aja t saabumise tõenäosus, mis on võrdne k nõudega, antakse valemiga:

kus λ on voolu parameeter (vt allpool).

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

Tavalisus voog – kahe või enama nõude samaaegse vastuvõtmise praktiline võimatus. Näiteks tõenäosus, et remondimeeste meeskonna poolt hooldatavast masinarühmast mitu masinat korraga rikki läheb, on üsna väike.

Statsionaarne helistas voolu, mille puhul matemaatiline ootus süsteemi sisenevate nõuete arvu kohta ajaühikus (tähistatakse λ-ga) ajas ei muutu. Seega tõenäosus, et teatud arv kliente siseneb süsteemi antud ajaintervalli Δt jooksul, sõltub selle väärtusest ja ei sõltu selle päritolust ajateljel.

Ei mingit järelmõju tähendab, et enne aega t süsteemi sisenevate klientide arv ei määra, kui palju kliente aja jooksul t + Δt süsteemi siseneb.

Näiteks kui kangastelgedel toimub hetkel niidi katkemine ja selle kõrvaldab kuduja, siis see ei määra, kas sellel kangastel tuleb järgmisel hetkel uus katkestus või mitte, seda enam ei mõjuta teiste masinate purunemise tõenäosust.

QS-i oluliseks tunnuseks on nõuete teenindamise aeg süsteemis. Teenindusaeg on reeglina juhuslik suurus ja seetõttu saab seda kirjeldada jaotusseadusega. Eksponentseadus on saanud suurima leviku teoorias ja eriti praktilistes rakendustes. Selle seaduse puhul on tõenäosusjaotuse funktsioonil järgmine kuju:

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

need. tõenäosus, et tööaeg ei ületa teatud väärtust t määratakse valemiga (1 - e -μt), kus μ on süsteemi nõuete kasutusaja eksponentsiaalseaduse parameeter - keskmise pöördväärtus teenistusaeg, s.o. .

Kaaluge ootuspäraselt analüütilisi QS-mudeleid(kõige levinum QS, kus kõigi teenindusüksuste hõivatuse hetkel saabunud päringud seatakse järjekorda ja teenindatakse teenindusüksuste vabanemisel).

Järjekordadega tööülesanded on tüüpilised tootmistingimustes, näiteks reguleerimis- ja remonditööde korraldamisel, mitme masina hooldusel jne.

Üldine probleemipüstitus on järgmine.

Süsteem koosneb n teeninduskanalist. Igaüks neist saab korraga esitada ainult ühe päringu. Süsteem võtab vastu kõige lihtsama (Poissoni) nõuete voo parameetriga λ. Kui järgmise päringu saabumise hetkel süsteemis on juba vähemalt n päringut teenuses (st kõik kanalid on hõivatud), siis siseneb see päring järjekorda ja ootab teenuse algust.

Iga nõude teenindusaeg t about on juhuslik suurus, mis järgib eksponentsiaalse jaotuse seadust parameetriga μ.

Nagu eespool märgitud, võib ootusega QS jagada kahte suurde rühma: suletud ja avatud.

Mõlemat tüüpi süsteemide toimimise omadused annavad kasutatavale matemaatilisele seadmele oma varju. Erinevat tüüpi QS-operatsiooni karakteristikute arvutamist saab läbi viia QS-i olekute tõenäosuste arvutamise (Erlangi valemite) põhjal.

Kuna süsteem on suletud, tuleks probleemiavaldusele lisada tingimus: sissetulevate päringute voog on piiratud, s.t. järjekorrasüsteemil ei saa olla korraga rohkem kui m päringut (m on teenindatavate objektide arv).

Vaadeldava süsteemi toimimise kvaliteeti iseloomustavate põhikriteeriumitena valime: 1) keskmise järjekorra pikkuse ja suurima nõuete arvu, mis samaaegselt teenindussüsteemis on - teenindatava objekti seisakutegur; 2) tühikäigul teenindavate kanalite keskmise arvu ja nende koguarvu suhe on teenindatava kanali jõudeoleku suhe.

Mõelge suletud QS vajalike tõenäosuslike karakteristikute (jõudlusnäitajate) arvutamisele.

1. Tõenäosus, et süsteemis on k nõuet eeldusel, et nende arv ei ületa teenindusseadmete arvu n:

P k = α k P 0, (1 ≤ k ≤ n),

kus

λ on nõuete ühest allikast süsteemi vastuvõtmise sagedus (intensiivsus);

Ühe nõude keskmine teenindamise kestus;

m - suurim võimalik arv nõudeid, mis on samal ajal teenindavas süsteemis;

n on teenindusseadmete arv;

P 0 - tõenäosus, et kõik teenindusseadmed on vabad.

2. Tõenäosus, et süsteemis on k nõuet, eeldusel, et nende arv on suurem kui teenindusseadmete arv:

P k = α k P 0, (n ≤ k ≤ m),

kus

3. Tõenäosus, et kõik serverid on vabad, määratakse tingimuse põhjal

Järelikult

4. Teenuse käivitamist ootavate päringute keskmine arv (keskmine järjekorra pikkus):

5. Nõudluse seisakute suhe hoolduse ootel:

6. Tõenäosus, et kõik teenindusseadmed on hõivatud:

7. Keskmine nõuete arv teenindussüsteemis (teenindatud ja teenust ootav):

8. Teenindusnõuete ja teenuse ootamise koguseisakute suhe:

9. Nõude keskmine jõudeaeg teenusejärjekorras:

10. Keskmine tasuta saatjate arv:

11. Teenindussõidukite seisakuaeg:

12. Tõenäosus, et teenust ootavate päringute arv on suurem kui mõni arv B (tõenäosus, et teenusejärjekorras on rohkem kui B päringuid):

Inimtegevuse praktikas hõivavad suure koha järjekorraprotsessid, mis esinevad sama tüüpi ülesannete lahendamisel korduvkasutuseks mõeldud süsteemides. Selliseid süsteeme nimetatakse järjekorrasüsteemideks (QS). Selliste süsteemide näideteks on telefonisüsteemid, arvutisüsteemid, autotööstus, lennundus, hooldussüsteemid, kauplused, piletikassad jms.

Iga süsteem koosneb teatud arvust teenindusüksustest (instrumendid, seadmed, seadmed "punktid, jaamad), mida nimetatakse teeninduskanaliteks. Kanalite arvu järgi jaguneb QS ühekanaliliseks ja mitme kanaliga. Diagramm ühe kanaliga järjekorrasüsteemi on näidatud joonisel 6.2.

Tavaliselt ei sisene rakendused süsteemi regulaarselt, vaid juhuslikult, moodustades juhusliku rakenduste voo (nõuded). Iga nõude teenindamine võib kesta kas teatud aja või sagedamini määramata aja. Juhuslik olemus toob kaasa asjaolu, et QS laaditakse ebaühtlaselt: mõnel ajaperioodil koguneb väga palju rakendusi (nad kas satuvad ritta või jätavad QS-i teenindamata), samal ajal kui teistel perioodidel töötab QS alakoormusega. või on jõude.

Riis. 6.2.

Järjekorrasüsteemide uuringu eesmärk on analüüsida nende toimimise kvaliteeti ja välja selgitada võimalused selle parandamiseks. Samal ajal on mõistel "toimimise kvaliteet" igal üksikjuhul oma konkreetne tähendus ja seda väljendatakse erinevate kvantitatiivsete näitajatega. Näiteks sellised kvantitatiivsed näitajad nagu teenindusjärjekorra suurus, keskmine teenindusaeg, teeninduse ootamine või teenindussüsteemis nõude leidmine, teenindusseadmete tühikäiguaeg; kindlustunne, et kõik süsteemi saabunud päringud teenindatakse.

Seega ei mõisteta järjekorrasüsteemi toimimise kvaliteedi all mitte konkreetse töö teostamise kvaliteeti, mille tegemiseks taotlus laekus, vaid teenusevajaduse rahuldamise astet.

Järjekorrateooria aineks on matemaatiliste mudelite konstrueerimine, mis seovad QS etteantud töötingimused (kanalite arv, nende jõudlus, rakenduste voo iseloom jne) QS jõudlusnäitajatega, mis kirjeldavad. selle võimet tulla toime rakenduste vooluga.

Järjekorrasüsteemide klassifikatsioon

Esimene omadus, mis võimaldab järjekorra ülesandeid klassifitseerida, on teenindava süsteemi poolt vastuvõetud nõudmiste käitumine hetkel, kui kõik masinad on hõivatud.

Mõnel juhul ei jõua nõue, mis siseneb süsteemi ajal, mil kõik masinad on hõivatud, nende vabastamist ära oodata ja jätab süsteemi teenindamata, s.t. nõue on antud teenindussüsteemi jaoks kadunud. Selliseid teenindussüsteeme nimetatakse kadudega süsteemideks ja nende põhjal sõnastatud probleeme nimetatakse kadudega süsteemide teenindusprobleemideks.

Kui aga süsteemi sisenenud nõudlus satub järjekorda ja ootab seadme vabastamist, siis selliseid süsteeme nimetatakse ootamisega süsteemideks ja vastavaid ülesandeid ootamisega süsteemides teenindusülesanneteks. Ootega QS jaguneb erinevateks tüüpideks olenevalt järjekorra korraldusest: piiratud või piiramatu järjekorra pikkusega, piiratud ooteajaga jne.

QS-id erinevad ka nõuete arvu poolest, mis võivad samaaegselt olla teenindussüsteemis. Eraldage:

• 1) piiratud nõuetevooga süsteemid;
• 2) piiramatu nõuetevooga süsteemid.

Sõltuvalt teenuse sisemise korralduse vormidest süsteemis on:

• 1) tellitud teenusega süsteemid;
• 2) häiritud teenindusega süsteemid.

Oluline samm QS-i uurimisel on uuritavat protsessi iseloomustavate kriteeriumide valik. Valik sõltub uuritavate probleemide tüübist, lahenduse eesmärgist.

Enamasti on praktikas süsteeme, kus nõuete voog on kõige lihtsama ja teenindusaeg järgib eksponentsiaalse jaotuse seadust. Need süsteemid on kõige täiuslikumalt välja töötatud järjekorrateoorias.

Ettevõtte tingimustes on tüüpilised ootamisega, piiratud arvu teenindusseadmetega, piiratud nõuetevooga ja korrastamata teenindusega ülesanded.

23. oktoober 2013, kell 14:22

Squeak: Modeling Queuing Systems

• programmeerimine,
• OOP,
• Paralleelne programmeerimine

Sellise programmeerimiskeele nagu Squeak kohta on Habré kohta väga vähe teavet. Püüan sellest rääkida järjekorrasüsteemide modelleerimise kontekstis. Näitan, kuidas kirjutada lihtsat klassi, kirjeldada selle struktuuri ja kasutada seda programmis, mis teenindab päringuid mitme kanali kaudu.

Paar sõna Squeaki kohta

Squeak on Smalltalk-80 programmeerimiskeele avatud, platvormideülene teostus koos dünaamilise tippimise ja prügikogujaga. Liides on üsna spetsiifiline, kuid silumiseks ja analüüsimiseks üsna mugav. Squeak vastab täielikult OOP kontseptsioonile. Kõik koosneb objektidest, isegi struktuuridest kui-siis-muidu, ajaks, ajaks nende abiga ellu viidud. Kogu süntaks taandub objektile sõnumi saatmisele kujul:

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

Iga meetod tagastab alati objekti ja sellele saab saata uue sõnumi.
Squeaki kasutatakse sageli protsesside modelleerimiseks, kuid seda saab kasutada ka multimeediumirakenduste ja mitmesuguste haridusplatvormide loomise tööriistana.

Järjekorrasüsteemid

Järjekorrasüsteemid (QS) sisaldavad ühte või mitut kanalit, mis töötlevad mitmest allikast pärit rakendusi. Iga päringu teenindamise aeg võib olla fikseeritud või suvaline, samuti nende saabumise vahelised intervallid. See võib olla telefonikeskjaam, pesumaja, poe kassapidajad, trükkimisbüroo jne. See näeb välja umbes selline:

QS sisaldab mitmeid allikaid, mis sisenevad ühisesse järjekorda ja saadetakse hooldusesse, kui töötlemiskanalid vabanevad. Sõltuvalt reaalsete süsteemide spetsiifilistest omadustest võib mudel sisaldada erinevat arvu päringuallikaid ja teenusekanaleid ning omada erinevaid piiranguid järjekorra pikkusele ja sellega seotud päringute (tõrgete) kaotamise võimalusele.

QS-i modelleerimisel lahendatakse tavaliselt järjekorra keskmise ja maksimaalse pikkuse hindamise, teenindussageduse, keskmise kanalikoormuse ja nende arvu määramise ülesanded. Olenevalt ülesandest sisaldab mudel tarkvaraplokke protsesside käitumise kohta vajalike statistiliste andmete kogumiseks, akumuleerimiseks ja töötlemiseks. QS analüüsis kõige sagedamini kasutatavad sündmuste voo mudelid on tavaline ja Poisson. Regulaarseid iseloomustab sama aeg sündmuste toimumise vahel, Poissoni omasid aga juhuslikud.

Natuke matemaatikat

Poissoni voolu puhul sündmuste arv X mis jäävad pikkusevahemikku τ (tau) punktiga külgnev t, jaotatud vastavalt Poissoni seadusele:
kus a (t, τ)- keskmine sündmuste arv ajavahemikus τ .
Ajaühikus toimuvate sündmuste keskmine arv on võrdne λ(t). Seega keskmine sündmuste arv ajaintervalli kohta τ , ajahetkega külgnev t, on võrdne:

Aeg T kahe sündmuse vahel λ(t) = const = λ levitatakse vastavalt seadusele:
Juhusliku suuruse jaotustihedus T tundub, et:
Ajavahemike pseudojuhuslike Poissoni jadade saamiseks t i lahendage võrrand:
kus r i on juhuslik arv, mis on intervalli peale ühtlaselt jaotatud.
Meie puhul annab see väljendi:

Juhuslikke numbreid genereerides saate kirjutada terveid köiteid. Intervalli peale ühtlaselt jaotatud täisarvude genereerimiseks kasutame järgmist algoritmi:
kus R i- teine ​​juhuslik täisarv;
R- mõni suur algarv (nt 2311);
K- täisarv - intervalli ülempiir, näiteks 2 21 = 2097152;
rem- täisarvude jagamisest jäägi saamine.

Algne väärtus R0 tavaliselt suvaliselt seadistatud, kasutades näiteks taimeri näitu:
Aeg kokku sekundites
Intervallile ühtlaselt jaotatud numbrite saamiseks kasutame keeleoperaatorit:

Rand klass

Intervallile ühtlaselt jaotatud juhuslike arvude saamiseks loome klassi - reaalarvude generaatori:

Float muutujaWordSubclass: #Rand "klassi nimi" eksemplarVariableNames: "" "eksemplari muutujad" classVariableNames: "R" "klassi muutujad" poolSõnastikud: "" "levisõnastikud" kategooria: "Näidis" "kategooria nimi"
Meetodid:

"Initsialiseerimine" init R:= Time totalSeconds.next "Järgmine pseudojuhuslik arv" next R:= (R * 2311 + 1) rem: 2097152. ^(R/2097152) asFloat
Anduri algoleku määramiseks saatke sõnum Rand init.
Teise juhusliku numbri saamiseks saatke Rand järgmisena.

Taotluste töötlemise programm

Nii et lihtsa näitena teeme järgmist. Oletame, et peame simuleerima ühest allikast pärinevate päringute korrapärase voo säilitamist juhusliku ajaintervalliga päringute vahel. Seal on kaks erineva jõudlusega kanalit, mis võimaldavad rakendusi teenindada vastavalt 2 ja 7 ajaühikuga. Iga kanali poolt teenindatavate päringute arv tuleb registreerida 100 ajaühiku intervalliga.

Squeak Code

"Ajutiste muutujate deklareerimine" | proc1 proc2 t1 t2 s1 s2 sysPrioriteedi järjekord jätka r | "Esialgne muutuja seaded" Rand init. SysTime:= 0. s1:= 0. s2:= 0. t1:= -1. t2:= -1. jätka:=tõsi. sysPriority:= Protsessori aktiivneProtsessi prioriteet. "Praegune prioriteet" järjekord:= Semafor uus. "Nõudejärjekorra mudel" "Loo protsess – kanali mudel 1" s1:= s1 + 1. proc1 peata."Peatage protsess teenuse lõpetamise ootel" ].proc1:= nil."Eemalda viide protsessile 1" ]priority: (sysPriority + 1)) CV. "Uus prioriteet on suurem kui taust" "Loo protsess – kanali mudel 2" .proc2:= null.] prioriteet: (sysPriority + 1)) jätka. "Põhiprotsessi ja lähtemudeli kirjelduse jätkamine", kuigiTõsi: [ r:= (Rand järgmine * 10) ümardatud. (r = 0) kuiTrue: . ((SysTime rem: r) = 0) kuiTrue: . "Saada päring" "Teenuseprotsessi lüliti" (t1 = SysTime) ifTrue: . (t2 = SysTime) ifTrue: . SysTime:= SysTime + 1. "Modeli aeg tiksub" ]. "Näita päringu loenduri olekut" PopUpMenu inform: "proc1: ",(s1 printString),", proc2: ",(s2 printString). jätka:= vale.

Käivitamisel näeme, et protsess 1 suutis töödelda 31 taotlust ja protsess 2 ainult 11: