Matemaattiset mallit yksinkertaisimmista jonojärjestelmistä. Yksinkertaisimmat jonojärjestelmät, käyttöesimerkkejä taloudellisten ongelmien ratkaisemisessa

Tehtävä 1. Lähetyskonsoli vastaanottaa pyyntövirran, joka on toisen asteen Erlang-kulku. Levitysvirran intensiteetti on 6 levitystä tunnissa. Jos lähettäjä poistuu konsolista satunnaisella hetkellä, hänen on palattava konsoliin ensimmäisellä seuraavalla pyynnöstä. Etsi seuraavan pyynnön odotusajan jakautumistiheys ja piirrä sen kaavio. Laske todennäköisyys, että lähettäjä voi olla poissa 10-20 minuuttia. Ratkaisu. Koska toisen asteen Erlang-virtaus on kiinteä virtaus, jolla on rajoitettu jälkivaikutus, niin Palm-kaava pätee siihen

missä f1(θ)- ensimmäisen lähimmän tapahtuman odotusajan todennäköisyysjakauman tiheys;
λ - virtauksen intensiteetti;
- virtausjärjestys;
(θ) on todennäköisyysjakaumafunktio ajalle, joka on kahden vierekkäisen tapahtuman välillä Erlangin järjestyksessä (E).
Tiedetään, että virtauksen E jakautumisfunktiolla on muoto

. (2)

Tehtävän ehtojen mukaan sovellusten kulku on Erlang, kertaluokkaa =2. Sitten (1) ja (2) saamme
.
Viimeisestä suhteesta λ=6 saamme

f1(θ)=3e-6θ(1+6θ), θ≥0. (3)

Piirretään funktio f1(θ) . klo θ <0 meillä on f1(θ) =0 . klo θ =0 , f1(0)=3. Harkitse rajaa

Tyypin epäselvyyden paljastamisen rajaa laskettaessa käytettiin L'Hopital-sääntöä. Tutkimuksen tulosten perusteella rakennamme funktiosta graafin f1(θ) (Kuva 1).

Kiinnitetään huomiota tehtävän tekstin ajan mittasuhteisiin: intensiteetille nämä ovat sovelluksia tunnissa, ajalla, minuutteissa. Siirrytään yhteen aikayksikköön: 10 minuuttia = 1/6 tuntia, 20 minuuttia = 1/3 tuntia. Näille arvoille voidaan laskea f1(θ) ja tarkentaa käyrän luonnetta

Nämä ordinaatit on esitetty kaaviossa vastaavien käyräpisteiden yläpuolella.
Todennäköisyysteorian aikana tiedetään, että todennäköisyys osua satunnaismuuttujaan X segmenttiin [α, β] on numeerisesti yhtä suuri kuin todennäköisyystiheyskäyrän alla oleva pinta-ala f(x). Tämä alue ilmaistaan ​​määrätyllä integraalilla

Siksi haluttu todennäköisyys on yhtä suuri kuin

Tämä integraali voidaan helposti laskea osittain, jos laitamme
U=1+6θ ja dV = e-69dθ. Sitten dU=6dθ ja V= .
Käyttämällä kaavaa saamme

Vastaus: todennäköisyys, että lähettäjä voi olla poissa 10-20 minuuttia, on 0,28.

Tehtävä 2. Näyttelyhuoneessa on 5 näyttöä. Käyttäjävirta on yksinkertaisin. Esittelysalissa vierailee keskimäärin 140 käyttäjää päivässä. Yhden käyttäjän tietojen käsittelyaika yhdellä näytöllä jakautuu eksponentiaalisen lain mukaan ja on keskimäärin 40 minuuttia. Selvitä, onko hallilla paikallaan oleva toimintatila; todennäköisyys, että käyttäjä löytää kaikki näytöt varattuina; käyttäjien keskimääräinen määrä esittelytilassa; jonossa olevien käyttäjien keskimääräinen määrä; keskimääräinen tyhjäkäynnin näyttöaika; käyttäjän keskimääräinen näyttöhuoneessa viettämä aika. Ratkaisu. Tehtävässä tarkasteltu QS kuuluu monikanavaisten järjestelmien luokkaan, joissa on rajoittamaton jono. Kanavien määrä =5. Etsitään sovellusvirran λ-intensiteetti: missä (tuntia) - saapuvan käyttäjävirran keskimääräinen aika kahden peräkkäisen sovelluksen välillä. Sitten käyttäjä/tunti

Selvitetään - palveluvirran intensiteetti: , jossa M[T service]=40 min=0,67 tuntia – keskimääräinen palveluaika yhdelle käyttäjälle yhdellä näytöllä,

sitten käyttäjä/tunti

Siten tämän järjestelmän luokitin on muotoa CMO (5, ∞; 5,85; 1,49).
Laske QS-kuormituskerroin . Tiedetään, että tämän luokan QS:llä on paikallaan pysyvä tila, jos järjestelmän kuormituskertoimen suhde kanavien lukumäärään on pienempi kuin yksi. Tämän suhteen löytäminen
.
Siksi kiinteä järjestelmä on olemassa. Rajatilan todennäköisyysjakauma lasketaan kaavoilla

Koska =5, meillä on

Lasketaan P* - todennäköisyys, että käyttäjä löytää kaikki näytöt varattuina. Ilmeisesti se on yhtä suuri kuin tällaisten tapahtumien todennäköisyyksien summa: kaikki näytöt ovat varattuja, jonoa ei ole (p5); kaikki näytöt varattu, yksi käyttäjä jonossa (p6); kaikki näytöt ovat varattuja, kaksi käyttäjää on jonossa (p7) ja niin edelleen. Koska kokonaiselle tapahtumaryhmälle näiden tapahtumien todennäköisyyksien summa on yhtä suuri kuin yksi, niin yhtälö

P * \u003d p5 + p6 + p7 + ... \u003d 1 - ro - p1 - p2 - p3 - p4.

Etsitään nämä todennäköisyydet: ro=0,014; p1=3,93*0,014; p2=7,72*0,014; p3=10,12*0,014; p4=9,94*0,014.
Ottamalla yhteisen tekijän suluista saamme
P*=1-0,0148*(1+3,93+7,72+10,12+9,94)=1-0,014*32,71=1-0,46=0,54.
Käytätkö kaavoja suoritusindikaattoreiden laskemiseen? löytö:

• 1. jonossa olevien käyttäjien keskimääräinen määrä

2. käyttäjien keskimääräinen määrä esittelytilassa

3. Keskimääräinen ilmaisen näytön odotusaika

4. keskimääräinen aika, jonka käyttäjä viettää esittelytilassa

Vastaus: näyttöhuoneen kiinteä toimintatila on olemassa ja sille on tunnusomaista seuraavat indikaattorit R*= 0,54; käyttäjä; käyttäjä; ; .

Tehtävä 3. kaksikanavaiseen järjestelmään jonotus(QS) vikojen kanssa saapuu kiinteä Poisson-sovellusvirta. Kahden peräkkäisen pyynnön saapumisaika jaetaan eksponentiaalisen lain mukaan parametrilla λ=5 pyyntöä minuutissa. Jokaisen pyynnön huollon kesto on 0,5 min. Etsi Monte Carlo -menetelmällä keskimääräinen huollettujen pyyntöjen määrä 4 minuutin ajalta. Vihje: tee kolme testiä. Ratkaisu. Kuvataan tietyn QS:n toiminnan tilastollinen mallinnus aikakaavioiden avulla. Otetaan käyttöön seuraava aika-akseleiden merkintä:
Vx- saapuva sovellusvirta täällä ti- hakemusten vastaanottohetki; Ti- kahden peräkkäisen sovelluksen väliset aikavälit. Se on selvää ti=ti-1 +Ti.
K1 - ensimmäinen palvelukanava;
K2-toinen palvelukanava; tässä aika-akselin paksut viivat edustavat kanavan varattuja aikavälejä. Jos molemmat kanavat ovat vapaita, pyyntö palvellaan kanavalla K1, jos se on varattu, pyyntö palvelee kanavaa K2.
Jos molemmat kanavat ovat varattuja, pyyntö jättää QS:n palvelematta.
Out OB - lähtevä huollettujen pyyntöjen virta.
Out PT on QS-vioista johtuvien kadonneiden pyyntöjen lähtevä virta (molemmat kanavat ovat varattuja).
Tilastollinen testaus jatkuu tietyn ajan. Ilmeisesti kaikki ylityöt tmax edellyttää pyynnön pudottamista lähtevään streamiin Out PT. Joten kuvassa 3 hakemus nro 10, joka tuli järjestelmään tuolloin t10, ei ole aikaa tarjoilla tähän hetkeen asti tmax, koska t10+Tmont.>tmax. Siksi ilmainen kanava K1 ei hyväksy sitä palveluun, ja se palautetaan Out PT:hen, jolloin se vastaanottaa kieltäytymisen.

Riisi. 3

Ajoituskaavioista voidaan nähdä, että intervallien mallintaminen on välttämätöntä Ti. Käytämme käänteisfunktioiden menetelmää. Koska satunnaismuuttuja Ti jaetaan eksponentiaalisen lain mukaan parametrin kanssa λ =5, silloin jakautumistiheydellä on muoto f(τ) = 5е-5τ. Sitten arvo F(Ti) todennäköisyysjakaumafunktion määrittää integraali

.

Tiedetään, että jakelufunktion alue F(T) on leikkaus. Valitsemme luvun satunnaislukutaulukosta ja määritämme Ti tasa-arvosta, mistä. Kuitenkin, jos. Siksi voit saada toteutukset välittömästi satunnaislukutaulukosta. Näin ollen
e-5Ti= ri, tai -5Ti= lnri, missä . On kätevää syöttää laskelmien tulokset taulukkoon.
Testiä nro 1 varten satunnaisluvut otettiin liitteestä 2 alkaen ensimmäisen rivin ensimmäisestä numerosta. Lisänäytteenotto suoritettiin riveittäin. Tehdään vielä kaksi testiä.
Kiinnitä huomiota satunnaislukujen valintaan liitteen 2 taulukosta, jos testissä nro 1 viimeinen satunnaisluku hakemukselle nro 16 oli 0,37 (ensimmäinen satunnaisluku toisella rivillä), niin testi nro 2 alkaa seuraava satunnaisluku 0,54 . Koe 2 sisältää viimeisen satunnaisluvun 0,53 (viides numero kolmannella rivillä). Siksi kolmas testi alkaa numerolla 0.19. Yleensä samassa testisarjassa satunnaisluvut taulukosta valitaan ilman aukkoja ja lisäyksiä tietyssä järjestyksessä, esimerkiksi riveissä.

Taulukko 1. TESTI #1

Hakemus nro i	Sl. määrä ri		-In ri Ti	Hakemuksen vastaanottohetki ti=ti-1+Ti	Palveluajan päättyminen. ti+0,50		Sovelluslaskuri
					K1

Taulukko 2 TESTI #2

Hakemus nro i	Sl. määrä ri		-In ri Ti	Hakemuksen vastaanottohetki ti=ti-1+Ti	Palveluajan päättyminen. ti+0,50		Sovelluslaskuri

Taulukko #3 TESTI #3

Hakemus nro i		Sl. määrä ri		-In ri Ti	Hakemuksen vastaanottohetki ti=ti-1+Ti	Palveluajan päättyminen. ti+0,50		Sovelluslaskuri
						K1

Siten kolmen testin tulosten mukaan huollettujen sovellusten määrä oli vastaavasti: x1=9, x2=9, x3=8. Etsi huollettujen pyyntöjen keskimääräinen määrä:

Vastaus: QS:n keskimääräinen hakemusten määrä neljässä minuutissa on 8,6(6).

Tavoitteet

Jonoteoriaksi tai jonoteoriaksi kutsuttujen jonotiedon perusteet ovat tärkeä osa tuotannon johtamisen teoriaa. Jonot ovat yleisiä. He voivat pukeutua univormuihin odottaessaan auton korjausta autokorjaamossa tai opiskelijat odottavat konsultaatiota professorin kanssa. Taulukossa on joitain esimerkkejä jonosta jonojärjestelmissä:

Jonomallit (esim lineaarinen ohjelmointi, varastonhallintamallit, -menetelmät verkkoanalyysi projektit) käytetään sekä materiaalituotannon hallinnassa että palvelusektorilla. Jonojen analysointi jonon pituuden, keskimääräisen odotusajan, keskimääräisen palveluajan ja muiden tekijöiden perusteella auttaa ymmärtämään paremmin, miten palvelujärjestelmä on organisoitu. Potilaan odottaminen lääkärin odotushuoneessa ja rikkinäisen porakoneen korjauksen odottaminen korjaamossa ovat paljon yhteistä palvelunhallinnan kannalta. Molemmat prosessit käyttävät henkilöstö- ja laiteresursseja asiakkaiden tarpeiden täyttämiseksi.

Ammattimainen johtaja ottaa jonojärjestelmän parantamisen käsiinsä järjestelmän käyttökustannuksissa ja asiakkaiden odottamiseen liittyvissä kustannuksissa syntyvät muutokset. Voidaan vuokrata suuri määrä työntekijöitä, jotka palvelevat asiakkaita nopeasti. Esimerkiksi supermarketin ylläpitäjä voi vähentää kassojen jonoja lisäämällä myyjien ja kassojen määrää ruuhka-aikoina. Ruuhka-aikoina pankkien tai lentoasemien kassatyöskentelyyn saatetaan ottaa lisää työntekijöitä. Odotusajan lyhentäminen liittyy kuitenkin yleensä työpaikkojen luomisen ja varustamisen kustannuksiin sekä lisähenkilöstön palkkaamiseen. Nämä kustannukset voivat olla melko merkittäviä.

Voit säästää työvoimakustannuksissa. Mutta silloin asiakas ei välttämättä odota palvelua tai menettää halunsa palata uudelleen. Jälkimmäisessä tapauksessa jonotusjärjestelmälle aiheutuu tappioita, joita voidaan kutsua odotuskuluiksi. Joissakin palvelujärjestelmissä, kuten ambulansseissa, pitkiin odotusaikoihin liittyvät kustannukset voivat olla erittäin korkeita. Pääasiallinen taloudellinen periaate jonojärjestelmien parantamisessa on arvioida odotettavissa olevat kokonaiskustannukset, mukaan lukien palvelukustannukset ja tappiot, joita järjestelmälle aiheutuu asiakkaan odottamisesta.

Kun olet suorittanut tämän luvun tehtävät, osaat määritellä ja käyttää seuraavia talousanalyysin käsitteitä:

Jonotusjärjestelmä;

Vuoro;

Hakemusten vastaanottoprosentti;

Palvelun nopeus;

Keskimääräinen aika, jonka sovellus viettää jonossa;

Keskimääräinen jonon pituus;

Keskimääräinen aika, jonka sovellus viettää palvelujärjestelmässä;

Keskimääräinen asiakasmäärä palvelujärjestelmässä;

Palvelujärjestelmän toiminnan kustannukset;

Odotuskulut.

Mallit

Jonojärjestelmien luokitteluominaisuudet.

Jonotusjärjestelmissä kukin sovellus käy läpi kolme päävaihetta:

