Kurssityöt

"Järjestelmän simulointi jonotus»

kurssilla "Toimintatutkimus"

Johdanto

Toimintatutkimuksessa kohtaa usein järjestelmiä, jotka on suunniteltu siihen uudelleen käytettävä kun ratkaiset samanlaisia ​​ongelmia. Tässä tapauksessa syntyviä prosesseja kutsutaan palveluprosesseiksi ja järjestelmiä kutsutaan jonojärjestelmiksi (QS). Jokainen QS koostuu tietystä määrästä palveluyksiköitä (instrumentteja, laitteita, pisteitä, asemia), joita kutsutaan palvelukanaviksi. Kanavat voivat olla viestintälinjoja, toimintapisteitä, tietokoneita, myyjiä jne. Kanavien lukumäärän mukaan QS jaetaan yksikanavaisiin ja monikanavaisiin.

Sovellukset eivät yleensä saapuvat QS:ään säännöllisesti, vaan satunnaisesti muodostaen niin sanotun satunnaisen sovellusvirran (vaatimukset). Myös sovellusten palvelu jatkuu jonkin aikaa satunnaisesti. Sovellusvirran ja palveluajan satunnaisuus johtaa siihen, että QS kuormitetaan epätasaisesti: joinakin ajanjaksoina paljon suuri määrä sovellukset (joko joutuvat jonoon tai jättävät QS:n käyttämättä), kun taas muina aikoina QS toimii alikuormituksella tai on tyhjäkäynnillä.

Jonoteorian aiheena on matemaattisten mallien rakentaminen, jotka yhdistävät QS:n annetut toimintaolosuhteet (kanavien lukumäärä, niiden suorituskyky, sovellusvirran luonne jne.) QS:n suoritusindikaattoreihin, jotka kuvaavat sen kyky selviytyä sovellusten virtauksesta. Seuraavia käytetään QS:n suoritusindikaattoreina:

– Absoluuttinen läpijuoksu järjestelmät ( MUTTA

K

- hakemuksen tiedoksiantamisesta kieltäytymisen todennäköisyys ();

k);

- jonossa olevien hakemusten keskimääräinen määrä ();

QS on jaettu kahteen päätyyppiin: QS, jossa on epäonnistumisia ja QS, joissa on odotus (jono). Kieltoja sisältävässä QS:ssä pyyntö, joka saapuu sillä hetkellä, kun kaikki kanavat ovat varattu, saa kieltäytymisen, poistuu QS:stä eikä osallistu jatkopalveluprosessiin (esim. puhelinkeskustelu sillä hetkellä, kun kaikki kanavat ovat varattu, saa kieltäytymisen ja jättää QS:n käyttämättä). Odottavassa QS:ssä vaatimus, joka saapuu aikana, jolloin kaikki kanavat ovat varattu, ei lähde, vaan joutuu palveluun.

Yksi QS-suorituskykyindikaattoreiden laskentamenetelmistä on simulointimenetelmä. Tietokonesimulaatiomallinnuksen käytännön käyttö edellyttää sopivan matemaattisen mallin rakentamista, joka ottaa huomioon epävarmuustekijät, dynaamiset ominaisuudet ja koko tutkittavan järjestelmän elementtien välisten suhteiden kompleksin. Järjestelmän toiminnan simulaatiomallinnus alkaa tietystä alkutilasta. Erilaisten satunnaisten tapahtumien toteutumisesta johtuen järjestelmän malli siirtyy myöhempinä hetkinä muihin mahdollisiin tiloihinsa. Tämä kehitysprosessi jatkuu suunnittelukauden loppuun, ts. simulaation loppuun asti.

1. Yhteisen markkinajärjestelyn pääominaisuudet ja niiden tehokkuuden indikaattorit

1.1 Markovin stokastisen prosessin käsite

Olkoon jokin järjestelmä, joka muuttaa tilaansa satunnaisesti ajan myötä. Tässä tapauksessa sanomme, että järjestelmässä tapahtuu satunnainen prosessi.

Prosessia kutsutaan prosessiksi, jossa on diskreetit tilat, jos sen tilat voidaan luetella etukäteen ja järjestelmän siirtyminen tilasta toiseen tapahtuu hyppynä. Prosessia kutsutaan jatkuvaaikaiseksi prosessiksi, jos järjestelmän siirtymät tilasta tilaan tapahtuvat välittömästi.

QS-toimintaprosessi on satunnainen prosessi, jossa on diskreetit tilat ja jatkuva aika.

Satunnaista prosessia kutsutaan Markovin tai satunnaisprosessiksi ilman jälkivaikutusta, jos prosessin todennäköisyysominaisuudet tulevaisuudessa riippuvat vain sen nykyisestä tilasta eivätkä riipu siitä, milloin ja miten järjestelmä on joutunut tähän tilaan.

QS-toimintaprosesseja analysoitaessa on kätevää käyttää geometristä kaaviota - tilakaavio. Yleensä järjestelmän tilat esitetään suorakulmioilla, ja mahdolliset siirtymät tilasta tilaan esitetään nuolilla. Esimerkki tilakaaviosta on esitetty kuvassa. yksi.

Tapahtumavirta on homogeenisten tapahtumien sarja, jotka seuraavat peräkkäin satunnaisina aikoina.

Virtalle on tunnusomaista intensiteetti λ - tapahtumien esiintymistiheys tai QS:ään saapuvien tapahtumien keskimääräinen määrä aikayksikköä kohti.

Tapahtumavirtaa kutsutaan säännölliseksi, jos tapahtumat seuraavat peräkkäin säännöllisin väliajoin.

Tapahtumavirtaa kutsutaan paikallaan pysyväksi, jos sen todennäköisyysominaisuudet eivät riipu ajasta. Erityisesti paikallaan olevan virtauksen intensiteetti on vakioarvo: .

Tapahtumavirtaa kutsutaan tavalliseksi, jos todennäköisyys, että kaksi tai useampi tapahtuma osuu pieneen ajanjaksoon, on pieni verrattuna yksittäisen tapahtuman osumisen todennäköisyyteen, eli jos tapahtumat esiintyvät siinä yksitellen, eivät ryhmissä.

Tapahtumavirtaa kutsutaan virraksi ilman jälkivaikutuksia, jos kahdella ei-leikkautuvalla aikavälillä ja jompaankumpaan osuvien tapahtumien määrä ei riipu muiden tapahtumien lukumäärästä.

Tapahtumien virtaa kutsutaan yksinkertaisimmaksi (tai kiinteäksi Poissoniksi), jos se on sekä paikallaan että tavallinen eikä sillä ole jälkivaikutusta.

1.2 Kolmogorov-yhtälöt

Kaikki järjestelmän siirtymät tilasta tilaan tapahtuvat jonkin tapahtumavirran alaisena. Olkoon systeemi jossain tilassa, josta siirtyminen tilaan on mahdollista, silloin voidaan olettaa, että järjestelmään vaikuttaa yksinkertaisin virtaus, jonka intensiteetti on siirtäen sen tilasta tilaan. Heti kun säikeen ensimmäinen tapahtuma tapahtuu, sen siirtyminen tapahtuu. Selvyyden vuoksi tilakaaviossa jokainen siirtymää vastaava nuoli on merkitty intensiteetillä . Tällainen merkitty tilakaavio mahdollistaa rakentamisen matemaattinen malli prosessi, ts. löytää kaikkien tilojen todennäköisyydet ajan funktiona. Heille laaditaan differentiaaliyhtälöt, joita kutsutaan Kolmogorov-yhtälöiksi.

Kolmogorovin yhtälöiden laatimissääntö: Jokaisen yhtälön vasemmalla puolella on todennäköisyyden aikaderivaata annettu tila. Oikealla puolella on kaikkien niiden tilojen tulojen summa, joista siirtyminen tiettyyn tilaan on mahdollista, vastaavien tapahtumavirtojen intensiteetillä vähennettynä kaikkien järjestelmän tästä tilasta tuovien virtojen kokonaisintensiteetillä kerrottuna tämän tilan todennäköisyys.

Esimerkiksi kuvassa 2 esitetylle tilakaaviolle. 1, Kolmogorov-yhtälöillä on muoto:

Koska järjestelmän oikealla puolella jokainen termi tulee 1 kerran merkillä ja 1 kerran merkillä , sitten lisäämällä kaikki yhtälöt, saamme sen

,

,

Siksi yksi järjestelmän yhtälöistä voidaan hylätä ja korvata yhtälöllä (1.2.1).

Saada haltuunsa erityinen ratkaisu sinun on tiedettävä alkuehdot, ts. todennäköisyydet alkuhetkellä.

1.3 QS:n lopulliset todennäköisyydet ja tilakaavio

