Rad na kursu

“Simulacijsko modeliranje sistema čekanja”

na predmetu "Operaciono istraživanje"

Uvod

Prilikom istraživanja operacija često se susreću sa sistemima dizajniranim za višekratnu upotrebu prilikom rješavanja sličnih problema. Procesi koji nastaju nazivaju se uslužni procesi, a sistemi sistemi čekanja (QS). Svaki QS se sastoji od određenog broja servisnih jedinica (instrumenata, uređaja, tačaka, stanica), koje se nazivaju servisni kanali. Kanali mogu biti komunikacione linije, radna mesta, kompjuteri, prodavci itd. Na osnovu broja kanala, QS sistemi se dele na jednokanalne i višekanalne.

Prijave QS obično prima ne redovno, već nasumično, formirajući takozvani slučajni tok prijava (zahtjeva). Servis aplikacija se također nastavlja neko nasumično vrijeme. Nasumična priroda toka aplikacija i vremena servisiranja dovodi do toga da je QS neravnomjerno učitan: u nekim vremenskim periodima se akumulira veoma veliki broj aplikacija (ili dođu u red čekanja ili ostave QS neuslužen), dok u drugim periodima QS radi sa podopterećenjem ili je u stanju mirovanja.

Predmet teorije redova čekanja je izgradnja matematičkih modela koji povezuju date radne uslove QS-a (broj kanala, njihovu produktivnost, prirodu toka zahteva itd.) sa indikatorima performansi QS-a, koji opisuju njegovu sposobnost. da se nosi sa protokom zahteva. Kao indikatori efikasnosti QS-a koriste se:

– Apsolutna propusnost sistema ( A

Q

– vjerovatnoća odbijanja servisiranja zahtjeva ();

k);

– prosječan broj aplikacija u redu čekanja ();

QS je podijeljen u 2 glavna tipa: QS sa kvarovima i QS sa čekanjem (red). U QS-u sa odbijanjima, aplikacija primljena u trenutku kada su svi kanali zauzeti prima odbijenicu, napušta QS i ne učestvuje u daljem procesu usluge (na primjer, prijava za telefonski razgovor u vrijeme kada su svi kanali zauzet, prima odbijenicu i ostavlja QS neuslužen) . U QS-u na čekanju, zahtjev koji stigne u vrijeme kada su svi kanali zauzeti ne odlazi, već se stavlja u red čekanja za uslugu.

Jedna od metoda za izračunavanje indikatora efikasnosti QS je simulacijska metoda. Praktična upotreba računarske simulacije podrazumeva izgradnju odgovarajućeg matematičkog modela koji uzima u obzir faktore nesigurnosti, dinamičke karakteristike i čitav kompleks odnosa između elemenata sistema koji se proučava. Simulacijsko modeliranje rada sistema počinje nekim specifičnim početnim stanjem. Zbog implementacije različitih događaja slučajne prirode, model sistema prelazi u naredna vremena u svoja druga moguća stanja. Ovaj evolutivni proces se nastavlja do završnog trenutka planskog perioda, tj. do završne tačke simulacije.

1. Glavne karakteristike CMO-a i pokazatelje njihove efikasnosti

1.1 Koncept Markovljevog slučajnog procesa

Neka postoji neki sistem koji tokom vremena nasumično mijenja svoje stanje. U ovom slučaju kažu da se u sistemu dešava slučajni proces.

Proces se naziva procesom sa diskretnim stanjima ako se njegova stanja mogu unaprijed navesti i ako se prijelaz sistema iz jednog stanja u drugo dogodi naglo. Proces se naziva procesom kontinuiranog vremena ako se sistemski prijelasci iz stanja u stanje odvijaju trenutno.

Proces rada QS je slučajan proces sa diskretnim stanjima i kontinuiranim vremenom.

Slučajni proces se naziva Markovljevim ili slučajnim procesom bez naknadnog efekta ako za bilo koji trenutak u vremenu vjerovatnoće karakteristike procesa u budućnosti ovise samo o njegovom trenutnom stanju i ne ovise o tome kada i kako je sistem došao do tog stanja. stanje.

Prilikom analize procesa rada QS-a, zgodno je koristiti geometrijski dijagram - graf stanja. Tipično, stanja sistema su prikazana pravokutnicima, a mogući prijelazi iz stanja u stanje su prikazani strelicama. Primjer grafa stanja prikazan je na Sl. 1.

Tok događaja je niz homogenih događaja koji slijede jedan za drugim u nasumično vrijeme.

Protok je karakteriziran intenzitetom λ - učestalošću pojavljivanja događaja ili prosječnim brojem događaja koji ulaze u QS po jedinici vremena.

Tok događaja se naziva regularnim ako događaji slijede jedan za drugim u određenim jednakim vremenskim intervalima.

Tok događaja se naziva stacionarnim ako njegove vjerovatnoće ne zavise od vremena. Konkretno, intenzitet stacionarnog strujanja je konstantna vrijednost: .

Tok događaja se naziva običnim ako je vjerovatnoća da će se dva ili više događaja desiti u malom vremenskom periodu mala u odnosu na vjerovatnoću da se dogodi jedan događaj, odnosno ako se događaji pojavljuju u njemu jedan po jedan, a ne u grupama.

Tok događaja naziva se tok bez naknadnog efekta ako, za bilo koja dva vremenska perioda koja se ne preklapaju, broj događaja koji pada na jedan od njih ne zavisi od broja događaja koji pada na druge.

Tok događaja naziva se najjednostavniji (ili stacionarni Poisson) ako je istovremeno stacionaran, običan i nema naknadni efekat.

1.2 Kolmogorovljeve jednadžbe

Svi prelazi u sistemu iz stanja u stanje odvijaju se pod određenim tokom događaja. Neka je sistem u određenom stanju iz kojeg je moguć prijelaz u stanje, onda možemo pretpostaviti da na sistem utiče jednostavan tok intenziteta koji ga prenosi iz stanja u stanje. Čim se dogodi prvi događaj niti, dolazi do njegovog prijelaza. Radi jasnoće, intenzitet svake strelice koja odgovara prelazu je naznačen na grafikonu stanja. Ovako označeni graf stanja omogućava konstruisanje matematičkog modela procesa, tj. pronaći vjerovatnoće svih stanja kao funkciju vremena. Za njih se sastavljaju diferencijalne jednadžbe, koje se nazivaju Kolmogorovljeve jednadžbe.

Pravilo za sastavljanje Kolmogorovljevih jednačina: Na lijevoj strani svake jednačine je vremenski izvod vjerovatnoće datog stanja. Na desnoj strani je zbir proizvoda svih stanja iz kojih je moguć prijelaz u dato stanje intenzitetom odgovarajućih tokova događaja minus ukupni intenzitet svih tokova koji sistem vode iz datog stanja, pomnožen vjerovatnoćom datog stanja.

Na primjer, za graf stanja prikazan na Sl. 1, Kolmogorovljeve jednadžbe imaju oblik:

Jer na desnoj strani sistema, svaki član se pojavljuje 1 put sa predznakom i 1 put sa predznakom, zatim, sabiranjem svih jednačina, dobijamo da

,

,

Prema tome, jedna od jednačina sistema se može odbaciti i zamijeniti jednačinom (1.2.1).

Da biste dobili konkretno rješenje, potrebno je poznavati početne uslove, tj. vrijednosti vjerovatnoće u početnom trenutku.

1.3 Konačne vjerovatnoće i grafikon stanja QS

Ako je vrijeme procesa u sistemu dovoljno dugo (na ), mogu se ustanoviti vjerovatnoće stanja koja ne zavise od vremena, koja se nazivaju konačne vjerovatnoće, tj. sistem je postavljen na stacionarni način rada. Ako je broj stanja sistema konačan, a iz svakog od njih u konačnom broju koraka moguće je preći u bilo koje drugo stanje, tada postoje konačne vjerovatnoće, tj.

Značenje konačnih vjerovatnoća je da su jednake prosječnom relativnom vremenu u kojem je sistem u datom stanju.

Jer u stacionarnom stanju, vremenski derivati ​​su jednaki nuli, tada se jednačine za konačne vjerovatnoće dobijaju iz Kolmogorovljevih jednačina izjednačavanjem njihovih desnih strana sa nulom.

Grafovi stanja koji se koriste u modelima sistema čekanja nazivaju se obrasci "umri-i-reproduciraj". Ovo ime je zbog činjenice da se ova shema koristi u biološkim problemima vezanim za proučavanje veličine populacije. Njegova posebnost je da se sva stanja sistema mogu predstaviti kao lanac u kojem je svako stanje povezano sa prethodnim i narednim (slika 2).

Rice. 2. Grafikon stanja u QS modelima

Pretpostavimo da su svi tokovi koji prenose sistem iz jednog stanja u drugo najjednostavniji. Prema grafikonu prikazanom na Sl. 2, napravimo jednačine za konačne vjerovatnoće sistema. izgledaju kao:

Rezultat je sistem iz ( n +1) jednadžba, koja se rješava eliminacijom. Ova metoda se sastoji u tome da se sekvencijalno sve vjerovatnoće sistema izražavaju kroz vjerovatnoću.

,

.

Zamjenom ovih izraza u posljednju jednačinu sistema, nalazimo , zatim nalazimo preostale vjerovatnoće QS stanja.

1.4 Pokazatelji učinka QS-a

Svrha QS modeliranja je izračunavanje indikatora performansi sistema kroz njegove karakteristike. Kao indikatori efikasnosti QS-a koriste se:

– apsolutni kapacitet sistema ( A), tj. prosječan broj usluženih aplikacija u jedinici vremena;

– relativna propusnost ( Q), tj. prosječan udio primljenih aplikacija koje servisira sistem;

– vjerovatnoća kvara (), tj. vjerovatnoća da će aplikacija ostaviti QS neuslužen;

– prosječan broj zauzetih kanala ( k);

– prosječan broj aplikacija u QS ();

– prosječno vrijeme boravka aplikacije u sistemu ();

– prosječan broj aplikacija u redu () – dužina reda;

– prosječan broj aplikacija u sistemu ();

– prosječno vrijeme dok aplikacija ostaje u redu čekanja ();

– prosječno vrijeme boravka aplikacije u sistemu ()

– stepen opterećenja kanala (), tj. vjerovatnoća da je kanal zauzet;

– prosječan broj servisiranih zahtjeva u jedinici vremena;

– prosječno vrijeme čekanja na uslugu;

– vjerovatnoća da će broj aplikacija u redu čekanja premašiti određenu vrijednost, itd.

Dokazano je da je za bilo koju prirodu toka aplikacija, za bilo koju distribuciju vremena usluge, za bilo koju uslužnu disciplinu, prosječno vrijeme zadržavanja zahtjeva u sistemu (redu) jednako prosječnom broju aplikacija u sistemu ( queue) podijeljen sa intenzitetom toka aplikacija, tj.

(1.4.1)

Formule (1.4.1) i (1.4.2) se zovu Littleove formule. Oni proizilaze iz činjenice da je u graničnom stacionarnom režimu prosječan broj aplikacija koje pristižu u sistem jednak prosječnom broju aplikacija koje ga napuštaju, tj. oba toka zahtjeva imaju isti intenzitet.