1) sovelluksen ilmestyminen järjestelmän sisäänkäynnille;

2) jonon ohittaminen;

3) palveluprosessi, jonka jälkeen sovellus poistuu järjestelmästä.

Jokaisessa vaiheessa käytetään tiettyjä ominaisuuksia, joista tulee keskustella ennen matemaattisten mallien rakentamista.

Syöttötiedot:

1) sisäänkäynnin hakemusten määrä (väestökoko);

2) hakemusten vastaanottotapa palvelujärjestelmässä;

3) asiakkaan käyttäytyminen.

Hakemusten määrä sisäänkäynnillä. Mahdollisten sovellusten määrää (populaatiokoko) voidaan pitää joko äärettömänä (rajaton populaatio) tai äärellisenä (rajoitettu populaatio). Jos järjestelmään saapuvien asiakkaiden määrä palveluprosessin alusta mihin tahansa tiettyyn hetkeen on vain pieni osa potentiaalisesta asiakasmäärästä, syöttöpopulaatioksi katsotaan Rajoittamaton. Esimerkkejä rajoittamattomista populaatioista: autot, jotka kulkevat tarkastuspisteiden läpi moottoriteillä, ostajat supermarketissa jne. Useimmissa sisäänkäynnin jonomalleissa otetaan huomioon rajoittamattomat väestöryhmät.

Jos järjestelmään pääsevien asiakkaiden määrä on verrattavissa jonotusjärjestelmässä olevien asiakkaiden määrään, lasketaan perusjoukko Rajoitettu. Esimerkki rajatusta populaatiosta: Tietyn organisaation omistamat tietokoneet, joita korjaamo huoltaa.

Hakemusten vastaanottotapa palvelujärjestelmässä. Sovellukset voivat tulla palvelujärjestelmään tietyn aikataulun mukaan (esim. yksi potilas hammaslääkärille 15 minuutin välein, yksi auto kokoonpanolinjalla 20 minuutin välein) tai satunnaisesti. Asiakaskäynnit lasketaan satunnainen, jos ne ovat toisistaan ​​riippumattomia ja täsmälleen arvaamattomia. Usein jonoongelmissa esiintymien lukumäärä aikayksikköä kohti voidaan arvioida käyttämällä Poissonin todennäköisyysjakaumaa. Tietyllä sisääntulonopeudella (esimerkiksi kaksi asiakasta tunnissa tai neljä kuorma-autoa minuutissa) diskreetti jakelu Poisson kuvataan seuraavalla kaavalla:

Missä P(x) - pääsyn todennäköisyys X sovellukset aikayksikköä kohti;

X - hakemusten määrä aikayksikköä kohti;

L on hakemusten keskimääräinen määrä aikayksikköä kohti (hakemusten vastaanottonopeus);

Vastaavat todennäköisyydet P(x) on helppo määrittää Poisson-jakaumataulukon avulla. Jos esimerkiksi pyyntöjen keskimääräinen vastaanottonopeus on kaksi asiakasta tunnissa, niin todennäköisyys, ettei järjestelmään tule tunnissa yhtään pyyntöä, on 0,135, yhden pyynnön todennäköisyys on noin 0,27 ja kaksi on myös noin 0,27, kolme väitettä voi ilmaantua todennäköisyydellä 0,18, neljä noin 0,09 jne. Todennäköisyys, että järjestelmään tulee tunnissa vähintään 9 vaatimusta, on lähellä nollaa.

Käytännössä sovellusten esiintymistodennäköisyydet eivät tietenkään aina noudata Poisson-jakaumaa (heillä voi olla jokin muu jakauma). Siksi vaaditaan esitutkimukset sen tarkistamiseksi, että Poisson-jakauma voi toimia hyvänä approksimaationa.

Asiakkaan käyttäytyminen. Useimmat jonomallit perustuvat olettamukseen, että asiakkaiden käyttäytyminen on normaalia, eli jokainen järjestelmään saapuva asiakas menee jonoon, odottaa palvelua eikä poistu järjestelmästä ennen kuin se on huollettu. Toisin sanoen jonoon tullut asiakas (ihminen tai kone) odottaa, kunnes se palvellaan, poistuu jonosta ja siirtyy jonosta toiseen.

Elämä on paljon vaikeampaa. Käytännössä asiakkaat voivat poistua jonosta, koska se on liian pitkä. Voi syntyä toinenkin tilanne: asiakkaat odottavat vuoroaan, mutta lähtevät jostain syystä palvelematta. Nämä tapaukset ovat myös jonoteorian kohteena, mutta niitä ei käsitellä tässä.

Jonon ominaisuudet:

2) palvelusääntö.

Jonon pituus. Pituus voi olla rajoitettu tai ei. Jonon pituus (jono) Rajoitettu jos jostain syystä (esim fyysisiä rajoituksia) ei voi kasvaa loputtomasti. Jos jono saavuttaa sen enimmäiskoko, niin seuraava sovellus järjestelmään ei ole sallittu ja hylkäys tapahtuu. Jonon pituus Ei rajoitettu, Jos jonossa voi olla kuinka monta sovellusta tahansa. Esimerkiksi autojen jono huoltoasemalla.

palvelusääntö. Useimmat todelliset järjestelmät käyttävät ensin sisään, ensin ulos -sääntöä. (FIFO- ensimmäinen sisällä ensimmäinen ulkona). Joissakin tapauksissa, kuten sairaalan ensiapuun, tämän säännön lisäksi erilaisia Prioriteetit. Kriittisesti sairas sydänkohtauksen saanut potilas on todennäköisesti etusijalla hoidossa kuin potilas, jolla on murtunut sormi. Järjestys, jossa tietokoneohjelmat käynnistetään, on toinen esimerkki palvelun priorisoinnista.

Palveluprosessin ominaisuudet:

1) palvelujärjestelmän konfiguraatio (kanavien määrä ja palveluvaiheiden lukumäärä);

2) huoltotila.

Palvelujärjestelmän konfigurointi. Palvelujärjestelmät eroavat toisistaan Palvelukanavien määrä. Tyypillisesti kanavien määrä voidaan määritellä asiakkaiden lukumääräksi, joita voidaan palvella samanaikaisesti, esimerkiksi: mestareiden lukumäärä kampaajassa. Esimerkkejä yksi kanava palvelujärjestelmät: pankki, jossa on yksi ikkuna asiakaspalvelua varten, tai ravintola, joka palvelee asiakkaita autossa. Jos pankissa on auki useita palveluikkunoita, asiakas odottaa yleisjonossa ja lähestyy ensimmäistä vapaata ikkunaa, niin olemme tekemisissä Monikanavainen yksivaiheinen huoltojärjestelmä. Useimmat pankit, samoin kuin postitoimistot ja lentolipputoimistot, ovat monikanavaisia ​​palvelujärjestelmiä.

Toinen ominaisuus - Vaiheiden lukumäärä(tai peräkkäisiä vaiheita) Palvelut yksi asiakas. yksivaihe ovat sellaisia ​​järjestelmiä, joissa asiakasta palvellaan yhdessä pisteessä (yhdessä työpaikassa) ja poistuu sitten järjestelmästä. Autohuoltoravintola, jossa tarjoilija vastaanottaa rahat ja tuo tilauksen autoon, on esimerkki yksivaiheisesta järjestelmästä. Jos ravintolassa sinun on tehtävä tilaus yhdestä paikasta, maksettava se toisessa ja saatava ruokaa kolmannessa, niin olemme tekemisissä monivaiheinen(kolmivaiheinen) palvelujärjestelmä.

Kuvassa Kuvassa 1 on esitetty erikokoisia palvelujärjestelmiä.

Huoltotila. Pyyntöjen vastaanottotavan lisäksi palvelutilaa voidaan luonnehtia joko vakio- tai satunnaisella palveluajalla. klo pysyvä Jokaisen asiakkaan palvelemiseen kuluu saman verran aikaa. Tämä tilanne voidaan havaita automaattisessa autonpesussa. Useammin tulee kuitenkin tilanteita, joissa palveluaika on Satunnainen jakelu. Monissa tapauksissa voidaan olettaa, että palveluaika seuraa eksponentiaalista jakautumista jakaumafunktiolla

F( T ) = P(T< t) =1 – e–tm, missä R (T< t) on todennäköisyys, että todellinen aika T palvelupyyntö ei ylitä määritettyä arvoa t;

M - toimitettujen hakemusten keskimääräinen määrä aikayksikköä kohti;

E \u003d 2,7182 - luonnollisen logaritmin kanta.

Jonomallien parametrit. Jonojärjestelmien analysoinnissa käytetään teknisiä ja taloudellisia ominaisuuksia.

Seuraavat ovat yleisimmin käytettyjä Tekniset tiedot:

1) keskimääräinen aika, jonka asiakas viettää jonossa;

2) jonon keskimääräinen pituus;

3) keskimääräinen aika, jonka asiakas viettää palvelujärjestelmässä (odotusaika plus palveluaika);

4) keskimääräinen asiakasmäärä palvelujärjestelmässä;

5) todennäköisyys, että palvelujärjestelmä jää käyttämättömäksi;

6) todennäköisyys, että järjestelmässä on tietty määrä asiakkaita.

Joukossa Taloudelliset ominaisuudet mielenkiintoisimpia ovat seuraavat:

1) jonossa odotuskustannukset;

2) järjestelmässä odottamisen kustannukset;

3) ylläpitokustannukset.

Jonojärjestelmien mallit. Yllä olevien ominaisuuksien yhdistelmästä riippuen voidaan harkita erilaisia ​​jonojärjestelmien malleja.

Tässä tarkastellaan joitain tunnetuimmista malleista. Niillä kaikilla on seuraavat yhteiset ominaisuudet:

A) Hakemusten vastaanottamisen todennäköisyyden Poisson-jakauma;

B) normaali asiakaskäyttäytyminen;

B) palvelusääntö FIFO(palvellaan saapumisjärjestyksessä);

D) ainoa palveluvaihe.

minä Malli A - yksikanavainen jonojärjestelmämalli MM/ 1 s Poisson saapuva sovellusvirta ja Eksponentiaalinen palveluaika.

Yleisimmät yhden kanavan jono-ongelmat. Tällöin asiakkaat muodostavat yhden jonon yhteen palvelupisteeseen. Oletetaan, että seuraavat ehdot täyttyvät tämän tyyppisille järjestelmille:

1. Hakemukset toimitetaan saapumisjärjestyksessä (FIFO) Lisäksi jokainen asiakas odottaa jonansa loppuun jonon pituudesta riippumatta.

2. Hakemusten esiintymiset ovat itsenäisiä tapahtumia, mutta aikayksikköä kohti saapuvien hakemusten keskimäärä on ennallaan.

3. Hakemusten vastaanottoprosessi kuvataan Poisson-jakelulla, ja hakemuksia tulee rajattomasta joukosta.

4. Palveluaika kuvataan eksponentiaalisella todennäköisyysjakaumalla.

5. Palvelun määrä on korkeampi kuin hakemusten vastaanottoaste.

Olkoon l sovellusten lukumäärä aikayksikköä kohti;

M on palveltujen asiakkaiden määrä aikayksikköä kohti;

P - järjestelmässä olevien sovellusten määrä.

Sitten jonojärjestelmä kuvataan alla olevilla yhtälöillä.

Kaavat M/M/-järjestelmän kuvaamiseksi 1:

- keskimääräinen asiakkaiden määrä järjestelmässä;

Keskimääräinen palveluaika asiakasta kohti järjestelmässä (odotusaika plus palveluaika);

Keskimääräinen asiakkaiden määrä jonossa;

jonossa olevan asiakkaan keskimääräinen odotusaika;

Järjestelmän kuormituksen ominaisuudet (osuus ajasta, jonka aikana järjestelmä on varattu huoltoon);

Todennäköisyys, että järjestelmässä ei ole sovelluksia;

Todennäköisyys, että järjestelmä sisältää enemmän kuin K sovellukset.

II. Malli B - monikanavainen palvelujärjestelmä M/M/S. Monikanavajärjestelmässä kaksi tai useampi kanava on avoinna palvelua varten. Oletetaan, että asiakkaat odottavat yleisessä jonossa ja hakevat ensimmäiselle ilmaiselle palvelukanavalle.

Esimerkki tällaisesta monikanavaisesta yksivaihejärjestelmästä on nähtävissä monissa pankeissa: yleisestä jonosta asiakkaat menevät ensimmäiseen ilmaiseen huoltoon.

Monikanavaisessa järjestelmässä pyyntöjen virta on riippuvainen Poisson laki ja palvelusaika - Eksponentiaalinen. Ensimmäinen tulija palvellaan ensin, ja kaikki palvelukanavat toimivat samaan tahtiin. Mallia kuvaavat kaavat AT, melko vaikea käyttää. Monikanavaisen jonotusjärjestelmän parametrien laskemiseen on kätevää käyttää asianmukaista ohjelmistoa.

Aika, jolloin hakemus oli jonossa;

Sovelluksen järjestelmässä käyttämä aika.

III. Malli C- malli jatkuvalla huoltoajalla M/D/ 1.

Joissakin järjestelmissä on pysyvä, eksponentiaalisesti jakautuneen palveluajan sijaan. Tällaisissa järjestelmissä asiakkaita palvellaan määrätyn ajan, esimerkiksi automaattipesulassa. Mallille FROM Palveluarvojen vakionopeudella Lq ja wq Puolet mallin vastaavista arvoista MUTTA, vaihtuvalla palveluhinnalla.

Mallia C kuvaavat kaavat:

- jonon keskimääräinen pituus;

- keskimääräinen odotusaika jonossa;

Keskimääräinen asiakkaiden lukumäärä järjestelmässä;

Keskimääräinen odotusaika järjestelmässä.

IV. Malli D - rajallisen väestön malli.

Jos numero potentiaalisia asiakkaita palvelujärjestelmät rajoitettu, olemme tekemisissä erikoismallin kanssa. Tällainen ongelma voi syntyä esimerkiksi jos me puhumme viiden koneen tehtaan kaluston kunnossapidosta.

Tämän mallin erikoisuus verrattuna kolmeen aiemmin tarkasteltuun malliin on, että on Keskinäinen riippuvuus jonon pituuden ja hakemusten vastaanottonopeuden välillä.

v. Malli E - rajoitetun jonon malli. Malli eroaa aikaisemmista jonossa olevien paikkojen määrällä Rajoitettu. Tässä tapauksessa pyyntö, joka saapui järjestelmään, kun kaikki kanavat ja paikat jonossa ovat varattu, jättää järjestelmän palvelematta, eli hylätään.

Rajoitetun jonomallin erikoistapauksena voidaan harkita epäonnistunut malli, jos jonon paikkojen määrä pienenee nollaan.

Seuraavassa taulukossa on esitetty erilaisten jonojärjestelmien mallien vertailuominaisuudet.

Matemaattinen (abstrakti) objekti, jonka elementit ovat (kuva 2.1):

