TEORIJA REDOVANJA

Uvod

Teorija redova čekanja je važna grana sistemske analize i istraživanja operacija. Bogat je raznim aplikacijama: od zadataka. vezano za operaciju telefonske mreže naučnoj organizaciji proizvodnje. Ova teorija se koristi tamo gdje postoje pozivi i kupci, signali i proizvodi masovne proizvodnje, kao i gdje se proizvodi servisiraju, obrađuju, prenose.

Ideje i metode teorije queuing(TMT) postaju sve rasprostranjeniji. Mnogi zadaci tehnologije, ekonomije, vojnih poslova, prirodnih nauka mogu se postaviti i riješiti u terminima TMT-a.

Svoju pojavu TMO duguje, prije svega, primijenjenim pitanjima telefonije, u kojoj, zbog veliki broj nezavisni ili slabo zavisni izvori (pretplatnici telefonskih centrala) tokovi aplikacija (poziva) imaju izražen slučajan karakter. Slučajne fluktuacije (fluktuacije) oko određenog prosjeka u ovom slučaju nisu rezultat nekog odstupanja od norme, već obrazac svojstven cijelom procesu. S druge strane, stabilnost rada telefonskih centrala, mogućnost dobijanja dobrih statističkih podataka stvorile su pretpostavke za identifikaciju osnovnih karakteristika svojstvenih ovom uslužnom procesu.

Po prvi put na ovo je skrenuo pažnju i sproveo istraživanje Dane A.K. Erlang. Njegovi glavni radovi u ovoj oblasti datiraju iz 1908-1921. Od tog vremena, interesovanje za probleme koje je izneo Erlang je enormno poraslo. Godine 1927 - 1928 pojavila su se djela Moline i Fraye, kasnije 1930 - 1932 - zanimljiva djela Pollacheka, A.N. Kolmogorova, A.Ya. Khinčin.

Mora se reći da su prvi zadaci TMT-a bili prilično jednostavni i omogućavali su dobijanje konačnih analitičkih zavisnosti. O, razvoj je išao kako na liniji povećanja obima primjene TMT-a, tako i na liniji usložnjavanja zadataka koji su pred njim. Ispostavilo se da se problemi telefonskog tipa javljaju u širokom spektru oblasti istraživanja: u prirodnim naukama. u tehnologiji, u transportu, u vojnim poslovima, u organizaciji proizvodnje itd.

23. Sistemi čekanja

U mnogim područjima ljudske praktične aktivnosti suočavamo se s potrebom da ostanemo u stanju očekivanja. Slične situacije nastaju u redovima na blagajnama, na velikim aerodromima, kada službenici aviona čekaju dozvolu za poletanje ili slijetanje, na telefonskim centralama čekajući puštanje pretplatničke linije, u servisima koji čekaju popravku alatnih mašina i opreme , u magacinima nabavnih i marketinških organizacija u čekanju na istovar ili utovar vozila. U svim ovim slučajevima radi se o masovnom karakteru i usluzi. Teorija čekanja se bavi proučavanjem takvih situacija.

Teorija čekanja- oblast primenjene matematike koja se bavi analizom procesa u proizvodnji, uslugama, sistemima upravljanja u kojima se homogeni događaji ponavljaju više puta, na primer, u preduzećima za usluge potrošača; u sistemima za prijem, obradu i prenošenje informacija; automatske proizvodne linije itd.

Predmet teorije čekanja je uspostavljanje odnosa između prirode toka aplikacija, broja servisnih kanala, performansi pojedinačnog kanala i efikasne usluge kako bi se pronašli najbolji načini za kontrolu ovih procesa.

23.1. Koncept smo

U teoriji sistema čekanja (QS), servisirani objekt se naziva zahtjevom. U opštem slučaju, pod zahtevom se obično podrazumeva zahtev da se zadovolji neka potreba, na primer, razgovor sa pretplatnikom, sletanje aviona, kupovina karte, prijem materijala u skladište.

Sredstva koja ispunjavaju zahtjeve se nazivaju uslužni uređaji ili servisni kanali . Na primjer, to uključuje telefonske kanale, sletne trake, majstore popravke, prodavače karata, punktove za utovar i istovar u bazama i skladištima.

Zove se skup sličnih servisnih uređaja sistem čekanja . Takvi sistemi mogu biti telefonske centrale, aerodromi, biletarnice, servisne radionice, skladišta i baze nabavnih i marketinških organizacija itd.

Osnovni zadatak QS teorije je proučavanje načina rada uslužnog sistema i proučavanje pojava koje se javljaju u procesu usluge. Dakle, jedna od karakteristika sistema usluživanja je vrijeme provedeno od strane zahtjeva u redu čekanja. Očigledno, ovo vrijeme se može smanjiti povećanjem broja servisnih uređaja. Međutim, svaki dodatni uređaj zahtijeva određene materijalne troškove, dok se vrijeme mirovanja servisnog uređaja povećava zbog nepostojanja zahtjeva za održavanjem, što je također negativna pojava. Posljedično, u teoriji QS-a javljaju se problemi optimizacije: kako postići određeni nivo usluge (maksimalno smanjenje čekanja ili gubitak zahtjeva) sa minimalni trošak povezano sa prekidom rada servisnih uređaja.

Izvor. Izvor se definira kao uređaj ili skup iz kojeg zahtjevi ulaze u sistem za servis. Izvor se naziva beskonačan ili konačan, ovisno o tome da li sadrži beskonačan ili konačan broj zahtjeva. Uvijek ćemo pretpostaviti da su zahtjevi za stvaranje izvora neiscrpni. Na primjer, iako postoji konačan broj pretplatnika neke telefonske centrale, pretpostavljamo da oni čine beskonačan izvor.