Formule za izračunavanje indikatora efikasnosti date su u tabeli. 1.

Tabela 1.

Indikatori	Jednokanalni QS sa ograničen red	Višekanalni QS sa ograničen red
Final vjerovatnoće
Vjerovatnoća
Apsolutna propusnost sposobnost
Relativna propusnost sposobnost
Prosječan broj prijava po
Prosječan broj prijava po usluga
Prosječan broj aplikacija u sistemu

1.5 Osnovni koncepti simulacijskog modeliranja

Osnovni cilj simulacije je reprodukcija ponašanja sistema koji se proučava na osnovu analize najznačajnijih odnosa njegovih elemenata.

Kompjutersku simulaciju treba smatrati statičkim eksperimentom.

Iz teorije funkcija slučajnih varijabli poznato je da je za modeliranje slučajne varijable sa bilo kojom kontinuiranom i monotono rastućom funkcijom distribucije dovoljno da se može modelirati slučajna varijabla ravnomjerno raspoređena na segmentu. Nakon što ste primili implementaciju slučajne varijable, možete pronaći odgovarajuću implementaciju slučajne varijable, jer su one povezane jednakošću

Pretpostavimo da je u nekom sistemu čekanja vrijeme usluge jednog zahtjeva raspoređeno prema eksponencijalnom zakonu sa parametrom , gdje je intenzitet toka usluge. Tada funkcija raspodjele vremena usluge ima oblik

Neka je realizacija slučajne varijable ravnomjerno raspoređene na segmentu , i neka je odgovarajuća realizacija slučajnog vremena servisiranja jednog zahtjeva. Tada, prema (1.5.1)

1.6 Izgradnja simulacijskih modela

Prva faza kreiranja bilo kog simulacionog modela je faza opisivanja sistema iz stvarnog života u smislu karakteristika glavnih događaja. Ovi događaji se obično povezuju sa prelazima sistema koji se proučava iz jednog mogućeg stanja u drugo i označavaju se kao tačke na vremenskoj osi. Da bi se postigao glavni cilj modeliranja, dovoljno je posmatrati sistem u momentima kada se dešavaju glavni događaji.

Razmotrimo primjer jednokanalnog sistema čekanja. Svrha simulacionog modeliranja ovakvog sistema je da se odrede procjene njegovih glavnih karakteristika, kao što su prosječno vrijeme zadržavanja aplikacije u redu čekanja, prosječna dužina reda i procenat zastoja sistema.

Karakteristike samog procesa čekanja mogu promijeniti svoje vrijednosti bilo kada se primi novi zahtjev za uslugu, ili kada je servisiranje drugog zahtjeva završeno. QS može odmah početi sa servisiranjem sljedećeg zahtjeva (kanal usluge je slobodan), ali će možda biti potrebno sačekati dok zahtjev ne zauzme mjesto u redu (QS sa redom, servisni kanal je zauzet). Nakon završetka servisiranja sljedećeg zahtjeva, QS može odmah započeti servisiranje sljedećeg zahtjeva, ako ga ima, ali može biti i neaktivan ako ga nema. Potrebne informacije se mogu dobiti posmatranjem različitih situacija koje nastaju tokom realizacije glavnih događaja. Dakle, kada zahtjev stigne u QS sa redom i servisni kanal je zauzet, dužina reda se povećava za 1. Slično, dužina reda se smanjuje za 1 ako je servisiranje sljedećeg zahtjeva završeno i skup zahtjeva u redu nije prazan.

Za rad sa bilo kojim simulacijskim modelom potrebno je odabrati vremensku jedinicu. U zavisnosti od prirode sistema koji se modelira, takva jedinica može biti mikrosekunda, sat, godina itd.

Budući da je, u svojoj srži, kompjuterska simulacija računarski eksperiment, njeni opaženi rezultati u agregatu moraju imati svojstva slučajnog uzorka. Samo u ovom slučaju će biti osigurana ispravna statistička interpretacija simuliranog sistema.

U kompjuterskom simulacionom modelovanju, glavni interes su zapažanja dobijena nakon što sistem koji se proučava dostigne stacionarni režim rada, jer u ovom slučaju varijansa uzorka naglo opada.

Vrijeme potrebno da sustav postigne stacionarni način rada određeno je vrijednostima njegovih parametara i početnim stanjem.

Budući da je glavni cilj dobiti opservacijske podatke sa najmanjom mogućom greškom, za postizanje ovog cilja možete:

1) produžiti trajanje simulacije procesa funkcionisanja sistema koji se proučava. U ovom slučaju ne samo da se povećava vjerovatnoća da sistem postigne stacionarni režim rada, već se povećava i broj korišćenih pseudoslučajnih brojeva, što takođe pozitivno utiče na kvalitet dobijenih rezultata.

2) na određeno vreme T izvršiti simulacijsko modeliranje N kompjuterski eksperimenti, koji se još nazivaju i modelima, sa različitim skupovima pseudoslučajnih brojeva, od kojih svaki daje jedno zapažanje. Sva pokretanja počinju sa istim početnim stanjem simuliranog sistema, ali koristeći različite skupove pseudoslučajnih brojeva. Prednost ove metode je nezavisnost dobijenih zapažanja, pokazatelja efikasnosti sistema. Ako je broj N model dovoljno velik, tada se granice simetričnog intervala povjerenja za parametar određuju na sljedeći način:

, , tj. , Gdje

Varijanca ispravljena, ,

N– broj izvođenja programa, – pouzdanost, .

2. Analitičko modeliranje QS-a

2.1 Grafikon stanja sistema i Kolmogorovljeve jednačine

Razmotrimo dvokanalni sistem čekanja (n = 2) sa ograničenim redom od šest (m = 4). QS prima najjednostavniji tok aplikacija sa prosječnim intenzitetom λ = 4,8 i eksponencijalnim zakonom raspodjele vremena između prijema aplikacija. Tok zahtjeva koji se serviraju u sistemu je najjednostavniji sa prosječnim intenzitetom μ = 2 i eksponencijalnim zakonom raspodjele vremena usluge.

Ovaj sistem ima 7 stanja, označimo ih:

S 0 – slobodan sistem, nema zahtjeva;

S 1 – 1 zahtjev za uslugu, red je prazan;

S 2 – 2 zahtjeva za servis, red je prazan;

S 3 – 2 zahtjeva za uslugu, 1 zahtjev u redu;

S 4 – 2 zahtjeva za uslugu, 2 zahtjeva u redu;

S 5 – 2 zahtjeva za uslugu, 3 zahtjeva u redu;

S 6 – 2 zahtjeva za uslugu, 4 zahtjeva u redu;

Verovatnoće da sistem dođe u stanja S 0 , S 1 , S 2 , …, S 6 su redom jednake P 0 , P 1 , P 2 , …, P 6 .

Grafikon stanja sistema čekanja je obrazac smrti i reprodukcije. Sva stanja sistema mogu se predstaviti kao lanac u kojem je svako stanje povezano sa prethodnim i narednim.

Rice. 3. Grafikon stanja dvokanalnog QS-a

Za konstruisani graf pišemo Kolmogorovljeve jednačine:

Da bismo riješili ovaj sistem, postavili smo početne uslove:

Kolmogorovljev sistem jednadžbi (sistem diferencijalnih jednačina) rješavat ćemo Ojlerovom numeričkom metodom uz korištenje softverskog paketa Maple 11 (vidi Dodatak 1).

Eulerova metoda

Gdje - u našem slučaju, to su desne strane Kolmogorovljeve jednačine, n=6.

Odaberimo vremenski korak. Pretpostavimo gde T– ovo je vrijeme tokom kojeg sistem dolazi u stacionarni način rada. Odavde dobijamo broj koraka . Dosljedno N Kada se jednom izračuna pomoću formule (1), dobijamo zavisnost verovatnoća stanja sistema od vremena, prikazanu na Sl. 4.

Vrijednosti QS vjerovatnoća na jednake su:

Rice. 4. Zavisnost vjerovatnoća stanja sistema od vremena

P0

P5

P 4

P 3

P2

P 1

2.2 Konačne vjerovatnoće sistema

Ako je vrijeme procesa u sistemu () dovoljno dugo, mogu se uspostaviti vremenski nezavisne vjerovatnoće stanja koje se nazivaju konačne vjerovatnoće, tj. sistem je postavljen na stacionarni način rada. Ako je broj stanja sistema konačan, a iz svakog od njih u konačnom broju koraka možete ići u bilo koje drugo stanje, tada postoje konačne vjerovatnoće, tj.

Jer u stacionarnom stanju, vremenski derivati ​​su jednaki 0, tada se jednačine za konačne vjerovatnoće dobijaju iz Kolmogorovljevih jednačina izjednačavanjem desnih strana sa 0. Napišimo jednačine za konačne vjerovatnoće za naš QS.

Rešimo ovaj sistem linearnih jednačina pomoću softverskog paketa Maple 11 (vidi Dodatak 1).

Dobijamo konačne vjerovatnoće sistema:

Poređenje verovatnoća dobijenih iz Kolmogorovljevog sistema jednačina za , sa konačnim verovatnoćama pokazuje da su greške su jednaki:

One. prilično malo. Ovo potvrđuje tačnost dobijenih rezultata.

2.3 Proračun indikatora efikasnosti sistema prema konačnim vjerovatnoćama

Nađimo indikatore efikasnosti sistema čekanja.

Prvo izračunavamo smanjeni intenzitet protoka aplikacija:

1) Vjerovatnoća odbijanja servisiranja zahtjeva, tj. vjerovatnoća da zahtjev ostavi sistem neuslužen.U našem slučaju, zahtjev je odbijen ako su sva 2 kanala zauzeta i red je maksimalno popunjen (tj. 4 osobe u redu), to odgovara stanju sistema S 6 . Jer vjerovatnoća da sistem dođe u stanje S 6 je tada jednaka P 6

4) Prosječna dužina reda, tj. prosječan broj aplikacija u redu je jednak zbiru proizvoda broja aplikacija u redu i vjerovatnoće odgovarajućeg stanja.

5) Prosječno vrijeme koje aplikacija ostaje u redu je određeno Littleovom formulom:

3. Simulacijsko modeliranje QS

3.1 Algoritam metode QS simulacije (pristup korak po korak)

Razmotrimo dvokanalni sistem čekanja (n = 2) sa maksimalnom dužinom reda od šest (m = 4). QS prima najjednostavniji tok aplikacija sa prosječnim intenzitetom λ = 4,8 i eksponencijalnim zakonom raspodjele vremena između prijema aplikacija. Tok zahtjeva koji se serviraju u sistemu je najjednostavniji sa prosječnim intenzitetom μ = 2 i eksponencijalnim zakonom raspodjele vremena usluge.

Za simulaciju QS koristićemo jednu od metoda statističkog modeliranja - simulacijsko modeliranje. Koristićemo pristup korak po korak. Suština ovog pristupa je da se stanja sistema razmatraju u narednim trenucima vremena, korak između kojih je dovoljno mali tako da se tokom njegovog vremena ne dogodi više od jednog događaja.

Odaberimo vremenski korak (). Trebalo bi biti mnogo manje od prosječnog vremena prijema aplikacije () i prosječnog vremena njenog servisiranja (), tj.