• syöttö (saapuva) sovellusten virta (vaatimukset) palvelua varten;
• palvelulaitteet (kanavat);
• palvelua odottavien sovellusten jono;
• Huoltopyyntöjen lähtö (lähtevä) virta;
• jälkihoitopyyntöjen virta palvelun keskeytymisen jälkeen;
• toimittamattomien pyyntöjen virta.

Pyyntö(pyyntö, vaatimus, puhelu, asiakas, viesti, paketti) - QS:ään saapuva objekti, joka vaatii huoltoa laitteessa. Peräkkäisten sovellusten joukko jaettu aikamuodossa sovellusten syöttövirta.

Riisi. 2.1.

huoltolaite(laite, laite, kanava, linja, työkalu, auto, reititin jne.) - QS-elementti, jonka tarkoitus on palvella sovelluksia.

Palvelu- pyynnön viivästyminen palvelulaitteessa jonkin aikaa.

Palvelun kesto- sovelluksen viive (palvelu) laitteessa.

Tallennuslaite(puskuri, syöttöpuskuri, lähtöpuskuri) - joukko paikkoja sovellusten odottamiseen palvelevan laitteen edessä. Odotuspaikkojen määrä - varastokapasiteetti.

CMO:n vastaanottama hakemus voi olla kahdessa tilassa:

• 1) palvelua(laitteessa);
• 2) odotuksia(akussa), jos kaikki laitteet palvelevat muita pyyntöjä.

Vaatimukset akku- ja odotuspalvelulomakkeessa vuoro sovellukset. Akun palvelua odottavien sovellusten määrä - jonon pituus.

Puskuroiva kurinalaisuus(jonokuri) - sääntö saapuvien sovellusten syöttämiseksi asemaan (puskuriin).

Palvelukuri- sääntö pyyntöjen valitsemiseksi laitteen palvelujonosta.

Prioriteetti- etuostooikeus (resurssien kaappaamiseen) päästä akkuun tai valita jonosta huoltoon yhden luokan laitesovelluksissa suhteessa muiden luokkien sovelluksiin.

On monia jonojärjestelmiä, jotka eroavat rakenteeltaan ja toimiva organisaatio. Samanaikaisesti analyyttisten menetelmien kehittäminen QS-suorituskykyindikaattoreiden laskemiseksi sisältää monissa tapauksissa useita rajoituksia ja olettamuksia, jotka kaventavat tutkittavien laatustandardien joukkoa. Siksi yleinen analyyttinen malli mielivaltaiselle QS:lle monimutkainen rakenne ei ole olemassa.

QS-analyyttinen malli on joukko yhtälöitä tai kaavoja, joiden avulla voidaan määrittää järjestelmän toiminnan todennäköisyydet ja suorituskykyindikaattorit sisääntulevan virtauksen ja palvelukanavien, puskuroinnin ja palveluiden tunnettujen parametrien perusteella.

QS:n analyyttistä mallintamista helpottaa huomattavasti, jos QS:ssä tapahtuvat prosessit ovat markovia (sovellusvirta on yksinkertaisin, palveluajat jakautuvat eksponentiaalisesti). Tässä tapauksessa kaikki prosessit QS:ssä voidaan kuvata tavallisella differentiaaliyhtälöt, ja rajoittavassa tapauksessa - stationäärisille tiloille - lineaarisilla algebrallisilla yhtälöillä ja ratkaistuaan ne millä tahansa matemaattisissa ohjelmistopaketeissa saatavilla olevilla menetelmillä määrittää valitut suoritusindikaattorit.

IM-järjestelmissä QS:ää toteutettaessa hyväksytään seuraavat rajoitukset ja oletukset:

• sovellus syötetty järjestelmään välittömästi menee käyttöön, jos jonossa ei ole pyyntöjä ja laite on vapaa;
• laitteen huoltoa varten milloin tahansa voi olla vain yksi pyyntö;
• minkä tahansa laitteessa olevan pyynnön palvelun päätyttyä valitaan jonosta välittömään huoltoon seuraava pyyntö, eli laite ei käy tyhjäkäynnillä jos jonossa on vähintään yksi sovellus;
• hakemusten vastaanottaminen QS:ssä ja niiden palvelun kesto ei riipu järjestelmässä jo olevien hakemusten määrästä tai muista tekijöistä;
• palvelupyyntöjen kesto ei riipu järjestelmään tulevien pyyntöjen intensiteetistä.

Tarkastellaanpa joitain QS:n elementtejä yksityiskohtaisemmin.

Sovellusten sisääntulo (saapuva) virta. Tapahtumien virtaus kutsutaan sarjaksi homogeenisiä tapahtumia, jotka seuraavat peräkkäin ja esiintyvät joissakin yleisesti ottaen satunnainen aikapisteitä. Jos tapahtuma koostuu vaateiden esittämisestä, meillä on sovelluskulku. Kuvaamaan sovellusten kulkua sisään yleinen tapaus on tarpeen asettaa aikavälit t = t k - t k-1 vierekkäisten hetkien välillä t k _ k ja t k hakemusten vastaanottaminen sarjanumeroilla - 1 ja to vastaavasti (- 1, 2, ...; t 0 - 0 - ensimmäinen ajanhetki).

Sovellusvirran pääominaisuus on sen X intensiteetti- QS-tuloon saapuvien sovellusten keskimääräinen määrä aikayksikköä kohti. Arvo t = 1/X määrittelee keskimääräinen aikaväli kahden peräkkäisen tilauksen välillä.

Virtausta kutsutaan deterministinen jos aikavälejä t vierekkäisten sovellusten välillä hyväksy ennalta määrätty tunnetut arvot. Jos välit ovat samat (x to= t kaikille k = 1, 2, ...), sitten virtaa kutsutaan säännöllinen. varten täydellinen kuvaus säännölliseen sovellusvirtaan riittää virtauksen intensiteetin asettaminen X tai välin t = arvo 1/X.

Virta, jossa aikavälejä x k vierekkäisten sovellusten välillä on satunnaismuuttujia, ns satunnainen. Täydellisen kuvauksen saamiseksi satunnaisesta sovellusten kulusta yleisessä tapauksessa on tarpeen asettaa jakautumislait F fc (x fc) kullekin aikavälille x k, k = 1,2,...

Satunnainen stream, jossa kaikki aikavälit x b x 2,... vierekkäisten peräkkäisten asiakkaiden välillä on riippumattomia satunnaismuuttujia, joita kuvaavat jakautumisfunktiot FjCij), F 2 (x 2), ... kutsutaan vastaavasti virtaukseksi rajoitettu jälkivaikutus.

Satunnaisvirtaa kutsutaan toistuva, jos kaikki aikavälit x b t 2 , ... jaettu sovellusten välillä saman lain mukaan F(t). Toistuvia virtoja on monia. Jokainen jakelulaki luo oman toistuvan virtauksensa. Toistuvat streamit tunnetaan muuten Palm-virroina.

Jos intensiteetti X ja peräkkäisten pyyntöjen välisten välien jakautumislaki F(t) ei muutu ajan myötä, niin pyyntöjen virtaa kutsutaan paikallaan Muuten sovelluskulku on ei-kiinteä.

Jos joka hetki t k vain yksi asiakas voi ilmestyä QS:n sisääntuloon, jolloin asiakasvirta kutsutaan tavallinen. Jos useampi kuin yksi sovellus voi ilmestyä kerrallaan, sovellusvirta on epätavallinen, tai ryhmä.

Pyyntöjen kulkua kutsutaan virtaukseksi ei jälkivaikutuksia, jos hakemuksia tulee riippumatta toisistaan, ts. seuraavan hakemuksen vastaanottohetki ei riipu siitä, milloin ja kuinka monta hakemusta on vastaanotettu ennen tätä hetkeä.

Kiinteää tavallista virtausta ilman jälkivaikutusta kutsutaan yksinkertaisin.

Yksinkertaisimman vuon pyyntöjen väliset aikavälit t jaetaan sen mukaan eksponentiaalinen (esimerkillinen) laki: jakaumafunktiolla F(t) = 1 - e~ m; jakautumistiheys/(f) = Heh~"l, missä X > 0 - jakautumisparametri - sovellusten virtauksen intensiteetti.

Yksinkertaisinta virtausta kutsutaan usein Poisson. Nimi tulee siitä, että tälle virtaukselle on täsmälleen todennäköisyys P fc (At). to pyynnöt tietylle aikavälille At määritetään Poissonin laki:

On huomattava, että Poisson-virtaus, toisin kuin yksinkertaisin, voi olla:

• paikallaan, jos intensiteetti X ei muutu ajan myötä;
• ei-kiinteä, jos virtausnopeus riippuu ajasta: X= >.(t).

Samaan aikaan yksinkertaisin virtaus on määritelmän mukaan aina paikallaan.

Jonomallien analyyttiset tutkimukset suoritetaan usein olettamalla yksinkertaisin pyyntövirta, mikä johtuu useista siihen sisältyvistä merkittävistä piirteistä.

1. Virtojen summaus (yhdistäminen). Yksinkertaisin virtaus QS-teoriassa on samanlainen kuin todennäköisyysteorian normaalijakauman laki: siirtyminen rajaan virtaukselle, joka on mielivaltaisten ominaisuuksien omaavien virtojen summa termien lukumäärän äärettömällä kasvulla ja niiden intensiteetin pienenemisellä johtaa yksinkertaisimpaan virtaukseen.

Summa N itsenäiset kiinteät tavalliset virtaukset intensiteetillä x x x 2 ,..., X N muodostaa yksinkertaisimman virtauksen intensiteetillä

X=Y,^i edellyttäen, että lisätyillä virroilla on enemmän tai

vähemmän yhtä pieni vaikutus kokonaisvirtaukseen. Käytännössä kokonaisvirtaus on lähellä yksinkertaisinta N > 5. Joten kun lasketaan yhteen itsenäiset yksinkertaisimmat virrat, kokonaisvirtaus on yksinkertaisin mille tahansa arvolle N.

• 2. Virran todennäköisyysharvinaisuus. todennäköisyys(mutta ei-deterministinen) harvinaisuus yksinkertaisin virtaus sovelluksia, joissa mikä tahansa sovellus satunnaisesti jollain todennäköisyydellä R jätetään pois virtauksesta riippumatta siitä, onko muut sovellukset jätetty pois vai ei, johtaa muodostumiseen yksinkertaisin virtaus intensiteetin kanssa X* = pX, missä X- alkuvirtauksen intensiteetti. Poissuljettujen sovellusten virtaus voimakkuudella X** = (1 - p)X- myös alkueläin virtaus.
• 3. Tehokkuus. Jos palvelevat kanavat (laitteet) on suunniteltu yksinkertaisimpaan pyyntöjen virtaan intensiteetillä x, silloin muun tyyppisten virtausten (samalla intensiteetillä) huolto on yhtä tehokasta.
• 4. Yksinkertaisuus. Yksinkertaisimman sovellusvirran oletus mahdollistaa sen, että monet matemaattiset mallit voivat saada eksplisiittisessä muodossa QS-indikaattoreiden riippuvuuden parametreista. Suurin numero analyyttisiä tuloksia saatiin yksinkertaisimmille sovelluksille.

Sellaisten mallien analysointi, joissa sovellusvirrat poikkeavat yksinkertaisimmista, yleensä monimutkaistaa matemaattisia laskelmia, eikä aina ole mahdollista saada eksplisiittistä analyyttistä ratkaisua. "Yksinkertaisin" virtaus sai nimensä juuri tämän ominaisuuden ansiosta.

Sovelluksilla voi olla erilaiset oikeudet aloittaa palvelu. Tässä tapauksessa sovellusten sanotaan olevan heterogeeninen. Joidenkin sovellusvirtojen edut muihin verrattuna palvelun alussa määräytyvät prioriteettien mukaan.

Syöttövirran tärkeä ominaisuus on variaatiokerroin

missä t int - välin pituuden matemaattinen odotus; noin- keskiverto keskihajonta intervallin pituus x int (satunnainen muuttuja) .

Yksinkertaisimmalla virtauksella (a = -, m = -) meillä on v = 1. Useimmille

todelliset virtaukset 0

Palvelukanavat (laitteet). Kanavan pääominaisuus on palvelun kesto.

Palvelun kesto- sovelluksen laitteessa viettämä aika - yleensä arvo on satunnainen. QS:n epätasaisen kuormituksen tapauksessa eri luokkien pyyntöjen palveluajat voivat vaihdella jakelulakien tai vain keskiarvojen mukaan. Tällöin yleensä oletetaan, että kunkin luokan pyyntöjen palveluajat ovat riippumattomia.

Ammatinharjoittajat olettavat usein, että huoltopyyntöjen kesto on jaettu eksponentiaalinen laki mikä yksinkertaistaa huomattavasti analyyttisiä laskelmia. Tämä johtuu siitä, että prosessit, jotka tapahtuvat järjestelmissä, joissa aikavälit ovat eksponentiaalisesti jakautuneet Markov prosessit:

missä c - palvelun intensiteetti, tässä p = _--; t 0 bsl - matematiikka-

tic odotusaika palveluun.

Eksponentiaalisen jakauman lisäksi on Erlang /c-jakaumia, hypereksponentiaalisia jakaumia, kolmiojakaumia ja joitain muita. Tämän ei pitäisi hämmentää meitä, koska on osoitettu, että QS-tehokkuuskriteerien arvo riippuu vähän palveluajan jakautumislain muodosta.

QS-tutkimuksessa palvelun olemus, palvelun laatu, jää huomioimatta.

Kanavat voivat olla ehdottoman luotettava nuo. älä epäonnistu. Sen sijaan se voidaan hyväksyä tutkimuksessa. Kanavilla voi olla lopullinen luotettavuus. Tässä tapauksessa QS-malli on paljon monimutkaisempi.

QS-tehokkuus ei riipu pelkästään tulovirtojen ja palvelukanavien parametreista, vaan myös siitä, missä järjestyksessä saapuvia pyyntöjä palvellaan, eli ts. tavoista hallita sovellusten virtaa, kun ne tulevat järjestelmään ja lähetetään huoltoon.

Tapoja hallita sovellusvirtaa määrittävät tieteenalat:

• puskurointi;
• palvelua.

Puskurointi- ja ylläpitoalat voidaan luokitella seuraavien kriteerien mukaan:

• prioriteettien saatavuus eri luokkien sovellusten välillä;
• menetelmä sovellusten työntämiseksi ulos jonosta (puskurointia varten) ja palvelupyyntöjen osoittamiseksi (palvelualoille);
• sääntö palvelupyyntöjen ennakoimiseksi tai valitsemiseksi;
• kyky muuttaa prioriteetteja.

Kuvassa 1 on esitetty muunnelma puskurointialojen luokittelusta (jono) lueteltujen ominaisuuksien mukaisesti. 2.2.

Riippuen saatavuus tai prioriteettien puute eri luokkien sovellusten välillä kaikki puskurointialat voidaan jakaa kahteen ryhmään: ei-prioriteetti ja prioriteetti.

Tekijä: tapa työntää sovelluksia ulos tallennustilasta seuraavat puskurointitieteen luokat voidaan erottaa:

• syrjäyttämättä pyyntöjä - järjestelmään tulleet pyynnöt, jotka havaitsivat aseman olevan täysin täytetty, menetetään;
• tämän luokan sovelluksen siirtymisen kanssa, ts. sama luokka kuin vastaanotettu hakemus;
• sovelluksen siirtymisen kanssa alimman prioriteetin luokasta;
• sovelluksen syrjäyttämisen kanssa alhaisen prioriteetin luokkien ryhmästä.

Riisi. 2.2.

Puskurointialat voivat käyttää seuraavia säännöt pyyntöjen poistamiseksi akusta:

• vahingossa tapahtuva siirtymä;
• viimeisen tilauksen poissulkeminen, ts. tuli järjestelmään myöhemmin kuin kaikki;
• "pitkän" tilauksen syrjäyttäminen, ts. sijaitsee akussa pidempään kuin kaikki aiemmin vastaanotetut hakemukset.

Kuvassa 2.3 esittää sovellusten huollon tieteenalojen luokituksen samojen ominaisuuksien mukaisesti kuin puskuroinnin tieteenaloilla.

Joskus mallien tallennuskapasiteettia pidetään rajoittamattomana, vaikka todellisessa järjestelmässä se on rajoitettu. Tällainen oletus on perusteltu, kun tilauksen menettämisen todennäköisyys todellisessa järjestelmässä tallennuskapasiteetin ylivuodon vuoksi on alle 10_3. Tässä tapauksessa kurilla ei ole käytännössä mitään vaikutusta pyyntöjen suorittamiseen.

Riippuen saatavuus tai prioriteettien puute eri luokkien pyyntöjen välillä kaikki palvelualat sekä puskurointialat voidaan jakaa kahteen ryhmään: ei-prioriteettiin ja prioriteetteihin.

Tekijä: miten palveluliput jaetaan Palvelualat voidaan jakaa tieteenaloihin:

• yksitila;
• ryhmätila;
• yhdistetty tila.

Riisi. 2.3.

Palvelualoilla yksitila palvelu joka kerta vain yksi määrätty pyyntö, jonka jonot tarkistetaan edellisen pyynnön huollon päätyttyä.

Palvelualoilla ryhmätila palvelu joka kerta sovellusryhmä on määritetty yksi jono, jonka jonot tarkistetaan vasta, kun kaikki aiemmin määritetyn ryhmän pyynnöt on käsitelty. Äskettäin määritetty lippuryhmä voi sisältää kaikki tietyn jonon liput. Määritetyt ryhmäpyynnöt valitaan peräkkäin jonosta ja laite palvelee, minkä jälkeen toisen jonon seuraava sovellusten ryhmä osoitetaan palveluun määritellyn palvelukurin mukaisesti.

Yhdistetty tila- yksi- ja ryhmämoodien yhdistelmä, kun osa pyyntöjonoista käsitellään yksittäistilassa ja toinen osa ryhmätilassa.

Palvelualat voivat käyttää seuraavia palvelupyyntöjen valintasääntöjä.

Ei-prioriteetti(sovelluksilla ei ole varhaisia ​​palveluoikeuksia - resurssien sieppaus):

• ensin tullutta palvellaan palvelua FIFO (ensimmäinen sisään -ensin ulos, ensimmäinen sisällä ensimmäinen ulkona)
• käänteinen palvelu- sovellus valitaan tilan jonosta LIFO (viimeinen sisään - ensin ulos, viimeisenä sisään ensimmäisenä ulos)
• satunnainen palvelu- sovellus valitaan tilan jonosta RAND (satunnainen- satunnaisesti);
• syklinen palvelu- sovellukset valitaan asemien syklisessä kyselyssä järjestyksessä 1, 2, H FROM H- asemien lukumäärä), jonka jälkeen määritetty sekvenssi toistetaan;

Prioriteetti(sovelluksilla on oikeudet varhaiseen palveluun - resurssien sieppaus):

• Kanssa suhteelliset prioriteetit- jos pyynnön meneillään olevan palvelemisen aikana järjestelmään tulee pyyntöjä, joilla on korkeampi prioriteetti, niin nykyisen pyynnön palvelu ei keskeydy edes ilman prioriteettia ja vastaanotetut pyynnöt lähetetään jonoon; suhteellisilla prioriteeteilla on rooli vain sovelluksen nykyisen palvelun lopussa, kun uusi palvelupyyntö valitaan jonosta.
• Kanssa ehdottomia prioriteetteja- korkean prioriteetin pyynnön vastaanotettuaan matalan prioriteetin pyynnön palvelu keskeytyy ja vastaanotettu pyyntö lähetetään huollettavaksi; keskeytynyt sovellus voidaan palauttaa jonoon tai poistaa järjestelmästä; jos hakemus palautetaan jonoon, sen jatkopalvelu voidaan suorittaa keskeytetystä paikasta tai uudelleen;
• co sekalaisia ​​prioriteetteja- yksittäisten sovellusten huoltojonon odotusajan tiukat rajoitukset edellyttävät ehdottomien prioriteettien osoittamista niille; tämän seurauksena alhaisten prioriteettien hakemusten odotusaika voi osoittautua liian pitkäksi, vaikka yksittäisillä hakemuksilla onkin odotusaikamarginaalia; kaikentyyppisten pyyntöjen rajoitusten täyttämiseksi sekä absoluuttisten prioriteettien kanssa joillekin pyynnöille voidaan määrittää suhteelliset prioriteetit ja loput voidaan palvella ei-prioriteettitilassa;
• Kanssa vaihtuvat prioriteetit- suhteellisten prioriteettien analogi, prioriteetti otetaan huomioon vain silloin, kun yhden jonon pyyntöryhmän nykyinen palvelu on saatu päätökseen ja uusi ryhmä huoltoon osoitetaan;
• määräaikaishuolto- eri luokkien vaatimukset (sijaitsevat eri varastoissa) valitaan palveluun tietyn aikataulun mukaan, joka määrittää sovellusjonojen kyselyn järjestyksen, esimerkiksi kolmen sovellusluokan (myymälän) tapauksessa aikataulu voi näyttää kuten (2, 1, 3, 3, 1, 2) tai (1, 2, 3, 3, 2, 1).

Tietokoneen IM-järjestelmissä kurinalaisuus on pääsääntöisesti toteutettu oletusarvoisesti FIFO. Niissä on kuitenkin työkaluja, jotka antavat käyttäjälle mahdollisuuden järjestää tarvitsemansa palvelualat myös aikataulun mukaan.

CMO:n vastaanottamat hakemukset on jaettu luokkiin. QS:ssä, joka on abstrakti matemaattinen malli, sovellukset kuuluvat eri luokkiin siinä tapauksessa, että ne eroavat simuloidussa todellisessa järjestelmässä ainakin yhdellä seuraavista ominaisuuksista:

• palvelun kesto;
• prioriteetteja.

Jos sovellukset eivät eroa palvelun keston ja prioriteettien suhteen, ne voidaan esittää saman luokan sovelluksilla, myös silloin, kun ne tulevat eri lähteistä.

Käytämme matemaattista kuvausta palvelualoista, joilla on sekalainen prioriteetti prioriteettimatriisi, edustaa neliömatriisi Q = (q, ;), minä, j- 1,..., I, I - järjestelmään tulevien sovellusluokkien lukumäärä.

Elementti q(j matriisi asettaa luokkapyyntöjen prioriteetin i luokkahakemuksiin liittyen; ja voi ottaa seuraavat arvot:

• 0 - ei prioriteettia;
• 1 - suhteellinen prioriteetti;
• 2 - ehdoton prioriteetti.

Prioriteettimatriisin elementtien on täytettävä seuraavat asiat vaatimukset:

• q n= 0, koska prioriteetteja ei voida asettaa saman luokan pyyntöjen välillä;
• jos q (j = 1 tai 2 sitten q^ = 0, koska jos luokkasovelluksia i ovat etusijalla luokkapyyntöihin nähden j, niin jälkimmäinen ei voi olla etusijalla ryhmävaatimuksiin nähden i (i,j = 1, ..., I).

Riippuen mahdollisuus muuttaa prioriteetteja Järjestelmän toiminnan aikana ensisijaiset puskuroinnin ja huollon osa-alueet on jaettu kahteen luokkaan:

• 1) kanssa staattiset prioriteetit, jotka eivät muutu ajan myötä;
• 2) kanssa dynaamiset prioriteetit, joka voi muuttua järjestelmän toiminnan aikana eri tekijöistä riippuen, esimerkiksi kun tietty kriittinen minkä tahansa luokan, jolla ei ole prioriteettia tai jolla on matala prioriteetti, pyyntöjonon pituus, sille voidaan antaa korkeampi prioriteetti.

IM-tietokonejärjestelmissä on välttämättä yksi elementti (objekti), jonka kautta ja vain sen kautta pyynnöt syötetään malliin. Oletuksena kaikki syötetyt sovellukset eivät ole prioriteetteja. Mutta prioriteettien asettamiseen on mahdollisuuksia sekvenssissä 1, 2, ..., myös mallin suorituksen aikana, ts. dynamiikassa.

Lähtevä stream on QS:stä lähtevien palvelupyyntöjen virta. Todellisissa järjestelmissä sovellukset käyvät läpi useita QS:itä: kauttakulkuviestintä, tuotantoputki jne. Tässä tapauksessa lähtevä virta on seuraavan QS:n tuleva virta.

Ensimmäisen QS:n tuleva virta, joka on kulkenut seuraavien QS:ien läpi, on vääristynyt, mikä vaikeuttaa analyyttistä mallintamista. Se on kuitenkin pidettävä mielessä yksinkertaisimmalla syöttövirralla ja eksponentiaalisella palvelulla(nuo. Markovin järjestelmissä) lähtövirta on myös yksinkertaisin. Jos palveluajalla on ei-eksponentiaalinen jakauma, niin lähtevä virta ei ole vain yksinkertainen, vaan myös toistuva.

Huomaa, että lähtevien pyyntöjen väliset aikavälit eivät ole samat kuin huoltovälit. Loppujen lopuksi voi käydä niin, että seuraavan palvelun päätyttyä QS on jonkin aikaa käyttämättömänä sovellusten puutteen vuoksi. Tässä tapauksessa lähtevän virtauksen aikaväli koostuu QS:n joutoajasta ja ensimmäisen seisokkiajan jälkeen saapuneen pyynnön huoltovälistä.

QS:ssä voi olla palvelupyyntöjen lähtevän virran lisäksi toimittamattomien pyyntöjen virta. Jos tällainen QS vastaanottaa toistuvan virran ja palvelu on eksponentiaalinen, myös palvelemattomien asiakkaiden virta on toistuvaa.

Ilmaiset kanavajonot. Monikanavaisessa QS:ssä voidaan muodostaa vapaiden kanavien jonoja. Vapaiden kanavien määrä on satunnainen arvo. Tutkijat voivat olla kiinnostuneita tämän satunnaismuuttujan erilaisista ominaisuuksista. Tyypillisesti tämä on palvelun käyttämien kanavien keskimäärä tutkimusväliä kohden ja niiden kuormituskertoimet.

Kuten aiemmin totesimme, todellisissa objekteissa pyynnöt palvellaan peräkkäin useissa QS:issä.

Kutsutaan äärellinen joukko peräkkäin kytkettyjä QS:itä, jotka käsittelevät niissä kiertäviä sovelluksia jonotusverkko (Semo) (Kuva 2.4, a).

Riisi. 2.4.

SEMO on myös nimeltään monivaiheinen QS.

Tarkastellaan esimerkkiä QEMO IM:n rakentamisesta myöhemmin.

QS:n pääelementit ovat solmut (U) ja pyyntöjen lähteet (generaattorit) (G).

Solmu verkot ovat jonojärjestelmä.

Lähde- verkkoon tulevien sovellusten generaattori, jotka vaativat tiettyjä palveluvaiheita verkkosolmuissa.

Kaaviota käytetään yksinkertaistettuun QEMO-kuvaan.

Kreivi Semo- suunnattu graafi (digraph), jonka kärjet vastaavat QEM-solmuja ja kaaret edustavat sovellusten siirtymiä solmujen välillä (kuva 2.4, b).

Olemme siis pohtineet QS:n peruskäsitteitä. Mutta IM:n tietokonejärjestelmien kehittämisessä ja niiden parantamisessa käytetään välttämättä myös QS:n analyyttiseen mallinnukseen tällä hetkellä sisältyvää valtavaa luovaa potentiaalia.

Tämän luovan potentiaalin ymmärtämiseksi paremmin, ensimmäisenä likiarvona, katsotaanpa QS-mallien luokittelua.

Sitä tarvitaan tehtävien 1-3 ratkaisemiseen. Alkutiedot on esitetty taulukossa. 2-4.

Joitakin merkintöjä, joita käytetään jonoteoriassa kaavoille:

n on kanavien lukumäärä QS:ssä;

λ - saapuvan sovellusvirran P in intensiteetti;

v - lähtevän sovellusvirran P out intensiteetti;

μ - palveluvirran P noin intensiteetti;

ρ - järjestelmän kuormituksen ilmaisin (liikenne);

m - jonon paikkojen enimmäismäärä rajoittaen hakemusjonon pituutta;

i - sovelluslähteiden lukumäärä;

p to - järjestelmän k:nnen tilan todennäköisyys;

p noin - koko järjestelmän joutoajan todennäköisyys, ts. todennäköisyys, että kaikki kanavat ovat vapaita;

p syst - hakemuksen hyväksymisen todennäköisyys järjestelmässä;

p otk - hakemuksen hylkäämisen todennäköisyys sen hyväksyessä järjestelmään;

p noin - todennäköisyys, että hakemus toimitetaan;

A on järjestelmän absoluuttinen suorituskyky;

Q on järjestelmän suhteellinen suorituskyky;

och - jonossa olevien sovellusten keskimääräinen lukumäärä;

o - käytössä olevien hakemusten keskimääräinen määrä;

syst - järjestelmän sovellusten keskimääräinen lukumäärä;

pt - hakemuksen keskimääräinen odotusaika jonossa;

o - hakemuksen keskimääräinen tiedoksiantoaika, joka koskee vain palveluita sovelluksia;

sys - sovelluksen keskimääräinen viipymisaika järjestelmässä;

exp - keskimääräinen aika, joka rajoittaa hakemuksen odottamista jonossa;

Keskimääräinen varattujen kanavien määrä.

QS A:n absoluuttinen suorituskyky on sovellusten keskimääräinen määrä, jonka järjestelmä voi palvella aikayksikköä kohti.

Suhteellinen QS-läpäisykyky Q on järjestelmän keskimääräisen palvelemien sovellusten lukumäärän aikayksikköä kohti suhde tänä aikana vastaanotettujen sovellusten keskimääräiseen määrään.

Jonoongelmia ratkaistaessa on noudatettava seuraavaa järjestystä:

1) QS-tyypin määrittäminen taulukon mukaan. 4,1;

2) kaavojen valinta QS-tyypin mukaan;

3) ongelmanratkaisu;

4) johtopäätösten muotoilu ongelmasta.

1. Kuoleman ja lisääntymisen kaavio.