dolazni tok. Zahtjevi koji dolaze od izvora do usluge formiraju dolazni tok. Sam zahtjev se može posmatrati kao zahtjev za zadovoljenjem neke potrebe. Postoji mnogo primjera dolaznih tokova. Ovo je tok informacija primljenih za obradu u kompjuteru; protok aplikacija za ATS; protok klijenata koji dolaze u studio i pacijenata u polikliniku, protok brodova koji pristižu u luku; neprijateljski avioni i projektili koji lete na metu, itd.

Servisni sistem. Servisni sistem je skup tehnička sredstva ili proizvodno osoblje (razne instalacije, uređaji, uređaji, tuneli, piste, komunikacione linije, prodavci, timovi radnika ili zaposlenih, blagajnici, itd.) koji obavljaju uslužne funkcije. Sve navedeno, kao što je već spomenuto, objedinjuje jedan naziv “servisni kanal” (servisni uređaj). Sastav sistema je određen brojem kanala (uređaja, linija). Prema broju kanala sistemi se mogu podijeliti na jednokanalne i višekanalne.

Odlazni tok. Odliv je tok zahtjeva koji napuštaju sistem nakon što su servisirani. Ovo može uključivati zahtjeve koji su napustili sistem bez servisiranja.

Dolazni tok, funkcionisanje uslužnog sistema kao rezultat servisiranja, odlazni tok podliježu kvantitativnom opisu. Da bi se izvršila matematička studija procesa čekanja, potrebno je u potpunosti definisati sistem čekanja. To obično znači:

- podešavanje ulaznog toka. Ovdje imamo u vidu kako prosječan intenzitet prijema zahtjeva, tako i statistički model njihovog prijema (tj. zakon raspodjele momenata prijema zahtjeva u sistemu);

- postavljanje mehanizma servisa. To znači navođenje kada je usluga dozvoljena, koliko zahtjeva može biti servisirano u isto vrijeme i koliko dugo usluga traje. Posljednju osobinu obično karakterizira statistička distribucija trajanja usluge (zakon raspodjele vremena službe);

- zadatak službene discipline. To znači specificiranje metode pomoću koje se jedan zahtjev bira iz reda čekanja (ako postoji) za uslugu. U svom najjednostavnijem obliku, uslužna disciplina je ispunjavanje zahtjeva redoslijedom kojim su primljeni (pravičan princip), ali postoje mnoge druge mogućnosti.

Zadatak sistema takođe pretpostavlja dobro poznati opis interakcije između njegovih pojedinačnih delova.

Kada je sistem dovoljno u potpunosti definisan, postoji osnova za konstruisanje matematičkog modela. Ako matematički model manje-više adekvatno odražava stvarni sistem, onda omogućava dobijanje glavnih karakteristika funkcionisanja sistema. Naravno, model uvelike pojednostavljuje praktičnu situaciju, ali to ne umanjuje matematičke metode teorije redova čekanja i stanje stvari se ne razlikuje od stanja stvari u drugim oblastima primijenjene matematike.

Vrste sistema čekanja

Ovisno o tome kako se aplikacija rješava ako su svi kanali zauzeti, postoje:

QS sa zahtjevom za uskraćivanje usluge i QS sa očekivanjem.

Tipično je za QS sa neuspjehom da zahtjev koji otkrije da su svi kanali zauzeti odmah napusti sistem.

U QS-u sa čekanjem, zahtjev koji je našao da su svi kanali zauzeti ne napušta sistem, već se stavlja u red čekanja i, kada jedan od kanala postane slobodan, servisira se. U QS-u na čekanju, proces čekanja aplikacija u redu može ili ne mora biti podložan bilo kakvim ograničenjima. U potonjem slučaju kažemo da imamo posla sa "čistim" QS-om sa očekivanjem. Ako su na proces čekanja nametnuta ograničenja, tada se QS naziva „sistem mješoviti tip U takvim sistemima, zbog nametnutih ograničenja, može doći do slučajeva kada će aplikacija dobiti odbijenicu, odnosno QS mješovitog tipa također pokazuje znakove QS-a sa odbijanjem.

U mješovitim sistemima mogu se primijeniti sljedeća ograničenja:

a) broj prijava u redu;

b) za vrijeme dok je aplikacija u redu čekanja;

c) na ukupno vrijeme pronalaženje aplikacije u SMO.

U REM tehnologiji najčešće se susreću QS mješovitog tipa.

Matematički opis QS-a sa otkazom

Razmislite o sigurnom sistemu čekanja sa P kanala. Pretpostavimo da je tok zahtjeva koji pristižu u QS najjednostavniji i da ima gustinu l. Uz to, pretpostavit ćemo da je vrijeme usluge za zahtjeve raspoređeno prema eksponencijalnom zakonu sa parametrom

gdje M(Tob) - matematičko očekivanje vremena servisiranja aplikacije.

Dakle, gustina distribucije vremena usluge

Za sistem koji se razmatra, to je moguće sledeća stanja:

x0- svi kanali su besplatni;

x 1 - jedan kanal je zauzet;

xk -- zauzeto k kanali;

x n -- svi su zauzeti P kanala.

Podaci o stanju servisnog sistema se mogu opisati diferencijalne jednadžbe Erlang. njihovo rješenje omogućava da se dobiju formule za izračunavanje vjerovatnoća koje su konstantne za stabilno stanje. Ovaj način rada se javlja kada t® ¥.

Koeficijent je definisan kao

gdje M(Tob) - matematičko očekivanje vremena usluge jednog zahtjeva.

Erlangove formule su dobijene za slučaj eksponencijalne distribucije vremena usluge, ali vrijede i za bilo koji drugi zakon, sve dok je protok kupaca najjednostavniji.

Vjerovatnoća neusluge aplikacije definira se kao

Prosječan dio vremena u kojem će servisni sistem biti neaktivan može se odrediti vjerovatnoćom stanja x 0 , one.

P mirovanje = p (x 0) = p 0

