Lihtsamate järjekorrasüsteemide matemaatilised mudelid. Lihtsamad järjekorrasüsteemid, kasutusnäited majandusprobleemide lahendamisel

Ülesanne 1. Saatekonsool võtab vastu päringute voo, mis on teist järku Erlangi voog. Rakenduste voo intensiivsus on 6 rakendust tunnis. Kui dispetšer lahkub konsoolist suvalisel hetkel, siis esimesel järgmisel nõudmisel peab ta konsooli tagasi pöörduma. Leidke järgmise päringu ooteaja jaotustihedus ja koostage selle graafik. Arvutage tõenäosus, et dispetšer võib puududa 10 kuni 20 minutit. Lahendus. Kuna teist järku Erlangi voog on piiratud järelmõjuga statsionaarne voog, siis selle jaoks kehtib Palmi valem

Kus f1(θ)- tõenäosusjaotuse tihedus esimese lähima sündmuse ooteaja kohta;
λ - voolu intensiivsus;
- voolu järjekord;
(θ) on tõenäosusjaotuse funktsioon Erlangi järjestuse voo (E) kahe kõrvuti asetseva sündmuse vahelise aja kohta.
On teada, et voolu E jaotusfunktsioonil on vorm

. (2)

Vastavalt ülesande tingimustele on rakenduste voog erlang järjestusega =2. Siis (1) ja (2) saame
.
Viimasest seosest λ=6 saame

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

Joonistame funktsiooni f1(θ) . Kell θ <0 meil on f1(θ) =0 . Kell θ =0 , f1(0)=3. Kaaluge piiri

Tüübi ebaselguse avalikustamise limiidi arvutamisel kasutati L'Hopitali reeglit. Uurimistöö tulemuste põhjal koostame funktsiooni graafiku f1(θ) (joonis 1).

Pöörame tähelepanu aja mõõtmetele ülesande tekstis: intensiivsuse jaoks on need rakendused tunnis, ajale, minutis. Liigume edasi ühe ajaühiku juurde: 10 minutit = 1/6 tundi, 20 minutit = 1/3 tundi. Nende väärtuste puhul saab arvutada f1(θ) ja täpsustada kõvera olemust

Need ordinaadid on näidatud vastavate kõvera punktide kohal oleval graafikul.
Tõenäosusteooria käigust on teada, et juhusliku suuruse tabamise tõenäosus X segmenti [α, β] on arvuliselt võrdne tõenäosustiheduse kõvera aluse pindalaga f(x). Seda ala väljendab kindel integraal

Seetõttu on soovitud tõenäosus võrdne

Seda integraali saab hõlpsasti osade kaupa arvutada, kui paneme
U=1+6θ Ja dV=e-6θdθ. Siis dU=6dθ Ja V= .
Kasutades valemit saame

Vastus: tõenäosus, et dispetšer võib puududa 10-20 minutit, on 0,28.

2. ülesanne. Väljapanekuruumis on 5 väljapanekut. Kasutajate voog on kõige lihtsam. Keskmine eksponeerimisruumi külastab ööpäevas 140 kasutajat. Ühe kasutaja info töötlemise aeg ühel kuvaril jaotub eksponentsiaalseaduse järgi ja on keskmiselt 40 minutit. Tehke kindlaks, kas saalil on statsionaarne töörežiim; tõenäosus, et kasutaja leiab, et kõik kuvad on hõivatud; keskmine kasutajate arv väljapanekuruumis; keskmine kasutajate arv järjekorras; keskmine tühikäigu kuvamisaeg; kasutaja kuvaruumis veedetud keskmine aeg. Lahendus. Probleemis käsitletav QS kuulub piiramatu järjekorraga mitmekanaliliste süsteemide klassi. Kanalite arv =5. Leiame päringuvoo λ-intensiivsuse: kus (tunnid) - keskmine aeg sissetuleva kasutajavoo kahe järjestikuse rakenduse vahel. Siis kasutaja/tund

Leiame - teenuse voo intensiivsus: , kus M[T teenus]=40 min=0,67 tundi – keskmine teenindusaeg ühe kasutaja kohta ühe ekraaniga,

Siis kasutaja/tund

Seega on selle süsteemi klassifikaatoril vorm CMO (5, ∞; 5,85; 1,49).
Arvutage QS-i koormustegur . On teada, et selle klassi QS-i puhul eksisteerib statsionaarne režiim, kui süsteemi koormusteguri ja kanalite arvu suhe on väiksem kui üks. Selle suhte leidmine
.
Seetõttu on statsionaarne režiim olemas. Valemite abil arvutatakse piirseisundi tõenäosusjaotus

Kuna =5, oleme

Arvutame P* – tõenäosus, et kasutaja leiab, et kõik kuvad on hõivatud. Ilmselgelt võrdub see selliste sündmuste tõenäosuste summaga: kõik kuvad on hõivatud, järjekorda pole (p5); kõik kuvad on hõivatud, üks kasutaja järjekorras (p6); kõik kuvarid on hõivatud, kaks kasutajat on järjekorras (p7) ja nii edasi. Kuna terve sündmuste rühma korral on nende sündmuste tõenäosuste summa võrdne ühega, siis võrdsus

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

Leiame need tõenäosused: ro=0,014; p1=3,93*0,014; p2=7,72*0,014; p3=10,12*0,014; p4=9,94*0,014.
Võttes ühisteguri sulgudest välja, saame
P*=1-0,0148*(1+3,93+7,72+10,12+9,94)=1-0,014*32,71=1-0,46=0,54.
Kas kasutada tulemusnäitajate arvutamiseks valemeid? leia:

• 1. keskmine kasutajate arv järjekorras

2. keskmine kasutajate arv väljapanekuruumis

3. Keskmine tasuta ekraani ooteaeg

4. kasutaja keskmine väljapanekuruumis veedetud aeg

Vastus: väljapanekuruumi statsionaarne töörežiim on olemas ja seda iseloomustavad järgmised näitajad R*=0,54; kasutaja; kasutaja; ; .

3. ülesanne. kahe kanaliga süsteemile järjekorras seismine(QS) riketega saabub statsionaarne Poissoni rakenduste voog. Kahe järjestikuse päringu saabumise vaheline aeg jaotatakse vastavalt eksponentsiaalseadusele parameetriga λ=5 päringut minutis. Iga päringu teenindamise kestus on 0,5 min. Monte Carlo meetodi abil leidke keskmine teenindatud päringute arv 4 minuti jooksul. Vihje: tehke kolm testi. Lahendus. Kujutagem etteantud QS töö statistilist modelleerimist ajadiagrammide abil. Tutvustame ajatelgede jaoks järgmist tähistust:
Vx- sissetulev rakenduste voog siin ti- avalduste laekumise hetk; Ti- ajavahemikud kahe järjestikuse rakenduse vahel. See on ilmne ti=ti-1 +Ti.
K1 - esimene teeninduskanal;
K2-teine ​​teeninduskanal; siin tähistavad paksud jooned ajateljel kanali hõivatud intervalle. Kui mõlemad kanalid on vabad, teenindatakse päringut kanalis K1, kui see on hõivatud, teenindab päringut kanal K2.
Kui mõlemad kanalid on hõivatud, jätab taotlus QS-i esitamata.
Out OB – teenindatud päringute väljuv voog.
Out PT on QS-i tõrgete tõttu kadunud päringute väljaminev voog (mõlemad kanalid on hõivatud).
Statistiline testimine jätkub teatud aja jooksul. Ilmselgelt iga ületunnitöö tmax tähendab päringu kukutamist väljuvasse voogu Out PT. Nii et joonisel fig. 3 avaldus nr 10, mis omal ajal süsteemi sisenes t10, ei jõua hetkeni kätte saada tmax, sest t10+Tmont.>tmax. Seetõttu ei aktsepteeri tasuta kanal K1 seda teeninduseks ja lähtestatakse väljund-PT-le, saades keeldumise.

Riis. 3

Ajastusskeemidelt on näha, et intervallide modelleerimist on vaja õppida Ti. Kasutame pöördfunktsioonide meetodit. Kuna juhuslik muutuja Ti jaotatud vastavalt eksponentsiaalseadusele parameetriga λ =5, siis on jaotustihedusel kuju f(τ)=5е-5τ. Siis väärtus F(Ti) tõenäosusjaotuse funktsiooni määrab integraal

.

On teada, et jaotusfunktsiooni vahemik F(T) seal on lõige. Valime juhuslike arvude tabelist arvu ja määrame Ti võrdsusest , kust . Kui aga . Seetõttu saate juhuslike arvude tabelist kohe rakendusi. Seega
e-5Ti= ri, või -5Ti= lnri, kus. Arvutuste tulemused on mugav sisestada tabelisse.
Testi nr 1 jaoks võeti juhuslikud arvud lisast 2, alustades esimese rea esimesest numbrist. Edasine proovide võtmine viidi läbi ridade kaupa. Teeme veel kaks testi.
Pöörake tähelepanu juhuslike arvude valikule lisa 2 tabelist, kui testis nr 1 oli taotluse nr 16 viimane juhuslik arv 0,37 (esimene juhuslik arv teisel real), siis test nr 2 algab sellega, et järgmine juhuslik arv 0,54 . Katse nr 2 sisaldab viimast juhuslikku numbrit 0,53 (viies number kolmandas reas). Seetõttu algab kolmas test numbriga 0,19. Üldjuhul valitakse sama testide seeria raames tabelist juhuslikud arvud ilma lünkadeta ja sisestamisteta kindlas järjekorras, näiteks ridadena.

Tabel 1. TEST nr 1

Taotlus nr. i	Sl. number ri		-Ln ri Ti	Avalduse kättesaamise hetk ti=ti-1+Ti	Teenindusaja lõpp. ti+0,50		Rakenduste loendur
					K1

Tabel 2 TEST nr 2

Taotlus nr. i	Sl. number ri		-Ln ri Ti	Avalduse kättesaamise hetk ti=ti-1+Ti	Teenindusaja lõpp. ti+0,50		Rakenduste loendur

Tabel #3 TEST #3

Taotlus nr. i		Sl. number ri		-Ln ri Ti	Avalduse kättesaamise hetk ti=ti-1+Ti	Teenindusaja lõpp. ti+0,50		Rakenduste loendur
						K1

Seega oli kolme testi tulemuste kohaselt teenindatud rakenduste arv vastavalt: x1=9, x2=9, x3=8. Leidke teenindatud taotluste keskmine arv:

Vastus: QS-i keskmine taotluste arv 4 minuti jooksul on 8,6(6).

Eesmärgid

Järjekorrateadmiste alused, mida mõnikord nimetatakse järjekorrateooriaks või järjekorrateooriaks, moodustavad olulise osa tootmise juhtimise teooriast. Järjekorrad on tavalised. Nad võivad kanda vormiriietust autoteeninduses remonti oodates või üliõpilased, kes ootavad professori konsultatsiooni. Tabelis on mõned näited järjekorrast järjekorrasüsteemides:

Järjekorramudelid (nt lineaarne programmeerimine, varude juhtimise mudelid, meetodid võrgu analüüs projektid) kasutatakse nii materjalitootmise juhtimise kui ka teenindussektoris. Järjekordade analüüsimine järjekorra pikkuse, keskmise ooteaja, keskmise teenindusaja ja muude tegurite järgi aitab meil paremini mõista, kuidas teenindussüsteem on organiseeritud. Patsiendi ootamine arsti ootesaalis ja katkise puuri parandamise ootamine remonditöökojas on teenuse juhtimises palju ühist. Mõlemad protsessid kasutavad klientide vajaduste rahuldamiseks inimressursse ja seadmeressursse.