Gdje (3.1.1)

Na osnovu uslova (3.1.1) određujemo vremenski korak .

Vrijeme prijema aplikacije od strane QS-a i vrijeme njenog servisiranja su slučajne varijable. Stoga se pri simulaciji QS sistema oni izračunavaju korištenjem slučajnih brojeva.

Hajde da razmotrimo podnošenje prijave CMO-u. Vjerovatnoća da će QS primiti zahtjev tokom intervala jednaka je: . Hajde da generišemo slučajni broj, i if , tada ćemo pretpostaviti da je aplikaciju u ovom koraku sistem primio ako , onda nisam stigao.

Program to radi isRequested () . Uzmimo da je vremenski interval konstantan i jednak 0,0001, tada će omjer biti jednak 10000. Ako je aplikacija primljena, onda ona uzima vrijednost “true”, u suprotnom vrijednost je “false”.

bool isRequested()

double r = R. NextDouble();

ako (r< (timeStep * lambda))

Razmotrimo sada servisiranje aplikacije u QS-u. Vrijeme za servisiranje zahtjeva u sistemu je određeno izrazom , gdje je slučajni broj. U programu se vrijeme servisiranja određuje pomoću funkcije GetServiceTime () .

duplo GetServiceTime()

double r = R. NextDouble();

return (-1/mu*Math. Log (1-r, Math. E));

Algoritam metode simulacije može se formulisati na sljedeći način. SMO radni sati ( T) je podijeljen na vremenske korake dt, svaki od njih izvodi niz radnji. Prvo se određuju stanja sistema (zauzetost kanala, dužina reda), a zatim pomoću funkcije isRequested () , utvrđuje se da li je prijava primljena u ovom koraku ili ne.

Ako je primljeno, a postoje slobodni kanali, onda koristite funkciju GetServiceTime () Generiramo vrijeme obrade aplikacije i stavljamo je na servis. Ako su svi kanali zauzeti i dužina reda je manja od 4, onda postavljamo zahtjev u red čekanja, ali ako je dužina reda 4, tada će zahtjev biti odbijen.

U slučaju kada u ovom koraku aplikacija nije primljena, a servisni kanal je slobodan, provjeravamo da li postoji red čekanja. Ako postoji, onda postavljamo zahtjev iz reda za uslugu u besplatni kanal. Nakon završenih operacija, vrijeme usluge za zauzete kanale se smanjuje za vrijednost koraka dt .

Nakon što je vrijeme prošlo T, odnosno, nakon modeliranja rada QS-a, izračunavaju se indikatori performansi sistema i rezultati se prikazuju na ekranu.

3.2 Dijagram toka programa

Blok dijagram programa koji implementira opisani algoritam prikazan je na Sl. 5.

Rice. 5. Blok dijagram programa

Opišimo neke blokove detaljnije.

Blok 1. Postavljanje početnih vrijednosti parametara.

Random R; // Generator slučajnih brojeva

public uint maxQueueLength; // Maksimalna dužina reda čekanja

public uint channelCount; // Broj kanala u sistemu

javna dvostruka lambda; // Intenzitet toka primljenih zahtjeva

javni dupli mu; // Intenzitet toka servisiranja zahtjeva

javni dvostruki timeStep; // Vremenski korak

javno dvostruko vrijemeOfFinishProcessingReq; // Vrijeme završetka servisiranja zahtjeva na svim kanalima

public double timeInQueue; // Vrijeme provedeno od strane QS-a u stanjima sa redom

javno dvostruko vrijeme obrade; // Vrijeme rada sistema

javno duplo totalProcessingTime; // Ukupno vrijeme za servisiranje zahtjeva

public uint requestEntryCount; // Broj primljenih prijava

public uint declinedRequestCount; // Broj odbijenih prijava

public uint acceptedRequestCount; // Broj usluženih zahtjeva

uint queueLength; // Dužina reda //

Tip koji opisuje QS stanja

enum SysCondition(S0, S1, S2, S3, S4, S5, S6);

SysCondition currentSystemCondition; // Trenutno stanje sistema

Podešavanje stanja sistema. Razlikujemo 7 različitih stanja za ovaj 2-kanalni sistem: S 0, S 1. S 6. QS je u S0 stanju kada je sistem slobodan; S 1 – najmanje jedan kanal je slobodan; u stanju S 2, kada su svi kanali zauzeti i postoji mjesto u redu čekanja; u stanju S 6 – svi kanali su zauzeti i red je dostigao maksimalnu dužinu (queueLength = 4).

Određujemo trenutno stanje sistema pomoću funkcije GetCondition()

SysCondition GetCondition()

SysCondition p_currentCondit = SysCondition.S0;

int busyChannelCount = 0;

za (int i = 0; i< channelCount; i++)

if (timeOfFinishProcessingReq[i] > 0)

busyChannelCount++;

p_currentCondit += k * (i + 1);

if (busyChannelCount > 1)

(p_currentCondit++;)

return p_currentCondit + (int) QueueLength;

Promjena vremena provedenog od strane QS-a u stanjima sa dužinama čekanja 1, 2,3,4. Ovo se implementira sljedećim programskim kodom:

if (queueLength > 0)

timeInQueue += timeStep;

if (dužina čekanja > 1)

(timeInQueue += timeStep;)

Postoji takva operacija kao što je postavljanje zahtjeva za uslugu u besplatni kanal. Svi kanali se skeniraju počevši od prvog kada se ispuni uslov timeOfFinishProcessingReq [ i ] <= 0 (kanal je besplatan), na njega se podnosi prijava, tj. Generira se vrijeme završetka za servisiranje zahtjeva.

za (int i = 0; i< channelCount; i++)

if (timeOfFinishProcessingReq [i]<= 0)

timeOfFinishProcessingReq [i] = GetServiceTime();

totalProcessingTime+= timeOfFinishProcessingReq [i];

Servis zahtjeva u kanalima modeliran je kodom:

za (int i = 0; i< channelCount; i++)

if (timeOfFinishProcessingReq [i] > 0)

timeOfFinishProcessingReq [i] -= timeStep;

Algoritam metode simulacije implementiran je u programskom jeziku C#.

3.3 Proračun indikatori učinka QS-a na osnovu rezultate njegovog simulacijskog modeliranja

Najvažniji pokazatelji su:

1) Vjerovatnoća odbijanja servisiranja aplikacije, tj. vjerovatnoća da zahtjev ostavi sistem neuslužen.U našem slučaju, zahtjev je odbijen ako su sva 2 kanala zauzeta i red je maksimalno popunjen (tj. 4 osobe u redu). Da bismo pronašli vjerovatnoću kvara, dijelimo vrijeme kada je QS u stanju s redom 4 sa ukupnim vremenom rada sistema.

2) Relativna propusnost je prosječan udio dolaznih zahtjeva koje opslužuje sistem.

3) Apsolutna propusnost je prosječan broj usluženih zahtjeva u jedinici vremena.

4) Dužina reda, tj. prosječan broj aplikacija u redu čekanja. Dužina reda je jednaka zbiru proizvoda broja ljudi u redu i vjerovatnoće odgovarajućeg stanja. Pronaći ćemo vjerovatnoće stanja kao omjer vremena kada je QS u ovom stanju i ukupnog vremena rada sistema.

5) Prosječno vrijeme koje aplikacija ostaje u redu je određeno Littleovom formulom

6) Prosječan broj zauzetih kanala utvrđuje se na sljedeći način:

7) Procenat aplikacija kojima je odbijena usluga nalazi se pomoću formule

8) Procenat usluženih aplikacija određuje se formulom

3.4 Statistička obrada rezultata i njihovo poređenje sa rezultatima analitičkog modeliranja

Jer indikatori efikasnosti se dobijaju kao rezultat simulacije QS-a u konačnom vremenu i sadrže slučajnu komponentu. Stoga, da bi se dobili pouzdaniji rezultati, potrebno ih je statistički obraditi. U tu svrhu ćemo procijeniti interval pouzdanosti za njih na osnovu rezultata 20 pokretanja programa.

Vrijednost pada unutar intervala povjerenja ako je nejednakost zadovoljena

, Gdje

matematičko očekivanje (prosječna vrijednost), pronađeno po formuli

Varijanca ispravljena,

,

N =20 – broj trčanja,

– pouzdanost. Kada i N =20 .

Rezultat programa je prikazan na sl. 6.

Rice. 6. Vrsta programa

Radi lakšeg poređenja rezultata dobijenih različitim metodama modeliranja, prikazujemo ih u obliku tabele.

Tabela 2.

Indikatori efikasnost QS-a	rezultate analitički modeliranje	rezultate simulacijsko modeliranje (zadnji korak)	Rezultati simulacije
			Zaključak povjerenje interval	Gornja granica povjerenje interval
Vjerovatnoća neuspjeha		0,174698253017626	0,158495148639101	0,246483801571923
Relativna širina pojasa		0,825301746982374	0,753516198428077	0,841504851360899
Apsolutna propusnost		3,96144838551539	3,61687775245477	4,03922328653232
Prosječna dužina čekanja		1,68655313447018	1,62655862750852	2,10148609204869
Prosječno vrijeme koje aplikacija provede u redu čekanja	0,4242558575	0,351365236347954	0,338866380730942	0,437809602510145
Prosječan broj zauzetih kanala		1,9807241927577	1,80843887622738	2,01961164326616

Sa stola 2 pokazuje da rezultati dobijeni analitičkim modeliranjem QS-a spadaju u interval pouzdanosti dobijen iz rezultata simulacionog modeliranja. Odnosno, rezultati dobijeni različitim metodama su konzistentni.

Zaključak

Ovaj rad razmatra glavne metode za modeliranje QS i izračunavanje njihovih indikatora učinka.

Dvokanalni QS sistem sa maksimalnom dužinom reda od 4 modeliran je pomoću Kolmogorovljevih jednačina i pronađene su konačne vjerovatnoće stanja sistema. Izračunati su pokazatelji njegove efikasnosti.

Provedeno je simulacijsko modeliranje rada takvog QS-a. Kreiran je program u programskom jeziku C# koji simulira njegov rad. Proveden je niz proračuna na osnovu kojih su pronađene vrijednosti indikatora efikasnosti sistema i izvršena njihova statistička obrada.

Rezultati dobiveni simulacijskim modeliranjem su u skladu s rezultatima analitičkog modeliranja.

Književnost

1. Ventzel E.S. Operativno istraživanje. – M.: Drfa, 2004. – 208 str.

2. Volkov I.K., Zagoruiko E.A. Operativno istraživanje. – M.: Izdavačka kuća MSTU po imenu. N.E. Bauman, 2002. – 435 str.

3. Volkov I.K., Zuev S.M., Cvetkova G.M. Slučajni procesi. – M.: Izdavačka kuća MSTU po imenu. N.E. Bauman, 2000. – 447 str.

4. Gmurman V.E. Vodič za rješavanje problema iz teorije vjerovatnoće i matematičke statistike. – M.: Viša škola, 1979. – 400 str.

5. Ivnitsky V.L. Teorija mreža čekanja. – M.: Fizmatlit, 2004. – 772 str.

6. Istraživanje operacija u ekonomiji / ur. N.Sh. Kremer. – M.: Jedinstvo, 2004. – 407 str.

