Matematički modeli sustava čekanja za rješavanje ekonomskih problema. · Prije početka rada provjerite da nema vidljivih oštećenja na opremi i žicama

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:

· kvarovi (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 primljenih aplikacija koje je sustav opslužio (omjer prosječnog broja aplikacija koje je sustav opslužio po jedinici vremena prema prosječnom broju primljenih aplikacija 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 koliki će broj klijenata 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.

Markovljev slučajni proces s diskretnim stanjima i kontinuiranim vremenom, o kojemu je bilo riječi u prethodnom predavanju, odvija se u sustavima čekanja (QS).

Sustavi čekanja – to su sustavi koji primaju zahtjeve za uslugu u nasumičnim vremenima, a primljeni zahtjevi se servisiraju korištenjem servisnih kanala dostupnih sustavu.

Primjeri sustava čekanja uključuju:

• jedinice za obračun gotovine u bankama i poduzećima;
• osobna računala koja služe dolaznim aplikacijama ili zahtjevima za rješavanje određenih problema;
• servisne stanice za automobile; benzinska postaja;
• revizorske tvrtke;
• odjeli porezne inspekcije odgovorni za prihvaćanje i provjeru tekućih izvješća poduzeća;
• telefonske centrale itd.

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

Razmotrimo radni dijagram QS-a (slika 1). Sustav se sastoji od generatora zahtjeva, dispečera i servisne jedinice, jedinice za obračun kvarova (terminator, razarač naloga). Općenito, servisni čvor može imati nekoliko servisnih kanala.

Riža. 1

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

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

1. Red – aplikacijski akumulator. Možda nema čekanja u redu.
2. Servisni centar sastoji se od konačnog broja uslužnih kanala. Svaki kanal ima 3 stanja: slobodan, zauzet, ne radi. Ako su svi kanali zauzeti, onda možete smisliti strategiju kome prenijeti zahtjev.
3. Odbijanje iz usluge se javlja ako su svi kanali zauzeti (neki od njih možda neće raditi).

Uz ove osnovne elemente u QS-u, neki izvori također ističu sljedeće komponente:

terminator – uništavač transakcija;

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

računovodstveni račun – za obavljanje poslova tipa „knjiženje“;

manager – menadžer resursa;

Klasifikacija SMO

Prva podjela (na temelju prisutnosti redova):

• QS s kvarovima;
• SMO s čekanjem.

U QS s kvarovima prijava primljena u vrijeme kada su svi kanali zauzeti biva odbijena, napušta QS i ne servisira se u budućnosti.

U Red s redom aplikacija koja stigne u trenutku kada su svi kanali zauzeti ne odlazi, već staje u red i čeka priliku za posluživanje.

QS s redovima dijele se na različite vrste 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-ovi:

• CMO s nestrpljivim zahtjevima (duljina čekanja i vrijeme usluge su ograničeni);
• QS s prioritetnom uslugom, tj. neki zahtjevi se servisiraju izvan reda itd.

Vrste ograničenja čekanja mogu se kombinirati.

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

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

Osim toga, SMO se dijele na otvoren 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 – ovise. Na primjer, ako jedan radnik servisira skupinu strojeva koji s vremena na vrijeme zahtijevaju prilagodbu, tada intenzitet protoka "zahtjeva" od strojeva ovisi o tome koliko ih je već u funkciji i čeka prilagodbu.

Primjer zatvorenog sustava: blagajnica koja izdaje plaću u poduzeću.

Prema broju kanala QS se dijele na:

• jednokanalni;
• višekanalni.

Karakteristike sustava čekanja

Glavne karakteristike bilo koje vrste sustava čekanja su:

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

Tok ulaznih zahtjeva

Da biste opisali ulazni tok, morate navesti zakon vjerojatnosti koji određuje redoslijed trenutaka kada su zahtjevi za uslugu primljeni, i navesti broj takvih zahtjeva u svakom sljedećem primitku. U ovom slučaju, u pravilu, oni rade s konceptom "probabilističke distribucije trenutaka primitka zahtjeva". Ovdje mogu učiniti sljedeće: individualne i grupne zahtjeve (broj takvih zahtjeva u svakoj redovnoj potvrdi). U potonjem slučaju obično govorimo o sustavu čekanja s opsluživanjem paralelnih grupa.

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

E(A)– prosječno (MO) vrijeme dolaska;

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

Karakteristike ulaznog toka:

1. Vjerojatni zakon koji određuje redoslijed trenutaka kada su zahtjevi za uslugom primljeni.
2. Broj zahtjeva u svakom sljedećem dolasku za grupne tokove.

Disciplina čekanja

Red – skup zahtjeva koji čekaju uslugu.

Red čekanja ima ime.

Disciplina čekanja definira princip prema kojem se zahtjevi pristigli na ulaz sustava za posluživanje povezuju iz reda čekanja s procedurom servisiranja. 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. Zapis je ćelija popisa. Aplikacija dolazi na kraju liste, a odabire se za uslugu s početka liste. Zapis se sastoji od karakteristika aplikacije i linka (indikatora tko stoji iza nje). Osim toga, ako red čekanja ima ograničenje vremena čekanja, tada mora biti naznačeno i maksimalno vrijeme čekanja.

Kao programeri, trebali biste moći napraviti dvosmjerne, jednosmjerne popise.

Popis radnji:

• umetnite u rep;
• uzeti od početka;
• ukloniti s popisa nakon isteka vremena.
• Zadnji stigne - prvi poslužen LIFO (spajalica, slijepa ulica na željezničkoj stanici, ušao u prepun automobil).

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

• slučajni odabir aplikacija;
• odabir prijava na temelju kriterija prioriteta.

Svaka prijava karakterizirana je, između ostalog, i razinom prioriteta te se po primitku ne nalazi na repu reda, već na kraju svoje prioritetne skupine. Dispečer sortira po prioritetu.

Karakteristike reda čekanja

• ograničenjevrijeme čekanja trenutak usluge (postoji red s ograničenim vremenom čekanja na uslugu, koji je povezan s konceptom "dopuštene duljine reda");
• duljina čekanja.

Servisni mehanizam

Servisni mehanizam određena karakteristikama samog uslužnog postupka i strukturom uslužnog sustava. Karakteristike postupka održavanja uključuju:

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

Za analitički opis karakteristika uslužnog postupka koristi se koncept “probabilističke distribucije vremena za potrebe servisiranja”.

S i– vrijeme usluge ja-th zahtjev;

E(S)– prosječno vrijeme usluge;

μ=1/E(S)– brzina servisiranja zahtjeva.

Treba napomenuti da vrijeme potrebno za servisiranje 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 razdoblja. Ova se karakteristika može modelirati kao niz neuspjeha koji ulaze u QS i imaju prioritet nad svim ostalim zahtjevima.

QS stopa iskorištenja

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

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

Struktura uslužnog sustava

Struktura uslužnog sustava određena je brojem i međusobnim položajem uslužnih kanala (mehanizama, uređaja i dr.). Prije svega, treba naglasiti da servisni sustav može imati više od jednog servisnog kanala, već nekoliko; Ova vrsta sustava može istovremeno zadovoljiti više zahtjeva. U ovom slučaju svi kanali usluga nude iste usluge, pa se stoga može tvrditi da paralelna usluga .

Primjer. Blagajne u trgovini.

Sustav usluga može se sastojati od nekoliko različitih vrsta kanala usluga kroz koje mora proći svaki servisirani zahtjev, tj. u sustavu usluga procedure servisiranja zahtjeva provode se dosljedno . Mehanizam servisiranja određuje 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 :

• vjerojatnosna raspodjela trenutaka primitka zahtjeva za uslugu (pojedinačna ili skupna);
• snaga izvora zahtjeva;
• probabilistička distribucija vremena trajanja usluge;
• konfiguracija sustava posluživanja (paralelna, sekvencijalna ili paralelno-sekvencijalna usluga);
• broj i produktivnost uslužnih kanala;
• disciplina čekanja.

Glavni kriteriji učinkovitosti funkcioniranja QS-a

Kao glavni kriteriji za učinkovitost sustava čekanja Ovisno o prirodi problema koji se rješava, može se pojaviti sljedeće:

• vjerojatnost trenutnog servisiranja pristigle aplikacije (P obsl = K obs / K post);
• vjerojatnost odbijanja servisiranja dolazne aplikacije (P open = K open / K post);

Očito, P obsl + P otvoreno =1.

Protoci, kašnjenja, održavanje. Pollacheck-Khinchinova formula

Odgoditi – jedan od kriterija za servisiranje QS-a je vrijeme koje aplikacija provede čekajući servis.

D i– kašnjenje u redu zahtjeva ja;

W i =D i +S i– vrijeme potrebno u sustavu ja.

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

(s vjerojatnošću 1) – utvrđeno prosječno vrijeme kada je zahtjev u QS-u (čekanje).

Q(t) – broj zahtjeva u redu odjednom t;

L(t)– broj zahtjeva u sustavu u isto vrijeme t(Q(t) plus broj zahtjeva koji se istovremeno servisiraju t.

Zatim indikatori (ako postoje)

(s vjerojatnošću 1) – prosječni broj zahtjeva u redu tijekom vremena u stabilnom stanju;

(s vjerojatnošću 1) – prosječni broj zahtjeva u sustavu tijekom vremena u stabilnom stanju.

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 prijava veći od Nμ, tada je ρ>1 i prirodno je da sustav neće moći podnijeti toliki tok prijava, pa se stoga ne može govoriti o količinama 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 zahtjeva 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, također možemo govoriti o karakteristikama kao što su:

• apsolutni kapacitet sustava – A=R obsl *λ;
• relativni kapacitet sustava –

Još jedan zanimljiv (i ilustrativan) primjer analitičkog rješenja – izračunavanje prosječnog kašnjenja u stacionarnom stanju u redu čekanja 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) veće, onda je preopterećenje (u ovom slučaju 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 distribucije 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 servisa može poprimiti veliku vrijednost (jer mora biti pozitivna), tj. jedini servisni uređaj će biti dugo zauzet, što će dovesti do povećanje u redu čekanja.

Predmet teorije čekanja je uspostaviti odnos između čimbenika koji određuju funkcionalnost sustava čekanja i učinkovitosti njegova rada. U većini slučajeva svi parametri koji opisuju sustave čekanja su slučajne varijable ili funkcije, stoga ovi sustavi pripadaju 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 markovski i nemarkovski sustavi . U Markovljevim sustavima, dolazni tok zahtjeva i odlazni tok servisiranih zahtjeva (aplikacija) su Poissonovi. Poissonovi tokovi olakšavaju opisivanje i konstruiranje matematičkog modela sustava čekanja. Ovi modeli imaju prilično jednostavna rješenja, tako da većina dobro poznatih primjena teorije čekanja koristi Markovljevu shemu. U slučaju ne-Markovljevih procesa problemi proučavanja sustava čekanja postaju znatno kompliciraniji i zahtijevaju korištenje statističkog modeliranja i numeričkih metoda pomoću računala.

Velika klasa sustava koje je teško proučavati analitičkim metodama, ali su dobro proučeni metodama statističkog modeliranja, svodi se na sustave čekanja (QS).

QS implicira da postoji tipične staze(uslužni kanali) kroz koje prolaze tijekom procesa obrade aplikacije. Obično se kaže da aplikacije služio kanala. Kanali mogu biti različiti po namjeni, karakteristikama, mogu se kombinirati u različitim kombinacijama; aplikacije mogu biti u redovima čekanja na uslugu. Neke aplikacije mogu biti servisirane kanalima, dok druge to mogu odbiti. Bitno je da su zahtjevi, sa stajališta sustava, apstraktni: oni su nešto što želi biti usluženo, odnosno ići određenim putem u sustavu. Kanali su također apstrakcija: oni služe zahtjevima.

Zahtjevi mogu stizati neravnomjerno, kanali mogu posluživati ​​različite zahtjeve u različito vrijeme, i tako dalje, broj zahtjeva je uvijek vrlo velik. Sve to čini takve sustave teškima za proučavanje i upravljanje, te nije moguće pratiti sve uzročno-posljedične veze u njima. Stoga je općenito prihvaćeno da je održavanje u složenim sustavima nasumično.

Primjeri CMO-a (vidi tablicu 30.1) uključuju: autobusne linije i prijevoz putnika; proizvodni transporter za obradu dijelova; eskadrila zrakoplova koja leti na strani teritorij, koju "opslužuju" protuzračni topovi protuzračne obrane; cijev i rog mitraljeza, koji "poslužuju" patrone; električni naboji koji se kreću u nekom uređaju itd.

Tablica 30.1. Primjeri sustava čekanja

Prijave Kanali Autobusna linija i prijevoz putnika Putnici Autobusi Proizvodni transporter za obradu dijelova Dijelovi, komponente Alatni strojevi, skladišta Eskadrila zrakoplova koja leti na strani teritorij, koju "opslužuju" protuzračni topovi protuzračne obrane Zrakoplov Protuavionski topovi, radari, strijele, granate Cijev i rog mitraljeza, koji "poslužuju" patrone Bačva, rog Električni naboji koji se kreću u nekom uređaju Kaskade tehničkih uređaja

Ali svi su ti sustavi kombinirani u jednu klasu QS-a, jer je pristup njihovom proučavanju isti. Sastoji se od činjenice da se, prvo, uz pomoć generatora slučajnih brojeva izvlače slučajni brojevi koji simuliraju SLUČAJNE trenutke pojavljivanja naloga i vrijeme njihove usluge u kanalima. Ali uzeti zajedno, ovi nasumični brojevi su, naravno, podređeni statistički uzorci.

Na primjer, neka se kaže: "u prosjeku, prijave stižu u količini od 5 komada na sat." To znači da su vremena između dolaska dva susjedna zahtjeva slučajna, na primjer: 0.1; 0,3; 0,1; 0,4; 0,2, kao što je prikazano na sl. 30,1, ali ukupno daju prosjek 1 (imajte na umu da u primjeru to nije točno 1, već 1,1 - ali na drugom satu taj zbroj, na primjer, može biti jednak 0,9); ali samo dosta dugo prosjek ovih brojeva postat će blizu jednog sata.

Rezultat (npr. propusnost sustava), naravno, također će biti slučajna varijabla u pojedinim vremenskim intervalima. No, mjerena kroz dugo vremensko razdoblje, ova će vrijednost u prosjeku odgovarati točnom rješenju. To jest, da bi se okarakterizirao QS, oni su zainteresirani za odgovore u statističkom smislu.

Dakle, sustav se testira slučajnim ulaznim signalima, podložnim zadanom statističkom zakonu, a rezultat su statistički pokazatelji prosječni tijekom vremena razmatranja ili broja eksperimenata. Prethodno, u predavanja 21(cm. riža. 21.1), već smo razvili shemu za takav statistički eksperiment (vidi sl. 30.2).

Drugo, svi QS modeli sastavljeni su na standardan način iz malog skupa elemenata (kanal, izvor zahtjeva, red čekanja, zahtjev, disciplina usluge, stog, prsten itd.), što vam omogućuje simulaciju ovih zadataka tipičan put. Da biste to učinili, model sustava sastavlja se iz konstruktora takvih elemenata. Nije važno koji se sustav proučava, važno je da je dijagram sustava sastavljen od istih elemenata. Naravno, struktura kruga će uvijek biti drugačija.

Nabrojimo neke osnovne koncepte QS-a.

Kanali su ono što služi; Postoje vrući (počinju servisirati zahtjev čim uđe u kanal) i hladni (kanalu treba vremena da se pripremi prije početka servisiranja). Izvori naloga - generirajte naloge u nasumično vrijeme, prema statističkom zakonu koji je odredio korisnik. Aplikacije, također poznate kao klijenti, ulaze u sustav (generiraju ih izvori aplikacija), prolaze kroz njegove elemente (servisiraju se) i ostavljaju ga servisiranim ili nezadovoljnim. Ima nestrpljivih prijava - onih kojima je dosadilo čekati ili biti u sustavu i koji svojom voljom napuštaju CMO. Prijave formiraju tokove - tok aplikacija na ulazu sustava, tok servisiranih aplikacija, tok odbijenih aplikacija. Protok karakterizira broj primjena određene vrste opaženih na određenom mjestu QS-a u jedinici vremena (sat, dan, mjesec), odnosno protok je statistička veličina.

Redove karakteriziraju pravila čekanja (disciplina usluživanja), broj mjesta u redu (maksimalni broj klijenata koji mogu biti u redu) i struktura reda (odnos između mjesta u redu). Postoje ograničeni i neograničeni redovi. Nabrojimo najvažnije discipline održavanja. FIFO (First In, First Out - prvi ušao, prvi izašao): ako je zahtjev prvi stigao u red čekanja, tada će prvi ići na uslugu. LIFO (Last In, First Out - zadnji ušao, prvi izašao): ako je zahtjev zadnji stigao u red čekanja, tada će prvi ići na servis (primjer - patrone u trubi mitraljeza). SF (Short Forward): prvi se servisiraju oni zahtjevi iz reda koji imaju kraće vrijeme servisa.

Navedimo upečatljiv primjer koji pokazuje kako ispravan odabir jedne ili druge discipline usluge omogućuje postizanje značajnih ušteda vremena.

Neka budu dva dućana. U prodavaonici br. 1 usluga se obavlja po principu prvi došao, prvi poslužen, odnosno ovdje se primjenjuje FIFO disciplina usluživanja (vidi sl. 30.3).

Vrijeme usluge t servis na sl. 30.3 pokazuje koliko će vremena prodavač potrošiti na opsluživanje jednog kupca. Jasno je da će prodavač pri kupnji komadnog proizvoda potrošiti manje vremena na servis nego pri kupnji, recimo, masovnih proizvoda koji zahtijevaju dodatne manipulacije (branje, vaganje, izračun cijene i sl.). Vrijeme čekanja t očekivano pokazuje koliko će vremena trebati sljedećem kupcu da ga prodavač usluži.

U prodavaonici br. 2 provodi se disciplina SF (vidi sl. 30.4), što znači da se komadna roba može kupiti izvan reda, budući da je vrijeme usluge t servis takva kupnja je mala.

Kao što se može vidjeti iz obje slike, posljednji (peti) kupac će kupiti komadni proizvod, tako da je njegovo servisno vrijeme kratko - 0,5 minuta. Ako ovaj kupac dođe u trgovinu broj 1, morat će stajati u redu punih 8 minuta, dok će u trgovini broj 2 biti uslužen odmah, izvan reda. Tako će prosječno vrijeme usluge za svakog kupca u trgovini s disciplinom FIFO usluge biti 4 minute, au trgovini s disciplinom HF usluge samo 2,8 minuta. A društvena korist, ušteda vremena bit će: (1 – 2,8/4) · 100% = 30 posto! Dakle, 30% ušteđenog vremena za društvo - i to samo zahvaljujući pravilnom odabiru discipline servisa.

Specijalist za sustave mora imati temeljito razumijevanje resursa performansi i učinkovitosti sustava koje on ili ona dizajnira, a koji su skriveni u optimizaciji parametara, struktura i disciplina održavanja. Modeliranje pomaže identificirati te skrivene rezerve.

Pri analizi rezultata modeliranja također je važno navesti interese i u kojoj su mjeri oni ispunjeni. Razlikuju se interesi klijenta i interesi vlasnika sustava. Imajte na umu da se ti interesi ne poklapaju uvijek.

Učinkovitost QS-a može se procijeniti prema pokazateljima. Najpopularniji od njih:

vjerojatnost korisničke usluge od strane sustava;

propusnost sustava;

vjerojatnost da će korisniku biti uskraćena usluga;

vjerojatnost korištenja svakog kanala i svih njih zajedno;

prosječno vrijeme zauzetosti svakog kanala;

vjerojatnost popunjenosti svih kanala;

prosječan broj zauzetih kanala;

vjerojatnost prekida rada za svaki kanal;

vjerojatnost prekida rada cijelog sustava;

prosječan broj prijava u redu čekanja;

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

prosječno vrijeme za servisiranje aplikacije;

prosječno vrijeme koje aplikacija ostaje u sustavu.

Kvaliteta dobivenog sustava mora se procijeniti prema ukupnosti vrijednosti pokazatelja. Pri analizi rezultata modeliranja (pokazatelja) također je važno obratiti pozornost na interese klijenta i interese vlasnika sustava, odnosno, jedan ili drugi pokazatelj mora biti minimiziran ili maksimiziran, kao i stupanj njihove implementacije. . Imajte na umu da se najčešće interesi klijenta i vlasnika međusobno ne poklapaju ili se ne poklapaju uvijek. U nastavku ćemo označiti indikatore H = { h 1 , h 2 , …} .

Parametri QS-a mogu biti: intenzitet protoka zahtjeva, intenzitet protoka usluge, prosječno vrijeme tijekom kojeg je zahtjev spreman čekati uslugu u redu čekanja, broj kanala usluge, disciplina usluge i tako dalje. Parametri su ono što utječe na performanse sustava. Parametre u nastavku označit ćemo kao R = { r 1 , r 2 , …} .

Primjer. Benzinska postaja (benzinska postaja).

1. Izjava problema. Na sl. Na slici 30.5 prikazan je izgled benzinske postaje. Razmotrimo metodu modeliranja QS-a na njegovom primjeru i planu za njegovo istraživanje. Vozači koji prolaze pokraj benzinskih crpki na cesti možda će htjeti natočiti svoje vozilo. Ne žele svi vozači dobiti servis (napuniti automobil benzinom); Pretpostavimo da od ukupnog protoka automobila, prosječno 5 automobila dođe na benzinsku postaju na sat.

Na benzinskoj postaji postoje dva identična stupca, od kojih je statistički učinak poznat. Prvi stupac u prosjeku služi 1 automobil na sat, drugi u prosjeku - 3 automobila na sat. Vlasnik benzinske postaje asfaltirao je mjesto za automobile gdje mogu čekati servis. Ako su pumpe zauzete, onda na ovom mjestu servis mogu čekati i druga vozila, ali ne više od dva odjednom. Red ćemo smatrati općim. Čim se jedna od kolona oslobodi, prvi automobil u redu može zauzeti svoje mjesto u koloni (dok se drugi automobil pomiče na prvo mjesto u redu). Ako se pojavi treći automobil, a sva mjesta (ima ih dva) u redu su zauzeta, tada mu je usluga uskraćena, jer je stajanje na cesti zabranjeno (pogledajte prometne znakove u blizini benzinske postaje). Takav automobil zauvijek izlazi iz sustava i kao potencijalni klijent izgubljen je za vlasnika benzinske postaje. Zadatak možete zakomplicirati uzimajući u obzir blagajnu (još jedan servisni kanal, gdje trebate stići nakon servisiranja u jednom od stupaca) i red do nje, i tako dalje. No, u najjednostavnijoj verziji, očito je da se tokovi aplikacija kroz QS mogu prikazati u obliku ekvivalentnog dijagrama, a dodavanjem vrijednosti i oznaka karakteristika svakog elementa QS-a konačno dobivamo dobiti dijagram prikazan na sl. 30.6.

2. Metoda istraživanja SMO. U našem primjeru primijenit ćemo princip sekvencijalnog knjiženja naloga (za detalje o principima modeliranja vidi predavanje 32). Njegova ideja je da se aplikacija provuče kroz cijeli sustav od ulaza do izlaza, a tek nakon toga se modelira sljedeća aplikacija.

Radi jasnoće, konstruirajmo vremenski dijagram QS operacije, odražavajući svaku liniju (vremenska os t) stanje pojedinog elementa sustava. Postoji onoliko vremenskih linija koliko ima različitih mjesta u QS-u i tokovima. U našem primjeru ima ih 7 (tok zahtjeva, nit koja čeka na prvom mjestu u redu čekanja, nit koja čeka na drugom mjestu u redu čekanja, tok usluge na kanalu 1, tok usluge na kanalu 2) , tijek zahtjeva koje sustav opslužuje, tijek odbijenih zahtjeva).

Za generiranje vremena pristizanja zahtjeva koristimo formulu za izračunavanje intervala između vremena pristizanja dvaju slučajnih događaja (vidi. predavanje 28):

U ovoj formuli, vrijednost protoka λ mora biti specificiran (prije toga se mora odrediti eksperimentalno u postrojenju kao statistički prosjek), r- slučajni jednoliko raspodijeljeni broj od 0 do 1 iz RNG odn stolovi, u kojem se slučajni brojevi moraju uzimati u nizu (bez posebnog odabira).

Zadatak. Generirajte tok od 10 nasumičnih događaja s brzinom događaja od 5 komada/sat.

Rješenje problema. Uzmimo nasumične brojeve ravnomjerno raspoređene u rasponu od 0 do 1 (vidi. stol), i izračunajte njihove prirodne logaritme (vidi tablicu 30.2).

Tablica 30.2. Fragment tablice slučajnih brojeva i njihovih logaritama

r str ln(r str )

Poissonova formula protoka određuje udaljenost između dva slučajna događaja na sljedeći način: t= –Ln(r rr)/ λ . Zatim, s obzirom na to λ = 5, imamo udaljenosti između dva slučajna susjedna događaja: 0,68, 0,21, 0,31, 0,12 sati. To jest, događaji se događaju: prvi - u trenutku vremena t= 0, drugi - u trenutku vremena t= 0,68, treći - u trenutku vremena t= 0,89, četvrti - u trenutku vremena t= 1,20, peti - u trenutku vremena t= 1,32 i tako dalje. Događaji - pristizanje narudžbi će se odraziti u prvom retku (vidi sl. 30.7).

Riža. 30.7. Vremenski dijagram rada QS-a

Prvi zahtjev se preuzima i, budući da su kanali u ovom trenutku slobodni, postavlja se na servisiranje prvog kanala. Aplikacija 1 prebacuje se u liniju "1 kanal".

Vrijeme usluge u kanalu također je slučajno i izračunava se pomoću slične formule:

gdje ulogu intenziteta ima veličina toka usluge μ 1 ili μ 2, ovisno o tome koji kanal služi zahtjevu. Na dijagramu nalazimo trenutak završetka usluge, odgađajući generirano vrijeme usluge od trenutka početka usluge i spuštamo zahtjev na redak "Posluženo".

Prijava je išla sve do CMO-a. Sada je po principu sekvencijalnog knjiženja naloga moguće simulirati i putanju drugog naloga.

Ako se u nekom trenutku ispostavi da su oba kanala zauzeta, tada zahtjev treba staviti u red čekanja. Na sl. 30.7 je zahtjev s brojem 3. Imajte na umu da prema uvjetima problema, za razliku od kanala, zahtjevi nisu u redu čekanja nasumično vrijeme, već čekaju da se jedan od kanala oslobodi. Nakon oslobađanja kanala, zahtjev se podiže na liniju odgovarajućeg kanala i tamo se organizira njegovo servisiranje.

Ako su sva mjesta u redu čekanja zauzeta u trenutku kada stigne sljedeća prijava, tada prijavu treba poslati u redak “Odbijeno”. Na sl. 30.7 je aplikacija broj 6.

Procedura za simulaciju servisiranja aplikacije nastavlja se neko vrijeme promatranja. T n. Što je ovo vrijeme dulje, to će rezultati simulacije biti precizniji u budućnosti. U stvarnosti, za jednostavne sustave oni biraju T n, jednako 50-100 ili više sati, iako je ponekad bolje izmjeriti ovu vrijednost prema broju pregledanih aplikacija.

Analitičko istraživanje sustava čekanja (QS) alternativa je pristupu simulacijskom modeliranju, a sastoji se od dobivanja formula za izračun izlaznih parametara QS-a i zatim zamjene vrijednosti argumenata u te formule u svakom pojedinačnom eksperimentu.

QS modeli razmatraju sljedeće objekte:

1) zahtjevi za uslugu (transakcije);

2) servisni uređaji (OA), odnosno uređaji.