Professionaalne juht, võttes enda õlule järjekorrasüsteemi täiustamise, hindab muudatusi, mis tekivad süsteemi opereerimiskuludes ja klientide ootamisega kaasnevates kuludes. Saab palgata suur hulk töötajad, kes teenindavad kliente kiiresti. Näiteks saab supermarketi administraator vähendada kassade järjekordi, suurendades tipptundidel müüjate ja kassapidajate arvu. Pankade või lennujaamade kassadesse võib tipptundidel kaasata täiendavaid töötajaid. Ooteaja vähendamine on aga tavaliselt seotud töökohtade loomise ja varustamise kuludega, lisatööjõu tasustamisega. Need kulud võivad olla üsna märkimisväärsed.

Saate säästa tööjõukulusid. Kuid siis ei pruugi klient teenust oodata või kaotab soovi uuesti naasta. Viimasel juhul tekib järjekorrasüsteemile kahju, mida võib nimetada ootekuludeks. Mõnedes teenindussüsteemides, näiteks kiirabiautodes, võivad pikkade ooteaegadega seotud kulud olla äärmiselt suured. Järjekorrasüsteemide täiustamise peamine majanduslik põhimõte on prognoosida eeldatavaid kogukulusid, sealhulgas teenuskulusid ja kahjusid, mis süsteemile kliendi ootamise tõttu tekivad.

Pärast selle peatüki ülesannete täitmist saate määratleda ja kasutada majandusanalüüsi jaoks järgmisi mõisteid.

Järjekorrasüsteem;

Järjekord;

Taotluste laekumise määr;

Teenuse tempo;

Keskmine aeg, mille rakendus järjekorras viibib;

Keskmine järjekorra pikkus;

Keskmine aeg, mille rakendus veedab teenindussüsteemis;

Keskmine klientide arv teenindussüsteemis;

Teenindussüsteemi toimimise kulud;

Ootekulud.

Mudelid

Järjekorrasüsteemide klassifitseerimistunnused.

Järjekorrasüsteemides on kolm peamist etappi, mille iga rakendus läbib:

1) rakenduse ilmumine süsteemi sissepääsu juurde;

2) järjekorra läbimine;

3) teenindusprotsess, mille järel rakendus süsteemist lahkub.

Igas etapis kasutatakse teatud karakteristikuid, mida tuleks enne matemaatiliste mudelite koostamist arutada.

Sisendi spetsifikatsioonid:

1) taotluste arv sissepääsu juures (rahvastiku suurus);

2) taotluste vastuvõtmise viis teenindussüsteemi;

3) kliendi käitumine.

Taotluste arv sissepääsu juures. Potentsiaalsete rakenduste arvu (populatsiooni suurust) võib pidada kas lõpmatuks (piiramatu populatsioon) või lõplikuks (piiratud populatsioon). Kui süsteemi sisenevate klientide arv alates teenindusprotsessi algusest kuni mis tahes ajahetkeni on vaid väike osa potentsiaalsest klientide arvust, loetakse sisendpopulatsiooniks Piiramatu. Näited piiranguteta elanikkonnast: autod, mis läbivad kiirteede kontrollpunkte, ostlejad supermarketis jne. Enamiku sissepääsu järjekordade mudelite puhul arvestatakse piiramatute elanike arvuga.

Kui süsteemi sisenevate klientide arv on võrreldav juba järjekorrasüsteemis olevate klientide arvuga, arvestatakse populatsiooni Piiratud. Piiratud populatsiooni näide: kindlale organisatsioonile kuuluvad arvutid, mida hooldab remonditöökoda.

Taotluste vastuvõtmise viis teenindussüsteemis. Rakendused võivad siseneda teenindussüsteemi kindla ajakava järgi (näiteks üks patsient hambaarsti juurde iga 15 minuti järel, üks auto koosteliinil iga 20 minuti järel) või juhuslikult. Klientide külastused lähevad arvesse juhuslik, kui need on üksteisest sõltumatud ja täpselt ettearvamatud. Sageli saab järjekorraprobleemide korral esinemiste arvu ajaühiku kohta hinnata Poissoni tõenäosusjaotuse abil. Teatud sisenemiskiirusega (näiteks kaks klienti tunnis või neli veokit minutis) diskreetne jaotus Poissonit kirjeldatakse järgmise valemiga:

Kus P(x) - vastuvõtmise tõenäosus X rakendused ajaühiku kohta;

X - taotluste arv ajaühiku kohta;

L on taotluste keskmine arv ajaühikus (taotluste laekumise määr);

Vastavad tõenäosused P(x) on Poissoni jaotustabeli abil lihtne kindlaks teha. Kui näiteks päringute keskmine laekumise määr on kaks klienti tunnis, siis tõenäosus, et tunni jooksul ei jõua süsteemi ühtegi päringut, on 0,135, ühe päringu tõenäosus on umbes 0,27 ja kaks on samuti umbes 0,27 , kolm nõuet võivad ilmneda tõenäosusega 0,18, neli väidet umbes 0,09 jne Tõenäosus, et tunni jooksul jõuab süsteemi 9 või enam nõuet, on nullilähedane.

Praktikas ei järgi rakenduste esinemise tõenäosused muidugi alati Poissoni jaotust (neil võib olla mõni muu jaotus). Seetõttu on nõutav eeluuringud et kontrollida, kas Poissoni jaotus võib olla hea ligikaudne väärtus.

Kliendi käitumine. Enamik järjekorramudeleid põhinevad eeldusel, et kliendi käitumine on standardne, st iga süsteemi sisenev klient siseneb järjekorda, ootab teenindust ega lahku süsteemist enne, kui seda on teenindatud. Teisisõnu, järjekorda astunud klient (inimene või masin) ootab, kuni teda teenindatakse, lahkub järjekorrast ja liigub ühest järjekorrast teise.

Elu on palju raskem. Praktikas võivad kliendid järjekorrast lahkuda, kuna see on liiga pikk. Võib tekkida teine ​​olukord: kliendid ootavad oma järjekorda, kuid jätavad mingil põhjusel teenindamata. Need juhtumid on ka järjekorrateooria teemaks, kuid neid siin ei käsitleta.

Järjekorra omadused:

2) teeninduseeskiri.

Järjekorra pikkus. Pikkus võib, aga ei pruugi olla piiratud. Järjekorra pikkus (järjekord) Piiratud kui mingil põhjusel (näiteks füüsilised piirangud) ei saa lõputult suureneda. Kui järjekord jõuab oma maksimaalne suurus, siis järgmine rakendus süsteemis ei ole lubatud ja toimub keeldumine. Järjekorra pikkus Pole piiratud, Kui järjekorras saab olla suvaline arv rakendusi. Näiteks autode järjekord tanklas.

teeninduse reegel. Enamik reaalseid süsteeme kasutab esimene sisse, esimene välja reeglit. (FIFO- esimene sisse, esimene välja). Mõnel juhul, näiteks haigla kiirabis, lisaks sellele reeglile mitmesugused Prioriteedid. Südameinfarktiga kriitilises seisundis patsiendil on tõenäoliselt hooldusel eelisõigus murtud sõrmega patsiendi ees. Arvutiprogrammide käivitamise järjekord on teenuste prioritiseerimise teine ​​näide.

Teenindusprotsessi omadused:

1) teenindussüsteemi konfiguratsioon (kanalite arv ja teenindusfaaside arv);

2) hooldusrežiim.

Teenindussüsteemi konfiguratsioon. Teenindussüsteemid erinevad Teeninduskanalite arv. Tavaliselt saab kanalite arvu määratleda kui klientide arvu, keda saab samal ajal teenindada, näiteks: juuksuri meistrite arv. Näited üks kanal teenindussüsteemid: pank, millel on üks aken klienditeeninduseks, või restoran, mis teenindab kliente autodes. Kui pangas on avatud mitu teenindusakent, klient ootab üldjärjekorras ja läheneb esimesele vabale aknale, siis tegeleme Mitme kanaligaühefaasiline hooldussüsteem. Enamik panku, aga ka postkontoreid ja lennupiletite kassasid, on mitme kanaliga teenindussüsteemid.

Teine funktsioon - Faaside arv(või järjestikused etapid) Teenusedüks klient. üksik faas on sellised süsteemid, kus klienti teenindatakse ühes punktis (ühes töökohas), seejärel lahkutakse süsteemist. Ühefaasilise süsteemi näide on autoteenindusrestoran, kus kelner saab raha vastu ja toob tellimuse autosse. Kui restoranis on vaja ühes kohas tellimus esitada, teises selle eest tasuda ja kolmandas süüa saada, siis on meil tegemist mitmefaasiline(kolmefaasiline) hooldussüsteem.

Joonisel fig. 1 kujutab erineva konfiguratsiooniga teenindussüsteeme.

Hooldusrežiim. Lisaks päringute vastuvõtmise režiimile saab teenindusrežiimi iseloomustada kas konstantse või juhusliku teenindusajaga. Kell Alaline Sama palju aega kulub iga kliendi teenindamiseks. Sellist olukorda saab jälgida automaatpesulas. Sagedamini tuleb aga ette olukordi, kus teenistusaeg on käes Juhuslik levitamine. Paljudel juhtudel võib eeldada, et teenindusaeg järgib jaotusfunktsiooniga eksponentsiaalset jaotust

F( T ) = P(T< t) =1 – e–tm, kus R (T< t) on tõenäosus, et tegelik aeg T teenusetaotlus ei ületa määratud väärtust t;

M - keskmine kättetoimetatud taotluste arv ajaühiku kohta;

E \u003d 2,7182 - naturaalse logaritmi alus.

Järjekorramudelite parameetrid. Järjekorrasüsteemide analüüsimisel kasutatakse tehnilisi ja majanduslikke näitajaid.

Järgmised on kõige sagedamini kasutatavad Tehnilised andmed:

1) keskmine aeg, mille klient sabas viibib;

2) järjekorra keskmine pikkus;

3) kliendi keskmine teenindussüsteemis veedetud aeg (ooteaeg pluss teenindusaeg);

4) keskmine klientide arv teenindussüsteemis;

5) teenindussüsteemi jõudeoleku tõenäosus;

6) teatud arvu klientide tõenäosus süsteemis.

hulgas Majanduslikud omadused kõige huvitavamad on järgmised:

1) järjekorras seismise kulu;

2) süsteemis ootamise kulud;

3) ülalpidamiskulud.

Järjekorrasüsteemide mudelid. Sõltuvalt ülaltoodud omaduste kombinatsioonist võib kaaluda erinevaid järjekorrasüsteemide mudeleid.

Siin vaatleme mõningaid kuulsamaid mudeleid. Neil kõigil on järgmised ühised omadused:

A) Taotluste laekumise tõenäosuse Poissoni jaotus;

B) kliendi standardkäitumine;

B) teenindusreegel FIFO(kes ees, see mees);

D) ainus teenindusfaas.

I. Mudel A - ühe kanaliga järjekorrasüsteemi mudel MM/ 1 s Poisson sissetulev rakenduste voog ja Eksponentsiaalne teenindusaeg.

Kõige levinumad järjekorraprobleemid ühe kanaliga. Sel juhul moodustavad kliendid ühe järjekorra ühte teeninduspunkti. Oletame, et seda tüüpi süsteemide puhul on täidetud järgmised tingimused:

1. Taotlused toimetatakse kätte, see mees, see mees (FIFO) pealegi ootab iga klient oma järjekorra lõppu, olenemata järjekorra pikkusest.

2. Taotluste ilmumised on iseseisvad sündmused, kuid keskmine saabuvate avalduste arv ajaühiku kohta on muutumatu.

3. Taotluste vastuvõtmise protsessi kirjeldab Poissoni jaotus ja rakendusi tuleb piiramatust hulgast.

4. Kasutusaega kirjeldatakse eksponentsiaalse tõenäosusjaotusega.

5. Teenuse määr on kõrgem kui taotluste laekumise määr.

Olgu l rakenduste arv ajaühiku kohta;

M on teenindatavate klientide arv ajaühikus;