Primjer. Pustite na mjesto popravke tehnološke opreme uređaji dolaze iz srednje gustine l= 2 jedinice/h. Prosečno vreme servisiranja jednog komada opreme je 24 minuta (0,4 sata). Zahtjev koji utvrdi da su svi kanali zauzeti je odbijen.

Potrebno je odrediti karakteristike QS-a pod pretpostavkom da postoji jedno radno mjesto. Pored toga, potrebno je utvrditi kako se karakteristike QS-a mijenjaju kada se uvede drugo radno mjesto.

Rješenje. Prema uslovu problema, imamo QS sa kvarom. Pretpostavićemo da je tok aplikacija koje ulaze u QS najjednostavniji sa prosečnom gustinom l.

1. Izračunajte faktor opterećenja kanala ili smanjenu gustinu zahtjeva

2. Pronađite QS karakteristike za broj kanala n = 1. Vjerovatnoća neuslužnih zahtjeva:

Relativno propusnost q odlučiti kako

q=1- P potrebno = 1 – 0,44 = 0,56.

Shodno tome, približno 56% prijava koje je primio CMO će biti uručeno.

Vjerovatnoća zastoja kanala p 0

QS teorija je posvećena razvoju metoda za analizu, projektovanje i racionalnu organizaciju sistema vezanih za različite oblasti delovanja, kao što su komunikacija, Computer Engineering, trgovina, transport, vojni poslovi. I pored svoje raznolikosti, navedeni sistemi imaju niz tipičnih svojstava, tj.

QS (sistemi čekanja) je sistemske modele, u kojem, u nasumično vrijeme, prijave (zahtjevi) stižu izvana ili iznutra. Mora ih opsluživati sistem na ovaj ili onaj način. Trajanje usluge je najčešće nasumično.
CMO je totalitet serving oprema i osoblje uz odgovarajuću organizaciju uslužnog procesa.
Postaviti QS znači postaviti ga strukturu i statistiku karakteristike redoslijeda prijema zahtjeva i redoslijeda njihovog servisiranja.

Zadatak QS analize sastoji se u određivanju niza pokazatelja njegove efikasnosti, koji se mogu podijeliti u sljedeće grupe:

indikatori koji karakterišu sistem u celini: broj n zauzeti servisni kanali, broj servisnih kanala (λ b) čeka servis ili odbijene prijave (λ c) po jedinici vremena itd.;
probabilističke karakteristike: vjerovatnoća da će zahtjev biti uručen ( P obs) ili primite odbijenicu usluge ( P otk) da su svi uređaji besplatni ( str 0) ili je određeni broj njih zauzet ( p k), vjerovatnoća čekanja u redu itd.;
ekonomski pokazatelji: trošak gubitaka u vezi sa odlaskom aplikacije koja iz ovog ili onog razloga nije servisirana iz sistema, ekonomski efekat dobijen kao rezultat servisiranja aplikacije itd.

Dio tehničkih indikatora (prve dvije grupe) karakteriziraju sistem sa stanovišta potrošača, drugi dio karakterizira sistem u smislu njegovog učinka. Često izbor ovih indikatora može poboljšati performanse sistema, ali pogoršati sistem sa stanovišta potrošača i obrnuto. Upotreba ekonomski pokazatelji omogućava vam da rešite ovu kontradikciju i optimizujete sistem, uzimajući u obzir obe tačke gledišta.
Tokom domaće zadaće kontrolni rad proučavaju se najjednostavniji QS. Ovo su sistemi otvorene petlje; beskonačan izvor zahtjeva nije uključen u sistem. Ulazni tok zahtjeva, tokovi usluga i očekivanja ovih sistema su najjednostavniji. Nema prioriteta. Sistemi su jednofazni.

Višekanalni sistem sa kvarovima

Sistem se sastoji od jednog servisnog čvora koji sadrži n servisnih kanala, od kojih svaki može opsluživati samo jedan zahtjev.
Svi servisni kanali iste performanse ne mogu se razlikovati za model sistema. Ako zahtjev uđe u sistem i nađe barem jedan slobodan kanal, on odmah počinje da se servisira. Ako su svi kanali zauzeti u trenutku kada zahtjev uđe u sistem, onda zahtjev napušta sistem neuslužen.

mješoviti sistemi

Ograničeni sistem za dužinu reda .
Sastoji se od pogona (reda) i servisnog čvora. Nalog napušta red i izlazi iz sistema ako već ima m naloga u akumulatoru do trenutka kada se pojavi (m je maksimalni mogući broj mjesta u redu). Ako aplikacija uđe u sistem i pronađe barem jedan slobodan kanal, odmah počinje da se servisira. Ako su svi kanali zauzeti u trenutku kada zahtjev uđe u sistem, tada zahtjev ne napušta sistem, već zauzima mjesto u redu čekanja. Zahtjev ostavlja sistem neuslužen ako su do trenutka kada uđe u sistem zauzeti svi servisni kanali i sva mjesta u redu čekanja.
Disciplina reda je definirana za svaki sistem. Ovo je sistem pravila koja određuju redosled kojim aplikacije stižu iz reda čekanja do servisnog čvora. Ako su sve aplikacije i servisni kanali ekvivalentni, onda najčešće važi pravilo „ko je ranije došao, ranije je uslužen“.
Ograničeni sistem za vrijeme trajanja aplikacije u redu čekanja.
Sastoji se od pogona (reda) i servisnog čvora. Razlikuje se od prethodnog sistema po tome što aplikacija koja je ušla u akumulator (red) može čekati na početak servisa samo ograničeno vrijeme. T ozh(najčešće je to slučajna varijabla). Ako je njeno vreme T ozh istekao, tada zahtjev napušta red čekanja i ostavlja sistem neuslužen.

Matematički opis QS-a