Praktična zadaća teorije čekanja povezana je s proučavanjem operacija ovih objekata i sastoji se od pojedinačnih elemenata na koje utječu slučajni čimbenici.

Primjeri problema koji se razmatraju u teoriji čekanja uključuju: usklađivanje kapaciteta izvora poruke s kanalom prijenosa podataka, analizu optimalnog protoka gradskog prijevoza, izračunavanje kapaciteta čekaonice za putnike u zračnoj luci, itd.

Zahtjev može biti ili u stanju usluge ili u stanju čekanja usluge.

Uređaj za servisiranje može biti ili zauzet servisiranjem ili slobodan.

Stanje QS-a karakterizira skup stanja servisnih uređaja i zahtjeva. Promjena stanja u QS-u naziva se događaj.

QS modeli se koriste za proučavanje procesa koji se odvijaju u sustavu kada se tokovi zahtjeva podnose na ulaze. Ovi procesi su slijed događaja.

Najvažniji izlazni parametri QS-a

Izvođenje

Širina pojasa

Vjerojatnost odbijanja usluge

Prosječno vrijeme usluge;

Faktor opterećenja opreme (OA).

Aplikacije mogu biti narudžbe za proizvodnju proizvoda, problemi riješeni u računalnom sustavu, klijenti u bankama, roba primljena na transport itd. Očito, parametri aplikacija koje ulaze u sustav su slučajne varijable i tijekom istraživanja ili projektiranja vrijede samo njihovi zakoni distribucije. .