7. Taha H.A. Uvod u istraživanje operacija. – M.: Izdavačka kuća “Williams”, 2005. – 902 str.

8. Kharin Yu.S., Malyugin V.I., Kirlitsa V.P. i dr.. Osnove simulacije i statističkog modeliranja. – Minsk: Design PRO, 1997. – 288 str.

Markovljev slučajni proces sa diskretnim stanjima i kontinuiranim vremenom, o kojem je bilo reči u prethodnom predavanju, odvija se u sistemima čekanja (QS).

Sistemi čekanja – to su sistemi koji primaju zahtjeve za servis u nasumično vrijeme, a primljeni zahtjevi se servisiraju korištenjem servisnih kanala dostupnih sistemu.

Primjeri sistema čekanja uključuju:

• jedinice za poravnanje gotovine u bankama i preduzećima;
• osobna računala koja služe dolaznim aplikacijama ili zahtjevima za rješavanje određenih problema;
• Auto servisi; benzinska pumpa;
• revizorske firme;
• odjeljenja poreske inspekcije odgovorne za prihvatanje i provjeru tekućih izvještaja preduzeća;
• telefonske centrale itd.

	Čvorovi	Zahtjevi
Bolnica	Bolničari	Pacijenti
Proizvodnja
Aerodrom	Izlazi na pistu Tačke registracije	Putnici

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

Rice. 1

1. Generator aplikacija – objektno generiranje zahtjeva: ulica, radionica sa ugrađenim jedinicama. Ulaz je tok aplikacija(protok kupaca do prodavnice, protok pokvarenih jedinica (mašina, mašina) za popravke, protok posetilaca u garderobu, protok automobila do benzinske pumpe, itd.).
2. Dispečer – osoba ili uređaj koji zna šta da radi sa aplikacijom. Čvor koji reguliše i usmjerava zahtjeve ka servisnim kanalima. dispečer:

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

1. Red – akumulator aplikacija. Možda nema reda.
2. Servisni centar sastoji se od konačnog broja servisnih 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).

Pored ovih osnovnih elemenata u QS-u, neki izvori ističu i sljedeće komponente:

terminator – uništavač transakcija;

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

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

menadžer – menadžer resursa;

Klasifikacija SMO

Prva podjela (na osnovu prisutnosti redova):

• QS sa kvarovima;
• SMO sa redom.

IN QS sa kvarovima aplikacija primljena u trenutku kada su svi kanali zauzeti se odbija, napušta QS i ne servisira se u budućnosti.

IN Red s redom aplikacija koja stigne u vrijeme kada su svi kanali zauzeti ne napušta, već staje u red i čeka priliku da bude uslužena.

QS sa redovima dijele se na različite tipove ovisno o tome kako je red organiziran - ograničeno ili neograničeno. Ograničenja se mogu odnositi i na dužinu reda i na vrijeme čekanja, „disciplina usluga“.

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

• CMO sa nestrpljivim zahtjevima (dužina reda i vrijeme usluge su ograničeni);
• QS sa prioritetnom uslugom, tj. neki zahtjevi se servisiraju van reda itd.

Vrste ograničenja reda mogu se kombinirati.

Druga klasifikacija dijeli CMO prema izvoru aplikacija. Aplikacije (zahtjeve) može generirati sam sistem ili neko vanjsko okruženje koje postoji nezavisno od sistema.

Naravno, tok zahtjeva koje generiše sam sistem zavisiće od sistema i njegovog stanja.

Osim toga, SMO se dijele na otvoren CMO and zatvoreno SMO.

U otvorenom QS-u, karakteristike toka aplikacija ne zavise od stanja samog QS-a (koliko kanala je zauzeto). U zatvorenom QS - zavise. Na primjer, ako jedan radnik servisira grupu mašina koje s vremena na vrijeme zahtijevaju prilagođavanje, onda intenzitet toka „zahtjeva“ od mašina ovisi o tome koliko ih je već u funkciji i čeka na prilagođavanje.

Primjer zatvorenog sistema: blagajnik koji izdaje plate u preduzeću.

Na osnovu broja kanala, QS se dijele na:

• jednokanalni;
• višekanalni.

Karakteristike sistema čekanja

Glavne karakteristike bilo koje vrste sistema čekanja su:

• ulazni tok dolaznih zahtjeva ili zahtjeva za uslugom;
• disciplina u redu čekanja;
• servisni mehanizam.

Ulazni zahtjevi Stream

Da biste opisali ulazni tok, morate navesti zakon vjerovatnoće koji određuje redoslijed trenutaka kada se primaju zahtjevi za uslugu, i naznačiti broj takvih zahtjeva u svakoj narednoj priznanici. U ovom slučaju, po pravilu, oni rade s konceptom „vjerovatnoće raspodjele trenutaka prijema zahtjeva“. Ovdje mogu uraditi sljedeće: individualne i grupne zahteve (broj takvih zahtjeva u svakom redovnom prijemu). U potonjem slučaju obično govorimo o sistemu čekanja sa paralelnim grupnim servisiranjem.

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

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

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

Karakteristike ulaznog toka:

1. Vjerovatni zakon koji određuje redoslijed trenutaka kada se primaju zahtjevi za uslugu.
2. Broj zahtjeva u svakom sljedećem dolasku za grupne tokove.

Disciplina u redu

Red – skup zahtjeva koji čekaju uslugu.

Red ima ime.

Disciplina u redu definiše princip prema kojem se zahtjevi koji pristižu na ulaz uslužnog sistema povezuju iz reda čekanja u servisnu proceduru. Najčešće korištene discipline redova su definirane sljedećim pravilima:

• prvi dođe, prvi uslužen;

prvi ušao prvi izašao (FIFO)

najčešći tip reda čekanja.

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

Lista ima početak i kraj. Lista se sastoji od unosa. Zapis je ćelija liste. Aplikacija stiže na kraj liste, a za servis se bira sa početka liste. Zapis se sastoji od karakteristika aplikacije i veze (indikator ko stoji iza nje). Osim toga, ako red ima ograničenje vremena čekanja, tada mora biti naznačeno i maksimalno vrijeme čekanja.

Kao programeri, trebali biste biti u mogućnosti da pravite dvosmjerne, jednosmjerne liste.

Lista radnji:

• umetnite u rep;
• uzeti od početka;
• ukloniti sa liste nakon isteka vremenskog ograničenja.
• Poslednji koji stiže - prvi koji će biti uslužen LIFO (štipaljka za patrone, slijepa ulica na željezničkoj stanici, ušao u prepun vagon).

Struktura poznata kao STACK. Može se opisati nizom ili strukturom liste;

• slučajni odabir aplikacija;
• izbor aplikacija na osnovu kriterijuma prioriteta.

Svaku aplikaciju karakteriše, između ostalog, njen nivo prioriteta i po prijemu se ne postavlja na rep reda, već na kraj svoje grupe prioriteta. Dispečer sortira po prioritetu.

Karakteristike reda čekanja

• ograničenjevrijeme čekanja trenutak usluge (postoji red sa ograničenim vremenom čekanja na uslugu, što je povezano sa konceptom „dozvoljene dužine reda”);
• dužina reda čekanja.

Service Mechanism

Service Mechanism određena karakteristikama samog uslužnog postupka i strukturom uslužnog sistema. Karakteristike postupka održavanja uključuju:

• broj servisnih kanala ( N);
• trajanje servisnog postupka (vjerovatna raspodjela vremena za potrebe servisiranja);
• broj zahtjeva ispunjenih kao rezultat svake takve procedure (za grupne prijave);
• vjerovatnoća kvara servisnog kanala;
• strukturu uslužnog sistema.

Za analitički opis karakteristika servisne procedure koristi se koncept „vjerovatne raspodjele vremena za potrebe servisiranja“.

S i– servisno vrijeme i-th uslov;

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 sistema. U nekim slučajevima je takođe potrebno uzeti u obzir vjerovatnoća kvara servisnog kanala nakon određenog ograničenog vremenskog perioda. Ova karakteristika se može modelirati kao tok kvarova koji ulaze u QS i imaju prioritet nad svim ostalim zahtjevima.

Stopa iskorištenosti QS-a

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

ρ=λ/( Nμ) – zove se koeficijent iskorištenosti QS , pokazuje koliko se sistemskih resursa koristi.

Struktura uslužnog sistema

Struktura uslužnog sistema određena je brojem i relativnim položajem servisnih kanala (mehanizama, uređaja itd.). Prije svega, treba naglasiti da uslužni sistem može imati više od jednog uslužnog kanala, ali više; Ovaj tip sistema je sposoban da zadovolji više zahteva istovremeno. U ovom slučaju, svi kanali usluga nude iste usluge, pa se stoga može tvrditi paralelna usluga .

Primjer. Kase u prodavnici.

Servisni sistem se može sastojati od nekoliko različitih tipova servisnih kanala kroz koje svaki servisirani zahtjev mora proći, tj. u uslužnom sistemu procedure servisiranja zahtjeva se sprovode dosljedno . Mehanizam servisiranja određuje karakteristike odlaznog (serviranog) toka zahtjeva.

Primjer. Lekarska komisija.

Kombinovana usluga – servisiranje depozita u štedionici: prvo kontrolor, pa blagajnik. U pravilu, 2 kontrolora po blagajni.

dakle, funkcionalnost bilo kog sistema čekanja je određena sljedećim glavnim faktorima :

• vjerovatnoća distribucije momenata prijema zahtjeva za uslugu (pojedinačni ili grupni);
• snaga izvora zahtjeva;
• vjerovatnoća distribucije vremena trajanja usluge;
• konfiguracija uslužnog sistema (paralelna, sekvencijalna ili paralelno-sekvencijalna usluga);
• broj i produktivnost kanala usluga;
• disciplina u redu.

Glavni kriterijumi za efektivnost funkcionisanja QS-a

As glavni kriterijumi za efikasnost sistema čekanja Ovisno o prirodi problema koji se rješava, može se pojaviti sljedeće:

• vjerovatnoća trenutnog servisiranja dolazne aplikacije (P obsl = K obs / K post);
• vjerovatnoća odbijanja servisiranja dolazne aplikacije (P open = K open / K post);

Očigledno, P obsl + P open =1.

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

Kašnjenje – jedan od kriterijuma za servisiranje QS-a je vreme koje aplikacija provede čekajući na servis.

D i– kašnjenje u redu zahtjeva i;

W i =D i +S i– vrijeme potrebno u sistemu i.

(sa vjerovatnoćom 1) – utvrđeno prosječno kašnjenje zahtjeva u redu čekanja;

(sa vjerovatnoćom 1) – utvrđeno prosječno vrijeme u kojem je zahtjev u QS-u (čekanje).

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

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

Zatim indikatori (ako postoje)

(sa vjerovatnoćom 1) – prosječan broj zahtjeva u redu u stabilnom stanju tokom vremena;

(sa vjerovatnoćom 1) – prosječan broj zahtjeva u sistemu u stabilnom stanju tokom vremena.

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

Ako se sjetimo da je ρ= λ/( Nμ), onda je jasno da ako je intenzitet prijema prijava veći od Nμ, onda je ρ>1 i prirodno je da sistem neće moći da se nosi sa takvim tokom aplikacija, te stoga ne možemo govoriti o veličinama d, w, Q I L.