QS se smatraju nekim fizičkim sistemima sa diskretna stanja x 0, x 1, ..., x n, koji radi u kontinuirano vrijeme t . Broj stanja n može biti konačan ili prebrojiv (n → ∞). Sistem može preći iz jednog stanja x i (i= 1, 2, ... , n) u drugo x j (j= 0, 1,…,n) u proizvoljnom trenutku t. Da bi se prikazala pravila za takve tranzicije, nazvan je dijagram graf stanja. Za gore navedene tipove sistema, grafovi stanja formiraju lanac u kojem je svako stanje (osim ekstremnih) povezano direktnom i povratnom spregom sa dva susjedna stanja. Ovo je šema smrti i reprodukcije .
Prijelazi iz stanja u stanje se dešavaju u nasumično vrijeme. Zgodno je pretpostaviti da se ovi prijelazi javljaju kao rezultat djelovanja nekih tokovi(tokovi dolaznih zahtjeva, odbijanja u servisiranju zahtjeva, tok vraćanja uređaja itd.). Ako svi tokovi protozoa, zatim nasumično proces sa diskretnim stanjem i kontinuiranim vremenom biće Markovian .
Tok događaja je niz sličnih događaja koji se dešavaju u nasumično vrijeme. Može se posmatrati kao niz slučajnih trenutaka u vremenu t 1 , t 2 , … pojava događaja.
najjednostavniji Protok se poziva ako ima sljedeća svojstva:

Uobičajenost. Događaji slijede jedan po jedan (suprotno od toka, gdje događaji slijede u grupama).
stacionarnost. Vjerovatnoća pogađanja određenog broja događaja u vremenskom intervalu T zavisi samo od dužine intervala i ne zavisi od toga gde se na vremenskoj osi nalazi ovaj interval.
Nema naknadnih efekata. Za dva vremenska intervala τ 1 i τ 2 koja se ne preklapaju, broj događaja koji pada na jedan od njih ne zavisi od toga koliko je događaja palo na drugi interval.

U najjednostavnijem toku, vremenski intervali T 1 , T 2 ,… između trenutaka t 1 , t 2 , … pojave događaja su nasumične, nezavisne jedna od druge i imaju eksponencijalnu distribuciju vjerovatnoće f(t)=λe -λt , t≥0, λ=const, gdje je λ parametar eksponencijalne distribucije, koja je istovremeno intenzitet protok i predstavlja prosečan broj događaja koji se dešavaju u jedinici vremena. Dakle, t =M[T]=1/λ.
Markovskie slučajni događaji su opisani od strane običnih diferencijalne jednadžbe. Varijable u njima su vjerovatnoće stanja R 0 (t), str 1 (t),…,p n (t).
Za veoma veliki trenuci posmatra se vreme rada sistema (teoretski, pri t → ∞) u najjednostavnijim sistemima (sistemi u kojima su svi tokovi jednostavni, a graf je šema smrti i reprodukcije) osnovana, ili stacionarno način rada. U ovom režimu, sistem će promeniti svoje stanje, ali verovatnoće ovih stanja ( konačne vjerovatnoće) r to, k= 1, 2 ,…, n, ne zavise od vremena i mogu se smatrati kao prosječno relativno vrijeme sistem je u ispravnom stanju.

U operativnim istraživanjima se često susreću sistemi dizajnirani za višekratnu upotrebu u rješavanju iste vrste problema. Rezultirajući procesi se nazivaju uslužni procesi, i sistemi sistemi čekanja (QS). Primjeri takvih sistema su telefonski sistemi, servisi, kompjuterski sistemi, blagajne, trgovine, frizerski saloni i slično.

Svaki SMO se sastoji od određeni broj servisne jedinice (instrumenti, uređaji, tačke, stanice) koje ćemo pozvati servisni kanali. Kanali mogu biti komunikacijske linije, operativne tačke, računari, prodavci itd. Prema broju kanala QS se dijele na jednokanalni i višekanalni.

Prijave obično pristižu u CMO ne redovno, već nasumično, formirajući tzv nasumični tok aplikacija (zahtjevi). Zahtjevi za servisiranje, općenito govoreći, također se nastavljaju neko nasumično vrijeme. Nasumična priroda toka aplikacija i vremena servisiranja dovodi do činjenice da se QS neravnomjerno učitava: u nekim vremenskim periodima, mnogo veliki broj aplikacije (ili dođu u red ili ostave QS neuslužen), dok u drugim periodima QS radi sa podopterećenjem ili je u stanju mirovanja.

Predmet teorije čekanja je konstrukcija matematički modeli, povezujući date radne uslove QS-a (broj kanala, njihove performanse, prirodu toka aplikacija, itd.) sa pokazateljima performansi QS-a, koji opisuju njegovu sposobnost da se nosi sa tokom aplikacija.

As Pokazatelji performansi QS korišteno: prosječan broj usluženih aplikacija po jedinici vremena; prosječan broj aplikacija u redu čekanja; prosječno vrijeme čekanja na uslugu; vjerovatnoća uskraćivanja usluge bez čekanja; vjerovatnoća da će broj aplikacija u redu čekanja premašiti određenu vrijednost itd.

QS se dijele na dva glavna tipa (klase): CMO sa kvarovima i QS sa čekanjem (red). U QS-u sa odbijenicama, zahtjev koji stigne u trenutku kada su svi kanali zauzeti prima odbijenicu, napušta QS i ne učestvuje u daljem procesu usluge (npr. zahtjev za telefonski razgovor u trenutku kada su svi kanali zauzeti, dobije odbijenicu i ostavi QS neuslužen). U QS-u sa čekanjem, zahtjev koji stigne u vrijeme kada su svi kanali zauzeti ne odlazi, već čeka u redu za uslugu.

QS sa očekivanjem se dijele na različite vrste ovisno o tome kako je red organiziran: s ograničenom ili neograničenom dužinom reda, s ograničenim vremenom čekanja itd.