Järjestelmän prosessien riittävän pitkäksi ajaksi (at ) voidaan määrittää ajasta riippumattomien tilojen todennäköisyydet, joita kutsutaan lopullisiksi todennäköisyyksiksi, ts. järjestelmä on paikallaan. Jos järjestelmän tilojen määrä on äärellinen ja niistä jokaisesta äärellisessä määrässä askeleita voidaan siirtyä mihin tahansa muuhun tilaan, niin lopulliset todennäköisyydet ovat olemassa, ts.

Lopullisten todennäköisyyksien merkitys on, että ne ovat yhtä suuria kuin keskimääräinen suhteellinen aika, jonka järjestelmä viettää tietyssä tilassa.

Koska stationääritilassa aikaderivaatat ovat nolla, jolloin lopullisten todennäköisyyksien yhtälöt saadaan Kolmogorov-yhtälöistä vertaamalla niiden oikeat puolet nollaan.

Jonotusjärjestelmien malleissa käytettyjä tilakaavioita kutsutaan kuoleman ja lisääntymisen skeemaksi. Tämä nimi johtuu siitä, että tätä järjestelmää käytetään populaation koon tutkimukseen liittyvissä biologisissa ongelmissa. Sen erikoisuus on siinä, että järjestelmän kaikki tilat voidaan esittää ketjuna, jossa jokainen tila on yhteydessä edelliseen ja seuraaviin (kuva 2).

Riisi. 2. Tilakaavio QS-malleissa

Oletetaan, että kaikki virrat, jotka siirtävät järjestelmän tilasta toiseen, ovat yksinkertaisimpia. Kuvassa esitetyn kaavion mukaan. 2, laadimme yhtälöitä järjestelmän lopullisille todennäköisyyksille. He näyttävät:

Järjestelmä on hankittu ( n +1) yhtälö, joka ratkaistaan ​​eliminointimenetelmällä. Tämä menetelmä koostuu siitä, että peräkkäin kaikki järjestelmän todennäköisyydet ilmaistaan ​​todennäköisyydellä.

,

.

Korvaamalla nämä lausekkeet järjestelmän viimeiseen yhtälöön, löydämme , sitten löydämme QS-tilojen jäljellä olevat todennäköisyydet.

1.4 QS:n suorituskykyindikaattorit

QS-mallinnuksen tarkoituksena on laskea järjestelmän suorituskykyä sen ominaisuuksien kautta. Seuraavia käytetään QS:n suoritusindikaattoreina:

on järjestelmän absoluuttinen kapasiteetti ( MUTTA), eli keskimääräinen käsiteltyjen hakemusten lukumäärä aikayksikköä kohti;

on suhteellinen suorituskyky ( K), eli järjestelmän palvelemien vastaanotettujen pyyntöjen keskimääräinen osuus;

on epäonnistumisen todennäköisyys (), ts. todennäköisyys, että sovellus jättää QS:n käyttämättä;

on varattujen kanavien keskimääräinen määrä ( k);

- hakemusten keskimääräinen määrä QS:ssä ();

– hakemuksen keskimääräinen viipymisaika järjestelmässä ();

- jonossa olevien sovellusten keskimääräinen lukumäärä () - jonon pituus;

- järjestelmässä olevien sovellusten keskimääräinen määrä ();

- sovelluksen keskimääräinen jonossaoloaika ();

- sovelluksen keskimääräinen viipymä järjestelmässä ()

– kanavan kuormitusaste (), ts. todennäköisyys, että kanava on varattu;

on toimitettujen hakemusten keskimääräinen määrä aikayksikköä kohti;

– palvelun keskimääräinen odotusaika;

– todennäköisyys, että jonossa olevien sovellusten määrä ylittää tietyn arvon jne.

On todistettu, että minkä tahansa tyyppiselle pyyntövirralle, mille tahansa palveluajan jakautumiselle, mille tahansa palvelualalle, pyynnön keskimääräinen aika järjestelmässä (jonossa) on yhtä suuri kuin järjestelmässä olevien pyyntöjen keskimääräinen määrä. (jono) jaettuna pyyntövirran intensiteetillä, ts.

(1.4.1)

Kaavoja (1.4.1) ja (1.4.2) kutsutaan pieniksi kaavoiksi. Ne johtuvat siitä, että rajoittavassa kiinteässä järjestelmässä järjestelmään saapuvien korvausten keskimääräinen määrä on yhtä suuri kuin siitä lähtevien korvausten keskimääräinen määrä, ts. molemmilla sovellusvirroilla on sama intensiteetti.

Suoritusindikaattoreiden laskentakaavat on esitetty taulukossa. yksi.

Pöytä 1.

Indikaattorit	Yksikanavainen QS rajoitettu jono	Monikanavainen QS rajoitettu jono
Lopullinen todennäköisyydet
Todennäköisyys
Absoluuttinen suorituskyky kyky
Suhteellinen suorituskyky kyky
Keskimääräinen hakemusten määrä per
Hakemusten keskimääräinen määrä alle palvelua
Sovellusten keskimääräinen määrä järjestelmässä

1.5 Simuloinnin peruskäsitteet

Simulaatiomallinnuksen päätavoitteena on toistaa tutkittavan järjestelmän käyttäytyminen sen elementtien merkittävimpien suhteiden analyysin perusteella.

Tietokonesimulaatiota tulisi pitää staattisena kokeena.

Satunnaismuuttujien funktioteoriasta tiedetään, että satunnaismuuttujan mallintamiseen millä tahansa jatkuvalla ja monotonisesti kasvavalla jakaumafunktiolla riittää, että osataan mallintaa tasaisesti jakautunut satunnaismuuttuja välillä . Kun satunnaismuuttujan toteutus on saatu, voidaan löytää satunnaismuuttujan vastaava toteutus, koska ne liittyvät yhtäläisyyteen

Oletetaan, että jossain jonojärjestelmässä yhden asiakkaan palveluaika jakautuu eksponentiaalisen lain mukaan parametrilla , jossa on palveluvirran intensiteetti. Sitten palveluajan jakautumisfunktiolla on muoto

Olkoon välille tasaisesti jakautuneen satunnaismuuttujan toteutus ja olkoon sitä vastaavan yhden pyynnön satunnaisen palveluajan toteutus. Sitten kohdan (1.5.1) mukaan

1.6 Simulaatiomallien rakentaminen

Ensimmäinen vaihe minkä tahansa simulaatiomallin luomisessa on vaihe, jossa kuvataan todellista olemassa oleva järjestelmä päätapahtumien ominaisuuksien kannalta. Nämä tapahtumat liittyvät pääsääntöisesti tutkittavan järjestelmän siirtymiin mahdollisesta tilasta toiseen ja ne on merkitty pisteiksi aika-akselilla. Mallintamisen päätavoitteen saavuttamiseksi riittää, että havainnoidaan järjestelmää tärkeimpien tapahtumien toteutushetkellä.

Harkitse esimerkkiä yksikanavaisesta jonojärjestelmästä. Tällaisen järjestelmän simulaatiomallinnuksen tarkoituksena on määrittää arviot sen pääominaisuuksista, kuten sovelluksen jonossa viettämä keskimääräinen aika, jonon keskimääräinen pituus ja järjestelmän seisokkien osuus.

Itse jonotusprosessin ominaisuudet voivat muuttaa arvojaan joko uuden palvelupyynnön vastaanottohetkellä tai seuraavan pyynnön palvelun päättyessä. QS voi aloittaa seuraavan pyynnön palvelemisen välittömästi (palvelukanava on vapaa), mutta ei ole poissuljettua tarvetta odottaa, kun pyynnön on asetettava paikka jonossa (QS jonossa, palvelukanava on varattu). Seuraavan pyynnön suorittamisen jälkeen QS voi välittömästi aloittaa seuraavan pyynnön palvelemisen, jos se on olemassa, mutta se voi myös olla käyttämättömänä, jos sellaista ei ole. Tarvittavat tiedot saadaan tarkkailemalla erilaisia ​​tilanteita tärkeimpien tapahtumien toteuttamisesta. Joten kun vaatimus saapuu QS:ään jonossa varattu palvelukanavalla, jonon pituus kasvaa yhdellä. Samoin jonon pituus pienenee yhdellä, jos seuraavan vaatimuksen ja vaatimusjoukon palvelu on jonossa. ei ole tyhjä.

Minkä tahansa simulointimallin toimintaa varten on tarpeen valita aikayksikkö. Mallinnettavan järjestelmän luonteesta riippuen tällainen yksikkö voi olla mikrosekunti, tunti, vuosi jne.

Koska tietokonesimulaatio on pohjimmiltaan laskennallinen koe, sen havaittujen tulosten aggregaatissa tulee olla satunnaisotostoteutuksen ominaisuuksia. Vain tässä tapauksessa varmistetaan simuloidun järjestelmän oikea tilastollinen tulkinta.