S tim u vezi, analiza funkcioniranja na razini sustava u pravilu je statističke prirode. Prikladno je prihvatiti teoriju čekanja kao aparat za matematičko modeliranje, a koristiti sustave čekanja kao modele sustava na ovoj razini.

Najjednostavniji modeli QS

U najjednostavnijem slučaju, QS je uređaj koji se naziva servisni aparat (SA), s redovima zahtjeva na ulazima.

MODEL USLUGE ZA KORISNIKE (Sl. 5.1)

Riža. 5.1. QS model s greškama:

0 – izvor zahtjeva;

1 – servisni uređaj;

A– ulazni tijek zahtjeva za uslugu;

V– izlazni tok usluženih zahtjeva;

S– izlazni tok neobrađenih zahtjeva.

U ovom modelu nema akumulatora potražnje na ulazu OA. Ako zahtjev stigne iz izvora 0 u vrijeme kada je OA zauzet servisiranjem prethodnog zahtjeva, tada novopristigli zahtjev napušta sustav (budući da mu je uskraćena usluga) i gubi se (tok S).

M o d e l o m o r m e n t a (Sl. 5.2)

Riža. 5.2. QS model s očekivanjem

(N– 1) – broj aplikacija koje mogu stati u pohranu

U ovom modelu postoji akumulator potražnje na ulazu OA. Ako zahtjev stigne iz izvora 0 u trenutku kada je OA zauzet servisiranjem prethodnog zahtjeva, tada novopristigli zahtjev završava u jedinici za pohranu, gdje čeka neodređeno dugo dok se OA ne oslobodi.

SERVISNI MODEL SA VREMENSKIM OGRANIČENJEM

o w i d a n i a (Sl. 5.3)

Riža. 5.4. Višekanalni QS model s greškama:

n– broj istovrsnih servisnih uređaja (uređaja)

U ovom modelu ne postoji jedan OA, već nekoliko. Prijave, osim ako nije izričito navedeno, mogu se podnijeti bilo kojem OA bez usluge. Nema uređaja za pohranu, tako da ovaj model uključuje svojstva modela prikazanog na sl. 5.1: odbijanje servisiranja aplikacije znači njen nepovratni gubitak (ovo se događa samo ako, u trenutku prispijeća ove aplikacije, svi OA su zauzeti).

Vrijeme čekanja (Sl. 5.5)

Riža. 5.6. Višekanalni model SMO s očekivanjem i restauracijom OA:

e– servisne uređaje koji su u kvaru;

f– obnovljena servisna oprema

Ovaj model ima svojstva modela prikazanih na sl. 5.2 i 5.4, i dodatno svojstava koja omogućuju da se uzmu u obzir mogući slučajni kvarovi OA, koji u ovom slučaju stižu u jedinicu za popravak 2, gdje ostaju slučajna razdoblja vremena potrošena na njihovu obnovu, a zatim se vraćaju ponovno u servisnu jedinicu 1.

VIŠEKANALNI MODEL SMO S LIMITED

VRIJEME ČEKANJA I OPORAVKA OA (Sl. 5.7)

Riža. 5.7. Višekanalni QS model s ograničenom latencijom i OA oporavkom

Ovaj model je prilično složen, budući da istovremeno uzima u obzir svojstva dva ne baš jednostavna modela (sl. 5.5 i 5.6).

Pošaljite svoj dobar rad u bazu znanja jednostavno je. Koristite obrazac u nastavku

Studenti, diplomanti, mladi znanstvenici koji koriste bazu znanja u svom studiju i radu bit će vam vrlo zahvalni.

Objavljeno na http://allbest.ru

UVOD

POGLAVLJE 1. TEORIJSKI DIO

1.1 Sustavi čekanja s kvarovima

1.2 Modeliranje sustava čekanja

1.3 Najjednostavniji QS s kvarovima

1.4 Jednokanalni QS s kvarovima

1.5 Višekanalni QS s kvarovima

1.6 Jednokanalni QS s ograničenom duljinom čekanja

1.7 Jednokanalni QS s neograničenim redom

1.8 Višekanalni QS s ograničenom duljinom čekanja

1.9 Višekanalni QS s neograničenim redom

1.10 Algoritam QS modeliranja

POGLAVLJE 2. PRAKTIČNI DIO

POGLAVLJE 3. SIGURNOSNA PRAVILA

ZAKLJUČAK

POPIS KORIŠTENE LITERATURE

UVOD

U posljednje vrijeme u različitim područjima prakse javlja se potreba za rješavanjem raznih probabilističkih problema vezanih uz rad tzv. sustava čekanja (QS).

Primjeri takvih sustava uključuju: telefonske centrale, servisne radionice, blagajne za prodaju karata, taksi stajališta, frizerske salone itd.

Tema ovog nastavnog projekta je upravo rješenje takvog problema.

Međutim, u predloženom problemu proučavat će se QS u kojem se razmatraju 2 toka zahtjeva, od kojih jedan ima prioritet.

Također, procesi koji se razmatraju nisu markovski, jer Faktor vremena je važan.

Stoga se rješenje ovog problema ne temelji na analitičkom opisu sustava, već na statističkom modeliranju.