P - rakenduste arv süsteemis.

Seejärel kirjeldatakse järjekorrasüsteemi allpool toodud võrranditega.

Valemid süsteemi M/M/ kirjeldamiseks 1:

- keskmine klientide arv süsteemis;

Keskmine teenindusaeg kliendi kohta süsteemis (ooteaeg pluss teenindusaeg);

Keskmine klientide arv järjekorras;

Keskmine kliendi ooteaeg järjekorras;

süsteemi koormuse karakteristikud (aja osakaal, mille jooksul süsteem on hõivatud teenindusega);

rakenduste puudumise tõenäosus süsteemis;

Tõenäosus, et süsteem sisaldab rohkem kui K rakendusi.

II. Mudel B - mitmekanaliline teenindussüsteem M/M/S. Mitme kanaliga süsteemis on teeninduseks avatud kaks või enam kanalit. Eeldatakse, et kliendid ootavad üldjärjekorras ja kandideerivad esimesele tasuta teenusekanalile.

Sellise mitme kanaliga ühefaasilise süsteemi näidet võib näha paljudes pankades: üldisest järjekorrast lähevad kliendid teenuse saamiseks esimesse tasuta aknasse.

Mitme kanaliga süsteemis sõltub päringute voog Poisson seadus ja teenistusaeg - Eksponentsiaalne. Esimesena teenindatakse esimest tulijat ja kõik teeninduskanalid töötavad samas tempos. Mudelit kirjeldavad valemid IN,üsna raske kasutada. Mitme kanaliga järjekorrasüsteemi parameetrite arvutamiseks on mugav kasutada vastavat tarkvara.

Aeg, mil taotlus oli järjekorras;

Rakenduse poolt süsteemis kulutatud aeg.

III. Mudel C- konstantse hooldusajaga mudel M/D/ 1.

Mõnel süsteemil on püsiv, mitte eksponentsiaalselt jaotatud teenindusaega. Sellistes süsteemides teenindatakse kliente kindla aja jooksul, näiteks automaatpesulas. Modelli jaoks KOOS Konstantse teenindusväärtuste määraga Lq Ja wq Pool vastavatest väärtustest mudelis A, muutuva teenusemääraga.

Mudelit C kirjeldavad valemid:

- keskmine järjekorra pikkus;

- keskmine ooteaeg järjekorras;

Keskmine klientide arv süsteemis;

Keskmine ooteaeg süsteemis.

IV. Mudel D - piiratud elanikkonnaga mudel.

Kui number potentsiaalsed kliendid teenindussüsteemid piiratud, meil on tegemist erimudeliga. Selline probleem võib tekkida näiteks siis, kui me räägime viie masinaga tehase sisseseade hooldamise kohta.

Selle mudeli eripära võrreldes kolme varem vaadeldud mudeliga on see, et see on olemas Vastastikune sõltuvus järjekorra pikkuse ja avalduste laekumise määra vahel.

v. Mudel E - piiratud järjekorraga mudel. Mudel erineb eelmistest kohtade arvu poolest järjekorras Piiratud. Sel juhul jätab päring, mis saabus süsteemi siis, kui kõik kanalid ja järjekorras olevad kohad on hõivatud, süsteemi teenindamata, st keeldutakse.

Piiratud järjekorra mudeli erijuhtumina võib kaaluda ebaõnnestumise mudel, kui järjekorra kohtade arv väheneb nullini.

Järjekorrasüsteemide erinevate mudelite võrdlusomadused on toodud järgmises tabelis.

Matemaatiline (abstraktne) objekt, mille elemendid on (joonis 2.1):

• sisend (sissetulev) rakenduste voog (nõuded) teenuse jaoks;
• teenindusseadmed (kanalid);
• teenust ootavate rakenduste järjekord;
• teenindatavate päringute väljund (väljaminev) voog;
• järelhoolduse taotluste voog pärast teenuse katkemist;
• esitamata taotluste voog.

Rakendus(taotlus, nõue, kõne, klient, sõnum, pakett) - QS-i sisenev objekt, mis vajab seadmes teenust. Järjestikuste rakenduste kogum, mis jaotatakse ajaliselt rakenduste sisendvoog.

Riis. 2.1.

teenindusseade(seade, seade, kanal, liin, tööriist, auto, ruuter jne) - QS-element, mille eesmärk on rakendusi teenindada.

Teenindus- päringu viivitus teenindusseadmes mõnda aega.

Teenuse kestus- rakenduse viivitusaeg (teenus) seadmes.

Salvestusseade(puhver, sisendpuhver, väljundpuhver) - kohtade komplekt rakenduste ootamiseks teenindava seadme ees. Ootekohtade arv - mälumaht.

CMO-le saabunud taotlus võib olla kahes olekus:

• 1) teenus(seadmes);
• 2) ootustele(akus), kui kõik seadmed on hõivatud muude päringute teenindamisega.

Nõuded akumulaatori ja ootel teenuse vormil järjekorda rakendusi. Teenust ootavate rakenduste arv akumulaatoris - järjekorra pikkus.

Puhverdistsipliin(järjekorra distsipliin) - sissetulevate rakenduste draivi (puhvrisse) sisestamise reegel.

Teenindusdistsipliin- seadme teenindusjärjekorrast päringute valimise reegel.

Prioriteet- eelisõigus (ressursside hõivamiseks) siseneda akumulaatorisse või valida hooldusjärjekorrast ühe klassi seadmerakendustes teiste klasside rakenduste suhtes.

On palju järjekorrasüsteeme, mis erinevad struktuurselt ja funktsionaalne organisatsioon. Samal ajal hõlmab QS tulemusnäitajate arvutamise analüütiliste meetodite väljatöötamine paljudel juhtudel mitmeid piiranguid ja eeldusi, mis kitsendavad uuritavate QS-ide kogumit. Sellepärast üldine analüütiline mudel suvalise QS jaoks keeruline struktuur ei eksisteeri.

QS-i analüütiline mudel on võrrandite või valemite kogum, mis võimaldab määrata sissetuleva voo ja teeninduskanalite, puhverdus- ja teenindusdistsipliinide teadaolevate parameetrite põhjal süsteemi olekute tõenäosusi selle töö käigus ja jõudlusnäitajaid.

QS-i analüütilist modelleerimist hõlbustab oluliselt see, kui QS-is toimuvad protsessid on markovilikud (rakenduste vood on kõige lihtsamad, teenindusajad jaotuvad eksponentsiaalselt). Sel juhul saab kõiki QS-i protsesse kirjeldada tavalisega diferentsiaalvõrrandid, ja piirjuhul - statsionaarsete olekute puhul - lineaarsete algebraliste võrrandite abil ja pärast nende lahendamist matemaatika tarkvarapakettides saadaolevate meetoditega määrata valitud jõudlusnäitajad.

IM-süsteemides aktsepteeritakse QS-i rakendamisel järgmisi piiranguid ja eeldusi:

• süsteemi sisestatud rakendus koheselt langeb kasutusse, kui järjekorras pole päringuid ja seade on vaba;
• seadmes hooldust igal ajal saab ainult üks rakendus;
• pärast seadme mis tahes päringu teenindamise lõppu valitakse koheselt teenindamiseks järjekorrast järgmine päring, st seade tühikäigul ei käi kui järjekorras on vähemalt üks taotlus;
• taotluste laekumine QS-i ja nende teenindamise kestus ei sõltu juba süsteemis olevate taotluste arvust ega muudest teguritest;
• teenindamispäringute kestus ei sõltu süsteemi sisenevate päringute intensiivsusest.

Vaatleme üksikasjalikumalt mõnda QS-i elementi.

Sisend (sissetulev) rakenduste voog. Sündmuste voog nimetatakse homogeensete sündmuste jadaks, mis järgnevad üksteise järel ja toimuvad mõnes, üldiselt, juhuslik ajapunktid. Kui sündmus seisneb nõuete esitamises, siis meil on rakenduste voog. Rakenduste voo kirjeldamiseks üldine juhtum on vaja määrata ajaintervallid t = t k - t k-1 külgnevate hetkede vahel t k _ k Ja t k seerianumbritega avalduste vastuvõtmine Kellele - 1 ja To vastavalt (Saada- 1, 2, ...; t 0 - 0 – esialgne ajahetk).

Rakendusvoo peamine omadus on selle X intensiivsus- QS-i sisendisse saabunud rakenduste keskmine arv ajaühikus. Väärtus t = 1/X määratleb keskmine ajavahemik kahe järjestikuse tellimuse vahel.

Voolu nimetatakse deterministlik kui ajaintervallid t kuni külgnevate rakenduste vahel aktsepteerida ettemääratud teadaolevad väärtused. Kui intervallid on samad (x kuni= t kõigi jaoks k = 1, 2, ...), siis kutsutakse voogu regulaarne. Sest täielik kirjeldus regulaarse rakenduste voo jaoks piisab voolu intensiivsuse määramisest X või intervalli t = väärtus 1/X.

Voog, milles ajavahemikud x k külgnevate rakenduste vahel on juhuslikud muutujad, nn juhuslik.Üldjuhul juhusliku rakenduste voo täielikuks kirjeldamiseks on vaja iga ajaintervalli jaoks määrata jaotusseadused F fc (x fc) x k, k = 1,2,...

Juhuslik voog, milles kõik ajavahemikud x b x 2,... külgnevate järjestikuste klientide vahel on sõltumatud juhuslikud muutujad, mida kirjeldavad jaotusfunktsioonid FjCij), F 2 (x 2), ... nimetatakse vastavalt vooluks koos piiratud järelmõju.

Juhuslikku voogu nimetatakse korduv, kui kõik ajaintervallid xb t 2 , ... rakenduste vahel jaotatud sama seaduse alusel F(t). Korduvaid vooge on palju. Iga jaotusseadus loob oma korduva voo. Korduvaid vooge nimetatakse ka Palmi voogudeks.

Kui intensiivsus X ja järjestikuste päringute vaheliste intervallide jaotusseadus F(t) ajas ei muutu, siis päringute voogu nimetatakse paigal Vastasel juhul on rakenduste voog mittestatsionaarne.

Kui igal ajahetkel t k QS-i sisendisse saab ilmuda ainult üks klient, siis kutsutakse klientide voogu tavaline. Kui korraga võib ilmuda rohkem kui üks rakendus, siis rakenduste voog on selline erakordne, või Grupp.

Päringute voogu nimetatakse vooks ei mingit järelmõju, kui avaldusi laekub sõltumataüksteisest, st. järgmise avalduse laekumise hetk ei sõltu sellest, millal ja kui palju avaldusi on enne seda hetke laekunud.

Statsionaarset tavalist voolu ilma järelmõjuta nimetatakse kõige lihtsam.

Ajavahemikud t päringute vahel kõige lihtsamas voos jaotatakse vastavalt eksponentsiaalne (eeskujulik) seadus: jaotusfunktsiooniga F(t) = 1 - e~ m; jaotustihedus/(f) = Heh~"l, Kus X > 0 - jaotusparameeter - rakenduste voo intensiivsus.

Sageli nimetatakse lihtsaimaks vooluks Poisson. Nimetus tuleneb sellest, et selle voo puhul on täpselt esinemise tõenäosus P fc (At). To taotlusi teatud ajaintervall At määratakse Poissoni seadus:

Tuleb märkida, et erinevalt kõige lihtsamast võib Poissoni vool olla:

• statsionaarne, kui intensiivsus X ei muutu aja jooksul;
• mittestatsionaarne, kui voolukiirus sõltub ajast: X= >.(t).

Samal ajal on kõige lihtsam vool definitsiooni järgi alati paigal.

Järjekorramudelite analüütilisi uuringuid tehakse sageli kõige lihtsama päringute voo eeldusel, mis on tingitud mitmetest sellele omasetest märkimisväärsetest omadustest.