Tpääasiallisena kiinnostuksen kohteena ovat havainnot, jotka saadaan sen jälkeen, kun tutkittava järjestelmä on saavuttanut stationaarisen toimintatavan, koska tällöin otosvarianssi pienenee jyrkästi.

Aika, joka tarvitaan järjestelmän saavuttamiseen kiinteään toimintatilaan, määräytyy sen parametrien ja alkutilan arvojen perusteella.

Koska päätavoitteena on saada havainnointitiedot mahdollisimman pienellä virheellä, tämän tavoitteen saavuttamiseksi voit:

1) pidentää tutkittavan järjestelmän toimintaprosessin simulaatiomallinnuksen kestoa. Tässä tapauksessa ei vain todennäköisyys, että järjestelmä saavuttaa kiinteän toimintatavan, kasvaa, vaan myös käytettävien näennäissatunnaisten lukujen määrä kasvaa, mikä myös vaikuttaa positiivisesti saatujen tulosten laatuun.

2) määrätyn ajan T suoritettava simulaatiomallinnus N laskennalliset kokeet, joita kutsutaan myös malliajoiksi, erilaisilla näennäissatunnaisten lukusarjoilla, joista jokainen antaa yhden havainnon. Kaikki ajot alkavat simuloidun järjestelmän samasta alkutilasta, mutta käyttämällä erilaisia ​​näennäissatunnaislukuja. Tämän menetelmän etuna on saatujen havaintojen riippumattomuus, järjestelmän tehokkuuden indikaattorit. Jos numero N malli on tarpeeksi suuri, niin rajat symmetrinen luottamusväli parametrille määritellään seuraavasti:

, , eli , missä

korjattu varianssi, ,

N– ohjelman ajokertojen määrä, – luotettavuus, .

2. QS:n analyyttinen mallintaminen

2.1 Järjestelmän tilakaavio ja Kolmogorov-yhtälö

Tarkastellaan kaksikanavaista jonojärjestelmää (n = 2), jonka rajoitettu jono on kuusi (m = 4). QS vastaanottaa yksinkertaisimman sovellusvirran, jonka keskimääräinen intensiteetti on λ = 4,8 ja eksponentiaalinen aikajakauman laki sovellusten saapumisen välillä. Järjestelmässä palvelevien pyyntöjen virta on yksinkertaisin, jonka keskimääräinen intensiteetti on μ = 2 ja palveluaikajakauman eksponentiaalinen laki.

Tässä järjestelmässä on 7 tilaa, me merkitsemme niitä:

S 0 - järjestelmä on ilmainen, pyyntöjä ei ole;

S 1 - 1 palvelupyyntö, jono on tyhjä;

S 2 - 2 palvelupyyntöä, jono on tyhjä;

S 3 - 2 palvelupyyntöä, 1 pyyntö jonossa;

S 4 - 2 huoltopyyntöä, 2 pyyntöä jonossa;

S 5 - 2 palvelupyyntöä, 3 pyyntöä jonossa;

S 6 - 2 palvelupyyntöä, 4 pyyntöä jonossa;

Todennäköisyys sille, että järjestelmä pääsee tiloihin S 0, S 1, S 2, …, S 6, on vastaavasti yhtä suuri kuin Р 0, Р 1, Р 2, …, Р 6.

Jonojärjestelmän tilakaavio on kuoleman ja lisääntymisen kaavio. Kaikki järjestelmän tilat voidaan esittää ketjuna, jossa jokainen tila on yhteydessä edelliseen ja seuraavaan.

Riisi. 3. Kaavio kaksikanavaisen QS:n tiloista

Muodostuneelle graafille kirjoitamme Kolmogorov-yhtälöt:

Tämän järjestelmän ratkaisemiseksi asetamme alkuehdot:

Kolmogorovin yhtälöjärjestelmä (järjestelmä differentiaaliyhtälöt) ratkaisemme numeerisella Euler-menetelmällä Maple 11 -ohjelmistopaketilla (katso liite 1).

Eulerin menetelmä

missä - meidän tapauksessamme nämä ovat Kolmogorov-yhtälöiden oikeat osat, n=6.

Valitaan aikavaihe. Oletetaan missä T on aika, jonka järjestelmä saavuttaa vakaan tilan. Täältä saamme vaiheiden määrän . Johdonmukaisesti N kun lasketaan kaavalla (1), saadaan järjestelmän tilojen todennäköisyyksien riippuvuudet ajasta, jotka on esitetty kuvassa 1. neljä.

QS-todennäköisyyksien arvot ovat yhtä suuret kuin:

Riisi. 4. Järjestelmän tilojen todennäköisyyksien riippuvuudet ajasta

P0

P5

P4

P3

P2

P1

2.2 Järjestelmän lopulliset todennäköisyydet

Riittävän pitkällä järjestelmän prosesseilla () voidaan määrittää ajasta riippumattomien tilojen todennäköisyydet, joita kutsutaan lopullisiksi todennäköisyyksiksi, ts. järjestelmä on paikallaan. Jos järjestelmän tilojen määrä on äärellinen ja jokaisesta niistä on mahdollista siirtyä mihin tahansa toiseen tilaan äärellisessä määrässä askelia, niin lopulliset todennäköisyydet ovat olemassa, ts.

Koska stationääritilassa aikaderivaatat ovat yhtä kuin 0, jolloin lopullisten todennäköisyyksien yhtälöt saadaan Kolmogorov-yhtälöistä vertaamalla oikeat puolet 0:aan. Kirjoitetaan QS:n lopullisten todennäköisyyksien yhtälöt.

Ratkaistaan ​​tämä järjestelmä lineaariset yhtälöt käyttämällä Maple 11 -ohjelmistopakettia (katso liite 1).

Saamme järjestelmän lopulliset todennäköisyydet:

Kolmogorov-yhtälöjärjestelmästä saatujen todennäköisyyksien vertailu lopullisiin todennäköisyyksiin osoittaa, että virheet ovat tasavertaisia:

Nuo. tarpeeksi pieni. Tämä vahvistaa saatujen tulosten oikeellisuuden.

2.3 Järjestelmän suorituskykyindikaattoreiden laskeminen lopullisilla todennäköisyyksillä

Etsitään jonojärjestelmän suorituskykyindikaattorit.

Ensin laskemme sovellusvirran vähentyneen intensiteetin:

1) Todennäköisyys kieltäytyä hakemuksen palvelusta, ts. todennäköisyys, että asiakas jättää järjestelmän palvelematta. Tässä tapauksessa asiakkaalta evätään palvelu, jos kaikki 2 kanavaa ovat varattu ja jono on maksimi täynnä (eli 4 henkilöä jonossa), tämä vastaa järjestelmän tilaa S 6 . Koska todennäköisyys järjestelmän siirtymiselle tilaan S6 on P 6, silloin

4) Keskimääräinen jonon pituus, ts. jonossa olevien pyyntöjen keskimääräinen määrä on yhtä suuri kuin jonossa olevien pyyntöjen määrän ja vastaavan tilan todennäköisyyden tulojen summa.

5) Keskimääräinen aika, jonka sovellus viettää jonossa, määritetään Littlen kaavalla:

3. QS:n simulaatiomallinnus

3.1 QS-simulointimenetelmän algoritmi (askel askeleelta lähestymistapa)

Tarkastellaan kaksikanavaista jonojärjestelmää (n = 2), jonka jonon enimmäispituus on kuusi (m = 4). QS vastaanottaa yksinkertaisimman sovellusvirran, jonka keskimääräinen intensiteetti on λ = 4,8 ja eksponentiaalinen aikajakauman laki sovellusten saapumisen välillä. Järjestelmässä palvelevien pyyntöjen virta on yksinkertaisin, jonka keskimääräinen intensiteetti on μ = 2 ja palveluaikajakauman eksponentiaalinen laki.

QS:n simuloimiseksi käytämme yhtä tilastollisen mallinnuksen menetelmistä - simulaatiomallinnusta. Käytämme vaiheittaista lähestymistapaa. Tämän lähestymistavan ydin on, että järjestelmän tiloja tarkastellaan seuraavina ajanhetkenä, joiden välinen askel on riittävän pieni, jotta sen aikana ei tapahdu enempää kuin yksi tapahtuma.

Valitaan aikavaihe (). Sen tulisi olla paljon lyhyempi kuin hakemuksen keskimääräinen vastaanottoaika () ja sen keskimääräinen palveluaika (), ts.

Missä (3.1.1)

Ehdon (3.1.1) perusteella määritämme aikaaskeleen.

Hakemuksen vastaanottoaika QS:ssä ja sen palveluaika on satunnaismuuttujia. Siksi QS:ää simuloitaessa ne lasketaan satunnaislukujen avulla.

Harkitse hakemuksen vastaanottamista yhteiseen markkinajärjestelyyn. Todennäköisyys, että tilaus saapuu QS:ään välin aikana, on yhtä suuri: . Luodaan satunnaisluku , ja jos , katsomme, että tässä vaiheessa pyyntö tuli järjestelmään, jos , ei sitten mennyt sisään.