Svrha kolegija je modeliranje proizvodnog procesa na temelju prikaza glavne opreme kao sustava čekanja.

Za postizanje cilja postavljeni su sljedeći zadaci: - Analizirati značajke upravljanja proizvodnim procesom; - Razmotriti organizaciju proizvodnog procesa tijekom vremena; - Navesti glavne opcije za smanjenje trajanja proizvodnog ciklusa;

Provesti analizu metoda upravljanja proizvodnim procesom u poduzeću;

Razmotriti značajke modeliranja proizvodnog procesa pomoću teorije QMS-a;

Razviti model proizvodnog procesa i ocijeniti glavne karakteristike QS-a, te dati izglede za njegovu daljnju programsku implementaciju.

Učvršćivanje teorijskih znanja i stjecanje vještina njihove praktične primjene;

Izvješće sadrži uvod, tri poglavlja, zaključak, popis literature i priloge.

Drugo poglavlje govori o teorijskim materijalima o sustavu čekanja. A u trećem izračunavamo problem sustava čekanja.

POGLAVLJE 1. TEORIJSKI DIO

1.1 Sustavi čekanjackvarovi

Sustav čekanja (QS) je svaki sustav koji je dizajniran da opslužuje sve aplikacije (zahtjeve) koje mu pristižu u nasumično vrijeme. Svaki uređaj koji je izravno uključen u zahtjeve za servisiranjem naziva se servisni kanal (ili "uređaj"). SMO mogu biti jednokanalni ili višekanalni.

Postoje QS s kvarovima i QS s čekanjem. U QS-u s odbijanjima, aplikacija koja stigne u vrijeme kada su svi kanali zauzeti dobiva odbijenicu, napušta QS i nakon toga ne sudjeluje u njegovom radu. U QS-u s redom čekanja, zahtjev koji stigne kada su svi kanali zauzeti ne napušta QS, već ulazi u red čekanja i čeka dok se neki kanal ne oslobodi. Broj mjesta u redu m može biti ograničen ili neograničen. Pri m=0 QS s redom se pretvara u QS s kvarovima. Red čekanja može imati ograničenja ne samo na broj aplikacija koje stoje u njemu (duljina reda), već i na vrijeme čekanja (takvi QS-ovi se nazivaju "sustavi s nestrpljivim klijentima").

Analitičko proučavanje QS-a je najjednostavnije ako su svi tokovi događaja koji ga prenose iz stanja u stanje najjednostavniji (stacionarni Poisson). To znači da vremenski intervali između događaja u tokovima imaju eksponencijalnu raspodjelu s parametrom jednakim intenzitetu odgovarajućeg toka. Za QS, ova pretpostavka znači da su i tijek zahtjeva i tijek usluge najjednostavniji. Tijek usluge shvaća se kao tijek zahtjeva koji se jedan za drugim poslužuju putem jednog kontinuirano zauzetog kanala. Ovaj tok se pokazuje najjednostavnijim samo ako je vrijeme servisiranja zahtjeva tobsl slučajna varijabla s eksponencijalnom distribucijom. Parametar ove distribucije m je recipročna vrijednost prosječnog vremena usluge:

Umjesto fraze "tijek usluge je najjednostavniji", često kažu "vrijeme usluge je indikativno". Svaki QS u kojem su svi tokovi najjednostavniji naziva se najjednostavniji QS.

Ako su svi tokovi događaja najjednostavniji, tada je proces koji se odvija u QS-u Markovljev slučajni proces s diskretnim stanjima i kontinuiranim vremenom. Ako su ispunjeni određeni uvjeti za ovaj proces, postoji konačni stacionarni režim u kojem i vjerojatnosti stanja i druge karakteristike procesa ne ovise o vremenu.

QS modeli su pogodni za opisivanje pojedinih podsustava modernih računalnih sustava, kao što su procesorski podsustav - glavna memorija, ulazno-izlazni kanal itd.

Računalni sustav kao cjelina skup je međusobno povezanih podsustava čija je interakcija vjerojatnosne prirode. Aplikacija za rješavanje određenog problema koja ulazi u računalni sustav prolazi kroz slijed faza brojanja, pristupa vanjskim uređajima za pohranu i ulazno-izlaznim uređajima.

Nakon završetka određenog niza takvih faza, čiji broj i trajanje ovisi o složenosti programa, zahtjev se smatra servisiranim i napušta računalni sustav.

Dakle, računalni sustav u cjelini može se prikazati skupom QS-ova od kojih svaki odražava proces funkcioniranja pojedinog uređaja ili grupe sličnih uređaja koji su dio sustava.

Zadaci teorije čekanja su pronaći vjerojatnosti različitih stanja QS-a, kao i uspostaviti odnos između zadanih parametara (broj kanala n, intenzitet protoka zahtjeva n, raspodjela vremena usluge itd.). .) i karakteristike izvedbe QS-a. Takve karakteristike mogu se smatrati, na primjer, sljedećim:

Prosječan broj zahtjeva A koje je QS opslužio po jedinici vremena ili apsolutni kapacitet QS-a;

Vjerojatnost servisiranja dolaznog zahtjeva Q ili relativni kapacitet QS-a; Q = A/l;

Vjerojatnost kvara Rotk-a, tj. vjerojatnost da primljena prijava neće biti servisirana i da će biti odbijena; Rotk = 1 - Q;

Prosječan broj prijava u QS-u (posluženih ili čekanja u redu);

Prosječan broj prijava u redu čekanja;

Prosječno vrijeme koje aplikacija ostaje u QS-u (u redu čekanja ili na usluzi);

Prosječno vrijeme koje aplikacija provede u redu čekanja;

Prosječan broj zauzetih kanala.

Općenito, sve ove karakteristike ovise o vremenu. Ali mnogi samoposlužni sustavi rade u stalnim uvjetima dosta dugo, pa se za njih uspijeva uspostaviti režim blizak stacionarnom.

Ovdje smo cijelo vrijeme, bez da to svaki put posebno uvjetujemo, izračunat ćemo konačne vjerojatnosti stanja i konačne karakteristike učinkovitosti QS-a vezane uz ograničavajući stacionarni način njegova rada.

QS se naziva otvorenim ako intenzitet toka aplikacija koje mu pristižu ne ovisi o stanju samog QS-a.

Za svaki otvoreni QS u ograničavajućem stacionarnom načinu rada, prosječno vrijeme boravka zahtjeva u sustavu izražava se kroz prosječan broj zahtjeva u sustavu pomoću Littleove formule:

gdje je l intenzitet protoka prijava.

Slična formula (koja se naziva i Littleova formula) povezuje prosječno vrijeme koje aplikacija provede u redu čekanja i prosječan broj aplikacija u redu čekanja:

Littleove formule su vrlo korisne jer vam omogućuju da izračunate ne obje karakteristike učinkovitosti (prosječno vrijeme zadržavanja i prosječan broj primjena), već samo jednu od njih.

Posebno naglašavamo da formule (1) i (2) vrijede za bilo koji otvoreni QS (jednokanalni, višekanalni, za sve vrste tokova zahtjeva i tokova usluga); jedini zahtjev za tokove aplikacija i usluge je da budu stacionarni.

Slično tome, formula koja izražava prosječan broj zauzetih kanala kroz apsolutni kapacitet A ima univerzalno značenje za otvoreni QS:

gdje je intenzitet toka usluge.

Mnogi problemi teorije čekanja koji se tiču ​​najjednostavnijeg QS-a rješavaju se pomoću sheme smrti i reprodukcije.

Konačne vjerojatnosti stanja izražavaju se formulama:

Svitak karakteristike sustava čekanja mogu se predstaviti na sljedeći način:

· prosječno vrijeme usluge;

· prosječno vrijeme čekanja u redu;

· prosječno vrijeme boravka u zdravstvenoj službi;

prosječna duljina čekanja;

· prosječan broj prijava CMO-u;

· broj uslužnih kanala;

· intenzitet ulaznog toka prijava;

· intenzitet usluge;

· intenzitet opterećenja;

· faktor opterećenja;

· relativna propusnost;

· apsolutna propusnost;

· udio zastoja QS-a;

· udio usluženih zahtjeva;

· udio izgubljenih zahtjeva;

· prosječan broj zauzetih kanala;

· prosječan broj besplatnih kanala;

· faktor opterećenja kanala;

· prosječno vrijeme prekida rada kanala.

1 . 2 Modeliranje sustava čekanja

Prijelazi QS-a iz jednog stanja u drugo događaju se pod utjecajem vrlo specifičnih događaja – zaprimanja zahtjeva i njihovog servisiranja. Niz događaja koji se pojavljuju jedan za drugim u nasumično odabranim vremenima čini takozvani tok događaja. Primjeri takvih tokova u komercijalnim aktivnostima su tokovi različite prirode - roba, novac, dokumenti, transport, klijenti, kupci, telefonski pozivi, pregovori. Ponašanje sustava obično nije određeno jednim, već nekoliko tokova događaja. Na primjer, usluga kupcima u trgovini određena je protokom kupaca i protokom usluge; u tim tokovima, trenuci kada se kupci pojavljuju, vrijeme čekanja u redu i vrijeme utrošeno na posluživanje svakog kupca su slučajni.

U ovom slučaju, glavna karakteristika tokova je vjerojatnosna raspodjela vremena između susjednih događaja. Postoje različiti tokovi koji se razlikuju po svojim karakteristikama.

Tijek događaja naziva se pravilnim ako događaji slijede jedan za drugim u unaprijed određenim i točno određenim vremenskim razmacima. Ovaj tok je idealan i vrlo se rijetko susreće u praksi. Češće postoje nepravilni tokovi koji nemaju svojstvo pravilnosti.

Tijek događaja naziva se stacionarnim ako vjerojatnost da bilo koji broj događaja upadne u vremenski interval ovisi samo o duljini tog intervala, a ne o tome koliko je taj interval udaljen od početka vremena. Stacionarnost protoka znači da su njegove vjerojatnosne karakteristike neovisne o vremenu, posebno, intenzitet takvog protoka je prosječan broj događaja u jedinici vremena i ostaje konstantna vrijednost. U praksi se tokovi obično mogu smatrati stacionarnim samo tijekom određenog ograničenog vremenskog razdoblja. Obično se tok kupaca, na primjer, u trgovini, značajno mijenja tijekom radnog dana. Međutim, moguće je identificirati određene vremenske intervale unutar kojih se to strujanje može smatrati stacionarnim, konstantnog intenziteta.

Tijek događaja naziva se tijek bez posljedica ako broj događaja koji spadaju u jedan od proizvoljno odabranih vremenskih intervala ne ovisi o broju događaja koji ulaze u drugi, također proizvoljno odabran interval, pod uvjetom da se ti intervali međusobno ne sijeku. . U toku bez posljedica, događaji se događaju u uzastopnim vremenima neovisno jedan o drugom. Na primjer, protok kupaca koji ulaze u trgovinu može se smatrati protokom bez posljedica jer razlozi koji su odredili dolazak svakog od njih nisu povezani sa sličnim razlozima za druge kupce.

Tijek događaja naziva se običnim ako je vjerojatnost da se dva ili više događaja dogode odjednom u vrlo kratkom vremenskom razdoblju zanemariva u usporedbi s vjerojatnošću da se dogodi samo jedan događaj. U običnom toku događaji se događaju jedan po jedan, umjesto dva ili više puta. Ako tok istodobno ima svojstva stacionarnosti, običnosti i neposljedičnosti, tada se takav tok naziva najjednostavnijim (ili Poissonovim) tokom događaja. Matematički opis utjecaja takvog toka na sustave pokazuje se najjednostavnijim. Stoga, posebno, najjednostavniji tok igra posebnu ulogu među ostalim postojećim tokovima.

