Modeli sustava čekanja. Matematički modeli najjednostavnijih sustava čekanja

Chetverikov S. Yu., Popov M.A.

Rusija, Institut za ekonomiju i poduzetništvo (Moskva)

Teorija sustava čekanja je primijenjena matematička disciplina koja istražuje numeričke karakteristike pojave koje se događaju u gospodarstvu. To uključuje rad telefonske centrale, centara za potrošačke usluge, blagajne u supermarketu itd.

Matematički modeli takvih objekata su sustavi čekanja (QS) koji se opisuju na sljedeći način: zahtjevi (aplikacije za uslugu) ulaze u sustav, od kojih se svaki neko vrijeme servisira i zatim napušta sustav. Međutim, zbog ograničenosti resursa (broj blagajni koje se poslužuju, brzina usluge i sl.), sustav je u mogućnosti opsluživati ​​samo određeni broj potraživanja u isto vrijeme. Matematički modeli u ovom slučaju dizajnirani su za rješavanje problema izračuna numeričkih pokazatelja kvalitete funkcioniranja QS-a.

Pri konstruiranju QS modela temeljno se razlikuju dva sustava: deterministički i stohastički, koji zapravo određuju vrstu matematičkog modela.

Razmotrimo najjednostavniji deterministički sustav koji se sastoji od P identične uređaje, kod kojih zahtjevi pristižu u determinističkim (konstantnim) vremenskim intervalima, a vrijeme servisiranja svakog zahtjeva također je konstantno. Očito je da ako zahtjevi stižu u intervalima

a vrijeme usluge za svaki zahtjev je

tada je nužan i dovoljan uvjet za normalno funkcioniranje sustava ispunjenje nejednakosti

Inače će se s vremenom zahtjevi akumulirati u sustavu.

Mogućnosti x i q imaju jednostavno fizičko značenje:

x- prosječan broj pristiglih zahtjeva u jedinici vremena ili intenzitet dolaznog toka;

q je prosječan broj zahtjeva koje svaki uređaj može ispuniti u jedinici vremena, odnosno intenzitet zahtjeva servisiranja po jednom uređaju;

/ 7ts - prosječan broj zahtjeva koji mogu poslužiti P uređaja ili zahtjeva intenziteta održavanja cijelog sustava.

Dakle, uvjet (1) znači da intenzitet dolaznog toka ne smije premašiti intenzitet zahtjeva opsluživanja od strane cijelog sustava. Uzmite u obzir količinu

Takozvano pokretanje sustava.

Tada se nejednakost (1) može prepisati kao:

U ovom slučaju, opterećenje se može tumačiti kao prosječni udio vremena tijekom kojeg su uređaji zauzeti servisiranjem zahtjeva, a vrijednost 1 - p - kao prosječni udio vremena tijekom kojeg uređaji miruju.

Na kraju, još jedna napomena o funkcioniranju sustava s determinističkim karakteristikama:

ako je u početnom trenutku sustav slobodan i zadovoljen uvjet (2), tada svaki zahtjev koji uđe u sustav odmah postaje servisni uređaj;

u slučaju str

konačno, ako je p > 1, tada se po jedinici vremena red u prosjeku povećava za Mr-1).

U stvarnim sustavima čekanja elementi slučajnosti igraju značajnu ulogu:

prvo, vremena između pristizanja zahtjeva nisu deterministička;

drugo, vremena usluge zahtjeva nisu deterministička.

Osim toga, elementi slučajnosti mogu se pojaviti zbog drugih razloga, na primjer, kvarova elemenata sustava čekanja.

Pokazalo se da elementi slučajnosti značajno utječu na kvalitetu funkcioniranja uslužnih sustava. Dakle, ako je opterećenje p = 1, tada, za razliku od determinističkih sustava, u stohastičkim sustavima red čekanja tijekom vremena u prosjeku teži beskonačnosti. Redovi u stohastičkim sustavima nastaju čak iu slučaju p

Razmotrimo formalizirani opis QS-a. Glavni parametri QS-a su:

dolazni tok zahtjeva;

struktura sustava;

vremenske karakteristike zahtjeva usluge;

disciplina službe.

Pogledajmo ove opcije.

Dolazni tok karakteriziraju slučajni trenuci prijema zahtjeva u jednostavnom sustavu, a za složene sustave - vrste zahtjeva koji stižu u tim trenucima.

Kada se specificira slučajni tok, obično se pretpostavlja da je ulazni tok rekurentan i najčešće Poissonov.

Napravimo neke napomene o ispravnosti opisa tokova zahtjeva koji ulaze u realne sustave od strane Poissona i onih koji se ponavljaju. Očito je svojstvo odsutnosti naknadnog učinka u stvarnim sustavima izuzetno rijetko, budući da tijek s takvim svojstvom može primiti proizvoljno velik broj zahtjeva s različitom od nule (iako iznimno malom) vjerojatnošću u bilo kojem proizvoljno malom vremenskom razdoblju. Međutim, praksa pokazuje da je Poissonov opis dolaznog toka u većini slučajeva legitiman s dovoljnim stupnjem točnosti. Dodatna matematička potvrda ove činjenice je Khinchinov teorem, koji kaže da unija velikog broja "rijetkih" tokova pod vrlo slabim ograničenjima daje Poissonov tok.

Drugo svojstvo Poissonovog toka - stacionarnost - također ne izaziva kritiku. Doista, intenzitet dolaznog protoka, u pravilu, ovisi o dobu dana, godini i tako dalje. Ako se očuvaju svojstva odsutnosti naknadnog djelovanja i običnosti, tada se dobiva nestacionarno Poissonovo strujanje. U nekim slučajevima moguće je razviti matematičke modele za izračunavanje ekonomski sustavi s takvim dolaznim protokom, ali rezultirajuće formule su vrlo glomazne i teške za praktična aplikacija. Zbog toga su proračuni ograničeni na određeni vremenski interval u kojem se intenzitet nadolazećeg toka malo mijenja.

Ako se napusti samo svojstvo običnosti, tada se dobiva neuobičajeni Poissonov tok, u kojem trenuci dolaska zahtjeva tvore obični Poissonov tok, ali u svakom takvom trenutku dolazi slučajan broj zahtjeva. Većina rezultata koji vrijede za sustave s Poissonovim strujanjem prenosi se praktički nepromijenjena na sustave s neuobičajenim Poissonovim strujanjem.

Za postavljanje QS strukture potrebno je navesti sve elemente koji su dostupni u sustavu i naznačiti koje vrste zahtjeva ili čak u kojim fazama usluge svaki element može poslužiti. U ovom slučaju, jedan element može služiti zahtjevima nekoliko vrsta i, obrnuto, zahtjevi iste vrste mogu biti posluženi na nekoliko elemenata. U nastavku ćemo pretpostaviti da QS ima jedan ili više identičnih elemenata, a svaki zahtjev se može ispuniti na bilo kojem od njih. Sustavi ove vrste nazivaju se jedna linija(jedan element) ili višelinijski(više stavki).

Sustavi usluga mogu imati elemente za zahtjeve za čekanje početka usluge. Ako takvih elemenata ima beskonačno mnogo, onda se govori o sustavima s čekanjem, ako je njihov broj konačan - o sustavima s konačnim brojem mjesta za čekanje, ako ih uopće nema (zahtjev koji je činio da su svi elementi zauzeti u trenutku ulaza u sustav se gubi; primjer su obični telefonski sustavi) - o sustavima s gubicima.

Vrijeme zahtjevi usluge su također složeni objekt za formalizirani opis. Obično se pretpostavlja da su vremena usluge svih kupaca neovisna jedna o drugoj i da su jednako raspoređene slučajne varijable. Ako QS prima zahtjeve više vrsta, raspodjela vremena usluge može ovisiti o vrsti zahtjeva.

Disciplina servisa sastoji se od pravila čekanja zahtjeva i redoslijeda njihovog odabira iz reda za uslugu, raspodjele elemenata između zahtjeva, au višefaznim sustavima – između faza usluge. Pretpostavit ćemo da je u sustav implementirana najjednostavnija disciplina - servisiranje zahtjeva po redu prispjeća (FIFO). U višelinijskim sustavima formira se zajednički red za sve elemente, a prvi zahtjev u redu ide svakom oslobođenom elementu.

Međutim, QS također koristi složenije servisne discipline. Najjednostavniji primjeri takvih disciplina su inverzni (obrnuti) poredak usluge (LIFO), u kojem se servisira zahtjev koji je zadnji ušao u sustav.

Disciplina ravnomjernog odvajanja elemenata sustava, u kojoj svaki od P zahtjevi u sustavu servisiraju se istom brzinom 1/str. Ponekad, u trenutku kada zahtjev uđe u sustav, postaje poznato vrijeme njegove usluge (posao koji treba obaviti). Tada je moguće koristiti discipline koje ovise o preostalom vremenu servisiranja zahtjeva. Konkretno, disciplina posluživanja prvog zahtjeva uz minimalno preostalo vrijeme usluge omogućuje vam da dobijete minimalnu duljinu čekanja u bilo kojem trenutku. Korištenje složenih uslužnih disciplina vrlo često omogućuje, bez ikakvih dodatnih troškova, značajno poboljšanje kvalitete funkcioniranja QS-a.

Posebna klasa QS-ova su sustavi prioriteta koji primaju tokove zahtjeva nekoliko prioriteta, a zahtjevi višeg prioriteta imaju prednost nad zahtjevima nižeg prioriteta, tj. služio ranije. Prioriteti mogu biti relativni, kada zahtjevi višeg prioriteta ne prekidaju usluge zahtjeva nižeg prioriteta na elementima, i apsolutni, kada se takav prekid dogodi.

U slučaju apsolutnih prioriteta također su moguće različite modifikacije: nedovoljno opsluženi korisnici s prekinutom uslugom napuštaju sustave (sustavi s ispadanjem), nastavljaju se servisirati nakon što svi korisnici višeg prioriteta napuste sustav (sustavi s naknadnom skrbi), te se ponovno servisiraju.

Uslužne discipline također bi trebale uključivati ​​takve čimbenike kao što je pripremna faza prije početka servisiranja sljedećeg zahtjeva ili nakon što je zahtjev stigao u slobodni sustav, faza prebacivanja elementa na servisne zahtjeve druge vrste, zahtjevi servisiranja nepouzdanim elementima sustav, itd. Konačno, količina vremena koju zahtjev provede u sustavu ili vrijeme potrebno za čekanje na početak usluge može se ograničiti.

Opišimo sada one QS karakteristike koje su od interesa za korisnika. Ponekad se u praksi nazivaju vjerojatnosno-vremenske karakteristike. Najvažniji od njih su duljina čekanja(tj. broj zahtjeva koji čekaju na uslugu) i vrijeme čekanja za početak posluživanja zahtjeva. Budući da su i duljina reda i vrijeme čekanja na početak usluge slučajne varijable, onda su, naravno, opisane vlastitim distribucijama. Osim toga, raspodjele duljine reda i vremena čekanja ovise o trenutnom vremenu.

U sustavima s gubicima ili konačnim brojem mjesta čekanja, najvažnije karakteristike također uključuju vjerojatnost gubitka potraživanja. Ponekad, uz duljinu čekanja, uzimaju u obzir ukupan broj zahtjeva u sustavu, i zajedno s uslugom počinje vrijeme čekanja - vrijeme zadržavanja zahtjeva u sustavu.

U sustavima s gubicima ili konačnim brojem mjesta čekanja, kao i u sustavima s čekanjem i opterećenjem p

Većina radova o teoriji čekanja posvećena je pronalaženju stacionarnih karakteristika, iako su nestacionarne karakteristike proučene dovoljno detaljno.

Književnost

• 1. Gnedenko B.V. Tečaj vjerojatnosti. Moskva: Fizmatgiz, 1961.
• 2. Feller V. Uvod u teoriju vjerojatnosti i njezine primjene.T.I. M.: Mir,
• 1984.
• 3. Gnedenko B.V., Kovalenko I.N. Uvod u teoriju čekanja. Moskva: Nauka, 1966.
• 4. Saaty T.L. Elementi teorije čekanja i njezine primjene. M.: Sov. radio, 1965.

Razmatran u prethodnom predavanju, Markovljev slučajni proces s diskretnim stanjima i kontinuiranim vremenom odvija se u sustavima čekanja (QS).

Sustavi čekanja - to su sustavi u kojima se servisni zahtjevi primaju u nasumičnim razdobljima, dok se primljeni zahtjevi servisiraju korištenjem servisnih kanala koji su sustavu dostupni.

Primjeri sustava čekanja su:

• poravnanje i gotovinski čvorovi u bankama, poduzećima;
• osobnih računala, posluživanje dolaznih zahtjeva ili zahtjeva za rješavanje određenih problema;
• servisne stanice za automobile; benzinska postaja;
• revizorske tvrtke;
• odjeli poreznih inspekcija uključeni u prihvaćanje i provjeru tekućeg izvješćivanja poduzeća;
• telefonske centrale itd.

	Čvorovi	Zahtjevi
Bolnica	bolničari	Pacijenti
Proizvodnja
Zračna luka	Izlazi s piste Točke registracije	Putnici

Razmotrite shemu rada QS-a (slika 1). Sustav se sastoji od generatora zahtjeva, dispečera i servisnog čvora, čvora za obračun kvarova (terminator, razarač zahtjeva). Servisni čvor u opći slučaj može imati više servisnih kanala.

Riža. jedan

1. Generator aplikacija – objekt koji generira aplikacije: ulica, radionica s instaliranim jedinicama. Ulaz je tijek primjene(protok kupaca u trgovinu, protok pokvarenih jedinica (automobila, alatnih strojeva) za popravke, protok posjetitelja u garderobu, protok automobila na benzinske postaje itd.).
2. Dispečer – osoba ili uređaj koji zna što učiniti s kartom. Čvor koji regulira i usmjerava zahtjeve prema servisnim kanalima. Dispečer:

• prima prijave;
• formira red ako su svi kanali zauzeti;
• upućuje ih na servisne kanale, ako postoje;
• odbija prijave (iz raznih razloga);
• prima informacije od servisnog čvora o slobodnim kanalima;
• prati vrijeme sustava.

1. Skretanje - zahtjev akumulator. Red možda ne postoji.
2. Servisni čvor sastoji se od konačnog broja uslužnih kanala. Svaki kanal ima 3 stanja: slobodan, zauzet, neaktivan. Ako su svi kanali zauzeti, onda možete smisliti strategiju kome prebaciti aplikaciju.
3. Odbijanje iz usluge se javlja ako su svi kanali zauzeti (neki od njih možda neće raditi).

Osim ovih osnovnih elemenata u QS-u, neki izvori razlikuju i sljedeće komponente:

terminator - razarač transakcija;

skladište - skladište resursa i gotovih proizvoda;

računovodstveni račun - za obavljanje poslova tipa "knjiženje";

manager - upravitelj resursa;

CMO klasifikacija

Prva podjela (prema prisutnosti redova):

• CMO s neuspjesima;
• CMO s redom čekanja.

NA CMO s neuspjesima zahtjev koji stigne u trenutku kada su svi kanali zauzeti biva odbijen, napušta QS i ne služi se dalje.

NA CMO s redom čekanja aplikacija koja stigne u trenutku kada su svi kanali zauzeti ne odlazi, već stoji u redu i čeka priliku da bude poslužena.

QS s redovima podijeljeno na različiti tipovi ovisno o tome kako je red organiziran - ograničeno ili neograničeno. Ograničenja se mogu odnositi i na duljinu reda i na vrijeme čekanja, "disciplinu usluživanja".

Tako se, na primjer, razmatraju sljedeći QS:

• QS s nestrpljivim zahtjevima (duljina čekanja u redu i vrijeme usluge su ograničeni);
• QS s prioritetnom uslugom, tj. neke se aplikacije poslužuju izvan reda, itd.

Vrste ograničenja čekanja mogu se kombinirati.

Druga klasifikacija dijeli CMO prema izvoru aplikacija. Sam sustav ili neko vanjsko okruženje koje postoji neovisno o sustavu može generirati aplikacije (zahtjeve).

Naravno, tok zahtjeva koje generira sam sustav ovisit će o sustavu i njegovom stanju.

Osim toga, SMO se dijele na otvorena CMO i zatvoreno SMO.

U otvorenom QS-u karakteristike tijeka aplikacija ne ovise o stanju samog QS-a (koliko je kanala zauzeto). U zatvorenom QS-u ovise. Na primjer, ako jedan radnik servisira grupu strojeva koji s vremena na vrijeme zahtijevaju podešavanje, tada intenzitet protoka "zahtjeva" od strojeva ovisi o tome koliko ih je već u ispravnom stanju i čeka na podešavanje.

Primjer zatvorenog sustava: izdavanje plaće od strane blagajnika u poduzeću.

Prema broju kanala QS se dijele na:

• jednokanalni;
• višekanalni.

Karakteristike sustava čekanja

Glavne karakteristike sustava čekanja bilo koje vrste su:

• ulazni tok dolaznih zahtjeva ili zahtjeva za uslugama;
• disciplina čekanja;
• servisni mehanizam.

Ulazni tok zahtjeva

Da biste opisali ulazni tok, morate postaviti vjerojatnosni zakon koji određuje redoslijed trenutaka primitka zahtjeva za uslugom, te u svakoj redovnoj potvrdi naznačiti broj takvih tražbina. U ovom slučaju, u pravilu, operiraju s konceptom "probabilističke distribucije trenutaka primitka zahtjeva". Ovdje se možete ponašati kao pojedinačne i grupne zahtjeve (broj takvih tražbina u svakom sljedećem primitku). U potonjem slučaju obično pričamo o sustavu čekanja s uslugom paralelne grupe.

A i– vrijeme dolaska između zahtjeva – nezavisne identično raspoređene slučajne varijable;

E(A) je srednje (MO) vrijeme dolaska;

λ=1/E(A)- intenzitet zaprimanja zahtjeva;

Karakteristike ulaznog toka:

1. Vjerojatni zakon koji određuje redoslijed trenutaka prijema zahtjeva usluge.
2. Broj zahtjeva u svakom sljedećem dolasku za multicast tokove.

Disciplina čekanja

Skretanje - skup zahtjeva koji čekaju na servis.

Red čekanja ima ime.

Disciplina čekanja određuje princip prema kojem se zahtjevi pristigli na ulaz servisnog sustava povezuju iz reda čekanja na servisnu proceduru. Najčešće korištene discipline čekanja definirane su sljedećim pravilima:

• prvi dodje prvi je posluzen;

prvi ušao prvi izašao (FIFO)

najčešći tip reda čekanja.

Koja je struktura podataka prikladna za opisivanje takvog reda? Niz je loš (ograničen). Možete koristiti strukturu LIST.

Lista ima početak i kraj. Popis se sastoji od unosa. Unos je ćelija popisa. Aplikacija dolazi na kraj liste, a odabire se za uslugu s početka liste. Unos se sastoji od opisa aplikacije i linka (indeksa tko stoji iza nje). Osim toga, ako red čekanja ima vremensko ograničenje, tada i vremensko ograničenje mora biti navedeno.

Vi, kao programeri, trebali biste moći napraviti popise dvostrane, jednostrane.

Popis radnji:

• umetnite u rep;
• uzeti od početka;
• ukloniti s popisa nakon isteka vremena.
• posljednji dođe, prvi poslužen LIFO (spajalica, slijepa ulica na željezničkoj stanici, ušao u pun auto).

Struktura poznata kao STAK. Može se opisati strukturom polja ili liste;

• slučajni odabir aplikacija;
• selekcija prijava prema kriteriju prvenstva.

Svaka aplikacija se, između ostalog, odlikuje razinom prioriteta i po dolasku se ne postavlja na rep reda, već na kraj svoje prioritetne grupe. Dispečer sortira po prioritetu.

Karakteristike reda čekanja

• ograničenjevrijeme čekanja trenutak usluge (postoji red sa ograničeno vrijemečekanje usluge, što je povezano s konceptom "dopuštene duljine čekanja");
• duljina čekanja.

Servisni mehanizam

Servisni mehanizam određena je karakteristikama samog uslužnog postupka i strukturom uslužnog sustava. Servisni postupci uključuju:

• broj servisnih kanala ( N);
• trajanje servisnog postupka (probabilistička raspodjela servisnog vremena zahtjeva);
• broj zahtjeva koji su zadovoljeni kao rezultat provedbe svakog takvog postupka (za grupne prijave);
• vjerojatnost kvara kanala za posluživanje;
• struktura uslužnog sustava.

Za analitički opis karakteristika uslužnog postupka koristi se koncept "probabilističke distribucije vremena usluge zahtjeva".

Si– vrijeme usluge ja th zahtjev;

E(S)– prosječno vrijeme usluge;

μ=1/E(S)- zahtjevi za brzinom usluge.

Treba napomenuti da vrijeme servisiranja aplikacije ovisi o prirodi same aplikacije ili zahtjevima klijenta te o stanju i mogućnostima servisnog sustava. U nekim slučajevima također je potrebno uzeti u obzir vjerojatnost kvara servisnog kanala nakon određenog ograničenog vremenskog intervala. Ova se karakteristika može modelirati kao tok kvarova koji ulaze u QS i imaju prioritet nad svim drugim aplikacijama.

QS faktor iskorištenja

Nμ – brzina usluge u sustavu kada su svi servisni uređaji zauzeti.

ρ=λ/( Nμ) se zove QS faktor iskorištenja , pokazuje koliko se resursa sustava koristi.

Struktura uslužnog sustava

Struktura uslužnog sustava određena je brojem i međusobni dogovor uslužnih kanala (mehanizama, uređaja i sl.). Prije svega, treba naglasiti da uslužni sustav ne može imati jedan uslužni kanal, već nekoliko; sustav ove vrste može zadovoljiti nekoliko zahtjeva istovremeno. U ovom slučaju, svi kanali usluga nude iste usluge i, stoga, može se tvrditi da postoji paralelna usluga .

Primjer. Blagajne u trgovini.

Servisni sustav se može sastojati od nekoliko različitih vrsta servisnih kanala kroz koje mora proći svaki servisirani zahtjev, tj. u servisnom sustavu procedure servisiranja zahtjeva implementiraju se sekvencijalno . Servisni mehanizam definira karakteristike odlaznog (serviranog) toka zahtjeva.

Primjer. Liječnička komisija.

Kombinirana usluga - servisiranje uloga u štedionici: prvo kontrolor, zatim blagajnik. U pravilu 2 kontrolora po blagajniku.

Tako, funkcionalnost bilo kojeg sustava čekanja određuju sljedeći glavni čimbenici :

• probabilistička raspodjela trenutaka zaprimanja servisnih zahtjeva (pojedinačnih ili grupnih);
• kapacitet izvora zahtjeva;
• probabilistička distribucija vremena trajanja usluge;
• konfiguracija servisnog sustava (paralelna, serijska ili paralelno-serijska usluga);
• broj i izvedba kanala za posluživanje;
• disciplina čekanja.

Glavni kriteriji učinkovitosti funkcioniranja QS-a

Kao glavni kriteriji učinkovitosti funkcioniranja sustava čekanja Ovisno o prirodi problema koji se rješava, može postojati:

• vjerojatnost trenutne dostave zaprimljene prijave (P usluga =K obs /K post);
• vjerojatnost odbijanja usluge primljene aplikacije (P otk =K otk /K post);

Očito je R obl + P otk =1.

Protoci, kašnjenja, usluga. Pollacek–Khinchinova formula

Odgoditi – jedan od kriterija QS usluge, vrijeme koje je zahtjev proveo u iščekivanju usluge.

D i– kašnjenje u redu zahtjeva ja;

W i \u003d D i + S i– vrijeme provedeno u sustavu zahtjeva ja.

(s vjerojatnošću 1) je utvrđeno prosječno kašnjenje zahtjeva u redu čekanja;

(s vjerojatnošću 1) je prosječno vrijeme u stabilnom stanju koje zahtjev provede u QS-u (čekanje).

Q(t) - broj zahtjeva u redu u jednom trenutku t;

L(t)– broj kupaca u sustavu u jednom trenutku t(Q(t) plus broj zahtjeva koji su u upotrebi u to vrijeme t.

Zatim eksponenti (ako postoje)

(s vjerojatnošću 1) je stacionarni vremenski prosječni broj zahtjeva u redu čekanja;

(s vjerojatnošću 1) je stalni vremenski prosječni broj zahtjeva u sustavu.

Imajte na umu da je ρ<1 – обязательное условие существования d, w, Q i L u sustavu čekanja.

Ako se sjetimo da je ρ= λ/( Nμ), onda je jasno da ako je intenzitet zaprimanja zahtjeva veći od Nμ, tada je ρ>1, te je prirodno da sustav neće moći podnijeti toliki protok aplikacija, pa se ne može govoriti o d, w, Q i L.

Najopćenitiji i najpotrebniji rezultati za sustave čekanja uključuju jednadžbe očuvanja

Treba napomenuti da se gornji kriteriji za ocjenu performansi sustava mogu analitički izračunati za sustave čekanja M/M/N(N>1), tj. sustavi s Markovljevim tokovima kupaca i usluge. Za M/G/ l za bilo koju distribuciju G i za neke druge sustave. Općenito, distribucija vremena između dolazaka, distribucija vremena usluge ili obje moraju biti eksponencijalne (ili neka vrsta eksponencijalne Erlangove distribucije k-tog reda) da bi analitičko rješenje bilo moguće.

Osim toga, možete govoriti o takvim karakteristikama kao što su:

• apsolutna propusnost sustava – A=R usluga *λ;
• relativna propusnost sustava -

Još jedan zanimljiv (i ilustrativan) primjer analitičkog rješenja – izračun prosječnog kašnjenja u stacionarnom stanju za sustav čekanja M/G/ 1 prema formuli:

.

U Rusiji je ova formula poznata kao Pollacek formula. – Khinchin, u inozemstvu se ova formula povezuje s imenom Ross.

Dakle, ako E(S) Ima veću vrijednost, zatim preopterećenje (in ovaj slučaj mjereno kao d) bit će veći; što je i za očekivati. Formula također otkriva manje očitu činjenicu: zagušenje se također povećava kada se povećava varijabilnost u distribuciji vremena usluge, čak i ako prosječno vrijeme usluge ostaje isto. Intuitivno se to može objasniti na sljedeći način: varijanca slučajne varijable vremena usluge može trajati veliki značaj(jer mora biti pozitivan), tj. jedini uređaj za posluživanje će biti zauzet Dugo vrijeme, što će povećati red.

Predmet teorije čekanja je utvrditi odnos između faktora koji određuju funkcionalnost sustava čekanja i učinkovitosti njegovog funkcioniranja. U većini slučajeva, svi parametri koji opisuju sustave čekanja su slučajne varijable ili funkcije, pa se ti sustavi nazivaju stohastičkim sustavima.

Slučajna priroda toka zahtjeva (zahtjeva), kao i, općenito, trajanje usluge dovodi do toga da se u sustavu čekanja događa slučajni proces. Po prirodi slučajnog procesa koji se javljaju u sustavu čekanja (QS) razlikuju se Markovljevi i nemarkovski sustavi . U Markovljevim sustavima, dolazni tok zahtjeva i odlazni tok servisiranih zahtjeva (potraživanja) su Poissonovi. Poissonovi tokovi olakšavaju opisivanje i izgradnju matematičkog modela sustava čekanja. Ovi modeli imaju dovoljno jednostavna rješenja, tako da većina poznatih primjena teorije čekanja koristi Markovljevu shemu. U slučaju ne-Markovljevih procesa, problemi proučavanja sustava čekanja postaju mnogo kompliciraniji i zahtijevaju korištenje statističkog modeliranja, numeričkih metoda pomoću računala.

U praksi ljudskog djelovanja veliko mjesto zauzimaju procesi čekanja koji se javljaju u sustavima dizajniranim za višekratnu upotrebu u rješavanju iste vrste problema. Takvi sustavi nazivaju se sustavi čekanja (QS). Primjeri takvih sustava su telefonski sustavi, računalni sustavi, automobilski, zrakoplovni, sustavi održavanja, trgovine, blagajne i slično.

Svaki sustav se sastoji od određenog broja servisnih jedinica (instrumenata, uređaja, uređaja "točaka, stanica), koje se nazivaju servisni kanali. Prema broju kanala QS se dijeli na jednokanalne i višekanalne. Dijagram jednokanalnog sustava čekanja prikazan je na sl. 6.2.

Aplikacije obično ne ulaze u sustav redovno, već nasumično, tvoreći slučajni tijek aplikacija (zahtjeva). Sama usluga svakog zahtjeva može trajati ili određeno vrijeme, ili, češće, neodređeno vrijeme. Slučajna priroda dovodi do činjenice da je QS neravnomjerno opterećen: u nekim vremenskim razdobljima nakuplja se vrlo veliki broj aplikacije (dođu u red ili ostave QS neposlužen), dok u ostalim razdobljima QS radi pod opterećenjem ili je u stanju mirovanja.

Riža. 6.2.

Svrha proučavanja sustava čekanja je analiza kvalitete njihova funkcioniranja i prepoznavanje mogućnosti za njegovo poboljšanje. Istodobno, koncept "kvalitete funkcioniranja" u svakom pojedinom slučaju imat će svoj vlastiti specifično značenje i izraženo u različitim kvantitativnim izrazima. Na primjer, kvantitativni pokazatelji kao što su veličina reda za uslugu, prosječno vrijeme usluge, čekanje na uslugu ili pronalaženje zahtjeva u sustavu usluge, vrijeme mirovanja servisnih uređaja; povjerenje da će svi zahtjevi koje sustav primi biti usluženi.

Dakle, kvaliteta funkcioniranja sustava čekanja nije shvaćena kao kvaliteta obavljanja određenog posla, čiji je zahtjev primljen, već stupanj zadovoljenja potrebe za uslugom.

Predmet teorije čekanja je konstrukcija matematičkih modela koji povezuju zadane uvjete rada QS-a (broj kanala, njihovu izvedbu, prirodu toka aplikacija itd.) s pokazateljima učinkovitosti QS-a, koji opisuju njegovu sposobnost da se nosi s protokom aplikacija.

Klasifikacija sustava čekanja

Prva značajka koja omogućuje klasificiranje zadataka čekanja je ponašanje zahtjeva koje prima sustav za posluživanje u trenutku kada su svi strojevi zauzeti.

U nekim slučajevima, zahtjev koji uđe u sustav u trenutku kada su svi strojevi zauzeti ne može čekati da budu otpušteni i ostavlja sustav neopsluženim, tj. zahtjev je izgubljen za dani sustav posluživanja. Takvi servisni sustavi nazivaju se sustavi s gubicima, a problemi formulirani na njihovoj osnovi nazivaju se servisni problemi za sustave s gubicima.

Ako pak zahtjev, ušavši u sustav, ulazi u red čekanja i čeka da se uređaj oslobodi, tada se takvi sustavi nazivaju sustavima s čekanjem, a odgovarajući zadaci servisnim zadacima u sustavima s čekanjem. QS s čekanjem dijeli se na različite vrste ovisno o tome kako je red organiziran: s ograničenom ili neograničenom dužinom reda, s ograničenim vremenom čekanja itd.

QS-ovi se također razlikuju po broju zahtjeva koji mogu istovremeno biti u sustavu posluživanja. Dodijeliti:

• 1) sustavi s ograničenim protokom zahtjeva;
• 2) sustavi s neograničenim protokom zahtjeva.

Ovisno o oblicima unutarnja organizacija usluge u sustavu su:

• 1) sustavi s naručenim servisom;
• 2) sustavi s neuređenim servisom.

Važan korak u proučavanju QS-a je izbor kriterija koji karakteriziraju proces koji se proučava. Izbor ovisi o vrsti problema koji se proučavaju, o cilju kojem se rješenje teži.

Najčešće u praksi postoje sustavi u kojima je tijek zahtjeva blizak najjednostavnijem, a vrijeme servisiranja slijedi eksponencijalni zakon raspodjele. Ovi sustavi su najpotpunije razvijeni u teoriji čekanja.

U uvjetima poduzeća tipični su zadaci s čekanjem, s konačnim brojem servisnih uređaja, s ograničenim protokom zahtjeva i s neuređenim servisiranjem.

Tijekom proteklih desetljeća, na raznim područjima Nacionalna ekonomija pojavila se potreba rješavanja probabilističkih problema vezanih uz rad sustava čekanja. Primjeri takvih sustava su telefonske centrale, radionice za popravak, maloprodajna mjesta, uredi za prodaju karata i tako dalje. rad bilo kojeg sustava čekanja sastoji se od servisiranja dolaznog toka zahtjeva (pozivi pretplatnika, protok kupaca do trgovine, zahtjevi za rad u radionici itd.).
Matematička disciplina koja proučava modele realnih sustava čekanja zove se teorija čekanja. Zadatak teorije čekanja je utvrditi ovisnost rezultirajućih pokazatelja performansi sustava čekanja (vjerojatnost da će zahtjev biti ispunjen; matematičko očekivanje broja opsluženih zahtjeva itd.) o ulaznim pokazateljima (broj uređaji u sustavu, parametri dolaznog toka zahtjeva itd.) .) moguće je uspostaviti takve ovisnosti u formulskom obliku samo za jednostavne sustave čekanja. Proučavanje realnih sustava provodi se oponašanjem, odnosno modeliranjem njihovog rada na računalu metodom statističkih ispitivanja.
Sustav čekanja smatra se danim ako je definirano sljedeće:
1) dolazni tok zahtjeva, ili, drugim riječima, zakon raspodjele koji karakterizira trenutke u vremenu kada zahtjevi ulaze u sustav. Glavni uzrok zahtjeva naziva se izvor. U nastavku se slažemo da pretpostavimo da izvor ima neograničen broj zahtjeva i da su zahtjevi homogeni, odnosno da se razlikuju samo u trenucima pojavljivanja u sustavu;
2) servisni sustav koji se sastoji od pogona i servisnog čvora. Potonji je jedan ili više servisnih uređaja, koji će se nazivati ​​uređajima. Svaki zahtjev mora ići na jedan od instrumenata kako bi bio servisiran. Može se pokazati da će zahtjevi morati pričekati dok uređaji ne budu slobodni. U ovom slučaju, zahtjevi su u trgovini, tvoreći jedan ili više redova. Pretpostavimo da se prijelaz zahtjeva sa skladišnog na servisni čvor događa trenutačno;
3) vrijeme servisiranja zahtjeva od strane svakog uređaja, koje je slučajna varijabla i karakterizira ga određeni zakon raspodjele;
4) disciplina čekanja, tj. skup pravila koja reguliraju broj zahtjeva koji se istovremeno nalaze u sustavu. Sustav u kojem se dolazni zahtjev odbija kada su svi uređaji zauzeti naziva se sustav bez čekanja. Ako zahtjev koji je držao sve uređaje zauzetima ulazi u red i čeka dok
dok se jedan od uređaja ne oslobodi, tada se takav sustav naziva čistim sustavom čekanja. Sustav u kojem kupac koji je držao sve poslužitelje zauzetima ulazi u red čekanja samo ako broj kupaca u sustavu ne prelazi određenu razinu (inače je kupac izgubljen) naziva se mješoviti sustav čekanja;
5) disciplina servisa, tj. skup pravila prema kojima se zahtjev odabire iz reda čekanja za servis. U praksi se najčešće koriste sljedeća pravila:
- prijave se primaju u službu po redu prvenstva;
- Prijave se prihvaćaju za uslugu prema minimalnom vremenu za primanje odbijanja;
- prijave se primaju na uslugu slučajnim redoslijedom u skladu sa zadanim vjerojatnostima;
6) disciplina čekanja, t.j. skup pravila prema kojima zahtjev daje prednost jednom ili drugom redu čekanja (ako ih ima više) i nalazi se u odabranom redu čekanja. Na primjer, dolazni zahtjev može zauzeti mjesto u najkraćem redu čekanja; u ovom redu čekanja, može se nalaziti zadnji (takav red čekanja se naziva naručeni), ili može ići na uslugu izvan reda. Moguće su i druge opcije.

Simulacijsko modeliranje sustava čekanja

Model - to je svaka slika, analogna, misaona ili ustaljena, slika, opis, dijagram, crtež itd. bilo kojeg predmeta, procesa ili pojave, koja u procesu spoznaje (proučavanja) zamjenjuje izvornik, zadržavajući neke važne za ovu studiju tipična svojstva.
Modeliranje je proučavanje bilo kojeg objekta ili sustava objekata izgradnjom i proučavanjem njihovih modela. Također - to je korištenje modela za određivanje ili doradu karakteristika i racionalizaciju načina konstruiranja novoizgrađenih objekata.
Model je alat za proučavanje složenih sustava.
Općenito složen sustav predstavljen je kao višerazinska konstrukcija međusobno djelujućih elemenata kombiniranih u podsustave različitih razina. Složeni sustavi, uključujući, uključuju Informacijski sustavi. Projektiranje tako složenih sustava provodi se u dvije faze.

1 Vanjski dizajn

U ovoj fazi odabir strukture sustava, njegovih glavnih elemenata, organizacije interakcije između elemenata, razmatranje utjecaja vanjsko okruženje, procjena pokazatelja performansi sustava.

2 Unutarnji dizajn - dizajn pojedinih elemenata
sustava

Tipična metoda za proučavanje složenih sustava u prvoj fazi je njihova simulacija na računalu.
Kao rezultat modeliranja dobivaju se ovisnosti koje karakteriziraju utjecaj strukture i parametara sustava na njegovu učinkovitost, pouzdanost i druga svojstva. Te se ovisnosti koriste za dobivanje optimalne strukture i parametara sustava.
Model formuliran matematičkim jezikom matematičke metode nazvao matematički model.
Simulacijsko modeliranje karakterizira reprodukcija pojava opisanih matematičkim modelom, uz očuvanje njihove logičke strukture, slijeda izmjene u vremenu. Sve prikladne informacije koje kruže u modelu mogu se koristiti za procjenu željenih vrijednosti, sve dok su dostupne za registraciju i naknadnu obradu.
Željene vrijednosti u proučavanju procesa simulacijom obično se određuju kao prosječne vrijednosti iz podataka velikog broja implementacija procesa. Ako je broj realizacija N korištenih za procjenu traženih vrijednosti dovoljno velik, tada, zbog zakona velikih brojeva, dobivene procjene dobivaju statističku stabilnost i mogu se uzeti kao približne vrijednosti traženih vrijednosti s dovoljna točnost za praksu.
Bit metode simulacijskog modeliranja primijenjene na zadatke čekanja je sljedeća. Algoritmi su izgrađeni
uz pomoć kojih je moguće razvijati slučajne realizacije zadanih tokova homogenih događaja, kao i modelirati procese funkcioniranja uslužnih sustava. Ovi se algoritmi koriste za višekratnu reprodukciju implementacije nasumičnog servisnog procesa pod fiksnim uvjetima problema. Dobivene informacije o stanju procesa podvrgavaju se statističkoj obradi radi evaluacije vrijednosti koje su pokazatelji kvalitete usluge.

3 Formiranje implementacija slučajnog toka aplikacija

U proučavanju složenih sustava metodom simulacije značajna se pažnja posvećuje uzimanju u obzir slučajnih čimbenika.
Kao matematičke sheme koje se koriste za formaliziranje djelovanja ovih faktora koristimo slučajni događaji, slučajne varijable i slučajni procesi (funkcije). Formiranje na računalu realizacija slučajnih objekata bilo koje prirode svodi se na generiranje i transformaciju slučajnih brojeva. Razmotrite metodu za dobivanje mogućih vrijednosti slučajnih varijabli s danim zakonom distribucije. Za formiranje mogućih vrijednosti slučajnih varijabli sa zadanim zakonom raspodjele, početni materijal su slučajne varijable koje imaju jednoliku raspodjelu u intervalu (0, 1). Drugim riječima, moguće vrijednosti xi slučajne varijable t, koja ima jednoliku raspodjelu u intervalu (0, 1), mogu se transformirati u moguće vrijednosti yi slučajne varijable r), čiji je zakon raspodjele dano. Metoda transformacije sastoji se u odabiru slučajnih brojeva iz ravnomjerno raspoređene populacije koji zadovoljavaju određeni uvjet na način da odabrani brojevi poštuju zadani zakon distribucije.
Pretpostavimo da je potrebno dobiti niz slučajnih brojeva yi s funkcijom gustoće 1^(y). Ako domena funkcije f^y) nije ograničena s jedne ili s obje strane, potrebno je prijeći na odgovarajuću krnju distribuciju. Neka raspon mogućih vrijednosti za skraćenu distribuciju bude (a, b).
Od slučajne varijable r) koja odgovara funkciji gustoće f → y), prelazimo na f.
Slučajna vrijednost b, imat će raspon mogućih vrijednosti (0, 1) i funkciju gustoće f ^ (z) danu izrazom.
Neka najveća vrijednost f^(z) bude jednaka f m . Postavimo jednolike raspodjele u intervalima (0, 1) slučajnih brojeva x 2 i-1 i x 2 i. Postupak za dobivanje niza yi slučajnih brojeva s funkcijom gustoće ^(y) svodi se na sljedeće:
1) parovi slučajnih brojeva x2i-1 odabrani su iz početne populacije,
2) za ove brojeve provjerava se valjanost nejednakosti
x 21<-- ^[а + (Ъ-а)х 2М ] (3)
m
3) ako je nejednakost (3) zadovoljena, tada se sljedeći broj yi određuje iz relacije
yi \u003d a + (b-a) x 21 (4)
Pri modeliranju uslužnih procesa postaje nužno formirati realizacije slučajnog toka homogenih događaja (aplikacija). Svaki točni događaj karakterizira vrijeme tj u kojem se događa. Da bi se slučajni tok homogenih događaja opisao kao slučajni proces, dovoljno je navesti zakon distribucije koji karakterizira slijed slučajnih varijabli tj. Da bi se dobila realizacija toka homogenih događaja t1, t2..., tk, potrebno je formirati realizaciju z b z 2 ,...,zk k-dimenzionalnog slučajnog vektora ££2,... , Sk i izračunajte vrijednosti ti u skladu sa sljedećim omjerima:
t 2 =
Neka je stacionarno obično strujanje s ograničenim naknadnim učinkom zadano funkcijom gustoće f(z). Sukladno Palmovoj formuli (6) nalazimo funkciju gustoće f1(z1) za prvi interval z1.
1-Jf(u)du
Sada možemo generirati slučajni broj z b kao što je prikazano gore, koji odgovara funkciji gustoće f1(z1), i dobiti trenutak pojavljivanja prvog zahtjeva t1 = z1. Zatim formiramo niz slučajnih brojeva koji odgovaraju funkciji gustoće f(z), te pomoću relacije (4) izračunavamo vrijednosti veličina t2, t3 ,.., tk.
4 Obrada rezultata simulacije
Prilikom implementacije algoritama modeliranja na računalu, generiraju se informacije o stanjima sustava koji se proučava. Ovi podaci su izvorni materijal za određivanje približnih vrijednosti traženih količina, ili, kako se kaže, procjena za tražene količine.
Procjena vjerojatnosti događaja A izračunava se formulom
p(A) = mN. (7)
Procjena srednje vrijednosti x slučajne varijable b, izračunato po
formula
_ 1n
k=1
Procjena S 2 za varijancu slučajne varijable ^ izračunava se po formuli
1 N 1 ( N L 2
S2=1 YA xk 2-5> J (9)
Procjena korelacijskog momenta K^ za slučajne varijable b, i c s mogućim vrijednostima x k odnosno y k izračunava se formulom
1 N 1 N
Y> [ vau

5 QS primjer modeliranja
Razmotrite sljedeći sustav:
1 Zahtjevi stižu u nasumično vrijeme, dok
vremenski interval Q između bilo koja dva uzastopna zahtjeva ima eksponencijalni zakon s parametrom ja, tj. Funkcija distribucije ima oblik
>0. (11) Sustav čekanja sastoji se od s identičnih, numeriranih poslužitelja.
3 Vrijeme T o bsl - slučajna varijabla s jednolikim zakonom raspodjele na segmentu.
4 Sustav bez čekanja, tj. zahtjev koji je zauzeo sve uređaje napušta sustav.
5 Disciplina servisa je sljedeća: ako je u trenutku prijema k -tog zahtjeva prvi poslužitelj slobodan, tada počinje servisirati zahtjev; ako je ovaj poslužitelj zauzet, a drugi je slobodan, tada zahtjev servisira drugi poslužitelj, i tako dalje.
Treba procijeniti matematička očekivanja broj zahtjeva koje je sustav poslužio u vremenu T i odbio.
Za početni trenutak izračuna biramo trenutak dolaska prvog zahtjeva T1=0. Uvedimo sljedeću oznaku: Tk je trenutak prijema k-tog zahtjeva; ti - vrijeme završetka usluge i-ti zahtjevi uređaj, i=1, 2, 3, ...,s.
Pretpostavimo da su u trenutku T1 svi uređaji slobodni.
Prvi zahtjev stiže na poslužitelj 1. Vrijeme usluge ovog poslužitelja ima jednoliku raspodjelu na segmentu . Stoga se specifična vrijednost t obl ovog vremena nalazi pomoću formule
(12)
gdje je r vrijednost slučajne varijable R ravnomjerno raspoređene na segmentu. Uređaj 1 će biti zauzet tijekom vremena t o bsl. Stoga se vremenska točka t 1 završetka servisiranja zahtjeva od strane uređaja 1 treba smatrati jednakom: t 1 = T1+ t o obsl.
Zatim dodajte jedan brojaču usluženih zahtjeva i prijeđite na sljedeći zahtjev.
Pretpostavimo da je k zahtjeva već razmotreno. Definirajmo trenutak T k+1 primitka (k+1)-tog zahtjeva. Da bismo to učinili, pronalazimo vrijednost t vremenskog intervala između uzastopnih zahtjeva. Budući da ovaj interval ima eksponencijalni zakon, onda
12
x \u003d - In r (13)
| Ll
gdje je r sljedeća vrijednost slučajne varijable R . Tada je trenutak dolaska (k + 1)-og zahtjeva: T k +1 = Tk + T.
Je li prvi uređaj slobodan u ovom trenutku? Za odgovor na ovo pitanje potrebno je provjeriti uvjet ti< Tk + i - Если это условие выполнено, то к моменту Т k +1 первый прибор освободился и может обслуживать требование. В этом случае t 1 заменяем на (Т k +1 + t обсл), добавляем единицу в счетчик об служенных требований и переходим к следующему требованию. Если t 1>T k +1, tada je prvi uređaj u trenutku T k +1 zauzet. U tom slučaju provjeravamo je li drugi uređaj slobodan. Ako je uvjet i 2< Tk + i выполнено, заменяем t2 на (Т k +1+ t о бсл), добавляем единицу в счетчик обслуженных требований и переходим к следующему требованию. Если t 2>T k +1, tada provjeravamo uvjet 1z<Тк+1 и т. д. Eсли при всех i от 1 до s имеет ti >T k +1, tada su u trenutku T k +1 svi uređaji zauzeti. U ovom slučaju dodajemo jedan brojaču neuspjeha i prelazimo na sljedeći zahtjev. Svaki put, nakon izračuna T k + 1, moramo provjeriti i uvjet za prestanak provedbe: Tk + i< T . Если это условие выполнено, то одна реализация процесса функционирования системы воспроизведена и испыта ние заканчивается. В счетчике обслуженных требований и в счетчике отказов находятся числа n обсл и n отк.
Nakon ponavljanja takvog testa n puta (koristeći različite r) i izračunavanja prosjeka rezultata eksperimenata, utvrđujemo procjene matematičkih očekivanja broja usluženih kupaca i broja kupaca koji su odbijeni:
(14)
(Ji
n j =1
gdje su (n obl) j i (n obl) j vrijednosti n obl i n obl u j-tom eksperimentu.
13

Popis korištenih izvora
1 Emelyanov A.A. Simulacijsko modeliranje gospodarskih procesa [Tekst]: Zbornik. dodatak za sveučilišta / A.A. Emelyanov, E.A. Vlasova, R.V. Misao. - M. : Financije i statistika, 2002. - 368s.
2 Buslenko, N.P. Modeliranje složenih sustava [Tekst] / N.P. Buslenko.- M.: Nauka, 1978. - 399p.
3 Sovjeti B.Ya. Modeliranje sustava [Tekst]: Zbornik. za sveučilišta / B.Ya. Sove tov, S.A. Jakovljev. -M. : Najviši. škola, 1985. - 271 str.
4 Sovjeti B.Ya. Modeliranje sustava [Tekst]: Laboratorijska radionica: Proc. dodatak za sveučilišta u specijalnosti: "Automatizirani sustav za obradu informacija i kontrolu." / B.Ya. Sovetov, S.A. Jakovljev. -M. : Najviši. škola, 1989. - 80 str.
5 Maksimej I.V. Simulacijsko modeliranje na računalu [Tekst] / Maksimey, I.V. -M: RADIO I KOMUNIKACIJE, 1988. - 231s.
6 Wentzel E.S. Teorija vjerojatnosti [Tekst]: udžbenik. za sveučilišta / E.S. Ventilacijski gol - M. : Viš. škola, 2001. - 575 str.
7 Gmurman, V.E. Teorija vjerojatnosti i matematička statistika [Tekst]: udžbenik. dodatak / V.E. Gmurman - M .: Viši. škola, 2001. - 479 str.
Dodatak A
(obavezno)
Okvirna tematika naselja i grafičkih radova
1 Na hitnoj radi jedan liječnik. Trajanje liječenja pacijenta
a vremenski intervali između prijema pacijenata su slučajne varijable raspoređene prema Poissonovom zakonu. Prema težini ozljeda pacijenti se dijele u tri kategorije, prijem bolesnika bilo koje kategorije je slučajan događaj s jednakovjerojatnom raspodjelom. Liječnik prvo obrađuje bolesnike s najtežim ozljedama (redoslijedom zaprimanja), zatim, ako ih nema, s bolesnicima srednje težine, a tek onda s lakšim ozljedama. Simulirajte proces i procijenite prosječno vrijeme čekanja u redu pacijenata svake kategorije.
2 U gradskom voznom parku postoje dvije remontne zone. Prvi služi za popravke kratkih i srednjeg trajanja, drugi - srednji i dugi. Kao kvarovi, vozila se isporučuju voznom parku; vremenski interval između isporuka je slučajna Poissonova varijabla. Trajanje popravka je slučajna varijabla s normalnom distribucijom. Modelirajte opisani sustav. Procijenite prosječna vremena čekanja u transportnom redu, koja zahtijevaju kratkoročne, srednjoročne i dugoročne popravke.
3 Mini market s jednim kontrolorom – blagajnikom opslužuje kupce čiji dolazni tok poštuje Poissonov zakon s parametrom od 20 kupaca/sat. Provesti simulaciju opisanog procesa i odrediti vjerojatnost zastoja kontrolora – blagajnika prosječna dužina redovima, prosječnom broju kupaca u minimarketu, prosječnom vremenu čekanja na uslugu, prosječnom vremenu koje kupci provode u mini marketu i ocjenjuju njegov rad.
4 ATS prima prijave za međugradske pozive. Tijek zahtjeva je Poisson. U prosjeku na sat pristigne 13 prijava. Pronađite prosječan broj primljenih zahtjeva po danu, prosječno vrijeme između pojavljivanja zahtjeva. Na telefonskoj centrali kvarovi se javljaju ako u pola sata stigne više od 50 zahtjeva. Odredite vjerojatnost kvara stanice.
5 Servis prima najjednostavniji
protok prijava intenzitetom od 1 automobila na 2 sata.U redu čekanja u dvorištu ne smiju biti više od 3 automobila. Prosječno vrijeme popravka - 2 sata. Ocijenite rad CMO-a i izradite preporuke za poboljšanje usluge.
6 Jedan tkalac opslužuje grupu tkalačkih stanova, po potrebi obavljajući kratkotrajne intervencije čije je trajanje slučajna varijabla. Simulirajte opisanu situaciju. Kolika je vjerojatnost zastoja dva stroja odjednom. Koliko dugo traje prosječno vrijeme zastoja po stroju.
7 U međugradskoj telefonskoj centrali dva telefonska operatera opslužuju zajednički red naloga. Sljedeći nalog uslužuje telefonist koji je prvi pušten. Ako su oboje zauzeti kada je narudžba primljena, poziv će biti otkazan. Simulirajte proces pod pretpostavkom da su ulazni tokovi Poissonovi.
8 Na hitnoj pomoći rade dva liječnika. Trajanje liječenja boli
a vremenski intervali između prijema pacijenata su slučajne varijable raspoređene prema Poissonovom zakonu. Prema težini ozljeda pacijenti se dijele u tri kategorije, prijem bolesnika bilo koje kategorije je slučajan događaj s jednakovjerojatnom raspodjelom. Liječnik prvo obrađuje bolesnike s najtežim ozljedama (redoslijedom zaprimanja), zatim, ako ih nema, s bolesnicima srednje težine, a tek onda s lakšim ozljedama. Simulirajte proces i procijenite prosječno vrijeme čekanja u redu pacijenata svake kategorije.
9 Na međugradskoj telefonskoj centrali služe dva telefonista
stvoriti zajednički red narudžbi. Sljedeću narudžbu uslužuje taj telefonski operater,
koji je prvi objavljen. Ako su oba zauzeta u trenutku primitka narudžbe, tada se formira red. Simulirajte proces pod pretpostavkom da su ulazni tokovi Poissonovi.
10 U sustavu prijenosa podataka, paketi podataka se razmjenjuju između čvorova A i B preko dupleksnog komunikacijskog kanala. Paketi stižu na točke sustava od pretplatnika s vremenskim intervalima između njih od 10 ± 3 ms. Prijenos paketa traje 10 ms. Točke imaju međuspremnike koji mogu pohraniti dva paketa, uključujući i onaj koji se šalje. Ukoliko paket stigne u trenutku kada su registri zauzeti, točkama sustava omogućen je pristup satelitskoj half duplex komunikacijskoj liniji, koja prenosi pakete podataka za 10 ± 5 ms. Kada je satelitska linija zauzeta, paket se odbija. Simulirati razmjenu informacija u sustavu prijenosa podataka 1 min. Odredite učestalost poziva na satelitsku liniju i njezino opterećenje. Ako su kvarovi mogući, odredite volumen registara međuspremnika potrebnih da sustav radi bez kvarova.
11 Neka se standardni sustav koristi na telefonskoj centrali s jednim ulazom: ako je pretplatnik zauzet, tada se ne formira red i potrebno je ponovno nazvati. Simulirajte situaciju: tri pretplatnika pokušavaju doći do istog vlasnika broja i, ako uspiju, razgovaraju s njim neko (slučajno trajanje) vrijeme. Kolika je vjerojatnost da netko tko se pokušava javiti na telefon to neće uspjeti u određenom vremenu T.
12 Trgovačko poduzeće planira telefonski izvršavati narudžbe za kupnju robe, za što je potrebno instalirati odgovarajuću mini-automatsku centralu s više telefonskih aparata. Ako narudžba stigne kada su sve linije zauzete, tada klijent dobiva odbijenicu. Ako je u trenutku primitka zahtjeva barem jedna linija slobodna, tada se prelazi na tu liniju i postavlja se narudžba. Intenzitet dolaznog toka prijava je 30 narudžbi po satu. Trajanje aplikacije je u prosjeku 5 minuta. Odrediti optimalan broj servisnih kanala za osiguranje stacionarnog rada QS-a.
13 U samoposluzi radi 6 kontrolora – blagajnika. Dolazni tok kupaca poštuje Poissonov zakon s intenzitetom od 120 ljudi na sat. Jedna blagajnica može opslužiti 40 ljudi na sat. Odredite vjerojatnost neaktivnog blagajnika, prosječan broj kupaca u redu, prosječno vrijeme čekanja, prosječan broj zaposlenih blagajnika. Dati ocjenu rada QS-a.
14 Poissonov protok od 200 kupaca na sat ulazi u samoposlužnu trgovinu. Tijekom dana opslužuju ih 3 blagajnička kontrolora s intenzitetom od 90 kupaca na sat. Intenzitet ulaznog toka kupaca u vršnim satima raste do vrijednosti od 400 kupaca po satu, au recesijskim satima doseže 100 kupaca po satu. Odredite vjerojatnost formiranja reda u trgovini i prosječnu duljinu reda tijekom dana, kao i potreban broj blagajnika u satima najvećeg opterećenja i recesije, osiguravajući istu duljinu reda i vjerojatnost njegovog formiranja kao u nominalnom načinu rada.
15 Prosječan broj kupaca koji dolaze na obračunski čvor u samoposluzi je 100 ljudi na sat. Blagajna može poslužiti 60 ljudi na sat. Simulirajte proces i odredite koliko je blagajnika potrebno tako da vjerojatnost reda ne prelazi 0,6.
16 Simulirajte red u trgovini s jednim prodavačem s jednakovjerojatnim zakonima raspodjele slučajnih varijabli: dolazak kupaca i trajanje usluge (s nekim fiksnim skupom parametara). Dobijte stabilne karakteristike: prosječne vrijednosti čekanja u redu od strane kupca i vrijeme mirovanja prodavača u iščekivanju dolaska kupaca. Procijenite njihovu vjerodostojnost.
17 Simulirajte red u trgovini s jednim prodavačem s Poissonovim zakonima distribucije slučajnih varijabli: dolazak kupaca i trajanje usluge (s nekim fiksnim skupom parametara). Dobijte stabilne karakteristike: prosječne vrijednosti čekanja u redu od strane kupca i vrijeme mirovanja prodavača u iščekivanju dolaska kupaca. Procijenite njihovu vjerodostojnost.
18 Napravite model benzinske postaje. Pronađite pokazatelje kvalitete zahtjeva za uslugom. Odredite broj regala tako da red čekanja ne raste.
19 Prosječan broj kupaca koji dolaze na blagajnu u samoposluživanju 60 ljudi na sat. Blagajna može poslužiti 35 osoba na sat. Simulirajte proces i odredite koliko je blagajnika potrebno tako da vjerojatnost reda ne prelazi 0,6.
20 Izradite model autobusna ruta sa n zaustavljanja. Odrediti pokazatelje uspješnosti za korištenje QS-a.

rad ili učinkovitost sustava čekanja su sljedeći.

Za CMO s neuspjesima:

Za CMO s neograničenim čekanjem i apsolutna i relativna propusnost gube svoje značenje, budući da će svaki dolazni zahtjev biti poslužen prije ili kasnije. Za takav QS važni pokazatelji su:

Za CMO mješoviti tip koriste se obje skupine pokazatelja: i relativni i apsolutna propusnost, i karakteristike očekivanja.

Ovisno o svrsi operacije čekanja, bilo koji od gore navedenih pokazatelja (ili skup pokazatelja) može se odabrati kao kriterij izvedbe.

analitički model QS je skup jednadžbi ili formula koje vam omogućuju određivanje vjerojatnosti stanja sustava u procesu njegovog rada i izračunavanje pokazatelja performansi prema poznate karakteristike dolazni protok i servisni kanali.

Ne postoji opći analitički model za proizvoljan QS. Analitički modeli razvijeni su za ograničeni broj posebnih slučajeva QS-a. Analitički modeli koji više ili manje točno prikazuju stvarne sustave u pravilu su složeni i teško vidljivi.

Analitičko modeliranje QS-a uvelike je olakšano ako su procesi koji se odvijaju u QS-u Markovljevi (tokovi zahtjeva su jednostavni, vremena usluge su eksponencijalno raspoređena). U ovom slučaju, svi procesi u QS mogu se opisati uobičajenim diferencijalne jednadžbe, a u graničnom slučaju, za stacionarna stanja- linearni algebarske jednadžbe te nakon njihovog rješavanja odrediti odabrane pokazatelje uspješnosti.

Razmotrimo primjere nekih QS-ova.

2.5.1. Višekanalni QS s kvarovima

Primjer 2.5. Tri prometna inspektora provjeravaju putne listove vozača kamiona. Ako je barem jedan inspektor slobodan, kamion koji prolazi se zaustavlja. Ako su svi inspektori zauzeti, kamion prolazi bez zaustavljanja. Tok kamiona je najjednostavniji, vrijeme provjere je slučajno s eksponencijalnom raspodjelom.

Takvu situaciju može simulirati trokanalni QS s kvarovima (bez čekanja). Sustav je otvoren, s homogenim aplikacijama, jednofazni, s apsolutno pouzdanim kanalima.

Opis stanja:

Svi inspektori su besplatni;

Jedan inspektor ima posla;

Dva inspektora su zauzeta;

Tri inspektora su zauzeta.

Graf stanja sustava prikazan je na sl. 2.11.

Riža. 2.11.

Na grafikonu: - intenzitet protoka kamiona; - intenzitet provjere dokumenata od strane jednog prometnog inspektora.

Simulacija se provodi kako bi se odredio dio automobila koji neće biti testiran.

Riješenje

Željeni dio vjerojatnosti je vjerojatnost zaposlenja sva tri inspektora. Budući da graf stanja predstavlja tipična shema"smrt i reprodukcija", tada ćemo pronaći pomoću ovisnosti (2.2).

Može se okarakterizirati učinak ovog radnog mjesta prometnih inspektora relativna propusnost:

Primjer 2.6. Za primanje i obradu dojava izvidničke skupine, izvidničkom odjelu zdruga raspoređena je skupina od tri časnika. Očekivana stopa javljanja je 15 prijava na sat. Prosječno vrijeme obrade jedne prijave od strane jednog službenika je . Svaki časnik može primati izvješća od bilo koje izvidničke grupe. Otpušteni službenik obrađuje posljednju od primljenih prijava. Dolazna izvješća moraju biti obrađena s vjerojatnošću od najmanje 95%.

Utvrdite je li dodijeljena grupa od tri časnika dovoljna za izvršenje dodijeljene zadaće.

Riješenje

Skupina časnika radi kao CMO s kvarovima, koji se sastoji od tri kanala.

Tijek izvješća s intenzitetom može se smatrati najjednostavnijim, budući da je skup nekoliko izviđačkih skupina. Intenzitet održavanja . Zakon raspodjele je nepoznat, ali to nije bitno, jer je pokazano da za sustave s kvarovima može biti proizvoljan.

Opis stanja i grafikon stanja QS-a bit će slični onima danima u primjeru 2.5.

Budući da je graf stanja shema "smrti i reprodukcije", postoje gotovi izrazi za granične vjerojatnosti stanja za njega:

Relacija se zove smanjeni intenzitet protoka prijava. fizičko značenje sljedeće: vrijednost je prosječan broj zahtjeva koji dolaze u QS za prosječno vrijeme usluge jednog zahtjeva.

U primjeru .

u CMO neuspjeh javlja se kada su sva tri kanala zauzeta, tj. Zatim:

Jer vjerojatnost kvara u obradi izvješća je više od 34% (), tada je potrebno povećati osoblje grupe. Udvostručimo sastav grupe, odnosno QS će sada imati šest kanala, i izračunajmo:

Tako će samo grupa od šest službenika moći obraditi pristigla izvješća s vjerojatnošću od 95%.

2.5.2. Višekanalni QS s čekanjem

Primjer 2.7. Na dionici forsiranja rijeke nalazi se 15 istovrsnih prijelaza. Protok vozila koja dolaze na prijelaz u prosjeku je 1 jedinica/min, prosječno vrijeme prelaska jedne jedinice opreme je 10 minuta (uzimajući u obzir povratak objekta prijelaza).

Ocijenite glavne karakteristike prijelaza, uključujući vjerojatnost neposrednog prelaska odmah po dolasku dijela opreme.

Riješenje

Apsolutna propusnost, tj. sve što dođe do prijelaza gotovo se odmah prijeđe.

Prosječan broj operativnih prijelaza:

Omjeri iskorištenosti križanja i zastoja:

Također je razvijen program za rješavanje primjera. Vremenski intervali dolaska opreme na prijelaz, vrijeme prijelaza uzeti su raspoređeni po eksponencijalnom zakonu.

Stope iskorištenosti trajekta nakon 50 vožnji praktički su iste: .