Tämä tehdään ohjelmassa on pyydetty () . Otamme aikavälin vakioksi 0,0001, jolloin suhde on 10 000. Jos pyyntö vastaanotetaan, se saa arvon "true", muuten arvo on "false".

bool isRequested()

double r = R.SeuraavaKaksois();

jos (r< (timeStep * lambda))

Tarkastellaan nyt sovelluksen palvelua QS:ssä. Sovelluksen palveluaika järjestelmässä määräytyy lausekkeella , missä on satunnaisluku. Ohjelmassa palveluaika määritetään toiminnolla GetServiceTime () .

double GetServiceTime()

double r = R.SeuraavaKaksois();

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

Simulointimenetelmän algoritmi voidaan muotoilla seuraavasti. QS:n aukioloajat ( T) on jaettu aikavaiheisiin dt, jokainen niistä suorittaa sarjan toimintoja. Ensin määritetään järjestelmän tilat (varatut kanavat, jonon pituus), sitten funktion avulla on pyydetty () , määritetään, vastaanotettiinko pyyntö tässä vaiheessa vai ei.

Jos vastaanotetaan ja samalla on ilmaisia ​​kanavia, käytä toimintoa GetServiceTime () luomme hakemuksen käsittelyajan ja otamme sen käyttöön. Jos kaikki kanavat ovat varattuja ja jonon pituus on alle 4, asetamme pyynnön jonoon; jos jonon pituus on 4, pyyntö evätään.

Siinä tapauksessa, että tässä vaiheessa pyyntöä ei vastaanotettu ja palvelukanava oli vapaa, tarkistamme, onko jonoa. Jos on, laitamme pyynnön huoltojonosta ilmaiseen kanavaan. Tehtyjen toimintojen jälkeen varattujen kanavien palveluaika pienenee askelarvolla dt .

Kun aika on kulunut T ts. QS:n toiminnan mallintamisen jälkeen lasketaan järjestelmän suorituskykyindikaattorit ja tulokset näytetään näytöllä.

3.2 Ohjelman vuokaavio

Kuvatun algoritmin toteuttavan ohjelman lohkokaavio on esitetty kuvassa. 5.

Riisi. 5. Ohjelman vuokaavio

Kirjoitetaanpa joitain lohkoja tarkemmin.

Lohko 1. Parametrien alkuarvojen asettaminen.

Satunnainen R; // Satunnaislukugeneraattori

julkinen uint maxQueueLength; // Jonon enimmäispituus

julkinen uint channelCount; // Järjestelmän kanavien lukumäärä

julkinen kaksinkertainen lambda; // Saapuvien pyyntöjen virran intensiteetti

julkinen kaksinkertainen mu; // Pyynnön palveluvirran intensiteetti

julkinen kaksinkertainen aikaStep; // Aika askel

julkinen double timeOfFinishProcessingReq; // Pyynnön käsittelyn päättymisaika kaikissa kanavissa

julkinen double timeInQueue; // QS:n käyttämä aika jonossa olevissa tiloissa

julkinen kaksinkertainen käsittelyaika; // Järjestelmän ajoaika

julkinen kaksinkertainen totalProcessingTime; // Huoltopyyntöjen kokonaisaika

julkinen uint requestEntryCount; // Vastaanotettujen pyyntöjen määrä

julkinen uint hylättyRequestCount; // Hylättyjen hakemusten määrä

julkinen uint hyväksyttyRequestCount; // Toimitettujen pyyntöjen määrä

uint queueLength; // Jonon pituus //

QS-tiloja kuvaava tyyppi

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

SysCondition currentSystemCondition; // Järjestelmän nykyinen tila

Järjestelmän tilojen asettaminen. Otetaan 7 eri tilaa tälle 2-kanavaiselle järjestelmälle: S 0 , S 1 . S 6. QS on tilassa S 0, kun järjestelmä on vapaa; S 1 – vähintään yksi kanava on vapaa; tilassa S2, kun kaikki kanavat ovat varattuja ja jonossa on tilaa; tilassa S6 kaikki kanavat ovat varattuja ja jono on saavuttanut maksimipituuden (queueLength = 4).

Määritämme järjestelmän nykyisen tilan funktion avulla Hanki ehto()

SysCondition GetCondition()

SysCondition p_currentCondit = SysCondition.S0;

int busyChannelCount = 0;

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

jos (FinishProcessingReq[i] > 0)

busyChannelCount++;

p_virtatila += k * (i + 1);

jos (busyChannelCount > 1)

(p_nykyinentila++;)

return p_currentCondit + (int) QueueLength;

Muutos QS-viipymisajassa valtioissa, joiden jonon pituus on 1, 2, 3, 4. Tämä toteutetaan seuraavalla koodilla:

jos (jonon pituus > 0)

timeInQueue += timeStep;

jos (jonon pituus > 1)

(timeInQueue += timeStep;)

On olemassa sellainen toiminto kuin palvelupyynnön sijoittaminen ilmaiseen kanavaan. Kaikki kanavat skannataan ensimmäisestä alkaen, kun timeOfFinishProcessingReq-ehto täyttyy [ i ] <= 0 (kanava on ilmainen), siihen lähetetään hakemus, ts. pyynnön käsittelyn päättymisaika luodaan.

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

if (timeOfFinishProcessingReq[i]<= 0)

timeOfFinishProcessingReq[i] = GetServiceTime();

totalProcessingTime+= timeOfFinishProcessingReq[i];

Sovellusten palvelu kanavissa mallinnetaan koodilla:

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

jos (FinishProcessingReq[i] > 0)

timeOfFinishProcessingReq[i] -= timeStep;

Simulointimenetelmän algoritmi on toteutettu C#-ohjelmointikielellä.

3.3 Laskenta QS suorituskykyindikaattorit perustuvat sen simuloinnin tulokset

Tärkeimmät indikaattorit ovat:

1) Todennäköisyys kieltäytyä hakemuksen tiedoksiannosta, ts. todennäköisyys, että asiakas jättää järjestelmän käyttämättä. Tässä tapauksessa asiakkaalta evätään palvelu, jos kaikki 2 kanavaa ovat varattuja ja jono on mahdollisimman täynnä (eli 4 henkilöä jonossa). Vian todennäköisyyden selvittämiseksi jaetaan aika, jonka QS pysyy jonon 4 tilassa, järjestelmän kokonaisajalla.

2) Suhteellinen suorituskyky on järjestelmän palvelemien saapuvien pyyntöjen keskimääräinen osuus.

3) Absoluuttinen suorituskyky on keskimääräinen palveltujen sovellusten lukumäärä aikayksikköä kohti.

4) Jonon pituus, ts. jonossa olevien hakemusten keskimääräinen määrä. Jonon pituus on yhtä suuri kuin jonossa olevien ihmisten määrän ja vastaavan tilan todennäköisyyden tulojen summa. Löydämme tilojen todennäköisyydet tässä tilassa olevan QS-ajan suhteena järjestelmän kokonaistoimintaaikaan.

5) Keskimääräinen aika, jonka sovellus viettää jonossa, määräytyy Littlen kaavan mukaan

6) Keskimääräinen varattujen kanavien määrä määritellään seuraavasti:

7) Niiden sovellusten prosenttiosuus, joilta palvelu evättiin, saadaan kaavalla

8) Palveltujen pyyntöjen prosenttiosuus saadaan kaavasta

3.4 Tulosten tilastollinen käsittely ja niiden vertailu analyyttisen mallinnuksen tuloksiin

Koska suoritusindikaattorit saadaan QS-mallinnuksen tuloksena rajalliseksi ajaksi, ne sisältävät satunnaiskomponentin. Siksi luotettavampien tulosten saamiseksi on tarpeen suorittaa niiden tilastollinen käsittely. Tätä varten arvioimme niiden luottamusvälin 20 ohjelman ajon tulosten perusteella.

Arvo putoaa luottamusväliin, jos epäyhtälö

, missä

matemaattinen odotus (keskiarvo), löydetään kaavalla

korjattu varianssi,

,

N =20 - juoksujen määrä

- luotettavuus. klo ja N =20 .

Ohjelman tulos näkyy kuvassa. 6.

Riisi. 6. Ohjelman tyyppi

Eri mallinnusmenetelmillä saatujen tulosten vertailun helpottamiseksi esitämme ne taulukon muodossa.

Taulukko 2.

Indikaattorit QS-tehokkuus	tuloksia analyyttinen mallinnus	tuloksia simulaatiomallinnus (viimeinen vaihe)	Simulaatiotulokset
			Bottom line luottamusmies intervalli	Yläraja luottamusmies intervalli