Promotrimo određeni vremenski interval t na vremenskoj osi. Pretpostavimo da je vjerojatnost da slučajni događaj padne u ovaj interval p, a ukupan broj mogućih događaja je n. U prisutnosti svojstva uobičajenog toka događaja, vjerojatnost p bi trebala biti dovoljno mala vrijednost, i trebao bi biti dovoljno velik broj, budući da se razmatraju masovni fenomeni.

Pod ovim uvjetima, za izračunavanje vjerojatnosti određenog broja događaja m koji se dogode u vremenskom razdoblju t, možete koristiti Poissonovu formulu:

Pm, n= am_e-a; (m=0,n),

gdje je vrijednost a = pr prosječan broj događaja koji padaju unutar vremenskog razdoblja t, koji se može odrediti preko intenziteta toka događaja X na sljedeći način: a = l f

Dimenzija intenziteta protoka X je prosječan broj događaja u jedinici vremena. Između p i l, p i f postoji sljedeća veza:

n= l t; p= f/t

gdje je t cijelo vremensko razdoblje tijekom kojeg se razmatra djelovanje toka događaja.

Potrebno je odrediti raspodjelu vremenskog intervala T između događaja u takvom toku. Budući da je ovo slučajna varijabla, pronađimo njenu funkciju distribucije. Kao što je poznato iz teorije vjerojatnosti, kumulativna funkcija distribucije F(t) je vjerojatnost da će vrijednost T biti manja od vremena t.