1. Voogude summeerimine (ühendamine). Lihtsaim voog QS-teoorias sarnaneb tõenäosusteooria normaaljaotuse seadusega: üleminek voolu piirile, mis on suvaliste omadustega voogude summa koos terminite arvu lõpmatu suurenemise ja nende intensiivsuse vähenemisega lihtsaima vooluni.

Summa N sõltumatud statsionaarsed tavalised voolud intensiivsusega x x x 2 ,..., X N moodustab intensiivsusega kõige lihtsama voolu

X=Y,^i eeldusel, et lisatud voogudes on rohkem või

vähem võrdselt väike mõju koguvoolule. Praktikas on koguvool kõige lihtsama lähedal N > 5. Niisiis sõltumatute lihtsaimate voolude summeerimisel on koguvool kõige lihtsam mis tahes väärtuse eest N.

• 2. Voolu tõenäosuslik haruldus. tõenäosuslik(Aga mittedeterministlik) haruldus lihtsaim vool rakendused, milles mis tahes rakendus juhuslikult teatud tõenäosusega R on voolust välja jäetud, sõltumata sellest, kas teised rakendused on välja jäetud või mitte, viib moodustumiseni lihtsaim vool intensiivsusega X* = pX, Kus X- esialgse voo intensiivsus. Välistatud rakenduste voog intensiivsusega X** = (1 - p)X- Sama algloom voolu.
• 3. Tõhusus. Kui teenindavad kanalid (seadmed) on mõeldud kõige lihtsama intensiivsusega päringute voo jaoks x, siis tagatakse ka teist tüüpi voogude teenindamine (sama intensiivsusega) mitte vähem tõhusalt.
• 4. Lihtsus. Lihtsaima rakenduste voo eeldus võimaldab paljudel matemaatilistel mudelitel saada selgel kujul QS-indikaatorite sõltuvust parameetritest. Suurim arv analüütilised tulemused saadi rakenduste lihtsaima voo jaoks.

Lihtsamatest erinevate rakenduste voogudega mudelite analüüs muudab tavaliselt matemaatilised arvutused keeruliseks ega võimalda alati selget analüütilist lahendust saada. "Kõige lihtsam" voog sai oma nime just selle funktsiooni tõttu.

Rakendustel võivad teenuse käivitamiseks olla erinevad õigused. Sel juhul öeldakse, et rakendused on heterogeenne. Mõnede rakenduste voogude eelised teiste ees on teenuse alguses seatud prioriteetide alusel.

Sisendvoo oluline omadus on variatsioonikoefitsient

kus t int - intervalli pikkuse matemaatiline ootus; O- keskmine standardhälve intervalli pikkus x int (juhuslik muutuja) .

Lihtsaima voolu (a = -, m = -) jaoks on meil v = 1. Enamiku jaoks

tegelikud voolud 0

Teeninduskanalid (seadmed). Kanali peamine omadus on teenuse kestus.

Teenuse kestus- rakenduse poolt seadmes veedetud aeg - üldiselt on väärtus juhuslik. QS-i ebaühtlase koormuse korral võivad erinevate klasside päringute teenindusajad jaotusseaduste või ainult keskmiste väärtuste järgi erineda. Sel juhul eeldatakse tavaliselt, et iga klassi päringute teenindusajad on sõltumatud.

Sageli eeldavad praktikud, et teenindustaotluste kestus on jagatud eksponentsiaalne seadus mis lihtsustab oluliselt analüütilisi arvutusi. See on tingitud asjaolust, et ajavahemike eksponentsiaalse jaotusega süsteemides toimuvad protsessid on Markov protsessid:

kus c - teenuse intensiivsus, siin p = _--; t 0 bsl - matemaatika-

tic ooteaeg teenusele.

Lisaks eksponentsiaalsele jaotusele on Erlangi /c-jaotused, hüpereksponentjaotused, kolmnurkjaotused ja mõned teised. See ei tohiks meid segadusse ajada, kuna on näidatud, et QS efektiivsuskriteeriumide väärtus sõltub teenindusaja jaotuse seaduse vormist vähe.

QS-i uurimisel jääb tähelepanuta teenuse olemus, teenuse kvaliteet.

Kanalid võivad olla täiesti usaldusväärne need. ära ebaõnnestu. Pigem saab seda uuringus aktsepteerida. Kanalitel võib olla ülim usaldusväärsus. Sel juhul on QS-mudel palju keerulisem.

QS tõhusus ei sõltu ainult sisendvoogude ja teeninduskanalite parameetritest, vaid ka järjestusest, milles sissetulevaid päringuid teenindatakse, s.t. kuidas hallata rakenduste voogu, kui need sisenevad süsteemi ja saadetakse hooldusesse.

Rakenduste voo haldamise viisid määravad distsipliinid:

• puhverdamine;
• teenus.

Puhverdus- ja hooldusdistsipliinid saab klassifitseerida järgmiste kriteeriumide alusel:

• prioriteetide olemasolu erinevate klasside rakenduste vahel;
• meetod rakenduste järjekorrast välja tõrjumiseks (puhverdusvaldkondade jaoks) ja teenusepäringute määramiseks (teenusedistsipliinide jaoks);
• teenusepäringute eelostmise või valimise reegel;
• võime prioriteete muuta.

Puhverdistsipliinide (järjekorra) klassifitseerimise variant vastavalt loetletud tunnustele on näidatud joonisel fig. 2.2.

Sõltuvalt sellest, kättesaadavus või prioriteetide puudumine erinevate klasside rakenduste vahel võib kõik puhverdusvaldkonnad jagada kahte rühma: mitteprioriteetsed ja prioriteetsed.

Kõrval meetod rakenduste mälust välja tõrjumiseks eristada saab järgmisi puhverdusvaldkondade klasse:

• taotlusi välja tõrjumata - süsteemi sisenenud ja draivi täielikult täidetud päringud lähevad kaotsi;
• selle klassi rakenduse nihkega, s.o. samasse klassi kui laekunud taotlus;
• rakenduse nihutamisega madalaima prioriteediga klassist;
• rakenduse väljatõrjumisega madala prioriteediga klasside rühmast.

Riis. 2.2.

Puhverdistsipliinid võivad kasutada järgmist reeglid päringute akumulaatorist väljasaatmiseks:

• juhuslik nihkumine;
• viimase järjekorra välistamine, s.o. sisenes süsteemi hiljem kui kõik;
• "pika" tellimuse väljatõrjumine, st. asub akumulaatoris kauem kui kõik varem laekunud taotlused.

Joonisel fig. 2.3 näitab rakenduste teenindamise distsipliinide klassifikatsiooni samade tunnuste järgi nagu puhverdamise erialadel.

Mõnikord peetakse mudelite mälumahtu piiramatuks, kuigi reaalses süsteemis on see piiratud. Selline eeldus on õigustatud, kui reaalses süsteemis tellimuse kaotamise tõenäosus salvestusmahu ülevoolu tõttu on väiksem kui 10_3. Sellisel juhul ei mõjuta distsipliin taotluste täitmist praktiliselt.

Sõltuvalt sellest, kättesaadavus või prioriteetide puudumine erinevate klasside päringute vahel võib kõik teenindusvaldkonnad ja ka puhverdusvaldkonnad jagada kahte rühma: mitteprioriteetsed ja prioriteetsed.

Kõrval kuidas teeninduspileteid määratakse Teenindusvaldkonnad võib jagada erialadeks:

• ühe režiimiga;
• rühmarežiim;
• kombineeritud režiim.

Riis. 2.3.

Teenindusvaldkondades ühe režiimiga teenindus iga kord määratud ainult üks päring, mille järjekorrad skannitakse pärast eelmise päringu teenindamise lõppu.

Teenindusvaldkondades rühmarežiim teenindus iga kord päringute rühm on määratudüks järjekord, mille jaoks järjekordi kontrollitakse alles pärast seda, kui kõik eelnevalt määratud rühma päringud on teenindatud. Äsja määratud piletite grupp võib sisaldada kõiki antud järjekorra pileteid. Määratud rühmataotlused järjestikku järjekorrast valitud ja neid teenindab seade, misjärel määratakse teenuseks vastavalt määratud teenindusdistsipliinile teise järjekorra järgmine rakenduste rühm.

Kombineeritud režiim- ühe- ja rühmarežiimide kombinatsioon, kui osa päringujärjekordadest töödeldakse üksikrežiimis ja teist osa rühmarežiimis.

Teenusedistsipliinid võivad kasutada järgmisi teenusepäringu valikureegleid.

Mitteprioriteetne(rakendustel pole varaseid teenuseõigusi – ressursihõive):

• teenus, kes ees, see mees FIFO (esimene sisse - kõigepealt välja, esimene sisse - esimene välja)
• vastupidine teenus- rakendus valitakse režiimis olevast järjekorrast LIFO (viimane sisse - esimene välja, viimane sisse, esimene välja)
• juhuslik teenus- rakendus valitakse režiimis olevast järjekorrast RAND (juhuslik- juhuslikult);
• tsükliline teenus- rakendused valitakse draivide tsüklilise küsitluse käigus järjestuses 1, 2, H KOOS H- draivide arv), mille järel korratakse määratud järjestust;

Prioriteet(rakendustel on varajase teenuse privileegid – ressursside hõivamine):

• Koos suhtelised prioriteedid- kui päringu jooksva teenindamise käigus satuvad süsteemi kõrgema prioriteediga päringud, siis jooksva päringu teenindamine ka ilma prioriteedita ei katke ning saabunud päringud saadetakse järjekorda; suhtelised prioriteedid mängivad rolli ainult rakenduse praeguse teenuse lõpus, kui järjekorrast valitakse uus teenusepäring.
• Koos absoluutsed prioriteedid- kõrge prioriteediga päringu saamisel katkestatakse madala prioriteediga päringu teenindamine ja saabunud päring saadetakse teenindamiseks; katkestatud rakenduse saab järjekorda tagasi saata või süsteemist eemaldada; kui taotlus tagastatakse järjekorda, saab selle edasist teenust teostada katkenud kohast või uuesti;
• co segased prioriteedid- ranged piirangud ooteajale üksikute rakenduste teenindamise järjekorras nõuavad neile absoluutsete prioriteetide määramist; selle tulemusena võib madala prioriteediga taotluste ooteaeg osutuda lubamatult suureks, kuigi üksikutel taotlustel on ooteaja varu; igat tüüpi päringute piirangute täitmiseks koos absoluutsete prioriteetidega saab mõnele päringule määrata suhtelised prioriteedid ja ülejäänud saab teenindada mitteprioriteetses režiimis;
• Koos vahelduvad prioriteedid- suhteliste prioriteetide analoog, prioriteeti võetakse arvesse ainult ühe järjekorra taotluste rühma jooksva teenindamise lõpetamise ja uue grupi teenindamiseks määramise hetkedel;
• plaaniline teenus- erinevate klasside pretensioonid (asuvad erinevates hoidlates) valitakse teenindamiseks kindla ajakava järgi, mis määrab rakenduste järjekordade pollimise järjestuse, näiteks kolme klassi rakenduste (poodide) korral saab ajakava vaadata nagu (2, 1, 3, 3, 1, 2) või (1, 2, 3, 3, 2, 1).

Arvuti IM-süsteemides rakendatakse distsipliin reeglina vaikimisi FIFO. Küll aga on neil olemas tööriistad, mis annavad kasutajale võimaluse korraldada talle vajalikke teenindusdistsipliini, sh ajakava järgi.

CMO-le laekunud taotlused on jagatud klassidesse. QS-is, mis on abstraktne matemaatiline mudel, rakendused kuuluvad erinevatesse klassidesse juhul, kui need erinevad simuleeritud reaalsüsteemis vähemalt ühe järgmise tunnuse poolest:

• teenistuse kestus;
• prioriteedid.

