2.2 Višekanalni QS sa čekanjem
Sistem sa ograničenom dužinom čekanja. Razmotrimo kanal QS sa čekanjem, koji prima tok zahtjeva sa intenzitetom; intenzitet usluge (za jedan kanal); broj mjesta u redu.
Stanja sistema su numerisana prema broju zahteva povezanih sa sistemom:
bez reda:
Svi kanali su besplatni;
Jedan kanal je zauzet, ostali su slobodni;
-kanali su zauzeti, ostali nisu;
Svi kanali su zauzeti, nema slobodnih kanala;
postoji red:
Svi n-kanali su zauzeti; jedna aplikacija je u redu čekanja;
Svi n-kanali, r-zahtjevi u redu su zauzeti;
Svi n-kanali, r-zahtjevi u redu su zauzeti.
GSP je prikazan na sl. 17. Svaka strelica je označena odgovarajućim intenzitetima tokova događaja. Duž strelica slijeva na desno, sistem se uvijek prenosi istim tokom zahtjeva intenziteta od
Rice. 17. Višekanalni QS sa čekanjem
Grafikon je tipičan za procese reprodukcije i smrti, za koje je prethodno dobiveno rješenje. Napišimo izraze za granične vjerovatnoće stanja koristeći notaciju: (ovdje koristimo izraz za zbir geometrijska progresija sa imeniocem).
Tako su pronađene sve vjerovatnoće stanja.
Hajde da odredimo karakteristike performansi sistema.
Vjerovatnoća neuspjeha. Dolazni zahtjev se odbija ako su svi n-kanali i sva m-mjesta u redu zauzeti:
(18)
Relativna propusnost dopunjuje vjerovatnoću kvara na jednu:
Apsolutna propusnost QS-a:
(19)
Prosječan broj zauzetih kanala. Za QS sa odbijanjima, to se poklopilo sa prosječnim brojem prijava u sistemu. Za QS sa redom, prosječan broj zauzetih kanala ne poklapa se sa prosječnim brojem aplikacija u sistemu: potonja vrijednost se razlikuje od prve po prosječnom broju aplikacija u redu.
Označimo prosječan broj zauzetih kanala sa . Svaki zauzeti kanal služi u prosjeku A-zahtjeva u jedinici vremena, a QS u cjelini služi u prosjeku A-zahtjeva u jedinici vremena. Dijelimo jedno na drugo, dobijamo:
Prosječan broj aplikacija u redu može se izračunati direktno kao matematičko očekivanje diskretnog slučajna varijabla:
(20)
Ovdje se opet (izraz u zagradama) javlja derivacija zbira geometrijske progresije (vidi gore (11), (12) - (14)), koristeći relaciju za to, dobijamo:
Prosječan broj aplikacija u sistemu:
Prosječno vrijeme čekanja za aplikaciju u redu čekanja. Razmotrimo niz situacija koje se razlikuju po stanju u kojem će novopristigli zahtjev naći sistem i koliko dugo će morati da čeka na servis.
Ako zahtjev ne utvrdi da su svi kanali zauzeti, on uopće neće morati čekati (odgovarajući članovi u matematičko očekivanje jednaki su nuli). Ako zahtjev stigne u vrijeme kada su svi n-kanali zauzeti i nema reda, morat će čekati u prosjeku vrijeme koje je jednako (jer "tok oslobađanja" -kanala ima intenzitet ). Ako zahtjev pronađe sve kanale zauzete i jedan zahtjev ispred njega u redu čekanja, morat će čekati u prosjeku određeno vrijeme (za svaki zahtjev ispred) itd. Ako se zahtjev nađe u redu od - zahtjeva, morat će u prosjeku čekati vrijeme Ako novopristigli zahtjev pronađe m-zahtjeve koji su već u redu čekanja, onda uopće neće čekati (ali neće biti uslužen). Prosječno vrijeme čekanja pronalazimo množenjem svake od ovih vrijednosti sa odgovarajućim vjerovatnoćama:
(21)
Kao iu slučaju jednokanalnog QS-a sa čekanjem, napominjemo da se ovaj izraz od izraza za prosječnu dužinu reda (20) razlikuje samo po faktoru , tj.
.
Prosječno vrijeme boravka zahtjeva u sistemu, kao i za jednokanalni QS, razlikuje se od prosječnog vremena čekanja za prosječno vrijeme usluge pomnoženo sa relativnom propusnošću:
.
Sistemi sa neograničenom dužinom čekanja. Razmatrali smo kanal QS sa čekanjem, kada u redu istovremeno ne može biti više od m-zahtjeva.
Kao i do sada, pri analizi sistema bez ograničenja potrebno je uzeti u obzir dobijene relacije za .
Dobijamo vjerovatnoće stanja iz formula prelaskom na granicu (na ). Imajte na umu da se zbir odgovarajuće geometrijske progresije konvergira na i divergira na >1. Pod pretpostavkom da<1 и устремив в формулах величину m к бесконечности, получим выражения для предельных вероятностей состояний:
(22)
Vjerovatnoća kvara, relativna i apsolutna propusnost. Budući da će svaki zahtjev prije ili kasnije biti servisiran, karakteristike QS propusnosti će biti:
Prosječan broj aplikacija u redu se dobija iz (20):
,
a prosječno vrijeme čekanja je od (21):
.
Prosječan broj zauzetih kanala, kao i ranije, određuje se kroz apsolutnu propusnost:
.
Prosječan broj aplikacija povezanih s QS-om definiran je kao prosječan broj aplikacija u redu plus prosječan broj aplikacija u usluzi (prosječan broj zauzetih kanala):
Primjer 2. Benzinska stanica sa dvije pumpe (n = 2) opslužuje protok automobila intenziteta =0,8 (automobila u minuti). Prosečno servisno vreme po mašini:
U okolini nema druge benzinske pumpe, tako da red automobila ispred pumpe može rasti gotovo neograničeno. Pronađite karakteristike QS-a.
Zbog<1, очередь не растет безгранично и имеет смысл говорить о предельном стационарном режиме работы СМО. По формулам (22) находим вероятности состояний:
itd.
Prosječan broj zauzetih kanala ćemo pronaći tako što ćemo apsolutni kapacitet QS A = = 0,8 podijeliti sa intenzitetom usluge = 0,5:
Verovatnoća da nema čekanja u redu na benzinskoj pumpi će biti:
Prosječan broj automobila u redu:
Prosječan broj automobila na benzinskim pumpama:
Prosječno vrijeme čekanja u redu:
Prosječno vrijeme koje automobil provede na benzinskoj pumpi:
QS sa ograničenim vremenom čekanja. Ranije smo razmatrali sisteme sa čekanjem ograničenim samo dužinom reda (broj m zahteva istovremeno u redu). U takvom QS-u, aplikacija koja je narasla u redu čekanja ne napušta je dok ne čeka na servis. U praksi postoje i drugi tipovi QS-a u kojima aplikacija nakon nekog vremena može napustiti red čekanja (tzv. „nestrpljive“ aplikacije).
Razmotrimo QS ovog tipa, pod pretpostavkom da je ograničenje vremena čekanja slučajna varijabla.
Pretpostavimo da postoji QS na n-kanalnom čekanju u kojem je broj mjesta u redu neograničen, ali vrijeme zadržavanja zahtjeva u redu je neka slučajna varijabla sa srednjom vrijednošću, tako da je svaki zahtjev u redu podložan svojevrsnom Poissonovom "toku njege" sa intenzitetom:
Ako je ovaj tok Poisson, tada će proces koji se odvija u QS-u biti markovski. Nađimo vjerovatnoće stanja za to. Numeracija stanja sistema povezana je sa brojem aplikacija u sistemu - i koje se poslužuju i stoje u redu:
bez reda:
Svi kanali su besplatni;
Jedan kanal je zauzet;
Dva kanala su zauzeta;
Svi n-kanali su zauzeti;
postoji red:
Svi n-kanali su zauzeti, jedan zahtjev je u redu;
Svi n-kanali su zauzeti, r-zahtjevi su u redu itd.
Grafikon stanja i prelaza sistema prikazan je na sl. 23.
Rice. 23. QS sa ograničenim vremenom čekanja
Označimo ovaj graf kao prije; sve strelice koje vode s lijeva na desno pokazat će intenzitet toka aplikacija. Za stanja bez reda, strelice koje vode od njih s desna na lijevo će, kao i do sada, označavati ukupan intenzitet toka koji opslužuje sve zauzete kanale. Što se tiče stanja sa redom, strelice koje vode od njih s desna na lijevo imat će ukupan intenzitet toka usluge svih n-kanala plus odgovarajući intenzitet toka odlazaka iz reda. Ako u redu ima r aplikacija, tada će ukupan intenzitet toka odlazaka biti jednak .
Kao što se može vidjeti iz grafikona, postoji obrazac reprodukcije i smrti; koristeći opšte izraze za granične vjerovatnoće stanja u ovoj shemi (koristeći skraćene oznake, pišemo:
(24)
Napomenimo neke karakteristike QS-a sa ograničenim čekanjem u poređenju sa prethodno razmatranim QS-om sa zahtjevima „pacijenata“.
Ako dužina reda nije ograničena i zahtjevi su "strpljivi" (ne napuštaju red), tada stacionarni granični režim postoji samo u slučaju (na , odgovarajuća beskonačna geometrijska progresija divergira, što fizički odgovara neograničenom rastu reda u ).
Naprotiv, u QS-u sa “nestrpljivim” zahtjevima koji prije ili kasnije napuštaju red, uvijek se postiže uspostavljeni servisni režim na, bez obzira na smanjeni intenzitet toka zahtjeva. Ovo slijedi iz činjenice da red za u nazivniku formule (24) konvergira za bilo koje pozitivne vrijednosti i .
Za QS sa “nestrpljivim” zahtjevima, koncept “vjerovatnosti neuspjeha” nema smisla - svaki zahtjev dolazi u red, ali možda neće čekati uslugu, već odlazi prije vremena.
Relativna propusnost, prosječan broj zahtjeva u redu čekanja. Relativni kapacitet q takvog QS-a može se izračunati na sljedeći način. Očigledno je da će sve aplikacije biti servisirane, osim onih koje napuste red prije roka. Izračunajmo prosječan broj aplikacija koje rano napuštaju red. Da bismo to učinili, izračunavamo prosječan broj aplikacija u redu čekanja:
Svaka od ovih aplikacija podliježe „toku odlazaka“ s intenzitetom od . To znači da će od prosječnog broja -prijava u redu čekanja, u prosjeku, -prijave otići bez čekanja na servis, -prijave po jedinici vremena i ukupno po jedinici vremena, u prosjeku -prijave će biti uslužene. Relativni kapacitet QS-a će biti:
Još uvijek dobijamo prosječan broj zauzetih kanala dijeljenjem apsolutne propusnosti A sa:
(26)
Prosječan broj aplikacija u redu čekanja. Relacija (26) vam omogućava da izračunate prosječan broj aplikacija u redu bez zbrajanja beskonačne serije (25). Iz (26) dobijamo:
a prosječan broj zauzetih kanala uključenih u ovu formulu može se naći kao matematičko očekivanje slučajne varijable Z, uzimajući vrijednosti 0, 1, 2,..., n sa vjerovatnoćama ,:
U zaključku, napominjemo da ako u formulama (24) idemo na granicu na (ili, što je isto, na ), tada na 
Red dužine k ostaje u njemu sa verovatnoćom Pk i ne ulazi u red sa verovatnoćom gk=1 - Pk." Upravo tako se ljudi obično ponašaju u redovima. U sistemima čekanja, koji su matematički modeli proizvodnih procesa, moguće je Dužina reda čekanja je ograničena konstantnom veličinom (na primjer, kapacitet bunkera).
U ovom odeljku ćemo pogledati neke od najjednostavnijih QS-a i izvesti izraze za njihove karakteristike (indikatore učinka). Istovremeno ćemo demonstrirati glavne metodološke tehnike karakteristične za elementarnu, “Markovljevu” teoriju čekanja. Nećemo juriti za brojem QS uzoraka za koje će biti izvedeni konačni izrazi karakteristika; Ova knjiga nije referentna knjiga o teoriji čekanja (tu ulogu mnogo bolje ispunjavaju posebni priručnici). Naš cilj je da čitatelja upoznamo s nekim „malim trikovima“ koji olakšavaju put kroz teoriju čekanja, što u nizu postojećih (čak i pretendiranih da su popularne) knjiga može izgledati kao nekoherentan skup primjera.
U ovom odeljku ćemo smatrati sve tokove događaja koji prenose QS iz stanja u stanje najjednostavnijim (bez posebnog propisivanja svakog puta). Među njima će biti i takozvani „tok usluga“. Odnosi se na tok zahtjeva koje opslužuje jedan kontinuirano zauzet kanal.
U ovom toku, interval između događaja, kao i uvijek u najjednostavnijem toku, ima eksponencijalnu distribuciju (u mnogim priručnicima umjesto toga kažu: “vrijeme usluge je eksponencijalno”; mi ćemo sami koristiti ovaj termin u budućnosti). U ovom dijelu, eksponencijalna distribucija vremena servisa će se podrazumijevati, kao i uvijek za „najjednostavniji“ sistem.
U nastavku ćemo predstaviti karakteristike performansi QS-a koji se razmatra.
1. n-kanalni QS sa kvarovima (Erlang problem).
Ovdje ćemo razmotriti jedan od prvih, “klasičnih” problema teorije čekanja; ovaj problem je proizašao iz praktičnih potreba telefonije i rešio ga je početkom ovog veka danski matematičar Erlang. Problem je formulisan na sledeći način: postoje kanali (komunikacijske linije) koji primaju tok zahteva sa intenzitetom K. Tok usluga ima intenzitet (inverzna vrednost prosečnog vremena usluge). Pronađite konačne vjerovatnoće QS stanja, kao i karakteristike njegove efektivnosti:
A - apsolutna propusnost, odnosno prosječan broj servisiranih aplikacija u jedinici vremena;
Relativna propusnost, tj. prosječan udio dolaznih aplikacija koje opslužuje sistem;
Rotk je vjerovatnoća odbijanja, tj. da će aplikacija ostaviti QS neserviran;
k je prosječan broj zauzetih kanala.
Rješenje. Numerićemo stanja sistema S (SMO) prema broju zahteva koji se nalaze u sistemu (u ovom slučaju to se poklapa sa brojem zauzetih kanala):
Ne postoji niti jedna aplikacija u CMO,
U QS-u postoji jedan zahtjev (jedan kanal je zauzet, ostali su slobodni),
U sistemu QS, zahtjevi za kanalima su zauzeti, ostali su besplatni),
Postoje zahtjevi u QS-u (svi kanali su zauzeti).
Grafikon stanja QS odgovara obrascu smrti i reprodukcije (slika 20.1). Označimo ovaj grafikon - stavimo intenzitet tokova događaja pored strelica Tok aplikacija intenziteta X se prenosi iz sistema (čim stigne aplikacija, sistem skače sa ).
Isti tok zahtjeva prenosi sistem iz bilo kojeg lijevog stanja u susjedno desno (vidi gornje strelice na slici 20.1).
Stavimo intenzitete na donje strelice. Neka sistem bude u stanju (jedan kanal radi). Obavlja održavanje po jedinici vremena. Označavamo intenzitet strelice. Sada zamislimo da je sistem u stanju (dva kanala rade). Da bi otišao na, ili prvi ili drugi kanal moraju završiti servisiranje; ukupan intenzitet njihovih tokova usluga jednak je odgovarajućoj strelici. Ukupan tok usluga koje pružaju tri kanala ima intenzitet jednak kanalima - ove intenzitete stavljamo na donje strelice na Sl. 20.1.
A sada, znajući sve intenzitete, koristićemo gotove formule (19.7), (19.8) za konačne verovatnoće u šemi smrti i reprodukcije. Koristeći formulu (19.8) dobijamo:
Uvjeti proširenja će biti koeficijenti u izrazima za
Imajte na umu da su u formulama (20.1), (20.2) intenziteti jaja uključeni ne pojedinačno, već samo u obliku omjera
a vrijednost ćemo nazvati „smanjeni intenzitet toka aplikacija“. Njegovo značenje je prosječan broj primljenih zahtjeva tokom prosječnog vremena servisiranja jednog zahtjeva. Koristeći ovu notaciju, prepisujemo formule (20.1), (20.2) u obliku:
Formule (20.4), (20.5) za konačne vjerovatnoće stanja zovu se Erlangove formule - u čast osnivača teorije čekanja. Većina ostalih formula ove teorije (danas ih ima više nego gljiva u šumi) ne nose nikakva posebna imena.
Tako su pronađene konačne vjerovatnoće. Koristeći ih, izračunat ćemo karakteristike performansi QS-a. Prvo, pronađimo vjerovatnoću da će dolazna aplikacija biti odbijena (neće biti servisirana). Da biste to učinili, svi kanali moraju biti zauzeti, što znači
Odavde nalazimo relativnu propusnost - vjerovatnoću da će zahtjev biti uslužen:
Apsolutnu propusnost dobijamo množenjem intenziteta toka zahtjeva X sa
Ostaje samo da se pronađe prosječan broj zauzetih kanala k. Ova vrijednost se može naći "direktno", kao matematičko očekivanje diskretne slučajne varijable sa mogućim vrijednostima i vjerovatnoćama ovih vrijednosti.
Zamjenom izraza (20.5) za ovdje i izvođenjem odgovarajućih transformacija, na kraju bismo dobili ispravnu formulu za k, ali ćemo je izvesti mnogo jednostavnije (evo ga, jedan od “malih trikova”!) U stvari, znamo. apsolutna propusnost A. Ovo nije ništa drugo do intenzitet protoka aplikacija koje opslužuje sistem. Svaki zauzeti kanal služi u prosjeku zahtjeva po jedinici vremena. To znači da je prosječan broj zauzetih kanala
I koji će udio kanala biti neaktivan?
Ovdje je već vidljiv nagovještaj optimizacije. Zapravo, održavanje svakog kanala po jedinici vremena košta određeni iznos. Istovremeno, svaka servisirana aplikacija donosi određeni prihod. Pomnoživši ovaj prihod sa prosječnim brojem servisiranih aplikacija A po jedinici vremena, dobijamo prosječan prihod od QS-a po jedinici vremena. Naravno, kako se broj kanala povećava, taj prihod raste, ali se povećavaju i troškovi vezani za održavanje kanala. Šta će prevagnuti - povećanje prihoda ili rashoda? Zavisi od uslova rada, „naknade za servisiranje aplikacije“ i troškova održavanja kanala. Znajući ove vrijednosti, možete pronaći optimalan broj kanala, najisplativiji. Takav problem nećemo rješavati, prepuštajući istom “nelijenjem, radoznalom čitaocu” da smisli primjer i riješi ga. Općenito, izmišljanje problema razvija se više od rješavanja onih koje je neko već postavio.
ML sistemi su dio šire klase dinamičkih sistema koji se ponekad nazivaju sistemi protoka. Sistem navoja je sistem u kojem se određeni objekti pomiču kroz jedan ili više kanala ograničenog kapaciteta u svrhu premještanja s jedne tačke na drugu. Kada se analiziraju protočni sistemi, oni se dijele u dvije glavne klase:
regularni sistemi, odnosno sistemi u kojima se tokovi ponašaju na predvidljiv način (poznata je veličina toka i vrijeme njegovog pojavljivanja u kanalu). U slučaju kada postoji samo jedan kanal, proračun sistema je trivijalan. Očigledno je da između intenziteta strujanja λ i brzinu usluge With postoji odnos λ < c;
nepravilni sistemi, tj. sistemi u kojima se niti ponašaju na nepredvidive načine.
Zanimljiviji je slučaj redovnog toka koji je raspoređen preko mreže kanala. Očigledno je da je stanje λ < c sačuvane za svaki kanal. Ovo stvara složen kombinatorni problem.
Postoji sedam puteva:
A→B→D→E→F
A→C→B→ E→F
A→C→B→D→E→F
A→C→B→ D→F
Potrebno je prevoziti teret iz A V F. Kapacitet svakog kanala je poznat. Koliki je kapacitet mreže i kojim putem treba da ide tok? Ovaj problem se može riješiti korištenjem teoreme o maksimalnom protoku, koju smo ranije razmatrali (slika 6).
Druga klasa uključuje slučajne vjerovatne tokove, u kojima vrijeme prijema zahtjeva nije određeno, a broj zahtjeva je nepredvidiv. Teorija čekanja se bavi rješavanjem takvih problema.
Generalno, sistem čekanja se može predstaviti na slici 7.
Rice. 7.
Predmet teorije čekanja je da se uspostavi odnos između prirode toka zahteva, broja kanala, produktivnosti, ispravnog rada i efikasnosti.
As karakteristike performansi Mogu se koristiti sljedeće količine i funkcije:
prosječan broj aplikacija koje QS može servisirati po jedinici vremena;
prosječan broj prijava koje se odbijaju i napuštaju CMO;
vjerovatnoća da će primljeni zahtjev biti odmah servisiran;
prosječno vrijeme čekanja u redu;
prosječan broj aplikacija u redu čekanja;
prosječni prihod SMO po jedinici vremena i drugi ekonomski pokazatelji SMO.
Analiza QS je pojednostavljena ako se u sistemu javlja Markovljev proces, tada se sistem može opisati običnim diferencijalnim jednačinama, a granične vjerovatnoće - linearnim algebarskim jednačinama.
Markovljev proces zahtijeva da svi tokovi budu Poissonovi (bez naknadnih efekata), ali se aparat Markovljevih procesa također koristi kada se proces razlikuje od Markovljevog. U ovom slučaju, karakteristike QS-a se mogu približno procijeniti: što je QS složeniji, to je aproksimacija tačnija.
Klasifikacija sistema čekanja
QS može biti dva tipa:
QS sa kvarovima;
QS sa čekanjem (tj. sa redom).
Usluga u sistemima sa redom može biti različite prirode:
usluga se može pojednostaviti;
nasumična usluga;
usluga sa prioritetom, dok prioritet može biti sa ili bez prekida.
Sistemi čekanja se dijele na:
sistemima sa neograničenim čekanjem, u ovom slučaju, zadatak koji je primio QS postaje u redu čekanja i čeka na uslugu. Prije ili kasnije ona će biti uslužena;
sistemima sa ograničenim očekivanjima, dok se aplikaciji u redu postavljaju ograničenja, na primjer, ograničeno vrijeme provedeno u redu čekanja, dužina reda, ukupno vrijeme provedeno u QS-u. U zavisnosti od vrste QS-a, mogu se koristiti različiti indikatori za procenu efektivnosti.
Za QS sa kvarovima koriste se sljedeći pokazatelji učinka:
apsolutna propusnost A– prosječan broj aplikacija koje se mogu servisirati u jedinici vremena;
relativna propusnost Q– relativni prosječan broj prijava. U ovom slučaju, relativna propusnost se može pronaći pomoću formule
Gdje je λ intenzitet zahtjeva koje je primio QS.
Za SMO sa očekivanjem apsolutna propusnost A I relativna propusnost Q gube svoje značenje, ali druge karakteristike postaju važne:
jedinica vremena čekanja u redu;
prosječan broj aplikacija u redu čekanja;
prosječno vrijeme provedeno u sistemu.
Za QS sa ograničenim redom, interesantne su obe grupe karakteristika.
Uzmite u obzir n - sistem čekanja kanala sa čekanjem.
Intenzitet toka usluge je μ. Trajanje usluge je slučajna varijabla koja podliježe zakonu eksponencijalne distribucije. Tok usluge je najjednostavniji Poissonov tok događaja.
Veličina reda omogućava ljudima da budu u njemu m aplikacija.
Da biste pronašli granične vjerovatnoće, možete koristiti sljedeće izraze.
(0‑1)
Gdje.
Vjerovatnoća odbijanja servisiranja aplikacije(kvar će se dogoditi ako su svi kanali zauzeti i postoje m zahtjeva):
(0‑2)
Relativna propusnost.
(0‑3)
Apsolutna propusnost.
(0‑4)
Prosječan broj zauzetih kanala.
Za QS sa redom, prosječan broj zauzetih kanala se ne poklapa (za razliku od QS-a sa kvarovima) sa prosječnim brojem zahtjeva u sistemu. Razlika je jednaka broju aplikacija koje čekaju u redu.
Označimo prosječan broj zauzetih kanala. Svaki zauzeti kanal opslužuje u prosjeku μ zahtjeva po jedinici vremena, a QS kao cjelina opslužuje A potraživanja po jedinici vremena. Dijeljenjem A sa μ dobijamo
(0‑5)
Prosječan broj aplikacija u redu čekanja.
Da biste pronašli prosječan broj aplikacija koje čekaju u redu ako je χ≠1, možete koristiti izraz:
(0‑6)
(0‑7)
gdje je = .
Prosječan broj aplikacija u sistemu.
(0‑8)
Prosječno vrijeme čekanja za aplikaciju u redu čekanja.
Prosječno vrijeme čekanja za aplikaciju u redu može se naći iz izraza (χ≠1).
(0‑9)
Prosječno vrijeme boravka aplikacije u sistemu.
Kao iu slučaju jednokanalnog QS-a, imamo:
(0‑10)
Sadržaj rada.
Priprema eksperimentalnih instrumenata .
Izvodi se u skladu sa opštim pravilima.
Proračun korištenjem analitičkog modela .
1. Pripremite sljedeću tabelu u programu Microsoft Excel.
|
Opcije |
Analitički |
Imitacija |
|||||||||||||||
|
n |
m |
Ta |
Ts |
ρ |
χ |
P0 |
P1 |
p2 |
Rotk |
W |
nozh |
q |
A |
Rotk |
W |
q |
A |
2. U kolone za QS parametre tabele upišite svoje početne podatke koji se određuju prema pravilu:
n =1,2,3
m=1,3,5
Za svaku kombinaciju ( n,m) potrebno je pronaći teorijske i eksperimentalne vrijednosti QS indikatora za sljedeće parove vrijednosti:
= <порядковый номер в списке группы>
3. Unesite odgovarajuće formule u kolone sa indikatorima analitičkog modela.
Eksperimentirajte na simulacijskom modelu.
1. Postavite način pokretanja s eksponencijalno raspoređenim vremenom usluge postavljanjem vrijednosti odgovarajućeg parametra na 1.
2. Za svaku kombinaciju n, m i pokrenite model.
Unesite rezultate trčanja u tabelu.
3. U odgovarajuće kolone tabele unesite formule za izračunavanje prosečne vrednosti indikatora Ptk, q i A.
Analiza rezultata .
1. Analizirati rezultate dobijene teorijskim i eksperimentalnim metodama, međusobno upoređujući rezultate.
2. Za jednu od kombinacija (n,m) nacrtajte na jednom dijagramu zavisnost Ptk od teorijski i eksperimentalno dobijenih podataka.
Optimizacija QS parametara .
Riješite problem optimizacije veličine broja mjesta u redu čekanja m za dva uređaja sa prosječnim servisnim vremenom = sa stanovišta postizanja maksimalnog profita. Kao uslove problema uzmite:
- prihod od servisiranja jedne aplikacije jednak 80 USD/sat,
- trošak održavanja jednog uređaja je 1$/sat,
- trošak održavanja jednog mjesta u redu je 0,2 USD/sat.
1. Za proračune je preporučljivo napraviti tabelu:
Prva kolona je popunjena brojem uređaja n =1.
Druga kolona je ispunjena vrijednostima brojeva u prirodnom nizu (1,2,3...).
Sve ćelije u trećoj i četvrtoj koloni su ispunjene vrijednostima.
Formule za kolone tabele u sekciji 0 prenose se u ćelije kolona od pet do četrnaest.
U kolone sa početnim podacima odjeljaka Prihod, Rashod, Dobit unesite vrijednosti (vidi gore).
U kolone sa izračunatim vrijednostima odjeljaka Prihodi, Rashodi, Dobit upišite formule za obračun:
- broj aplikacija u jedinici vremena
N r =A
- ukupan prihod po jedinici vremena
I S = I r *N r
- ukupna potrošnja po jedinici vremena
E S =E s *n + E q *m
- profit po jedinici vremena
P = I S - E S
Gdje
Ir - prihod od jedne prijave,
E s - potrošnja po uređaju,
Eq - cijena po mjestu u redu
2. Popunite redove tabele za n=2 i n=3.
Pronađite m opt za n =1,2,3.
3. Nacrtajte grafove zavisnosti C(m) za n=1,2,3 na jednom dijagramu.
izvještaj o radu:
Izveštaj o radu treba da sadrži:
- početni podaci,
- rezultate proračuna i eksperimenata sa softverskim modelom,
Grafovi za P otvoren,
- tabela sa podacima kako biste pronašli najbolje m i vrijednost m opt,
- grafovi dobiti po jedinici vremena u zavisnosti od m za n=1,2,3.
Kontrolna pitanja :
1) Dajte kratak opis višekanalnog QS modela sa ograničenim redom čekanja.
2) Koji pokazatelji karakteriziraju funkcioniranje višekanalnog QS-a s ograničenim redom čekanja?
3) Kako se izračunavaju granične vjerovatnoće višekanalnog QS-a sa ograničenim redom čekanja?
4) Kako pronaći vjerovatnoću neuspjeha servisiranja aplikacije?
5) Kako pronaći relativnu propusnost?
6) Koja je apsolutna propusnost?
7) Kako se izračunava prosječan broj aplikacija u sistemu?
8) Navedite primjere višekanalnog QS-a s ograničenim redom čekanja.
Zadaci.
1) Benzinska pumpa ima 3 pumpe i platformu za 3 automobila koji čekaju na punjenje. U prosjeku, jedan automobil dolazi na stanicu svaka 4 minute. Prosečno servisno vreme za jednu mašinu je 2,8 minuta. Odredite radne karakteristike benzinske pumpe.
2) Stanica za tehnički pregled vozila, koja ima 3 punkta za pregled, prima u prosjeku 1 vozilo na svakih 0,4 sata. Parking u dvorištu kapaciteta 3 automobila. Prosječno vrijeme rada jednog posta je 0,5 sati. Odredite karakteristike servisne stanice.
3) Roba se u radnju dostavlja vozilima. U toku dana u prosjeku stigne 6 automobila. Pomoćne prostorije za pripremu robe za prodaju omogućavaju preradu i skladištenje robe koju donose dva vozila. Radnja zapošljava tri pakera proizvoda u smjenama, od kojih svaki u prosjeku može preraditi robu jedne mašine u roku od 5 sati. Radni dan pakera je 12 sati. Odrediti operativne karakteristike prodavnice, kao i koliki treba da bude kapacitet pomoćnih prostorija da verovatnoća kompletne obrade robe bude veća od 0,96.
4) Prodavnica ima tri kase. Prosječno vrijeme usluge za jednog korisnika je 3 minute. Intenzitet protoka kupaca je 7 ljudi u minuti. Broj kupaca koji stoje u redu na blagajni ne može biti veći od 5 osoba. Kupac koji dođe u prodavnicu u kojoj je po 5 ljudi u redu na kasi ne čeka, već napušta radnju. Odredite karakteristike radnje.
5) Veleprodajno skladište isporučuje robu kupcima. Utovar vozila vrše tri ekipe utovarivača, od kojih se svaki sastoji od 4 osobe. Skladište može istovremeno primiti 5 vozila i ukoliko u to vrijeme stigne novo vozilo, ono se ne servisira. Intenzitet dolaznog toka je 5 automobila na sat. Brzina utovara je 2 vozila na sat. Dajte ocjenu rada skladišta i mogućnost njegove reorganizacije.
6) Carinarnica ima tri terminala. Intenzitet protoka vozila koja prevoze robu i podležu carinskoj kontroli je 30 jedinica. po danu. Prosječno vrijeme carinske obrade na terminalu za jedno vozilo je 3 sata. Ako je 5 automobila u redu za prolazak carinske kontrole, onda automobili koji dolaze idu u drugu carinarnicu. Pronađite indikatore učinka carine.
7) U prosjeku, vozila sa građevinskim materijalom stignu na gradilište za 40 minuta. Prosječno vrijeme istovara jednog vozila je 1,8 sati. U istovaru učestvuju dvije ekipe utovarivača. U redu za istovar na gradilištu ne smije biti više od 5 vozila. Odredite pokazatelje učinka gradilišta.
8) U prosjeku, 12 automobila na sat stigne u autopraonicu sa tri radna mjesta. Ako je u redu već 6 automobila, novopridošli automobili ne ulaze u red, već napuštaju pranje. Prosječno vrijeme pranja automobila je 20 minuta, prosječna cijena usluga pranja automobila je 150 rubalja. Odredite pokazatelje učinka autopraonice i prosječan gubitak prihoda tokom radnog dana (od 9 do 19 sati).
9) Intenzitet protoka vozila koja prevoze robu i podležu carinskoj kontroli je 50 jedinica. po danu. Prosječno vrijeme carinske obrade na terminalu za jedno vozilo je 2,8 sati. Maksimalni red za carinsku kontrolu ne bi trebao biti veći od 8 automobila. Odredite koliko terminala treba otvoriti na carini kako bi vjerovatnoća zastoja vozila bila minimalna.
Sistem sa ograničenom dužinom čekanja. Razmotrimo kanal QS sa čekanjem, koji prima tok zahtjeva sa intenzitetom; intenzitet usluge (za jedan kanal); broj mjesta u redu.
Stanja sistema su numerisana prema broju zahteva povezanih sa sistemom:
bez reda:
Svi kanali su besplatni;
Jedan kanal je zauzet, ostali su slobodni;
Kanali su zauzeti, ostali nisu;
Svi kanali su zauzeti, nema slobodnih kanala;
postoji red:
Svi n kanala su zauzeti; jedna aplikacija je u redu čekanja;
Svih n kanala je zauzeto, r aplikacija je u redu čekanja;
Svi n kanala su zauzeti, m aplikacije u redu.
GSP je prikazan na sl. 5.9. Svaka strelica je označena odgovarajućim intenzitetima tokova događaja. Duž strelica slijeva na desno, sistem se uvijek prenosi istim tokom zahtjeva intenziteta od
Višekanalni eksponencijalni SMO razlikuje se od jednokanalnog na sljedeći način. Ima više od jednog kanala u njemu. Dolazni zahtjev postaje u redu ako su svi kanali zauzeti. U suprotnom, zahtjev zauzima slobodan kanal. 
(5.56)
Napišimo izraze za granične vjerovatnoće stanja koristeći notaciju: (vidi 5.45)
Vjerovatnoća neuspjeha. Primljena prijava se odbija ako su svi zauzeti n kanali i sve m mjesta u redu:
(5.57)
Relativna propusnost dopunjuje vjerovatnoću kvara na jednu:
Apsolutna propusnost QS-a:
(5.58)
Prosječan broj zauzetih kanala. Za SMO sa odbijanjima, poklopio se sa prosječnim brojem prijava u sistemu. Za SMO sa redom, prosječan broj zauzetih kanala ne poklapa se sa prosječnim brojem aplikacija u sistemu: posljednja vrijednost se razlikuje od prve po prosječnom broju aplikacija u redu.
Označimo prosječan broj zauzetih kanala sa . Svaki zauzeti kanal služi u prosjeku zahtjeva po jedinici vremena, i SMO ukupna usluga je prosječna A aplikacija u jedinici vremena. Dijelimo jedno na drugo, dobijamo:
Prosječan broj zahtjeva u redu može se izračunati direktno kao matematičko očekivanje diskretne slučajne varijable:
(5.59)
Ovdje se opet (izraz u zagradama) javlja derivacija zbira geometrijske progresije (vidi gore (5.50), (5.51)-(5.53)), koristeći relaciju za to, dobijamo:
Prosječan broj aplikacija u sistemu:
Prosječno vrijeme čekanja za aplikaciju u redu čekanja. Razmotrimo niz situacija koje se razlikuju po stanju u kojem će novopristigli zahtjev naći sistem i koliko dugo će morati da čeka na servis.
Ako zahtjev ne otkrije da su svi kanali zauzeti, on uopće neće morati čekati (odgovarajući termini u matematičkom očekivanju jednaki su nuli). Ako aplikacija stigne u vrijeme kada su svi zauzeti P kanala, ali nema reda, ona će u prosjeku morati čekati vrijeme jednako (jer „tok ispuštanja“ kanala ima intenzitet od ). Ako aplikacija pronađe sve kanale zauzete i jednu aplikaciju ispred nje u redu čekanja, morat će čekati u prosjeku određeno vrijeme (za svaku aplikaciju ispred) itd. Ako se aplikacija nađe u redu aplikacija , moraće da čeka u proseku neko vreme . Ako je novopristigla aplikacija već u redu čekanja m aplikacija, onda uopće neće čekati (ali neće biti uručene).
Prosječno vrijeme čekanja nalazimo množenjem svake od ovih vrijednosti sa odgovarajućim vjerovatnoćama:
(5.60)
Kao iu slučaju jednokanalnog QS-a sa čekanjem, napominjemo da se ovaj izraz od izraza za prosječnu dužinu reda (5.59) razlikuje samo po faktoru , tj.
Prosječno vrijeme boravka aplikacije u sistemu, isto kao i za jednokanalni SMO, razlikuje se od prosječnog vremena čekanja za prosječno vrijeme usluge pomnoženo relativnom propusnošću:
Sistemi sa neograničenom dužinom čekanja.
Razmatrali smo kanal QS sa čekanjem, kada ne više od m aplikacije.
Kao i do sada, pri analizi sistema bez ograničenja potrebno je uzeti u obzir dobijene relacije za .
Dobijamo vjerovatnoće stanja iz formula (5.56) prelaskom na granicu (na ). Imajte na umu da se zbir odgovarajuće geometrijske progresije konvergira na i divergira na > 1. Pod pretpostavkom da< 1 и устремив в формулах (5.56) величину m do beskonačnosti, dobijamo izraze za granične verovatnoće stanja:
(5.61)
Vjerovatnoća kvara, relativna i apsolutna propusnost. Budući da će svaki zahtjev prije ili kasnije biti servisiran, karakteristike QS propusnosti će biti:
Dobijamo prosječan broj aplikacija u redu na od (5.59):
a prosječno vrijeme čekanja je od (5.60):
Prosječan broj zauzetih kanala, kao i ranije, određuje se kroz apsolutnu propusnost:
Prosječan broj aplikacija povezanih s QS-om definiran je kao prosječan broj aplikacija u redu plus prosječan broj aplikacija u usluzi (prosječan broj zauzetih kanala):
Sve veća složenost struktura i načina realnih sistema otežava upotrebu klasičnih metoda teorije redova čekanja zbog sve veće dimenzije problema koji se rešavaju, što je posebno tipično za sisteme sa mrežnom strukturom. Jedan od mogućih načina za prevazilaženje dimenzionalnosti je korištenje modela u obliku mreža čekanja (Queuing).
SeMO je kolekcija konačnog broja servisnih čvorova u kojima kruže zahtjevi, krećući se u skladu s matricom rutiranja od jednog čvora do drugog. Čvor je uvijek otvoren SMO. Istovremeno, odvojeno SMO SMO- strukturu sistema i zahtjeve koji kruže SeMO, − komponente materijalnih tokova (poruke (paketi) u komunikacionoj mreži, zadaci u višeprocesorskim sistemima, kontejneri tokova tereta, itd.).
sa svoje strane, SeMO koristi se za određivanje najvažnijih sistemskih karakteristika informacionih sistema: produktivnost; vrijeme isporuke paketa; vjerovatnoća gubitka poruke i blokiranja u čvorovima; područja dozvoljenih vrijednosti opterećenja pri kojima se osigurava traženi kvalitet usluge itd.
U teoriji SeMO Koncept stanja mreže je fundamentalan. Najvažnija karakteristika mreža MO− vjerovatnoće njihovih stanja. Odrediti vjerovatnoće stanja SeMO istražiti slučajni proces koji se odvija u mreži. Kao modeli koji ulaze SeMO Markovski i polumarkovski procesi se takođe najčešće koriste.
3.3. Sistem čekanja kao model
1.5. Mreže čekanja
Markovljev proces s kontinuiranim vremenom opisuje funkcioniranje eksponencijala SeMO.
Mreža se zove eksponencijalna ako dolazni tokovi zahtjeva u svakom SMO Poisson, i vremena svake faze usluge implementirane u bilo kojem SMO mreže imaju eksponencijalna distribucija. Ovo nam omogućava da pretpostavimo da su faze usluge nezavisne jedna od druge i da ne zavise ni od parametara dolaznog toka, ni od stanja mreže, ni od ruta zahteva.
Teorija eksponencijala SeMO najrazvijeniji, i široko se koristi kako za proučavanje PD mreža tako i za proučavanje višeprocesora računarski sistemi (CS). Razvijene su praktične formule za proračun vjerovatno-vremenskih karakteristika (PTC) takvih mreža i sistema.
Pokušaji dubinske analize ne-Markovljevih modela mrežnih sistema nailaze na značajne poteškoće, koje su uzrokovane, posebno, nedostatkom neovisnosti o trajanju zadržavanja zahtjeva u različitim čvorovima modela mrežnih sistema sa nestandardnim disciplinama. Tako je, na primjer, uz prilično realnu pretpostavku da dužina zahtjeva ostaje konstantna tokom njegovog prijenosa kroz mrežne čvorove, potrebno je pratiti putanju svakog zahtjeva, što onemogućuje analitičko izračunavanje karakteristika mreže sa broj čvorova M>2.
Analiza radova posvećenih proučavanju ili proračunu ne-Markovljevih modela pokazuje da se rješenja, po pravilu, dobijaju algoritamskim putem složenih numeričkih proračuna korištenjem Laplace-Stieltjesovih transformacija, implementiraju se softverski, vrlo su radno intenzivna ili imaju značajne rezultate. greške u procjeni pokazatelja performansi informacionih sistema (IS) u oblasti srednjeg i velikog opterećenja. Dakle, za modeliranje SeMO, napuštajući klasu multiplikativnih, koriste približne metode.
Komparativna analiza metoda aproksimativnog modeliranja SeMO a prikazani primjeri pokazuju da je potrebno s velikim oprezom koristiti aproksimativne metode za izračunavanje SeMO, da se pri proračunu specifičnog SeMO, u procesu rješavanja različitih primijenjenih problema, čini neophodnim provesti istraživanja kako bi se ocijenila tačnost i osjetljivost korištene metode, kao i provesti simulacijski eksperiment originalnog SeMO za dovoljno veliki skup vrijednosti različitih parametara.
Analitičke metode za proračun karakteristika IS baziraju se po pravilu na analizi eksponencijalnog CeMO. Koristeći ovaj matematički aparat moguće je dobiti analitičke modele za rješavanje širokog spektra problema u proučavanju sistema. SeMO je, prije svega, skup međusobno povezanih sistema čekanja. Stoga je potrebno podsjetiti na glavne karakteristike ovih sistema.
Mreža čekanja predstavlja kolekciju konačnih brojeva N uslužni čvorovi, u kojima kruže zahtjevi, krećući se u skladu sa matricom rutiranja od jednog čvora do drugog. Čvor je uvijek otvoreni QS (a QS može biti bilo koje klase). Istovremeno, odvojeno SMO prikaz funkcionalno nezavisnih delova realnog sistema, veze između SMO- strukturu sistema i zahtjeve koji kruže SeMO,- komponente materijalnih tokova (poruke (paketi) u komunikacionoj mreži, zadaci u višeprocesorskim sistemima, kontejneri tokova tereta, itd.).
Za vizuelno predstavljanje SeMO koristi se graf čiji vrhovi (čvorovi) odgovaraju pojedinim SMO, a lukovi prikazuju veze između čvorova.
Tranzicija aplikacija između čvorova se dešava trenutno u skladu sa vjerovatnoćama tranzicije 
, p ij- vjerovatnoća da zahtjev nakon servisiranja u čvoru iće ići na čvor j. Naravno, ako čvorovi nisu direktno povezani jedan s drugim, onda p ij= 0. Ako je od ja- tranzicija čvora na samo jedan čvor j, To p ij= 1.
SeMO klasifikovane prema nekoliko kriterijuma (slika 4).
Mreža se zove linearno, ako su intenziteti tokova aplikacija u čvorovima međusobno povezani linearnim odnosom
l j= a ij l i,
gdje a ij- koeficijent proporcionalnosti, ili u odnosu na izvor
l j= a j l 0 ,.
Koeficijent a j nazvan koeficijent prijenosa, on karakterizira udio primljenih prijava u j- th čvor iz izvora aplikacija, ili - prosječan broj puta da aplikacija prođe kroz ovaj čvor za vrijeme dok je aplikacija u mreži.
Ako su intenziteti tokova aplikacija u mrežnim čvorovima povezani nelinearnim odnosom (na primjer, 
), tada se poziva mreža nelinearni..
Mreža je uvijek linearna ako se aplikacije u njoj ne izgube ili umnože.
Otvori Mreža je otvorena mreža u koju zahtjevi dolaze iz vanjskog okruženja i ostavljaju mrežu u vanjsko okruženje nakon servisiranja. Drugim riječima, karakteristika otvorene petlje SeMO(RSeMO) je prisustvo jednog ili više nezavisnih eksternih izvora koji generišu aplikacije koje ulaze u mrežu, bez obzira na to koliko je aplikacija već u mreži. U bilo koje vrijeme u RSeMO može postojati proizvoljan broj aplikacija (od 0 do ¥).
Rice. 4. Klasifikacija mreža čekanja
IN zatvoren SeMO (ZSeMO) kruži fiksni broj aplikacija i ne postoji vanjski nezavisni izvor. Na osnovu fizičkih razmatranja, u ZSeM O vanjskom luku je odabrano, na kojem je označeno pseudo-nula tačka u odnosu na koju se mogu meriti vremenske karakteristike.
Kombinovano mreža je mreža u kojoj stalno cirkuliše određeni broj aplikacija i postoje aplikacije koje dolaze iz vanjskih nezavisnih izvora.
IN homogena aplikacije iste klase kruže u mreži. I obrnuto, u heterogena mreže mogu sadržavati aplikacije nekoliko klasa. Aplikacije pripadaju različitim klasama ako se razlikuju u barem jednom od sljedećih atributa:
Zakon raspodjele trajanja usluge u čvorovima;
Prioriteti;
Rute (putevi kretanja zahtjeva u mreži).
IN eksponencijalna mreže trajanja usluge u svim čvorovima su raspoređene prema eksponencijalnom zakonu, a tokovi koji ulaze u mrežu otvorene petlje su jednostavni (Poisson). U svim ostalim slučajevima mreža jeste neeksponencijalna.
Ako je prioritetna usluga pružena u barem jednom čvoru, onda je to - prioritet net. Prioritet je znak koji određuje redosled usluge. Ako se servisiranje zahtjeva u čvorovima vrši po redoslijedu prijema, onda je takva mreža bez prioriteta.
Stoga ćemo nazvati eksponencijalnim SeMO, ispunjava uslove:
Ulazni tokovi SeMO Poisson;
U svemu N SMO vrijeme servisiranja zahtjeva ima funkciju eksponencijalne distribucije vjerovatnoće, a zahtjevi se servisiraju po redoslijedu dolaska;
Prijenos aplikacije sa izlaza i th SMO na ulazu j- je nezavisan slučajni događaj sa vjerovatnoćom p ij ; p i0- vjerovatnoća da aplikacija napusti CeMO.
Ako aplikacije dođu u mrežu i napuste je, tada se mreža naziva otvorena. Ako aplikacije ne ulaze ili ne izlaze iz mreže, mreža se naziva zatvorena. Broj aplikacija u zatvorenoj mreži je konstantan.