Epäonnistumisen todennäköisyys		0,174698253017626	0,158495148639101	0,246483801571923
Suhteellinen kaistanleveys		0,825301746982374	0,753516198428077	0,841504851360899
Absoluuttinen kaistanleveys		3,96144838551539	3,61687775245477	4,03922328653232
Keskimääräinen jonon pituus		1,68655313447018	1,62655862750852	2,10148609204869
Keskimääräinen aika, jonka sovellus viettää jonossa	0,4242558575	0,351365236347954	0,338866380730942	0,437809602510145
Keskimäärin varatut kanavat		1,9807241927577	1,80843887622738	2,01961164326616

Taulukosta. Kuva 2 osoittaa, että QS:n analyyttisessä mallinnuksessa saadut tulokset osuvat simulaation tuloksista saadun luottamusväliin. Eli eri menetelmillä saadut tulokset ovat yhdenmukaisia.

Johtopäätös

Tässä artikkelissa tarkastellaan tärkeimpiä menetelmiä QS-mallinnukseen ja niiden suoritusindikaattoreiden laskemiseen.

Kaksikanavaisen QS:n, jonka jonon pituus on enintään 4, simulointi suoritettiin Kolmogorov-yhtälöiden avulla ja löydettiin järjestelmän tilojen lopulliset todennäköisyydet. Sen tehokkuuden indikaattorit lasketaan.

Tällaisen QS:n toiminnan simulointi on suoritettu. C#-ohjelmointikielessä on käännetty ohjelma, joka simuloi sen toimintaa. Suoritettiin sarja laskelmia, joiden tulosten perusteella löydettiin järjestelmän tehokkuusindikaattoreiden arvot ja suoritettiin niiden tilastollinen käsittely.

Simulaatiomallinnuksen aikana saadut tulokset ovat yhdenmukaisia ​​analyyttisen mallinnuksen tulosten kanssa.

Kirjallisuus

1. Wentzel E.S. Toimintatutkimus. – M.: Bustard, 2004. – 208 s.

2. Volkov I.K., Zagoruiko E.A. Toimintatutkimus. - M .: Kustantaja MSTU im. N.E. Bauman, 2002. - 435 s.

3. Volkov I.K., Zuev S.M., Tsvetkova G.M. satunnaisia ​​prosesseja. - M .: Kustantaja MSTU im. N.E. Bauman, 2000. - 447 s.

4. Gmurman V.E. Opas todennäköisyysteorian ja matemaattisten tilastojen ongelmien ratkaisemiseen. - M.: Korkeakoulu, 1979. - 400 s.

5. Ivnitsky V.L. Jonoverkkojen teoria. – M.: Fizmatlit, 2004. – 772 s.

6. Tutkimustoiminta taloudessa / toim. N.Sh. Kremer. - M.: Unity, 2004. - 407 s.

7. Takha H.A. Johdatus toimintatutkimukseen. - M.: Kustantaja "Williams", 2005. - 902 s.

8. Kharin Yu.S., Malyugin V.I., Kirlitsa V.P. et al. Simuloinnin ja tilastollisen mallinnuksen perusteet. - Minsk: Design PRO, 1997. - 288 s.

Jonojärjestelmien (QS) analyyttinen tutkimus on vaihtoehtoinen lähestymistapa simulaatiomallinnukseen, ja se koostuu kaavojen hankkimisesta QS:n lähtöparametrien laskemiseksi, minkä jälkeen argumenttiarvot korvataan näihin kaavoihin kussakin yksittäisessä kokeessa.

QS-malleissa otetaan huomioon seuraavat objektit:

1) palvelupyynnöt (tapahtumat);

2) palvelulaitteet (OA) tai laitteet.

Jonoteorian käytännön tehtävä liittyy näiden objektien toimintojen tutkimiseen ja koostuu erillisistä elementeistä, joihin vaikuttavat satunnaiset tekijät.

Esimerkkinä jonoteoriassa käsitellyistä ongelmista voidaan mainita: sanomalähteen läpäisykyvyn sovittaminen tiedonsiirtokanavaan, kaupunkiliikenteen optimaalisen sujuvuuden analysointi, matkustajien odotushuoneen kapasiteetin laskeminen lentoasemalla , jne.

Pyyntö voi olla joko palvelutilassa tai palvelu odottaa -tilassa.

Palvelulaite voi olla joko varattu huoltoon tai vapaa.

QS-tilalle on tunnusomaista joukko palvelulaitteiden ja pyyntöjen tiloja. QS:n tilojen muutosta kutsutaan tapahtumaksi.

QS-malleja käytetään järjestelmässä tapahtuvien prosessien tutkimiseen sovellettaessa sovellusvirtojen syötteisiin. Nämä prosessit ovat tapahtumien sarja.

QS:n tärkeimmät lähtöparametrit

Esitys

Kaistanleveys

Palvelun kieltämisen todennäköisyys

Keskimääräinen palveluaika;

Laitteen kuormituskerroin (OA).

Sovelluksia voivat olla tilaukset tuotteiden valmistusta varten, tietokonejärjestelmässä ratkaistavia tehtäviä, asiakkaita pankeissa, kuljetuksiin saapuvia tavaroita jne. On selvää, että järjestelmään tulevien sovellusten parametrit ovat satunnaismuuttujia ja vain niiden parametrit voidaan tietää aikana tutkimusta tai suunnittelua, jakelulakeja.

Tässä suhteessa toiminnan analyysi järjestelmätasolla on pääsääntöisesti tilastollista. Jonotuksen teoria on kätevää ottaa matemaattisena mallinnustyökaluna ja käyttää jonojärjestelmiä tämän tason järjestelmien mallina.

Yksinkertaisimmat QS-mallit

Yksinkertaisimmassa tapauksessa QS on laite, jota kutsutaan palvelulaitteeksi (OA), jonka tuloissa on sovellusten jonot.

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

Riisi. 5.1. QS-malli, jossa on vikoja:

0 – pyynnön lähde;

1 - huoltolaite;

a– palvelupyyntöjen syöttövirta;

sisään on huollettujen pyyntöjen lähtövirta;

Kanssa on käyttämättömien pyyntöjen lähtövirta.

Tässä mallissa OA:n tulossa ei ole korvausakkua. Jos vaatimus saapuu lähteestä 0 sillä hetkellä, kun AA on varattu edellisen vaatimuksen hoitamiseen, niin vasta saapunut vaatimus poistuu järjestelmästä (koska sitä evättiin palvelu) ja se katoaa (virtaus Kanssa).

M o d e l o f C ja d i n s s e c r i o n s (Kuva 5.2)

Riisi. 5.2. QS-malli odotuksella

(N– 1) - akkuun mahtuvien sovellusten määrä

Tässä mallissa on korvausakku OA:n tulossa. Jos asiakas saapuu lähteestä 0 sillä hetkellä, kun varmentaja palvelee edellistä asiakasta, niin uusi saapunut asiakas menee varaajaan, jossa se odottaa toistaiseksi kunnes CA vapautuu.

RAJOITETTU PALVELUMALLI

w i d a n y (kuva 5.3)

Riisi. 5.4 Monikanavainen QS-malli, jossa on vikoja:

n- identtisten palvelulaitteiden (laitteet) määrä

Tässä mallissa ei ole yhtä OA:ta, vaan useita. Hakemukset, ellei toisin mainita, voidaan toimittaa mille tahansa ei-palvelua tarjoavalle AB:lle. Säilytystilaa ei ole, joten tämä malli sisältää kuvassa 2 esitetyn mallin ominaisuudet. 5.1: hakemuksen palvelun epääminen tarkoittaa sen peruuttamatonta menetystä (tämä tapahtuu vain, jos tämän hakemuksen saapumishetkellä kaikki OA ovat kiireisiä).

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

Riisi. 5.6. Monikanavainen QS-malli odottavalla ja palautuvalla OA:lla:

e- huoltolaitteet, jotka ovat epäkunnossa;

f– kunnostetut huoltoautot

Tällä mallilla on samat ominaisuudet kuin kuvissa 1 ja 2 esitetyt mallit. 5.2 ja 5.4 sekä ominaisuudet, jotka mahdollistavat OA:n mahdollisten satunnaisten vikojen huomioon ottamisen, jotka tässä tapauksessa siirtyvät korjauslohkoon 2, jossa ne pysyvät satunnaisesti kunnostukseen käytetyn ajan ja palaavat sitten takaisin huoltolohko 1 uudelleen.

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

OA odotusaika ja palautuminen (kuva 5.7)

Riisi. 5.7. Monikanavainen QS-malli, jossa on rajoitettu odotusaika ja OA-palautus

Tämä malli on melko monimutkainen, koska se ottaa samanaikaisesti huomioon kahden ei-yksinkertaisimman mallin ominaisuudet (kuvat 5.5 ja 5.6).

Luokittelu, peruskäsitteet, mallielementit, pääominaisuuksien laskeminen.