Kui rakendused ei erine teenuse kestuse ja prioriteetide poolest, saab neid esindada sama klassi rakendustega, sealhulgas siis, kui need pärinevad erinevatest allikatest.

Segatud prioriteetidega teenindusdistsipliinide matemaatiliseks kirjeldamiseks kasutame prioriteetmaatriks, esindavad ruutmaatriks Q = (q, ;), mina, j - 1,..., I, I - süsteemi sisenevate rakenduste klasside arv.

Element q(j maatriks määrab klassipäringute prioriteedi i seoses klassi taotlustega; ja võib võtta järgmisi väärtusi:

• 0 - prioriteet puudub;
• 1 - suhteline prioriteet;
• 2 - absoluutne prioriteet.

Prioriteetmaatriksi elemendid peavad vastama järgmisele nõuded:

• q n= 0, kuna sama klassi päringute vahel ei saa prioriteete seada;
• Kui q (j = 1 või 2 siis q^ = 0, kuna kui klassirakendused i klassi taotluste suhtes ülimuslikud j, siis ei saa viimased olla klassinõuete suhtes ülimuslikud i (i,j = 1, ..., I).

Sõltuvalt sellest, võimalusi prioriteete muuta Süsteemi töötamise ajal on puhverdamise ja teenindamise prioriteetsed distsipliinid jagatud kahte klassi:

• 1) koos staatilised prioriteedid, mis aja jooksul ei muutu;
• 2) koos dünaamilised prioriteedid, mis võivad süsteemi töö käigus muutuda sõltuvalt erinevatest teguritest, näiteks kui teatud kriitiline mis tahes prioriteedita või madala prioriteediga klassi päringute järjekorra pikkus, võib sellele anda kõrgema prioriteedi.

IM-i arvutisüsteemides on tingimata üks element (objekt), mille kaudu ja ainult selle kaudu päringuid mudelisse sisestatakse. Vaikimisi on kõik sisestatud rakendused mitteprioriteetsed. Kuid on olemas võimalused prioriteetide määramiseks järjestuses 1, 2, ..., sh mudeli täitmise ajal, s.t. dünaamikas.

Väljuv voog on QS-ist lahkuvate teenindatud päringute voog. Reaalsetes süsteemides läbivad rakendused mitu QS-i: transiitside, tootmistoru jne. Sel juhul on väljaminev voog järgmise QS-i sissetulev voog.

Esimese QS-i sissetulev voog, mis on läbinud järgmised QS-id, on moonutatud ja see raskendab analüütilist modelleerimist. Siiski tuleb meeles pidada, et lihtsaima sisendvoo ja eksponentsiaalse teenusega(need. Markovi süsteemides) on ka väljundvoog kõige lihtsam. Kui teenindusajal on mitteeksponentsiaalne jaotus, pole väljaminev voog mitte ainult lihtne, vaid ka mitte korduv.

Pange tähele, et väljaminevate päringute vahelised intervallid ei ole samad, mis hooldusintervallid. Lõppude lõpuks võib selguda, et pärast järgmise hoolduse lõppu on QS rakenduste puudumise tõttu mõnda aega jõude. Sel juhul koosneb väljamineva voo intervall QS-i tühikäiguajast ja pärast seisakuaega saabunud esimese päringu teenindusintervallist.

QS-is võib lisaks teenindatavate päringute väljaminevatele voogudele olla esitamata taotluste voog. Kui selline QS saab korduva voo ja teenus on eksponentsiaalne, siis on ka teenindamata klientide voog korduv.

Tasuta kanalite järjekorrad. Mitme kanaliga QS-is saab moodustada vabade kanalite järjekordi. Tasuta kanalite arv on juhuslik väärtus. Teadlasi võivad huvitada selle juhusliku suuruse erinevad omadused. Tavaliselt on see teenuse poolt hõivatud kanalite keskmine arv uuringuintervalli kohta ja nende koormustegurid.

Nagu me varem märkisime, teenindatakse reaalsetes objektides päringuid mitmes QS-is järjestikku.

Nimetatakse lõplik kogum järjestikku ühendatud QS-e, mis töötlevad neis ringlevaid rakendusi järjekorravõrk (Semo) (joonis 2.4, A).

Riis. 2.4.

SEMO-ks nimetatakse ka mitmefaasiline QS.

Vaatleme QEMO IM konstrueerimise näidet hiljem.

QS-i põhielemendid on sõlmed (U) ja päringute allikad (generaatorid) (G).

Sõlm võrgud on järjekorrasüsteem.

Allikas- võrku sisenevate rakenduste generaator, mis nõuavad võrgusõlmedes teatud teenindusetappe.

QEMO lihtsustatud kujutise jaoks kasutatakse graafikut.

Krahv Semo- suunatud graafik (digraaf), mille tipud vastavad QEM-sõlmedele ja kaared kujutavad rakenduste üleminekuid sõlmede vahel (joon. 2.4, b).

Niisiis, oleme kaalunud QS-i põhikontseptsioone. Kuid IM-i arvutisüsteemide väljatöötamisel ja nende täiustamisel kasutatakse tingimata ära ka praegu QS-i analüütilises modelleerimises sisalduvat tohutut loomingulist potentsiaali.

Selle loomingulise potentsiaali paremaks tajumiseks peatume esmalt QS-mudelite klassifikatsioonil.

See on vajalik ülesannete 1-3 lahendamiseks. Algandmed on toodud tabelis. 2-4.

Mõned järjekorrateoorias valemite jaoks kasutatud tähistused:

n on QS kanalite arv;

λ - sissetuleva rakenduste voo intensiivsus P in;

v - väljamineva rakenduste voo intensiivsus P out;

μ - teenuse voo intensiivsus P umbes;

ρ - süsteemi koormuse indikaator (liiklus);

m - maksimaalne kohtade arv järjekorras, piirates taotluste järjekorra pikkust;

i - rakendusallikate arv;

p kuni - süsteemi k-nda oleku tõenäosus;

p umbes - kogu süsteemi jõudeaja tõenäosus, st tõenäosus, et kõik kanalid on vabad;

p syst - rakenduse aktsepteerimise tõenäosus süsteemis;

p otk - taotluse tagasilükkamise tõenäosus selle süsteemi vastuvõtmisel;

p about – tõenäosus, et taotlus kätte toimetatakse;

A on süsteemi absoluutne läbilaskevõime;

Q on süsteemi suhteline läbilaskevõime;

och - keskmine taotluste arv järjekorras;

o - teenindatavate taotluste keskmine arv;

syst - keskmine rakenduste arv süsteemis;

pt - keskmine taotluse ooteaeg järjekorras;

o - rakenduse keskmine kättetoimetamise aeg, mis puudutab ainult teenindatavaid rakendusi;

sys - rakenduse keskmine süsteemis viibimise aeg;

exp - keskmine aeg, mis piirab taotluse ootamist järjekorras;

Keskmine hõivatud kanalite arv.

QS A absoluutne läbilaskevõime on keskmine rakenduste arv, mida süsteem saab ajaühikus teenindada.

QS suhteline läbilaskevõime Q on süsteemi poolt ajaühikus teenindatavate rakenduste keskmise arvu ja selle aja jooksul vastuvõetud rakenduste keskmise arvu suhe.

Järjekorraprobleemide lahendamisel tuleb järgida järgmist järjestust:

1) QS tüübi määramine vastavalt tabelile. 4,1;

2) valemite valik vastavalt QS tüübile;

3) probleemide lahendamine;

4) probleemi kohta järelduste sõnastamine.

1. Surma ja paljunemise skeem.

Teame, et kui meie käsutuses on märgistatud olekugraafik, saame hõlpsasti kirjutada Kolmogorovi võrrandeid olekutõenäosuste jaoks, samuti kirjutada ja lahendada algebralised võrrandid lõplike tõenäosuste jaoks. Mõnel juhul on võimalik lahendada viimased võrrandid ette, sõnasõnalises vormis. Eelkõige saab seda teha siis, kui süsteemi olekugraafik on nn "surma ja taastootmise skeem".

Surma ja paljunemise skeemi olekugraafik on joonisel fig. 19.1. Selle graafiku eripära on see, et süsteemi kõik olekud saab tõmmata ühte ahelasse, milles iga keskmine olek ( S 1 , S 2 , …, S n-1) on ühendatud edasi- ja tagasinoolega iga naaberolekuga - parem ja vasak ning äärmuslikud olekud (S 0 , S n) — ainult ühe naaberriigiga. Mõiste "surma ja paljunemise skeem" pärineb bioloogilistest probleemidest, kus populatsiooni suuruse muutust kirjeldatakse sellise skeemiga.

Surma ja paljunemise skeemi kohtab väga sageli erinevates praktikaprobleemides, eriti järjekorra teoorias, seetõttu on kasulik üks kord ja igaveseks leida selle jaoks olekute lõplikud tõenäosused.

Oletame, et kõik sündmuste vood, mis edastavad süsteemi piki graafiku nooli, on kõige lihtsamad (lühiduse huvides nimetame süsteemiks ka S ja selles toimuv protsess on kõige lihtsamad).

Kasutades joonisel fig. 19.1, koostame ja lahendame oleku lõpptõenäosuste algebralised võrrandid), olemasolu tuleneb sellest, et igast olekust saab minna igasse teise, olekute arv on lõplik).

Esimese osariigi jaoks S 0 meil on:

(19.1)

Teise oleku jaoks S1:

(19.1) tõttu taandatakse viimane võrdsus vormile

Kus k võtab kõik väärtused 0 kuni P. Nii et lõplikud tõenäosused p0, p1,..., p n rahuldavad võrrandid

(19.2)

lisaks peame arvestama normaliseerimise tingimusega

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

Lahendame selle võrrandisüsteemi. Esimesest võrrandist (19.2) väljendame lk 1 läbi R 0 :

lk 1 = lk 0. (19.4)

Teisest, võttes arvesse (19.4), saame:

(19.5)

alates kolmandast, võttes arvesse (19,5),

(19.6)

ja üldiselt mis tahes k(alates 1 kuni n):

(19.7)

Pöörame tähelepanu valemile (19.7). Lugeja on kõigi vasakult paremale suunduvate noolte intensiivsuste korrutis (algusest kuni antud olek S k) ja nimetaja on kõigi paremalt vasakule suunduvate noolte intensiivsuste korrutis (algusest kuni Sk).

Seega kõik olekutõenäosused R 0 , lk 1 , ..., р n väljendatud ühe neist ( R 0). Asendame need avaldised normaliseerimistingimusega (19.3). Saame sulgudes R 0:

siit saame väljendi jaoks R 0 :

(tõstsime sulgu astmeni -1, et mitte kirjutada kahekorruselisi murde). Kõik muud tõenäosused on väljendatud R 0 (vt valemeid (19.4)-(19.7)). Pange tähele, et koefitsiendid R 0 on igaühes neist midagi muud kui järjestikused liikmed valemis (19.8) ühiku järel. Niisiis, arvutades R 0 , oleme kõik need koefitsiendid juba leidnud.

Saadud valemid on väga kasulikud järjekorrateooria lihtsamate ülesannete lahendamisel.

2. Väike valem.

Nüüd tuletame ühe olulise valemi, mis on seotud (piirava, statsionaarse režiimi jaoks) rakenduste keskmise arvuga L syst, mis asub järjekorrasüsteemis (st teenindatakse või seisab järjekorras) ja rakenduse keskmine viibimisaeg süsteemis W süsteem

Vaatleme mis tahes QS-i (ühe kanaliga, mitme kanaliga, markovi, mitte-Markovi, piiramatu või piiratud järjekorraga) ja kahte sellega seotud sündmuste voogu: QS-i saabuvate klientide voogu ja teenusest lahkuvate klientide voogu. QS. Kui süsteemis on kehtestatud piirav statsionaarne režiim, siis QS-i saabuvate rakenduste keskmine arv ajaühikus võrdub sealt väljuvate rakenduste keskmise arvuga: mõlema voo intensiivsus λ on sama.