F(t)=P(T

Prema uvjetu, tijekom vremena T ne bi se trebao dogoditi nijedan događaj, a tijekom vremenskog intervala t trebao bi se pojaviti barem jedan događaj. Ova vjerojatnost izračunava se pomoću vjerojatnosti suprotnog događaja u vremenskom intervalu (0; t), u kojem se nije dogodio nijedan događaj, tj. m = 0, tada

F(t)=1-P0=1-(a0*e-a)0!=1-e-Xt,t?0

Za male?t, može se dobiti približna formula dobivena zamjenom funkcije e-Xt sa samo dva člana ekspanzije potencijama?t, tada je vjerojatnost da se barem jedan događaj dogodi unutar malog vremenskog razdoblja?t

P(T

Gustoću distribucije vremenskog intervala između dva uzastopna događaja dobivamo diferenciranjem F(t) s obzirom na vrijeme,

f(t)= l e- l t ,t?0

Pomoću dobivene funkcije gustoće distribucije mogu se dobiti numeričke karakteristike slučajne varijable T: matematičko očekivanje M (T), varijanca D (T) i standardna devijacija y (T).

M(T)= l??0 t*e-lt*dt=1/l; D(T)=l/l2; y(T)=1/l.

Odavde možemo izvući sljedeći zaključak: prosječni vremenski interval T između bilo koja dva susjedna događaja u najjednostavnijem toku je u prosjeku jednak 1/l, a njegova standardna devijacija također je jednaka 1/l, l gdje je intenzitet protoka, tj. prosječan broj događaja koji se događaju u jedinici vremena. Zakon raspodjele slučajne varijable s takvim svojstvima M(T) = T naziva se eksponencijalni (ili eksponencijalni), a vrijednost l je parametar tog eksponencijalnog zakona. Dakle, za najjednostavniji tok, matematičko očekivanje vremenskog intervala između susjednih događaja jednako je njegovoj standardnoj devijaciji. U ovom slučaju, vjerojatnost da je broj primljenih zahtjeva za uslugu tijekom vremenskog razdoblja t jednak k određena je Poissonovim zakonom:

Pk(t)=(lt)k/ k! *e-l t,

gdje je l intenzitet protoka zahtjeva, prosječan broj događaja u QS-u po jedinici vremena, na primjer [osoba/min; rub./sat; čekovi/sat; dokument/dan; kg./sat; t./godina].

Za takav tijek zahtjeva, vrijeme između dva susjedna zahtjeva T distribuira se eksponencijalno s gustoćom vjerojatnosti:

ѓ(t)= l e-l t.

Slučajno vrijeme čekanja t u redu čekanja za početak usluge također se može smatrati eksponencijalno raspodijeljenim:

? (toch)=V*e-v toch,

gdje je v intenzitet toka prolaza u redu čekanja, određen prosječnim brojem aplikacija koje prolaze za uslugu po jedinici vremena:

v=1/bod,

gdje je Toch prosječno vrijeme čekanja na uslugu u redu.

Izlazni tok zahtjeva povezan je s protokom usluge u kanalu, gdje je trajanje usluge tobs također slučajna varijabla iu mnogim slučajevima poštuje zakon eksponencijalne distribucije s gustoćom vjerojatnosti:

?(t obs)=µ*e µ t obs,

gdje je µ intenzitet toka usluge, tj. prosječan broj obrađenih zahtjeva po jedinici vremena:

µ=1/ t obs[osoba/min; rub./sat; čekovi/sat; dokument/dan; kg./sat; t./godina] ,

gdje je t obs prosječno vrijeme za servisiranje zahtjeva.

Važna karakteristika QS-a, kombinirajući pokazatelje l i µ, je intenzitet opterećenja: c = l/ µ, koji pokazuje stupanj koordinacije ulaznih i izlaznih tokova zahtjeva uslužnog kanala i određuje stabilnost sustava čekanja. .

Uz koncept najjednostavnijeg toka događaja, često je potrebno koristiti koncepte tokova drugih vrsta. Tok događaja naziva se Palma tok kada su u tom toku vremenski intervali između uzastopnih događaja T1, T2, ..., Tk ..., Tn neovisne, identično raspoređene, slučajne varijable, ali za razliku od najjednostavnijeg toka, oni su nije nužno raspoređeno prema eksponencijalnom zakonu. Najjednostavniji tok je poseban slučaj Palmovog toka.

Važan poseban slučaj Palmovog toka je takozvani Erlangov tok.

Ovaj tok se dobiva "stanjivanjem" najjednostavnijeg toka. Ovo “stanjivanje” provodi se odabirom događaja iz najjednostavnijeg toka prema određenom pravilu.

Na primjer, pristajući uzeti u obzir samo svaki drugi događaj koji tvori najjednostavniji tok, dobivamo Erlangov tok drugog reda. Ako uzmemo samo svaki treći događaj, tada se formira Erlangov tok trećeg reda, itd.

Moguće je dobiti Erlangove tokove bilo kojeg k-tog reda. Očito, najjednostavniji tok je Erlangov tok prvog reda.

Svako proučavanje sustava čekanja počinje proučavanjem onoga što treba poslužiti, dakle proučavanjem dolaznog toka aplikacija i njegovih karakteristika.

Budući da su vremenski trenuci t i vremenski intervali prijema zahtjeva f, zatim trajanje servisnih operacija t obs i vrijeme čekanja u redu čekanja toch, kao i duljina reda čekanja loch slučajne varijable, tada su, prema tome, karakteristike stanja QS-a su probabilističke prirode, a za njihovo opisivanje potrebno je primijeniti metode i modele teorije čekanja.

Gore navedene karakteristike k, f, l, Loch, Toch, v, tobs, µ, p, Pk su najčešće za QS, koje su obično samo neki dio funkcije cilja, jer je također potrebno uzeti u obzir pokazatelji komercijalne aktivnosti.

1 . 3 Najjednostavniji QS s kvarovima

n-kanalni QS s kvarovima prima najjednostavniji tok zahtjeva s intenzitetom n; vrijeme usluge je indikativno za parametar. Stanja QS-a su numerirana prema broju zahtjeva koji se nalaze u QS-u (zbog nepostojanja reda čekanja, podudara se s brojem zauzetih kanala):

S0 - QS je slobodan;

S1 - jedan kanal je zauzet, ostali su slobodni;

...;

S k- zaposlen k kanali, ostali su besplatni (1 kn);

…;

S n- svi su zauzeti n kanala.

Konačne vjerojatnosti stanja izražavaju se Erlangovim formulama:

gdje je s=l/m.

Karakteristike učinkovitosti:

A=(1-str n); Q = 1-p n; Ptk= str n; =(1-str n).

Za velike vrijednosti P vjerojatnosti stanja (1*) prikladno se izračunavaju pomoću tabličnih funkcija:

(Poissonova distribucija) i

,

od kojih se prvi može izraziti kroz drugi:

Pomoću ovih funkcija Erlangove formule (1*) mogu se prepisati u obliku

.

1.4 Jednokanalni QS s kvarovima

Analizirajmo jednostavan jednokanalni QS s kvarovima servisa, koji prima Poissonov protok zahtjeva intenziteta l, a servisiranje se odvija pod utjecajem Poissonovog protoka intenziteta m.

Rad jednokanalnog QS n=1 može se prikazati u obliku označenog grafikona stanja (3.1).

Prijelazi QS-a iz jednog stanja S0 u drugo S1 događaju se pod utjecajem ulaznog toka zahtjeva intenziteta l, a obrnuti prijelaz događa se pod utjecajem servisnog toka intenziteta m.

Zapišimo sustav Kolmogorovih diferencijalnih jednadžbi za vjerojatnosti stanja prema gore navedenim pravilima:

Gdje ćemo dobiti diferencijalnu jednadžbu za određivanje vjerojatnosti p0(t) stanja S0:

Ova se jednadžba može riješiti pod početnim uvjetima uz pretpostavku da je sustav u trenutku t=0 bio u stanju S0, tada je p0(0)=1, p1(0)=0.

U ovom slučaju, rješavanje diferencijalne jednadžbe omogućuje nam da odredimo vjerojatnost da je kanal slobodan i da nije zauzet uslugom:

Tada je lako dobiti izraz za vjerojatnost određivanja vjerojatnosti zauzetosti kanala:

Vjerojatnost p0(t) opada tijekom vremena iu granici pri t>? teži vrijednosti

a vjerojatnost p1(t) u isto vrijeme raste od 0, težeći granici pri t>? na veličinu

Ove granice vjerojatnosti mogu se dobiti izravno iz priloženih Kolmogorovljevih jednadžbi

Funkcije r0(t) i r1(t) definiraju prijelazni proces u jednokanalnom QS-u i opisuju proces eksponencijalnog približavanja QS-a svom graničnom stanju s vremenskom konstantom karakterističnom za sustav koji se razmatra.

S dovoljnom točnošću za praksu, možemo pretpostaviti da proces tranzicije u QS-u završava unutar vremena jednakog 3f.

Vjerojatnost p0(t) određuje relativni kapacitet QS-a, koji određuje udio servisiranih aplikacija u odnosu na ukupni broj dolaznih aplikacija u jedinici vremena.

Doista, p0(t) je vjerojatnost da će zahtjev koji stigne u vrijeme t biti prihvaćen za uslugu. Ukupno u jedinici vremena stigne prosječno l prijava, a servisira se lr0 prijava.

Tada će vrijednost biti određena udjelom servisiranih aplikacija u odnosu na cjelokupni tok aplikacija

U granici kod t>? praktički će već pri t>3ph vrijednost relativne propusnosti biti jednaka

Apsolutna propusnost, koja određuje broj zahtjeva opsluženih po jedinici vremena u ograničenju na t>?, jednaka je:

Sukladno tome, udio zahtjeva koji su odbijeni je, pod istim ograničavajućim uvjetima:

a ukupan broj neposluženih aplikacija jednak je

Primjeri jednokanalnog QS-a s uskraćivanjem usluge su: šalter za narudžbe u trgovini, kontrolna soba poduzeća za motorni prijevoz, ured skladišta, ured uprave trgovačkog poduzeća, s kojim se komunikacija uspostavlja telefonom.

1.5 Višekanalni QS s kvarovima

U komercijalnim aktivnostima, primjeri višekanalnog QS-a su uredi komercijalnih poduzeća s nekoliko telefonskih kanala; besplatna služba za pomoć za dostupnost najjeftinijih automobila u auto trgovinama u Moskvi ima 7 telefonskih brojeva, a, kao što je poznato, vrlo teško nazvati i dobiti pomoć.

Posljedično, auto trgovine gube kupce, mogućnost povećanja broja prodanih automobila i prihoda od prodaje, prometa i dobiti.

Turističke tvrtke koje prodaju turističke pakete imaju dva, tri, četiri ili više kanala, kao što je Express-Line.

Razmotrimo višekanalni QS s kvarovima usluge čiji ulaz prima Poissonov protok zahtjeva s intenzitetom l.

Protok usluge u svakom kanalu ima intenzitet m. Na temelju broja QS zahtjeva određuju se njegova stanja Sk, prikazana u obliku označenog grafa:

S0 - svi kanali su slobodni k=0,

S1 - samo jedan kanal je zauzet, k=1,

S2 - samo dva kanala su zauzeta, k=2,

Sk - k kanali su zauzeti,

Sn - svih n kanala je zauzeto, k= n.

Stanja višekanalnog QS-a se naglo mijenjaju u slučajnim vremenima. Prijelaz iz jednog stanja, na primjer S0 u S1, događa se pod utjecajem ulaznog toka zahtjeva intenziteta l, i obrnuto - pod utjecajem toka uslužnih zahtjeva intenziteta m.

Za prijelaz sustava iz stanja Sk u Sk-1 nije važno koji se kanal oslobađa, stoga tok događaja koji prenosi QS ima intenzitet km, dakle tok događaja koji prenosi sustav iz Sn do Sn-1 ima intenzitet od nm.

Ovako je formuliran klasični Erlangov problem, nazvan po danskom inženjeru i matematičaru koji je utemeljio teoriju čekanja u redu.

Slučajni proces koji se događa u QS-u poseban je slučaj procesa "rođenje-smrt" i opisuje se sustavom Erlangovih diferencijalnih jednadžbi, koje omogućuju dobivanje izraza za granične vjerojatnosti stanja sustava koji se razmatra, nazvane Erlangove formule:

.

Izračunavanjem svih vjerojatnosti stanja n-kanalnog QS-a s kvarovima p0, p1, p2, ..., pk,..., pn, mogu se pronaći karakteristike uslužnog sustava.

Vjerojatnost odbijanja usluge određena je vjerojatnošću da će dolazni zahtjev za uslugom pronaći svih n kanala zauzetima, sustav će biti u Sn stanju:

k=n.

U sustavima s kvarovima, kvarovi i događaji održavanja čine kompletnu grupu događaja, dakle:

Rotk+Robs=1

Na temelju toga, relativna propusnost određena je formulom

Q = Pobs = 1-Rotk = 1-Pn

Apsolutni kapacitet QS-a može se odrediti formulom

A=l*Robs

Vjerojatnost usluge, ili udio isporučenih zahtjeva, određuje relativni kapacitet QS-a, koji se može odrediti pomoću druge formule:

Iz ovog izraza možete odrediti prosječan broj zahtjeva pod uslugom ili, što je isto, prosječan broj kanala koje usluga zauzima

Stopa popunjenosti kanala po uslugama određena je omjerom prosječnog broja zauzetih kanala i njihovog ukupnog broja

Vjerojatnost da će kanali biti zauzeti uslugom, koja uzima u obzir prosječno vrijeme zauzetosti tbusy i vrijeme mirovanja tpr kanala, određuje se na sljedeći način:

Iz ovog izraza možete odrediti prosječno vrijeme prekida rada kanala

Prosječno vrijeme koje zahtjev ostaje u sustavu u stabilnom stanju određeno je Littleovom formulom

Tsmo= nz/l.

1.6 Jednokanalni QS s ograničenom duljinom čekanja

U trgovačkim djelatnostima češća je QS s čekanjem (queuing).

Razmotrimo jednostavan jednokanalni QS s ograničenim redom čekanja, u kojem je broj mjesta u redu čekanja m fiksna vrijednost. Slijedom toga, prijava zaprimljena u trenutku kada su sva mjesta u redu čekanja zauzeta ne prihvaća se na uslugu, ne ulazi u red čekanja i napušta sustav.

Grafikon ovog QS-a prikazan je na sl. 3.4 i poklapa se s grafom na sl. 2.1 koji opisuje proces “rađanja-smrti”, s tom razlikom da u prisustvu samo jednog kanala.

Označeni graf procesa usluge “rođenje - smrt”, svi intenziteti tokova usluge su jednaki

Stanja QS-a mogu se predstaviti na sljedeći način:

S0 - kanal usluge je besplatan,

S, - servisni kanal je zauzet, ali nema čekanja,

S2 - servisni kanal je zauzet, postoji jedan zahtjev u redu čekanja,

S3 - servisni kanal je zauzet, u redu su dva zahtjeva,

Sm+1 - servisni kanal je zauzet, svih m mjesta u redu je zauzeto, svaki sljedeći zahtjev se odbija.

Kako biste opisali slučajni QS proces, možete koristiti prethodno navedena pravila i formule. Napišimo izraze koji određuju granične vjerojatnosti stanja:

Izraz za p0 se u ovom slučaju može napisati na jednostavniji način, koristeći činjenicu da nazivnik sadrži geometrijsku progresiju u odnosu na p, pa nakon odgovarajućih transformacija dobivamo:

c= (1- S)

Ova formula vrijedi za sve p osim 1, ali ako je p = 1, tada je p0 = 1/(m + 2), a sve ostale vjerojatnosti također su jednake 1/(m + 2).

Ako pretpostavimo da je m = 0, tada prelazimo s razmatranja jednokanalnog QS-a s čekanjem na već razmatrani jednokanalni QS s uskraćivanjem usluge.

Doista, izraz za graničnu vjerojatnost p0 u slučaju m = 0 ima oblik:

po = m / (l+m)

A u slučaju l = m ima vrijednost p0 = 1 / 2.

Odredimo glavne karakteristike jednokanalnog QS-a s čekanjem: relativnu i apsolutnu propusnost, vjerojatnost kvara, kao i prosječnu duljinu čekanja i prosječno vrijeme čekanja aplikacije u redu čekanja.

Prijava je odbijena ako stigne u trenutku kada je QS već u stanju Sm+1 i stoga su sva mjesta u redu čekanja zauzeta i jedan kanal služi

Stoga je vjerojatnost neuspjeha određena vjerojatnošću pojavljivanja

Sm+1 navodi:

Ptk = pm+1 = sm+1 * p0

Relativna propusnost, odnosno udio servisiranih zahtjeva koji stižu po jedinici vremena, određen je izrazom

Q = 1-rotk = 1- cm+1 * p0

apsolutna propusnost je:

Prosječan broj prijava L u redu čekanja za uslugu određen je matematičkim očekivanjem slučajne varijable k - broj prijava u redu čekanja

Slučajna varijabla k uzima samo sljedeće cjelobrojne vrijednosti:

1 - postoji jedna aplikacija u redu čekanja,

2 - postoje dvije aplikacije u redu čekanja,

t-sva mjesta u redu su zauzeta

Vjerojatnosti ovih vrijednosti određene su odgovarajućim vjerojatnostima stanja, počevši od stanja S2. Zakon distribucije diskretne slučajne varijable k prikazan je na sljedeći način:

Tablica 1. Zakon distribucije diskretne slučajne varijable

Matematičko očekivanje ove slučajne varijable je:

Loch = 1* p2 +2* p3 +...+ m* pm+1

U općem slučaju, za p ? 1, ovaj se zbroj može transformirati, koristeći modele geometrijske progresije, u prikladniji oblik:

Loch = p2 * 13:00 * (m-m*p+1)* p0

U posebnom slučaju kada je p = 1, kada su sve vjerojatnosti pk jednake, možete koristiti izraz za zbroj članova numeričkog niza

1+2+3+ m = m(m+1)

Tada dobivamo formulu

L"och= m(m+1)* p0 = m(m+1)(p=1).

Koristeći slično razmišljanje i transformacije, može se pokazati da je prosječno vrijeme čekanja za servisiranje zahtjeva u redu čekanja određeno Littleovim formulama

Točka = Loch/A (na p? 1) i T1och= L"och/A (na p = 1).

Ovaj rezultat, kada se pokaže da je Toc ~ 1/l, može izgledati čudno: s povećanjem intenziteta protoka prijava, čini se da raste duljina reda i smanjuje se prosječno vrijeme čekanja. Međutim, treba imati na umu da je, kao prvo, vrijednost Locha funkcija l i m i, kao drugo, QS koji se razmatra ima ograničenu duljinu čekanja na ne više od m aplikacija.

Prijava primljena od strane QS-a u trenutku kada su svi kanali zauzeti biva odbijena, pa je stoga njeno vrijeme “čekanja” u QS-u jednako nuli. To dovodi u općem slučaju (za p? 1) do smanjenja Tochromost l, jer udio takvih zahtjeva raste s povećanjem l.

Ako odustanemo od ograničenja duljine čekanja, tj. izravni m--> >?, zatim padeži str< 1 и р?1 начинают существенно различаться. Записанные выше формулы для вероятностей состояний преобразуются в случае р < 1 к виду

Kada je k dovoljno velik, vjerojatnost pk teži nuli. Stoga će relativna propusnost biti Q = 1, a apsolutna propusnost jednaka A --l Q -- l Prema tome, svi dolazni zahtjevi su opsluženi, a prosječna duljina reda čekanja bit će jednaka:

Loch = str2 1-str

a prosječno vrijeme čekanja prema Littleovoj formuli

Točka = Loch/A

U granici str<< 1 получаем Точ = с / м т.е. среднее время ожидания быстро уменьшается с увеличением интенсивности потока обслуживания. В противном случае при р? 1 оказывается, что в СМО отсутствует установившийся режим. Обслуживание не успевает за потоком заявок, и очередь неограниченно растет со временем (при t >?). Granične vjerojatnosti stanja stoga se ne mogu odrediti: za Q = 1 one su jednake nuli. Zapravo, QS ne ispunjava svoje funkcije, budući da nije u mogućnosti servisirati sve dolazne aplikacije.

Nije teško utvrditi da su udio servisiranih aplikacija, odnosno apsolutni protok u prosjeku c i m, međutim, neograničeno povećanje reda čekanja, a time i vremena čekanja u njemu, dovodi do toga da nakon nekog time se aplikacije počnu gomilati u redu čekanja na neodređeno dugo vrijeme.

Kao jedna od karakteristika QS-a koristi se prosječno vrijeme Tsmo boravka aplikacije u QS-u, uključujući prosječno vrijeme provedeno u redu čekanja i prosječno vrijeme usluge. Ova se vrijednost izračunava pomoću Littleovih formula: ako je duljina reda čekanja ograničena, prosječan broj aplikacija u redu čekanja jednak je:

Lsmo= m+1 ;2

Tsmo= Lsmo; na p?1

I tada je prosječno vrijeme zadržavanja zahtjeva u sustavu čekanja (i u redu čekanja i na usluzi) jednako:

Tsmo= m+1 pri p ?1 2m

1.7 Jednokanalni QS s neograničenim redom

U komercijalnim aktivnostima, na primjer, komercijalni direktor djeluje kao jednokanalni CMO s neograničenim čekanjem, budući da je u pravilu prisiljen servisirati zahtjeve različite prirode: dokumente, telefonske razgovore, sastanke i razgovore s podređenima, predstavnicima porezna inspekcija, policija, robni vještaci, trgovci, dobavljači proizvoda i probleme u robno-financijskoj sferi rješavaju s visokim stupnjem financijske odgovornosti, što je povezano s obveznim ispunjavanjem zahtjeva koji ponekad nestrpljivo čekaju ispunjenje svojih zahtjeva, te greške neispravne usluge su u pravilu vrlo ekonomski značajne. Markovljev model održavanja kvara

U isto vrijeme, roba uvezena za prodaju (uslugu), dok je u skladištu, čini red za uslugu (prodaju).

Duljina reda je broj robe namijenjene prodaji. U ovoj situaciji prodavači djeluju kao kanali koji opslužuju robu.

Ako je količina robe namijenjene prodaji velika, tada se u ovom slučaju radi o tipičnom slučaju QS s čekanjem.

Razmotrimo najjednostavniji jednokanalni QS s čekanjem na uslugu, koji prima Poissonov tok zahtjeva s intenzitetom l i intenzitetom usluge?.

Štoviše, zahtjev primljen u vrijeme kada je kanal zauzet servisiranjem stavlja se u red čekanja i čeka uslugu.

Označeni graf stanja takvog sustava prikazan je na sl. 3.5

Broj mogućih stanja je beskonačan:

Kanal je besplatan, nema čekanja u redu, ;

Kanal je zauzet servisom, nema čekanja, ;

Kanal zauzet, jedan zahtjev u redu, ;

Kanal je zauzet, aplikacija je u redu.

Modeli za procjenu vjerojatnosti stanja QS-a s neograničenim redom čekanja mogu se dobiti iz formula dodijeljenih za QS s neograničenim redom čekanja prelaskom na ograničenje pri m>?:

Treba napomenuti da za QS s ograničenom duljinom čekanja u formuli

postoji geometrijska progresija s prvim članom 1 i nazivnikom.

Takav niz je zbroj beskonačnog broja članova na.

Ovaj zbroj konvergira ako progresija, koja se beskonačno smanjuje na, koja određuje stacionarni način rada QS-a, s redom čekanja na može rasti do beskonačnosti tijekom vremena.

Budući da u razmatranom QS-u ne postoji ograničenje duljine reda čekanja, može se poslužiti bilo koji zahtjev, dakle, relativna propusnost, odnosno apsolutna propusnost

Vjerojatnost da k aplikacija bude u redu čekanja je:

Prosječan broj prijava u redu čekanja -

Prosječan broj prijava u sustavu -

Prosječno vrijeme koje aplikacija ostaje u sustavu -

Prosječno vrijeme koje aplikacija ostaje u sustavu -

Ako je u jednokanalnom QS-u s čekanjem intenzitet primljenih zahtjeva veći od intenziteta usluge, tada će se red stalno povećavati. U tom smislu, analiza stabilnih QS sustava koji rade u stacionarnom načinu rada na.

1.8 Višekanalni QS s ograničenom duljinom čekanja

Razmotrimo višekanalni QS, čiji ulaz prima Poissonov tok zahtjeva s intenzitetom, a intenzitet usluge svakog kanala je, maksimalni mogući broj mjesta u redu čekanja ograničen je s m. Diskretna stanja QS-a određena su brojem prijava koje je primio sustav i koje se mogu zabilježiti.

Svi kanali su besplatni;

Samo jedan kanal (bilo koji) je zauzet;

Samo dva kanala (bilo koja) su zauzeta;

Svi kanali su zauzeti.

Dok je QS u bilo kojem od ovih stanja, nema čekanja. Nakon što su svi servisni kanali zauzeti, naredni zahtjevi formiraju red čekanja, određujući na taj način daljnje stanje sustava:

Svi kanali su zauzeti i jedna aplikacija je u redu čekanja,

Svi kanali su zauzeti i dva zahtjeva su u redu,

Svi kanali i sva mjesta u redu su zauzeti,

Prijelaz QS-a u stanje s velikim brojevima određen je protokom pristiglih zahtjeva s intenzitetom, dok prema uvjetu u opsluživanju tih zahtjeva sudjeluju identični kanali s jednakim intenzitetom protoka usluge za svaki kanal. U tom slučaju ukupni intenzitet protoka usluge raste sa spajanjem novih kanala do stanja kada je svih n kanala zauzeto. Pojavom reda čekanja intenzivnost usluge se dodatno povećava, jer je već dosegla maksimalnu vrijednost jednaku.

Zapišimo izraze za granične vjerojatnosti stanja:

Izraz za može se transformirati pomoću formule geometrijske progresije za zbroj članova s ​​nazivnikom:

Formiranje reda čekanja moguće je kada novoprimljena prijava pronađe barem zahtjeve u sustavu, tj. kada postoje zahtjevi u sustavu.

Ovi događaji su neovisni, pa je vjerojatnost da su svi kanali zauzeti jednaka zbroju odgovarajućih vjerojatnosti

Stoga je vjerojatnost formiranja reda čekanja:

Vjerojatnost odbijanja usluge javlja se kada su svi kanali i sva mjesta u redu čekanja zauzeti:

Relativna propusnost bit će jednaka:

Apsolutna propusnost -

Prosječan broj zauzetih kanala -

Prosječan broj neaktivnih kanala -

Faktor zauzetosti (korištenja) kanala -

Omjer prekida rada kanala -

Prosječan broj prijava u redovima -

Ako ova formula ima drugačiji oblik -

Prosječno vrijeme čekanja u redu određeno je Littleovim formulama -

Prosječno vrijeme boravka aplikacije u QS-u, kao i za jednokanalni QS, veće je od prosječnog vremena čekanja u redu čekanja za prosječno vrijeme servisiranja, koje je jednako, jer aplikaciju uvijek opslužuje samo jedan kanal:

1.9 Višekanalni QS s neograničenim redom čekanja

Razmotrimo višekanalni QS s čekanjem i neograničenom duljinom reda čekanja, koji prima tok zahtjeva s intenzitetom i koji ima intenzitet usluge svakog kanala.

Označeni graf stanja prikazan je na slici 3.7. Ima beskonačan broj stanja:

S - svi kanali su slobodni, k=0;

S - jedan kanal je zauzet, ostali su slobodni, k=1;

S - dva kanala su zauzeta, ostali su slobodni, k=2;

S - svih n kanala je zauzeto, k=n, nema čekanja;

S - svih n kanala je zauzeto, jedan zahtjev je u redu čekanja, k=n+1,

S - svih n kanala je zauzeto, r aplikacija je u redu, k=n+r,

Vjerojatnosti stanja dobivamo iz formula za višekanalni QS s ograničenim redom pri prijelazu na granicu na m.

Treba napomenuti da zbroj geometrijske progresije u izrazu za p divergira na razini opterećenja p/n>1, red čekanja će se povećavati neograničeno, a na p/n<1 ряд сходится, что определяет установившийся стационарный режим работы СМО.

Nema čekanja u redu

Budući da u takvim sustavima ne može biti uskraćivanja usluge, karakteristike propusnosti su jednake:

prosječan broj prijava u redu čekanja -

prosječno vrijeme čekanja u redu -

prosječan broj prijava CMO-u -

Vjerojatnost da je QS u stanju u kojem nema zahtjeva i nijedan kanal nije zauzet određena je izrazom

Ova vjerojatnost određuje prosječni postotak prekida servisnog kanala. Vjerojatnost da budete zauzeti servisiranjem k zahtjeva -

Na temelju toga moguće je odrediti vjerojatnost, odnosno udio vremena da su svi kanali zauzeti uslugom

Ako su svi kanali već zauzeti servisiranjem, tada je vjerojatnost stanja određena izrazom

Vjerojatnost da budete u redu čekanja jednaka je vjerojatnosti da pronađete sve kanale koji su već zauzeti uslugom

Prosječan broj prijava u redu čekanja i usluga na čekanju je:

Prosječno vrijeme čekanja na aplikaciju u redu prema Littleovoj formuli:

i u sustavu

prosječan broj kanala koje usluga zauzima:

prosječan broj besplatnih kanala:

omjer zauzetosti uslužnog kanala:

Važno je napomenuti da parametar karakterizira stupanj usklađenosti ulaznog toka, na primjer, kupaca u trgovini s intenzitetom protoka usluge. Proces usluživanja bit će stabilan ako se u sustavu povećava prosječna duljina reda i prosječno vrijeme čekanja kupaca na početak usluge, pa će stoga sustav usluga raditi nestabilno.

1.10 QS algoritam modeliranja

QS koji se razmatra u problemu je QS sa:

Dvokanalna usluga;

Dvokanalni ulazni tok (ima 2 ulaza, od kojih jedan prima nasumični tok naloga I, a drugi ulaz prima tok naloga II).

Određivanje termina zaprimanja i servisiranja zahtjeva:

· Vremena primitka i servisiranja zahtjeva generiraju se nasumično uz zadani eksponencijalni zakon distribucije;

· Navedene su cijene zaprimanja i servisiranja zahtjeva;

Funkcioniranje razmatranog QS-a:

Svaki kanal opslužuje jedan po jedan zahtjev;

Ako je u trenutku primitka novog zahtjeva barem jedan kanal slobodan, tada se dolazni zahtjev prima na uslugu;

Ako nema aplikacija, sustav je u stanju mirovanja.

Disciplina servisa:

Prioritet Naloga I: ako je sustav zauzet (oba kanala poslužuju naloge), a jedan od kanala je zauzet Nalogom II, Nalog I ima prednost nad Nalogom II; Zahtjev II ostavlja sustav neposluženim;

Ako su do trenutka kada zahtjev II stigne oba kanala zauzeta, zahtjev II se ne servisira;

Ako do trenutka kada Nalog I stigne, oba kanala opslužuju Nalog I, primljeni Nalog I ostavlja sustav neposluženim;

Zadatak modeliranja: poznavajući parametre ulaznih tokova zahtjeva, simulirati ponašanje sustava i izračunati njegove glavne karakteristike njegove učinkovitosti. Promjenom vrijednosti T s manjih vrijednosti na veće (vremenski interval tijekom kojeg se događa slučajni proces prijema prijava 1. i 2. toka u QS za uslugu), možete pronaći promjene u kriteriju učinkovitosti rada i odaberite optimalnu.

Kriteriji za učinkovitost funkcioniranja QS-a:

· Vjerojatnost neuspjeha;

· Relativna propusnost;

· Apsolutna propusnost;

Princip modeliranja:

Predstavljamo početne uvjete: ukupno vrijeme rada sustava, vrijednosti intenziteta tokova aplikacije; broj implementacija sustava;

Generiramo vremenske točke u kojima zahtjevi stižu, redoslijed pristizanja zahtjeva I, zahtjeva II, vrijeme usluge svakog dolaznog zahtjeva;

Brojimo koliko je zahtjeva servisirano, a koliko odbijeno;

Izračunavamo kriterij učinkovitosti QS-a;

POGLAVLJE2 . PRAKTIČNI DIO

Slika 1. Ovisnost OPSS-a o vremenu

PROGRAM CAN_SMO;

KANAL = (SLOBODAN, ZAHTJEV1, ZAHTJEV2);

INTENZITET = riječ;

STATISTIKA = riječ;

CHANNAL1, CHANNAL2: CHANNAL; (kanali)

T_, t, tc1, tc2: VRIJEME; (Vrijeme)

l1, l2, n1, n2: INTENZITET; (intenzitet)

služio1, nije_služio1,

služio2, nije_servirao2,

S: STATISTIKA; (Statistika)

M,N:CIJELI BROJ;(broj implementacija)

FUNKCIJA W(t: VRIJEME; l: INTENZITET) : boolean; (Određuje je li se red pojavio)

Početak (prema intenzitetu protoka l)

ako slučajno< l/60 then W:= TRUE else W:= FALSE;

FUNKCIJA F(t: VRIJEME; n: INTENZITET) : VRIJEME; (Određuje koliko će dugo aplikacija biti obrađena)

Početak (prema intenzitetu servisnih zahtjeva n)

F:= t +okruglo(60/(n));

Slika 2. Ovisnost OPPS-a o vremenu

WRITELN("UNESITE BROJ IMPLEMENTACIJA SMO");

writeln(M, "th implementacija");

KANAL1:= BESPLATNO; KANAL2:= BESPLATNO;

l1:= 3; l2:= 1; n1:= 2; n2:= 1;

posluženo1:= 0; nije_servirano1:= 0;

posluženo2:= 0; nije_servirano2:= 0;

write("Unesite vrijeme SMO studije - T: "); readln(_T_);

if CHANNAL1 = CLAIM1 then inc(served1) else inc(served2);

KANAL1:= BESPLATNO;

writeln("Kanal1 je završio zahtjev");

if CHANNAL2 = CLAIM1 then inc(served1) else inc(served2);

KANAL2:= BESPLATNO;

writeln("Kanal2 je završio zahtjev");

Slika 3. Grafikon vjerojatnosti kvara u sustavu u odnosu na vrijeme

writeln("Zahtjev1 primljen");

ako je CHANNAL1 = BESPLATNO tada

početak CHANNAL1:= CLAIM1; tc1:= F(t,n1); writeln("Kanal1 prihvatio zahtjev1"); kraj

inače ako je CHANNAL2 = BESPLATNO

početak CHANNAL2:= CLAIM1; tc2:= F(t,n1); writeln("Kanal2 prihvatio zahtjev1"); kraj

inače ako je CHANNAL1 = CLAIM2 tada

početak CHANNAL1:= CLAIM1; tc1:= F(t,n1); inc(not_served2); writeln("Kanal1 je prihvatio zahtjev1 umjesto zahtjeva2"); kraj

inače ako je CHANNAL2 = CLAIM2 tada

početak CHANNAL2:= CLAIM1; tc2:= F(t,n1); inc(not_served2); writeln("Kanal2 je prihvatio zahtjev1 umjesto zahtjeva2"); kraj

else begin inc(not_served1); writeln("zahtjev 1 nije servisiran"); kraj;

Slika 4. Ovisnost broja aplikacija o vremenu

writeln("Zahtjev2 primljen");

ako je CHANNAL1 = BESPLATNO tada

početak CHANNAL1:= CLAIM2; tc1:= F(t,n2); writeln("Kanal1 prihvatio zahtjev2");kraj

inače ako je CHANNAL2 = BESPLATNO

početak CHANNAL2:= CLAIM2; tc2:= F(t,n2); writeln("Kanal2 prihvatio zahtjev2");kraj

else begin inc(not_served2); writeln("zahtjev2 nije servisiran"); kraj;

S:= posluženo1 + nije_posluženo1 + posluženo2 + nije_posluženo2;

writeln("Vrijeme rada SMO ",_T_);

writeln("served by channel1: " ,served1);

writeln("served by channel2: ",served2);

writeln("Primljeni zahtjevi: ",S);

writeln("Usluženi zahtjevi: ",served1+served2);

writeln("Zahtjevi nisu usluženi: ",not_served1+not_served2);

(writeln("Intenzitet zahtjeva koji ulaze u sustav: ",(served1+served2)/_T_:2:3);)

writeln("Apsolutna propusnost sustava: ",(served1+served2)/T:2:3);

writeln("Vjerojatnost kvara: ",(not_served1+not_served2)/S*100:2:1,"%");

writeln("Relativna propusnost sustava: ",(served1+served2)/S:2:3);

writeln("simulacija završena");

Tablica 2. Rezultati rada QS-a

Karakteristike rada QS-a

SMO radno vrijeme

Zaprimljene prijave

Prijave uručene

Nema usluženih zahtjeva

Apsolutna propusnost sustava

Relativna propusnost sustava

POGLAVLJE 3.SIGURNOSNE MJERE

Opće odredbe

· U informatičkoj učionici smiju raditi osobe koje su upoznate sa sigurnosnim uputama i pravilima ponašanja.

· U slučaju kršenja uputa, student se udaljava s rada i može učiti samo uz pisano dopuštenje nastavnika.

· Rad studenata u informatičkoj učionici dopušten je samo u prisustvu nastavnika (inženjera, laboranta).

· Ne zaboravite da je svaki učenik odgovoran za stanje svog radnog mjesta i sigurnost opreme koja se na njemu nalazi.

Prije početka rada:

· Prije početka rada provjerite da nema vidljivih oštećenja na opremi i žicama. Računala i periferni uređaji moraju biti postavljeni u stabilnom položaju na stolovima.

· Učenicima je strogo zabranjen pristup uređajima. Uređaje možete uključiti samo uz dopuštenje učitelja.

Prilikom rada u informatičkoj klasi zabranjeno je:

1. Ulazak i izlazak iz učionice bez dopuštenja nastavnika.

2. Kasnite na nastavu.

3. Uđite u učionicu u prljavim i mokrim cipelama, prašnjavoj odjeći i gornjoj odjeći u hladnoj sezoni.

4. Radite na računalu mokrih ruku.

5. Stavite strane predmete na radno mjesto.

6. Ustanite dok radite, okrenite se, razgovarajte sa susjedom.

7. Uključite i isključite opremu bez dopuštenja učitelja.

8. Kršiti postupak za uključivanje i isključivanje opreme.

9. Dodirujte tipkovnicu i miša kada je računalo isključeno, premještajte namještaj i opremu.

10. Dodirnite zaslon, kabele, spojne žice, konektore, utikače i utičnice.

11. Prilaziti radnom mjestu nastavnika bez dopuštenja

Glavna prijetnja ljudskom zdravlju pri radu s računalom je opasnost od strujnog udara. Stoga je zabranjeno:

1. Rad na opremi koja ima vidljive nedostatke. Otvorite jedinicu sustava.

2. Spojite ili odspojite kabele, dodirne konektore spojnih kabela, žice i utičnice, uređaje za uzemljenje.

3. Dodirnite zaslon i stražnju stranu monitora i tipkovnicu.

4. Pokušajte sami otkloniti kvarove opreme.

5. Radite u vlažnoj odjeći i mokrim rukama

6. Ispunjava uvjete nastavnika i laboranta; Održavati tišinu i red;

7. Dok ste online, radite samo pod svojim imenom i lozinkom;

8. Pridržavajte se načina rada (u skladu sa sanitarnim pravilima i standardima);

9. Počinjati i završavati rad samo uz dopuštenje učitelja.

10. Ako dođe do naglog pogoršanja zdravstvenog stanja (bol u očima, naglo pogoršanje vidljivosti, nemogućnost fokusiranja ili izoštravanja pogleda, bolovi u prstima i rukama, ubrzan rad srca), odmah napustite radno mjesto, prijavite incident učitelja i posavjetovati se s liječnikom;

11. Održavajte radno mjesto čistim.

12. Dovršite rad uz dopuštenje nastavnika.

13. Predajte završeni rad.

14. Zatvorite sve aktivne programe i ispravno ugasite računalo.

15. Uredite radno mjesto.

16. Dežurni treba provjeriti spremnost ureda za sljedeću lekciju.

Prilikom rada s opremom morate se čuvati: - strujnog udara;

- mehanička oštećenja, ozljede

U hitnim slučajevima:

1. Ako se otkrije iskrenje, pojavi se miris paljevine ili se otkriju drugi problemi, trebali biste odmah prestati s radom i obavijestiti učitelja.

2. Ako netko bude pogođen strujnim udarom, potrebno je: prekinuti rad i udaljiti se na sigurnu udaljenost; isključite napon (na razvodnoj ploči ormara); obavijestiti nastavnika; Pružite prvu pomoć i pozovite liječnika.

3. U slučaju požara potrebno je: prekinuti rad i započeti evakuaciju; obavijestiti učitelja i pozvati vatrogasce (tel. 01); isključite napon (na razvodnoj ploči ormara); Pristupiti gašenju požara aparatom za gašenje požara (zabranjeno je gašenje vodom.

Slični dokumenti

Matematička teorija čekanja kao grana teorije slučajnih procesa. Sustavi čekanja za zahtjeve koji stižu u intervalima. Otvorena Markovljeva mreža, njen ne-Markovljev slučaj, nalaženje stacionarnih vjerojatnosti.

kolegij, dodan 09/07/2009


Pojam sustava čekanja, njegova suština i značajke. Teorija čekanja kao jedna od grana teorije vjerojatnosti, pitanja koja se razmatraju. Pojam i karakteristike slučajnog procesa, njegove vrste i modeli. Usluga čekanja.

kolegij, dodan 15.02.2009


Optimizacija kontrole tijeka zahtjeva u mrežama čekanja. Metode za utvrđivanje ovisnosti između prirode zahtjeva, broja uslužnih kanala, njihove produktivnosti i učinkovitosti. Teorija grafova; Kolmogorova jednadžba, tokovi događaja.

test, dodan 01.07.2015


Teorija čekanja je područje primijenjene matematike koje analizira procese u proizvodnim sustavima u kojima se homogeni događaji ponavljaju mnogo puta. Određivanje parametara sustava čekanja s konstantnim karakteristikama.

kolegij, dodan 01.08.2009


Definicija slučajnog procesa i njegove karakteristike. Osnovni pojmovi teorije čekanja. Pojam Markovljevog slučajnog procesa. Streamovi događaja. Kolmogorovljeve jednadžbe. Granične vjerojatnosti stanja. Procesi smrti i reprodukcije.

sažetak, dodan 01.08.2013


Stacionarna distribucija vjerojatnosti. Konstrukcija matematičkih modela, prijelazni grafovi. Dobivanje jednadžbe ravnoteže za sustave čekanja s različitim brojem uređaja, zahtjevima različitih vrsta i ograničenim redovima na uređajima.

diplomski rad, dodan 23.12.2012


Analiza učinkovitosti najjednostavnijih sustava čekanja, izračun njihovih tehničkih i ekonomskih pokazatelja. Usporedba performansi sustava s kvarovima s odgovarajućim mješovitim sustavom. Prednosti prelaska na sustav s mješovitim svojstvima.

kolegij, dodan 25.02.2012


Izrada simulacijskog modela i izračunavanje pokazatelja rada sustava čekanja na temelju zadanih parametara. Usporedba pokazatelja učinkovitosti s onima dobivenim numeričkim rješavanjem Kolmogorovljevih jednadžbi za vjerojatnosti stanja sustava.

kolegij, dodan 17.12.2009


Primjeri procesa reprodukcije i smrti u slučaju najjednostavnijih sustava čekanja. Matematičko očekivanje za sustav čekanja. Dodatni protok i beskonačan broj uređaja. Sustav s ograničenjem trajanja prijave.

kolegij, dodan 26.01.2014


Neka matematička pitanja iz teorije opsluživanja složenih sustava. Organizacija održavanja s ograničenim informacijama o pouzdanosti sustava. Algoritmi za nesmetan rad sustava i pronalaženje vremena za plansko preventivno održavanje sustava.