Ratkaistaessa kaupan, kuluttajapalvelujen, varastoinnin jne. järkevään järjestämiseen liittyviä ongelmia. erittäin hyödyllinen on tuotantorakenteen toiminnan tulkinta jonotusjärjestelmät, eli järjestelmä, jossa toisaalta syntyy jatkuvasti pyyntöjä minkä tahansa työn suorittamisesta, ja toisaalta näitä pyyntöjä tyydytetään jatkuvasti.

Jokainen SMO sisältää neljä elementtiä: saapuva stream, jono, palvelin, lähtevä stream.

vaatimus(asiakas, sovellus) on QS:ssä jokainen yksittäinen pyyntö minkä tahansa työn suorittamiseksi.

Palvelu on töiden suorittaminen saapuvan kysynnän tyydyttämiseksi. Kohdetta, joka suorittaa vaatimusten ylläpidon, kutsutaan palvelulaitteeksi (-laitteeksi) tai palvelukanavaksi.

Palveluaika on ajanjakso, jonka aikana palvelutarve täyttyy, ts. ajanjakso palvelun aloittamisesta sen valmistumiseen. Ajanjaksoa pyynnön saapumisesta järjestelmään palvelun alkamiseen kutsutaan palvelun odotusajaksi. Palvelun odotusaika yhdessä palveluajan kanssa on vaatimuksen viipymisaika järjestelmässä.

SMO:t luokitellaan eri kriteerien mukaan..

1. Palvelukanavien lukumäärän mukaan QS jaetaan yksikanavaisiin ja monikanavaisiin.

2. Odotusolosuhteista riippuen palvelun aloitusvaatimus erottaa QS:n häviöistä (epäonnistumista) ja QS:n odottamisesta.

AT QS kysynnän menetyksellä, vastaanotettu sillä hetkellä, kun kaikki laitteet ovat varattu huoltoon, hylätään, ne menetetään tälle järjestelmälle eikä niillä ole vaikutusta jatkohuoltoprosessiin. Klassinen esimerkki epäonnistuneesta järjestelmästä on puhelinkeskus – yhteyspyyntö hylätään, jos soitettava osapuoli on varattu.

Järjestelmässä, jossa on vikoja, toiminnan tehokkuuden pääominaisuus on epäonnistumisen todennäköisyys tai palvelemattomien pyyntöjen keskimääräinen osuus.

AT Yhteinen markkinajärjestely kysyntä odottaa, joka vastaanotetaan sillä hetkellä, kun kaikki laitteet ovat varattu huoltoon, ei poistu järjestelmästä, vaan asettuu jonoon ja odottaa, kunnes jokin kanavista vapautuu. Kun seuraava laite vapautetaan, yksi jonossa olevista sovelluksista hyväksytään välittömästi huollettavaksi.

Odottavan QS:n tärkeimmät ominaisuudet ovat matemaattiset odotukset jonon pituudesta ja odotusajasta.

Esimerkki odottavasta järjestelmästä on televisioiden kunnostus korjaamossa.

On olemassa järjestelmiä, jotka sijaitsevat näiden kahden ryhmän välillä ( yhdistetyt yhteiset markkinajärjestelyt). Niille on ominaista joidenkin väliehtojen olemassaolo: rajoitukset voivat olla rajoituksia palvelun alkamisen odotusaikaan, jonon pituuteen jne.

Suorituskykyominaisuuksina vian todennäköisyyttä voidaan käyttää sekä järjestelmissä, joissa on häviöitä (tai odotusajan ominaisuuksia) että järjestelmissä, joissa on odotus.

3. Palvelualan mukaan QS:t jaetaan palveluprioriteettiin ja ilman palveluprioriteettia oleviin järjestelmiin.

Pyynnöt voidaan käsitellä niiden saapumisjärjestyksessä, joko satunnaisesti tai asetettujen prioriteettien perusteella.

4. QS voi olla yksivaiheinen ja monivaiheinen.

AT yksivaihe järjestelmät, vaatimuksia palvelevat samantyyppiset kanavat (esimerkiksi saman ammatin työntekijät) siirtämättä niitä kanavasta toiseen, monivaiheinen Tällaiset siirrot ovat mahdollisia.

5. Vaatimuslähteen sijainnin mukaan QS jaetaan avoimeen (kun vaatimuksen lähde on järjestelmän ulkopuolella) ja suljettuun (kun lähde on itse järjestelmässä).

Vastaanottaja suljettu sisältää järjestelmiä, joissa tuleva vaatimusvirta on rajoitettu. Esimerkiksi työnjohtajan, jonka tehtävänä on asentaa koneita konepajaan, on huollettava ne säännöllisesti. Jokaisesta asennetusta koneesta tulee mahdollinen asennustarpeiden lähde tulevaisuudessa. Tällaisissa järjestelmissä kiertävien vaatimusten kokonaismäärä on rajallinen ja useimmiten vakio.

Jos syöttölähteellä on ääretön määrä vaatimuksia, järjestelmät kutsutaan avata. Esimerkkejä tällaisista järjestelmistä ovat kaupat, asemien lipputoimistot, satamat jne. Näissä järjestelmissä saapuvien pyyntöjen virtaa voidaan pitää rajoittamattomana.

QS-tutkimuksen menetelmät ja mallit voidaan jakaa ehdollisesti analyyttisiin ja tilastollisiin (jonoprosessien simulaatiomallinnus).

Analyyttisten menetelmien avulla on mahdollista saada järjestelmän ominaisuudet sen toiminnan parametrien joidenkin funktioiden perusteella. Tämä mahdollistaa laadullisen analyysin yksittäisten tekijöiden vaikutuksesta QS:n tehokkuuteen.

Valitettavasti vain melko rajoitettu joukko jonoteorian ongelmia voidaan ratkaista analyyttisesti. Analyyttisten menetelmien jatkuvasta kehittämisestä huolimatta monissa todellisissa tapauksissa analyyttinen ratkaisu on joko mahdotonta saada tai tuloksena syntyvät riippuvuudet osoittautuvat niin monimutkaisiksi, että niiden analysoinnista tulee itsenäinen vaikea tehtävä. Siksi, jotta voidaan soveltaa analyyttisiä ratkaisumenetelmiä, on turvauduttava erilaisiin yksinkertaistaviin oletuksiin, joita jossain määrin kompensoi mahdollisuus soveltaa lopullisten riippuvuuksien kvalitatiivista analyysiä (tässä tapauksessa tietysti on välttämätöntä, jotta tehdyt oletukset eivät vääristä todellista kuvaa prosessista).

Tällä hetkellä teoreettisesti kehittyneimmät ja kätevimmät käytännön sovelluksissa ovat menetelmät sellaisten jonoongelmien ratkaisemiseksi, joissa vaatimusvirta on yksinkertaisin ( Poisson).

Yksinkertaisimmalla virtauksella vaatimusten vastaanottotaajuus järjestelmään noudattaa Poissonin lakia, eli todennäköisyys saapua ajassa t, joka on yhtä suuri kuin k vaatimusta, saadaan kaavalla:

missä λ on virtausparametri (katso alla).

Yksinkertaisimmalla virtauksella on kolme pääominaisuutta: tavallinen, kiinteä ja ei jälkivaikutusta.

Tavallisuus virtauksella tarkoitetaan käytännössä mahdotonta vastaanottaa kahta tai useampaa vaatimusta samanaikaisesti. Esimerkiksi todennäköisyys, että useat korjaamoryhmän huoltaman koneryhmän koneet rikkoutuvat yhtä aikaa, on melko pieni.

Paikallaan nimeltään virtaus, jonka matemaattinen odotus järjestelmään saapuvien korvausten lukumäärästä aikayksikköä kohti (merkitty λ:lla) ei muutu ajassa. Näin ollen todennäköisyys sille, että tietty määrä vaatimuksia tulee järjestelmään tietyn aikavälin AT aikana, riippuu sen arvosta eikä riipu sen alkuperästä aika-akselilla.

Ei jälkivaikutuksia tarkoittaa, että järjestelmään ennen aikaa t tulevien asiakkaiden määrä ei määrää, kuinka monta asiakasta tulee järjestelmään ajassa t + Δt.

Esimerkiksi jos langankatkos tapahtuu tällä hetkellä kutomakoneessa ja kutoja poistaa sen, tämä ei ratkaise sitä, tapahtuuko näissä kutomakoneissa uusi katkeaminen seuraavana hetkenä vai ei, varsinkin. eivät vaikuta muiden koneiden rikkoutumisen todennäköisyyteen.

QS:n tärkeä ominaisuus on järjestelmän vaatimusten palveluaika. Palveluaika on pääsääntöisesti satunnaismuuttuja ja siksi sitä voidaan kuvata jakautumislain avulla. Eksponentiaalilaki on saanut suurimman levinneisyyden teoriassa ja erityisesti käytännön sovelluksissa. Tässä laissa todennäköisyysjakaumafunktiolla on muoto:

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