Najopštiji i najpotrebniji rezultati za sisteme čekanja uključuju jednačine očuvanja

Treba napomenuti da se gore navedeni kriteriji za procjenu performansi sistema mogu analitički izračunati za sisteme čekanja M/M/N(N>1), odnosno sistemi sa Markovljevim tokovima zahtjeva i usluga. Za M/G/ l za bilo koju distribuciju G i za neke druge sisteme. Općenito, vremenska distribucija između dolazaka, raspodjela vremena usluge ili oboje moraju biti eksponencijalni (ili neka vrsta eksponencijalne Erlangove raspodjele k-tog reda) da bi analitičko rješenje bilo moguće.

Osim toga, možemo govoriti i o karakteristikama kao što su:

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

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

.

U Rusiji je ova formula poznata kao Pollacek formula – Khinčin, u inostranstvu se ova formula povezuje sa imenom Ross.

Dakle, ako E(S) je veće, onda preopterećenje (u ovom slučaju mjereno kao d) će biti veći; što je za očekivati. Formula također otkriva manje očiglednu č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, to se može objasniti na sljedeći način: varijansa slučajne varijable servisnog vremena može poprimiti veliku vrijednost (pošto mora biti pozitivna), tj. jedini servisni uređaj će biti zauzet dugo vremena, što će dovesti do povećanje reda.

Predmet teorije čekanja je uspostavljanje odnosa između faktora koji određuju funkcionalnost sistema čekanja i efikasnosti njegovog rada. U većini slučajeva, svi parametri koji opisuju sisteme čekanja su slučajne varijable ili funkcije, stoga ovi sistemi pripadaju stohastičkim sistemima.

Nasumična priroda toka aplikacija (zahtjeva), kao i, u općenitom slučaju, trajanje usluge dovode do toga da se u sistemu čekanja javlja slučajni proces. Po prirodi slučajnog procesa , koji se javljaju u sistemu čekanja (QS), razlikuju se Markovi i nemarkovski sistemi . U Markovljevim sistemima, ulazni tok zahtjeva i odlazni tok servisiranih zahtjeva (aplikacija) su Poissonovi. Poissonovi tokovi olakšavaju opisivanje i konstruisanje matematičkog modela sistema čekanja. Ovi modeli imaju prilično jednostavna rješenja, tako da većina poznatih aplikacija teorije čekanja koristi Markovljevu shemu. U slučaju nemarkovskih procesa, problemi proučavanja sistema čekanja postaju značajno komplikovaniji i zahtevaju korišćenje statističkog modeliranja i numeričkih metoda korišćenjem računara.

1.1. Struktura i parametri efikasnosti i kvaliteta funkcionisanja QS-a

Mnogi ekonomski problemi su vezani za sisteme čekanja, tj. takvi sistemi u kojima se, s jedne strane, javljaju masovni zahtjevi (zahtjevi) za obavljanje bilo koje usluge, a s druge strane, ti zahtjevi se zadovoljavaju. QS uključuje sljedeće elemente: izvor zahtjeva, ulazni tok zahtjeva, red čekanja, uslužni uređaji (uslužni kanali), odlazni tok zahtjeva. Teorija čekanja proučava takve sisteme.

Objekti koji služe zahtjevima nazivaju se serviseri ili servisni kanali. Na primjer, to uključuje uređaje za dopunu goriva na benzinskim pumpama, telefonske komunikacijske kanale, sletne piste, servisere, blagajnike karata, mjesta za utovar i istovar u bazama i skladištima.

Koristeći metode teorije redova čekanja, mogu se riješiti mnogi problemi u proučavanju procesa koji se dešavaju u privredi. Dakle, u organizovanju trgovine ove metode omogućavaju određivanje optimalnog broja maloprodajnih objekata datog profila, broja prodavaca, učestalosti isporuke robe i drugih parametara. Drugi tipičan primjer sistema čekanja mogu biti benzinske pumpe, a zadaci teorije čekanja u ovom slučaju svode se na uspostavljanje optimalnog omjera između broja zahtjeva za uslugom koji pristižu na benzinsku pumpu i broja servisnih uređaja, na kojima se ukupni troškovi usluge i gubici od zastoja bi bili minimalni. Teorija čekanja se može primijeniti i pri proračunu površine skladišnih prostora, dok se skladišni prostor smatra uslužnim uređajem, a dolazak vozila na istovar smatra se uslovom. Modeli teorije čekanja koriste se i u rješavanju niza problema organizacije i racionalizacije rada, te drugih društveno-ekonomskih problema.

Svaki QS u svojoj strukturi uključuje određeni broj servisnih uređaja, koji se nazivaju servisni kanali (mogu uključivati ​​osobe koje obavljaju određene operacije - blagajnike, operatere, menadžere, itd.) koji opslužuju određeni tok aplikacija (zahtjeva), koji nasumično dolaze na njegov ulaz puta. Servis aplikacija se javlja u nepoznatom, obično nasumičnom vremenu i zavisi od mnogo različitih faktora. Nakon servisiranja zahtjeva, kanal se oslobađa i spreman je za primanje sljedećeg zahtjeva. Nasumična priroda toka aplikacija i vrijeme njihovog servisiranja dovodi do neravnomjernog učitavanja QS-a - preopterećenja sa formiranjem redova aplikacija ili podopterećenja - sa mirovanjem njegovih kanala. Slučajnost prirode toka zahteva i trajanja njihove usluge dovodi do slučajnog procesa u QS-u, za čije proučavanje je potrebna konstrukcija i analiza njegovog matematičkog modela. Proučavanje funkcionisanja QS-a je pojednostavljeno ako je slučajni proces markovski (proces bez naknadnih efekata, ili bez memorije), kada se rad QS-a lako opisuje korišćenjem konačnih sistema običnih linearnih diferencijalnih jednadžbi prvog reda, i u graničnom režimu (sa dovoljno dugim radom QS) pomoću linearnih algebarskih jednačina konačnih sistema. Kao rezultat toga, pokazatelji efektivnosti funkcionisanja QS-a se izražavaju kroz parametre QS-a, protok aplikacija i disciplinu.

Iz teorije je poznato da je da bi slučajni proces bio markovski potrebno i dovoljno da svi tokovi događaja (tokovi aplikacija, tokovi servisnih aplikacija itd.) pod uticajem kojih prelaze sistem iz stanja u stanje stanja nastaju, su Poissonovi, tj. ima svojstva posledice (za bilo koja dva nepreklapajuća vremenska intervala, broj događaja koji se dešavaju tokom jednog od njih ne zavisi od broja događaja koji se dešavaju posle drugog) i običnosti (verovatnoća pojave više od jednog događaja tokom elementarni, ili mali, vremenski period je zanemarljiv u poređenju sa vjerovatnoćom da se jedan događaj dogodi tokom ovog vremenskog perioda). Za najjednostavniji Poissonov tok, slučajna varijabla T (vremenski interval između dva susjedna događaja) raspoređuje se prema eksponencijalnom zakonu, koji predstavlja njegovu gustinu distribucije ili diferencijalnu funkciju raspodjele.

Ako je priroda tokova u QS-u drugačija od Poissonove, onda se njegove karakteristike efikasnosti mogu odrediti približno koristeći Markovu teoriju čekanja, i što je tačnije, to je QS složeniji i ima više servisnih kanala. U većini slučajeva valjane preporuke za praktično upravljanje QS-om ne zahtijevaju poznavanje njegovih tačnih karakteristika, već je dovoljno imati njihove približne vrijednosti.

Svaki QS, u zavisnosti od svojih parametara, ima određenu radnu efikasnost.

Efikasnost funkcionisanja QS-a karakterišu tri glavne grupe indikatora:

1. Efikasnost korišćenja QS – apsolutna ili relativna propusnost, prosečno trajanje perioda zauzetosti QS, stepen iskorišćenja QS, odnos nekorišćenja QS;

2. Kvalitet servisiranja aplikacija - prosječno vrijeme (prosječan broj prijava, zakon o raspodjeli) čekanja aplikacije u redu ili zadržavanja aplikacije u QS-u; vjerovatnoća da će primljeni zahtjev odmah biti prihvaćen za izvršenje;

3. Efikasnost funkcionisanja para CMO-potrošača, a potrošač se shvaća kao skup aplikacija ili neki njihov izvor (npr. prosječni prihod koji donosi CMO po jedinici radnog vremena itd.) .

1.2 Klasifikacija QS-a i njihovih glavnih elemenata

QS se razvrstavaju u različite grupe u zavisnosti od sastava i vremena provedenog u redu prije početka servisa, te od discipline servisiranja zahtjeva.

Prema sastavu QS-a razlikuju se jednokanalne (sa jednim uslužnim uređajem) i višekanalne (sa velikim brojem uređaja za serviranje). Višekanalni sistemi se mogu sastojati od servisnih uređaja istih i različitih performansi.

Na osnovu vremena koje je potrebno u redu prije početka servisiranja, sistemi su podijeljeni u tri grupe:

1) sa neograničenim vremenom čekanja (sa čekanjem),

2) sa odbijanjem;

3) mješoviti tip.

U QS-u s neograničenim vremenom čekanja, sljedeći zahtjev, koji otkriva da su svi uređaji zauzeti, ulazi u red čekanja i čeka servis dok se jedan od uređaja ne oslobodi.

U sistemima sa kvarovima, pristigli zahtjev, koji otkriva da su svi uređaji zauzeti, napušta sistem. Klasičan primjer sistema sa kvarovima je rad automatske telefonske centrale.

U sistemima mješovitog tipa, dolazni zahtjev nalazi da su svi uređaji zauzeti, čekaju u redu i čekaju na servis ograničeno vrijeme.Bez čekanja servisa u zadano vrijeme, zahtjev napušta sistem.

Razmotrimo ukratko karakteristike funkcionisanja nekih od ovih sistema.

1. QS sa čekanjem karakteriše činjenica da u sistemu od n (n>=1) svaki zahtjev koji stigne u QS u trenutku kada su svi kanali zauzeti ulazi u red čekanja i čeka uslugu, a svaki dolazni zahtjev je servisiran. Takav sistem može biti u jednom od beskonačnog broja stanja: s n +k (r=1.2...) – svi kanali su zauzeti i ima r aplikacija u redu čekanja.

2. QS sa čekanjem i ograničenjem dužine reda se razlikuje od gore navedenog po tome što ovaj sistem može biti u jednom od n+m+1 stanja. U stanjima s 0 , s 1 ,…, s n nema reda, jer ili nema aplikacija u sistemu ili ih uopšte nema i kanali su slobodni (s 0), ili ih ima nekoliko I (I = 1,n ) aplikacije u sistemu, koje opslužuje odgovarajući (n+1, n+2,…n+r,…,n+m) broj aplikacija i (1,2,…r,…,m) aplikacije koje stoje u redu. Aplikacija koja stigne na QS ulaz u trenutku kada već ima m aplikacija u redu čekanja se odbija i ostavlja sistem neuslužen.