Tiedämme, että kun meillä on käytössämme merkitty tilagraafi, voimme helposti kirjoittaa Kolmogorov-yhtälöitä tilatodennäköisyyksiin sekä kirjoittaa ja ratkaista algebralliset yhtälöt lopullisia todennäköisyyksiä varten. Joissakin tapauksissa on mahdollista ratkaista viimeiset yhtälöt etukäteen kirjaimellisessa muodossa. Tämä voidaan tehdä erityisesti, jos järjestelmän tilakaavio on ns. "kuolema- ja lisääntymiskaavio".

Kuoleman ja lisääntymisen kaavion tilakaavio on kuvan 2 mukaisessa muodossa. 19.1. Tämän graafin erikoisuus on, että kaikki järjestelmän tilat voidaan vetää yhdeksi ketjuksi, jossa jokainen keskimääräinen tila ( S 1 , S 2 , …, S n-1) on yhdistetty eteen- ja taaksepäin osoittavalla nuolella jokaiseen naapuritilaan - oikeaan ja vasempaan sekä ääritiloihin (S 0 , S n) — vain yhden naapurivaltion kanssa. Termi "kuoleman ja lisääntymisen suunnitelma" juontaa juurensa biologisista ongelmista, joissa populaation koon muutosta kuvataan tällaisella kaavalla.

Kuoleman ja lisääntymisen järjestelmä kohdataan hyvin usein erilaisissa käytännön ongelmissa, erityisesti - jonoteoriassa, joten on hyödyllistä kerta kaikkiaan löytää tilojen lopulliset todennäköisyydet sille.

Oletetaan, että kaikki tapahtumavirrat, jotka siirtävät järjestelmää kaavion nuolia pitkin, ovat yksinkertaisimpia (lyhyyden vuoksi kutsumme myös järjestelmää S ja siinä tapahtuva prosessi ovat yksinkertaisimmat).

Käyttämällä kuvan kaaviota. 19.1, muodostamme ja ratkaisemme algebrallisia yhtälöitä tilan lopullisille todennäköisyyksille), olemassaolo seuraa siitä, että jokaisesta tilasta voi mennä joka toiseen, tilojen määrä on äärellinen).

Ensimmäiselle osavaltiolle S 0 meillä on:

(19.1)

Toiselle osavaltiolle S1:

Johtuen (19.1) viimeinen yhtälö pelkistyy muotoon

missä k ottaa kaikki arvot 0:sta P. Lopulliset todennäköisyydet siis p0, p1,..., p n täyttävät yhtälöt

(19.2)

lisäksi meidän on otettava huomioon normalisointiehto

s 0 + s 1 + s 2 +…+ s n = 1. (19.3)

Ratkaistaan ​​tämä yhtälöjärjestelmä. Ensimmäisestä yhtälöstä (19.2) ilmaisemme s 1 kautta R 0 :

s 1 = s 0. (19.4)

Toisesta, ottaen huomioon (19.4), saamme:

(19.5)

kolmannesta, kun otetaan huomioon (19.5),

(19.6)

ja yleensä mille tahansa k(1 - n):

(19.7)

Kiinnitetään huomiota kaavaan (19.7). Osoittaja on kaikkien vasemmalta oikealle johtavien nuolien intensiteettien tulo (alusta annettu tila S k), ja nimittäjä on kaikkien oikealta vasemmalle johtavien nuolien intensiteettien tulo (alusta Sk).

Eli kaikki tilatodennäköisyydet R 0 , s 1 , ..., р n ilmaistaan ​​yhden heistä ( R 0). Korvataan nämä lausekkeet normalisointiehtoon (19.3). Saamme sulkeiden avulla R 0:

tästä syystä saamme ilmaisun for R 0 :

(nostimme sulkeet potenssiin -1, jotta emme kirjoita kaksikerroksisia murtolukuja). Kaikki muut todennäköisyydet ilmaistaan R 0 (katso kaavat (19.4)-(19.7)). Huomaa, että kertoimet for R 0 kussakin niistä ei ole muuta kuin sarjan peräkkäisiä jäseniä kaavan (19.8) yksikön jälkeen. Lasketaan siis R 0 , olemme jo löytäneet kaikki nämä kertoimet.

Saadut kaavat ovat erittäin hyödyllisiä jonoteorian yksinkertaisimpien ongelmien ratkaisemisessa.

2. Pieni kaava.

Nyt johdetaan yksi tärkeä kaava, joka liittyy (rajoittavaan, kiinteään järjestelmään) sovellusten keskimääräiseen määrään L syst, joka sijaitsee jonojärjestelmässä (eli palvellaan tai seisoo jonossa) ja sovelluksen keskimääräinen viipymäaika järjestelmässä W syst.

Tarkastellaan mitä tahansa QS:tä (yksikanavainen, monikanavainen, markolainen, ei-markolainen, rajoittamattomalla tai rajoitetulla jonolla) ja kaksi siihen liittyvää tapahtumavirtaa: QS:ään saapuvien asiakkaiden virta ja sieltä poistuvien asiakkaiden virta. QS. Jos järjestelmään on muodostettu rajoittava, stationäärinen järjestelmä, niin QS:ään saapuvien sovellusten keskimäärä aikayksikköä kohti on yhtä suuri kuin sieltä lähtevien sovellusten keskimääräinen määrä: molemmilla virroilla on sama intensiteetti λ.

Merkitse: X(t) — hakemusten määrä, jotka saapuivat yhteiseen markkinajärjestelyyn ennen tätä hetkeä t. Y(t) — yhteisestä markkinajärjestelystä lähteneiden hakemusten määrä

hetkeen asti t. Molemmat toiminnot ovat satunnaisia ​​ja muuttuvat äkillisesti (nousevat yhdellä) pyyntöjen saapuessa (X(t)) ja hakemusten lähdöt (Y(t)). Toimintojen tyyppi X(t) ja Y(t) esitetty kuvassa. 19,2; molemmat rivit ovat porrastettuja, ylempi on X(t), alempi- Y(t). Ilmeisesti hetkeksi tahansa t niiden ero Z(t)= X(t) - Y(t) on vain QS-sovellusten määrä. Kun linjat X(t) ja K(t) yhdistä, järjestelmässä ei ole pyyntöjä.

Harkitse hyvin pitkää ajanjaksoa T(jatkamalla kaaviota mielessään paljon piirustuksen jälkeen) ja laskea sille QS:n sovellusten keskimääräinen määrä. Se on yhtä suuri kuin funktion integraali Z(t) tällä aikavälillä jaettuna välin pituudella T:

L syst. = . (19.9) o

Mutta tämä integraali ei ole mitään muuta kuin kuvassa 1 varjostetun kuvan alue. 19.2. Katsotaanpa tätä piirrosta hyvin. Kuvio koostuu suorakulmioista, joiden jokaisen korkeus on yhtä ja kanta, joka vastaa viipymisaikaa vastaavan järjestyksen järjestelmässä (ensimmäinen, toinen jne.). Merkitään nämä ajat t1, t2,... Totta, väliajan lopussa T jotkut suorakulmiot tulevat varjostettuun kuvioon ei kokonaan, vaan osittain, mutta riittävän suurella T näillä pienillä asioilla ei ole väliä.

(19.10)

jossa määrä koskee kaikkia kyseisenä aikana vastaanotettuja hakemuksia T.

Erotetaan oikea ja vasen puoli(.19.10) välin pituudella T. Saamme, ottaen huomioon (19.9),

L syst. = . (19.11)

Jaa ja kerro oikea puoli(19.11) intensiteettiin X:

L syst. = .

Mutta suuruus Tλ on vain kyseisenä aikana vastaanotettujen hakemusten keskimääräinen määrä ^ T. Jos jaamme kaikkien aikojen summan t i hakemusten keskimääräisestä määrästä, niin saamme sovelluksen keskimääräisen viipymisajan järjestelmässä W syst. Niin,

L syst. = λ W syst. ,

W syst. = . (19.12)

Tämä on Littlen upea kaava: mille tahansa QS:lle, minkä tahansa tyyppiselle sovellusvirralle, mille tahansa palveluajan jakautumiselle, mille tahansa palvelualalle pyynnön keskimääräinen viipymäaika järjestelmässä on yhtä suuri kuin järjestelmässä olevien pyyntöjen keskimääräinen lukumäärä jaettuna pyyntövirran intensiteetillä.

Täsmälleen samalla tavalla johdetaan Littlen toinen kaava, joka kertoo keskimääräisen ajan, jonka sovellus viettää jonossa ^ Oho ja jonossa olevien hakemusten keskimääräinen määrä L oho:

W oho = . (19.13)

Tulosta varten se riittää kuvan alimman rivin sijaan. 19.2 ota funktio U(t)- tähän mennessä jäljellä olevien hakemusten määrä t ei järjestelmästä, vaan jonosta (jos järjestelmään tullut sovellus ei pääse jonoon, vaan menee heti palveluun, voidaan silti katsoa, ​​että se joutuu jonoon, mutta pysyy siinä nolla-aikaa) .

Littlen kaavoilla (19.12) ja (19.13) on tärkeä rooli jonoteoriassa. Valitettavasti useimmissa olemassa olevissa käsikirjoissa nämä kaavat (todistettu yleisnäkymä suhteellisen äskettäin) ei ole annettu 1).

Yksinkertaisimmat jonojärjestelmät ja niiden ominaisuudet

Tässä osiossa tarkastelemme joitain yksinkertaisimmista QS:istä ja johdamme lausekkeita niiden ominaisuuksille (suorituskykyindikaattorit). Samalla esittelemme alkeelliselle, "markovilaiselle" jonoteorialle tyypillisiä metodologisia tekniikoita.

Emme etsi niiden QS-näytteiden määrää, joille ominaisuuksien lopulliset lausekkeet johdetaan; tämä kirja ei ole opas jonoteoriaan (erikoisoppaat täyttävät tämän roolin paljon paremmin). Tavoitteenamme on esitellä lukijalle joitain "temppuja", jotka helpottavat jonoteorian läpikulkua, mikä useissa saatavilla olevissa (jopa suosituissa) kirjoissa voi tuntua vauhdikkaalta esimerkkikokoelmalta.

Kaikki tapahtumavirrat, jotka siirtävät QS:n tilasta tilaan, tässä osiossa tarkastelemme yksinkertaisinta (ilman että tätä joka kerta erikseen määrätään). Niiden joukossa on niin sanottu "palveluvirta". Se tarkoittaa yhden jatkuvasti varatun kanavan palvelemaa pyyntöjen virtaa. Tässä virrassa tapahtumien välisellä aikavälillä, kuten aina yksinkertaisimmassa virrassa, on eksponentiaalinen jakautuminen (monissa käsikirjoissa sanotaan sen sijaan: "palveluaika on eksponentiaalinen", me itse käytämme tätä termiä jatkossa).

Suositussa kirjassa esitetään hieman erilainen, yllä olevaan verrattuna, johtaminen Littlen kaavasta. Yleensä tutustuminen tähän kirjaan ("Second Conversation") on hyödyllinen jonoteoriaan tutustumiselle.

Tässä osiossa käyttöajan eksponentiaalinen jakautuminen pidetään itsestäänselvyytenä, kuten aina "yksinkertaisimmassa" järjestelmässä.

Esittelemme esityksen aikana tarkasteltavan QS:n tehokkuusominaisuudet.

1. P- kanava QS vioilla(Erlangin ongelma). Tässä tarkastelemme yhtä ensimmäisistä ajoissa, "klassisista" jonoteorian ongelmista; tämä ongelma syntyi puhelimen käytännön tarpeista ja sen ratkaisi vuosisadamme alussa tanskalainen matemaatikko Erlant. Tehtävä on asetettu seuraavasti: on P kanavat (viestintälinjat), jotka vastaanottavat sovellusvirran intensiteetillä λ. Palveluvirran intensiteetti on μ (keskimääräisen palveluajan käänteisluku t noin).

Etsi QS-tilojen lopulliset todennäköisyydet sekä sen tehokkuuden ominaisuudet:

^ A - absoluuttinen suorituskyky, eli keskimääräinen palveltujen sovellusten lukumäärä aikayksikköä kohti;

Q- suhteellinen läpimeno, eli järjestelmän palvelemien saapuvien pyyntöjen keskimääräinen osuus;

^ R otk- epäonnistumisen todennäköisyys, eli se, että sovellus jättää QS:n käyttämättä;

k - keskimääräinen varattujen kanavien määrä.

Ratkaisu. Järjestelmän tilat ^S(QS) numeroidaan järjestelmän pyyntöjen määrän mukaan (tässä tapauksessa se on sama kuin varattujen kanavien lukumäärä):

S 0 — yhteisessä markkinajärjestelyssä ei ole hakemuksia,

S 1 - QS:ssä on yksi pyyntö (yksi kanava on varattu, loput ovat vapaita),

Sk - SMO:ssa on k sovellukset ( k kanavat ovat varattuja, loput ovat ilmaisia),

S n - SMO:ssa on P sovellukset (kaikki n kanavat ovat varattu).

QS-tilakaavio vastaa lisääntymiskuoleman kaaviota (kuva 20.1). Merkitään tämä kaavio - lasketaan tapahtumavirtojen intensiteetti nuolien lähelle. From S 0 tuumaa S1 järjestelmää siirtää pyyntöjen virta, jonka intensiteetti on λ (niin kun pyyntö saapuu, järjestelmä hyppää S0 sisään S1). Sama pyyntövirta siirtää järjestelmän mistä tahansa vasemmasta tilasta viereiseen oikeaan tilaan (katso ylempiä nuolia kuvassa 20.1).

Laitetaan alas alempien nuolien voimakkuus. Anna järjestelmän olla tilassa ^S 1 (yksi kanava toimii). Se tuottaa μ palveluita aikayksikköä kohden. Astuimme nuolen kohdalle S 1 →S 0 intensiteetti μ. Kuvittele nyt, että järjestelmä on tilassa S2(kaksi kanavaa toimii). Jotta hän menisi S 1, on välttämätöntä, että joko ensimmäinen tai toinen kanava lopettaa huollon; niiden palveluvirtojen kokonaisintensiteetti on 2μ; laita se vastaavan nuolen kohdalle. Kolmen kanavan antaman kokonaispalveluvirran intensiteetti on 3 μ, k kanavat - km. Laitamme nämä intensiteetit alas kuvan 1 alempien nuolien kohdalle. 20.1.

Ja nyt, kun tiedämme kaikki intensiteetit, käytämme valmiita kaavoja (19.7), (19.8) lopullisille todennäköisyyksille kuoleman ja lisääntymisen kaaviossa.

Kaavan (19.8) mukaan saamme:

Hajotustermit ovat kertoimet p 0 ilmaisuissa for p1

Huomaa, että kaavat (20.1), (20.2) eivät sisällä intensiteettejä λ ja μ erikseen, vaan vain suhteena λ/μ. Merkitse

λ/μ = ρ (20,3)

Ja me kutsumme p:n arvoa "sovellusvirran vähentyneeksi intensiteetiksi". Sen merkitys on yhden pyynnön keskimääräiselle palveluajalle saapuvien pyyntöjen keskimääräinen määrä. Tätä merkintää käyttämällä kirjoitamme kaavat (20.1), (20.2) uudelleen muotoon:

Lopullisten tilatodennäköisyyksien kaavoja (20.4), (20.5) kutsutaan Erlang-kaavoiksi jonoteorian perustajan kunniaksi. Useimmilla tämän teorian muilla kaavoilla (nykyään niitä on enemmän kuin sieniä metsässä) ei ole erityisiä nimiä.

Siten lopulliset todennäköisyydet löytyvät. Niiden perusteella laskemme QS-tehokkuusominaisuudet. Ensin löydämme ^ R otk. - todennäköisyys, että saapuva pyyntö hylätään (ei toimiteta). Tätä varten on välttämätöntä, että kaikki P kanavat olivat kiireisiä, joten

R otk = R n = . (20.6)

Täältä löydämme suhteellisen suorituskyvyn - todennäköisyyden, että sovellus palvellaan:

Q = 1 - P avata = 1 - (20,7)

Saamme absoluuttisen suorituskyvyn kertomalla pyyntöjen virran intensiteetin λ:lla K:

A = λQ = λ. (20.8)

Jää vain löytää kiireisten kanavien keskimääräinen määrä k. Tämä arvo voidaan löytää "suoraan" diskreetin satunnaismuuttujan matemaattisena odotuksena mahdollisilla arvoilla 0, 1, ..., P ja näiden arvojen todennäköisyydet p 0 p 1 , ..., p n:

k = 0 · p 0+ yksi · p 1 + 2 · p 2 + ... + n · p n .

Korvaa tässä lausekkeet (20.5) for R k , (k = 0, 1, ..., P) ja suorittamalla sopivat muunnokset, saisimme lopulta oikean kaavan k. Mutta me johdamme sen paljon helpommin (tässä se on, yksi "pienistä temppuista"!) Todellakin, tiedämme absoluuttisen suorituskyvyn MUTTA. Tämä ei ole muuta kuin järjestelmän palvelemien sovellusten virtauksen intensiteetti. Jokainen käytetty i .shal aikayksikköä kohden palvelee keskimäärin |l pyyntöä. Keskimääräinen varattujen kanavien määrä on siis

k = A/μ, (20.9)

tai annettu (20.8),

k = (20.10)

Kannustamme lukijaa laatimaan esimerkin itse. Siellä on viestintäasema, jossa on kolme kanavaa ( n= 3), sovellusvirran intensiteetti λ = 1,5 (applikaatiota minuutissa); keskimääräinen palveluaika pyyntöä kohti t v = 2 (min.), kaikki tapahtumavirrat (kuten tässä koko kappaleessa) ovat yksinkertaisimpia. Etsi QS:n lopulliset tilatodennäköisyydet ja suorituskykyominaisuudet: A, Q, P otk, k. Varmuuden vuoksi tässä vastaukset: s 0 = 1/13, s 1 = 3/13, s 2 = 9/26, p 3 = 9/26 ≈ 0,346,

MUTTA≈ 0,981, K ≈ 0,654, P avoin ≈ 0,346, k ≈ 1,96.

Vastauksista muuten näkyy, että QS on suurelta osin ylikuormitettu: kolmesta kanavasta keskimäärin noin kaksi on varattu ja noin 35 % saapuvista sovelluksista jää palvelematta. Pyydämme lukijaa, jos hän on utelias eikä laiska, ottamaan selvää: kuinka monta kanavaa tarvitaan, jotta vähintään 80% saapuvista hakemuksista voidaan tyydyttää? Ja mikä osa kanavista on yhtä aikaa käyttämättömänä?

Siitä on jo jonkinlainen vihje optimointi. Itse asiassa kunkin kanavan sisältö aikayksikköä kohti maksaa tietyn summan. Samalla jokainen huollettu sovellus tuo jonkin verran tuloja. Kerrotaan nämä tulot hakemusten keskimääräisellä määrällä MUTTA, huollettu aikayksikköä kohti, saamme keskimääräiset CMO-tulot aikayksikköä kohti. Luonnollisesti kanavien määrän kasvaessa nämä tulot kasvavat, mutta myös kanavien ylläpitokustannukset kasvavat.

Mikä painaa enemmän - tulojen tai menojen kasvu? Se riippuu toiminnan ehdoista, "sovelluspalvelumaksusta" ja kanavan ylläpitokustannuksista. Kun tiedät nämä arvot, voit löytää optimaalisen kanavien määrän, kustannustehokkaimman. Emme ratkaise tällaista ongelmaa, vaan jätämme saman "laiskalle ja uteliaalle lukijalle" keksimään esimerkin ja ratkaisemaan sen. Yleensä ongelmien keksiminen kehittää enemmän kuin jonkun jo asettamien ratkaiseminen.

Yksikanavainen QS rajoittamattomalla jonolla.

Käytännössä yksikanavainen jonollinen QS on varsin yleistä (potilaita palveleva lääkäri; yhden kopin maksupuhelin; käyttäjien tilauksia täyttävä tietokone). Jonoteoriassa yksikanavaiset QS:t, joissa on jono, ovat myös erityisellä paikalla (useimmat tähän mennessä saaduista analyyttisistä kaavoista ei-Markov-järjestelmille kuuluvat sellaiseen QS:ään). Siksi kiinnitämme erityistä huomiota yksikanavaiseen QS:ään, jossa on jono.

Olkoon yksikanavainen QS, jossa on jono, jolle ei ole asetettu rajoituksia (ei jonon pituuden eikä odotusajan suhteen). Tämä QS vastaanottaa pyyntöjen virran, jonka intensiteetti on λ ; palveluvirran intensiteetti on μ, joka on käänteinen pyynnön keskimääräiseen palveluaikaan t noin.

On löydettävä QS-tilojen lopulliset todennäköisyydet sekä sen tehokkuuden ominaisuudet:

L syst. — järjestelmässä olevien sovellusten keskimääräinen määrä,

W syst. on pyynnön keskimääräinen viipymäaika järjestelmässä,

^L och- jonossa olevien hakemusten keskimääräinen määrä,

W och — keskimääräinen aika, jonka sovellus viettää jonossa,

P zan — todennäköisyys, että kanava on varattu (kanavan kuormitusaste).

Mitä tulee absoluuttiseen kaistanleveys MUTTA ja suhteellinen Q, niin niitä ei tarvitse laskea:

koska jono on rajoittamaton, jokainen hakemus toimitetaan ennemmin tai myöhemmin A \u003d λ, samasta syystä Q= 1.

Ratkaisu. Järjestelmän tilat, kuten ennenkin, numeroidaan QS:n sovellusten määrän mukaan:

S 0 — kanava on ilmainen

S 1 - kanava on varattu (palvelee pyyntöä), ei ole jonoa,

S 2 — kanava on varattu, yksi pyyntö on jonossa,

S k - kanava on varattu, k - 1 hakemusta on jonossa,

Teoreettisesti tilojen määrää ei rajoita mikään (äärettä). Tilakaavion muoto on kuvan mukainen. 20.2. Tämä on kuoleman ja lisääntymisen järjestelmä, mutta siinä on ääretön määrä tiloja. Kaikissa nuolissa pyyntöjen virta, jonka intensiteetti on λ, siirtää järjestelmän vasemmalta oikealle ja oikealta vasemmalle palveluvirran intensiteetillä μ.

Ensinnäkin kysykäämme itseltämme, onko tässä tapauksessa olemassa lopullisia todennäköisyyksiä? Loppujen lopuksi järjestelmän tilojen lukumäärä on ääretön, ja periaatteessa on t → ∞ jono voi kasvaa loputtomiin! Kyllä, se on totta: lopulliset todennäköisyydet tällaiselle QS:lle eivät aina ole olemassa, mutta vain silloin, kun järjestelmä ei ole ylikuormitettu. Voidaan osoittaa, että jos ρ on ehdottomasti pienempi kuin yksi (ρ< 1), то финальные вероятности существуют, а при ρ ≥ 1 очередь при t→ ∞ kasvaa loputtomasti.

Tämä tosiasia vaikuttaa erityisen "käsittämättömältä" ρ = 1:lle. Vaikuttaa siltä, ​​​​että järjestelmälle ei ole mahdottomia vaatimuksia: yhden pyynnön palvelemisen aikana saapuu keskimäärin yksi pyyntö ja kaiken pitäisi olla kunnossa, mutta todellisuudessa se on ei ole. Kun ρ = 1, QS käsittelee pyyntöjen virtaa vain, jos tämä vuo on säännöllinen, eikä palveluaika ole myöskään satunnainen, yhtä suuri kuin pyyntöjen välinen aika. Tässä "ihanteellisessa" tapauksessa QS:ssä ei ole lainkaan jonoa, kanava on jatkuvasti varattu ja lähettää säännöllisesti palvelupyyntöjä.

Mutta heti kun pyyntöjen virta tai palveluvirta tulee ainakin hieman satunnaiseksi, jono kasvaa jo loputtomasti. Käytännössä näin ei tapahdu vain siksi, että "ääretön määrä sovelluksia jonossa" on abstraktio. Tässä on joitain virheitä, jotka voivat johtaa vaihtamiseen satunnaismuuttujia heidän matemaattisia odotuksiaan!

Mutta palataanpa yksikanavaiseen QS:ään, jossa on rajoittamaton jono. Tarkkaan ottaen kuoleman ja lisääntymisen kaavion lopullisten todennäköisyyksien kaavat johdimme vain rajallisen määrän tiloja varten, mutta otetaan vapaudet - käytämme niitä äärettömälle määrälle tiloja. Lasketaan tilojen lopulliset todennäköisyydet kaavojen (19.8), (19.7) mukaan. Meidän tapauksessamme termien määrä kaavassa (19.8) on ääretön. Saamme ilmaisun p 0:

s 0 \u003d -1 \u003d (1 + p + p 2 + ... + p k + ... .) -1. (20.11)

Kaavan (20.11) sarja on geometrinen progressio. Tiedämme, että ρ< 1 ряд сходится — это бесконечно убывающая геометрическая прогрессия со знаменателем р. При р ≥ 1 ряд расходится (что является косвенным, хотя и не строгим доказательством того, что финальные вероятности состояний p 0 , p 1 , ..., p k , ... olemassa vain r:lle<1).

Oletetaan nyt, että tämä ehto täyttyy ja ρ1 + ρ + ρ 2 + ... + ρ k + ... = ,

s 0 = 1 - s. (20.12)

Todennäköisyydet p 1 , p 2 , ..., p k ,... löytyy kaavoilla:

p1 = ρ p 0, s 2= ρ2 p 0,…,p k = ρ p0, ...,

Mistä, ottaen huomioon (20.12), löydämme lopulta:

p1= ρ (1 - ρ), p2= ρ 2 (1 - ρ), . . . , p k =ρ k(1 - p), . . .(20.13)

Kuten näet, todennäköisyydet p0, p1, ..., p k,... muodostavat geometrisen progression nimittäjällä p. Kummallista kyllä, suurin niistä p 0 — todennäköisyys, että kanava on ilmainen. Riippumatta siitä, kuinka kuormitettu järjestelmä jonolla on, jos se vain pystyy selviytymään sovellusvirrasta (ρ<1), самое вероятное число заявок в системе будет 0.

Etsi hakemusten keskimääräinen määrä QS:stä ^L syst. . Tässä pitää vähän puuhailla. Satunnainen arvo Z- pyyntöjen määrä järjestelmässä - on mahdollisia arvoja 0, 1, 2, .... k,... todennäköisyyksien kanssa p0, p 1 , p 2 , ..., p k , ... Sen matemaattinen odotus on

L syst = 0? p 0+ 1 ? s 1 + 2 ? s 2 +…+k ? s k +…= (20.14)

(summaa ei oteta arvosta 0 arvoon ∞, vaan arvosta 1 arvoon ∞, koska nollatermi on yhtä suuri kuin nolla).

Korvataan kaavaan (20.14) lauseke for p k (20.13):

L syst. =

Nyt otetaan pois summan ρ (1-ρ) etumerkki:

L syst. = ρ(1-ρ)

Käytämme tässä taas "pientä temppua": kρ k-1 ei ole muuta kuin derivaatta lausekkeen ρ suhteen ρ:n suhteen k; tarkoittaa,

L syst. = ρ(1-ρ)

Vaihtamalla differentioinnin ja summauksen operaatiot keskenään saamme:

L syst. = ρ (1-ρ) (20.15)

Mutta summa kaavassa (20.15) ei ole mitään muuta kuin äärettömästi pienenevän geometrisen progression summa ensimmäisellä termillä ρ ja nimittäjällä ρ; Tämä summa

on yhtä suuri kuin , ja sen johdannainen on . Kun tämä lauseke korvataan lausekkeella (20.15), saadaan:

L syst = . (20.16)

No, nyt sovelletaan Littlen kaavaa (19.12) ja etsitään sovelluksen keskimääräinen viipymäaika järjestelmästä:

W syst = (20.17)

Etsi jonossa olevien sovellusten keskimääräinen määrä L och. Väittelemme seuraavasti: jonossa olevien sovellusten määrä on yhtä suuri kuin järjestelmän sovellusten määrä miinus palvelussa olevien sovellusten määrä. Joten (matemaattisten odotusten lisäyssäännön mukaan) jonossa olevien hakemusten keskimääräinen määrä L pt on yhtä suuri kuin järjestelmän sovellusten keskimääräinen lukumäärä L syst miinus palvelussa olevien pyyntöjen keskimääräinen määrä.

Palvelun alla olevien pyyntöjen määrä voi olla joko nolla (jos kanava on vapaa) tai yksi (jos se on varattu). Tällaisen satunnaismuuttujan matemaattinen odotus on yhtä suuri kuin todennäköisyys, että kanava on varattu (merkitsimme sitä R zan). Ilmeisesti R zan on yhtä suuri kuin yksi miinus todennäköisyys p 0 että kanava on ilmainen:

R zan = 1 - R 0 = p. (20.18)

Siksi palvelussa olevien pyyntöjen keskimääräinen määrä on yhtä suuri kuin

^L noin= ρ, (20.19)

L oho = L syst - ρ =

ja lopuksi

L pt = (20.20)

Littlen kaavan (19.13) avulla löydämme sovelluksen jonossa viettämän keskimääräisen ajan:

(20.21)

Siten kaikki QS-tehokkuuden ominaisuudet on löydetty.

Ehdotetaan lukijaa ratkaisemaan esimerkki itse: yksikanavainen QS on ratapiha, joka vastaanottaa yksinkertaisimman junavirran intensiteetillä λ = 2 (junia tunnissa). Palvelu (lakkautus)

sävellys kestää satunnaisen (demonstratiivisen) ajan keskiarvolla t noin = 20(min.). Aseman tulopuistossa on kaksi rataa, joilla saapuvat junat voivat odottaa palvelua; jos molemmat radat ovat ruuhkaisia, junat joutuvat odottamaan uloimmilla raiteilla.