nuo. todennäköisyys, että palveluaika ei ylitä tiettyä arvoa t, määritetään kaavalla (1 - e -μt), jossa μ on järjestelmän vaatimusten palveluajan eksponentiaalisen lain parametri - keskiarvon käänteisluku palveluaika, ts. .

Harkitse analyyttisiä QS-malleja odotuksella(yleisin QS, jossa kaikki palveluyksiköt varattuhetkellä vastaanotetut pyynnöt asetetaan jonoon ja palvellaan palveluyksiköiden vapautuessa).

Jonotyöt ovat tyypillisiä tuotantoolosuhteissa, esimerkiksi säätö- ja korjaustöiden järjestämisessä, monikonehuollossa jne.

Yleinen ongelman kuvaus on seuraava.

Järjestelmä koostuu n palvelukanavasta. Jokainen niistä voi palvella vain yhden pyynnön kerrallaan. Järjestelmä vastaanottaa yksinkertaisimman (Poisson) vaatimusvirran parametrilla λ. Jos seuraavan pyynnön saapumishetkellä järjestelmässä on jo vähintään n pyyntöä palvelussa (eli kaikki kanavat ovat varattuja), tämä pyyntö menee jonoon ja odottaa palvelun alkamista.

Kunkin vaatimuksen palveluaika t about on satunnaismuuttuja, joka noudattaa eksponentiaalisen jakautumislakia parametrilla μ.

Kuten edellä todettiin, QS-odotus voidaan jakaa kahteen suureen ryhmään: suljettu ja avoin.

Kummankin järjestelmän toiminnan ominaisuudet antavat oman sävynsä käytetylle matemaattiselle laitteistolle. Eri tyyppisten QS-toiminnan ominaisuuksien laskenta voidaan suorittaa QS-tilojen todennäköisyyslaskennan (Erlang-kaavat) perusteella.

Koska järjestelmä on suljettu, ongelman ilmaisuun tulee lisätä ehto: saapuvien pyyntöjen virta on rajoitettu, ts. jonotusjärjestelmällä ei voi olla enempää kuin m pyyntöä samanaikaisesti (m on huollettavien objektien määrä).

Tarkasteltavana olevan järjestelmän toiminnan laatua kuvaaviksi pääkriteereiksi valitsemme: 1) keskimääräisen jonon pituuden suhteen suurimman osan vaatimuksista, jotka ovat samanaikaisesti huoltojärjestelmässä - huollettavan kohteen seisokkikerroin; 2) vapaana olevien palvelevien kanavien keskimääräisen lukumäärän suhde niiden kokonaismäärään on palvellun kanavan tyhjäkäyntisuhde.

Harkitse suljetun QS:n tarvittavien todennäköisyysominaisuuksien (suorituskykyindikaattoreiden) laskemista.

1. Todennäköisyys, että järjestelmässä on k vaatimusta, mikäli niiden määrä ei ylitä palvelulaitteiden määrää n:

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

missä

λ on vaatimusten vastaanottamisen taajuus (intensiteetti) järjestelmään yhdestä lähteestä;

Yhden vaatimuksen keskimääräinen palvelun kesto;

m - suurin mahdollinen määrä vaatimuksia, jotka ovat palvelevassa järjestelmässä samanaikaisesti;

n on palvelulaitteiden lukumäärä;

P 0 - todennäköisyys, että kaikki palvelulaitteet ovat ilmaisia.

2. Todennäköisyys, että järjestelmässä on k vaatimusta, jos niiden lukumäärä on suurempi kuin palvelulaitteiden lukumäärä:

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

missä

3. Todennäköisyys, että kaikki palvelimet ovat vapaita, määritetään ehdosta

Näin ollen

4. Palvelun aloittamista odottavien pyyntöjen keskimääräinen määrä (jonon keskimääräinen pituus):

5. Palvelua odottavien seisokkien kysyntäsuhde:

6. Todennäköisyys, että kaikki palvelulaitteet ovat varattu:

7. Palvelujärjestelmän vaatimusten keskimääräinen määrä (palveltu ja palvelua odottava):

8. Huoltovaatimusten ja palvelun odottamisen kokonaisseisokkien suhde:

9. Palvelujonon vaatimuksen keskimääräinen joutoaika:

10. Keskimääräinen ilmaisten avustajien määrä:

11. Huoltoajoneuvojen seisokkisuhde:

12. Todennäköisyys, että palvelua odottavien asiakkaiden määrä on suurempi kuin jokin luku B (todennäköisyys, että palvelujonossa on enemmän kuin B asiakasta):

Ihmistoiminnan käytännössä suuren paikan ovat jonotusprosessit, joita esiintyy uudelleenkäytettäviin järjestelmissä samantyyppisten ongelmien ratkaisemisessa. Tällaisia ​​järjestelmiä kutsutaan jonojärjestelmiksi (QS). Esimerkkejä tällaisista järjestelmistä ovat puhelinjärjestelmät, tietokonejärjestelmät, autot, ilmailu, huoltojärjestelmät, kaupat, lipputoimistot ja vastaavat.

Kukin järjestelmä koostuu tietystä määrästä palveluyksiköitä (instrumentteja, laitteita, laitteita "pisteitä, asemia), joita kutsutaan palvelukanaviksi. Kanavien lukumäärän mukaan QS jaetaan yksikanavaiseen ja monikanavaiseen. Kaavio Yksikanavaisen jonotusjärjestelmän toiminta on esitetty kuvassa 6.2.

Sovellukset eivät yleensä tule järjestelmään säännöllisesti, vaan satunnaisesti muodostaen satunnaisen sovellusvirran (vaatimukset). Itse kunkin vaatimuksen palvelu voi kestää joko tietyn ajan tai useammin määräämättömän ajan. Satunnainen luonne johtaa siihen, että QS latautuu epätasaisesti: joinakin ajanjaksoina sovelluksia kertyy hyvin suuri määrä (ne joko joutuvat jonoon tai jättävät QS:n käyttämättä), kun taas toisina jaksoina QS toimii alikuormituksella. tai on käyttämättömänä.

Riisi. 6.2.

Jonojärjestelmien tutkimuksen tarkoituksena on analysoida niiden toiminnan laatua ja tunnistaa mahdollisuuksia sen parantamiseksi. Samaan aikaan "toiminnan laadun" käsitteellä on kussakin yksittäisessä tapauksessa oma erityinen merkitys, ja se ilmaistaan ​​erilaisilla määrällisillä indikaattoreilla. Esimerkiksi sellaiset kvantitatiiviset indikaattorit kuten palvelujonon koko, keskimääräinen palveluaika, palvelun odotus tai vaatimuksen löytäminen palvelujärjestelmästä, palvelulaitteiden tyhjäkäyntiaika; luottaa siihen, että kaikki järjestelmän vastaanottamat pyynnöt käsitellään.

Jonotusjärjestelmän toiminnan laadulla ei siis ymmärretä tietyn työn, jota varten pyyntö vastaanotettiin, suorituksen laatua, vaan palvelutarpeen tyytyväisyyden astetta.

Jonoteorian aiheena on matemaattisten mallien rakentaminen, jotka yhdistävät QS:n annetut toimintaolosuhteet (kanavien lukumäärä, niiden suorituskyky, sovellusvirran luonne jne.) QS:n suoritusindikaattoreihin, jotka kuvaavat sen kyky selviytyä sovellusten virtauksesta.

Jonojärjestelmien luokittelu

Ensimmäinen ominaisuus, joka mahdollistaa jonotustehtävien luokittelun, on palvelevan järjestelmän vastaanottamien vaatimusten käyttäytyminen sillä hetkellä, kun kaikki koneet ovat varattuina.

Joissakin tapauksissa vaatimus, joka tulee järjestelmään aikana, jolloin kaikki koneet ovat varattuina, ei voi odottaa niiden vapauttamista ja jättää järjestelmän palvelematta, ts. vaatimus menetetään tietylle palvelujärjestelmälle. Tällaisia ​​palvelujärjestelmiä kutsutaan häviöllisiksi järjestelmiksi ja niiden perusteella muotoiltuja ongelmia häviöllisten järjestelmien palveluongelmiksi.

Jos taas järjestelmään saapunut pyyntö menee jonoon ja odottaa laitteen vapautumista, niin tällaisia ​​järjestelmiä kutsutaan odottaviksi järjestelmiksi ja vastaavia tehtäviä palvelutehtäviksi odottavissa järjestelmissä. Odottava QS on jaettu eri tyyppeihin riippuen siitä, miten jono on järjestetty: rajoitetulla tai rajoittamattomalla jonopituudella, rajoitetulla odotusajalla jne.

QS:t eroavat myös niiden vaatimusten lukumäärästä, jotka voivat olla samanaikaisesti palvelevassa järjestelmässä. Varaa:

• 1) järjestelmät, joilla on rajoitettu määrä vaatimuksia;
• 2) järjestelmät, joissa on rajoittamaton vaatimusvirta.