Dakle, višekanalni QS u suštini funkcioniše kao jednokanalni, kada svih n kanala rade kao jedan sa disciplinom uzajamne pomoći koja se zove svi kao jedan, ali sa većim intenzitetom usluge. Grafikon stanja ovakvog sličnog sistema sadrži samo dva stanja: s 0 (s 1) - svih n kanala su slobodni (zauzeti).

Analiza različitih tipova QS-a uz međusobnu pomoć tipa sve-u-jednom pokazuje da takva uzajamna pomoć smanjuje prosječno vrijeme boravka aplikacije u sistemu, ali pogoršava niz drugih karakteristika kao što su vjerovatnoća kvara, propusnost, prosječan broj aplikacija u redu i vrijeme čekanja na njihovo izvršenje. Stoga se za poboljšanje ovih pokazatelja koristi promjena u disciplini servisiranja zahtjeva uz jednoobraznu međusobnu pomoć između kanala na sljedeći način:

· Ako zahtjev stigne u QS u vrijeme kada su svi kanali slobodni, tada svih n kanala počinje da ga servisira;

· Ako u ovom trenutku stigne sljedeći zahtjev, onda se neki od kanala prebacuju na njegovo servisiranje

· Ako pri servisiranju ova dva zahtjeva stigne treći zahtjev, onda se neki od kanala prebacuju na servisiranje ovog trećeg zahtjeva, sve dok svaki zahtjev koji se nalazi u QS-u ne opsluži samo jedan kanal. U ovom slučaju, prijava primljena u trenutku kada su svi kanali zauzeti, u QS-u sa odbijanjima i jedinstvenom uzajamnom pomoći između kanala, može biti odbijena i biće prinuđena da napusti sistem neopslužen.

Metode i modeli koji se koriste u teoriji čekanja mogu se podijeliti na analitičke i simulacijske.

Analitičke metode teorije čekanja omogućavaju dobijanje karakteristika sistema kao nekih funkcija njegovih parametara rada. Zahvaljujući tome, postaje moguće izvršiti kvalitativnu analizu uticaja pojedinih faktora na efikasnost QS-a. Metode simulacije se baziraju na kompjuterskom modeliranju procesa čekanja i koriste se ako je nemoguće koristiti analitičke modele.

Trenutno su teoretski najrazvijenije i najpogodnije za praktičnu primjenu metode za rješavanje problema čekanja u kojima je dolazni tok zahtjeva najjednostavniji (Poisson).

Za najjednostavniji tok, učestalost zahtjeva koji ulaze u sistem poštuje Poissonov zakon, tj. vjerovatnoća dolaska u vrijeme t od tačno k zahtjeva je data formulom:

Važna karakteristika QS-a je vrijeme potrebno za servisiranje zahtjeva u sistemu. Vrijeme usluge jednog zahtjeva je, po pravilu, slučajna varijabla i stoga se može opisati zakonom distribucije. Eksponencijalni zakon raspodjele vremena usluge se najviše koristi u teoriji, a posebno u praktičnim primjenama. Funkcija distribucije za ovaj zakon ima oblik:

One. vjerovatnoća da vrijeme servisiranja ne pređe određenu vrijednost t određena je ovom formulom, gdje je µ parametar eksponencijalne usluge zahtjeva u sistemu, tj. recipročna vrijednost servisnog vremena t rev:

Razmotrimo analitičke modele najčešćeg QS-a sa očekivanjem, tj. takav QS u kojem se zahtjevi primljeni u vrijeme kada su svi kanali za opsluživanje zauzeti stavljaju u red i servisiraju kako kanali postaju slobodni.

Opća formulacija problema je sljedeća. Sistem ima n kanala za opsluživanje, od kojih svaki može poslužiti samo jedan zahtjev u isto vrijeme.

Sistem prima jednostavan (Paussonov) tok zahtjeva s parametrom . Ako u trenutku kada stigne sljedeći zahtjev, u sistemu već postoji najmanje n zahtjeva za servisiranje (tj. svi kanali su zauzeti), onda ovaj zahtjev postaje u redu čekanja i čeka da servisiranje počne.

U sistemima sa određenom servisnom disciplinom, dolazni zahtev, koji pronalazi da su svi uređaji zauzeti, u zavisnosti od njegovog prioriteta, se ili servisira van reda ili se stavlja u red čekanja.

Glavni elementi QS-a su: ulazni tok zahtjeva, red zahtjeva, opslužujući uređaji (kanali) i odlazni tok zahtjeva.

Proučavanje QS-a počinje analizom dolaznog toka zahtjeva. Dolazni tok zahtjeva je skup zahtjeva koji ulaze u sistem i trebaju biti servisirani. Proučava se dolazni tok zahtjeva kako bi se ustanovili obrasci ovog toka i dodatno unaprijedio kvalitet usluge.

U većini slučajeva, dolazni tok je nekontrolisan i zavisi od niza slučajnih faktora. Broj zahtjeva koji pristižu po jedinici vremena je slučajna varijabla. Slučajna varijabla je također vremenski interval između susjednih dolaznih zahtjeva. Međutim, pretpostavlja se da su dati prosječan broj primljenih zahtjeva po jedinici vremena i prosječni vremenski interval između susjednih dolaznih zahtjeva.

Prosječan broj zahtjeva koji ulaze u uslužni sistem u jedinici vremena naziva se stopa pristizanja potražnje i određuje se sljedećom relacijom:

gdje je T prosječna vrijednost intervala između pristizanja narednih zahtjeva.

Za mnoge stvarne procese, tok zahtjeva je prilično dobro opisan Poissonovim zakonom distribucije. Takav tok se naziva najjednostavnijim.

Najjednostavniji tok ima sljedeća važna svojstva:

1) Svojstvo stacionarnosti, koje izražava nepromjenjivost vjerovatnog režima protoka tokom vremena. To znači da bi broj zahtjeva koji ulaze u sistem u jednakim vremenskim intervalima trebao, u prosjeku, biti konstantan. Na primjer, broj automobila koji u prosjeku dnevno pristižu na utovar trebao bi biti isti za različite vremenske periode, na primjer, na početku i na kraju decenije.

2) odsustvo naknadnog dejstva, koje određuje međusobnu nezavisnost prijema jednog ili drugog broja zahteva za uručenje u vremenskim periodima koji se ne preklapaju. To znači da broj zahtjeva koji pristižu u datom vremenskom periodu ne zavisi od broja zahtjeva koji su servisirani u prethodnom vremenskom periodu. Na primjer, broj vozila koja stižu po materijal desetog dana u mjesecu je nezavisan od broja vozila servisiranih četvrtog ili bilo kojeg drugog prethodnog dana u mjesecu.

3) Svojstvo običnosti, koje izražava praktičnu nemogućnost istovremenog prijema dva ili više zahtjeva (vjerovatnoća takvog događaja je nemjerljivo mala u odnosu na period koji se razmatra, kada potonji teži nuli).

Uz najjednostavniji tok zahtjeva, distribucija zahtjeva koji ulaze u sistem poštuje Poissonov zakon distribucije:

vjerovatnoća da će tačno k zahtjeva stići u servisni sistem za vrijeme t:

Gdje. - prosječan broj primljenih zahtjeva za uslugu po jedinici vremena.

U praksi, uslovi najjednostavnijeg toka nisu uvek striktno ispunjeni. Proces je često nestacionaran (u različitim satima dana i različitim danima u mjesecu, tok zahtjeva se može promijeniti; može biti intenzivniji ujutro ili posljednjih dana u mjesecu). Postoji i posledica, kada broj zahteva za puštanje robe na kraju meseca zavisi od njihovog zadovoljenja na početku meseca. Fenomen heterogenosti se uočava i kada više klijenata istovremeno dolazi u skladište materijala. Međutim, općenito, Poissonov zakon distribucije odražava mnoge procese čekanja s prilično visokom aproksimacijom.

Osim toga, prisustvo Poissonovog toka zahtjeva može se utvrditi statističkom obradom podataka o prijemu zahtjeva za uslugu. Jedna od karakteristika Poissonovog zakona raspodjele je jednakost matematičkog očekivanja slučajne varijable i varijanse iste varijable, tj.

Jedna od najvažnijih karakteristika servisnih uređaja, koja određuje propusnost čitavog sistema, je servisno vrijeme.