Tähistage: X(t) — taotluste arv, mis saabusid ühisele turukorraldusele enne hetke t. Y(t) — ühisturust lahkunud taotluste arv

hetkeni t. Mõlemad funktsioonid on juhuslikud ja muutuvad järsult (suurenevad ühe võrra) päringu saabumise hetkel (X(t)) ja taotluste lahkumised (Y(t)). Funktsioonide tüüp X(t) ja Y(t) näidatud joonisel fig. 19,2; mõlemad read on astmelised, ülemine on X(t), madalam - Y(t). Ilmselgelt igaks hetkeks t nende erinevus Z(t)= X(t) - Y(t) pole midagi muud kui rakenduste arv QS-is. Kui read X(t) Ja Y(t) liita, süsteemis pole päringuid.

Mõelge väga pikale ajavahemikule T(mõtteliselt jätkates graafikut palju kaugemale joonisest) ja arvutage selle jaoks välja keskmine rakenduste arv QS-is. See on võrdne funktsiooni integraaliga Z(t) sellel intervallil jagatud intervalli pikkusega T:

L süsteem = . (19.9) o

Kuid see integraal pole midagi muud kui joonisel fig. 19.2. Vaatame seda joonist hästi. Joonis koosneb ristkülikutest, millest igaühe kõrgus on võrdne ühega ja alus on võrdne viibimisajaga vastava järjekorra süsteemis (esimene, teine ​​jne). Märgime need ajad ära t1, t2,... Tõsi, intervalli lõpus T mõned ristkülikud sisenevad varjutatud joonisele mitte täielikult, vaid osaliselt, kuid piisavalt suurena T need pisiasjad ei loe.

(19.10)

kus summa kehtib kõigi selle aja jooksul laekunud taotluste kohta T.

Eraldame parem- ja vasak pool(.19.10) intervalli pikkuse järgi T. Saame, võttes arvesse (19.9),

L süsteem = . (19.11)

Jaga ja korruta parem pool(19.11) intensiivsusele X:

L süsteem = .

Aga suurusjärk Tλ ei ole midagi muud kui selle aja jooksul laekunud taotluste keskmine arv ^ T. Kui jagame kõigi aegade summa t i keskmise taotluste arvu kohta, siis saame rakenduse keskmise süsteemis viibimise aja W süsteem Niisiis,

L süsteem = λ W süsteem ,

W süsteem = . (19.12)

See on Little'i suurepärane valem: mis tahes QS-i jaoks, mis tahes rakenduste voo olemuse jaoks, mis tahes teenindusaja jaotuse jaoks, mis tahes teenindusdistsipliini jaoks päringu keskmine viibimisaeg süsteemis võrdub keskmise päringute arvuga süsteemis, mis on jagatud päringu voo intensiivsusega.

Täpselt samamoodi tuletatakse Little'i teine ​​valem, mis seostab rakenduse keskmist järjekorras veedetud aega ^ Oeh ja keskmine taotluste arv järjekorras L oh:

W oh = . (19.13)

Väljundi jaoks piisab joonise fig. alumise rea asemel. 19.2 võta funktsioon U(t)- hetkeni jäänud taotluste arv t mitte süsteemist, vaid järjekorrast (kui süsteemi sisenenud rakendus ei satu järjekorda, vaid läheb kohe teenindusse, saame siiski arvestada, et ta satub järjekorda, kuid jääb sinna nulli) .

Little'i valemid (19.12) ja (19.13) mängivad järjekorrateoorias olulist rolli. Kahjuks on enamikus olemasolevates juhendites need valemid (tõestatud üldine vaade suhteliselt hiljuti) ei anta 1).

Lihtsamad järjekorrasüsteemid ja nende omadused

Selles jaotises käsitleme mõningaid lihtsamaid QS-e ja tuletame nende omaduste (jõudlusnäitajate) avaldisi. Samas demonstreerime elementaarsele, “markovilikule” järjekorrateooriale iseloomulikke põhilisi metodoloogilisi võtteid.

Me ei uuri QS-proovide arvu, mille jaoks karakteristikute lõplikud avaldised tuletatakse; see raamat ei ole järjekorrateooria juhend (spetsiaalsed juhendid täidavad seda rolli palju paremini). Meie eesmärk on tutvustada lugejale mõningaid "nippe", et hõlbustada järjekorrateooria läbimist, mis paljudes saadaolevates (isegi populaarseks pidavates) raamatutes võib tunduda ulmelise näitekoguna.

Kõiki sündmuste vooge, mis edastavad QS-i olekust olekusse, käsitleme selles jaotises kõige lihtsamat (ilma seda iga kord eraldi sätestamata). Nende hulgas on nn teenusevoog. See tähendab päringute voogu, mida teenindab üks pidevalt hõivatud kanal. Selles voos on sündmuste vaheline intervall, nagu ikka kõige lihtsamas voos, eksponentsiaalse jaotusega (paljudes juhendites on hoopis kirjas: "teenindusaeg on eksponentsiaalne", me ise kasutame seda terminit edaspidi).

Populaarses raamatus on toodud Little'i valemi tuletis ülaltooduga võrreldes mõnevõrra erinevalt. Üldiselt on selle raamatuga tutvumine (“Teine vestlus”) kasulik esmaseks tutvumiseks järjekorra teooriaga.

Selles jaotises peetakse teenindusaja eksponentsiaalset jaotust iseenesestmõistetavaks, nagu alati "lihtsaima" süsteemi puhul.

Vaadeldava QS-i efektiivsuskarakteristikuid tutvustame ettekande käigus.

1. P- kanal QS tõrgetega(Erlangi probleem). Siin käsitleme järjekorra teooria üht ajaliselt esimesi "klassikalisi" probleeme; see probleem tekkis telefoniside praktilistest vajadustest ja selle lahendas meie sajandi alguses Taani matemaatik Erlant. Ülesanne on püstitatud järgmiselt: on P kanalid (sideliinid), mis võtavad vastu rakenduste voogu intensiivsusega λ. Teenindusvoo intensiivsus on μ (keskmise teenindusaja pöördväärtus t umbes).

Leidke QS-i olekute lõplikud tõenäosused ja selle efektiivsuse omadused:

^ A - absoluutne läbilaskevõime, st ajaühikus teenindatud rakenduste keskmine arv;

K- suhteline läbilaskevõime, st süsteemi poolt teenindatavate sissetulevate päringute keskmine osakaal;

^ R otk- ebaõnnestumise tõenäosus, st asjaolu, et rakendus jätab QS-i teenindamata;

k - keskmine hõivatud kanalite arv.

Lahendus. Süsteemi olekud ^S(QS) nummerdatakse vastavalt taotluste arvule süsteemis (antud juhul langeb see kokku hõivatud kanalite arvuga):

S 0 —ühises turukorralduses ei ole taotlusi,

S 1 — QS-is on üks päring (üks kanal on hõivatud, ülejäänud on vabad),

Sk — SMO-s on k rakendused ( k kanalid on hõivatud, ülejäänud on tasuta),

S n — SMO-s on P rakendused (kõik n kanalid on hõivatud).

QS oleku graafik vastab sigimisel suremise skeemile (joonis 20.1). Märgistame selle graafiku – märkige sündmuste voogude intensiivsus noolte lähedale. Alates S 0 tolli S1 süsteemi edastab päringute voog intensiivsusega λ (niipea kui päring saabub, hüppab süsteem S0 V S1). Sama päringute voog kannab süsteemi mis tahes vasakpoolsest olekust üle parempoolsesse naaberolekusse (vt ülemisi nooli joonisel 20.1).

Paneme alumiste noolte intensiivsuse alla. Süsteem olgu seisukorras ^S 1 (üks kanal töötab). See toodab μ teenust ajaühiku kohta. Panime noole juurde S 1 →S 0 intensiivsus μ. Kujutage nüüd ette, et süsteem on olekus S2(töötavad kaks kanalit). Et ta läheks S 1, on vajalik, et kas esimene või teine ​​kanal lõpetaks hoolduse; nende teenusevoogude koguintensiivsus on 2μ; pane see vastava noole juurde. Kolme kanali kogu teenusevoo intensiivsus on 3 μ, k kanalid - km. Panime need intensiivsused alla joonisel fig. 20.1.

Ja nüüd, teades kõiki intensiivsusi, kasutame surma ja paljunemise skeemis lõplike tõenäosuste jaoks valmis valemeid (19.7), (19.8).

Valemi (19.8) järgi saame:

Lagunemise terminid on koefitsiendid p 0 väljendites jaoks p1

Pange tähele, et valemid (20.1), (20.2) ei sisalda intensiivsusi λ ja μ eraldi, vaid ainult suhtena λ/μ. Tähistage

λ/μ = ρ (20,3)

Ja me nimetame p väärtust "rakenduste voo vähenenud intensiivsuseks". Selle tähendus on ühe päringu keskmise teenindusaja jooksul saabunud päringute keskmine arv. Seda tähistust kasutades kirjutame valemid (20.1), (20.2) ümber järgmisel kujul:

Lõpliku oleku tõenäosuste valemeid (20.4), (20.5) nimetatakse järjekorrateooria rajaja auks Erlangi valemiteks. Enamik teisi selle teooria valemeid (tänapäeval on neid rohkem kui seeni metsas) ei kanna erilisi nimetusi.

Seega leitakse lõplikud tõenäosused. Nende põhjal arvutame välja QS efektiivsuskarakteristikud. Kõigepealt leiame ^ R otk. - tõenäosus, et sissetulevast päringust keeldutakse (ei toimetata kätte). Selleks on vaja, et kõik P kanalid olid hõivatud, nii et

R otk = R n = . (20.6)

Siit leiame suhtelise läbilaskevõime – rakenduse kättetoimetamise tõenäosuse:

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

Saame absoluutse läbilaskevõime, korrutades päringuvoo intensiivsuse λ-ga K:

A = λQ = λ. (20.8)

Jääb vaid leida hõivatud kanalite keskmine arv k. Selle väärtuse võib leida "otse" kui diskreetse juhusliku suuruse matemaatilise ootuse võimalike väärtustega 0, 1, ..., P ja nende väärtuste tõenäosused p 0 p 1, ..., p n:

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

Asendades siin avaldised (20.5) jaoks R k , (k = 0, 1, ..., P) ja sooritades vastavad teisendused, saaksime lõpuks õige valemi k. Kuid me tuletame selle palju lihtsamalt (siin see on üks "väikestest nippidest"!) Tõepoolest, me teame absoluutset läbilaskevõimet A. See pole midagi muud kui süsteemi teenindatavate rakenduste voo intensiivsus. Iga hõivatud i .shal ajaühiku kohta teenindab keskmiselt |l päringut. Seega keskmine hõivatud kanalite arv on

k = A/μ, (20.9)

või antud (20.8),

k = (20.10)

Soovitame lugejal näidet ise välja töötada. Seal on kolme kanaliga sidejaam ( n= 3), rakenduste voo intensiivsus λ = 1,5 (rakendusi minutis); keskmine teenindusaeg taotluse kohta t v = 2 (min.), on kõik sündmuste vood (nagu kogu selles lõigus) kõige lihtsamad. Leidke QS-i lõppoleku tõenäosused ja jõudlusnäitajad: A, Q, P otk, k. Igaks juhuks vastused siin: lk 0 = 1/13, lk 1 = 3/13, lk 2 = 9/26, lk 3 = 9/26 ≈ 0,346,

A≈ 0,981, K ≈ 0,654, P avatud ≈ 0,346, k ≈ 1,96.