On löydettävä (aseman rajoittavaa, paikallaan olevaa toimintatapaa varten): keskiarvo, junien lukumäärä l asemaan liittyvä järjestelmä, keskiaika W junan seisontajärjestelmä asemalla (sisäisillä radoilla, ulkoraiteilla ja huollettavana), keskimääräinen määrä L pt junia jonossa purkamista varten (ei väliä millä raiteilla), keskimääräinen aika W Pts pysyy kokoonpanossa jonotuslistalla. Yritä myös selvittää niiden junien keskimääräinen lukumäärä, jotka odottavat purkamista uloimmilla raiteilla. L ulkoinen ja tämän odotuksen keskimääräinen aika W ulkoinen (kaksi viimeistä määrää liittyvät Littlen kaavan mukaan).

Lopuksi selvitetään päiväsakko W, jonka asema joutuu maksamaan junien seisonnasta ulkoisilla raiteilla, jos asema maksaa sakkoa (ruplaa) yhden junan tunnin seisomisesta. Varmuuden vuoksi tässä vastaukset: L syst. = 2 (koostumus), W syst. = 1 (tunti), L pisteet = 4/3 (koostumus), W pt = 2/3 (tuntia), L ulkoinen = 16/27 (koostumus), W ulkoinen = 8/27 ≈ 0,297 (tuntia). Keskimääräinen päiväsakko W junien odottamisesta ulkoisilla raiteilla saadaan kertomalla asemalle saapuvien junien keskimäärä vuorokaudessa, junien keskimääräinen odotusaika ulkoraiteilla ja tuntisakko a: W ≈ 14,2 a.

kanava QS uudelleen rajoittamattomalla jonolla.

Täysin samanlainen kuin ongelma 2, mutta hieman monimutkaisempi ongelma n-kanava QS rajoittamattomalla jonolla.

μ 2μ kμ (k+1)μ nμ nμ nμ nμ nμ

On olemassa kuoleman ja lisääntymisen järjestelmä, mutta siinä on ääretön määrä tiloja. Ilmoitetaan ilman todisteita lopullisten todennäköisyyksien olemassaolon luonnollinen ehto: ρ/ n n ≥ 1, jono kasvaa äärettömään.

Oletetaan, että ehto ρ/ n < 1 выполнено, и финальные вероятности существуют. Применяя все те же формулы (19.8), (19.7) для схемы гибели и размножения, найдем эти финальные вероятности. В выражении для p 0 tulee joukko termejä, jotka sisältävät kertoimia plus loputtomasti pienenevän geometrisen progression summan nimittäjällä ρ/ n. Yhteenvetona löydämme

(20.22)

Etsitään nyt QS-tehokkuuden ominaisuudet. Näistä on helpoin löytää keskimääräinen varattujen kanavien lukumäärä k= λ/μ, = ρ (tämä pätee yleensä kaikille QS:ille, joissa on rajoittamaton jono). Etsi järjestelmän sovellusten keskimääräinen määrä L järjestelmä ja jonossa olevien sovellusten keskimääräinen määrä L och. Näistä on helpompi laskea toinen kaavan mukaan

L oho =

suorittaa vastaavat muunnokset tehtävän 2 näytteen mukaisesti

(sarjan eriyttämisellä) saamme:

L oho = (20.23)

Kun siihen lisätään palvelussa olevien sovellusten keskimääräinen määrä (se on myös varattujen kanavien keskimääräinen määrä) k =ρ, saamme:

L syst = L och + ρ. (20.24)

Jakolausekkeet for L och ja L syst on λ , Littlen kaavalla saadaan sovelluksen keskimääräinen viipymäaika jonossa ja järjestelmässä:

(20.25)

Ratkaistaan ​​nyt mielenkiintoinen esimerkki. Kahden ikkunan junalippukassa on kaksikanavainen QS, jossa on rajoittamaton jono, joka muodostetaan välittömästi kahteen ikkunaan (jos yksi ikkuna on vapaa, jonossa seuraava matkustaja ottaa sen). Lippukassa myydään lippuja kahdessa paikassa: A ja AT. Hakemusvirran intensiteetti (matkustajat, jotka haluavat ostaa lipun) molemmille kohdille A ja B on sama: λ A = λ B = 0,45 (matkustaja minuutissa), ja yhteensä ne muodostavat yleisen sovellusvirran, jonka intensiteetti on λ A + λB = 0,9. Kassa käyttää matkustajan palvelemiseen keskimäärin kaksi minuuttia.

Kokemus osoittaa, että lippukassalle kertyy jonoja, matkustajat valittavat palvelun hitaudesta. MUTTA ja sisään AT, luoda kaksi erikoistunutta lipputoimistoa (yksi ikkuna kummassakin), myymällä yksi lippu - vain asiaan MUTTA, toinen - vain asiaan AT. Tämän ehdotuksen järkevyys on kiistanalainen - jotkut väittävät, että jonot pysyvät ennallaan. Ehdotuksen hyödyllisyys on tarkistettava laskennallisesti. Koska pystymme laskemaan ominaisuuksia vain yksinkertaisimmille QS:lle, oletetaan, että kaikki tapahtumavirrat ovat yksinkertaisimpia (tämä ei vaikuta johtopäätösten laadulliseen puoleen).

No sitten mennään asiaan. Harkitse kahta vaihtoehtoa lipunmyynnin järjestämiseen - nykyistä ja ehdotettua.

Vaihtoehto I (olemassa). Kaksikanavainen QS vastaanottaa sovellusvirran, jonka intensiteetti on λ = 0,9; ylläpitovirtauksen intensiteetti μ = 1/2 = 0,5; ρ = λ/μ = l.8. Koska ρ/2 = 0,9<1, финальные вероятности существуют. По первой формуле (20.22) находим p 0 ≈ 0,0525. Keskiarvo, jonossa olevien sovellusten lukumäärä saadaan kaavalla (20.23): L och ≈ 7.68; asiakkaan keskimääräinen jonossa viettämä aika (ensimmäisen kaavan (20.25) mukaan) on yhtä suuri kuin W pts ≈ 8,54 (min.).

Vaihtoehto II (ehdotettu). On tarpeen harkita kahta yksikanavaista QS:ää (kaksi erikoisikkunaa); kukin vastaanottaa pyyntövirran, jonka intensiteetti on λ = 0,45; μ . edelleen yhtä suuri kuin 0,5; ρ = λ/μ = 0,9<1; финальные вероятности существуют. По формуле (20.20) находим среднюю длину очереди (к одному окошку) L och = 8.1.

Tässä yksi sinulle! Osoittautuu, että jonon pituus ei vain vähentynyt, vaan kasvoi! Ehkä keskimääräinen odotusaika jonossa on lyhentynyt? Katsotaan. Delya L pisteet λ = 0,45, saamme W pts ≈ 18 (minuuttia).

Siinä se rationalisointi! Vähenemisen sijaan sekä keskimääräinen jonon pituus että keskimääräinen odotusaika siinä kasvoivat!

Yritetään arvata miksi näin tapahtui? Aivojamme pohdittuamme päädymme siihen tulokseen: tämä tapahtui, koska ensimmäisessä versiossa (kaksikanavainen QS) keskimääräinen osa ajasta, jonka kumpikin kassasta on joutilaina, on pienempi: jos hän ei ole kiireinen palvelemaan matkustajaa, joka ostaa lipun MUTTA, hän voi huolehtia matkustajasta, joka ostaa lipun pisteeseen AT, ja päinvastoin. Toisessa versiossa tällaista vaihtokelpoisuutta ei ole: tyhjä kassa vain istuu joutilaina...

- Hyvin , OK, lukija on valmis samaa mieltä, kasvu voidaan selittää, mutta miksi se on niin merkittävä? Onko tässä joku laskuvirhe?

Ja me vastaamme tähän kysymykseen. Virhettä ei ole. tosiasia , että esimerkissämme molemmat QS:t toimivat kykyjensä rajoilla; jos hieman lisäät palveluaikaa (eli vähennät μ), he eivät enää selviä matkustajavirroista ja jono alkaa kasvaa loputtomasti. Ja kassan "ylimääräinen seisokki" on tavallaan sama kuin hänen tuottavuuden lasku μ.

Näin ollen laskelmien tulos, joka vaikuttaa aluksi paradoksaalliselta (tai jopa yksinkertaisesti väärältä), osoittautuu oikeaksi ja selitettäväksi.

Tällaiset paradoksaaliset johtopäätökset, joiden syy ei ole mitenkään ilmeinen, on rikas jonotusteoriassa. Kirjoittaja itse joutui toistuvasti "yllättämään" laskelmien tuloksista, jotka myöhemmin osoittautuivat oikeiksi.

Viimeistä tehtävää pohdittaessa lukija voi esittää kysymyksen näin: jos lippukassa myydään lippuja vain yhteen pisteeseen, niin luonnollisesti palveluajan pitäisi laskea, ei puoleen, mutta ainakin jonkin verran, mutta ajattelimme, että se oli silti keskiarvo on 2 (min.). Pyydämme niin nirsoa lukijaa vastaamaan kysymykseen: kuinka paljon sitä pitäisi pienentää, jotta "rationalisointiehdotuksesta" tulisi kannattava?

Taas tapaamme, vaikkakin alkeellisen, mutta silti optimointiongelman. Alustavien laskelmien avulla, jopa yksinkertaisimmilla, Markovin malleilla, on mahdollista selvittää ilmiön laadullinen puoli - kuinka kannattavaa on toimia ja miten se on kannattamatonta. Seuraavassa osiossa esittelemme joitain alkeellisia ei-markovialaisia ​​malleja, jotka laajentavat mahdollisuuksiamme entisestään.

Kun lukija on perehtynyt yksinkertaisimman QS:n lopputilan todennäköisyyksien ja suorituskykyominaisuuksien laskentamenetelmiin (hän ​​on hallinnut kuolema- ja lisääntymiskaavion sekä Pikku-kaavan), hänelle voidaan tarjota kaksi muuta yksinkertaista QS:tä itsenäiseen tarkasteluun.

Yksikanavainen QS rajoitetulla jonolla. Ongelma eroaa tehtävästä 2 vain siinä, että pyyntöjen määrä jonossa on rajoitettu (ei voi ylittää tiettyä t). Jos uusi pyyntö saapuu sillä hetkellä, kun kaikki jonon paikat ovat varattu, se jättää QS:n palvelematta (hylätty).

On tarpeen löytää tilojen lopulliset todennäköisyydet (muuten, ne ovat olemassa tässä tehtävässä mille tahansa ρ:lle - tilojen lukumäärä on loppujen lopuksi äärellinen), epäonnistumisen todennäköisyys R otk, absoluuttinen kaistanleveys MUTTA, todennäköisyys, että kanava on varattu R zan, keskimääräinen jonon pituus L och, hakemusten keskimääräinen määrä yhteisessä markkinajärjestelyssä L syst , keskimääräinen odotusaika jonossa W och , hakemuksen keskimääräinen viipymäaika yhteisessä markkinajärjestelyssä W syst. Jonon ominaisuuksia laskettaessa voidaan käyttää samaa tekniikkaa, jota käytimme tehtävässä 2, sillä erolla, että ei tarvitse tehdä yhteenvetoa äärettömästä etenemisestä, vaan äärellisestä.

Suljetun piirin QS yhdellä kanavalla ja m sovelluslähteet. Konkreettisuuden vuoksi asetetaan tehtävä seuraavaan muotoon: yksi työntekijä palvelee t koneet, joista jokainen vaatii säätöä (korjausta) aika ajoin. Kunkin työkoneen kysyntävirran intensiteetti on yhtä suuri kuin λ . Jos kone on epäkunnossa sillä hetkellä, kun työntekijä on vapaana, hän menee heti huoltoon.

Jos hän on epäkunnossa sillä hetkellä, kun työntekijällä on kiire, hän asettuu jonoon ja odottaa työntekijän vapautumista. Keskimääräinen asennusaika t kierrosluku = 1/μ. Työntekijälle tulevien pyyntöjen intensiteetti riippuu siitä, kuinka monta konetta toimii. Jos se toimii k työstökoneet, se on yhtä suuri kuin kλ. Selvitä lopullisen tilan todennäköisyydet, työkoneiden keskimääräinen lukumäärä ja todennäköisyys, että työntekijä on kiireinen.

Huomaa, että tässä QS:ssä lopulliset todennäköisyydet ovat olemassa myös kaikille arvoille λ ja μ = 1/ t o, koska järjestelmän tilojen määrä on äärellinen.

Edellisellä luennolla tarkasteltuna Markovin satunnainen prosessi, jossa on diskreetit tilat ja jatkuva aika, tapahtuu jonojärjestelmissä (QS).

Jonotusjärjestelmät - nämä ovat järjestelmiä, joissa palvelupyyntöjä vastaanotetaan satunnaisina aikoina, kun taas vastaanotettuja pyyntöjä palvellaan järjestelmän käytettävissä olevia palvelukanavia käyttäen.

Esimerkkejä jonojärjestelmistä ovat:

• maksu- ja kassasolmut pankeissa, yrityksissä;
• henkilökohtaiset tietokoneet, jotka palvelevat saapuvia sovelluksia tai vaatimuksia tiettyjen ongelmien ratkaisemiseksi;
• autojen huoltoasemat; huoltoasema;
• tilintarkastusyritykset;
• Verotarkastusosastot, jotka osallistuvat yritysten nykyisen raportoinnin hyväksymiseen ja tarkistamiseen;
• puhelinkeskukset jne.

	Solmut	Vaatimukset
Sairaala	järjestysmiehet	Potilaat
Tuotanto
Lentokenttä	Kiitotien uloskäynnit Rekisteröintipisteet	Matkustajat

Tarkastellaan QS-toiminnan kaaviota (kuva 1). Järjestelmä koostuu pyyntögeneraattorista, lähettäjästä ja palvelusolmusta, vikalaskentasolmusta (terminaattori, pyyntöhävittäjä). Palvelusolmulla voi yleensä olla useita palvelukanavia.

Riisi. yksi

1. Sovellusgeneraattori – kohde, joka tuottaa sovelluksia: katu, työpaja asennettuine yksiköineen. Syöte on sovelluskulku(asiakasvirta myymälään, rikkoutuneiden yksiköiden (autot, työstökoneet) virtaus korjauksiin, vierailijavirta vaatekaappiin, autojen virta huoltoasemille jne.).
2. Lähettäjä – henkilö tai laite, joka tietää mitä lipulla tehdä. Solmu, joka säätelee ja ohjaa pyyntöjä palvelukanaville. Lähettäjä:

• hyväksyy hakemuksia;
• muodostaa jonon, jos kaikki kanavat ovat varattu;
• ohjaa ne palvelukanaville, jos sellaisia ​​on;
• hylkää hakemukset (eri syistä);
• vastaanottaa palvelusolmulta tietoa vapaista kanavista;
• pitää kirjaa järjestelmän ajasta.

1. Vuoro - pyytää akkua. Jonoa ei ehkä ole olemassa.
2. Palvelusolmu koostuu rajallisesta määrästä palvelukanavia. Jokaisella kanavalla on 3 tilaa: vapaa, varattu, tyhjäkäynti. Jos kaikki kanavat ovat varattuja, voit keksiä strategian, kenelle sovellus siirretään.
3. Epääminen palvelusta tapahtuu, jos kaikki kanavat ovat varattu (jotkin niistä eivät ehkä toimi).