Za klasifikaciju QS važnost Ima servisna disciplina, koji određuje redoslijed odabira zahtjeva između primljenih i redosled njihove distribucije među besplatnim kanalima. Na osnovu toga, servis aplikacije se može organizovati po principu „prvi došao – prvi uslužen”, „poslednji došao – prvi uslužen” (ovaj redosled se može koristiti npr. prilikom odnošenja artikala iz skladišta radi servisiranja, jer su posljednji od njih često pristupačniji) ili prioritetna usluga (gdje se najvažniji zahtjevi prvo poslužuju). Prioritet može biti apsolutni, kada važnija aplikacija "izmješta" redovnu aplikaciju iz servisa (na primjer, u slučaju nužde, planirani rad remontnih timova se prekida dok se nesreća ne otkloni), i relativna, kada važnija aplikacija prima samo "najbolje" mjesto u redu čekanja.

Koncept Markovljevog stohastičkog procesa

Proces rada SMO je slučajni proces.

Ispod slučajni (vjerovatni ili stohastički) proces odnosi se na proces promjene stanja sistema tokom vremena u skladu sa vjerojatnosnim zakonima.

Proces se zove proces diskretnog stanja, ako se njegova moguća stanja mogu unaprijed navesti, a prijelaz sistema iz stanja u stanje se dešava trenutno (skok). Proces se zove kontinuirani vremenski proces, ako momenti mogućih prelazaka sistema iz stanja u stanje nisu unapred fiksirani, već su nasumični.

Proces rada QS je slučajan proces sa diskretnim stanjima i kontinuiranim vremenom. To znači da se stanje QS-a naglo mijenja u nasumičnim trenucima pojave nekih događaja (npr. nova aplikacija, kraj usluge itd.).

Matematička analiza rada QS-a je znatno pojednostavljena ako je proces ovog rada Markov. Nasumični proces se zove Markovian ili slučajan proces bez posledica, ako za bilo koji trenutak vremena vjerovatnoća karakteristike procesa u budućnosti zavise samo od njegovog trenutnog stanja i ne zavise od toga kada i kako je sistem došao u ovo stanje.

Primjer Markov proces: sistem - šalter u taksiju. Stanje sistema u ovom trenutku karakteriše broj kilometara (desetinki kilometara) koje je automobil prešao do datog trenutka. Neka u ovom trenutku brojač pokazuje . Vjerovatnoća da će u ovom trenutku mjerač pokazati jedan ili drugi broj kilometara (tačnije, odgovarajući broj rubalja) ovisi o , ali ne ovisi o vremenu u kojem su se očitanja brojila promijenila do trenutka .

Mnogi procesi se mogu smatrati približno markovskim. Na primjer, proces igranja šaha; sistem - grupa šahovskih figura. Stanje sistema karakteriše broj protivničkih figura preostalih na tabli u ovom trenutku. Verovatnoća da će u ovom trenutku materijalna prednost biti na strani nekog od protivnika zavisi prvenstveno od trenutnog stanja sistema, a ne od toga kada su i kojim redosledom figure nestale sa table do trenutka.

U nekim slučajevima, pretpovijest procesa koji se razmatra može se jednostavno zanemariti i Markovljevi modeli se mogu koristiti za njihovo proučavanje.

Prilikom analize slučajnih procesa sa diskretnim stanjima zgodno je koristiti geometrijsku shemu - tzv. graf stanja. Obično su stanja sistema predstavljena pravougaonicima (krugovima), a mogući prelazi iz stanja u stanje su predstavljeni strelicama (orijentisanim lukovima) koje povezuju stanja.

Primjer 1 Konstruirajte graf stanja sljedećeg slučajnog procesa: uređaj se sastoji od dva čvora, od kojih svaki može otkazati u slučajnom trenutku vremena, nakon čega odmah počinjete popravljati čvor, nastavljajući prethodno nepoznato nasumično vrijeme.

Rješenje. Moguća stanja sistema: - oba čvora su u funkciji; - prvi čvor je u popravci, drugi je servisiran; - drugi čvor se popravlja, prvi radi; Obje jedinice su u remontu. Grafikon sistema je prikazan na sl. jedan.

Strelica usmjerena, na primjer, od do , označava prijelaz sistema u trenutku kvara prvog čvora, od do - prijelaz u trenutku kada je popravak ovog čvora završen.

Na grafikonu nema strelica od do i od do. Ovo se objašnjava činjenicom da se pretpostavlja da su kvarovi čvorova neovisni jedan o drugom i, na primjer, vjerojatnost da dva čvora otpadnu istovremeno (prijelaz iz na ) ili istovremeni završetak popravka dva čvora (prijelaz iz na ) može se zanemariti .

Za matematički opis Markovljevog slučajnog procesa sa diskretnim stanjima i kontinuiranim vremenom, koji se dešava u QS, upoznajmo se sa jednim od važnih koncepata teorije vjerovatnoće - konceptom toka događaja.

Tokovi događaja

Ispod tok događaja odnosi se na niz homogenih događaja koji slijede jedan za drugim u nekom nasumičnom vremenu (na primjer, tok poziva na telefonskoj centrali, tok kvarova računara, tok kupaca, itd.).

Protok je karakteriziran intenzitet- učestalost pojavljivanja događaja ili prosječan broj događaja koji ulaze u QS po jedinici vremena.

Tok događaja se zove redovno, ako događaji slijede jedan za drugim u određenim jednakim vremenskim intervalima. Na primjer, tok proizvoda na montažnoj traci (konstantnom brzinom) je redovan.