Järjestelmän sisäisen palvelun organisoinnin muodoista riippuen on:

• 1) järjestelmät tilatuilla palveluilla;
• 2) järjestelmät, joiden palvelu on häiriintynyt.

Tärkeä askel QS-tutkimuksessa on tutkittavaa prosessia kuvaavien kriteerien valinta. Valinta riippuu tutkittavien ongelmien tyypistä, ratkaisun tavoitteesta.

Useimmiten käytännössä on järjestelmiä, joissa vaatimusvirta on lähellä yksinkertaisinta ja palveluaika noudattaa eksponentiaalista jakautumislakia. Nämä järjestelmät ovat kehittyneimmillään jonoteoriassa.

Yrityksen olosuhteissa ovat tyypillisiä tehtävät, joissa on odotus, rajallinen määrä palvelulaitteita, rajoitettu vaatimusvirta ja sekava huolto.

23. lokakuuta 2013 klo 14:22

Squeak: Modeling Queuing Systems

• ohjelmointi,
• OOP,
• Rinnakkaisohjelmointi

Habrelta on hyvin vähän tietoa sellaisesta ohjelmointikielestä kuin Squeak. Yritän puhua siitä jonojärjestelmien mallinnuksen yhteydessä. Näytän kuinka kirjoittaa yksinkertainen luokka, kuvailla sen rakennetta ja käyttää sitä ohjelmassa, joka palvelee pyyntöjä useiden kanavien kautta.

Muutama sana Squeakista

Squeak on Smalltalk-80-ohjelmointikielen avoin, monialustainen toteutus, jossa on dynaaminen kirjoitus ja roskakeräin. Käyttöliittymä on melko spesifinen, mutta melko kätevä virheenkorjaukseen ja analysointiin. Squeak on täysin OOP-konseptin mukainen. Kaikki koostuu esineistä, jopa rakenteista jos-niin-muu, jonkin aikaa toteutettu heidän avullaan. Koko syntaksi tiivistyy viestin lähettämiseen objektille muodossa:

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

Mikä tahansa menetelmä palauttaa aina objektin ja sille voidaan lähettää uusi viesti.
Squeakia käytetään usein prosessien mallintamiseen, mutta sitä voidaan käyttää myös työkaluna multimediasovellusten ja erilaisten koulutusalustojen luomiseen.

Jonotusjärjestelmät

Jonojärjestelmät (QS) sisältävät yhden tai useamman kanavan, joka käsittelee sovelluksia useista lähteistä. Kunkin pyynnön käsittelyaika voi olla kiinteä tai mielivaltainen, samoin kuin niiden saapumisvälit. Se voi olla puhelinkeskus, pesula, myymälän kassat, konekirjoitustoimisto jne. Se näyttää suunnilleen tältä:

QS sisältää useita lähteitä, jotka tulevat yhteiseen jonoon ja lähetetään huoltoon prosessointikanavien vapautuessa. Todellisten järjestelmien erityispiirteistä riippuen malli voi sisältää eri määrän pyyntölähteitä ja palvelukanavia ja siinä voi olla erilaisia ​​rajoituksia jonon pituudelle ja siihen liittyvälle mahdollisuudelle pyyntöjen (epäonnistumista) menettämiseen.

QS:ää mallinnettaessa ratkaistaan ​​yleensä jonojen keski- ja maksimipituuden, palvelutaajuuden, keskimääräisen kanavakuormituksen ja niiden lukumäärän määrittäminen. Tehtävästä riippuen malli sisältää ohjelmistolohkoja tarvittavan tilastollisen tiedon keräämiseen, keräämiseen ja käsittelyyn prosessien käyttäytymisestä. QS-analyysissä yleisimmin käytetyt tapahtumavirtamallit ovat säännöllinen ja Poisson. Säännöllisille on ominaista sama aika tapahtumien välillä, kun taas Poissonin tapauksille on ominaista satunnainen.

Vähän matematiikkaa

Poisson-virtaukselle tapahtumien määrä X kuuluvat pituusväliin τ (tau) pisteen vieressä t, jaettu Poissonin lain mukaan:
missä a (t, τ)- aikavälillä esiintyvien tapahtumien keskimääräinen lukumäärä τ .
Keskimääräinen tapahtumien lukumäärä aikayksikköä kohti on yhtä suuri kuin λ(t). Siksi tapahtumien keskimääräinen määrä aikaväliä kohti τ , ajan hetken vieressä t, on yhtä suuri kuin:

Aika T kahden tapahtuman välillä λ(t) = const = λ jaetaan lain mukaan:
Satunnaismuuttujan jakautumistiheys T näyttää:
Saadaksesi näennäissatunnaiset Poisson-sekvenssit aikaväleistä t i ratkaise yhtälö:
missä r i on satunnaisluku, joka on jakautunut tasaisesti aikavälille.
Meidän tapauksessamme tämä antaa ilmaisun:

Luomalla satunnaislukuja voit kirjoittaa kokonaisia ​​nitoja. Tässä välissä tasaisesti jakautuneiden kokonaislukujen luomiseksi käytämme seuraavaa algoritmia:
missä R i- toinen satunnainen kokonaisluku;
R- jokin suuri alkuluku (esim. 2311);
K- kokonaisluku - välin yläraja, esimerkiksi 2 21 = 2097152;
rem- operaatio jäännöksen saamiseksi kokonaislukujen jaosta.

Alkuarvo R0 asetetaan yleensä mielivaltaisesti esimerkiksi ajastimen lukemilla:
Aika yhteensäSekuntia
Saadaksemme numerot, jotka jakautuvat tasaisesti aikavälille, käytämme kielioperaattoria:

Rand luokka

Saadaksemme satunnaislukuja, jotka jakautuvat tasaisesti aikavälille, luomme luokan - reaalilukujen generaattorin:

Float variableWordSubclass: #Rand "luokan nimi" ilmentymäVariableNames: "" "instanssimuuttujat" classVariableNames: "R" "luokkamuuttujat" poolSanakirjat: "" "yleiset sanakirjat" luokka: "Esimerkki" "luokan nimi"
Menetelmät:

"Alustus" init R:= Aika totalSeconds.next "Seuraava näennäissatunnaisluku" next R:= (R * 2311 + 1) rem: 2097152. ^(R/2097152) asFloat
Aseta anturin alkutila lähettämällä viesti Rand init.
Saat toisen satunnaisluvun lähettämällä Rand seuraavaksi.

Hakemuksen käsittelyohjelma

Tehdään siis yksinkertaisena esimerkkinä seuraava. Oletetaan, että meidän on simuloitava säännöllisen pyyntövirran ylläpito yhdestä lähteestä satunnaisella aikavälillä pyyntöjen välillä. On olemassa kaksi eri suorituskykyistä kanavaa, jotka mahdollistavat sovellusten huollon 2 ja 7 aikayksikössä. Jokaisen kanavan palvelemien pyyntöjen määrä on rekisteröitävä 100 aikayksikön välein.

Squeak Code

"Väliaikaisten muuttujien ilmoittaminen" | proc1 proc2 t1 t2 s1 s2 sysPrioriteettijono jatka r | "Alkumuuttujan asetukset" Rand init. SysTime:= 0. s1:= 0. s2:= 0. t1:= -1. t2:= -1. jatka:=totta. sysPriority:= Prosessori aktiivinen Prosessin prioriteetti. "Nykyinen prioriteetti" -jono:= Semafori uusi. "Claim Queue Model" "Luoprosessi – kanavamalli 1" s1:= s1 + 1. proc1 suspend."Keskeytä prosessi odottaa palvelun lopettamista" ].proc1:= nil."Poista viittaus prosessiin 1" ]priority: (sysPriority + 1)) jatka. "Uusi prioriteetti on suurempi kuin tausta" "Luo prosessi - kanavamalli 2" .proc2:= nolla.] prioriteetti: (sysPriority + 1)) jatka. "Jatkuu pääprosessin ja lähdemallin kuvausta" whileTrue: [ r:= (Rand next * 10) pyöristetty. (r = 0) josTrue: . ((SysTime rem: r) = 0) ifTrue: . "Lähetä pyyntö" "Palveluprosessin kytkin" (t1 = SysTime) ifTrue: . (t2 = SysTime) ifTrue: . SysTime:= SysTime + 1. "Mallin aika tikittää" ]. "Näytä pyyntölaskurin tila" PopUpMenu inform: "proc1: ",(s1 printString),", proc2: ",(s2 printString). jatka:= false.

Käynnistettäessä näemme, että prosessi 1 onnistui käsittelemään 31 pyyntöä ja 2 vain 11: