U praktičnom satu razmotrit ćemo ovaj put i usporediti rezultate simulacije s teoretskim rješenjem. Primjeri rješavanja problema sustava čekanja

Matematički (apstraktni) objekt čiji su elementi (slika 2.1):

• ulazni (dolazni) tijek zahtjeva (zahtjeva) za uslugu;
• servisni uređaji (kanali);
• red aplikacija koje čekaju uslugu;
• izlazni (odlazni) tijek servisiranih aplikacija;
• tijek zahtjeva za dodatnom uslugom nakon prekida usluge;
• tijek neobrađenih zahtjeva.

Primjena(zahtjev, zahtjev, poziv, klijent, poruka, paket) - objekt koji ulazi u QS i zahtijeva servis u uređaju. Forma skupa uzastopnih zahtjeva raspoređenih u vremenu ulazni tijek zahtjeva.

Riža. 2.1.

Servisni uređaj(uređaj, uređaj, kanal, linija, alat, automobil, ruter itd.) - QS element čija je namjena servisiranje zahtjeva.

Servis- kašnjenje aplikacije u servisnom uređaju neko vrijeme.

Trajanje usluge- vrijeme odgode (servisiranja) zahtjeva u uređaju.

Uređaj za pohranu(buffer, input buffer, output buffer) - skup mjesta za čekanje zahtjeva ispred uređaja za posluživanje. Broj mjesta za čekanje - kapacitet pohrane.

Prijava koju primi CMO može biti u dva stanja:

• 1) servis(u uređaju);
• 2) očekivanja(u spremištu) ako su svi uređaji zauzeti servisiranjem drugih zahtjeva.

Zahtjevi koji se nalaze u obrascu za skladištenje i čekanje usluge red aplikacije. Broj aplikacija u spremniku koji čekaju servis - duljina čekanja.

Disciplina međuspremnika(queuing discipline) - pravilo unosa pristiglih zahtjeva u uređaj za pohranu (buffer).

Disciplina servisa- pravilo za odabir aplikacija iz reda čekanja za uslugu u uređaju.

Prioritet- pravo prvenstva (zauzimanje resursa) za ulazak u pohranu ili odabir iz reda čekanja za servisiranje u aplikacijama uređaja jedne klase u odnosu na aplikacije drugih klasa.

Postoje mnogi sustavi čekanja koji se razlikuju po strukturnoj i funkcionalnoj organizaciji. Istodobno, razvoj analitičkih metoda za izračunavanje pokazatelja učinkovitosti QS sustava u mnogim slučajevima pretpostavlja postojanje niza ograničenja i pretpostavki koje sužavaju skup QS sustava koji se proučavaju. Zato ne postoji opći analitički model za proizvoljan QS složene strukture.

Analitički QS model je skup jednadžbi ili formula koje omogućuju određivanje vjerojatnosti stanja sustava tijekom njegovog rada i pokazatelja performansi na temelju poznatih parametara dolaznog toka i uslužnih kanala, međuspremnika i uslužnih disciplina.

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 raspoređena su eksponencijalno). U ovom slučaju, svi procesi u QS-u mogu se opisati običnim diferencijalnim jednadžbama, au graničnom slučaju - za stacionarna stanja - linearnim algebarskim jednadžbama i, nakon što ih se riješi pomoću bilo koje metode dostupne u matematičkim programskim paketima, odrediti odabrane pokazatelje učinkovitosti .

U IM sustavima, pri implementaciji QS-a, prihvaćaju se sljedeća ograničenja i pretpostavke:

• aplikacija primljena u sustav odmah dobiva servis ako nema zahtjeva u redu i uređaj je slobodan;
• Uređaj se može servisirati samo u određenom trenutku. jedan primjena;
• nakon završetka servisiranja bilo kojeg zahtjeva u uređaju, odmah se iz reda čekanja za servis odabire sljedeći zahtjev, tj. uređaj ne stoji besposlen ako postoji barem jedna prijava u redu čekanja;
• zaprimanje zahtjeva u QS-u i trajanje njihovog servisiranja ne ovisi o broju zahtjeva koji su već u sustavu niti o bilo kojim drugim čimbenicima;
• trajanje servisiranja aplikacija ne ovisi o intenzitetu prijava koje ulaze u sustav.

Pogledajmo detaljnije neke elemente QS-a.

Ulazni (dolazni) tok aplikacija. Tijek događaja je niz homogenih događaja koji slijede jedan za drugim i događaju se na nekim, općenito govoreći, slučajan trenutaka u vremenu. Ako je događaj pojava aplikacija, imamo tijek aplikacija. Za opis tijeka prijava u općem slučaju potrebno je postaviti vremenske intervale t = tk - t k-1 između susjednih trenutaka tk_k I tk prijem prijava sa serijskim brojevima Za - 1 i Do odnosno (Za - 1, 2, ...; t 0 - 0 - početno vrijeme).

Glavna karakteristika toka aplikacije je njegova intenzitet X- prosječan broj prijava zaprimljenih na ulazu QS-a u jedinici vremena. Vrijednost t = 1/X definira prosječni vremenski interval između dvije uzastopne primjene.

Potok se zove deterministički ako vremenski intervali t do između susjednih aplikacija poprimaju određene prethodno poznate vrijednosti. Ako su intervali isti (x k= t za sve k = 1, 2, ...), tada se poziva tok redovito. Za potpuni opis redovitog protoka zahtjeva dovoljno je postaviti intenzitet protoka x odnosno vrijednost intervala t = 1/X.

Tok u kojem vremenski intervali x k između susjednih aplikacija su slučajne varijable, tzv slučajan. Za potpuni opis slučajnog tijeka zahtjeva u općem slučaju potrebno je specificirati zakone distribucije F fc (x fc) za svaki od vremenskih intervala x k, k = 1,2,....

Slučajni tok u kojem svi vremenski intervali x b x 2,... između susjednih uzastopnih zahtjeva su nezavisne slučajne varijable opisane distribucijskim funkcijama FjCij), F 2 (x 2), ... prema tome, naziva se tok s ograničeno naknadno djelovanje.

Slučajni tok se zove ponavljajuće, ako svi vremenski intervali x b t 2, ... raspoređeno između naloga prema istom zakonu F(t). Postoji mnogo ponavljajućih niti. Svaki zakon distribucije generira vlastiti rekurentni tok. Ponavljajući tokovi inače se nazivaju Palmovi tokovi.

Ako intenzitet x i zakon distribucije F(t) intervala između uzastopnih aplikacija se ne mijenjaju tijekom vremena, tada se tok aplikacija naziva stacionarni Inače, tijek zahtjeva je nestacionarno.

Ako u svakom trenutku vremena tk Na QS ulazu se može pojaviti samo jedna reklamacija, tada se poziva tijek reklamacija obični. Ako se više od jedne aplikacije može pojaviti u bilo kojem trenutku, tada je tok aplikacija izvanredno, ili skupina.

Tok zahtjeva naziva se tijek bez naknadnog djelovanja, ako prijave budu primljene bez obzira na to jedno od drugog, tj. trenutak zaprimanja sljedeće prijave ne ovisi o tome kada je i koliko je prijava zaprimljeno prije tog trenutka.

Stacionarno obično strujanje bez naknadnog djelovanja naziva se najjednostavniji.

Vremenski intervali t između zahtjeva u najjednostavnijem toku su raspoređeni eksponencijalni (indikativan) zakon: s funkcijom raspodjele F(t) = 1 - e ~ m; gustoća distribucije/(f) = Heh~" ja, Gdje X> 0 - parametar distribucije - intenzitet protoka prijava.

Najjednostavniji tok često se naziva poissonovski. Naziv dolazi od činjenice da je za ovaj tok vjerojatnost P fc (At) pojavljivanja točno Do primjene za određeni vremenski interval At određuje se Poissonov zakon:

Treba napomenuti da Poissonov tok, za razliku od najjednostavnijeg, može biti:

• stacionarno, ako intenzitet x ne mijenja se tijekom vremena;
• nestacionarno, ako intenzitet protoka ovisi o vremenu: x= >.(t).

U isto vrijeme, najjednostavniji tok, po definiciji, uvijek je stacionaran.

Analitičke studije modela čekanja često se provode pod pretpostavkom jednostavnog tijeka zahtjeva, što je zbog niza izvanrednih značajki koje su mu svojstvene.

1. Zbrajanje (spajanje) tokova. Najjednostavniji tok u teoriji QS sličan je normalnom zakonu distribucije u teoriji vjerojatnosti: najjednostavniji tok se postiže prelaskom na granicu za tok koji je zbroj tokova s ​​proizvoljnim karakteristikama s beskonačnim povećanjem broja članova i smanjenje njihovog intenziteta.

Iznos N neovisni stacionarni obični tokovi s intenzitetima X x 2 ,..., X N tvori najjednostavniji tok s intenzitetom

X=Y,^i pod uvjetom da tokovi koji se dodaju imaju više od ili

manje jednako mali utjecaj na ukupni protok. U praksi je ukupni protok blizak najjednostavnijem kada N> 5. Dakle, pri zbrajanju nezavisnih najjednostavnijih tokova, ukupni tok će biti najjednostavniji u bilo kojoj vrijednosti N.

• 2. Probabilističko razrjeđivanje protoka. Probabilistički(Ali ne deterministički) vakuum najjednostavniji tijek aplikacije, u kojima je svaka aplikacija slučajna s određenom vjerojatnošću R je isključen iz tijeka, bez obzira na to jesu li drugi zahtjevi isključeni ili ne, dovodi do formiranja najjednostavniji tijek s intenzitetom X* = rH, Gdje x- intenzitet izvornog protoka. Tijek izuzetih zahtjeva s intenzitetom X** = (1 - p) X- Isto najjednostavniji teći.
• 3. Učinkovitost. Ako su kanali posluživanja (uređaji) projektirani za najjednostavniji protok zahtjeva s intenzitetom X, onda će servisiranje drugih vrsta tokova (s istim intenzitetom) biti osigurano s ništa manjom učinkovitošću.
• 4. Jednostavnost. Pretpostavka o najjednostavnijem tijeku zahtjeva omogućuje mnogim matematičkim modelima da u eksplicitnom obliku dobiju ovisnost QS pokazatelja o parametrima. Najveći broj analitičkih rezultata dobiven je za najjednostavniji tok aplikacija.

Analiza modela s tokovima reda koji nisu najjednostavniji obično komplicira matematičke izračune i ne dopušta uvijek dobivanje analitičkog rješenja u eksplicitnom obliku. "Najjednostavniji" tijek je dobio svoje ime upravo zbog ove značajke.

Aplikacije mogu imati različite uvjete za početak usluge. U ovom slučaju kažu da aplikacije heterogena. Prednosti nekih tokova aplikacija u odnosu na druge na početku usluge određuju se prioritetima.

Važna karakteristika ulaznog toka je koeficijent varijacije

gdje je t int matematičko očekivanje duljine intervala; O- standardna devijacija duljine intervala x int (slučajna varijabla).

Za najjednostavniji tok (a = -, m = -) imamo v = 1. Za većinu

pravi tokovi 0

Servisni kanali (uređaji). Glavna karakteristika kanala je trajanje usluge.

Trajanje usluge- vrijeme kada je zahtjev u uređaju - u općem slučaju slučajna vrijednost. U slučaju heterogenog opterećenja QS-a, trajanje servisiranja zahtjeva različitih klasa može se razlikovati u zakonima raspodjele ili samo u prosječnim vrijednostima. U ovom slučaju obično se pretpostavlja da je trajanje servisiranja zahtjeva svake klase neovisno.

Praktičari često pretpostavljaju da je trajanje servisiranja aplikacija raspodijeljeno eksponencijalni zakonšto značajno pojednostavljuje analitičke proračune. To je zbog činjenice da su procesi koji se odvijaju u sustavima s eksponencijalnom distribucijom vremenskih intervala markovski procesi:

gdje c - intenzitet usluge, ovdje p = _--; t 0 bsl - matematika -

vrijeme čekanja na uslugu.

Osim eksponencijalne, postoje Erlang/c-distribucija, hipereksponencijalna, trokutasta i neke druge. To nas ne bi trebalo zbuniti, jer se pokazalo da vrijednost kriterija učinkovitosti QS-a malo ovisi o vrsti zakona raspodjele vremena usluge.

Pri proučavanju QS-a izostavljena je bit usluge i kvaliteta usluge.

Kanali mogu biti apsolutno pouzdan, oni. nemojte uspjeti. Ili bolje rečeno, to se može prihvatiti tijekom istraživanja. Kanali mogu imati krajnja pouzdanost. U ovom slučaju, QS model je mnogo kompliciraniji.

Učinkovitost QS-a ne ovisi samo o parametrima ulaznih tokova i uslužnih kanala, već i o redoslijedu u kojem se servisiraju dolazni zahtjevi, tj. o metodama upravljanja protokom zahtjeva kada uđu u sustav i pošalju se na servis.

Metode za upravljanje tokovima aplikacija određuju sljedeće discipline:

• puferiranje;
• servis.

Discipline međuspremnika i održavanja mogu se klasificirati prema sljedećim kriterijima:

• prisutnost prioriteta između aplikacija različitih klasa;
• metoda za premještanje zahtjeva iz reda čekanja (za discipline međuspremnika) i dodjeljivanje zahtjeva za uslugu (za discipline usluge);
• pravilo za izbacivanje ili odabir servisnih zahtjeva;
• sposobnost mijenjanja prioriteta.

Varijanta klasifikacije disciplina međuspremnika (queuing) u skladu s navedenim karakteristikama prikazana je na slici. 2.2.

Ovisno o dostupnost ili nedostatak prioriteta između zahtjeva različitih klasa, sve discipline međuspremnika mogu se podijeliti u dvije skupine: neprioritetne i prioritetne.

Po metoda premještanja zahtjeva iz skladišta Mogu se razlikovati sljedeće klase disciplina međuspremnika:

• bez izbacivanja zahtjeva - gube se zahtjevi koji su ušli u sustav i utvrdili da je disk potpuno pun;
• s premještanjem aplikacije ove klase, tj. iste klase kao i primljena prijava;
• s pomicanjem aplikacije iz najnižeg razreda prioriteta;
• uz istiskivanje aplikacije iz skupine klasa niskog prioriteta.

Riža. 2.2.

Mogu se koristiti sljedeće discipline međuspremnika: pravila za izbacivanje zahtjeva iz skladišta:

• slučajni pomak;
• premještanje posljednjeg zahtjeva, tj. ušao u sustav kasnije od svih ostalih;
• istiskivanje "duge" narudžbe, tj. nalazi u skladištu dulje od svih prethodno zaprimljenih prijava.

Na sl. 2.3 predstavlja klasifikaciju disciplina servisiranja aplikacija u skladu s istim kriterijima kao i za discipline međuspremnika.

Ponekad se pretpostavlja da je kapacitet pohrane u modelima neograničen, iako je u stvarnom sustavu ograničen. Ova pretpostavka je opravdana kada je vjerojatnost gubitka zahtjeva u stvarnom sustavu zbog toga što je kapacitet pohrane pun manji od 10_3. U ovom slučaju disciplina praktički nema utjecaja na izvedbu servisiranja aplikacije.

Ovisno o dostupnost ili nedostatak prioriteta Između zahtjeva različitih klasa, sve uslužne discipline, kao i discipline međuspremnika, mogu se podijeliti u dvije skupine: neprioritetne i prioritetne.

Po način dodjele servisnih zahtjeva Discipline održavanja mogu se podijeliti na discipline:

• pojedinačni način rada;
• grupni način rada;
• kombinirani način rada.

Riža. 2.3.

U servisnim disciplinama način rada za jednog igrača svaki put za servis dodijeljen je samo jedan aplikacija, za koju se redovi gledaju nakon završetka servisiranja prethodne aplikacije.

U servisnim disciplinama grupni način rada svaki put za servis dodijeljena je grupa aplikacija jedan red čekanja, za koji se pregled redova čeka tek nakon servisiranja svih zahtjeva prethodno dodijeljene grupe. Novododijeljena grupa zahtjeva može uključivati ​​sve zahtjeve danog reda čekanja. Zahtjevi iz grupe dodijeljene usluzi se sekvencijalno odabiru iz reda čekanja i servisiraju se od strane uređaja, nakon čega se sljedeća grupa zahtjeva drugog reda dodjeljuje servisu u skladu sa specificiranom servisnom disciplinom.

Kombinirani način rada- kombinacija pojedinačnog i grupnog načina, kada se dio redova zahtjeva obrađuje u pojedinačnom, a drugi dio u grupnom načinu.

Discipline usluga mogu koristiti sljedeća pravila za odabir zahtjeva za uslugu.

Neprioritetno(aplikacije nemaju privilegije za rano servisiranje - hvatanje resursa):

• prvi dođe, prvi uslužena usluga FIFO (prvi ušao - prvi izašao, prvi ušao - prvi izašao);
• obrnuta usluga- aplikacija je odabrana iz reda čekanja u modu LIFO (zadnji u - prvi van posljednji ušao - prvi izašao);
• nasumična usluga- aplikacija je odabrana iz reda čekanja u modu RAND (slučajan- nasumično);
• ciklička usluga- aplikacije se biraju u procesu cikličkog prozivanja pogona u nizu 1, 2, N S N- broj pogona), nakon čega se navedeni niz ponavlja;

Prioritet(aplikacije imaju privilegije za rano servisiranje - hvatanje resursa):

• S relativne prioritete- ako se u procesu tekućeg servisiranja zahtjeva u sustav zaprime zahtjevi višeg prioriteta, tada se servisiranje tekućeg čak i neprioritetnog zahtjeva ne prekida, a zaprimljeni zahtjevi se šalju u red čekanja; relativni prioriteti igraju ulogu samo u trenutku završetka trenutne usluge aplikacije prilikom odabira nove aplikacije za uslugu iz reda čekanja.
• S apsolutni prioriteti- po primitku aplikacije s visokim prioritetom, prekida se servis aplikacije s niskim prioritetom, a pristigla aplikacija se šalje na servis; prekinuta aplikacija može se vratiti u red čekanja ili izbrisati iz sustava; ako se aplikacija vrati u red čekanja, tada se njeno daljnje servisiranje može izvršiti s prekinutog mjesta ili ponovno;
• s mješoviti prioriteti- stroga ograničenja vremena čekanja u redu za servisiranje pojedinačnih zahtjeva zahtijevaju dodjelu apsolutnih prioriteta istima; kao rezultat toga, vrijeme čekanja za aplikacije s niskim prioritetom može ispasti neprihvatljivo dugo, iako pojedinačne aplikacije imaju marginu vremena čekanja; za poštivanje ograničenja za sve vrste zahtjeva, moguće je, uz apsolutne prioritete, nekim zahtjevima dodijeliti relativne prioritete, a ostale poslužiti u neprioritetnom načinu rada;
• S izmjenjivanje prioriteta- analog relativnih prioriteta, prioritet se uzima u obzir samo u trenutku završetka trenutne usluge grupe zahtjeva jednog reda čekanja i imenovanja nove grupe za uslugu;
• zakazani servis- zahtjevi različitih klasa (koji se nalaze u različitim pogonima) odabiru se za uslugu prema određenom rasporedu koji specificira redoslijed prozivanja reda zahtjeva, npr. u slučaju tri klase zahtjeva (pogona), raspored može izgledati ovako (2, 1, 3, 3, 1, 2) ili (1, 2, 3, 3, 2, 1).

U IM računalnim sustavima, u pravilu, disciplina je implementirana prema zadanim postavkama FIFO. Međutim, oni imaju alate koji korisniku pružaju mogućnost organiziranja disciplina usluga koje su mu potrebne, uključujući i prema rasporedu.

Prijave koje prima SMO podijeljene su u razrede. U QS-u, koji je apstraktni matematički model, aplikacije pripadaju različitim klasama u slučaju da se u simuliranom stvarnom sustavu razlikuju u barem jednoj od sljedećih karakteristika:

• trajanje usluge;
• prioriteti.

Ako se aplikacije ne razlikuju u trajanju usluge i prioritetima, mogu biti predstavljene aplikacijama iste klase, uključujući one primljene iz različitih izvora.

Da bismo matematički opisali uslužne discipline s mješovitim prioritetima, koristimo se matrica prioriteta,što je kvadratna matrica Q = (q, ;), i J - 1,..., I, I - broj klasa aplikacija koje ulaze u sustav.

Element q(j matrica specificira prioritet zahtjeva klase ja u odnosu na razredne prijave; i može poprimiti sljedeće vrijednosti:

• 0 - bez prioriteta;
• 1 - relativni prioritet;
• 2 - apsolutni prioritet.

Elementi matrice prioriteta moraju zadovoljiti sljedeće zahtjevi:

• qn= 0, budući da se prioriteti ne mogu postaviti između zahtjeva iste klase;
• Ako q (j = 1 ili 2 onda q^ = 0, jer ako klasa zahtijeva ja imaju prioritet nad aplikacijama klase j, onda potonji ne mogu imati prioritet nad aplikacijama klase ja (i,j = 1, ..., I).

Ovisno o sposobnost mijenjanja prioriteta Tijekom rada sustava, prioritetne discipline međuspremnika i održavanja podijeljene su u dvije klase:

• 1) sa statični prioriteti, koji se ne mijenjaju tijekom vremena;
• 2) sa dinamički prioriteti, koji se tijekom rada sustava može mijenjati ovisno o različitim čimbenicima, npr. kada se dosegne određena kritična vrijednost duljine reda čekanja aplikacija klase koja nema prioritet ili ima niski prioritet, može joj se dati viši prioritet .

U IM računalnim sustavima uvijek postoji jedan element (objekt) preko kojeg se, i samo preko njega, unose aplikacije u model. Prema zadanim postavkama, svi uneseni zahtjevi su neprioritetni. Ali postoje mogućnosti dodjele prioriteta u nizu 1, 2, ..., uključujući i tijekom izvođenja modela, tj. u dinamici.

Izlazni tok tok je servisiranih aplikacija koje napuštaju QS. U stvarnim sustavima zahtjevi prolaze kroz nekoliko QS-ova: tranzitnu komunikaciju, proizvodni transporter itd. U ovom slučaju, odlazni tok je dolazni tok za sljedeći QS.

Dolazni tok prvog QS-a, koji prolazi kroz sljedeće QS-ove, je iskrivljen, a to komplicira analitičko modeliranje. Ipak treba imati na umu da s najjednostavnijim ulaznim tokom i eksponencijalnom uslugom(oni. u Markovljevim sustavima) izlazni tok je također najjednostavniji. Ako vrijeme usluge ima neeksponencijalnu distribuciju, tada izlazni tok ne samo da nije najjednostavniji, već nije ni rekurentan.

Imajte na umu da vremenski intervali između zahtjeva odlaznog toka nisu isti kao servisni intervali. Uostalom, može se ispostaviti da nakon završetka sljedećeg servisa QS neko vrijeme miruje zbog nedostatka aplikacija. U ovom slučaju, interval odlaznog toka sastoji se od vremena mirovanja QS-a i intervala servisiranja prvog zahtjeva koji je stigao nakon vremena mirovanja.

U QS-u, osim odlaznog tijeka servisiranih aplikacija, također može postojati tijek neobrađenih zahtjeva. Ako takav QS prima rekurentni tok, a usluga je eksponencijalna, tada je tok neservisiranih zahtjeva rekurentan.

Redovi besplatnih kanala. U višekanalnom QS-u mogu se formirati redovi slobodnih kanala. Broj besplatnih kanala je slučajna vrijednost. Istraživača mogu zanimati različite karakteristike ove slučajne varijable. Obično je to prosječan broj kanala koje usluga zauzima tijekom intervala ankete i njihovi faktori opterećenja.

Kao što smo ranije primijetili, u stvarnim objektima aplikacije se sekvencijalno servisiraju u nekoliko QS-ova.

Poziva se konačan skup sekvencijalno međusobno povezanih QS-ova koji obrađuju zahtjeve koji kruže u njima mreža čekanja (SeMO) (Sl. 2.4, A).

Riža. 2.4.

SeMO se također naziva višefazni sustavi čekanja.

Kasnije ćemo razmotriti primjer konstruiranja IM SeMO.

Glavni elementi SeMO-a su čvorovi (U) i izvori (generatori) aplikacija (G).

Čvor mreže su sustav čekanja.

Izvor- generator zahtjeva koji ulaze u mrežu i zahtijevaju određene stupnjeve usluge u mrežnim čvorovima.

Za pojednostavljeni prikaz SeMO-a koristi se graf.

Brojite SeMO- orijentirani graf (digraf), čiji vrhovi odgovaraju čvorovima SeMO, a lukovi prikazuju prijelaze zahtjeva između čvorova (slika 2.4, b).

Dakle, pogledali smo osnovne koncepte QS-a. Ali pri razvoju računalnih informacijskih sustava i njihovom unaprjeđenju svakako se koristi i golemi kreativni potencijal trenutno sadržan u analitičkom modeliranju QS-a.

Da bismo bolje uočili ovaj kreativni potencijal, zadržimo se, kao prvu aproksimaciju, na klasifikaciji QS modela.

Crtanje 0 - 2 Tokovi događaja (a) i najjednostavniji tok (b)

10.5.2.1. Stacionarnost

Strujanje se naziva stacionarno , ako je vjerojatnost da se određeni broj događaja dogodi u elementarnom vremenskom segmentu duljina τ (

Slika 0-2 , A) ovisi samo o duljini odsječka i ne ovisi o tome gdje točno na osi t nalazi se ovo područje.

Stacionarno strujanje znači njegovu jednolikost tijekom vremena; probabilističke karakteristike takvog protoka ne mijenjaju se ovisno o vremenu. Konkretno, takozvani intenzitet (ili "gustoća") toka događaja - prosječan broj događaja po jedinici vremena za stacionarni tok - mora ostati konstantan. To, naravno, ne znači da je stvarni broj događaja koji se pojavljuju u jedinici vremena konstantan; tok može imati lokalne kondenzacije i razrjeđenja. Važno je da za stacionarno strujanje ove kondenzacije i razrijeđenosti nisu pravilne prirode, a prosječni broj događaja koji padaju unutar jednog vremenskog razdoblja ostaje konstantan za cijelo promatrano razdoblje.

U praksi često postoje tokovi događaja koji se (barem u ograničenom vremenskom razdoblju) mogu smatrati stacionarnim. Na primjer, tok poziva koji stiže na telefonsku centralu, recimo, između 12 i 13 sati može se smatrati fiksnim. Isti protok više neće biti stacionaran cijeli dan (noću je intenzitet protoka poziva mnogo manji nego danju). Imajte na umu da je isti slučaj s većinom fizičkih procesa, koje nazivamo "stacionarnim"; u stvarnosti, oni su stacionarni samo kroz ograničeno vremensko razdoblje, a proširenje ovog područja u beskonačnost samo je prikladna tehnika koja se koristi u svrhu pojednostavljenja.

10.5.2.2. Nema naknadnog učinka

Tok događaja naziva se tok bez naknadnog učinka , ako za bilo koje vremensko razdoblje koje se ne preklapa, broj događaja koji pada na jedan od njih ne ovisi o tome koliko događaja pada na drugi (ili druge, ako se u obzir uzme više od dva odjeljka).

U takvim tokovima, događaji koji tvore tok pojavljuju se u uzastopnim trenucima u vremenu, neovisno jedni o drugima. Na primjer, protok putnika koji ulazi u stanicu metroa može se smatrati protokom bez posljedica, jer razlozi koji su odredili dolazak pojedinog putnika u danom trenutku, a ne u drugom, u pravilu nisu povezani sa sličnim razlozima drugi putnici. Ako se takva ovisnost pojavi, narušava se uvjet nepostojanja posljedica.

Razmotrimo, na primjer, protok teretnih vlakova duž željezničke pruge. Ako zbog sigurnosnih uvjeta ne mogu slijediti jedan za drugim češće nego u intervalima t 0 , tada postoji ovisnost između događaja u toku, a uvjet nepostojanja naknadnog učinka je povrijeđen. Međutim, ako interval t 0 mali u usporedbi s prosječnim intervalom između vlakova, tada je takvo kršenje beznačajno.

Crtanje 0 - 3 Poissonova distribucija

Razmotrimo na osi t najjednostavniji tok događaja s intenzitetom λ. (Slika 0-2 b) . Zanimat će nas slučajni vremenski interval T između susjednih događaja u ovom toku; Nađimo njegov zakon distribucije. Prvo, pronađimo funkciju distribucije:

F(t) = P(T ( 0-2)

tj. vjerojatnost da vrijednost T će imati vrijednost manju odt. Odgodimo od početka intervala T (točke t 0 ) segment t i pronađite vjerojatnost da interval T bit će manje t . Da biste to učinili, potrebno je da za dio dužine t, susjedna točki t 0 , barem jedan pogodak događaja toka. Izračunajmo vjerojatnost toga F(t) kroz vjerojatnost suprotnog događaja (po odjeljku t neće pogoditi nijedan događaj toka):

F (t) = 1 - P 0

Vjerojatnost P 0 nalazimo iz formule (1), uz pretpostavkum = 0:

odakle će funkcija raspodjele vrijednosti T biti:

(0-3)

Da bismo pronašli gustoću distribucije f(t) nasumična varijabla T, potrebno je razlikovati izraz (0‑1) pot:

0-4)

Zakon raspodjele s gustoćom (0‑4) naziva se eksponencijalni (ili eksponencijalno ). Veličina λ se naziva parametar demonstrativno pravo.

Slika 0 - 4 Eksponencijalna distribucija

Nađimo numeričke karakteristike slučajne varijable T- matematičko očekivanje (prosječna vrijednost) M [ t ] = m t , i varijanca Dt. Imamo

( 0-5)

(integracija po dijelovima).

Disperzija T vrijednosti je:

(0-6)

Uzimanjem kvadratnog korijena varijance, nalazimo standardnu ​​devijaciju slučajne varijable T.

Dakle, za eksponencijalnu distribuciju, matematičko očekivanje i standardna devijacija su međusobno jednaki i inverzni parametru λ, gdje je λ. intenzitet protoka.

Dakle, izgled m događaja u određenom vremenskom razdoblju odgovara Poissonovoj distribuciji, a vjerojatnost da će vremenski intervali između događaja biti manji od određenog unaprijed određenog broja odgovara eksponencijalnoj distribuciji. Sve su to samo različiti opisi istog stohastičkog procesa.

Primjer SMO-1 .

Kao primjer, razmotrite bankarski sustav koji radi u stvarnom vremenu i opslužuje veliki broj klijenata. U vršnim satima zahtjevi bankovnih šaltera koji rade s klijentima čine Poissonov tok i stižu u prosjeku dva u 1 s (λ = 2.) Tok se sastoji od zahtjeva koji stižu intenzitetom od 2 zahtjeva u sekundi.

Izračunajmo vjerojatnost P ( m) izgled m poruke u 1 s. Kako je λ = 2, onda iz prethodne formule imamo

Zamjena m = 0, 1, 2, 3, dobivamo sljedeće vrijednosti (s točnošću od četiridecimalna mjesta):

Slika 0 - 5 Primjer jednostavnog toka

Moguće je primiti više od 9 poruka u 1 sekundi, ali je vjerojatnost za to vrlo niska (oko 0,000046).

Dobivena distribucija može se prikazati u obliku histograma (prikazano na slici).

Primjer SMO-2.

Uređaj (poslužitelj) koji obrađuje tri poruke u 1s.

Neka postoji oprema koja može obraditi tri poruke u 1 s (µ=3). U prosjeku se primaju dvije poruke po 1s, au skladu s c Poissonova distribucija. Koliki će udio ovih poruka biti obrađen odmah po primitku?

Vjerojatnost da će brzina dolaska biti manja ili jednaka 3 s dana je izrazom

Ako sustav može obraditi najviše 3 poruke u 1 s, tada je vjerojatnost da neće biti preopterećen

Drugim riječima, 85,71% poruka bit će posluženo odmah, a 14,29% s određenim kašnjenjem. Kao što vidite, rijetko će se dogoditi kašnjenje u obradi jedne poruke dulje od vremena obrade 3 poruke. Vrijeme obrade 1 poruke je prosječno 1/3 s. Stoga će kašnjenje veće od 1s biti rijetka pojava, što je sasvim prihvatljivo za većinu sustava.

Primjer SMO- 3

· Ako je šalter u banci zauzet 80% svog radnog vremena, a ostatak vremena provodi čekajući klijente, tada se može smatrati uređajem s faktorom iskorištenja 0,8.

· Ako se komunikacijskim kanalom prenose 8-bitni simboli brzinom od 2400 bps, tj. prenosi se maksimalno 2400/8 simbola u 1 s, a gradimo sustav u kojem je ukupna količina podataka 12000 simbola. poslano s različitih uređaja kroz komunikacijski kanal po minuti najvećeg opterećenja (uključujući sinkronizaciju, simbole za kraj poruke, kontrolu itd.), tada je stopa iskorištenja opreme komunikacijskog kanala tijekom te minute jednaka

· Ako stroj za pristup datoteci izvrši 9000 pristupa datotekama tijekom sata zauzetosti, a prosječno vrijeme po pristupu je 300 ms, tada je stopa iskorištenja hardvera u vršnom satu stroja za pristup

Koncept iskorištenja opreme često će se koristiti. Što je iskorištenost opreme bliža 100%, to je veće kašnjenje i duži su redovi.

Pomoću prethodne formule možete izraditi tablice vrijednosti Poissonove funkcije iz kojih možete odrediti vjerojatnost dolaskam ili više poruka u određenom vremenskom razdoblju. Na primjer, ako postoji prosječno 3,1 poruka u sekundi [tj. e. λ = 3.1], tada je vjerojatnost primanja 5 ili više poruka u danoj sekundi 0,2018 (zam = 5 u tablici). Ili u analitičkom obliku

Koristeći ovaj izraz, analitičar sustava može izračunati vjerojatnost da sustav neće zadovoljiti zadani kriterij opterećenja.

Često se početni izračuni mogu napraviti za vrijednosti opterećenja opreme

ρ ≤ 0,9

Ove vrijednosti mogu se dobiti pomoću Poissonovih tablica.

Neka je opet prosječna stopa pristizanja poruka λ = 3,1 poruka/s. Iz tablica proizlazi da je vjerojatnost primanja 6 ili više poruka u 1 sekundi 0,0943. Stoga se ovaj broj može uzeti kao kriterij opterećenja za početne izračune.

10.6.2. Projektantski zadaci

Ako poruke stignu na uređaj nasumično, uređaj troši dio svog vremena na obradu ili servisiranje svake poruke, što rezultira stvaranjem reda čekanja. Red u banci čeka oslobađanje blagajnika i njegovog računala (terminala). Red poruka u ulaznom međuspremniku računala čeka obradu od strane procesora. Red zahtjeva za nizove podataka čeka da se kanali oslobode, itd. Redovi se mogu formirati na svim uskim grlima u sustavu.

Što je veća stopa iskorištenja opreme, to su dulji redovi čekanja. Kao što će biti prikazano u nastavku, moguće je dizajnirati zadovoljavajući operativni sustav s faktorom iskorištenja ρ = 0,7, ali koeficijent veći od ρ > 0,9 može dovesti do pogoršanja kvalitete usluge. Drugim riječima, ako veza skupnih podataka ima 20% opterećenja, malo je vjerojatno da će na njoj biti čekanja. Ako se učitava; je 0,9, tada će se u pravilu formirati redovi čekanja, ponekad vrlo veliki.

Faktor iskorištenja opreme jednak je omjeru opterećenja opreme i maksimalnog opterećenja koje ta oprema može podnijeti, odnosno jednak omjeru vremena zauzetosti opreme i ukupnog vremena njenog rada.

Prilikom projektiranja sustava, uobičajeno je procijeniti faktor iskorištenja za različite vrste opreme; relevantni primjeri bit će dati u narednim poglavljima. Poznavanje ovih koeficijenata omogućuje vam izračun čekanja za odgovarajuću opremu.

· Kolika je duljina čekanja?

· Koliko će vremena trebati?

Na ove vrste pitanja može se odgovoriti pomoću teorije čekanja.

10.6.3. Sustavi čekanja, njihove klase i glavne karakteristike

Za QS, tokovi događaja su tokovi aplikacija, tokovi "servisnih" aplikacija, itd. Ako ti tokovi nisu Poissonov (Markovljev proces), matematički opis procesa koji se odvijaju u QS-u postaje neusporedivo složeniji i zahtijeva glomazniji aparata, dovođenje u analitičke formule moguće je samo u najjednostavnijim slučajevima.

Međutim, aparatura "Markovljeve" teorije čekanja također može biti korisna u slučaju kada se proces koji se odvija u QS-u razlikuje od Markovljevog; uz njegovu pomoć mogu se približno procijeniti karakteristike performansi QS-a. Treba napomenuti da što je QS složeniji, što ima više servisnih kanala, to su točnije približne formule dobivene Markovljevom teorijom. Osim toga, u nizu slučajeva, za donošenje informiranih odluka o upravljanju radom QS-a, nije potrebno točno poznavanje svih njegovih karakteristika, često je dovoljno samo okvirno, okvirno poznavanje.

QS se klasificiraju u sustave sa:

· odbijanja (s gubicima). U ovakvim sustavima zahtjev primljen u trenutku kada su svi kanali zauzeti dobiva “odbijenicu”, napušta QS i ne sudjeluje u daljnjem procesu usluživanja.

· čekanje (s redom čekanja). U takvim sustavima zahtjev koji stigne u trenutku kada su svi kanali zauzeti stavlja se u red čekanja i čeka dok se jedan od kanala ne oslobodi. Kada se kanal oslobodi, jedan od zahtjeva u redu čekanja prihvaća se za uslugu.

Usluga (disciplina čekanja) u sustavu čekanja može se

· naredio (prijave se obrađuju redoslijedom pristizanja),

· poremećen(prijave se poslužuju nasumičnim redoslijedom) ili

· složeni (posljednji zahtjev se bira prvi iz reda čekanja).

· Prioritet

o sa statičkim prioritetom

o s dinamičkim prioritetom

(u potonjem slučaju, prije tet se npr. može povećavati s trajanjem čekanja na zahtjev).

Sustavi čekanja dijele se na sustave

· s neograničenim čekanjem i

· s ograničenim čekajući.

U sustavima s neograničenim čekanjem svaki zahtjev koji stigne u trenutku kada nema slobodnih kanala ulazi u red čekanja i “strpljivo” čeka da kanal postane slobodan i prihvati ga za uslugu. Svaki zahtjev koji primi CMO će prije ili kasnije biti servisiran.

U sustavima s ograničenim čekanjem nametnuta su određena ograničenja na boravak aplikacije u redu čekanja. Mogu se primjenjivati ​​ova ograničenja

· duljina čekanja (broj aplikacija istovremeno u redu čekanja u sustavu s ograničenom duljinom čekanja),

· vrijeme koje je aplikacija provela u redu čekanja (nakon određenog vremena stajanja u redu čekanja, aplikacija izlazi iz reda čekanja i napušta sustav s ograničenim vremenom čekanja),

· ukupno vrijeme boravka aplikacije u CMO-u

itd.

Ovisno o vrsti QS-a, određene vrijednosti (pokazatelji učinka) mogu se koristiti pri procjeni njegove učinkovitosti. Na primjer, za QS s kvarovima, jedna od najvažnijih karakteristika njegove produktivnosti je tzv apsolutna propusnost prosječan broj zahtjeva koje sustav može poslužiti po jedinici vremena.

Uz apsolut često se smatra relativna propusnost QS je prosječni udio dolaznih aplikacija koje sustav opslužuje (omjer prosječnog broja aplikacija koje sustav servisira po jedinici vremena prema prosječnom broju aplikacija primljenih tijekom tog vremena).

Osim apsolutne i relativne propusnosti, pri analizi QS-a s kvarovima, ovisno o zadatku istraživanja, mogu nas zanimati i druge karakteristike, na primjer:

· prosječan broj zauzetih kanala;

· prosječno relativno vrijeme zastoja sustava u cjelini i pojedinog kanala

itd.

Pitanja s očekivanjem imaju nešto drugačije karakteristike. Očito, za QS s neograničenim čekanjem, i apsolutna i relativna propusnost gube svoje značenje, budući da je svaki primljeni zahtjev ranoili će biti posluženo kasnije. Za takav QS važne karakteristike su:

· prosječan broj prijava u redu čekanja;

· prosječan broj prijava u sustavu (u redu i na usluzi);

· prosječno vrijeme čekanja na zahtjev u redu čekanja;

· prosječno vrijeme koje aplikacija ostaje u sustavu (u redu čekanja i na usluzi);

kao i druge karakteristike očekivanja.

Za QS s ograničenim čekanjem interesantne su obje grupe karakteristika: i apsolutna i relativna propusnost i karakteristike čekanja.

Za analizu procesa koji se odvija u QS-u bitno je poznavati glavne parametre sustava: broj kanala P, intenzitet protoka aplikacijaλ , performanse svakog kanala (prosječan broj zahtjeva μ koje kanal opslužuje po jedinici vremena), uvjeti za formiranje reda čekanja (ograničenja, ako postoje).

Ovisno o vrijednostima ovih parametara izražavaju se karakteristike izvedbe QS-a.

10.6.4. Formule za izračunavanje karakteristika QS-a za slučaj servisiranja jednim uređajem

Slika 0 - 6 Model sustava čekanja s redom čekanja

Takve redove čekanja mogu stvoriti poruke na ulazu procesora koje čekaju na obradu. Mogu se pojaviti tijekom rada pretplatničkih točaka spojenih na komunikacijski kanal s više točaka. Slično se stvaraju redovi automobila na benzinskim postajama. Međutim, ako postoji više od jednog servisnog ulaza, imamo red s mnogo uređaja i analiza postaje kompliciranija.

Razmotrimo slučaj najjednostavnijeg toka servisnih zahtjeva.

Svrha predstavljene teorije čekanja je aproksimacija prosječne veličine reda čekanja, kao i prosječnog vremena koje poruke provedu čekajući u redu čekanja. Također je preporučljivo procijeniti koliko često red čekanja prelazi određenu duljinu. Ove informacije će nam omogućiti da izračunamo, na primjer, potrebnu količinu međuspremnika za pohranu redova poruka i odgovarajućih programa, potreban broj komunikacijskih linija, potrebne veličine međuspremnika za čvorišta, itd. Bit će moguće procijeniti vremena odziva.

Svaka od karakteristika varira ovisno o korištenom sredstvu.

Razmotrite red čekanja s jednim poslužiteljem. Prilikom projektiranja računalnog sustava, većina redova čekanja ove vrste izračunava se pomoću zadanih formula. koeficijent varijacije vremena usluge

Khinchin-Polacek formula se koristi za izračunavanje duljina čekanja pri projektiranju informacijskih sustava. Koristi se u slučaju eksponencijalne raspodjele vremena dolaska za bilo koju raspodjelu vremena usluge i bilo koju kontrolnu disciplinu, sve dok izbor sljedeće poruke za uslugu ne ovisi o vremenu usluge.

Pri projektiranju sustava postoje situacije u kojima nastaju redovi kada disciplina upravljanja nedvojbeno ovisi o vremenu usluge. Na primjer, u nekim slučajevima možemo odabrati kraće poruke za prioritetnu uslugu kako bismo postigli niže prosječno vrijeme usluge. Kada upravljate komunikacijskom linijom, možete dodijeliti veći prioritet ulaznim porukama nego izlaznim porukama jer su prve kraće. U takvim slučajevima više nije potrebno koristiti Khinchinovu jednadžbu

Većina servisnih vremena u informacijskim sustavima nalazi se negdje između ova dva slučaja. Vremena održavanja jednaka konstantnoj vrijednosti su rijetka. Čak ni vrijeme pristupa tvrdom disku nije konstantno zbog različitih položaja nizova podataka na površini. Jedan primjer koji ilustrira slučaj konstantnog vremena usluge je zauzimanje komunikacijske linije za prijenos poruka fiksne duljine.

S druge strane, širenje vremena usluge nije tako veliko kao u slučaju njegove proizvoljne ili eksponencijalne raspodjele, tj.σs rijetko dostiže vrijednostits. Ovaj se slučaj ponekad smatra "najgorim slučajem" i stoga se koriste formule koje se odnose na eksponencijalnu distribuciju vremena usluge. Takav izračun može dati malo napuhane veličine redova i vremena čekanja u njima, ali ova pogreška barem nije opasna.

Eksponencijalna distribucija vremena usluge, naravno, nije najgori slučaj s kojim se u stvarnosti treba suočiti. Međutim, ako se ispostavi da su vremena usluge dobivena iz proračuna čekanja raspodijeljena lošije od eksponencijalno raspodijeljenih vremena, to je često znak upozorenja za dizajnera. Ako je standardna devijacija veća od prosjeka, obično je potrebno prilagoditi izračune.

Razmotrite sljedeći primjer. Postoji šest vrsta poruka s servisnim vremenima od 15, 20, 25, 30, 35 i 300. Broj poruka svake vrste je isti. Standardna devijacija navedenih vremena nešto je viša od njihovog prosjeka. Posljednja vrijednost servisnog vremena mnogo je veća od ostalih. To će uzrokovati da poruke stoje u redu znatno duže nego da su vremena usluge istog reda veličine. U ovom slučaju, prilikom projektiranja, preporučljivo je poduzeti mjere za smanjenje duljine čekanja. Na primjer, ako su ti brojevi povezani s duljinom poruke, onda bi bilo vrijedno podijeliti vrlo dugačke poruke na dijelove.

10.6.6. Primjer izračuna

Prilikom projektiranja bankovnog sustava poželjno je znati broj klijenata koji će morati čekati u redu za jednog šaltera tijekom vršnih sati.

Vrijeme odziva sustava i njegova standardna devijacija izračunavaju se uzimajući u obzir vrijeme unosa podataka s radne stanice, ispisa i izvršenja dokumenta.

Radnje blagajnice bile su tempirane. Vrijeme usluge ts jednako je ukupnom vremenu koje je blagajnik proveo na klijentu. Stopa iskorištenosti blagajnika ρ proporcionalna je vremenu koje je on zauzet. Ako je λ broj kupaca tijekom vršnih sati, tada je ρ za blagajnika jednak

Pretpostavimo da tijekom vršnih sati ima 30 kupaca po satu. U prosjeku, blagajnik potroši 1,5 minuta po kupcu. Zatim

ρ =(1,5 * 30) / 60 = 0,75

tj. Blagajna se koristi 75%.

Broj ljudi u redu može se brzo procijeniti pomoću grafikona. Iz njih slijedi da ako je ρ = 0,75, tada je prosječan broj ljudi nqu blagajničkom redu leži između 1,88 i 3,0 ovisno o standardnoj devijaciji za ts .

Pretpostavimo da je mjerenje standardne devijacije za ts dao je vrijednost od 0,5 min. Zatim

σ s = 0,33 t s

Iz grafikona na prvoj slici nalazimo da je nq = 2,0, odnosno na blagajni će u prosjeku čekati dva klijenta.

Ukupno vrijeme koje kupac provede na blagajni može se pronaći kao

t ∑ = t q + t s = 2,5 min + 1,5 min = 4 min

gdje t s izračunato pomoću Khinchin-Polacek formule.

10.6.7. Faktor pojačanja

Analizirajući krivulje prikazane na slikama, vidimo da kada je oprema koja opslužuje red iskorištena više od 80%, krivulje počinju rasti alarmantnom brzinom. Ova činjenica je vrlo važna pri projektiranju sustava za prijenos podataka. Ako dizajniramo sustav s više od 80% iskorištenosti hardvera, tada blagi porast prometa može uzrokovati pad performansi sustava ili čak uzrokovati pad.

Povećanje dolaznog prometa za mali broj x%. dovodi do povećanja veličine čekanja za otprilike

Ako je stopa iskorištenja opreme 50%, tada je to povećanje jednako 4ts% za eksponencijalnu distribuciju vremena usluge. Ali ako je stopa iskorištenja hardvera 90%, tada je povećanje veličine reda čekanja 100ts%, što je 25 puta više. Lagano povećanje opterećenja pri iskorištenosti opreme od 90% rezultira 25-strukim povećanjem veličine čekanja u usporedbi sa slučajem iskorištenosti opreme od 50%.

Slično tome, vrijeme provedeno u redu čekanja povećava se za

Uz eksponencijalno raspodijeljeno vrijeme servisiranja, ova vrijednost ima vrijednost od 4 t s 2 za faktor iskorištenja opreme jednak 50% i 100 t s 2 za koeficijent od 90%, dakle opet 25 puta gore.

Osim toga, za niske stope iskorištenja opreme, učinak promjena u σs na veličinu reda je zanemariv. Međutim, za velike koeficijente promjena σ s uvelike utječe na veličinu reda čekanja. Stoga je pri projektiranju sustava s visokim iskorištenjem opreme poželjno dobiti točne informacije o parametruσ s. Netočnost pretpostavke o eksponencijalnosti t distribucijesje najuočljiviji pri velikim vrijednostima ρ. Štoviše, ako se vrijeme usluge iznenada poveća, što je moguće u komunikacijskim kanalima pri prijenosu dugih poruka, tada će se u slučaju velikog ρ formirati značajan red.

Nerijetko je pri analizi ekonomskih sustava potrebno riješiti takozvane probleme čekanja koji se javljaju u sljedećoj situaciji. Analizirajmo sustav za održavanje automobila koji se sastoji od niza stanica različitog kapaciteta. Na svakoj stanici (elementu sustava) mogu se pojaviti najmanje dvije tipične situacije:

1. broj zahtjeva je prevelik za određenu stanicu, nastaju redovi i morate platiti kašnjenja u usluzi;
2. stanica prima premalo zahtjeva i sada moramo uzeti u obzir gubitke uzrokovane zastojem stanice.

Jasno je da je svrha analize sustava u ovom slučaju utvrditi neki omjer između gubitaka prihoda zbog redovi čekanja i gubitke zbog samo ja stanice.

Teorija čekanja– poseban dio teorije sustava je dio teorije vjerojatnosti u kojem se sustavi čekanja proučavaju pomoću matematičkih modela.

Sustav čekanja (QS) je model koji uključuje: 1) nasumični tok zahtjeva, poziva ili klijenata kojima je potrebna usluga; 2) algoritam za izvođenje ove usluge; 3) kanali (uređaji) za uslugu.

Primjeri pružatelja usluga su blagajne, benzinske postaje, zračne luke, prodavači, frizeri, liječnici, telefonske centrale i drugi objekti u kojima se servisiraju određeni zahtjevi.

Problem teorije čekanja sastoji se od izrade preporuka za racionalnu izgradnju QS-a i racionalnu organizaciju njihova rada kako bi se osigurala visoka učinkovitost usluge uz optimalne troškove.

Glavna značajka zadataka ove klase je očigledna ovisnost rezultata analize i dobivenih preporuka o dva vanjska čimbenika: učestalosti prijema i složenosti naloga (a time i vremenu njihovog izvršenja).

Predmet teorije čekanja je uspostavljanje odnosa između prirode toka zahtjeva, performansi pojedinog kanala usluge, broja kanala i učinkovitosti usluge.

Kao karakteristike sustava smatraju se:

• prosječni postotak prijava koje su odbijene i ostavljaju sustav neobrađenim;
• prosječno vrijeme zastoja pojedinih kanala i sustava u cjelini;
• prosječno vrijeme čekanja u redu;
• vjerojatnost da će primljeni zahtjev biti odmah servisiran;
• zakon raspodjele duljine čekanja i drugi.

Dodajmo da aplikacije (zahtjevi) u QS stižu nasumično (u nasumično vrijeme), s točkama kondenzacije i razrijeđenosti. Vrijeme usluge za svaki zahtjev je također nasumično, nakon čega se kanal usluge oslobađa i spreman je ispuniti sljedeći zahtjev. Svaki QS, ovisno o broju kanala i njihovoj izvedbi, ima određeni kapacitet. QS propusnost Može biti apsolutni(prosječan broj isporučenih zahtjeva po jedinici vremena) i relativna(prosječni omjer broja isporučenih zahtjeva i broja podnesenih zahtjeva).

3.1 Modeli sustava čekanja.

Svaki QS se može okarakterizirati izrazom: (a B C D E F) , Gdje

a - raspodjela ulaznog toka aplikacija;

b - raspodjela izlaznog toka aplikacija;

c – konfiguracija servisnog mehanizma;

d – disciplina čekanja;

e – blok čekanja;

f – kapacitet izvora.

Sada pogledajmo pobliže svaku karakteristiku.

Ulazni tijek aplikacija– broj prijava zaprimljenih u sustav. Karakterizira ga intenzitet ulaznog toka l.

Izlazni tijek aplikacija– broj aplikacija koje sustav opslužuje. Karakterizira intenzitet izlaznog toka m.

sistemska konfiguracija podrazumijeva ukupan broj kanala i servisnih čvorova. QS može sadržavati:

1. jedan kanal usluge (jedna pista, jedan prodavač);
2. uključujući jedan servisni kanal nekoliko uzastopnih čvorova(kantina, klinika, pokretna traka);
3. nekoliko kanala iste vrste usluge povezane paralelno (benzinske postaje, informativna služba, željeznička stanica).

Dakle, moguće je razlikovati jednokanalni i višekanalni QS.

S druge strane, ako su svi servisni kanali u QS-u zauzeti, tada pristupljena aplikacija može ostati u redu čekanja ili može napustiti sustav (npr. štedionica i telefonska centrala). U ovom slučaju govorimo o sustavima s redom (čekanja) i sustavima s kvarovima.

Red– ovo je skup zahtjeva koji su ušli u sustav na uslugu i čekaju uslugu. Red karakterizira duljina reda i njegova disciplina.

Disciplina čekanja– ovo je pravilo za servisiranje zahtjeva iz reda čekanja. Glavne vrste čekanja uključuju sljedeće:

1. PERPPO (first come first served) najčešći je tip;
2. POSPPO (last in, first served);
3. ROP (slučajni odabir prijava) – iz baze podataka.
4. PR – prioritetna usluga.

Dužina čekanja Može biti

• neograničeno - tada se govori o sustavu s čistim očekivanjem;
• jednaka nuli - tada govore o sustavu s kvarovima;
• ograničena duljinom (sustav mješovitog tipa).

Blok čekanja– “kapacitet” sustava – ukupan broj prijava u sustavu (u redu i na usluzi). Tako, e=c+d.

Kapacitet izvora generiranje zahtjeva za uslugu je maksimalni broj zahtjeva koje može primiti QS. Na primjer, u zračnoj luci izvorni kapacitet ograničen je brojem svih postojećih zrakoplova, a izvorni kapacitet telefonske centrale jednak je broju stanovnika Zemlje, tj. može se smatrati neograničenim.

Broj QS modela odgovara broju mogućih kombinacija ovih komponenti.

3.2 Tijek zahtjeva za unos.

Sa svakim vremenskim razdobljem [ a, a+ T ], povežite slučajnu varijablu x, jednako broju zahtjeva koje je sustav primio tijekom vremena T.

Tijek zahtjeva se zove stacionarni, ako zakon distribucije ne ovisi o početnoj točki intervala A, ali ovisi samo o duljini zadanog intervala T. Na primjer, tijek zahtjeva prema telefonskoj centrali tijekom dana ( T=24 sata) ne može se smatrati stacionarnim, već od 13 do 14 sati ( T=60 minuta) – možete.

Potok se zove bez naknadnog djelovanja, ako povijest toka ne utječe na dolazak zahtjeva u budućnosti, tj. zahtjevi su neovisni jedni o drugima.

Potok se zove obični, ako u sustav ne može ući više od jednog zahtjeva u vrlo kratkom vremenskom razdoblju. Na primjer, protok do frizera je običan, ali do matičnog ureda - ne. Ali, ako je kao slučajna varijabla x razmotriti parove prijava koje je primio matični ured, tada će takav tijek biti običan (to jest, ponekad se izvanredni tok može svesti na običan).

Potok se zove najjednostavniji, ako je stacionarna, bez naknadnog djelovanja i obična.

Glavni teorem. Ako je tok najjednostavniji, onda je r.v. X[a. a+ T] distribuira se prema Poissonovom zakonu, tj. .

Korolar 1. Najjednostavnije strujanje naziva se i Poissonovo strujanje.

Korolar 2. M(x)= M(X [ a , a + T ] )= lT, tj. tijekom T lT aplikacije. Dakle, po jedinici vremena sustav prima prosječno l aplikacije. Ova količina se zove intenzitet ulazni tok.

Razmotrimo PRIMJER .

Studio u prosjeku prima 3 prijave dnevno. Smatrajući tok najjednostavnijim, pronađite vjerojatnost da će tijekom sljedeća dva dana broj prijava biti najmanje 5.

Riješenje.

Prema uvjetima problema, l=3, T=2 dana, ulazni protok je Poisson, n ³5. pri odlučivanju zgodno je uvesti suprotan događaj koji se sastoji u tome da tijekom vremena T pristići će manje od 5 prijava. Stoga, prema Poissonovoj formuli, dobivamo

^

3.3 Status sustava. Matrica i prijelazni graf.

U slučajnom vremenskom trenutku, QS se mijenja iz jednog stanja u drugo: mijenja se broj zauzetih kanala, broj zahtjeva i čekanja itd. Dakle, QS s n kanala i duljina reda čekanja jednaka m, može biti u jednom od sljedećih stanja:

E 0 – svi kanali su besplatni;

E 1 – jedan kanal je zauzet;

E n– svi kanali su zauzeti;

E n +1 – svi kanali su zauzeti i jedan zahtjev je u redu čekanja;

E n + m– svi kanali i sva mjesta u redu su zauzeti.

Sličan sustav s kvarovima može biti u državama E 0 – E n .

Za QS s čistim očekivanjem postoji beskonačan broj stanja. Tako, država E n QS u određenom trenutku t – ovo je količina n aplikacije (zahtjevi) koji se nalaze u sustavu u određenom trenutku, tj. n= n(t) - slučajna vrijednost, E n (t) su ishodi ove slučajne varijable, i P n (t) – vjerojatnost da je sustav u stanju E n .

Već smo upoznati sa stanjem sustava. Imajte na umu da nisu sva stanja sustava ekvivalentna. Stanje sustava naziva se izvor, ako sustav može izaći iz ovog stanja, ali se ne može vratiti u njega. Stanje sustava naziva se izoliran, ako sustav ne može izaći ili ući u ovo stanje.

Za vizualizaciju stanja sustava koriste se dijagrami (tzv. grafovi prijelaza) u kojima strelice označavaju moguće prijelaze sustava iz jednog stanja u drugo, kao i vjerojatnosti takvih prijelaza.

Slika 3.1 – graf prijelaza

Comp.	E 0	E 1	E 2
E 0	P 0,0	P 0,1	P 0,2
E 1	P 1.0	P 1.1	R 1.2
E 2	R 2.0	R 2.2	R 2.2

Također je ponekad zgodno koristiti prijelaznu matricu. U ovom slučaju prvi stupac označava početna stanja sustava (struja), a zatim su dane vjerojatnosti prijelaza iz tih stanja u druga.

Budući da će se sustav sigurno preseliti s jedne

stanja u drugu, tada je zbroj vjerojatnosti u svakom retku uvijek jednak jedan.

3.4 Jednokanalni QS.

3.4.1 Jednokanalni QS s kvarovima.

Razmotrit ćemo sustave koji ispunjavaju zahtjeve:

(P/E/1):(–/1/¥) . Pretpostavimo također da vrijeme potrebno za servisiranje zahtjeva ne ovisi o broju zahtjeva koji ulaze u sustav. Ovdje i dolje, "P" znači da je ulazni protok raspoređen prema Poissonovom zakonu, tj. najjednostavnije, "E" znači da je izlazni tok raspoređen prema eksponencijalnom zakonu. Također ovdje i niže, osnovne formule su dane bez dokaza.

Za takav sustav moguća su dva stanja: E 0 – sustav je besplatan i E 1 – sustav je zauzet. Kreirajmo matricu prijelaza. Idemo uzeti Dt- beskonačno malo vremensko razdoblje. Neka je događaj A taj u sustavu u vremenu Dt primljen je jedan zahtjev. Događaj B je taj tijekom vremena Dt jedan zahtjev je uručen. Događaj A ja , k- tijekom Dt sustav će prijeći iz države E ja u stanju E k. Jer l je intenzitet ulaznog protoka, zatim tijekom vremena Dt u prosjeku ulazi u sustav l*Dt zahtjevi. Odnosno, vjerojatnost primanja jednog zahtjeva P(A)=l* Dt, i vjerojatnost suprotnog događaja R(Ā)=1-l*Dt.P(B)=F(Dt)= P(b< D t)=1- e - m D t = m Dt– vjerojatnost servisiranja zahtjeva u roku Dt. Zatim A 00 - zahtjev neće biti zaprimljen ili će biti zaprimljen ali će biti servisiran. A 00 =Ā+A * V. P 00 =1 - l*Dt. (uzeli smo u obzir to (Dt) 2 – infinitezimalna vrijednost)

A 01 – zahtjev će biti primljen, ali neće biti servisiran. A 01 =A * . R 01 = l*Dt.

A 10 – aplikacija će biti servisirana i neće biti nove. A 10 =B * Ā. R 10 = doktor medicinet.

A 11 – aplikacija se neće servisirati ili će biti primljena nova koja još nije servisirana. A 11 = +B * A.P 01 = 1- doktor medicinet.

Dakle, dobivamo matricu prijelaza:

Comp.	E 0	E 1
E 0	1-l * Dt	l * Dt
E 1	m * Dt	1-m * Dt

Mogućnost zastoja i kvara sustava.

Pronađimo sada vjerojatnost da je sustav u stanju E 0 u bilo koje vrijeme t(oni. R 0 ( t) ). Graf funkcije
prikazano na slici 3.2.

Asimptota grafa je ravna linija
.

Očito, počevši od nekog trenutka t,

1

Slika 3.2

Napokon smo to shvatili
I
, Gdje R 1 (t) – vjerojatnost da u trenutku vremena t sustav je zauzet (tj. nalazi se u stanju E 1 ).

Očito je da na početku rada QS-a proces koji je u tijeku neće biti stacionaran: to će biti „prijelazni“, nestacionarni način. Nakon nekog vremena (koje ovisi o intenzitetima ulaznih i izlaznih tokova) ovaj proces će zamrijeti i sustav će prijeći u stacionarno, ustaljeno stanje rada, a probabilističke karakteristike više neće ovisiti o vremenu.

Stacionarni način rada i faktor opterećenja sustava.

Ako je vjerojatnost da je sustav u stanju E k, tj. R k (t), ne ovisi o vremenu t, onda kažu da je postavljen QS stacionarni način rada raditi. U ovom slučaju vrijednost
nazvao faktor opterećenja sustava(ili smanjena gustoća protoka aplikacija). Zatim za vjerojatnosti R 0 (t) I R 1 (t) dobivamo sljedeće formule:
,
. Također se može zaključiti: Što je veći faktor opterećenja sustava, veća je vjerojatnost kvara sustava (tj. vjerojatnost da je sustav zauzet).

Autopraonica ima jednu jedinicu održavanja. Automobili stižu prema Poissonovoj distribuciji brzinom od 5 automobila/sat. Prosječno vrijeme servisiranja jednog stroja je 10 minuta. Nađite vjerojatnost da će automobil koji se približava pronaći sustav zauzet ako QS radi u stacionarnom načinu rada.

Riješenje. Prema uvjetima problema, l=5, m g =5/6. Moramo pronaći vjerojatnost R 1 – vjerojatnost kvara sustava.
.

3.4.2 Jednokanalni QS s neograničenom duljinom čekanja.

Razmotrit ćemo sustave koji zadovoljavaju zahtjeve: (P/E/1):(d/¥/¥). Sustav može biti u jednom od stanja E 0 , …, E k, ... Analiza pokazuje da nakon nekog vremena takav sustav počinje raditi u stacionarnom režimu ako je intenzitet izlaznog protoka veći od intenziteta ulaznog protoka (tj. faktor opterećenja sustava je manji od jedan). Uzimajući u obzir ovaj uvjet, dobivamo sustav jednadžbi

rješavajući koje ćemo naći da . Dakle, pod uvjetom da g<1, получим
Konačno,
I
– vjerojatnost da je QS u stanju E k u slučajnom trenutku u vremenu.

Prosječna izvedba sustava.

Zbog neravnomjernog pristizanja zahtjeva u sustav i fluktuacija u vremenu servisa, u sustavu se formira red čekanja. Za takav sustav može se istražiti:

• n – broj zahtjeva u QS-u (u redu i na usluzi);
• v – duljina čekanja;
• w – vrijeme čekanja na početak usluge;
• w 0 – ukupno vrijeme provedeno u sustavu.

Zanimat će nas prosječne karakteristike(tj. uzimamo matematičko očekivanje slučajnih varijabli koje razmatramo i zapamtimo da g<1).

– prosječan broj aplikacija u sustavu.

– prosječna duljina čekanja.

– prosječno vrijeme čekanja na početak usluge, tj. vrijeme čekanja u redu.

– prosječno vrijeme koje aplikacija provede u sustavu – u redu i na servisu.

U autopraonici postoji jedan blok za servis i postoji mjesto za red. Automobili stižu prema Poissonovoj distribuciji brzinom od 5 automobila/sat. Prosječno vrijeme servisiranja jednog stroja je 10 minuta. Pronađite sve prosječne karakteristike QS-a.

Riješenje. l=5, m=60min/10min = 6. Faktor opterećenja g =5/6. Zatim prosječan broj automobila u sustavu
, prosječna duljina čekanja
, prosječno vrijeme čekanja na početak usluge
sati = 50 minuta, i na kraju, prosječno vrijeme provedeno u sustavu
sat.

3.4.3 Jednokanalni QS mješovitog tipa.

Pretpostavimo da je duljina reda čekanja m zahtjevi. Zatim, za bilo koga s£ m, vjerojatnost da je QS u stanju E 1+ s, izračunato formulom
, tj. služi se jedna prijava, a druga s prijave su u redu.

Vjerojatnost zastoja sustava je
,

a vjerojatnost kvara sustava je
.

Za svaki su data tri jednokanalna sustava l=5, m =6. Ali prvi je sustav s odbijanjima, drugi je s čistim čekanjem, a treći je s ograničenom duljinom čekanja, m=2. Pronađite i usporedite vjerojatnosti prekida rada ova tri sustava.

Riješenje. Za sve sustave faktor opterećenja g=5/6. Za sustav s kvarovima
. Za čisti sustav čekanja
. Za sustav s ograničenom duljinom čekanja
. Zaključak je očit: što je više aplikacija u redu čekanja, to je manja vjerojatnost zastoja sustava.

3.5 Višekanalni QS.

3.5.1 Višekanalni QS s kvarovima.

Razmotrit ćemo sustave (P/E/s):(-/s/¥) pod pretpostavkom da vrijeme usluge ne ovisi o ulaznom protoku i da sve linije rade neovisno. Višekanalne sustave, osim faktorom opterećenja, možemo karakterizirati i koeficijentom
, Gdje s– broj uslužnih kanala. Proučavanjem višekanalnog QS-a dobivamo sljedeće formule (Erlangove formule) za vjerojatnost da je sustav u stanju E k u nasumično vrijeme:

, k=0, 1, …

Funkcija troška.

Kao i kod jednokanalnih sustava, povećanje faktora opterećenja povećava vjerojatnost kvara sustava. S druge strane, povećanje broja uslužnih linija dovodi do povećanja vjerojatnosti zastoja sustava ili pojedinih kanala. Dakle, potrebno je pronaći optimalan broj uslužnih kanala za dati QS. Prosječan broj besplatnih uslužnih linija može se pronaći pomoću formule
. Uvedimo C( s) – funkcija troška QS ovisno o S 1 – trošak jednog odbijanja (novčana kazna za neispunjen zahtjev) i od S 2 – trošak zastoja jedne linije po jedinici vremena.

Da biste pronašli optimalnu opciju, morate pronaći (i to se može učiniti) minimalnu vrijednost funkcije troška: S(s) = s 1* l * str s +s 2*, čiji je grafikon prikazan na slici 3.3:

Slika 3.3

Pronalaženje minimalne vrijednosti funkcije troška sastoji se od pronalaženja njezinih vrijednosti prvo za s =1, zatim za s =2, zatim za s =3, itd. dok se u nekom koraku vrijednost funkcije C( s) neće postati veći od prethodnog. To znači da je funkcija dosegla svoj minimum i počela rasti. Odgovor će biti broj kanala usluge (vrijednost s), za koju je troškovna funkcija minimalna.

PRIMJER .

Koliko uslužnih linija treba sadržavati QS s kvarovima ako l=2 zahtjeva/sat, m=1 zahtjev/sat, kazna za svaki kvar je 7 tisuća rubalja, trošak zastoja jedne linije je 2 tisuće rubalja. u jedan sat?

Riješenje. g = 2/1=2. S 1 =7, S 2 =2.

Pretpostavimo da QS ima dva servisna kanala, tj. s =2. Zatim
. Stoga, C(2) = c 1 *l*str 2 +s 2 *(2- y*(1-r 2 )) = =7*2*0.4+2*(2-2*0.6)=7.2.

Hajdemo to pretvarati s =3. Zatim
, C(3) = c 1 *l*str 3 +s 2 *
=5.79.

Pretpostavimo da postoje četiri kanala, tj. s =4. Zatim
,
, C(4) = c 1 *l*str 4 +s 2 *
=5.71.

Pretpostavimo da QS ima pet servisnih kanala, tj. s =5. Zatim
, C(5) = 6,7 – više od prethodne vrijednosti. Stoga je optimalan broj servisnih kanala četiri.

3.5.2 Višekanalni QS s redom.

Razmotrit ćemo sustave (P/E/s):(d/d+s/¥) pod pretpostavkom da vrijeme usluge ne ovisi o ulaznom protoku i da sve linije rade neovisno. Reći ćemo da je sustav instaliran stacionarni način rada, ako je prosječan broj dolaznih zahtjeva manji od prosječnog broja zahtjeva opsluženih na svim linijama sustava, tj. l

P(w>0) – vjerojatnost čekanja na početak usluge,
.

Posljednja karakteristika nam omogućuje da riješimo problem određivanja optimalnog broja kanala usluge tako da je vjerojatnost čekanja na početak usluge manja od zadanog broja. Da biste to učinili, dovoljno je izračunati vjerojatnost čekanja uzastopno na s =1, s =2, s=3, itd.

PRIMJER .

SMO je stanica hitne pomoći u maloj četvrti. l=3 poziva na sat, i m= 4 poziva po satu za jedan tim. Koliko posade trebate imati na kolodvoru da vjerojatnost čekanja na polazak bude manja od 0,01?

Riješenje. Faktor opterećenja sustava g =0,75. Pretpostavimo da su na raspolaganju dva tima. Nađimo vjerojatnost čekanja na početak usluge na s =2.
,
.

Pretpostavimo da postoje tri tima, tj. s=3. Prema formulama to dobivamo R 0 =8/17, R(w>0)=0.04>0.01 .

Pretpostavimo da su na stanici četiri tima, tj. s=4. Onda to shvaćamo R 0 =416/881, R(w>0)=0.0077<0.01 . Dakle, na stanici bi trebala biti četiri tima.

3.6 Pitanja za samokontrolu

1. Predmet i zadaci teorije čekanja.
2. SMO, njihovi modeli i oznake.
3. Tijek zahtjeva za unos. Intenzitet ulaznog protoka.
4. Stanje sustava. Matrica i prijelazni graf.
5. Jednokanalni QS s kvarovima.
6. Jednokanalni QS s redom čekanja. Karakteristike.
7. Stacionarni način rada. Faktor opterećenja sustava.
8. Višekanalni QS s kvarovima.
9. Optimizacija troškovne funkcije.
10. Višekanalni QS s redom čekanja. Karakteristike.

3.7 Vježbe za samostalan rad

1. Zalogajnica benzinske postaje ima jedan pult. Automobili stižu prema Poissonovoj distribuciji, s prosjekom od 2 automobila svakih 5 minuta. Za izvršenje narudžbe u prosjeku je dovoljno 1,5 minuta, iako je trajanje usluge raspoređeno po eksponencijalnom zakonu. Nađite: a) vjerojatnost zastoja u boksu; b) prosječne karakteristike; c) vjerojatnost da će broj pristiglih vozila biti najmanje 10.
2. Rentgen omogućava pregled prosječno 7 osoba na sat. Intenzitet posjetitelja je 5 osoba na sat. Uz pretpostavku stacionarnog rada, odredite prosječne karakteristike.
3. Vrijeme servisiranja u QS-u slijedi eksponencijalni zakon,
   m = 7 zahtjeva po satu. Odredite vjerojatnost da je a) vrijeme usluge u rasponu od 3 do 30 minuta; b) zahtjev će biti uslužen unutar jednog sata. Koristite tablicu vrijednosti funkcija e x .
4. Riječna luka ima jedan vez, intenzitet priljeva je 5 plovila dnevno. Intenzitet utovarno-istovarnih radova je 6 brodova dnevno. Imajući u vidu stacionarni način rada, odredite sve prosječne karakteristike sustava.
5. l=3, m=2, kazna za svaki kvar je 5, a cijena zastoja jedne linije je 2?
6. Koji je optimalan broj servisnih kanala koji QS treba imati ako l=3, m =1, kazna za svaki kvar je 7, a cijena zastoja jedne linije je 3?
7. Koji je optimalan broj servisnih kanala koji QS treba imati ako l=4, m=2, kazna za svaki kvar je 5, a cijena zastoja jedne linije je 1?
8. Odrediti broj uzletno-sletnih staza za zrakoplove, uzimajući u obzir zahtjev da vjerojatnost čekanja mora biti manja od 0,05. Istovremeno, intenzitet ulaznog protoka je 27 zrakoplova dnevno, a intenzitet njihove usluge je 30 zrakoplova dnevno.
9. Koliko ekvivalentnih samostalnih pokretnih linija treba imati radionica da bi se osigurao ritam rada u kojem vjerojatnost čekanja proizvoda na obradu treba biti manja od 0,03 (svaki proizvod proizvodi jedna linija). Poznato je da je intenzitet zaprimljenih narudžbi 30 proizvoda na sat, a intenzitet obrade proizvoda po jednoj liniji 36 proizvoda na sat.
10. Kontinuirana slučajna varijabla X distribuira se po eksponencijalnom zakonu s parametrom l=5. Naći funkciju raspodjele, karakteristike i vjerojatnost pogađanja r.v. X u rasponu od 0,17 do 0,28.
11. Prosječan broj poziva koji stignu na PBX u jednoj minuti je 3. Uz pretpostavku da je protok Poissonov, pronađite vjerojatnost da će u 2 minute stići: a) dva poziva; b) manje od dva poziva; c) najmanje dva poziva.
12. U kutiji je 17 dijelova od kojih su 4 neispravna. Sastavljač odabire 5 dijelova nasumično. Odredite vjerojatnost da su a) svi izvađeni dijelovi visoke kvalitete; b) među izvađenim dijelovima 3 su bila neispravna.
13. Koliko kanala treba imati QS s kvarovima ako l=2 zahtjeva/sat, m=1 zahtjev/sat, kazna za svaki kvar je 8 tisuća rubalja, trošak zastoja jedne linije je 2 tisuće rubalja. u jedan sat?

1. Jednokanalni QS s kvarovima.

Primjer. Neka jednokanalni QS s kvarovima predstavlja jedno dnevno mjesto održavanja (DS) za pranje automobila. Prijavu - automobil koji stigne u vrijeme kada je radno mjesto zauzeto - odbija se usluga.

Brzina protoka vozila = 1,0 (vozila na sat).

Prosječno trajanje usluge je 1,8 sati.

Tok automobila i tok usluge su najjednostavniji.

Treba odrediti granične vrijednosti u stabilnom stanju:

Relativna propusnost q;

Apsolutna propusnost A ;

Vjerojatnosti neuspjeha P otvoriti.

Treba usporediti stvarni QS propusnost sa nominalni, što bi bilo da je svaki automobil servisiran točno 1,8 sati i da su automobili išli jedan za drugim bez pauze.

2. Jednokanalni QS s čekanjem

Karakteristike sustava

Ø SMO ima jedan kanal.

Ø Dolazni tijek zahtjeva za uslugama je najjednostavniji tok s intenzitetom.

Ø Intenzitet protoka usluge jednak je m (tj., u prosjeku, kontinuirano zauzet kanal će izdati m servisiranih zahtjeva).

Ø Trajanje usluge je slučajna varijabla podložna zakonu eksponencijalne distribucije.

Ø Tok usluge je najjednostavniji Poissonov tok događaja.

Ø Zahtjev primljen kada je kanal zauzet nalazi se u redu i čeka uslugu.

Grafikon stanja

QS stanja imaju sljedeće tumačenje:

S 0 - "besplatan kanal";

S 1 - "kanal zauzet" (nema čekanja);

S 2 - "kanal zauzet" (jedan zahtjev je u redu);

…………………………………………………….

S n- “kanal zauzet” ( n-1 prijava je u redu);

S N- “kanal zauzet” ( N- 1 prijava je u redu).

Stacionarni proces u ovom sustavu opisuje se sljedećim sustavom algebarskih jednadžbi:

Rješenje sustava jednadžbi je:

3. Jednokanalni QS s ograničenim redom čekanja.

Dužina čekanja :( N - 1)

Karakteristike sustava:

1. Vjerojatnost kvara usluge sustava:

2. Relativna propusnost sustava:

3. Apsolutna propusnost sustava:

4. Prosječan broj prijava u sustavu:

5. Prosječno vrijeme koje aplikacija ostaje u sustavu:

6. Prosječna duljina boravka klijenta (zahtjeva) u redu čekanja:

7. Prosječan broj prijava (klijenata) u redu (duljina čekanja):

Primjer.

Specijalizirani dijagnostički post je jednokanalni QS.

Broj parkirališta za automobile koji čekaju dijagnostiku je ograničen i iznosi 3 [( N- 1) = 3]. Ako su sva parkirna mjesta zauzeta, odnosno već su tri automobila u redu, tada sljedeći automobil koji stigne na dijagnostiku neće biti stavljen u red za servis.

Protok automobila koji dolaze na dijagnostiku raspoređen je prema Poissonovom zakonu i ima intenzitet od 0,85 (automobila na sat).

Vrijeme dijagnostike vozila raspoređeno je po eksponencijalnom zakonu i prosječno iznosi 1,05 sati.

4. Jednokanalni QS s čekanjem

nema ograničenja na duljinu čekanja

Uvjeti rada QS-a ostaju nepromijenjeni, uzimajući u obzir činjenicu da N.

Stacionarni način rada takvog QS-a postoji:

za bilo koga n= 0, 1, 2, ... i kada λ < μ .

Sustav jednadžbi koji opisuje rad QS-a:

Rješenje sustava jednadžbi ima oblik:

2. Prosječno trajanje boravka klijenta u sustavu:

3. Prosječan broj klijenata u redu za uslugu:

4. Prosječna duljina vremena koje klijent provede u redu čekanja:

Primjer.

Specijalizirani dijagnostički post je jednokanalni QS. Broj parking mjesta za automobile koji čekaju dijagnostiku je neograničen. Protok automobila koji dolaze na dijagnostiku raspoređen je prema Poissonovom zakonu i ima intenzitet λ = 0,85 (automobila na sat). Vrijeme dijagnostike vozila raspoređeno je po eksponencijalnom zakonu i prosječno iznosi 1,05 sati.

Potrebno je odrediti vjerojatnosne karakteristike dijagnostičke stanice koja radi u stacionarnom načinu rada.

Kao rezultat rješavanja problema, potrebno je odrediti konačne vrijednosti sljedećih vjerojatnosnih karakteristika:

ü vjerojatnost stanja sustava (dijagnostička stanica);

ü prosječan broj automobila u sustavu (na servisu i u redu čekanja);

ü prosječno trajanje boravka vozila u sustavu (za uslugu i u redu čekanja);

ü prosječan broj automobila u redu za servis;

ü prosječno trajanje boravka automobila u redu čekanja.

1. Parametar servisnog protoka i smanjeni intenzitet protoka vozila:

μ = 0,952; ψ = 0,893.

2. Granične vjerojatnosti stanja sustava:

P 0 (t) određuje udio vremena tijekom kojeg je dijagnostički post prisiljen biti neaktivan (mirovanje). U primjeru je taj udio 10,7%, jer P 0 (t) = 0,107.

3. Prosječan broj automobila u sustavu

(na usluzi i u redu):

4. Prosječno trajanje boravka klijenta u sustavu

5. Prosječan broj automobila u redu za servis:

6. Prosječna duljina vremena u kojem automobil stoji u redu čekanja:

7. Relativna propusnost sustava:

q= 1, tj. svaki zahtjev koji dođe u sustav bit će servisiran.

8. Apsolutna propusnost:

Prezentacijski dizajn materijala prikazan je u datoteci “TMO”.

Pitanja i zadaci

(prema Afanasyev M.Yu.)

Pitanje 1. Jedan radnik održava trideset tkalačkih stanova, osiguravajući da se pokreću nakon što nit pukne. Model takvog sustava čekanja može se okarakterizirati kao:

1) višekanalni jednofazni s ograničenom populacijom;

2) jednokanalni jednofazni s neograničenom populacijom;

3) jednokanalni višefazni s ograničenom populacijom;

4) jednokanalni jednofazni s ograničenom populacijom;

5) višekanalni jednofazni s neograničenom populacijom.

pitanje 2. U teoriji čekanja, distribucija vjerojatnosti se koristi za opisivanje najjednostavnijeg tijeka zahtjeva koji stižu na ulaz sustava:

1) normalno;

2) eksponencijalni;

3) Poisson;

4) binom;

pitanje 3. U teoriji čekanja pretpostavlja se da je broj zahtjeva u populaciji:

1) fiksni ili varijabilni;

2) ograničeno ili neograničeno;

3) poznato ili nepoznato;

4) slučajni ili deterministički;

5) ništa od navedenog nije točno.

pitanje 4. Dva glavna parametra koja određuju konfiguraciju sustava čekanja su:

1) stopu dolaska i stopu usluge;

2) duljina čekanja i pravilo usluge;

3) raspodjela vremena između zahtjeva i raspodjela vremena usluge;

4) broj kanala i broj faza usluge;

5) ništa od navedenog nije točno.

pitanje 5. U teoriji čekanja, distribucija vjerojatnosti obično se koristi za opisivanje vremena utrošenog na servisiranje zahtjeva:

1) normalno;

2) eksponencijalni;

3) Poisson;

4) binom;

5) ništa od navedenog nije točno.

Pitanje 6. Popravak neispravnih računala na Ekonomskom fakultetu obavljaju tri stručnjaka koji rade istovremeno i neovisno jedan o drugom. Model takvog sustava čekanja može se okarakterizirati kao:

1) višekanalni s ograničenom populacijom;

2) jednokanalni s neograničenom populacijom;

3) jednokanalni s ograničenom populacijom;

4) jednokanalni s ograničenim redom;

5) višekanalni s neograničenom populacijom.

Odgovori na pitanja: 1 -4, 2 - 3, 3 -2, 4 -4, 5 -2, 6 -1.

MREŽNO PLANIRANJE I UPRAVLJANJE

Sustavi mrežnog planiranja i upravljanja (NPS) predstavljaju posebnu vrstu organiziranih sustava upravljanja namijenjenih reguliranju proizvodnih aktivnosti timova. Kao iu ostalim sustavima ove klase, u SPU sustavima “objekt upravljanja” je skupina izvođača koji raspolažu određenim resursima: ljudskim, materijalnim, financijskim. Međutim, ovi sustavi imaju niz značajki, budući da njihovu metodološku osnovu čine metode operacijskih istraživanja, teorija usmjerenih grafova te neki dijelovi teorije vjerojatnosti i matematičke statistike. Neophodno svojstvo sustava planiranja i upravljanja je i sposobnost procjene trenutnog stanja, predviđanja daljnjeg tijeka rada i na taj način utječe na tijek pripreme i proizvodnje kako bi se cijeli niz radova završio u zadanom roku i na najniži trošak.

Trenutno se SPC modeli i metode široko koriste u planiranju i provedbi građevinskih i instalacijskih radova, planiranju trgovinskih aktivnosti, izradi računovodstvenih izvješća, izradi trgovinskog i financijskog plana itd.

Raspon primjene SPU-a vrlo je širok: od zadataka koji se odnose na aktivnosti pojedinaca do projekata u kojima sudjeluju stotine organizacija i deseci tisuća ljudi (na primjer, razvoj i stvaranje velikog teritorijalno-industrijskog kompleksa).

Da bi se izradio plan rada za realizaciju velikih i složenih projekata koji se sastoje od tisuća pojedinačnih studija i operacija, potrebno ga je opisati nekom vrstom matematičkog modela. Takvo sredstvo za opisivanje projekata (kompleksa) je mrežni model.