Tok događaja se zove stacionarno, ako njegove vjerovatnoće ne zavise od vremena. Konkretno, intenzitet stacionarnog strujanja je konstantna vrijednost: . Na primjer, tok automobila na gradskoj aveniji nije stacioniran tokom dana, ali se ovaj tok može smatrati stacionarnim tokom dana, recimo, u vršnim satima. Skrećemo pažnju na činjenicu da se u potonjem slučaju stvarni broj automobila koji prolaze u jedinici vremena (na primjer, u svakoj minuti) može značajno razlikovati jedan od drugog, ali će njihov prosječni broj biti konstantan i neće ovisiti o vremenu. .

Tok događaja se zove protok bez naknadnih efekata, ako za bilo koja dva vremenska intervala koji se ne sijeku i - broj događaja koji padaju na jedan od njih ne zavisi od broja događaja koji pada na druge. Na primjer, protok putnika koji ulaze u metro gotovo da i nema posljedice. A, recimo, tok kupaca koji napuštaju šalter sa svojim kupovinama već ima naknadni efekat (makar samo zato što vremenski interval između pojedinačnih kupaca ne može biti manji od minimalnog vremena usluge za svakog od njih).

Tok događaja se zove običan, ako je vjerovatnoća da će dva ili više događaja pogoditi mali (elementarni) vremenski interval zanemarljivo mala u usporedbi s vjerovatnoćom pogađanja jednog događaja. Drugim riječima, tok događaja je običan ako se događaji pojavljuju u njemu jedan po jedan, a ne u grupama. Na primjer, protok vozova koji se približavaju stanici je običan, ali protok vagona nije običan.

Tok događaja naziva se najjednostavnijim (ili stacionarni Poisson) ako je istovremeno nepomičan, običan i nema naknadno dejstvo. Naziv "najjednostavniji" objašnjava se činjenicom da QS sa najjednostavnijim tokovima ima najjednostavniji matematički opis. Imajte na umu da običan tok nije „najjednostavniji“ jer ima naknadni efekat: momenti nastanka događaja u takvom toku su rigidno fiksirani.