Vrijeme usluge za jedan zahtjev () je slučajna varijabla koja se može mijenjati u širokom rasponu. Zavisi od stabilnosti rada samih servisnih uređaja, kao i od različitih parametara koji ulaze u sistem, zahtjeva (na primjer, različita nosivost vozila koja dolaze na utovar ili istovar.

Slučajnu varijablu u potpunosti karakterizira zakon raspodjele, koji se utvrđuje na osnovu statističkih testova.

U praksi se najčešće prihvata hipoteza o eksponencijalnom zakonu raspodjele vremena usluge.

Eksponencijalni zakon raspodjele vremena servisiranja javlja se kada se gustina distribucije naglo smanjuje s povećanjem vremena t. Na primjer, kada se većina zahtjeva brzo servisira, a dugotrajna usluga je rijetka. Prisustvo eksponencijalnog zakona raspodjele za vrijeme službe utvrđuje se na osnovu statističkih opservacija.

Sa eksponencijalnim zakonom raspodjele vremena servisiranja, vjerovatnoća događaja da vrijeme servisiranja neće trajati duže od t jednaka je:

gdje je v intenzitet servisiranja jednog zahtjeva od strane jednog servisnog uređaja koji se određuje iz relacije:

gdje je prosječno vrijeme za servisiranje jednog zahtjeva od strane jednog servisnog uređaja.

Treba napomenuti da ako je zakon raspodjele radnog vremena indikativan, onda će u prisustvu više servisnih uređaja iste snage biti indikativan i zakon raspodjele vremena rada po nekoliko uređaja:

gdje je n broj uređaja za opsluživanje.

Važan parametar QS-a je faktor opterećenja, koji se definiše kao omjer intenziteta prijema zahtjeva i intenziteta usluge v.

gdje je a faktor opterećenja; - intenzitet zahtjeva koji ulaze u sistem; v je intenzitet servisiranja jednog zahtjeva od strane jednog servisnog uređaja.

Iz (1) i (2) dobijamo to

S obzirom da je to intenzitet zahtjeva koji ulaze u sistem po jedinici vremena, proizvod pokazuje broj zahtjeva koji ulaze u sistem usluga tokom prosječnog vremena servisiranja jednog zahtjeva od strane jednog uređaja.

Za QS sa čekanjem, broj servisiranih uređaja n mora biti striktno veći od faktora opterećenja (zahtjev za stabilan ili stacionarni način rada QS-a):

U suprotnom, broj dolaznih zahtjeva će biti veći od ukupne produktivnosti svih uređaja za opsluživanje, a red čekanja će rasti bez ograničenja.

Za QS sa kvarovima i mješovitim tipovima ovaj uvjet može biti oslabljen; za efikasan rad ovih tipova QS-a dovoljno je zahtijevati da minimalni broj servisiranih uređaja n ne bude manji od faktora opterećenja:

1.3 Proces simulacije

Kao što je ranije napomenuto, proces iterativnog razvoja simulacionog modela počinje kreiranjem jednostavnog modela, koji zatim postepeno postaje složeniji u skladu sa zahtjevima problema koji se rješava. U procesu simulacije mogu se razlikovati sljedeće glavne faze:

1. Formiranje problema: opis problema koji se proučava i određivanje ciljeva studije.

2. Razvoj modela: logički i matematički opis modeliranog sistema u skladu sa formulacijom problema.

3. Priprema podataka: identifikacija, specifikacija i prikupljanje podataka.

4. Prevod modela: prevod modela na jezik prihvatljiv za računar koji se koristi.

5. Verifikacija: utvrđivanje ispravnosti mašinskih programa.

6. Validacija: procjena potrebne tačnosti i usklađenosti simulacionog modela sa realnim sistemom.

7. Strateško i taktičko planiranje: određivanje uslova za izvođenje mašinskog eksperimenta sa simulacionim modelom.

8. Eksperimentisanje: pokretanje simulacionog modela na računaru za dobijanje potrebnih informacija.

9. Analiza rezultata: proučavanje rezultata simulacionog eksperimenta radi pripreme zaključaka i preporuka za rješavanje problema.

10. Implementacija i dokumentacija: implementacija preporuka dobijenih iz simulacije, priprema dokumentacije o modelu i njegovo korištenje.

Razmotrimo glavne faze simulacijskog modeliranja. Prvi zadatak simulacijske studije je precizno definiranje problema i detaljno formuliranje ciljeva studije. Tipično, definicija problema je stalni proces koji se obično dešava tokom studije. Revidira se kao dublje razumijevanje problema koji se proučava i pojavljivanje novih aspekata istog.

Nakon što je formulisana početna definicija problema, počinje faza izgradnje modela sistema koji se proučava. Model uključuje statistički i dinamički opis sistema. U statističkom opisu određuju se elementi sistema i njihove karakteristike, a u dinamičkom opisu interakcija elemenata sistema, usled čega dolazi do promene njegovog stanja tokom vremena.

Proces formiranja modela je na mnogo načina umjetnost. Programer modela mora razumjeti strukturu sistema, identificirati pravila njegovog funkcionisanja i biti u stanju da istakne ono najvažnije u njima, eliminirajući nepotrebne detalje. Model mora biti lak za razumijevanje i u isto vrijeme dovoljno složen da realno predstavlja karakteristike stvarnog sistema. Najvažnije odluke donosi projektant o tome da li su usvojena pojednostavljenja i pretpostavke tačne, koje elemente i interakcije između njih treba uključiti u model. Nivo detalja u modelu zavisi od svrhe njegovog kreiranja. Potrebno je uzeti u obzir samo one elemente koji su bitni za rješavanje problema koji se proučava. I u fazi formiranja problema iu fazi modeliranja, neophodna je bliska interakcija između razvijača modela i njegovih korisnika. Osim toga, bliska interakcija u fazama formulacije problema i razvoja modela daje korisniku povjerenje u ispravnost modela, te stoga pomaže u osiguravanju uspješne implementacije rezultata simulacijske studije.

U fazi razvoja modela određuju se zahtjevi za ulaznim podacima. Neki od ovih podataka možda su već dostupni modelarima, dok će za prikupljanje drugih biti potrebno vrijeme i trud. Obično se vrijednost takvih ulaznih podataka postavlja na osnovu nekih hipoteza ili preliminarne analize. U nekim slučajevima, tačne vrijednosti jednog (ili više) ulaznih parametara imaju mali utjecaj na rezultate pokretanja modela. Osetljivost dobijenih rezultata na promene u ulaznim podacima može se proceniti provođenjem serije simulacionih radnji za različite vrednosti ulaznih parametara. Simulacijski model se stoga može koristiti za smanjenje vremena i troškova potrebnih za preciziranje ulaznih podataka. Nakon što je model razvijen i sakupljeni početni ulazni podaci, sljedeći zadatak je prevesti model u kompjuterski dostupan oblik.

U fazama verifikacije i validacije procjenjuje se funkcioniranje simulacijskog modela. U fazi verifikacije utvrđuje se da li model programiran za računar odgovara namjeri programera. Ovo se obično radi ručnom provjerom izračuna, ali se može koristiti i niz statističkih metoda.

Utvrđivanje adekvatnosti simulacionog modela sistema koji se proučava vrši se u fazi validacije. Validacija modela se obično izvodi na različitim nivoima. Specifične metode validacije uključuju utvrđivanje adekvatnosti korištenjem konstantnih vrijednosti za sve parametre simulacijskog modela ili procjenom osjetljivosti izlaza na promjene vrijednosti ulaznih podataka. Tokom procesa validacije, poređenja treba napraviti na osnovu analize stvarnih i eksperimentalnih podataka o funkcionisanju sistema.

Uslovi za izvođenje mašinskih vožnji modela određuju se u fazama strateškog i taktičkog planiranja. Zadatak strateškog planiranja je razviti efikasan eksperimentalni plan, kao rezultat kojeg se razjašnjava odnos između kontroliranih varijabli ili pronalazi kombinacija vrijednosti kontroliranih varijabli, minimiziranje ili maksimiziranje simulacijskog modela. Taktičko planiranje, za razliku od strateškog planiranja, bavi se pitanjem kako provesti svaku simulaciju u okviru eksperimentalnog plana kako bi se dobila najveća količina informacija iz izlaznih podataka. Važno mjesto u taktičkom planiranju zauzima definicija uslova za simulacijske vožnje i metode za smanjenje varijanse prosječne vrijednosti odziva modela.

Sljedeće faze u procesu simulacijskog istraživanja - izvođenje kompjuterskog eksperimenta i analiza rezultata - uključuju pokretanje simulacionog modela na računaru i interpretaciju rezultirajućih izlaznih podataka. Posljednja faza simulacijske studije je implementacija rezultirajućih rješenja i dokumentiranje simulacijskog modela i njegove upotrebe. Nijedan projekat simulacije ne treba smatrati završenim dok se rezultati ne koriste u procesu donošenja odluka. Uspeh implementacije u velikoj meri zavisi od toga koliko je korektno programer modela završio sve prethodne faze procesa simulacionog istraživanja. Ako su programer i korisnik blisko sarađivali i postigli međusobno razumijevanje u razvoju modela i njegovom istraživanju, onda je vjerovatno da će rezultat projekta biti uspješno implementiran. Ako između njih nije bilo bliskog odnosa, tada će, uprkos eleganciji i adekvatnosti simulacijskog modeliranja, biti teško razviti učinkovite preporuke.

Gore navedeni koraci se rijetko izvode u strogo definiranom nizu, od definicije problema do dokumentacije. Tokom simulacije može doći do neuspjeha u izvođenju modela, pogrešnih pretpostavki koje kasnije moraju biti napuštene, ponovnog fokusiranja istraživačkih ciljeva, ponovnih procjena i ponovne izgradnje modela. Ovaj proces omogućava razvoj simulacionog modela koji daje valjanu procjenu alternativa i olakšava proces donošenja odluka.

Poglavlje 2. Distribucije i generatori pseudoslučajnih brojeva

U nastavku će se koristiti sljedeće oznake:

X je slučajna varijabla; f(x) - funkcija gustine vjerovatnoće X; F(x) - funkcija vjerovatnoće X;

a - minimalna vrijednost;

b - maksimalna vrijednost;

μ - matematičko očekivanje M[X]; σ2 - varijansa M[(X-μ)2];

σ - standardna devijacija; α-parametar funkcije gustoće vjerovatnoće;

Red dužine k ostaje u njemu sa verovatnoćom Pk i ne pridružuje se redu sa verovatnoćom gk=1 - Pk." Upravo tako se ljudi obično ponašaju u redovima. U sistemima čekanja, koji su matematički modeli proizvodnih procesa, moguće je Dužina reda čekanja je ograničena konstantnom veličinom (kapacitet bunkera, na primjer). Očigledno, ovo je poseban slučaj općenite postavke. Neki...

Pokazatelji učinka QS-a

• apsolutni i relativni kapacitet sistema;
• stope opterećenja i praznog hoda;
• prosječno vrijeme za potpuno učitavanje sistema;
• prosječno vrijeme koje aplikacija ostaje u sistemu.

Indikatori koji karakterišu sistem sa stanovišta potrošača:

• P obs – vjerovatnoća servisiranja zahtjeva,
• t syst – vrijeme boravka aplikacije u sistemu.

Indikatori koji karakterišu sistem u smislu njegovih operativnih svojstava:

• λ b– apsolutnu propusnost sistema (prosečan broj usluženih zahteva u jedinici vremena),
• P obs – relativni kapacitet sistema,
• k z – faktor opterećenja sistema.

vidi takođe Parametri ekonomske efikasnosti QS

Zadatak. Zajednički računarski centar sa tri računara prima narudžbine od preduzeća za rad na računaru. Ako sva tri računara rade, onda se novoprimljeni nalog ne prihvata i preduzeće je prinuđeno da kontaktira drugi računarski centar. Prosječno vrijeme rada sa jednom narudžbom je 3 sata.Intenzitet toka aplikacija je 0,25 (1/sat). Naći granične vjerovatnoće stanja i indikatora performansi računskog centra.
Rješenje. Prema uslovu n=3, λ=0,25(1/h), t vol. =3 (h). Intenzitet servisnog protoka μ=1/t vol. =1/3=0,33. Intenzitet opterećenja računara prema formuli (24) ρ=0,25/0,33=0,75. Nađimo granične vjerovatnoće stanja:
prema formuli (25) p 0 =(1+0,75+0,75 2 /2!+0,75 3 /3!) -1 =0,476;
prema formuli (26) p 1 =0,75∙0,476=0,357; p 2 =(0,75 2 /2!)∙0,476=0,134; p 3 =(0,75 3 /3!)∙0,476=0,033 tj. u stacionarnom režimu rada računarskog centra u proseku 47,6% vremena nema zahteva, 35,7% - postoji jedan zahtev (jedan računar je zauzet), 13,4% - dva zahteva (dva računara), 3,3% od vrijeme - tri zahtjeva (tri računara su zauzeta).
Verovatnoća kvara (kada su sva tri računara zauzeta), dakle, P otvoren. =p 3 =0,033.
Prema formuli (28), relativni kapacitet centra je Q = 1-0,033 = 0,967, tj. U prosjeku, na svakih 100 zahtjeva, računski centar obradi 96,7 zahtjeva.
Prema formuli (29), apsolutni kapacitet centra je A = 0,25∙0,967 = 0,242, tj. U prosjeku se uruče 0,242 prijave na sat.
Prema formuli (30) prosječan broj zauzetih računara k = 0,242/0,33 = 0,725, tj. svaki od tri računara će biti zauzet servisiranjem zahtjeva u prosjeku samo 72,5/3 = 24,2%.
Prilikom procene efikasnosti računarskog centra potrebno je uporediti prihod od izvršenja zahteva sa gubicima od zastoja skupih računara (s jedne strane imamo visoku propusnost QS-a, a sa druge strane , postoji značajan zastoj servisnih kanala) i izabrati kompromisno rješenje.

Zadatak. Luka ima jedan vez za iskrcaj brodova. Brzina protoka plovila je 0,4 (brodovi dnevno). Prosječno vrijeme istovara za jedno plovilo je 2 dana. Pretpostavlja se da red može biti neograničene dužine. Pronađite pokazatelje učinka veza, kao i vjerojatnost da ne više od 2 plovila čekaju iskrcaj.
Rješenje. Imamo ρ = λ/μ = μt vol. =0,4∙2=0,8. Pošto je ρ = 0,8 < 1, onda se red za istovar ne može neograničeno povećavati i postoje granične vjerovatnoće. Hajde da ih nađemo.
Vjerovatnoća da je vez slobodan, prema (33) p 0 = 1 - 0,8 = 0,2, a vjerovatnoća da je zauzet, P popunjenost. = 1-0,2 = 0,8. Prema formuli (34), vjerovatnoće da se na vezu nalazi 1, 2, 3 plovila (tj. 0, 1, 2 broda čekaju na istovar) jednake su p 1 = 0,8 (1-0,8) = 0, 16; p 2 = 0,8 2 ∙(1-0,8) = 0,128; p 3 = 0,8 3 ∙(1-0,8) = 0,1024.
Vjerovatnoća da najviše 2 plovila čekaju na istovar je jednaka
P=p 1 +p 2 +p 3 = 0,16 + 0,128 + 0,1024 = 0,3904
Prema formuli (40), prosječan broj brodova koji čekaju iskrcaj
L jh =0,8 2 /(1-0,8) = 3,2
i prosječno vrijeme čekanja na istovar prema formuli (15,42)
Tp = 3,2/0,8 = 4 dana.
Prema formuli (36), prosječan broj plovila smještenih na vezu, L sist. = 0,8/(1-0,8) = 4 (dana) (ili jednostavnije prema (37) L sist. = 3,2+0,8 = 4 (dana), a prosječno vrijeme boravka plovila na vezu prema formuli (41 ) T sist = 4/0,8 = 5 (dana).
Očigledno je da je efikasnost iskrcaja brodova niska. Da bi se to povećalo, potrebno je smanjiti prosječno vrijeme istovara plovila t oko ili povećati broj vezova n.

Zadatak. U supermarketu, tok kupaca stiže u naplatni centar sa intenzitetom λ = 81 osoba. u jedan sat. Prosječno trajanje usluge kontrolora blagajne jednom kupcu t rev = 2 min. definirati:
A. Minimalni broj blagajnika n min, u kojoj red neće rasti do beskonačnosti, i odgovarajuće karakteristike usluge za n=n min.
b. Optimalna količina n opt. kontrolori-blagajnici, kod kojih će relativna vrijednost troškova C rel., povezanih sa troškovima održavanja servisnih kanala i zadržavanjem u redu kupaca, datih na primjer kao , biti minimalna, a karakteristike usluge uporediti sa n= n min i n=n opt.
V. Vjerovatnoća da neće biti više od tri klijenta u redu.
Rješenje.
A. Po stanju l = 81(1/h) = 81/60 = 1,35 (1/min.). Prema formuli (24) r = l/m = lt rev = 1,35×2 = 2,7. Red neće rasti beskonačno pod uvjetom r/n< 1, т.е. при n >r = 2.7. Dakle, minimalni broj kontrolora blagajne je n min = 3.
Nađimo karakteristike servisa QS-a na P= 3.
Vjerovatnoća da u čvoru poravnanja nema kupaca, prema formuli (45) p 0 = (1+2,7+2,7 2 /2!+2,7 3 /3!+2,7 4 /3!(3 -2,7)) - 1 = 0,025, tj. u prosjeku 2,5% kontrolori i blagajnici će neko vrijeme mirovati.
Vjerovatnoća da će postojati red na proračunskom čvoru, prema (48) P vrlo. = (2,7 4 /3!(3-2,7))0,025 = 0,735
Prosječan broj kupaca u redu za (50) L och. = (2,7 4 /3∙3!(1-2,7/3) 2)0,025 = 7,35.
Prosječno vrijeme čekanja u redu za (42) T vrlo. = 7,35/1,35 = 5,44 (min).
Prosječan broj kupaca u čvoru poravnanja prema (51) L sistemu. = 7,35+2,7 = 10,05.
Prosječno vrijeme provedeno od strane kupaca u čvoru poravnanja prema (41) T sist. = 10,05/1,35 = 7,44 (min).
Tabela 1

Karakteristike usluge	Broj blagajnika
	3	4	5	6	7
Vjerovatnoća zastoja blagajnika p 0	0,025	0,057	0,065	0,067	0,067
Prosječan broj kupaca u redu T vrlo.	5,44	0,60	0,15	0,03	0,01
Relativna vrijednost troškova C rel.	18,54	4,77	4,14	4,53	5,22

Prosječan broj blagajnika uključenih u opsluživanje kupaca, prema (49) k = 2,7.
Koeficijent (udio) blagajnika zaposlenih u servisu
= ρ/n = 2,7/3 = 0,9.
Apsolutna propusnost računskog čvora A = 1,35 (1/min), ili 81 (1/h), tj. 81 kupac na sat.
Analiza karakteristika usluge ukazuje na značajno preopterećenje platnog centra u prisustvu tri blagajnika.
b. Relativna vrijednost troškova za n = 3
C rel. = = 3/1,35+3∙5,44 = 18,54.
Izračunajmo relativnu vrijednost troškova za ostale vrijednosti P(Tabela 1).
Kao što se vidi iz tabele. 2, minimalni troškovi se dobijaju pri n = n opt. = 5 kontrolora-blagajnika.
Odredimo karakteristike usluge proračunskog čvora za n = n opt. =5. Dobijamo P vrlo dobro. = 0,091; L vrlo = 0,198; T och. = 0,146 (min); L syst. = 2,90; T snst. = 2,15 (min); k = 2,7; k 3 = 0,54.
Kao što vidimo, sa n = 5 u poređenju sa n = 3, verovatnoća pojavljivanja reda P veoma je značajno smanjena. , dužina reda L vrlo i prosječno vrijeme provedeno u redu T vrlo. i, shodno tome, prosječan broj kupaca L sistema. i prosječno vrijeme provedeno u sistemu platnog čvora T, kao i udio kontrolora angažovanih na servisiranju k 3. Ali prosječan broj kontrolora blagajne uključenih u servisiranje k i apsolutna propusnost platnog čvora A se prirodno nisu promijenili.
V. Vjerovatnoća da neće biti više od 3 kupca u redu je data sa
= 1- P vrlo dobro + p 5+1 + p 5+2 + p 5+3 , pri čemu se svaki član nalazi pomoću formula (45) – (48). Dobijamo za n=5:

Imajte na umu da je u slučaju n=3 blagajnika ista vjerovatnoća znatno manja: P(r ≤ 3) =0,464.

1. Indikatori efikasnosti upotrebe QS:

Apsolutni kapacitet QS-a je prosječan broj zahtjeva koji mogu biti

može poslužiti QS po jedinici vremena.

Relativni kapacitet QS – odnos prosječnog broja zahtjeva,

broj uslužnih pružalaca usluga u jedinici vremena, na prosječan broj dolazaka za iste

vrijeme primjene.

Prosječno trajanje radnog staža CMO-a.

Stopa iskorištenosti QS-a je prosječan udio vremena tokom kojeg

CMO je zauzet servisiranjem zahtjeva itd.

2. Indikatori kvaliteta za servisiranje aplikacija:

Prosječno vrijeme čekanja za aplikaciju u redu čekanja.

Prosječno vrijeme boravka aplikacije u CMO-u.

Vjerovatnoća da će zahtjev biti odbijen bez čekanja.

Vjerovatnoća da će novoprimljena prijava biti odmah prihvaćena za servis.

Zakon raspodjele vremena čekanja za aplikaciju u redu čekanja.

Zakon raspodjele vremena boravka aplikacije u QS-u.

Prosječan broj aplikacija u redu čekanja.

Prosječan broj prijava u CMO, itd.

3. Indikatori efikasnosti funkcionisanja para „SMO – klijent“, pri čemu se pod „klijentom“ podrazumeva čitav skup zahteva ili određeni izvor istih. Takvi pokazatelji uključuju, na primjer, prosječan prihod koji je ostvario CMO po jedinici vremena

Klasifikacija sistema čekanja

Po broju QS kanala:

jednokanalni(kada postoji jedan servisni kanal)

višekanalni, preciznije n-kanal (kada je broj kanala n≥ 2).

Po servisnoj disciplini:

1. SMO sa neuspjesima, u kojem je aplikacija primljena na ulaz QS-a u trenutku kada je sve

kanali su zauzeti, prima "odbijanje" i napušta QS ("nestaje"). Tako da je ova aplikacija još uvijek

servisiran, mora ponovo ući na QS ulaz i smatrati se prijavom primljenom po prvi put. Primjer QS-a sa odbijanjima je rad automatske telefonske centrale: ako je birani telefonski broj (aplikacija primljena na ulazu) zauzeta, tada aplikacija prima odbijenicu, a da bi došla do ovog broja, mora biti ponovo birao.

2. SMO sa iščekivanjem(neograničeno čekanje ili queue). U takvim sistemima

zahtjev koji stigne kada su svi kanali zauzeti stavlja se u red čekanja i čeka da kanal postane dostupan i prihvati ga za uslugu. Svaka prijava primljena na ulazu će na kraju biti servisirana. Takvi samouslužni sistemi se često nalaze u trgovini, u oblasti potrošačkih i medicinskih usluga, te u preduzećima (na primjer, servisiranje mašina od strane tima montera).

3. SMO mješoviti tip(sa ograničenim očekivanjima). To su sistemi u kojima se nameću određena ograničenja ostanku aplikacije u redu čekanja.

Ova ograničenja se mogu odnositi na dužina reda čekanja, tj. maksimalno moguće

broj aplikacija koje mogu biti u redu u isto vrijeme. Primjer takvog sistema je automehaničarska radionica koja ima ograničen parking za neispravne automobile koji čekaju popravku.

Ograničenja čekanja mogu biti zabrinuta vrijeme koje je aplikacija provela u redu čekanja, prema istoriji

u kom trenutku izlazi iz reda i napušta sistem).

U QS-u sa čekanjem iu QS-u mješovitog tipa koriste se različite komunikacijske sheme.

servisiranje zahtjeva iz reda. Usluga može biti naredio, kada se zahtjevi iz reda servisiraju redoslijedom kojim ulaze u sistem, i poremećen, u kojem se aplikacije iz reda poslužuju slučajnim redoslijedom. Ponekad se koristi prioritetna usluga, kada se neki zahtjevi iz reda smatraju prioritetnim i stoga se poslužuju prvi.

Da ograničite protok aplikacija:

zatvoreno I otvoren.

Ako je protok aplikacija ograničen i aplikacije koje su napustile sistem mu se mogu vratiti,

xia, onda je QS zatvoreno, inače - otvoren.

Po broju servisnih faza:

jednofazni I višefazni

Ako su QS kanali homogeni, tj. izvršite istu operaciju održavanja

niya, onda se takvi QS nazivaju jednofazni. Ako se servisni kanali nalaze uzastopno i heterogeni su, budući da obavljaju različite uslužne operacije (tj. usluga se sastoji od nekoliko uzastopnih faza ili faza), tada se QS naziva višefazni. Primjer rada višefaznog QS-a je servis automobila na servisu (pranje, dijagnostika itd.).