Vastustest on muide näha, et meie QS on suures osas ülekoormatud: kolmest kanalist on keskmiselt hõivatud umbes kaks ja umbes 35% sissetulevatest rakendustest jääb teenindamata. Kutsume lugejat, kui ta on uudishimulik ja mitte laisk, välja selgitama: mitu kanalit on vaja, et rahuldada vähemalt 80% sissetulevatest taotlustest? Ja kui suur osa kanalitest jääb samal ajal jõude?

Mingi vihje on juba olemas optimeerimine. Tegelikult maksab iga kanali sisu ajaühiku kohta teatud summa. Samas toob iga hooldatud rakendus omajagu tulu. Korrutades selle sissetuleku keskmise taotluste arvuga A, teenindatakse ajaühiku kohta, saame ühise turukorralduse keskmise tulu ajaühiku kohta. Kanalite arvu kasvuga see tulu loomulikult kasvab, kuid kasvavad ka kanalite ülalpidamisega seotud kulud.

Mis kaalub üles – tulude või kulude kasv? See sõltub operatsiooni tingimustest, "rakenduse teenuse tasust" ja kanali ülalpidamiskuludest. Neid väärtusi teades saate leida optimaalse kanalite arvu, mis on kõige kuluefektiivsem. Sellist probleemi me ei lahenda, jättes samale "mittelaisale ja uudishimulikule lugejale" näite välja mõtlema ja seda lahendama. Üldiselt arendab probleemide väljamõtlemine rohkem kui kellegi poolt juba püstitatud probleemide lahendamine.

Ühe kanaliga QS piiramatu järjekorraga.

Praktikas on üsna levinud ühekanaliline järjekorraga QS (patsiente teenindav arst; ühe kabiiniga taksotelefon; kasutaja tellimusi täitev arvuti). Järjekorrateoorias on erilisel kohal ka ühe kanaliga QS koos järjekorraga (selliste QS-i alla kuulub enamik seni mitte-Markovi süsteemide kohta saadud analüütilisi valemeid). Seetõttu pöörame erilist tähelepanu ühe kanaliga järjekorraga QS-idele.

Olgu siis ühe kanaliga QS järjekorraga, millele piiranguid ei sea (ei järjekorra pikkusele ega ooteajale). See QS võtab vastu päringute voo intensiivsusega λ ; teenusevoo intensiivsus μ on päringu keskmise teenindusaja pöördvõrdeline t umbes.

On vaja leida QS-i olekute lõplikud tõenäosused ja selle efektiivsuse omadused:

L süsteem — keskmine rakenduste arv süsteemis,

W süsteem on päringu keskmine süsteemis viibimise aeg,

^L jah- järjekorras olevate taotluste keskmine arv,

W och — keskmine aeg, mille rakendus järjekorras veedab,

P zan — tõenäosus, et kanal on hõivatud (kanali koormuse aste).

Mis puutub absoluutsesse ribalaius A ja suhteline K, siis pole vaja neid arvutada:

kuna järjekord on piiramatu, siis iga avaldus varem või hiljem kätte toimetatakse, seega A \u003d λ, samal põhjusel Q= 1.

Lahendus. Süsteemi olekud, nagu varemgi, nummerdatakse vastavalt QS-is olevate rakenduste arvule:

S 0 — kanal on tasuta

S 1 - kanal on hõivatud (teenidab päringut), järjekorda pole,

S 2 — kanal on hõivatud, üks päring on järjekorras,

S k - kanal on hõivatud, k - 1 taotlust on järjekorras,

Teoreetiliselt ei piira olekute arvu miski (lõpmatult). Olekugraafikul on joonisel fig. 20.2. See on surma ja paljunemise skeem, kuid lõpmatu arvu olekutega. Kõigis nooltes edastab taotluste voog intensiivsusega λ süsteemi vasakult paremale ja paremalt vasakule teenusevoo intensiivsusega μ.

Kõigepealt küsigem endalt, kas sel juhul on lõplikud tõenäosused? Lõppude lõpuks on süsteemi olekute arv lõpmatu ja põhimõtteliselt at t → ∞ järjekord võib kasvada lõputult! Jah, see on tõsi: sellise QS-i lõplikud tõenäosused ei eksisteeri alati, vaid ainult siis, kui süsteem pole ülekoormatud. Võib tõestada, et kui ρ on rangelt väiksem kui üks (ρ< 1), то финальные вероятности существуют, а при ρ ≥ 1 очередь при t→ ∞ kasvab lõputult.

See asjaolu tundub eriti "arusaamatu" ρ = 1 korral. Tundub, et süsteemile pole võimatuid nõudeid: ühe päringu teenindamise ajal saabub keskmiselt üks päring ja kõik peaks olema korras, kuid tegelikult on ei ole. Kui ρ = ​​1, saab QS päringute vooga hakkama ainult siis, kui see voog on regulaarne ja teenindusaeg pole samuti juhuslik, võrdne päringute vahelise intervalliga. Sellisel "ideaalsel" juhul ei teki QS-is üldse järjekorda, kanal on pidevalt hõivatud ja väljastab regulaarselt teenindatud päringuid.

Kuid niipea, kui päringute voog või teenusevoog muutub vähemalt veidi juhuslikuks, kasvab järjekord juba määramatult. Praktikas ei juhtu see ainult seetõttu, et "lõpmatu arv rakendusi järjekorras" on abstraktsioon. Siin on mõned vead, mis võivad viia asendamiseni juhuslikud muutujad nende matemaatilised ootused!

Kuid pöördume tagasi meie piiramatu järjekorraga ühe kanaliga QS-i juurde. Rangelt võttes tuletasime surma ja taastootmise skeemi lõpptõenäosuste valemid ainult lõpliku arvu olekute korral, kuid võtame vabadused - me kasutame neid lõpmatu arvu olekute jaoks. Arvutame olekute lõpptõenäosused valemite (19.8), (19.7) järgi. Meie puhul on valemis (19.8) olevate liikmete arv lõpmatu. Saame väljendi jaoks p 0:

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

Seeria valemis (20.11) on geomeetriline progressioon. Me teame seda ρ puhul< 1 ряд сходится — это бесконечно убывающая геометрическая прогрессия со знаменателем р. При р ≥ 1 ряд расходится (что является косвенным, хотя и не строгим доказательством того, что финальные вероятности состояний p 0 , p 1 , ..., p k , ... eksisteerivad ainult r jaoks<1).

Oletame nüüd, et see tingimus on täidetud ja ρ1 + ρ + ρ 2 + ... + ρ k + ... = ,

lk 0 = 1 - lk. (20.12)

Tõenäosused p 1 , p 2 , ..., p k ,... leiad valemitega:

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

Kust (20.12) arvesse võttes leiame lõpuks:

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

Nagu näete, tõenäosus p0, p1, ..., p k , ... moodustavad geomeetrilise progressiooni nimetajaga p. Kummalisel kombel suurim neist p 0 — tõenäosus, et kanal üldse tasuta saab. Olenemata sellest, kui koormatud süsteem järjekorraga on, kui see ainult rakenduste vooga üldse hakkama saab (ρ<1), самое вероятное число заявок в системе будет 0.

Leidke QS-is rakenduste keskmine arv ^L süsteem. . Siin tuleb natuke nokitseda. Juhuslik väärtus Z- taotluste arv süsteemis - on võimalikud väärtused 0, 1, 2, .... k,... tõenäosustega p0, p 1 , p 2 , ..., p k , ... Selle matemaatiline ootus on

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

(summat ei võeta 0-st ∞-ni, vaid 1-st ∞-ni, kuna nullliige on võrdne nulliga).

Asendame valemisse (20.14) avaldise p k (20.13):

L süsteem =

Nüüd võtame välja summa ρ (1-ρ) märgi:

L süsteem = ρ(1-ρ)

Siin rakendame taas "väikest trikki": kρ k-1 pole midagi muud kui avaldise ρ tuletis ρ suhtes k; Tähendab,

L süsteem = ρ(1-ρ)

Diferentseerimise ja liitmise tehteid vahetades saame:

L süsteem = ρ (1-ρ) (20,15)

Kuid summa valemis (20.15) pole midagi muud kui lõpmatult kahaneva geomeetrilise progressiooni summa esimese liikmega ρ ja nimetajaga ρ; see summa

on võrdne , ja selle tuletis on . Asendades selle avaldise (20.15), saame:

L syst = . (20.16)

Noh, nüüd rakendame Little'i valemit (19.12) ja leiame rakenduse keskmise viibimisaja süsteemis:

W syst = (20.17)

Leidke järjekorras olevate rakenduste keskmine arv L och. Me vaidleme järgmiselt: järjekorras olevate rakenduste arv võrdub süsteemis olevate rakenduste arvuga, millest on lahutatud teenuses olevate rakenduste arv. Seega (vastavalt matemaatiliste ootuste liitmise reeglile) keskmine taotluste arv järjekorras L pt võrdub süsteemis olevate rakenduste keskmise arvuga L syst miinus teenindatavate päringute keskmine arv.

Teenuse all olevate päringute arv võib olla kas null (kui kanal on vaba) või üks (kui see on kinni). Sellise juhusliku muutuja matemaatiline ootus on võrdne tõenäosusega, et kanal on hõivatud (me tähistasime seda R zan). Ilmselgelt R zan on võrdne ühega miinus tõenäosus p 0 et kanal on tasuta:

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

Seetõttu on teenindatavate päringute keskmine arv võrdne

^L umbes= ρ, (20,19)

L oh = L syst - ρ =

ja lõpuks

L pt = (20.20)

Little'i valemit (19.13) kasutades leiame keskmise aja, mille rakendus järjekorras veedab:

(20.21)

Seega on leitud kõik QS efektiivsuse omadused.

Teeme lugejale ettepaneku lahendada näide iseseisvalt: ühe kanaliga QS on raudtee sorteerimisjaam, mis võtab vastu kõige lihtsama rongide voolu intensiivsusega λ = 2 (ronge tunnis). Teenindus (laialiminek)

kompositsioon kestab juhusliku (demonstratiivse) aja keskmise väärtusega t umbes = 20(min.). Jaama saabumispargis on kaks rada, millel saabuvad rongid saavad teenust oodata; kui mõlemad rajad on hõivatud, on rongid sunnitud ootama välimistel rööbasteedel.