Najjednostavniji tok kao granični tok javlja se u teoriji slučajnih procesa jednako prirodno kao i u teoriji vjerovatnoće normalna distribucija se dobija kao granica za sumu slučajnih varijabli: pri nametanju (superpoziciji) dovoljno velikog broja nezavisnih, stacionarnih i običnih strujanja (uporedivih jedni s drugima po intenzitetima, dobija se tok koji je blizak najjednostavnijem sa intenzitetom jednakim zbroju intenziteta dolaznih strujanja, tj. Razmotrimo na vremenskoj osi (slika 1) najjednostavniji tok događaja kao neograničeni niz slučajnih tačaka.

Može se pokazati da je za najjednostavniji tok broj m događaja (tačaka) koji padaju na proizvoljan vremenski interval raspoređen na Poissonov zakon

za koje je matematičko očekivanje slučajna varijabla jednaka njegovoj varijansi: .

Konkretno, vjerovatnoća da se nijedan događaj neće dogoditi tokom vremena jednaka je

Nađimo distribuciju vremenskog intervala između proizvoljna dva susjedna događaja najjednostavnijeg toka.

U skladu sa (2), vjerovatnoća da se nijedan od narednih događaja neće pojaviti u vremenskom intervalu jednaka je

i vjerovatnoća suprotnog događaja, tj. funkcija distribucije slučajne varijable , je

Gustoća vjerovatnoće slučajne varijable je izvod njene funkcije distribucije (slika 3), tj.

Poziva se distribucija data gustoćom vjerovatnoće (5) ili funkcijom raspodjele (4). otkrivajući(ili eksponencijalna). Dakle, vremenski interval između dva susedna proizvoljna događaja ima eksponencijalnu distribuciju, za koju je matematičko očekivanje jednako standardnoj devijaciji slučajne varijable

i obrnuto prema veličini intenziteta strujanja.

Najvažnija imovina eksponencijalna distribucija (inherentna samo eksponencijalnoj raspodjeli) je sljedeća: ako je vremenski interval raspoređen prema eksponencijalnom zakonu već trajao neko vrijeme, onda to ne utječe na zakon raspodjele preostalog dijela intervala: to će biti isto kao i zakon raspodjele cijelog intervala.

Drugim riječima, za vremenski interval između dva uzastopna susjedna događaja protoka koji ima eksponencijalnu distribuciju, bilo koja informacija o tome koliko dugo je ovaj interval protekao ne utiče na distribuciju ostatka. Ovo svojstvo eksponencijalnog zakona je, u suštini, još jedna formulacija za "nedostatak naknadnog efekta" - glavno svojstvo najjednostavnijeg toka.

Za najjednostavniji tok sa intenzitetom, vjerovatnoća udara

(Imajte na umu da je ova približna formula, dobijena zamjenom funkcije samo sa prva dva člana njenog proširenja u nizu stepena, točnija, što je manja).

Svaki QS se sastoji od određenog broja servisnih jedinica (instrumenata, uređaja, tačaka, stanica) koje ćemo nazvati servisni kanali. Kanali mogu biti komunikacijske linije, operativne tačke, računari, prodavci itd. Prema broju kanala QS se dijele na jednokanalni i višekanalni.

Prijave obično pristižu u CMO ne redovno, već nasumično, formirajući tzv nasumični tok aplikacija (zahtjevi). Zahtjevi za servisiranje, općenito govoreći, također se nastavljaju neko nasumično vrijeme. Nasumična priroda toka aplikacija i vremena servisiranja dovodi do toga da se QS učitava neravnomjerno: u nekim vremenskim periodima se akumulira veoma veliki broj aplikacija (ili stanu u red čekanja ili ostavljaju QS neuslužen), dok u drugim periode QS radi sa podopterećenjem ili je u stanju mirovanja.

Predmet teorije čekanja je konstrukcija matematičkih modela koji povezuju date radne uslove QS-a (broj kanala, njihove performanse, prirodu toka aplikacija, itd.) sa pokazateljima performansi QS-a koji opisuju njegovu sposobnost da se nosi sa tokom aplikacije.

QS se dijele na dva glavna tipa (klase): CMO sa kvarovima i QS sa čekanjem (red). U QS-u sa odbijenicama, zahtjev koji stigne u trenutku kada su svi kanali zauzeti prima odbijenicu, napušta QS i ne učestvuje u daljem servisnom procesu (na primjer, zahtjev za telefonski razgovor u trenutku kada svi kanali su zauzeti prima odbijenicu i ostavlja QS neuslužen). U QS-u sa čekanjem, zahtjev koji stigne u vrijeme kada su svi kanali zauzeti ne odlazi, već čeka u redu za uslugu.

QS sa čekanjem se dele na različite tipove u zavisnosti od toga kako je red organizovan: sa ograničenom ili neograničenom dužinom reda, sa ograničenim vremenom čekanja itd.

Za klasifikaciju QS-a je važno servisna disciplina, koji određuje redoslijed odabira zahtjeva između primljenih i redosled njihove distribucije među besplatnim kanalima. Na osnovu toga, servis aplikacije se može organizovati po principu „prvi došao – prvi uslužen”, „poslednji došao – prvi uslužen” (ovaj redosled se može koristiti npr. prilikom odnošenja artikala iz skladišta radi servisiranja, jer su posljednji od njih često pristupačniji) ili prioritetna usluga (gdje se najvažniji zahtjevi prvo poslužuju). Prioritet može biti apsolutni, kada važnija aplikacija "izmješta" redovnu aplikaciju iz servisa (na primjer, u slučaju nužde, planirani rad remontnih timova se prekida dok se nesreća ne otkloni), i relativna, kada važnija aplikacija prima samo "najbolje" mjesto u redu čekanja.

Koncept Markovljevog stohastičkog procesa

Proces rada SMO je slučajni proces.

Ispod slučajni (vjerovatni ili stohastički) proces odnosi se na proces promjene stanja sistema tokom vremena u skladu sa vjerojatnosnim zakonima.

Proces se zove proces diskretnog stanja ako su njegova moguća stanja S_1,S_2,\ldots,S_n može se unapred nabrojati, a prelazak sistema iz stanja u stanje se dešava trenutno (skok). Proces se zove kontinuirani vremenski proces, ako momenti mogućih prelazaka sistema iz stanja u stanje nisu unapred fiksirani, već su nasumični.

Proces rada QS je slučajan proces sa diskretnim stanjima i kontinuiranim vremenom. To znači da se stanje QS-a naglo mijenja u nasumičnim trenucima pojave nekih događaja (na primjer, dolazak novog zahtjeva, kraj usluge itd.).

Matematička analiza rada QS-a je znatno pojednostavljena ako je proces ovog rada Markov. Nasumični proces se zove Markovian ili slučajan proces bez posledica, ako za bilo koji trenutak vremena t_0 vjerovatnoće karakteristike procesa u budućnosti zavise samo od njegovog stanja u trenutnom trenutku t_0 i ne zavise od toga kada i kako je sistem došao u ovo stanje.

Primjer Markovljevog procesa: sistem S je brojač u taksiju. Stanje sistema u trenutku t karakteriše broj kilometara (desetinki kilometara) koje je automobil prešao do tog trenutka. Neka brojač pokaže S_0 u trenutku t_0. Vjerovatnoća da će u trenutku t>t_0 mjerač pokazati jedan ili drugi broj kilometara (tačnije, odgovarajući broj rubalja) S_1 ovisi o S_0 , ali ne ovisi o vremenu u kojem su se očitanja brojila promijenila prije trenutka t_0 .

Mnogi procesi se mogu smatrati približno markovskim. Na primjer, proces igranja šaha; sistem S je grupa šahovskih figura. Stanje sistema karakteriše broj protivničkih figura preostalih na tabli u trenutku t_0 . Verovatnoća da će u trenutku t>t_0 materijalna prednost biti na strani jednog od protivnika zavisi prvenstveno od stanja sistema u trenutku t_0, a ne od toga kada su i kojim redosledom figure nestale sa table do trenutak t_0 .

U nekim slučajevima, pretpovijest procesa koji se razmatra može se jednostavno zanemariti i Markovljevi modeli se mogu koristiti za njihovo proučavanje.

Primjer 1 Konstruirajte graf stanja sljedećeg slučajnog procesa: uređaj S se sastoji od dva čvora, od kojih svaki može otkazati u slučajnom trenutku vremena, nakon čega odmah počinjete popravljati čvor, nastavljajući u prethodno nepoznatom nasumičnom vremenu.

Rješenje. Moguća stanja sistema: S_0 - oba čvora su operativna; S_1 - prvi čvor je u popravci, drugi je servisiran; S_2 - drugi čvor je u popravci, prvi je servisiran; S_3 - oba čvora se popravljaju. Grafikon sistema je prikazan na sl. jedan.

Strelica usmjerena, na primjer, sa S_0 na S_1 označava prijelaz sistema u trenutku kvara prvog čvora, sa S_1 na S_0 - prijelaz u trenutku kada je popravak ovog čvora završen.

Na grafu od S_0 do S_3 i od S_1 do S_2 nema strelica. Ovo se objašnjava činjenicom da se pretpostavlja da su kvarovi čvorova nezavisni jedan od drugog i, na primjer, vjerovatnoća istovremenog kvara dva čvora (prijelaz sa S_0 na S_3) ili istovremeni završetak popravki dva čvora (prijelaz sa S_3 na S_3). S_0) može se zanemariti.

Tokovi događaja

Protok je karakteriziran intenzitet\lambda - učestalost pojavljivanja događaja ili prosječan broj događaja koji ulaze u QS po jedinici vremena.

Tok događaja se zove redovno, ako događaji slijede jedan za drugim u određenim jednakim vremenskim intervalima. Na primjer, tok proizvoda na montažnoj traci (konstantnom brzinom) je redovan.