Näiden QS:n peruselementtien lisäksi jotkut lähteet erottavat myös seuraavat komponentit:

terminaattori - liiketoimien tuhoaja;

varasto - resurssien ja valmiiden tuotteiden varastointi;

kirjanpitotili - "kirjaus"-tyyppisten toimintojen suorittamiseen;

johtaja - resurssien johtaja;

Yhteisen markkinajärjestelyn luokittelu

Ensimmäinen jako (jonojen vuoksi):

• YMJ, jossa on epäonnistumisia;
• CMO jonolla.

AT CMO epäonnistumisineen pyyntö, joka saapuu sillä hetkellä, kun kaikki kanavat ovat varattu, hylätään, poistuu QS:stä eikä sitä palvella enempää.

AT CMO jonolla sovellus, joka saapuu aikana, jolloin kaikki kanavat ovat varattu, ei lähde, vaan jonottaa ja odottaa tilaisuutta palvella.

QS jonoilla on jaettu eri tyyppeihin riippuen siitä, miten jono on järjestetty - rajoitettu tai ei rajoitettu. Rajoitukset voivat liittyä sekä jonon pituuteen että odotusaikaan, "palvelukuriin".

Joten esimerkiksi seuraavat QS:t otetaan huomioon:

• QS kärsimättömillä pyynnöillä (jonon pituus ja palveluaika ovat rajoitettuja);
• QS prioriteettipalvelulla, eli joitain sovelluksia palvellaan vuorokauden ulkopuolella jne.

Jonorajoitustyyppejä voidaan yhdistää.

Toinen luokitus jakaa yhteisen markkinajärjestelyn hakemusten lähteen mukaan. Järjestelmä itse tai jokin järjestelmästä riippumaton ulkoinen ympäristö voi luoda sovelluksia (vaatimuksia).

Luonnollisesti järjestelmän itsensä luomien pyyntöjen virta riippuu järjestelmästä ja sen tilasta.

Lisäksi SMO:t on jaettu avata CMO ja suljettu SMO.

Avoimessa QS:ssä sovellusvirran ominaisuudet eivät riipu itse QS:n tilasta (kuinka monta kanavaa on varattu). Suljetussa QS:ssä ne riippuvat. Jos esimerkiksi yksi työntekijä huoltaa ajoittain säätöä vaativaa koneryhmää, niin koneista tulevien "vaatimusten" virtauksen intensiteetti riippuu siitä, kuinka moni niistä on jo hyvässä kunnossa ja odottaa säätöä.

Esimerkki suljetusta järjestelmästä: yrityksen kassan suorittama palkan myöntäminen.

Kanavien lukumäärän mukaan QS on jaettu:

• yksikanavainen;
• monikanavainen.

Jonojärjestelmän ominaisuudet

Kaikenlaisen jonojärjestelmän pääominaisuudet ovat:

• saapuvien vaatimusten tai palvelupyyntöjen syöttövirta;
• jonokuri;
• palvelumekanismi.

Vaatimukset syöttövirta

Jotta voit kuvata syöttövirran, sinun on asetettava todennäköisyyslaki, joka määrittää palveluvaatimusten vastaanottamisen hetkien järjestyksen, ja ilmoittaa tällaisten vaateiden lukumäärä jokaisessa tavallisessa kuitissa. Tässä tapauksessa ne toimivat pääsääntöisesti "vaatimusten vastaanottohetkien todennäköisyysjakauman" käsitteellä. Täällä voit toimia kuten yhden ja ryhmän vaatimukset (tällaisten vaateiden lukumäärä kussakin peräkkäisessä kuitissa). Jälkimmäisessä tapauksessa puhutaan yleensä jonotusjärjestelmästä, jossa on rinnakkaisryhmäpalvelu.

A i– saapumisaika vaatimusten välillä – riippumattomat identtisesti jakautuneet satunnaismuuttujat;

E(A) on keskimääräinen (MO) saapumisaika;

λ=1/E(A)- vaatimusten vastaanottamisen intensiteetti;

Tulovirran ominaisuudet:

1. Todennäköisyyslaki, joka määrittää palveluvaatimusten vastaanottamisen hetkien järjestyksen.
2. Pyyntöjen määrä jokaisen seuraavan saapumisen yhteydessä monilähetysvirtoja varten.

Jonokuri

Vuoro - joukko vaatimuksia, jotka odottavat huoltoa.

Jonolla on nimi.

Jonokuri määrittelee periaatteen, jonka mukaan palvelujärjestelmän tuloon saapuvat pyynnöt yhdistetään jonosta palveluproseduuriin. Yleisimmin käytetyt jonokurssit määritellään seuraavilla säännöillä:

• palvellaan saapumisjärjestyksessä;

ensimmäinen sisään ensimmäinen ulos (FIFO)

yleisin jonotyyppi.

Millainen tietorakenne soveltuu tällaisen jonon kuvaamiseen? Joukko on huono (rajoitettu). Voit käyttää LIST-rakennetta.

Listalla on alku ja loppu. Lista koostuu merkinnöistä. Merkintä on luettelosolu. Sovellus tulee luettelon loppuun, ja se valitaan palveluun luettelon alusta. Merkintä koostuu sovelluksen kuvauksesta ja linkistä (hakemisto siitä, kuka sen takana on). Lisäksi, jos jonossa on aikaraja, myös aikaraja on määritettävä.

Sinun ohjelmoijana pitäisi pystyä tekemään luetteloita kaksipuolisia, yksipuolisia.

Listaa toiminnot:

• työnnä häntään;
• ota alusta;
• poistaa luettelosta aikakatkaisun jälkeen.
• viimeksi tullut, palvellaan ensin LIFO (patruunapidike, umpikuja rautatieasemalla, meni täyteen autoon).

Rakenne, joka tunnetaan nimellä STACK. Voidaan kuvata taulukon tai listarakenteen avulla;

• sovellusten satunnainen valinta;
• hakemusten valinta prioriteettikriteerin mukaan.

Jokaiselle sovellukselle on tunnusomaista mm. prioriteettitaso, ja saapuessaan se ei sijoiteta jonon päähän, vaan prioriteettiryhmän loppuun. Lähettäjä lajittelee tärkeysjärjestyksen mukaan.

Jonon ominaisuudet

• rajoitusodotusaika palvelun esiintymishetki (palvelua varten on jono, jolla on rajoitettu odotusaika, joka liittyy käsitteeseen "sallittu jonon pituus");
• jonon pituus.

Palvelumekanismi

Palvelumekanismi sen määräävät itse palvelumenettelyn ominaisuudet ja palvelujärjestelmän rakenne. Huoltotoimenpiteitä ovat:

• palvelukanavien määrä ( N);
• palvelumenettelyn kesto (vaatimusten palveluajan todennäköisyysjakauma);
• kunkin tällaisen menettelyn täytäntöönpanon seurauksena täytettyjen vaatimusten määrä (ryhmähakemukset);
• palvelukanavan epäonnistumisen todennäköisyys;
• palvelujärjestelmän rakenne.

Huoltomenettelyn ominaisuuksien analyyttiseen kuvaukseen käytetään käsitettä "vaatimusten palveluajan todennäköisyysjakauma".

Si– palveluaika i vaatimus;

E(S)– keskimääräinen palveluaika;

μ=1/E(S)- palveluvaatimusten nopeus.

On huomattava, että sovelluksen huoltoon kuluva aika riippuu itse sovelluksen luonteesta tai asiakkaan vaatimuksista sekä palvelujärjestelmän tilasta ja kyvyistä. Joissakin tapauksissa on myös tarpeen ottaa huomioon palvelukanavan epäonnistumisen todennäköisyys tietyn rajoitetun ajanjakson jälkeen. Tämä ominaisuus voidaan mallintaa virhevirtana, joka tulee QS:ään ja jolla on etusija kaikkiin muihin sovelluksiin nähden.

QS:n käyttökerroin

Nμ – palvelunopeus järjestelmässä, kun kaikki huoltolaitteet ovat varattuina.

ρ=λ/( Nμ) kutsutaan QS:n käyttökerroin , näyttää kuinka paljon järjestelmäresursseja käytetään.

Palvelujärjestelmän rakenne

Palvelujärjestelmän rakenteen määrää palvelukanavien määrä ja keskinäinen järjestely (mekanismit, laitteet jne.). Ensinnäkin on korostettava, että palvelujärjestelmässä ei voi olla yhtä palvelukanavaa, vaan useita; tällainen järjestelmä pystyy palvelemaan useita vaatimuksia samanaikaisesti. Tässä tapauksessa kaikki palvelukanavat tarjoavat samoja palveluita, ja siksi voidaan väittää, että niitä on rinnakkaispalvelu .

Esimerkki. Kassakoneet kaupassa.

Palvelujärjestelmä voi koostua useista erityyppisistä palvelukanavista, joiden kautta jokaisen palvelutarpeen tulee kulkea eli palvelujärjestelmässä vaatimusten mukaiset huoltotoimenpiteet toteutetaan peräkkäin . Palvelumekanismi määrittelee lähtevän (palvelun) pyyntövirran ominaisuudet.

Esimerkki. Lääketieteellinen komissio.

Yhdistetty palvelu - talletusten hoitaminen säästöpankissa: ensin valvoja, sitten kassa. Pääsääntöisesti 2 ohjainta per kassa.

Niin, minkä tahansa jonotusjärjestelmän toimivuus määräytyy seuraavista päätekijöistä :

• palvelupyyntöjen vastaanottohetkien todennäköisyysjakauma (yksittäinen tai ryhmä);
• vaatimukset lähteen kapasiteetti;
• palvelun keston ajan todennäköisyysjakauma;
• palvelujärjestelmän konfigurointi (rinnakkais-, sarja- tai rinnakkaissarjapalvelu);
• palvelevien kanavien lukumäärä ja suorituskyky;
• jonokuri.

QS:n toiminnan tehokkuuden pääkriteerit

Kuten pääkriteerit jonojärjestelmien toiminnan tehokkuudelle Ratkaistavan ongelman luonteesta riippuen voi olla:

• vastaanotetun hakemuksen välittömän palvelun todennäköisyys (P-palvelu =K obs /K post);
• vastaanotetun hakemuksen palvelun epäämisen todennäköisyys (P otk =K otk /K post);

On selvää, että R obl + P otk =1.

Virrat, viiveet, palvelu. Pollacek-Khinchin kaava

Viive – yksi QS-palvelukriteereistä, aika, jonka pyyntö vie palvelun odotukseen.

D i– viive pyyntöjonossa i;

W i \u003d D i + S i– vaatimuksen järjestelmässä käytetty aika i.

(todennäköisyydellä 1) on jonossa olevan pyynnön määritetty keskimääräinen viive;

(todennäköisyydellä 1) on vakaan tilan keskimääräinen aika, jonka vaatimus viettää QS:ssä (odotuksessa).

Q(t) - jonossa olevien pyyntöjen määrä kerrallaan t;

L(t)– asiakasmäärä järjestelmässä kerrallaan t(Q(t) sekä sillä hetkellä käytössä olevien vaatimusten määrä t.

Sitten eksponentit (jos niitä on)

(todennäköisyydellä 1) on vakaan tilan aikakeskimääräinen pyyntöjen määrä jonossa;

(todennäköisyydellä 1) on vakaan tilan aikakeskiarvoinen pyyntöjen määrä järjestelmässä.

Huomaa, että ρ<1 – обязательное условие существования d, w, Q ja L jonojärjestelmässä.

Jos muistamme, että ρ= λ/( Nμ), silloin on selvää, että jos pyyntöjen vastaanoton intensiteetti on suurempi kuin Nμ, sitten ρ>1, ja on luonnollista, että järjestelmä ei pysty selviytymään sellaisesta sovellusvirrasta, joten ei voida puhua d, w, Q ja L.

Yleisimmät ja tarpeellisimmat tulokset jonojärjestelmille sisältävät säilymisyhtälöt

On huomattava, että yllä olevat kriteerit järjestelmän suorituskyvyn arvioimiseksi voidaan laskea analyyttisesti jonojärjestelmille M/M/N(N>1), eli järjestelmät, joissa on Markovin asiakas- ja palveluvirrat. varten M/G/ l mihin tahansa jakeluun G ja joihinkin muihin järjestelmiin. Yleensä aikajakauman saapuvien, palveluajan jakauman tai molempien on oltava eksponentiaalinen (tai eräänlainen k:nnen kertaluvun eksponentiaalinen Erlang-jakauma), jotta analyyttinen ratkaisu olisi mahdollista.

Lisäksi voit puhua myös sellaisista ominaisuuksista kuin:

• järjestelmän absoluuttinen suorituskyky – А=Р palvelu *λ;
• järjestelmän suhteellinen suorituskyky -

Toinen mielenkiintoinen (ja havainnollistava) esimerkki analyyttisestä ratkaisusta – vakaan tilan keskimääräisen jonoviiveen laskeminen jonotusjärjestelmälle M/G/ 1 kaavan mukaan:

.

Venäjällä tämä kaava tunnetaan Pollacekin kaavana. – Khinchin, ulkomailla tämä kaava liittyy Rossin nimeen.

Eli jos E(S) on suurempi arvo, kuin ylikuormitus (mitattu tässä tapauksessa muodossa d) on suurempi; mikä on odotettavissa. Kaava paljastaa myös vähemmän ilmeisen tosiasian: myös ruuhkat lisääntyvät, kun palveluaikajakauman vaihtelu kasvaa, vaikka keskimääräinen palveluaika pysyisi samana. Intuitiivisesti tämä voidaan selittää seuraavasti: palveluajan satunnaismuuttujan varianssi voi saada suuren arvon (koska sen on oltava positiivinen), eli ainoa palvelulaite on pitkään varattuna, mikä johtaa nousuun jonossa.

Aiheena jonoteoria on selvittää jonojärjestelmän toimivuutta määrittävien tekijöiden ja sen toiminnan tehokkuuden välinen suhde. Useimmissa tapauksissa kaikki jonojärjestelmiä kuvaavat parametrit ovat satunnaismuuttujia tai funktioita, joten näitä järjestelmiä kutsutaan stokastisiksi järjestelmiksi.

Sovellusvirran (vaatimusten) satunnaisuus, samoin kuin yleisessä tapauksessa palvelun kesto, johtaa siihen, että jonojärjestelmässä tapahtuu satunnainen prosessi. Satunnaisen prosessin luonteesta johtuen Jonotusjärjestelmässä (QS) esiintyvät erot Markovin ja ei-Markov-järjestelmät . Markovin järjestelmissä saapuvat pyynnöt ja lähtevät huolletut pyynnöt (vaatimukset) ovat Poisson. Poisson-virtojen avulla on helppo kuvata ja rakentaa jonojärjestelmän matemaattinen malli. Näissä malleissa on varsin yksinkertaiset ratkaisut, joten useimmat tunnetut jonoteorian sovellukset käyttävät Markovin kaavaa. Ei-Markovilaisten prosessien tapauksessa jonojärjestelmien tutkimisen ongelmat monimutkaistuvat ja vaativat tilastollisen mallintamisen, numeeristen menetelmien käyttöä tietokoneella.