On vaja leida (jaama piirava, statsionaarse töörežiimi jaoks): keskmine, rongide arv l jaamaga seotud süsteem, keskmine aeg W rongipeatussüsteem jaamas (siseteedel, välisteedel ja hoolduses), keskmine arv L pts laialimineku järjekorras ootavaid ronge (pole vahet, millistel rööbastel), keskmine aeg W Pts jääb koosseis ootenimekirja. Püüdke leida ka välimistel rööbasteedel laiali saatmist ootavate rongide keskmine arv. L väline ja selle ootamise keskmine aeg W väline (kaks viimast suurust on seotud Little'i valemiga).

Lõpuks leidke päevane kogutrahv W, mille jaam peab tasuma rongide seisaku eest välistel rööbasteedel, kui jaam maksab trahvi a (rubla) ühe rongi ühetunnise seisaku eest. Igaks juhuks vastused siin: L süsteem = 2 (koostis), W süsteem = 1 (tund), L punktid = 4/3 (koosseis), W pt = 2/3 (tunnid), L väline = 16/27 (koostis), W väline = 8/27 ≈ 0,297 (tunnid). Keskmine päevatrahv W rongide välistel rööbasteedel ootamise eest saadakse, kui korrutatakse ööpäevas jaama saabuvate rongide keskmine arv, rongide keskmine ooteaeg välisteedel ja tunnitasu. A: W ≈ 14,2 A.

piiramatu järjekorraga QS-i uuesti kanaliseerimine.

Täiesti sarnane probleemiga 2, kuid veidi keerulisem, probleem n-channel QS piiramatu järjekorraga.

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

Surma ja paljunemise skeem on olemas, kuid lõpmatu arvu olekutega. Esitagem ilma tõestuseta lõplike tõenäosuste olemasolu loomulik tingimus: ρ/ n n ≥ 1, järjekord kasvab lõpmatuseni.

Oletame, et tingimus ρ/ n < 1 выполнено, и финальные вероятности существуют. Применяя все те же формулы (19.8), (19.7) для схемы гибели и размножения, найдем эти финальные вероятности. В выражении для p 0 seal on rida termineid, mis sisaldavad faktoriaale, millele lisandub lõpmatult kahaneva geomeetrilise progressiooni summa nimetajaga ρ/ n. Kokkuvõtteks leiame

(20.22)

Nüüd leiame QS-i efektiivsuse omadused. Nendest on kõige lihtsam leida keskmine hõivatud kanalite arv k= λ/μ, = ρ (see kehtib üldiselt iga piiramatu järjekorraga QS-i kohta). Leidke keskmine rakenduste arv süsteemis L süsteem ja keskmine rakenduste arv järjekorras L och. Neist teist on valemi järgi lihtsam arvutada

L oh =

vastavate teisenduste sooritamine vastavalt ülesande 2 näidisele

(koos seeriate eristamisega) saame:

L oh = (20.23)

Lisades sellele keskmine teenuses olevate rakenduste arv (see on ka keskmine hõivatud kanalite arv) k =ρ, saame:

L syst = L och + ρ. (20.24)

Avaldiste jagamine L och ja L syst on λ , Little'i valemit kasutades saame rakenduse keskmise viibimisaja järjekorras ja süsteemis:

(20.25)

Nüüd lahendame huvitava näite. Kahe aknaga raudteepiletikassa on kahe kanaliga piiramatu järjekorraga QS, mis moodustatakse kohe kahele aknale (kui üks aken on vaba, võtab selle järjekorras järgmine reisija). Kassa müüb pileteid kahes punktis: A ja IN. Taotluste voo intensiivsus (reisijad, kes soovivad piletit osta) mõlema punkti kohta A ja B on sama: λ A = λ B = 0,45 (reisija minutis) ja kokku moodustavad nad üldise rakenduste voo intensiivsusega λ A + λB = 0,9. Kassapidaja kulutab reisija teenindamiseks keskmiselt kaks minutit.

Kogemus näitab, et piletikassas kogunevad järjekorrad, reisijad kurdavad teeninduse aegluse üle. A ja sisse IN, luua kaks spetsialiseeritud piletikassat (üks aken mõlemas), müües pileteid üks - ainult punktini A, teine ​​- ainult punktini IN. Selle ettepaneku põhjendatus on vastuoluline – mõned väidavad, et järjekorrad jäävad samaks. Ettepaneku kasulikkust tuleb kontrollida arvutuste teel. Kuna karakteristikuid saame arvutada ainult kõige lihtsama QS jaoks, siis oletame, et kõik sündmuste vood on kõige lihtsamad (see ei mõjuta järelduste kvalitatiivset poolt).

Noh, asume siis asja kallale. Piletimüügi korraldamiseks kaaluge kahte võimalust - olemasolevat ja pakutavat.

Variant I (olemasolev). Kahe kanaliga QS võtab vastu rakenduste voo, mille intensiivsus on λ = 0,9; hooldusvoolu intensiivsus μ = 1/2 = 0,5; ρ = λ/μ = l.8. Kuna ρ/2 = 0,9<1, финальные вероятности существуют. По первой формуле (20.22) находим p 0 ≈ 0,0525. Keskmine, järjekorras olevate taotluste arv leitakse valemiga (20,23): L och ≈ 7,68; kliendi keskmine järjekorras viibitud aeg (vastavalt esimesele valemitest (20.25)) on võrdne W pts ≈ 8,54 (min).

II variant (pakutud). On vaja arvestada kahe ühe kanaliga QS-iga (kaks spetsiaalset akent); igaüks saab päringute voo intensiivsusega λ = 0,45; μ . ikka võrdne 0,5-ga; ρ = λ/μ = 0,9<1; финальные вероятности существуют. По формуле (20.20) находим среднюю длину очереди (к одному окошку) L och = 8,1.

Siin on üks teile! Selgub, et järjekorra pikkus mitte ainult ei vähenenud, vaid suurenes! Ehk on keskmine ooteaeg järjekorras vähenenud? Vaatame. Delya L punktid λ = 0,45, saame W pts ≈ 18 (minutit).

See on ratsionaliseerimine! Vähenemise asemel kasvas nii keskmine järjekorra pikkus kui ka keskmine ooteaeg selles!

Proovime arvata, miks see juhtus? Mõeldes oma ajudele, jõuame järeldusele: see juhtus seetõttu, et esimeses variandis (kahe kanaliga QS) on kahe kassapidaja keskmine jõudeoleku osa väiksem: kui ta ei tegele reisija teenindamisega, ostab pileti A, ta saab hoolitseda reisija eest, kes ostab pileti punkti IN, ja vastupidi. Teises variandis sellist vahetatavust pole: tühi kassapidaja istub lihtsalt käed rüpes...

- Noh , OK, lugeja on valmis nõustuma, kasv on seletatav, aga miks see nii märkimisväärne on? Kas siin on valearvestus?

Ja me vastame sellele küsimusele. Viga ei ole. Asi on selles et , et meie näites töötavad mõlemad QS-id oma võimaluste piiril; kui teenindusaega veidi pikendate (st vähendate μ), ei tule nad enam reisijatevoogudega toime ja järjekord hakkab lõputult kasvama. Ja kassapidaja "lisa seisakuaeg" on teatud mõttes võrdne tema tootlikkuse vähenemisega μ.

Seega osutub algul paradoksaalsena (või isegi lihtsalt valena) tunduv arvutustulemus õigeks ja seletatavaks.

Sedalaadi paradoksaalsed järeldused, mille põhjus pole sugugi ilmne, on järjekorra teoorias rikas. Autorit ennast tuli korduvalt "üllatuda" arvutuste tulemustest, mis hiljem õigeks osutusid.

Viimasele ülesandele mõeldes võib lugeja küsimuse esitada nii: kui kassa müüb pileteid ainult ühte punkti, siis loomulikult peaks teenindusaeg vähenema, noh, mitte poole võrra, aga vähemalt mõnevõrra, aga arvasime, et ikkagi keskmine on 2 (min.). Kutsume nii valivat lugejat vastama küsimusele: kui palju tuleks seda vähendada, et “ratsionaliseerimisettepanek” kasumlikuks muutuks?

Taas kohtume, kuigi elementaarne, kuid siiski optimeerimisprobleem. Esialgsete arvutuste abil on ka kõige lihtsamate, Markovi mudelite puhul võimalik selgitada nähtuse kvalitatiivset poolt – kuidas on tulus tegutseda ja kuidas kahjumlik. Järgmises osas tutvustame mõningaid elementaarseid mitte-Markovi mudeleid, mis avardavad veelgi meie võimalusi.

Pärast seda, kui lugeja on tutvunud kõige lihtsama QS lõppseisundi tõenäosuste ja jõudlusnäitajate arvutamise meetoditega (ta on selgeks saanud surma- ja paljunemisskeemi ning Little'i valemi), võib talle pakkuda iseseisvaks kaalumiseks veel kaks lihtsat QS-i.

Ühe kanaliga QS piiratud järjekorraga. Probleem erineb ülesandest 2 ainult selle poolest, et taotluste arv järjekorras on piiratud (ei tohi ületada mõnda antud T). Kui uus päring saabub hetkel, mil kõik kohad järjekorras on hõivatud, jätab see QS-i teenindamata (tagasilükatud).

On vaja leida olekute lõplikud tõenäosused (muide, need on selles ülesandes olemas mis tahes ρ korral - olekute arv on ju lõplik), ebaõnnestumise tõenäosus R otk, absoluutne ribalaius A, tõenäosus, et kanal on hõivatud R zan, keskmine järjekorra pikkus L och, ühise turukorralduse keskmine taotluste arv L süsteem , keskmine ooteaeg järjekorras W och , taotluse keskmine ühises turukorralduses viibimise aeg W süsteem Järjekorra karakteristikute arvutamisel saate kasutada sama tehnikat, mida kasutasime ülesandes 2, selle erinevusega, et kokkuvõte on vajalik mitte lõpmatu, vaid lõpliku progressiooni kohta.

Suletud ahelaga QS ühe kanaliga ja m rakenduste allikad. Konkreetsuse huvides püstitame ülesande järgmisel kujul: üks töötaja teenib T masinad, millest igaüks vajab aeg-ajalt reguleerimist (parandust). Iga töömasina nõudlusvoo intensiivsus on võrdne λ-ga . Kui masin on hetkel tööst väljas, kui töötaja on vaba, läheb ta kohe teenindusse.

Kui ta on hetkel, kui töötaja on hõivatud, rivist väljas, seab ta järjekorda ja ootab, et töötaja vabaneks. Keskmine seadistamise aeg t pööre = 1/μ. Töötajale saabuvate päringute voo intensiivsus sõltub sellest, kui palju masinaid töötab. Kui see töötab k tööpingid, on see võrdne kλ. Leidke lõppseisundi tõenäosused, töötavate masinate keskmine arv ja tõenäosus, et töötaja on hõivatud.

Pange tähele, et selles QS-is eksisteerivad lõplikud tõenäosused ka mis tahes väärtustele λ ja μ = 1/ t o, kuna süsteemi olekute arv on lõplik.

Eelmises loengus käsitletud diskreetsete olekute ja pideva ajaga Markovi stohhastiline protsess toimub järjekorrasüsteemides (QS).

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

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

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

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

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

Riis. 1

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

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

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

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

terminaator - tehingute hävitaja;

ladu - ressursside ja valmistoodete ladustamine;

raamatupidamiskonto - "konteerimise" tüüpi toimingute tegemiseks;

manager – ressursside juht;

Ühise turukorralduse klassifikatsioon

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

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

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

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

QS järjekordadega olenevalt järjekorra korraldusest on jagatud eri tüüpideks - piiratud või piiramata. Piirangud võivad puudutada nii järjekorra pikkust kui ka ooteaega, "teenindusdistsipliini".

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

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

Järjekorrapiirangu tüüpe saab kombineerida.

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

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

Lisaks jagunevad SMOd avatud CMO ja suletud SMO.

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

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

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

• ühe kanaliga;
• mitme kanaliga.

Järjekorrasüsteemi omadused

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

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

Nõuded sisendvoog

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

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

E(A) on keskmine (MO) saabumisaeg;

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

Sisendvoo omadused:

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

Järjekorra distsipliin

Järjekord - nõuete kogum, mis ootab hooldust.

Järjekorral on nimi.

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

• kes ees – see mees;

esimene sisse esimene välja (FIFO)

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

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

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

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

Toimingute loend:

• sisestage sabasse;
• võtta algusest peale;
• eemaldage loendist pärast aegumist.
• viimane tuli, see mees LIFO (padruniklamber, raudteejaama tupik, läks täis autosse).

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

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

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

Järjekorra omadused

• piirangooteaeg teenuse toimumise hetk (teenuse osutamisel on piiratud ooteajaga järjekord, mis on seotud mõistega "lubatav järjekorra pikkus");
• järjekorra pikkus.

Teenindusmehhanism

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

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

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

Si- teenindusaeg i th nõue;

E(S)– keskmine teenindusaeg;

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

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

QS-i kasutustegur

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

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

Teenindussüsteemi struktuur

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

Näide. Kaupluses kassaaparaadid.

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

Näide. Arstlik komisjon.

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

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

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

QS-i toimimise tõhususe peamised kriteeriumid

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

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

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

Vood, viivitused, teenindus. Pollacek-Khinchin valem

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

D i– päringujärjekorras viibimine i;

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

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

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

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

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

Seejärel eksponendid (kui neid on)

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

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

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

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

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

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

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

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

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

.

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

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

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

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