Tok događaja se zove stacionarno, ako njegove vjerovatnoće ne zavise od vremena. Konkretno, intenzitet stacionarnog strujanja je konstantna vrijednost: \lambda(t)=\lambda. Na primjer, tok automobila na gradskoj aveniji nije stacioniran tokom dana, ali se ovaj tok može smatrati stacionarnim tokom dana, recimo, u vršnim satima. Skrećemo pažnju na činjenicu da se u potonjem slučaju stvarni broj automobila koji prolaze u jedinici vremena (na primjer, u svakoj minuti) može značajno razlikovati jedan od drugog, ali će njihov prosječni broj biti konstantan i neće ovisiti o vremenu. .

Tok događaja se zove protok bez naknadnih efekata, ako za bilo koja dva ne-preklapajuća vremenska segmenta \tau_1 i \tau_2 - broj događaja koji pada na jedan od njih ne zavisi od broja događaja koji pada na druge. Na primjer, protok putnika koji ulaze u metro gotovo da i nema posljedice. A, recimo, tok kupaca koji napuštaju šalter sa svojim kupovinama već ima naknadni efekat (makar samo zato što vremenski interval između pojedinačnih kupaca ne može biti manji od minimalnog vremena usluge za svakog od njih).

Tok događaja se zove običan, ako je vjerovatnoća da će dva ili više događaja pogoditi mali (elementarni) vremenski interval \Delta t zanemarljiva u usporedbi s vjerovatnoćom jednog događaja. Drugim riječima, tok događaja je običan ako se događaji pojavljuju u njemu jedan po jedan, a ne u grupama. Na primjer, protok vozova koji se približavaju stanici je običan, ali protok vagona nije običan.

Najjednostavniji tok kao granični tok javlja se u teoriji slučajnih procesa jednako prirodno kao i u teoriji vjerovatnoće normalna distribucija se dobija kao granica za sumu slučajnih varijabli: pri nametanju (superpoziciji) dovoljno velikog broja n nezavisnih, stacionarnih i običnih strujanja (uporedivih jedni s drugima po intenzitetima \lambda_i~(i=1,2,\ldots,n) rezultat je tok blizak najjednostavnijem sa intenzitetom \lambda jednakim zbroju intenziteta dolaznih strujanja, tj. \textstyle(\lambda=\sum\limits_(i=1)^(n)\lambda_i). Razmotrimo na vremenskoj osi Ot (slika 1) najjednostavniji tok događaja kao neograničeni niz slučajnih tačaka.

Može se pokazati da je za najjednostavniji tok broj m događaja (tačaka) koji padaju na proizvoljan vremenski interval \tau raspoređen na Poissonov zakon

P_(m)(\tau)= \frac((\lambda\tau)^m)(m\,e^{-\lambda\tau}, !}

za koje je matematičko očekivanje slučajne varijable jednako njenoj varijansi: a=\sigma^2=\lambda\tau.

Konkretno, vjerovatnoća da se nijedan događaj (m=0) neće dogoditi tokom vremena \tau jednaka je

P_0(\tau)=e^(-\lambda\tau).

Nađimo distribuciju vremenskog intervala T između proizvoljna dva susjedna događaja najjednostavnijeg toka.

U skladu sa (2), vjerovatnoća da se nijedan od narednih događaja neće pojaviti u vremenskom intervalu dužine t jednaka je

P(T\geqslant t)=e^(-\lambda t),

i vjerovatnoća suprotnog događaja, tj. funkcija distribucije slučajne varijable T je

F(t)=P(T

Gustoća vjerovatnoće slučajne varijable je izvod njene funkcije distribucije (slika 3), tj.

\varphi(t)=F"(t)=\lambda e^(-\lambda t).

A=\sigma=\frac(1)(\lambda)

I obrnuto u smislu intenziteta toka \lambda .

Najvažnije svojstvo eksponencijalne raspodjele (inherentno samo eksponencijalnoj raspodjeli) je sljedeće: ako vremenski interval raspoređen prema eksponencijalnom zakonu već traje neko vrijeme \tau , onda to ne utiče na zakon raspodjele preostalih dio intervala (T-\tau) : bit će isti kao i zakon raspodjele cijelog intervala T .

Drugim riječima, za vremenski interval T između dva uzastopna susjedna događaja protoka koji ima eksponencijalnu distribuciju, bilo koja informacija o tome koliko dugo je ovaj interval protekao ne utiče na distribuciju ostatka. Ovo svojstvo eksponencijalnog zakona je, u suštini, još jedna formulacija za "nedostatak naknadnog efekta" - glavno svojstvo najjednostavnijeg toka.

Za najjednostavniji tok intenziteta \lambda, vjerovatnoća udara osnovno (malo) vremenski interval \Delta t najmanje jednog događaja toka jednak je prema (4)

P_(\Delta t)= P(T<\Delta t)= 1-e^{-\lambda\Delta t}\approx\lambda\Delta t.

(Imajte na umu da je ova približna formula, dobijena promjenom funkcije e^(-\lambda\Delta t) samo prva dva člana njegovog proširenja niza stepena \Delta t, što je tačnije što je manji \Delta t).

Preskočite na sljedeći odjeljak
Kolmogorovljeve jednačine. Granične vjerovatnoće stanja Javascript je onemogućen u vašem pretraživaču.
ActiveX kontrole moraju biti omogućene da bi se izvršili proračuni!

Koncept sistema čekanja (QS). Vrste sistema čekanja

23. Sistemi čekanja

23.1. Koncept smo

Vrste sistema čekanja

Višekanalni sistem sa kvarovima

mješoviti sistemi

Matematički opis QS-a

Koncept Markovljevog stohastičkog procesa

Tokovi događaja

Koncept Markovljevog stohastičkog procesa

Tokovi događaja