Dom
Razmotrimo jednokanalni sustav čekanja s čekanjem.
Pretpostavit ćemo da je dolazni tok zahtjeva za uslugom najjednostavniji tok intenziteta λ.
Intenzitet protoka usluge je μ. Trajanje usluge je slučajna varijabla podložna zakonu eksponencijalne distribucije. Tok usluge je najjednostavniji Poissonov tok događaja. Zahtjev primljen kada je kanal zauzet nalazi se u redu i čeka uslugu. Pretpostavit ćemo da je veličina reda ograničena i da ne može primiti više od m aplikacije, tj. aplikacija koja se zatekla u trenutku dolaska na CMO m +1 zahtjeva (m
čekanje u redu i jedan na servisu) napušta CMO.
(0‑1)
Sustav jednadžbi koji opisuje proces u ovom sustavu ima rješenje:
Nazivnik prvog izraza je geometrijska progresija s prvim članom 1 i nazivnikom ρ, odakle dobivamo Na ρ
(0‑8)
= 1 možete pribjeći izravnom izračunu
Prosječan broj aplikacija u sustavu.
(0‑9)
Budući da je prosječan broj aplikacija u sustavugdje je prosječan broj prijava u servisu, onda znajući da ostaje pronaći. Jer postoji samo jedan kanal, tada broj servisiranih zahtjeva može biti 0 ili 1 s vjerojatnostima P 0 i P 1=1- P 0
(0‑10)
prema tome, odakle
(0‑11)
a prosječan broj prijava u sustavu je.
Prosječno vrijeme čekanja na aplikaciju u redu
tj. prosječno vrijeme čekanja aplikacije u redu čekanja jednako je prosječnom broju aplikacija u redu čekanja podijeljenom s intenzitetom protoka aplikacija.
Vrijeme boravka aplikacije u sustavu zbroj je vremena čekanja aplikacije u redu čekanja i vremena usluge. Ako je opterećenje sustava 100%, tada je =1/μ, inače = q/μ. Odavde
(0‑13)
Sadržaj rada.
Priprema eksperimentalnih instrumenata .
Izvodi se slično u skladu s općim pravilima.
Proračun pomoću analitičkog modela.
1. Pripremite sljedeću tablicu u programu Microsoft Excel.
2. U stupce za QS parametre tablice upišite početne podatke koji se određuju prema pravilu:
m=1,2,3
(maksimalna duljina čekanja).
Za svaku vrijednost Zahtjev primljen kada je kanal zauzet nalazi se u redu i čeka uslugu. Pretpostavit ćemo da je veličina reda ograničena i da ne može primiti više od potrebno je pronaći teorijske i eksperimentalne vrijednosti QS indikatora za sljedeće parove vrijednosti:
= <порядковый номер в списке группы>
3. U stupce s pokazateljima analitičkog modela upiši odgovarajuće formule.
Eksperimentirajte na simulacijskom modelu.
1. Postavite način pokretanja s eksponencijalno raspodijeljenim vremenom servisiranja postavljanjem vrijednosti odgovarajućeg parametra na 1.
2. Za svaku kombinaciju Zahtjev primljen kada je kanal zauzet nalazi se u redu i čeka uslugu. Pretpostavit ćemo da je veličina reda ograničena i da ne može primiti više od , i pokrenite model.
3. Rezultate trčanja unesite u tablicu.
4. Unesite formule za izračun prosječne vrijednosti pokazatelja u odgovarajuće stupce tablice P otvoreno, q i A.
Analiza rezultata .
1. Analizirati rezultate dobivene teorijskim i eksperimentalnim metodama, međusobno uspoređujući rezultate.
2. Za m=3, nacrtajte ovisnosti na jednom dijagramu P otvoriti iz teorijski i eksperimentalno dobivenih podataka.
Optimizacija QS parametara .
Riješite problem optimizacije veličine broja mjesta u redu Zahtjev primljen kada je kanal zauzet nalazi se u redu i čeka uslugu. Pretpostavit ćemo da je veličina reda ograničena i da ne može primiti više od za uređaj s prosječnim radnim vremenom = s gledišta postizanja maksimalne dobiti. Kao uvjete problema uzmite:
- prihod od servisiranja jedne aplikacije jednak 80 USD/sat,
- trošak održavanja jednog uređaja jednak je 1cu/sat.
1. Za izračune je preporučljivo izraditi tablicu:
Prvi stupac popunjava se vrijednostima brojeva u prirodnom nizu (1,2,3...).
Sve ćelije u drugom i trećem stupcu ispunjene su vrijednostima i .
Formule za stupce tablice u odjeljku 0 prenose se u ćelije stupaca od četvrtog do devetog.
U stupce s početnim podacima odjeljaka Prihod, Trošak, Dobit unesite vrijednosti (vidi gore).
U stupce s izračunatim vrijednostima odjeljaka Prihod, Rashod, Dobit zapišite formule za izračun:
- broj aplikacija po jedinici vremena
N r =A
- ukupni prihod po jedinici vremena
I S = I r *N r
- ukupna potrošnja po jedinici vremena
E S =E s + E q *(n-1)
- profit po jedinici vremena
P = I S - E S
Gdje
Ir - prihod od jedne prijave,
E s - trošak rada jednog uređaja,
jednadžba - trošak rada jednog mjesta u redu.
Grafikoni za P otvoreni,
- tablica s podacima kako biste pronašli najbolje m i vrijednost m opt,
- graf dobiti po jedinici vremena u odnosu m.
Sigurnosna pitanja :
1) Ukratko opišite jednokanalni QS model s ograničenim redom čekanja.
2) Koji pokazatelji karakteriziraju funkcioniranje jednokanalnog QS-a s kvarovima?
3) Kako se izračunava vjerojatnost p 0 ?
4) Kako se računaju vjerojatnosti p ja?
5) Kako pronaći vjerojatnost neuspjeha servisiranja aplikacije?
6) Kako pronaći relativnu propusnost?
7) Što je apsolutna propusnost?
8) Kako se izračunava prosječan broj prijava u sustavu?
9) Navedite primjere QS-a s ograničenim redom.
Zadaci.
1) Luka ima jedan teretni vez za iskrcaj brodova. Protok je 0,5 posjeta dnevno. Prosječno vrijeme istovara za jedno plovilo je 2 dana. Ako su 3 plovila u redu čekanja za iskrcaj, tada se pristiglo plovilo šalje na drugi vez radi iskrcaja. Pronađite pokazatelje učinkovitosti veza.
2) Šalter informacija željezničkog kolodvora zaprima telefonske zahtjeve u intenzitetu od 80 zahtjeva na sat. Operater deska za pomoć odgovara na dolazni poziv u prosjeku za 0,7 minuta. Ako je operater zauzet, klijent dobiva poruku "Čekaj odgovor"; zahtjev se stavlja u red čekanja čija duljina ne prelazi 4 zahtjeva. Dati ocjenu rada Help deska i mogućnost njegove reorganizacije
Savezna agencija za obrazovanje Ruske Federacije
FGOU SPO "Perevozsky Construction College"
Nastavni rad
u disciplini "Matematičke metode"
na temu „SMO s ograničenim vremenom čekanja. Zatvoren QS"
Uvod................................................. ......................................................... ............. 2
1. Osnove teorije čekanja .............................................. ......... 3
1.1 Koncept slučajnog procesa..................................................... ......... .................... 3
1.2 Markovljev slučajni proces ............................................. ...... ................ 4
1.3 Tokovi događaja..................................................... .................... .............................. ............. 6
1.4 Kolmogorovljeve jednadžbe za vjerojatnosti stanja. Konačne vjerojatnosti stanja.................................................. .... ................................................ .......... 9
1.5 Problemi teorije čekanja .............................................. ....... .. 13
1.6 Klasifikacija sustava čekanja .............................................. ..... 15
2. Sustavi čekanja u redu................................................. ......... 16
2.1 Jednokanalni QS s čekanjem ................................................ ......... .......... 16
2.2 Višekanalni QS s čekanjem..................................... ......... ......... 25
3. Zatvoreni QS............................................. ...... ............................................ ... 37
Rješenje problema..................................................... ..................................................... 45
Zaključak................................................. ................................................. ...... .50
Reference ................................................. ......................................................... 51
U ovom kolegiju razmotrit ćemo različite sustave čekanja (QS) i mreže čekanja (Queuing).
Sustav čekanja (QS) shvaća se kao dinamički sustav dizajniran za učinkovito servisiranje toka zahtjeva (uslužni zahtjevi) pod ograničenjima resursa sustava.
QS modeli su zgodni 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 probabilistička. 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.
Skup međusobno povezanih QS-ova naziva se mreža čekanja (stohastička mreža).
Za početak ćemo se osvrnuti na osnove teorije QS-a, zatim ćemo prijeći na detaljnije upoznavanje sa QS-om s očekivanjem i zatvorenim QS-om. Tečaj uključuje i praktični dio, u kojem ćemo detaljno naučiti kako teoriju primijeniti u praksi.
Teorija čekanja jedna je od grana teorije vjerojatnosti. Ova teorija smatra vjerojatnosni problemi i matematički modeli (prije smo razmatrali determinističke matematičke modele). Podsjetimo da:
Deterministički matematički model odražava ponašanje objekta (sustava, procesa) iz perspektive puna izvjesnost u sadašnjosti i budućnosti.
Probabilistički matematički model uzima u obzir utjecaj slučajnih čimbenika na ponašanje objekta (sustava, procesa) i, prema tome, procjenjuje budućnost sa stajališta vjerojatnosti određenih događaja.
one. ovdje se, kao na primjer, u teoriji igara razmatraju problemi u uvjetima nesigurnost .
Razmotrimo najprije neke koncepte koji karakteriziraju "stohastičku nesigurnost", kada su neizvjesni čimbenici uključeni u problem slučajne varijable (ili slučajne funkcije), čije su vjerojatnosne karakteristike ili poznate ili se mogu dobiti iz iskustva. Takva nesigurnost se također naziva "povoljna", "benigna".
Strogo govoreći, nasumični poremećaji su svojstveni svakom procesu. Lakše je dati primjere slučajnog procesa nego "neslučajnog" procesa. Čak je, na primjer, proces pokretanja sata (čini se da je to strogo kalibriran rad - "radi kao sat") podložan nasumičnim promjenama (kretanje naprijed, zaostajanje, zaustavljanje). Ali sve dok su ti poremećaji beznačajni i imaju mali utjecaj na parametre koji nas zanimaju, možemo ih zanemariti i proces smatrati determinističkim, neslučajnim.
Neka postoji neki sustav S(tehnički uređaj, skupina takvih uređaja, tehnološki sustav - stroj, radilište, radionica, poduzeće, industrija itd.). U sustavu S curenja slučajni proces, ako tijekom vremena mijenja stanje (prelazi iz jednog stanja u drugo), štoviše, na dosad nepoznat slučajan način.
Primjeri:
1. Sustav S– tehnološki sustav (strojni dio). Strojevi se s vremena na vrijeme pokvare i popravljaju. Proces koji se odvija u ovom sustavu je slučajan.
2. Sustav S- zrakoplov koji leti na određenoj visini duž određene rute. Uznemirujući čimbenici - vremenski uvjeti, pogreške posade itd., posljedice - neravnine, kršenje rasporeda letenja itd.
Slučajni proces koji se odvija u sustavu naziva se Markovskog, ako za bilo koji trenutak vremena t 0 vjerojatnosnim karakteristikama procesa u budućnosti ovisi samo o njegovom trenutnom stanju t 0 i ne ovise o tome kada i kako je sustav dostigao ovo stanje.
Neka je sustav u trenutku t 0 u nekom stanju S 0 . Znamo karakteristike stanja sustava u sadašnjosti i sve što se događalo tijekom t <t 0 (povijest procesa). Možemo li predvidjeti (predvidjeti) budućnost, t.j. što će se dogoditi kada t >t 0? Ne baš, ali neke vjerojatnosne karakteristike procesa mogu se pronaći u budućnosti. Na primjer, vjerojatnost da nakon nekog vremena sustav S moći će S 1 ili će ostati u stanju S 0, itd.
Primjer. sustav S- skupina zrakoplova koja sudjeluje u zračnoj borbi. Neka x– broj “crvenih” aviona, g– broj “plavih” letjelica. Do vremena t 0 broj preživjelih (neoborenih) zrakoplova, odnosno – x 0 , g 0 . Zanima nas kolika je vjerojatnost da će u nekom trenutku brojčana nadmoć biti na strani “crvenih”. Ova vjerojatnost ovisi o stanju u kojem je sustav bio u tom trenutku t 0, a ne o tome kada su i kojim redoslijedom oboreni umrli do trenutka t 0 aviona.
U praksi se Markovljevi procesi u svom čistom obliku obično ne susreću. Ali postoje procesi za koje se utjecaj "prapovijesti" može zanemariti. I pri proučavanju takvih procesa mogu se koristiti Markovljevi modeli (teorija čekanja ne razmatra Markovljeve sustave čekanja, ali je matematički aparat koji ih opisuje mnogo složeniji).
U operacijskim istraživanjima od velike su važnosti Markovljevi slučajni procesi s diskretnim stanjima i kontinuiranim vremenom.
Proces se zove proces diskretnog stanja, ako su njegova moguća stanja S 1 , S 2, ... može se odrediti unaprijed, a prijelaz sustava iz stanja u stanje događa se "u skoku", gotovo trenutno.
Proces se zove kontinuirani vremenski proces, ako trenuci mogućih prijelaza iz stanja u stanje nisu unaprijed fiksirani, već su neizvjesni, slučajni i mogu se dogoditi u svakom trenutku.
Primjer. Tehnološki sustav (presjek) S sastoji se od dva stroja, od kojih svaki može otkazati (zakazati) u slučajnom trenutku, nakon čega odmah počinje popravak jedinice, koji također traje nepoznato, slučajno vrijeme. Moguća su sljedeća stanja sustava:
S 0 - oba stroja rade;
S 1 - prvi stroj se popravlja, drugi radi;
S 2 - drugi stroj se popravlja, prvi radi;
S 3 - oba stroja su na popravku.
Prijelazi sustava S iz stanja u stanje događa se gotovo trenutno, u nasumičnim trenucima kada određeni stroj zakaže ili je popravak dovršen.
Pri analizi slučajnih procesa s diskretnim stanjima prikladno je koristiti geometrijsku shemu - grafikon stanja. Vrhovi grafa su stanja sustava. Lukovi grafa su mogući prijelazi iz stanja u stanje. Za naš primjer, grafikon stanja je prikazan na sl. 1.
Riža. 1. Graf stanja sustava
Bilješka. Prijelaz iz stanja S 0 in S 3 nije označen na slici, jer pretpostavlja se da strojevi kvare neovisno jedan o drugom. Zanemarujemo mogućnost istovremenog kvara oba stroja.
Tok događaja– niz homogenih događaja koji slijede jedan za drugim u nekim slučajnim trenucima vremena.
U prethodnom primjeru, to je tijek kvarova i tok obnova. Ostali primjeri: protok poziva na telefonskoj centrali, protok kupaca u trgovini itd.
Tijek događaja može se vizualno prikazati nizom točaka na vremenskoj osi O t- riža. 2.
Riža. 2. Slika tijeka događaja na vremenskoj osi
Položaj svake točke je slučajan, a ovdje je prikazana samo jedna implementacija toka.
Intenzitet protoka događaja ( ) je prosječan broj događaja po jedinici vremena.
Pogledajmo neka svojstva (tipove) tokova događaja.
Tok događaja se zove stacionarni, ako njegove vjerojatnosne karakteristike ne ovise o vremenu.
Konkretno, intenzitet stacionarnog strujanja je konstantan. Tijek događaja neizbježno ima kondenzacije ili razrjeđenja, ali oni nisu pravilne prirode, a prosječan broj događaja u jedinici vremena je konstantan i ne ovisi o vremenu.
Tok događaja se zove protjecati bez posljedica, ako za bilo koja dva odsječka vremena koji se ne preklapaju i (vidi sliku 2) broj događaja koji padaju na jedan od njih ne ovisi o tome koliko događaja pada na drugi. Drugim riječima, to znači da se događaji koji tvore tijek pojavljuju u određenim vremenskim točkama neovisno jedan o drugom a svaki su uzrokovani svojim uzrocima.
Tok događaja se zove obični, ako se događaji u njemu pojavljuju jedan po jedan, a ne u skupinama od nekoliko odjednom.
Tok događaja se zove najjednostavniji (ili stacionarni Poisson), ako ima tri svojstva odjednom:
1) stacionarni;
2) obični;
3) nema posljedica.
Najjednostavniji tok ima najjednostavniji matematički opis. On igra istu posebnu ulogu među tokovima kao zakon normalne distribucije među drugim zakonima distribucije. Naime, superponiranjem dovoljno velikog broja neovisnih, stacionarnih i običnih strujanja (međusobno usporedivih po intenzitetu) dobiva se strujanje blisko najjednostavnijem.
Za najjednostavniji protok s intervalom intenziteta T između susjednih događaja ima tzv eksponencijalna distribucija s gustoćom:
gdje je parametar eksponencijalnog zakona.
Za slučajnu varijablu T, koji ima eksponencijalnu distribuciju, matematičko očekivanje je recipročna vrijednost parametra, a standardna devijacija jednaka je matematičkom očekivanju:
Uzimajući u obzir Markovljeve procese s diskretnim stanjima i kontinuiranim vremenom, pretpostavlja se da su svi prijelazi sustava S iz stanja u stanje nastaju pod utjecajem jednostavnih tokova događaja (tijekovi poziva, tokovi kvarova, tokovi oporavka, itd.). Ako svi tokovi događaja prenose sustav S od stanja do stanja najjednostavnijeg, tada će proces koji se odvija u sustavu biti markovski.
Dakle, na sustav u stanju utječe jednostavan tok događaja. Čim se pojavi prvi događaj ovog toka, sustav “skače” iz stanja u stanje (na grafikonu stanja uz strelicu).
Radi jasnoće, na grafikonu stanja sustava za svaki luk je naznačen intenzitet toka događaja koji pomiče sustav duž ovog luka (strelica). - intenzitet toka događaja koji sustav prenosi iz stanja u . Takav se graf naziva označeno. Za naš primjer, označeni graf je prikazan na sl. 3.
Riža. 3. Označeni grafikon stanja sustava
Na ovoj slici - intenzitet toka kvara; - intenzitet protoka oporavka.
Pretpostavljamo da prosječno vrijeme popravka stroja ne ovisi o tome popravlja li se jedan stroj ili oba odjednom. one. Svaki stroj popravlja poseban stručnjak.
Neka je sustav u državi S 0 . U stanju S 1 preveden je tijekom kvarova prvog stroja. Njegov intenzitet je jednak:
gdje je prosječno vrijeme rada bez kvara prvog stroja.
Od države S 1 in S 0 sustav se prenosi putem "završetka popravka" prvog stroja. Njegov intenzitet je jednak:
gdje je prosječno vrijeme popravka za prvi stroj.
Na sličan način izračunavaju se intenziteti tokova događaja koji prenose sustav duž svih lukova grafa. Imajući na raspolaganju označeni graf stanja sustava, konstruiramo matematički model ovog procesa.
Neka sustav koji se razmatra S ima -moguća stanja. Vjerojatnost th stanja je vjerojatnost da će u trenutku vremena sustav biti u stanju. Očito je da je za bilo koji trenutak u vremenu zbroj svih vjerojatnosti stanja jednak jedan:
Pronaći sve vjerojatnosti stanja kao funkcije vremena, sastaviti i riješiti Kolmogorovljeve jednadžbe– posebna vrsta jednadžbi u kojoj su nepoznate funkcije vjerojatnosti stanja. Ovdje je prikazano pravilo za sastavljanje ovih jednadžbi bez dokaza. Ali prije nego što ga predstavimo, objasnimo koncept konačna vjerojatnost stanja .
Što će se dogoditi s vjerojatnostima stanja na ? Hoće li težiti ikakvim granicama? Ako te granice postoje i ne ovise o početnom stanju sustava, tada se nazivaju vjerojatnosti konačnog stanja .
gdje je konačan broj stanja sustava.
Vjerojatnosti konačnog stanja– to više nisu promjenjive veličine (funkcije vremena), već stalni brojevi. Očito je da:
Vjerojatnost konačnog stanja je u biti prosječno relativno vrijeme u kojem sustav ostaje u ovom stanju.
Na primjer, sustav S ima tri stanja S 1 , S 2 i S 3. Njihove konačne vjerojatnosti su 0,2; 0,3 i 0,5. To znači da sustav u graničnom stacionarnom stanju provede u prosjeku 2/10 svog vremena u stanju S 1, 3/10 – sposoban S 2 i 5/10 – sposoban S 3 .
Pravilo za sastavljanje Kolmogorova sustava jednadžbi: u svakoj jednadžbi sustava na lijevoj strani je konačna vjerojatnost danog stanja, pomnožena s ukupnim intenzitetom svih tokova, vodeći iz ove države, A u njegovu pravu dijelovi– zbroj umnožaka intenziteta svih tokova, uključeno u -to stanje, o vjerojatnostima stanja iz kojih ti tokovi dolaze.
Pomoću ovog pravila pišemo sustav jednadžbi za naš primjer :
.
Ovaj sustav od četiri jednadžbe s četiri nepoznanice, čini se, može se u potpunosti riješiti. Ali te jednadžbe su homogene (nemaju slobodan član), pa stoga određuju nepoznanice samo do proizvoljnog faktora. Međutim, možete koristiti uvjet normalizacije: 
i koristiti ga za rješavanje sustava. U tom slučaju jedna (bilo koja) od jednadžbi može se odbaciti (slijedi kao posljedica ostalih).
Nastavak primjera. Neka su intenziteti strujanja jednaki: .
Odbacujemo četvrtu jednadžbu i umjesto nje dodajemo uvjet normalizacije:
.
one. u ograničavajućem, stacionarnom načinu rada sustava S u prosjeku će 40% vremena biti provedeno u stanju S 0 (oba stroja ispravna), 20% - u dobrom stanju S 1 (prvi stroj je na popravku, drugi radi), 27% - u stanju S 2 (drugi stroj je na popravku, prvi radi), 13% - u stanju S 3 (oba stroja su na popravku). Poznavanje ovih konačnih vjerojatnosti može pomoći u procjeni prosječne učinkovitosti sustava i radnog opterećenja organa za popravak.
Neka sustav S sposoban S 0 (potpuno operativan) donosi prihod od 8 konvencionalnih jedinica po jedinici vremena, u mogućnosti S 1 – prihod 3 konvencionalne jedinice, sposoban S 2 – prihod 5 konvencionalnih jedinica, sposoban S 3 – ne stvara prihod. Tada će u ograničavajućem, stacionarnom načinu rada prosječni prihod po jedinici vremena biti jednak: konvencionalnim jedinicama.
Stroj 1 popravlja se u djeliću vremena jednakom: . Stroj 2 popravlja se u djeliću vremena jednakom: . Nastaje problem optimizacije. Iako možemo smanjiti prosječno vrijeme popravka prvog ili drugog stroja (ili oba), to će nas koštati određeni iznos. Pitanje je hoće li povećani prihod povezan s bržim popravcima platiti povećane troškove popravka? Trebat ćete riješiti sustav od četiri jednadžbe s četiri nepoznanice.
Primjeri sustava čekanja (QS): telefonske centrale, servisne radionice, biletarnice, informacijski pultovi, alatni strojevi i drugi tehnološki sustavi, upravljački sustavi fleksibilnih proizvodnih sustava itd.
Svaki QS sastoji se od određenog broja uslužnih jedinica koje se tzv servisni kanali(to su strojevi, transportna kolica, roboti, komunikacijske linije, blagajnici, prodavači itd.). Svaki QS je dizajniran da služi nekoj vrsti tijek aplikacija(zahtjevi) koji dolaze u nekim slučajnim trenucima u vremenu.
Servisiranje zahtjeva traje neko, općenito govoreći, nasumično vrijeme, nakon čega se kanal oslobađa i spreman je primiti sljedeći zahtjev. Nasumična priroda protoka aplikacija i vremena usluge dovodi do činjenice da se u nekim vremenskim razdobljima na ulazu QS-a nakuplja pretjerano velik broj aplikacija (ili stoje u redu čekanja ili ostavljaju QS neposluženim). U ostalim razdobljima sustav će raditi s podopterećenjem ili će biti potpuno u stanju mirovanja.
Proces rada QS-a je slučajan proces s diskretnim stanjima i kontinuiranim vremenom. Stanje QS-a se naglo mijenja kada se dogode određeni događaji (dolazak nove aplikacije, kraj servisa, trenutak kada aplikacija koja je umorna od čekanja napusti red).
Predmet teorije čekanja– konstrukcija matematičkih modela koji povezuju zadane uvjete rada QS-a (broj kanala, njihovu produktivnost, pravila rada, prirodu toka zahtjeva) sa karakteristikama koje nas zanimaju – pokazateljima učinkovitosti QS-a. Ovi pokazatelji opisuju sposobnost CMO-a da se nosi s protokom prijava. Oni mogu biti: prosječan broj aplikacija koje je QS poslužio po jedinici vremena; prosječan broj zauzetih kanala; prosječan broj prijava u redu čekanja; prosječno vrijeme čekanja na uslugu itd.
Matematička analiza rada QS-a znatno je olakšana ako je proces tog rada markovski, tj. tokovi događaja koji prenose sustav iz stanja u stanje su najjednostavniji. U suprotnom, matematički opis procesa postaje vrlo kompliciran i rijetko ga je moguće dovesti do specifičnih analitičkih ovisnosti. U praksi se ne-Markovljevi procesi svode na Markovljeve procese s aproksimacijom. Sljedeći matematički aparat opisuje Markovljeve procese.
Prva podjela (na temelju prisutnosti redova):
1. QS s kvarovima;
2. Red s redom.
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 SMO s redom čekanja aplikacija koja stigne u vrijeme kada su svi kanali zauzeti ne odlazi, već staje u red i čeka priliku da bude poslužena.
QS s redovima čekanja su dodatno podijeljeni u 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 (dužina čekanja u redu i vrijeme usluge su ograničeni);
· QS s prioritetnom uslugom, tj. neke prijave se obrađuju izvan reda, itd.
Osim toga, QS se dijele na otvorene QS i zatvorene QS.
U otvorenom QS-u karakteristike protoka zahtjeva ne ovise o stanju samog QS-a (koliko je kanala zauzeto). U zatvorenom QS– ovisiti. 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.
Klasifikacija SMO-a nije ograničena na gore navedene sorte, ali ovo je dovoljno.
Razmotrimo najjednostavniji QS s čekanjem - jednokanalni sustav (n - 1), koji prima protok zahtjeva s intenzitetom ; intenzitet usluge (tj. u prosjeku će stalno zauzet kanal izdavati servisirane zahtjeve po jedinici (vremena). Zahtjev primljen u vrijeme kada je kanal zauzet nalazi se u redu čekanja i čeka uslugu.
Sustav s ograničenom dužinom čekanja. Pretpostavimo prvo da je broj mjesta u redu ograničen brojem m, tj. ako zahtjev stigne u trenutku kada već postoje m-prijave u redu čekanja, ostavlja sustav neposluženim. U budućnosti, usmjeravanjem m u beskonačnost, dobit ćemo karakteristike jednokanalnog QS-a bez ograničenja na duljinu čekanja.
Označit ćemo stanja QS-a prema broju aplikacija u sustavu (i servisiranih i servisa koji čekaju):
Kanal je besplatan;
Kanal je zauzet, nema čekanja;
Kanal je zauzet, jedan zahtjev je u redu;
Kanal je zauzet, k-1 prijava je u redu;
Kanal je zauzet, prijave su u redu.
GSP je prikazan na sl. 4. Svi intenziteti tokova događaja koji se kreću u sustav duž strelica s lijeva na desno jednaki su , a s desna na lijevo - . Doista, tijek zahtjeva pomiče sustav duž strelica s lijeva na desno (čim stigne zahtjev, sustav prelazi u sljedeće stanje), s desna na lijevo - tok "oslobađanja" zauzetog kanala, koji ima intenzitet (čim se sljedeći zahtjev servisira, kanal će ili postati slobodan ili će se smanjiti broj aplikacija u redu).
Riža. 4. Jednokanalni QS s čekanjem
Prikazano na sl. 4 dijagram je dijagram reprodukcije i smrti. Napišimo izraze za granične vjerojatnosti stanja:
(5)
ili koristeći: :
(6)
Zadnji redak u (6) sadrži geometrijsku progresiju s prvim članom 1 i nazivnikom p, iz čega se dobiva:
(7)
u vezi s čime ograničavajuće vjerojatnosti imaju oblik:
(8).
Izraz (7) vrijedi samo za< 1 (при = 1 она дает неопределенность вида 0/0). Сумма геометрической прогрессии со знаменателем = 1 равна m+2, и в этом случае:
Odredimo karakteristike QS-a: vjerojatnost kvara, relativna propusnost q, apsolutna propusnost A, prosječna duljina reda čekanja, prosječan broj aplikacija povezanih sa sustavom, prosječno vrijeme čekanja u redu čekanja, prosječno vrijeme koje aplikacija provede u QS-u. .
Vjerojatnost neuspjeha. Očito, prijava se odbija samo ako je kanal zauzet i sva t-mjesta u redu su također zauzeta:
(9).
Relativna propusnost:
(10).
Prosječna duljina čekanja. Nađimo prosječni broj aplikacija u redu čekanja kao matematičko očekivanje diskretne slučajne varijable R-broj aplikacija u redu čekanja:
S vjerojatnošću postoji jedna aplikacija u redu čekanja, s vjerojatnošću postoje dvije aplikacije, općenito s vjerojatnošću postoji k-1 aplikacija u redu čekanja itd., od čega:
(11).
Budući da se zbroj u (11) može interpretirati kao derivacija zbroja geometrijske progresije:
Zamjenom ovog izraza u (11) i korištenjem iz (8), konačno dobivamo:
(12).
Prosječan broj aplikacija u sustavu. Zatim dobivamo formulu za prosječan broj -zahtjeva povezanih sa sustavom (i onih koji stoje u redu i servisiranih). Budući da je , gdje je prosječan broj prijava u servisu, a k je poznato, preostaje odrediti . Budući da postoji samo jedan kanal, broj servisiranih zahtjeva može biti 0 (s vjerojatnošću ) ili 1 (s vjerojatnošću 1 - ), od čega:
.
a prosječan broj aplikacija povezanih s QS-om je:
(13).
Prosječno vrijeme čekanja aplikacije u redu čekanja. Označimo to ; ako zahtjev dođe u sustav u nekom trenutku vremena, tada kanal usluge vjerojatno neće biti zauzet i neće morati čekati u redu (vrijeme čekanja je nula). Najvjerojatnije će doći u sustav dok se neki zahtjev opslužuje, ali neće biti u redu ispred nje, a zahtjev će čekati na početak svog servisiranja neko vrijeme (prosječno vrijeme servisiranja jednog zahtjev). Postoji vjerojatnost da će biti još jedna prijava u redu čekanja prije prijave koja se razmatra, a prosječno vrijeme čekanja bit će jednako itd.
Ako je k=m+1, tj. kada novopristigli zahtjev utvrdi da je servisni kanal zauzet i m-zahtjevi u redu čekanja (vjerojatnost za to), onda u ovom slučaju zahtjev ne stoji u redu čekanja (i nije poslužen), tako da je vrijeme čekanja jednako nuli. Prosječno vrijeme čekanja bit će:
ako ovdje zamijenimo izraze za vjerojatnosti (8), dobivamo:
(14).
Ovdje koristimo relacije (11), (12) (derivacija geometrijske progresije), kao i iz (8). Uspoređujući ovaj izraz s (12), primjećujemo da je, drugim riječima, prosječno vrijeme čekanja jednako prosječnom broju prijava u redu čekanja podijeljenom s intenzitetom protoka aplikacija.
(15).
Prosječno vrijeme boravka aplikacije u sustavu. Označimo matematičko očekivanje slučajne varijable kao vrijeme zadržavanja zahtjeva u QS-u, što je zbroj prosječnog vremena čekanja u redu i prosječnog vremena usluge. Ako je opterećenje sustava 100%, očito, inače:
.
Primjer 1. Benzinska postaja (benzinska postaja) je benzinska postaja s jednim servisnim kanalom (jednom pumpom).
Područje na stanici dopušta da više od tri automobila budu u redu za točenje goriva u isto vrijeme (m = 3). Ako već postoje tri automobila u redu, sljedeći automobil koji dolazi na stanicu se ne pridružuje redu. Protok automobila koji dolaze na točenje goriva ima intenzitet = 1 (auto u minuti). Proces punjenja goriva u prosjeku traje 1,25 minuta.
Definirati:
vjerojatnost neuspjeha;
relativni i apsolutni kapacitet benzinskih postaja;
prosječan broj automobila koji čekaju na dolijevanje goriva;
prosječan broj automobila na benzinskoj crpki (uključujući one na servisu);
prosječno vrijeme čekanja automobila u redu;
prosječno vrijeme koje automobil provede na benzinskoj postaji (uključujući servis).
Drugim riječima, prosječno vrijeme čekanja jednako je prosječnom broju prijava u redu čekanja podijeljenom s intenzitetom protoka aplikacija.
Prvo nalazimo smanjeni intenzitet protoka aplikacija: =1/1,25=0,8; =1/0,8=1,25.
Prema formulama (8):
Vjerojatnost kvara je 0,297.
Relativni kapacitet QS: q=1-=0,703.
Apsolutna propusnost QS: A==0,703 automobila u minuti.
Prosječan broj automobila u redu nalazimo pomoću formule (12):
one. Prosječan broj automobila koji čekaju u redu za punjenje benzinske postaje je 1,56.
Dodajući ovoj vrijednosti prosječan broj vozila u servisu:
dobivamo prosječan broj automobila povezanih s benzinskom postajom.
Prosječno vrijeme čekanja automobila u redu prema formuli (15):
Dodajući ovu vrijednost, dobivamo prosječno vrijeme koje automobil provede na benzinskoj postaji:
Sustavi s neograničenim čekanjem. U takvim sustavima vrijednost m nije ograničena i stoga se glavne karakteristike mogu dobiti prelaskom na granicu u prethodno dobivenim izrazima (5), (6) itd.
Imajte na umu da je nazivnik u posljednjoj formuli (6) zbroj beskonačnog broja članova geometrijske progresije. Ovaj zbroj konvergira kada je progresija beskonačno opadajuća, tj. na<1.
Može se dokazati da<1 есть условие, при котором в СМО с ожиданием существует предельный установившийся режим, иначе такого режима не существует, и очередь при будет неограниченно возрастать. Поэтому в дальнейшем здесь предполагается, что <1.
Ako, tada relacije (8) imaju oblik:
(16).
Ako nema ograničenja na duljinu čekanja, svaka aplikacija koja dođe u sustav bit će servisirana, dakle q=1, 
.
Prosječan broj prijava u redu dobivamo iz (12) na:
Prosječan broj aplikacija u sustavu prema formuli (13) pri:
.
Prosječno vrijeme čekanja dobiva se iz formule (14) s:
.
Konačno, prosječno vrijeme koje aplikacija ostaje u QS-u je:
Sustav s ograničenom dužinom čekanja. Razmotrimo kanal QS s čekanjem, koji prima protok zahtjeva s intenzitetom ; intenzitet usluge (za jedan kanal); broj mjesta u redu čekanja.
Stanja sustava numerirana su prema broju zahtjeva povezanih sa sustavom:
bez čekanja:
Svi kanali su besplatni;
Jedan kanal je zauzet, ostali su slobodni;
-kanali su zauzeti, ostali nisu;
Svi kanali su zauzeti, slobodnih kanala nema;
postoji red:
Svi n-kanali su zauzeti; jedna prijava je u redu čekanja;
Svi n-kanali, r-zahtjevi u redu čekanja su zauzeti;
Svi n-kanali, r-zahtjevi u redu čekanja su zauzeti.
GSP je prikazan na sl. 17. Svaka strelica je označena odgovarajućim intenzitetima tokova događaja. Uzduž strelica slijeva nadesno, sustav se prenosi uvijek istim protokom zahtjeva intenzitetom od
Riža. 17. Višekanalni QS s čekanjem
Graf je tipičan za procese reprodukcije i smrti, za koje je prethodno dobiveno rješenje. Napišimo izraze za granične vjerojatnosti stanja koristeći notaciju: (ovdje koristimo izraz za zbroj geometrijske progresije s nazivnikom).
Dakle, pronađene su sve vjerojatnosti stanja.
Odredimo karakteristike učinkovitosti sustava.
Vjerojatnost neuspjeha. Dolazni zahtjev se odbija ako su svi n-kanali i sva m-mjesta u redu čekanja zauzeti:
(18)
Relativna propusnost nadopunjuje vjerojatnost kvara na jedan:
Apsolutna propusnost QS-a:
(19)
Prosječan broj zauzetih kanala. Za QS s odbijenicama podudarao se s prosječnim brojem prijava u sustavu. Za QS s redom čekanja, prosječan broj zauzetih kanala ne podudara se s prosječnim brojem aplikacija u sustavu: potonja vrijednost razlikuje se od prve prosječnim brojem aplikacija u redu čekanja.
Prosječan broj zauzetih kanala označimo sa . Svaki zauzeti kanal poslužuje prosječno A-zahtjeve po jedinici vremena, a QS kao cjelina poslužuje prosječno A-zahtjeve po jedinici vremena. Dijeleći jedno s drugim, dobivamo:
Prosječan broj zahtjeva u redu čekanja može se izravno izračunati kao matematičko očekivanje diskretne slučajne varijable:
(20)
Ovdje se opet (izraz u zagradama) pojavljuje derivacija zbroja geometrijske progresije (vidi gore (11), (12) - (14)), koristeći relaciju za to, dobivamo:
Prosječan broj prijava u sustavu:
Prosječno vrijeme čekanja aplikacije u redu čekanja. Razmotrimo niz situacija koje se razlikuju po stanju u kojem će novopristigli zahtjev pronaći sustav i koliko dugo će morati čekati na uslugu.
Ako zahtjev ne utvrdi da su svi kanali zauzeti, neće uopće morati čekati (odgovarajući članovi u matematičkom očekivanju jednaki su nuli). Ako zahtjev stigne u trenutku kada su svi n-kanali zauzeti i nema reda čekanja, morat će čekati u prosjeku jednako vrijeme (jer "protok oslobađanja" -kanala ima intenzitet ). Ako zahtjev pronađe sve kanale zauzete i jedan zahtjev ispred sebe u redu čekanja, morat će čekati u prosjeku određeno vrijeme (za svaki zahtjev ispred), itd. Ako se zahtjev nađe u redu čekanja od - zahtjeva, morat će čekati u prosjeku neko vrijeme Ako novopristigli zahtjev pronađe m-zahtjeve već u redu čekanja, tada uopće neće čekati (ali neće biti poslužen). Pronalazimo prosječno vrijeme čekanja množenjem svake od ovih vrijednosti s odgovarajućim vjerojatnostima:
(21)
Kao i u slučaju jednokanalnog QS-a s čekanjem, napominjemo da se ovaj izraz razlikuje od izraza za prosječnu duljinu čekanja (20) samo faktorom , tj.
.
Prosječno vrijeme zadržavanja zahtjeva u sustavu, kao i za jednokanalni QS, razlikuje se od prosječnog vremena čekanja za prosječno vrijeme usluge pomnoženo s relativnom propusnošću:
.
Sustavi s neograničenom duljinom čekanja. Razmotrili smo kanal QS s čekanjem, kada u redu čekanja ne može biti više od m-zahtjeva u isto vrijeme.
Kao i do sada, pri analizi sustava bez ograničenja potrebno je uzeti u obzir dobivene relacije za .
Vjerojatnosti stanja dobivamo iz formula prelaskom na limit (at ). Imajte na umu da zbroj odgovarajuće geometrijske progresije konvergira na i divergira na >1. Pod pretpostavkom da<1 и устремив в формулах величину m к бесконечности, получим выражения для предельных вероятностей состояний:
(22)
Vjerojatnost kvara, relativna i apsolutna propusnost. Budući da će svaki zahtjev prije ili kasnije biti servisiran, karakteristike propusnosti QS-a bit će:
Prosječan broj prijava u redu dobiva se iz (20):
,
a prosječno vrijeme čekanja je od (21):
.
Prosječan broj zauzetih kanala, kao i do sada, određuje se kroz apsolutnu propusnost:
.
Prosječan broj aplikacija povezanih s QS-om definiran je kao prosječan broj aplikacija u redu čekanja plus prosječan broj aplikacija u servisu (prosječan broj zauzetih kanala):
Primjer 2. Benzinska postaja s dvije pumpe (n = 2) opslužuje protok automobila intenzitetom =0,8 (auto u minuti). Prosječno vrijeme servisiranja po stroju:
U okolici nema druge benzinske crpke pa kolona automobila ispred crpke može rasti gotovo neograničeno. Pronađite karakteristike QS-a.
Jer<1, очередь не растет безгранично и имеет смысл говорить о предельном стационарном режиме работы СМО. По формулам (22) находим вероятности состояний:
itd.
Prosječan broj zauzetih kanala ćemo pronaći dijeljenjem apsolutnog kapaciteta QS A = = 0,8 s intenzitetom usluge = 0,5:
Vjerojatnost da nema reda na benzinskoj crpki bit će:
Prosječan broj automobila u koloni:
Prosječan broj automobila na benzinskim postajama:
Prosječno vrijeme čekanja u redu:
Prosječno vrijeme koje automobil provede na benzinskoj postaji:
QS s ograničenim vremenom čekanja. Prethodno smo razmatrali sustave s čekanjem ograničenim samo duljinom reda čekanja (brojem m-zahtjeva istovremeno u redu čekanja). U takvom QS-u, aplikacija koja je narasla u redu čekanja ne napušta ga dok ne čeka uslugu. U praksi postoje i druge vrste QS-a u kojima aplikacija nakon određenog vremena čekanja može izaći iz reda čekanja (tzv. “nestrpljive” aplikacije).
Razmotrimo QS ovog tipa, pod pretpostavkom da je ograničenje vremena čekanja slučajna varijabla.
Pretpostavimo da postoji n-kanalni QS koji čeka u kojem je broj mjesta u redu čekanja neograničen, ali je vrijeme koje zahtjev ostaje u redu čekanja neka slučajna varijabla sa srednjom vrijednošću, stoga je svaki zahtjev u redu čekanja podložna svojevrsnom Poissonovom "tijeku brige" s intenzitetom:
Ako je ovaj tok Poissonov, tada će proces koji se odvija u QS-u biti Markovijev. Nađimo vjerojatnosti stanja za to. Numeriranje stanja sustava povezano je s brojem aplikacija u sustavu - i onih koje se poslužuju i onih koje stoje u redu:
bez čekanja:
Svi kanali su besplatni;
Jedan kanal je zauzet;
Dva kanala su zauzeta;
Svi n-kanali su zauzeti;
postoji red:
Svih n-kanala je zauzeto, jedan zahtjev je u redu;
Svi n-kanali su zauzeti, r-zahtjevi su u redu, itd.
Graf stanja i prijelaza sustava prikazan je na sl. 23.
Riža. 23. QS s ograničenim vremenom čekanja
Označimo ovaj graf kao i prije; sve strelice koje vode slijeva nadesno pokazat će intenzitet toka prijava. Za stanja bez reda, strelice koje vode od njih s desna na lijevo će, kao i prije, označavati ukupni intenzitet protoka koji opslužuje sve zauzete kanale. Što se tiče stanja s redom čekanja, strelice koje vode od njih s desna na lijevo imat će ukupni intenzitet toka usluge svih n-kanala plus odgovarajući intenzitet toka odlazaka iz reda čekanja. Ako u redu čekanja ima r-prijava, tada će ukupni intenzitet toka odlazaka biti jednak .
Kao što se može vidjeti iz grafikona, postoji obrazac reprodukcije i smrti; koristeći općenite izraze za granične vjerojatnosti stanja u ovoj shemi (koristeći skraćene oznake, pišemo:
(24)
Napomenimo neke značajke QS-a s ograničenim čekanjem u usporedbi s prethodno razmatranim QS-om sa zahtjevima "pacijenta".
Ako duljina reda nije ograničena i zahtjevi su "strpljivi" (ne napuštaju red), tada stacionarni granični režim postoji samo u slučaju (kod odgovarajuće beskonačne geometrijske progresije divergira, što fizički odgovara neograničenom rastu) reda u ).
Naprotiv, u QS-u s “nestrpljivim” zahtjevima koji prije ili kasnije napuštaju red čekanja, uvijek se postiže uspostavljeni režim usluge na, bez obzira na smanjeni intenzitet protoka zahtjeva. To slijedi iz činjenice da niz za u nazivniku formule (24) konvergira za sve pozitivne vrijednosti i .
Za QS s "nestrpljivim" zahtjevima, koncept "vjerojatnosti neuspjeha" nema smisla - svaki zahtjev dolazi na red, ali možda neće čekati uslugu, odlazeći prije vremena.
Relativna propusnost, prosječan broj zahtjeva u redu. Relativni kapacitet q takvog QS-a može se izračunati na sljedeći način. Očito će sve prijave biti servisirane, osim onih koje napuste red prije roka. Izračunajmo prosječan broj prijava koje rano napuste red čekanja. Da bismo to učinili, izračunavamo prosječan broj aplikacija u redu čekanja:
Svaka od ovih aplikacija podliježe "tijeku odlazaka" intenzitetom od . To znači da će od prosječnog broja -aplikacija u redu čekanja, u prosjeku, -aplikacije otići bez čekanja na uslugu, -aplikacije po jedinici vremena i ukupno po jedinici vremena, u prosjeku -aplikacije će biti opslužene. Relativni kapacitet QS-a bit će:
Još uvijek dobivamo prosječan broj zauzetih kanala dijeljenjem apsolutne propusnosti A s:
(26)
Prosječan broj prijava u redu. Relacija (26) omogućuje izračunavanje prosječnog broja aplikacija u redu čekanja bez zbrajanja beskonačnog niza (25). Iz (26) dobivamo:
a prosječni broj zauzetih kanala uključenih u ovu formulu može se pronaći kao matematičko očekivanje slučajne varijable Z, uzimajući vrijednosti 0, 1, 2,..., n s vjerojatnostima,:
Zaključno, napominjemo da ako u formulama (24) idemo do granice na (ili, što je isto, na ), tada će se dobiti formule (22), tj. "nestrpljive" aplikacije će postati "strpljive".
Do sada smo razmatrali sustave u kojima dolazni tok nije ni na koji način povezan s odlaznim tokom. Takvi sustavi nazivaju se otvoreni krug. U nekim slučajevima, servisirani zahtjevi se ponovno primaju na ulaz nakon kašnjenja. Takvi QS-ovi se nazivaju zatvorenim. Klinika koja opslužuje određeno područje, tim radnika dodijeljen grupi strojeva, primjeri su zatvorenih sustava.
U zatvorenom QS-u kruži isti konačni broj potencijalnih zahtjeva. Dok se potencijalni zahtjev ne realizira kao zahtjev za uslugu, smatra se da je u bloku kašnjenja. U trenutku implementacije ulazi u sam sustav. Na primjer, radnici održavaju grupu strojeva. Svaki je stroj potencijalni zahtjev koji se u trenutku kvara pretvara u stvarni. Dok stroj radi, nalazi se u bloku odgode, a od trenutka kvara do završetka popravka nalazi se u samom sustavu. Svaki radnik je uslužni kanal.
Neka n- broj uslužnih kanala, s- broj potencijalnih prijava, n <s , - intenzitet protoka zahtjeva za svaki potencijalni zahtjev, μ - intenzitet usluge:
Vjerojatnost zastoja sustava određena je formulom
R
0
= 
.
Konačne vjerojatnosti stanja sustava:
Pk= na k
Kroz ove vjerojatnosti izražava se prosječan broj zauzetih kanala
=P 1 + 2P 2 +…+n(P n +P n+ 1 +…+P s) ili
=P 1 + 2P 2 +…+(n- 1)P n- 1 +n( 1-P 0 -P 1 -…-P n-1 ).
Koristeći ovo nalazimo apsolutnu propusnost sustava:
kao i prosječan broj prijava u sustavu
M=s- =s- .
Primjer 1. Ulaz trokanalnog QS-a s kvarovima prima tok zahtjeva s intenzitetom =4 zahtjeva u minuti, vrijeme servisiranja zahtjeva po jednom kanalu t obs =1/μ =0,5 min. Sa stajališta kapaciteta QS-a, je li isplativo forsirati sva tri kanala na servisne zahtjeve odjednom, a prosječno vrijeme servisa smanjiti tri puta? Kako će to utjecati na prosječno vrijeme koje aplikacija provede u CMO-u?
Otopina. Pronalazimo vjerojatnost zastoja trokanalnog QS-a pomoću formule
ρ = /μ =4/2=2, n=3,
P 0 = = = 0,158.
Vjerojatnost kvara određena je formulom:
P otvoreno = P n ==
P otvoreno = 0,21.
Relativna propusnost sustava:
R obsl = 1-R otvoreno 1-0,21=0,79.
Apsolutna propusnost sustava:
A= P obsl 3,16.
Prosječan broj zauzetih kanala određuje se formulom:
1,58, udio kanala zauzet servisiranjem,
q = 0,53.
Prosječno vrijeme zadržavanja aplikacije u QS-u nalazi se kao vjerojatnost da je aplikacija prihvaćena za uslugu, pomnožena s prosječnim vremenom usluge: t SMO 0,395 min.
Kombinirajući sva tri kanala u jedan, dobivamo jednokanalni sustav s parametrima μ= 6, ρ= 2/3. Za jednokanalni sustav, vjerojatnost zastoja je:
R 0 = = =0,6,
vjerojatnost kvara:
P otvoreno =ρ P 0 = = 0,4,
relativna propusnost:
R obsl = 1-R otvoreno =0,6,
apsolutna propusnost:
A=P ops =2,4.
t SMO =P obsl= =0,1 min.
Kao rezultat kombiniranja kanala u jedan, propusnost sustava se smanjila jer se povećala vjerojatnost kvara. Smanjilo se prosječno vrijeme koje aplikacija provede u sustavu.
Primjer 2. Ulaz trokanalnog QS-a s neograničenim redom čekanja prima protok zahtjeva s intenzitetom =4 aplikacije po satu, prosječno vrijeme za servisiranje jedne aplikacije t=1/μ=0,5 h. Pronađite pokazatelje performansi sustava.
Za sustav koji se razmatra n =3, =4, μ=1/0,5=2, ρ= /μ=2, ρ/ n =2/3<1. Определяем вероятность простоя по формуле:
P= 
.
P
0
= 
=1/9.
Prosječan broj prijava u redu čekanja nalazimo pomoću formule:
L
=
.
L = = .
Prosječno vrijeme čekanja aplikacije u redu čekanja izračunavamo pomoću formule:
t= = 0,22 sata.
Prosječno vrijeme koje aplikacija ostaje u sustavu:
T=t+ 0,22+0,5=0,72.
Primjer 3. U frizerskom salonu rade 3 frizera, au čekaonici su 3 stolice. Protok klijenata ima intenzitet =12 klijenata na sat. Prosječno vrijeme usluge t obsl =20 min. Odrediti relativnu i apsolutnu propusnost sustava, prosječan broj zauzetih stolica, prosječnu dužinu reda, prosječno vrijeme koje klijent provede u frizerskom salonu.
Za ovaj zadatak n =3, Zahtjev primljen kada je kanal zauzet nalazi se u redu i čeka uslugu. Pretpostavit ćemo da je veličina reda ograničena i da ne može primiti više od =3, =12, μ =3, ρ =4, ρ/n=4/3. Vjerojatnost prekida rada određena je formulom:
R
0
=
.
P
0
= 
0,012.
Vjerojatnost odbijanja usluge određena je formulom
P otvoreno =P n+m = .
P otvoriti =Pn + m 0,307.
Relativni kapacitet sustava, tj. vjerojatnost usluge:
P obsl =1-P otvoriti 1-0,307=0,693.
Apsolutna propusnost:
A= P obsl 12 .
Prosječan broj zauzetih kanala:
.
Prosječna duljina čekanja određuje se formulom:
L
=
L= 
1,56.
Prosječno vrijeme čekanja na uslugu u redu čekanja:
t= h.
Prosječan broj prijava CMO-u:
M=L + .
Prosječno vrijeme koje aplikacija ostaje u CMO-u:
T=M/ 0,36 sati
Primjer 4. Radnik upravlja sa 4 stroja. Svaki stroj otkazuje s intenzitetom =0,5 kvarova po satu, prosječno vrijeme popravka t rem=1/μ=0,8 h Odrediti propusnost sustava.
Ovaj problem razmatra zatvoreni QS, μ =1,25, ρ=0,5/1,25=0,4. Vjerojatnost prekida rada radnika određena je formulom:
R
0
=
.
P
0
= 
.
Vjerojatnost zapošljavanja radnika R zan = 1-P 0 . A=( 1-P 0 )μ =0,85μ strojeva po satu.
Zadatak:
Dva radnika upravljaju grupom od četiri stroja. Zaustavljanje radnog stroja događa se u prosjeku nakon 30 minuta. Prosječno vrijeme postavljanja je 15 minuta. Vrijeme rada i podešavanja raspoređeno je prema eksponencijalnom zakonu.
Odredi prosječni udio slobodnog vremena za svakog radnika i prosječno vrijeme rada stroja.
Pronađite iste karakteristike za sustav u kojem:
a) svakom radniku su dodijeljena dva stroja;
b) dva radnika uvijek zajedno opslužuju stroj i to dvostrukim intenzitetom;
c) jedini neispravni stroj opslužuju oba radnika odjednom (dvostrukim intenzitetom), a kada se pojavi barem još jedan neispravan stroj, počinju raditi odvojeno, svaki opslužujući jedan stroj (najprije sustav opišite procesima smrt i rođenje).
Otopina:
Moguća su sljedeća stanja sustava S:
S 0 – svi strojevi rade;
S 1 – 1 stroj je na popravku, ostali su u ispravnom stanju;
S 2 – 2 stroj je na popravku, ostali su ispravni;
S 3 – 3 stroj je na popravku, ostali su ispravni;
S 4 – 4 stroj je na popravku, ostali su u ispravnom stanju;
S 5 – (1, 2) strojevi su na popravku, ostali su u ispravnom stanju;
S 6 – (1, 3) strojevi su na popravku, ostali su u ispravnom stanju;
S 7 – (1, 4) strojevi su na popravku, ostali su u ispravnom stanju;
S 8 – (2, 3) strojevi su na popravku, ostali su u ispravnom stanju;
S 9 – (2, 4) strojevi su na popravku, ostali su u funkciji;
S 10 – (3, 4) strojevi su na popravku, ostali su u ispravnom stanju;
S 11 – (1, 2, 3) strojevi su na popravku, 4 stroj radi;
S 12 – (1, 2, 4) strojevi su na popravku, 3 stroj radi;
S 13 – (1, 3, 4) strojevi su na popravku, stroj 2 radi;
S 14 – (2, 3, 4) strojevi su na popravku, 1 stroj radi;
S 15 – svi strojevi su popravljeni.
Grafikon stanja sustava...
Ovaj sustav S je primjer zatvorenog sustava, budući da je svaki stroj potencijalni zahtjev koji se pretvara u stvarni u trenutku njegovog kvara. Dok stroj radi, nalazi se u bloku odgode, a od trenutka kvara do završetka popravka nalazi se u samom sustavu. Svaki radnik je uslužni kanal.
Ako je radnik zauzet, postavlja μ-strojeve po jedinici vremena, kapacitet sustava:
Odgovor:
Prosječni udio slobodnog vremena za svakog radnika je ≈ 0,09.
Prosječno vrijeme rada stroja ≈ 3,64.
a) Svaki radnik ima dva stroja.
Vjerojatnost prekida rada radnika određena je formulom:
Vjerojatnost zapošljavanja radnika:
Ako je radnik zauzet, postavlja μ-strojeve po jedinici vremena, kapacitet sustava:
Odgovor:
Prosječni udio slobodnog vremena za svakog radnika je ≈ 0,62.
Prosječno vrijeme rada stroja ≈ 1,52.
b) Dva radnika uvijek opslužuju stroj zajedno i to dvostrukim intenzitetom.
c) Jedini neispravni stroj opslužuju oba radnika odjednom (dvostrukim intenzitetom), a kada se pojavi barem još jedan neispravan stroj, počinju raditi odvojeno, svaki opslužujući jedan stroj (najprije sustav opišite procesima smrt i rođenje).
Usporedba 5 odgovora:
Najučinkovitiji način organiziranja radnika za strojevima bit će početna verzija zadatka.
Gore su razmatrani primjeri najjednostavnijih sustava čekanja (QS). Izraz "praživotinje" ne znači "elementarni". Matematički modeli ovih sustava primjenjivi su i uspješno se koriste u praktičnim proračunima.
Mogućnost primjene teorije odlučivanja u sustavima čekanja određuju sljedeći čimbenici:
1. Broj aplikacija u sustavu (koji se smatra QS-om) mora biti prilično velik (masovno).
2. Sve prijave zaprimljene na ulazu QS-a moraju biti iste vrste.
3. Za izračunavanje pomoću formula potrebno je poznavati zakonitosti koje određuju zaprimanje zahtjeva i intenzitet njihove obrade. Štoviše, tokovi reda moraju biti Poissonovi.
4. Struktura QS-a, tj. skup ulaznih zahtjeva i slijed obrade zahtjeva moraju biti strogo fiksirani.
5. Potrebno je subjekte isključiti iz sustava ili ih opisati kao zahtjeve s konstantnim intenzitetom obrade.
Gore navedenim ograničenjima možemo dodati još jedno koje ima snažan utjecaj na dimenziju i složenost matematičkog modela.
6. Broj korištenih prioriteta treba biti minimalan. Prioriteti aplikacija moraju biti konstantni, tj. ne mogu se mijenjati tijekom obrade unutar QS-a.
Tijekom rada postignut je glavni cilj - proučavano je glavno gradivo „QS s ograničenim vremenom čekanja“ i „Zatvorene QS“ koje je postavio nastavnik akademske discipline. Također smo se upoznali s primjenom stečenog znanja u praksi, tj. konsolidirao pređeno gradivo.
1) http://www.5ballov.ru.
2) http://www.studentport.ru.
3) http://vse5ki.ru.
4) http://revolucija..
5) Fomin G.P. Matematičke metode i modeli u komercijalnim djelatnostima. M: Financije i statistika, 2001.
6) Gmurman V.E. Teorija vjerojatnosti i matematička statistika. M: Viša škola, 2001.
7) Sovetov B.A., Yakovlev S.A. Modeliranje sustava. M: Viša škola, 1985.
8) Lifshits A.L. Statističko modeliranje QS-a. M., 1978.
9) Ventzel E.S. Operacijska istraživanja. M: Nauka, 1980.
10) Ventzel E.S., Ovcharov L.A. Teorija vjerojatnosti i njezine inženjerske primjene. M: Nauka, 1988.
Operacije ili učinkovitost sustava čekanja su kako slijedi.Za QS s kvarovima:
Za SMO s neograničenim čekanjem i apsolutna i relativna propusnost gube smisao, jer će svaki dolazni zahtjev prije ili kasnije biti servisiran. Za takav QS važni pokazatelji su:
Za Mješoviti tip QS koriste se obje skupine pokazatelja: i relativni i apsolutna propusnost i karakteristike očekivanja.
Ovisno o namjeni operacije čekanja, bilo koji od zadanih indikatora (ili skup indikatora) može se odabrati kao kriterij učinkovitosti.
Analitički model QS je skup jednadžbi ili formula koje omogućuju određivanje vjerojatnosti stanja sustava tijekom njegovog rada i izračunavanje pokazatelja performansi na temelju poznatih karakteristika dolaznog protoka i uslužnih kanala.
Ne postoji opći analitički model za proizvoljan QS. Analitički modeli razvijeni su za ograničeni broj posebnih slučajeva QS-a. Analitički modeli koji više ili manje točno odražavaju stvarne sustave obično su složeni i teško ih je vizualizirati.
Analitičko modeliranje QS-a uvelike je olakšano ako su procesi koji se odvijaju u QS-u Markovljevi (tokovi zahtjeva su jednostavni, vremena usluge raspoređena su eksponencijalno). Pritom se svi procesi u QS-u mogu opisati običnim diferencijalnim jednadžbama, au graničnom slučaju, za stacionarna stanja, linearnim algebarskim jednadžbama i njihovim rješavanjem odrediti odabrane pokazatelje učinkovitosti.
Pogledajmo primjere nekih QS-ova.
2.5.1. Višekanalni QS s kvarovima
Primjer 2.5. Tri prometna inspektora provjeravaju putne listove vozača kamiona. Ako je barem jedan inspektor slobodan, kamion koji prolazi se zaustavlja. Ako su svi inspektori zauzeti, kamion prolazi bez zaustavljanja. Protok kamiona je jednostavan, vrijeme provjere je slučajno s eksponencijalnom distribucijom.
Ova situacija može se modelirati trokanalnim QS-om s kvarovima (bez čekanja). Sustav je otvorenog tipa, s homogenim zahtjevima, jednofazni, s apsolutno pouzdanim kanalima.
Opis stanja:
Svi inspektori su besplatni;
Jedan inspektor ima posla;
Dva inspektora su zauzeta;
Tri inspektora su zauzeta.
Grafikon stanja sustava prikazan je na sl. 2.11.
Riža. 2.11.
Na grafikonu: - intenzitet protoka kamiona; - intenzitet provjere dokumenata od strane jednog prometnog inspektora.
Simulacija se provodi kako bi se odredio udio vozila koji neće biti testiran.
Otopina
Traženi dio vjerojatnosti je vjerojatnost zaposlenja sva tri inspektora. Budući da grafikon stanja predstavlja tipičnu shemu "smrti i reprodukcije", pronaći ćemo pomoću ovisnosti (2.2).
Može se okarakterizirati propusni kapacitet ovog prometnog inspektorata relativna propusnost:
Primjer 2.6. Za primanje i obradu dojava izvidničke skupine u obavještajnom odjelu zdruga određena je skupina od tri časnika. Očekivani intenzitet protoka dojava je 15 dojava na sat. Prosječno vrijeme obrade jedne prijave od strane jednog službenika je . Svaki časnik može primati izvješća od bilo koje izvidničke grupe. Otpušteni službenik obrađuje posljednju od primljenih prijava. Dolazna izvješća moraju biti obrađena s vjerojatnošću od najmanje 95%.
Utvrdite je li dodijeljeni tim od tri službenika dovoljan za izvršenje dodijeljene zadaće.
Otopina
Skupina časnika djeluje kao CMO s kvarovima, koji se sastoji od tri kanala.
Tijek izvješća s intenzitetom 
može se smatrati najjednostavnijim, budući da je skup nekoliko izviđačkih skupina. Intenzitet usluge 
. Zakon raspodjele je nepoznat, ali je nevažan, jer je pokazano da za sustave s kvarovima može biti proizvoljan.
Opis stanja i grafikon stanja QS-a bit će slični onima danima u primjeru 2.5.
Budući da je grafikon stanja shema "smrti i reprodukcije", za njega postoje gotovi izrazi za ograničavajuće vjerojatnosti stanja:
Stav se zove s obzirom na intenzitet protoka prijava. Njegovo fizičko značenje je sljedeće: vrijednost predstavlja prosječan broj zahtjeva koji stižu u QS tijekom prosječnog vremena servisiranja jednog zahtjeva.
U primjeru 
.
U razmatranom QS-u kvar nastaje kada su sva tri kanala zauzeta, tj. Zatim:
Jer vjerojatnost neuspjeha u obradi izvješća je više od 34% (), tada je potrebno povećati osoblje grupe. Udvostručimo sastav grupe, odnosno CMO će sada imati šest kanala i izračunajmo:
Tako će samo grupa od šest službenika s 95% vjerojatnosti moći obraditi pristigla izvješća.
2.5.2. Višekanalni QS s čekanjem
Primjer 2.7. Na dionici riječnog prijelaza nalazi se 15 sličnih prijelaznih objekata. Protok opreme koja dolazi na prijelaz je u prosjeku 1 jedinica/min, prosječno vrijeme prelaska jedne jedinice opreme je 10 minuta (uključujući povratak vozila na prijelaz).
Procijenite glavne karakteristike prijelaza, uključujući vjerojatnost neposrednog prelaska odmah po dolasku jedinice opreme.
Otopina
Apsolutna propusnost, odnosno sve što se približi prijelazu praktički se odmah prelazi.
Prosječan broj operativnih prijelaza:
Stope iskorištenosti i zastoja trajekta:
Također je razvijen program za rješavanje primjera. Pretpostavlja se da su vremenski intervali za dolazak opreme na prijelaz i vrijeme prelaska raspoređeni prema eksponencijalnom zakonu.
Stope iskorištenja križanja nakon 50 vožnji gotovo su iste: 
.
Maksimalna duljina reda je 15 jedinica, prosječno vrijeme provedeno u redu je oko 10 minuta.
Namjena usluge QS. Online kalkulator dizajniran je za izračun sljedećih pokazatelja jednokanalnog QS-a:- vjerojatnost kvara kanala, vjerojatnost slobodnog kanala, apsolutna propusnost;
- relativna propusnost, prosječno vrijeme usluge, prosječno vrijeme prekida kanala.
upute. Za rješavanje takvih problema online odaberite QS model. Navedite intenzitet protoka potražnje λ I intenzitet toka usluge μ. Za jednokanalni QS s ograničenom duljinom čekanja možete odrediti duljina reda m, a za jednokanalni QS s neograničenim redom čekanja - broj aplikacija u redu čekanja (kako bi se izračunala vjerojatnost da će te aplikacije biti u redu čekanja). pogledajte primjer rješenja. . Dobiveno rješenje sprema se u Word datoteku.
Klasifikacija jednokanalnih sustava čekanja
Primjer br. 1. Auto benzinska postaja ima jedan benzinska postaja. Pretpostavlja se da najjednostavniji tok automobila ulazi u stanicu intenzitetom λ=11 vagona/sat. Vrijeme servisiranja zahtjeva je slučajna varijabla koja se pridržava eksponencijalnog zakona s parametrom μ=14 vozila/sat. Odredite prosječan broj automobila na stanici.
Primjer br. 2. Postoji točka za obavljanje preventivnog pregleda strojeva s jednom preglednom grupom. U prosjeku je potrebno 0,4 sata za pregled i utvrđivanje kvarova na svakom stroju. Dnevno se u prosjeku na pregled primi 328 automobila. Tokovi zahtjeva i usluga su najjednostavniji. Ako automobil koji dolazi na točku pregleda ne nađe niti jedan slobodan kanal, ostavlja točku pregleda neservisiranu. Odrediti granične vjerojatnosti uvjeta i karakteristika održavanja točke preventivnog pregleda.
Otopina. Ovdje je α = 328/24 ≈ = 13,67, t = 0,4. Ove podatke potrebno je unijeti u kalkulator.
U praksi su jednokanalni QS-ovi s redom (liječnik koji poslužuje pacijente, procesor koji izvršava strojne naredbe) vrlo česti. Stoga je potrebno detaljnije razmotriti jednokanalni QS s redom čekanja.
Neka postoji jednokanalni QS s redom na koji nema ograničenja (ni na duljinu reda, ni na vrijeme čekanja). Ovaj QS prima tok aplikacija s intenzitetom l; tok usluge ima intenzitet m obrnut prosječnom vremenu usluge zahtjeva t oko. Potrebno je pronaći konačne vjerojatnosti stanja QS-a, kao i karakteristike njegove učinkovitosti:
L SUST– prosječan broj zahtjeva u sustavu;
W SUST– prosječno vrijeme zadržavanja zahtjeva u sustavu;
L JAKO– prosječan broj prijava u redu čekanja;
W JAKO– prosječno vrijeme zadržavanja aplikacije u redu čekanja;
P ZAN- vjerojatnost da je kanal zauzet (stupanj opterećenja kanala).
Što se tiče apsolutne propusnosti A i relativne Q, nema potrebe izračunavati ih: zbog činjenice da je red čekanja neograničen, svaki zahtjev će prije ili kasnije biti servisiran, dakle, iz istog razloga.
Otopina. Stanje sustava će se, kao i do sada, numerirati prema broju prijava u QS-u:
-S 0 – kanal je slobodan;
-S 1 – kanal je zauzet (služi zahtjev), nema čekanja;
-S 2 – kanal je zauzet, jedan zahtjev je u redu;
-S k – kanal je zauzet, k-1 prijave su u redu.
Teoretski, broj stanja je neograničen (beskonačan). Formule za konačne vjerojatnosti u shemi smrti i reprodukcije izvedene su samo za slučaj konačnog broja stanja, ali ćemo pretpostaviti da ćemo ih koristiti za beskonačan broj stanja. Tada će broj članova u formuli biti beskonačan. Dobivamo izraz za p o:
Niz u formuli (17) je geometrijska progresija. Znamo da niz konvergira - to je beskonačno padajuća progresija s nazivnikom r. Kada niz divergira (što je neizravan, iako ne strog, dokaz da konačne vjerojatnosti stanja p o, str 1, …, p k,...postoje samo kada ). Zatim:
Nađimo prosječan broj prijava CMO-u L SUST. Slučajna varijabla Z - broj aplikacija u sustavu - ima moguće vrijednosti 0, 1, 2, ..., k, ... s vjerojatnostima p o, str 1, …, p k,... Njegovo matematičko očekivanje je jednako:
Koristeći Littleovu formulu (9), nalazimo prosječno vrijeme koje zahtjev ostaje u sustavu:
Pronađimo prosječan broj prijava u redu. Rezonirat ćemo ovako: broj aplikacija u redu čekanja jednak je broju aplikacija u sustavu minus broj aplikacija u servisu. To znači (prema pravilu zbrajanja matematičkih očekivanja) prosječan broj prijava u redu L JAKO jednak prosječnom broju aplikacija u sustavu L SUST minus prosječni broj aplikacija u servisu. Broj zahtjeva u servisu može biti nula (ako je kanal slobodan) ili jedan (ako je zauzet). Matematičko očekivanje takve slučajne varijable jednako je vjerojatnosti da je kanal zauzet P ZAN. Očito je da:
Prema tome, prosječan broj zahtjeva u servisu je:
Pomoću Littleove formule (9) nalazimo prosječno vrijeme koje aplikacija ostaje u redu čekanja.
Učitavanje...
