U praktičnom satu razmotrit ćemo ovaj put i usporediti rezultate simulacije s teorijskim rješenjem. Struktura i parametri učinkovitosti i kvalitete funkcioniranja sustava čekanja. Pokazatelji rada sustava čekanja.

30.05.2020 Mali posao

Teorija QS-a posvećena je razvoju metoda za analizu, dizajn i racionalnu organizaciju sustava vezanih uz različita područja djelovanja, poput komunikacija, računarstva, trgovine, transporta i vojnih poslova. Unatoč svoj svojoj raznolikosti, navedeni sustavi imaju niz tipičnih svojstava, naime.

QS (sustavi Čekanje u redu) - ovo je modeli sustava, na koje, u nasumično vrijeme, zahtjevi (zahtjevi) stižu izvana ili iznutra. Njima sustav mora služiti na ovaj ili onaj način. Trajanje usluge je najčešće nasumično.
CMO je totalitet servirati oprema i osoblje uz odgovarajuću organizaciju uslužnog procesa.
Postaviti QS znači postaviti ga struktura i statistički karakteristike redoslijeda zaprimanja prijava i redoslijed njihove usluge.

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

pokazatelji koji karakteriziraju sustav u cjelini: broj n zauzeti servisni kanali, broj servisnih kanala (λ b) čekanje usluge ili odbijeni zahtjevi (λ c) po jedinici vremena itd.;
probabilističke karakteristike: vjerojatnost da će zahtjev biti uslužen ( P obs) ili primiti odbijenicu usluge ( P otk) da su svi uređaji besplatni ( str 0) ili je određeni broj njih zauzet ( p k), vjerojatnost čekanja u redu itd.;
ekonomski pokazatelji: trošak gubitaka povezanih s odlaskom zahtjeva koji iz ovog ili onog razloga nije uslužen iz sustava, ekonomski učinak, dobivene kao rezultat servisiranja zahtjeva i sl.

Dio tehničkih pokazatelja (prve dvije skupine) karakterizira sustav sa stajališta potrošača, drugi dio karakterizira sustav u smislu njegove izvedbe. Često izbor ovih pokazatelja može poboljšati performanse sustava, ali pogoršati sustav sa stajališta potrošača i obrnuto. Korištenje ekonomski pokazatelji omogućuje vam da riješite ovu kontradikciju i optimizirate sustav, uzimajući u obzir obje točke gledišta.
Tijekom domaće zadaće kontrolni rad proučavaju se najjednostavniji QS. To su sustavi otvorene petlje, u sustav nije uključen beskonačan izvor zahtjeva. Ulazni tokovi zahtjeva, tokovi usluga i očekivanja ovih sustava su najjednostavniji. Nema prioriteta. Sustavi su jednofazni.

Višekanalni sustav s kvarovima

Sustav se sastoji od jednog servisnog čvora koji sadrži n servisnih kanala, od kojih svaki može poslužiti samo jedan zahtjev.
Svi uslužni kanali iste izvedbe ne razlikuju se za model sustava. Ako zahtjev uđe u sustav i pronađe barem jedan slobodan kanal, odmah se počinje servisirati. Ako su svi kanali zauzeti u trenutku kada zahtjev uđe u sustav, tada zahtjev ostavlja sustav neobrađenim.

mješoviti sustavi

Ograničeni sustav za duljinu reda .
Sastoji se od pogona (reda) i servisnog čvora. Nalog izlazi iz reda i napušta sustav ako u akumulatoru do trenutka kada se pojavi već ima m naloga (m je najveći mogući broj mjesta u redu). Ako neka aplikacija uđe u sustav i pronađe barem jedan slobodan kanal, odmah počinje servisirati. Ako su svi kanali zauzeti u trenutku ulaska zahtjeva u sustav, tada zahtjev ne napušta sustav, već zauzima mjesto u redu čekanja. Aplikacija napušta sustav neposluženom ako su u trenutku ulaska u sustav svi servisni kanali i sva mjesta u redu čekanja zauzeti.
Disciplina čekanja definirana je za svaki sustav. Ovo je sustav pravila koji određuju redoslijed kojim aplikacije stižu iz reda čekanja do servisnog čvora. Ako su sve prijave i kanali usluge jednaki, onda najčešće vrijedi pravilo “tko je prije došao, prije je uslužen”.
Ograničeni sustav za vrijeme trajanja prijave u redu čekanja.
Sastoji se od pogona (reda) i servisnog čvora. Razlikuje se od prethodnog sustava po tome što aplikacija koja je ušla u akumulator (red čekanja) može samo ograničeno vrijeme čekati početak usluge. T ozh(najčešće je to slučajna varijabla). Ako joj vrijeme T ozh istekao, tada zahtjev napušta red čekanja i ostavlja sustav neposluženim.

Matematički opis QS-a

QS se smatraju nekim fizičkim sustavima sa diskretna stanja x 0, x 1, ..., x n, djeluju na neprekidno vrijeme t . Broj stanja n može biti konačan ili prebrojiv (n → ∞). Sustav se može kretati iz jednog stanja x i (i= 1, 2, ... , n) u drugo x j (j= 0, 1,…,n) u proizvoljnom trenutku u vremenu t. Da bi se prikazala pravila za takve prijelaze, dijagram tzv grafikon stanja. Za gore navedene tipove sustava, grafikoni stanja tvore lanac u kojem je svako stanje (osim onih ekstremnih) izravno i povratno povezano s dva susjedna stanja. Ovo je shema smrti i reprodukcije .
Prijelazi iz stanja u stanje događaju se u nasumično vrijeme. Zgodno je pretpostaviti da se ti prijelazi događaju kao rezultat djelovanja nekih teče(tijekovi dolaznih zahtjeva, odbijanja usluge zahtjeva, povratni tijek uređaja itd.). Ako svi tokovi protozoa, zatim slučajni proces s diskretnim stanjem i kontinuiranim vremenom bit će Markoviev .
Tok događaja je niz sličnih događaja koji se događaju u nasumično odabrano vrijeme. Može se promatrati kao slijed slučajnih trenutaka u vremenu t 1 , t 2 , … događaji.
najjednostavniji Tok se naziva ako ima sljedeća svojstva:

Običnost. Događaji slijede jedan po jedan (suprotno od toka, gdje događaji slijede u skupinama).
stacionarnost. Vjerojatnost pogađanja određenog broja događaja po vremenskom intervalu T ovisi samo o duljini intervala i ne ovisi o tome gdje se na vremenskoj osi taj interval nalazi.
Nema naknadnog učinka. Za dva vremenska intervala τ 1 i τ 2 koji se ne preklapaju, broj događaja koji padaju na jedan od njih ne ovisi o tome koliko događaja pada na drugi interval.

U najjednostavnijem toku vremenski intervali T 1 , T 2 ,… između trenutaka t 1 , t 2 , … pojave događaja su slučajne, neovisne jedna o drugoj i imaju eksponencijalnu distribuciju vjerojatnosti f(t)=λe -λt , t≥0, λ=const, gdje je λ parametar eksponencijalne distribucije, koji je istovremeno intenzitet tok i predstavlja prosječan broj događaja koji se događaju po jedinici vremena. Dakle, t =M[T]=1/λ.
Markovljevi slučajni događaji opisuju se običnim diferencijalne jednadžbe. Varijable u njima su vjerojatnosti stanja R 0 (t), str 1 (t),…,p n (t).
Za vrlo velika vremena funkcioniranja sustava (teoretski, pri t → ∞) u najjednostavnijim sustavima (sustavi u kojima su svi tokovi jednostavni, a graf je shema smrti i reprodukcije), promatramo uspostavljen, ili stacionarni način rada. U ovom načinu rada sustav će promijeniti svoje stanje, ali vjerojatnosti tih stanja ( konačne vjerojatnosti) r do, k= 1, 2 ,…, n, ne ovise o vremenu i mogu se smatrati kao prosječno relativno vrijeme sustav je u ispravnom stanju.

Razmatran u prethodnom predavanju, Markovljev slučajni proces s diskretnim stanjima i kontinuiranim vremenom odvija se u sustavima čekanja (QS).

Sustavi čekanja - to su sustavi u kojima se servisni zahtjevi primaju u nasumičnim razdobljima, dok se primljeni zahtjevi servisiraju korištenjem servisnih kanala koji su sustavu dostupni.

Primjeri sustava čekanja su:

poravnanje i gotovinski čvorovi u bankama, poduzećima;
osobnih računala, posluživanje dolaznih zahtjeva ili zahtjeva za rješavanje određenih problema;
stanice Održavanje automobili; benzinska postaja;
revizorske tvrtke;
odjeli poreznih inspekcija uključeni u prihvaćanje i provjeru tekućeg izvješćivanja poduzeća;
telefonske centrale itd.

	Čvorovi	Zahtjevi

Bolnica	Bolničari	Pacijenti
Proizvodnja
Zračna luka	Izlazi s piste Točke registracije	Putnici

Razmotrite shemu rada QS-a (slika 1). Sustav se sastoji od generatora zahtjeva, dispečera i servisnog čvora, čvora za obračun kvarova (terminator, razarač zahtjeva). Servisni čvor općenito može imati nekoliko servisnih kanala.

Riža. jedan

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

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

Skretanje - zahtjev akumulator. Red možda ne postoji.
Servisni čvor sastoji se od konačnog broja uslužnih kanala. Svaki kanal ima 3 stanja: slobodan, zauzet, neaktivan. Ako su svi kanali zauzeti, onda možete smisliti strategiju kome prebaciti aplikaciju.
Odbijanje iz usluge se javlja ako su svi kanali zauzeti (neki od njih možda neće raditi).

Osim ovih osnovnih elemenata u QS-u, neki izvori razlikuju i sljedeće komponente:

terminator - razarač transakcija;

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

ček računovodstvo- za obavljanje poslova tipa "knjiženje";

manager - upravitelj resursa;

CMO klasifikacija

Prva podjela (prema prisutnosti redova):

CMO s neuspjesima;
CMO s redom čekanja.

NA CMO s neuspjesima zahtjev koji stigne u trenutku kada su svi kanali zauzeti biva odbijen, napušta QS i ne služi se dalje.

NA CMO s redom čekanja aplikacija koja stigne u trenutku kada su svi kanali zauzeti ne odlazi, već stoji u redu i čeka priliku da bude poslužena.

QS s redovima podijeljeno na različiti tipovi 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:

QS s nestrpljivim zahtjevima (duljina čekanja u redu i vrijeme usluge su ograničeni);
QS s prioritetnom uslugom, tj. neke se aplikacije poslužuju izvan reda, itd.

Vrste ograničenja čekanja mogu se kombinirati.

Druga klasifikacija dijeli CMO prema izvoru aplikacija. Zahtjeve (zahtjeve) može generirati sam sustav ili neki od njih vanjsko okruženje, koji postoji neovisno o sustavu.

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

Osim toga, SMO se dijele na otvorena CMO i zatvoreno SMO.

U otvorenom QS-u karakteristike tijeka aplikacija ne ovise o stanju samog QS-a (koliko je kanala zauzeto). U zatvorenom QS-u ovise. Na primjer, ako jedan radnik servisira grupu strojeva koji s vremena na vrijeme zahtijevaju podešavanje, tada intenzitet protoka "zahtjeva" od strojeva ovisi o tome koliko ih je već u ispravnom stanju i čeka na podešavanje.

Primjer zatvorenog sustava: izdavanje plaće od strane blagajnika u poduzeću.

Prema broju kanala QS se dijele na:

jednokanalni;
višekanalni.

Karakteristike sustava čekanja

Glavne karakteristike sustava čekanja bilo koje vrste su:

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

Ulazni tok zahtjeva

Da biste opisali ulazni tok, morate postaviti vjerojatnosni zakon koji određuje redoslijed trenutaka primitka zahtjeva za uslugom, te u svakoj redovnoj potvrdi naznačiti broj takvih tražbina. U ovom slučaju, u pravilu, operiraju s konceptom "probabilističke distribucije trenutaka primitka zahtjeva". Ovdje se možete ponašati kao pojedinačne i grupne zahtjeve (broj takvih tražbina u svakom sljedećem primitku). U potonjem slučaju obično pričamo o sustavu čekanja s uslugom paralelne grupe.

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

E(A) je srednje (MO) vrijeme dolaska;

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

Karakteristike ulaznog toka:

Vjerojatni zakon koji određuje redoslijed trenutaka prijema zahtjeva usluge.
Broj zahtjeva u svakom sljedećem dolasku za multicast tokove.

Disciplina čekanja

Skretanje - skup zahtjeva koji čekaju na servis.

Red čekanja ima ime.

Disciplina čekanja određuje princip prema kojem se zahtjevi pristigli na ulaz servisnog sustava povezuju iz reda čekanja na servisnu proceduru. Najčešće korištene discipline čekanja definirane su sljedećim pravilima:

prvi dodje prvi je posluzen;

prvi ušao prvi izašao (FIFO)

najčešći tip reda čekanja.

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

Lista ima početak i kraj. Popis se sastoji od unosa. Unos je ćelija popisa. Aplikacija dolazi na kraj liste, a odabire se za uslugu s početka liste. Unos se sastoji od opisa aplikacije i linka (indeksa tko stoji iza nje). Osim toga, ako red čekanja ima vremensko ograničenje, tada i vremensko ograničenje mora biti navedeno.

Vi, kao programeri, trebali biste moći napraviti popise dvostrane, jednostrane.

Popis radnji:

umetnite u rep;
uzeti od početka;
ukloniti s popisa nakon isteka vremena.
posljednji dođe, prvi poslužen LIFO (spajalica, slijepa ulica na željezničkoj stanici, ušao u pun auto).

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

slučajni odabir aplikacija;
selekcija prijava prema kriteriju prvenstva.

Svaka aplikacija se, između ostalog, odlikuje razinom prioriteta i po dolasku se ne postavlja na rep reda, već na kraj svoje prioritetne grupe. Dispečer sortira po prioritetu.

Karakteristike reda čekanja

ograničenjevrijeme čekanja trenutak nastanka usluge (postoji red s ograničenim vremenom čekanja na uslugu, koji se povezuje s pojmom „dopuštene duljine reda“);
duljina čekanja.

Servisni mehanizam

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

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

Za analitički opis karakteristika uslužnog postupka koristi se koncept "probabilističke distribucije vremena usluge zahtjeva".

Si– vrijeme usluge ja th zahtjev;

E(S)– prosječno vrijeme usluge;

μ=1/E(S)- zahtjevi za brzinom usluge.

Treba napomenuti da vrijeme servisiranja aplikacije ovisi o prirodi same aplikacije ili zahtjevima klijenta te o stanju i mogućnostima servisnog sustava. U nekim slučajevima također je potrebno uzeti u obzir vjerojatnost kvara servisnog kanala nakon određenog ograničenog vremenskog intervala. Ova se karakteristika može modelirati kao tok kvarova koji ulaze u QS i imaju prioritet nad svim drugim aplikacijama.

QS faktor iskorištenja

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

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

Struktura uslužnog sustava

Struktura uslužnog sustava određena je brojem i međusobnim rasporedom uslužnih kanala (mehanizama, uređaja i sl.). Prije svega, treba naglasiti da uslužni sustav ne može imati jedan uslužni kanal, već nekoliko; sustav ove vrste može zadovoljiti nekoliko zahtjeva istovremeno. U ovom slučaju, svi kanali usluga nude iste usluge i, stoga, može se tvrditi da postoji paralelna usluga .

Primjer. Blagajne u trgovini.

Servisni sustav se može sastojati od nekoliko različitih vrsta servisnih kanala kroz koje mora proći svaki servisirani zahtjev, tj. u servisnom sustavu procedure servisiranja zahtjeva implementiraju se sekvencijalno . Servisni mehanizam definira karakteristike odlaznog (serviranog) toka zahtjeva.

Primjer. Liječnička komisija.

Kombinirana usluga - servisiranje uloga u štedionici: prvo kontrolor, zatim blagajnik. U pravilu 2 kontrolora po blagajniku.

Tako, funkcionalnost bilo koji sustav čekanja određuju sljedeći glavni čimbenici :

probabilistička raspodjela trenutaka zaprimanja servisnih zahtjeva (pojedinačnih ili grupnih);
kapacitet izvora zahtjeva;
probabilistička distribucija vremena trajanja usluge;
konfiguracija servisnog sustava (paralelna, serijska ili paralelno-serijska usluga);
broj i izvedba kanala za posluživanje;
disciplina čekanja.

Glavni kriteriji učinkovitosti funkcioniranja QS-a

Kao glavni kriteriji učinkovitosti funkcioniranja sustava čekanja Ovisno o prirodi problema koji se rješava, može postojati:

vjerojatnost trenutne dostave zaprimljene prijave (P usluga =K obs /K post);
vjerojatnost odbijanja usluge primljene aplikacije (P otk =K otk /K post);

Očito je R obl + P otk =1.

Protoci, kašnjenja, usluga. Pollacek–Khinchinova formula

Odgoditi – jedan od kriterija QS usluge, vrijeme koje je zahtjev proveo u iščekivanju usluge.

D i– kašnjenje u redu zahtjeva ja;

W i \u003d D i + S i– vrijeme provedeno u sustavu zahtjeva ja.

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

(s vjerojatnošću 1) je prosječno vrijeme u stabilnom stanju koje zahtjev provede u QS-u (čekanje).

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

L(t)– broj kupaca u sustavu u jednom trenutku t(Q(t) plus broj zahtjeva koji su u upotrebi u to vrijeme t.

Zatim eksponenti (ako postoje)

(s vjerojatnošću 1) je stacionarni vremenski prosječni broj zahtjeva u redu čekanja;

(s vjerojatnošću 1) je stalni vremenski prosječni broj zahtjeva u sustavu.

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

Ako se sjetimo da je ρ= λ/( Nμ), onda je jasno da ako je intenzitet zaprimanja zahtjeva veći od Nμ, tada je ρ>1, te je prirodno da sustav neće moći podnijeti toliki protok aplikacija, pa se ne može govoriti o d, w, Q i L.

Najopćenitiji i najpotrebniji rezultati za sustave čekanja uključuju jednadžbe očuvanja

Treba napomenuti da se gornji kriteriji za ocjenu performansi sustava mogu analitički izračunati za sustave čekanja M/M/N(N>1), tj. sustavi sa Markov teče zahtjeve i usluge. Za M/G/ l za bilo koju distribuciju G i za neke druge sustave. Općenito, distribucija vremena između dolazaka, distribucija vremena usluge ili obje moraju biti eksponencijalne (ili neka vrsta eksponencijalne Erlangove distribucije k-tog reda) da bi analitičko rješenje bilo moguće.

Osim toga, možete govoriti o takvim karakteristikama kao što su:

apsolutna propusnost sustava – A=R usluga *λ;
relativna propusnost sustava -

Još jedan zanimljiv (i ilustrativan) primjer analitičko rješenje – izračun prosječnog kašnjenja u stacionarnom stanju za sustav čekanja M/G/ 1 prema formuli:

U Rusiji je ova formula poznata kao Pollacek formula. – Khinchin, u inozemstvu se ova formula povezuje s imenom Ross.

Dakle, ako E(S) Ima veću vrijednost, zatim preopterećenje (in ovaj slučaj mjereno kao d) bit će veći; što je i za očekivati. Formula također otkriva manje očitu činjenicu: zagušenje se također povećava kada se povećava varijabilnost u distribuciji vremena usluge, čak i ako prosječno vrijeme usluge ostaje isto. Intuitivno se to može objasniti na sljedeći način: varijanca slučajne varijable vremena servisa može poprimiti veliku vrijednost (jer mora biti pozitivna), tj. jedini servisni uređaj će biti dugo zauzet, što će dovesti do povećanja u redu čekanja.

Predmet teorije čekanja je utvrditi odnos između faktora koji određuju funkcionalnost sustava čekanja i učinkovitosti njegovog funkcioniranja. U većini slučajeva, svi parametri koji opisuju sustave čekanja su slučajne varijable ili funkcije, pa se ti sustavi nazivaju stohastičkim sustavima.

Slučajna priroda toka zahtjeva (zahtjeva), kao i, općenito, trajanje usluge dovodi do toga da se u sustavu čekanja događa slučajni proces. Po prirodi slučajnog procesa koji se javljaju u sustavu čekanja (QS) razlikuju se Markovljevi i nemarkovski sustavi . U Markovljevim sustavima, dolazni tok zahtjeva i odlazni tok servisiranih zahtjeva (potraživanja) su Poissonovi. Poissonovi tokovi olakšati opisivanje i izgradnju matematički model sustavi čekanja. Ovi modeli imaju prilično jednostavna rješenja, tako da većina dobro poznatih primjena teorije čekanja koristi Markovljevu shemu. U slučaju ne-Markovljevih procesa, problemi proučavanja sustava čekanja postaju mnogo kompliciraniji i zahtijevaju korištenje statističkog modeliranja, numeričkih metoda pomoću računala.

4. TEORIJA ČEKOVA ČEKOVA

4.1. Klasifikacija sustava čekanja i pokazatelji njihove učinkovitosti

Sustavi u kojima se zahtjevi za uslugama javljaju u nasumično vrijeme i postoje uređaji za servisiranje tih zahtjeva nazivaju se sustavi čekanja(SMO).

QS se može klasificirati na temelju organizacije usluge kako slijedi:

Sustavi s kvarovima nemaju redove čekanja.

Sustavi čekanja imaju redove.

Zahtjev primljen u trenutku kada su svi servisni kanali zauzeti:

Ostavlja sustav s kvarovima;

Postaje u redu za uslugu u sustavima s čekanjem na neograničeni red ili na prazno mjesto s ograničenim redom;

Ostavlja sustav s ograničenim redom čekanja ako u redu čekanja nema slobodnog prostora.

Kao mjera učinkovitosti ekonomskog QS-a smatra se zbroj vremenskih gubitaka:

Čekanje u redu;

Zastoj servisnih kanala.

Za sve vrste QS-a koriste se: indikator performansi :

- relativna propusnost - ovo je prosječni udio dolaznih aplikacija koje servisira sustav;

- apsolutna propusnost - ovo je prosječan broj aplikacija koje sustav opslužuje po jedinici vremena;

- vjerojatnost kvara - je vjerojatnost da će zahtjev ostaviti sustav bez usluge;

- prosječno zauzeti kanali - za višekanalni QS.

Pokazatelji učinkovitosti QS-a izračunavaju se prema formulama iz posebnih priručnika (tablica). Početni podaci za takve izračune su rezultati QS modeliranja.

4.2. Modeliranje sustava čekanja:

osnovni parametri, grafikon stanja

Uz svu raznolikost QS-a, oni imaju zajedničke značajke , koji omogućuju objedinjavanje njihovog modeliranja pronaći najučinkovitije opcije za organizaciju takvih sustava .

Za modeliranje QS-a potrebno je imati sljedeće početne podatke:

Glavni parametri;

Grafikon stanja.

Rezultati QS modeliranja su vjerojatnosti njegovih stanja kroz koje se izražavaju svi pokazatelji njegove učinkovitosti.

Ključni parametri za QS modeliranje uključuju:

Karakteristike dolaznog tijeka servisnih zahtjeva;

Karakteristike uslužnog mehanizma.

Smatrati x karakteristike toka aplikacije .

Tijek aplikacije - redoslijed zahtjeva za uslugu.

Intenzitet protoka prijava - prosječan broj aplikacija koje ulaze u QS po jedinici vremena.

Tokovi aplikacije su jednostavni i razlikuju se od najjednostavnijih.

Za najjednostavnije tokove primjene koriste se QS modeli.

najjednostavniji , ili Poisson naziva se potok koji je stacionarni, singl i u njemu bez posljedica.

stacionarnost znači nepromjenjivost intenziteta zaprimanja prijava tijekom vremena.

singl tijek prijava je u slučaju kada je u kratkom vremenskom razdoblju vjerojatnost zaprimanja više od jedne prijave blizu nule.

Nema naknadnog učinka leži u činjenici da broj prijava koje je QS primio u jednom vremenskom intervalu ne utječe na broj prijava primljenih u drugom vremenskom intervalu.

Simulacijski modeli koriste se za aplikacije koje se razlikuju od najjednostavnijih.

Smatrati karakteristike servisnog mehanizma .

Servisni mehanizam karakterizira:

- broj servisni kanali ;

performanse kanala, ili intenzitet usluge - prosječan broj aplikacija koje opslužuje jedan kanal po jedinici vremena;

Disciplina čekanja (npr. volumen čekanja , redoslijed odabira od reda do uslužnog mehanizma itd.).

Grafikon stanja opisuje funkcioniranje uslužnog sustava kao prijelaze iz jednog stanja u drugo pod djelovanjem protoka zahtjeva i njihovog servisiranja.

Da biste izgradili QS grafikon stanja, trebate:

Napravite popis svih mogućih QS stanja;

Grafički prikazati navedena stanja i strelicama prikazati moguće prijelaze između njih;

Izvažite prikazane strelice, odnosno dodijelite im numeričke vrijednosti intenziteta prijelaza određene intenzitetom protoka zahtjeva i intenzitetom njihove usluge.

4.3. Izračun vjerojatnosti stanja

sustavi čekanja

QS graf stanja sa shema "smrti i rođenja" je linearni lanac, gdje svako od prosječnih stanja ima ravnu liniju i Povratne informacije sa svakom od susjednih država, a krajnje države sa samo jednom susjednom:

Broj država u stupcu je jedno više od ukupnog broja uslužnih kanala i mjesta u redu čekanja.

QS može biti u bilo kojem od svojih mogućih stanja, pa je očekivana stopa izlaska iz bilo kojeg stanja jednaka očekivanoj brzini ulaska sustava u to stanje. Odavde će sustav jednadžbi za određivanje vjerojatnosti stanja za najjednostavnije tokove izgledati ovako:

gdje je vjerojatnost da je sustav u stanju

- intenzitet prijelaza, odnosno prosječan broj prijelaza sustava u jedinici vremena iz stanja u stanje.

Koristeći ovaj sustav jednadžbi, kao i jednadžbu

vjerojatnost bilo kojeg -tog stanja može se izračunati na sljedeći način opće pravilo :

vjerojatnost nultog stanja izračunava se kao

a zatim se uzima razlomak u čijem je brojniku umnožak svih intenziteta protoka duž strelica koje vode s lijeva na desno od stanja do stanja, au nazivniku - umnožak svih intenziteta duž strelica koje idu s desna na lijevo od stanja do stanja , a taj se razlomak množi s izračunatom vjerojatnošću

Zaključci o četvrtom dijelu

Sustavi čekanja imaju jedan ili više servisnih kanala i mogu imati ograničen ili neograničen red čekanja (sustavi čekanja) zahtjeva za uslugama ili bez reda čekanja (sustavi odbijanja). Zahtjevi za uslugom javljaju se u nasumično vrijeme. Sustave čekanja karakteriziraju sljedeći pokazatelji performansi: relativna propusnost, apsolutna propusnost, vjerojatnost kvara, prosječan broj zauzetih kanala.

Modeliranje sustava čekanja provodi se kako bi se pronašle najučinkovitije opcije za njihovu organizaciju i pretpostavlja sljedeće početne podatke za to: osnovne parametre, grafikon stanja. Takvi podaci uključuju sljedeće: intenzitet protoka prijava, broj uslužnih kanala, intenzitet usluge i volumen čekanja. Broj stanja na grafu je za jedan veći od zbroja broja servisnih kanala i mjesta u redu čekanja.

Izračun vjerojatnosti stanja sustava čekanja sa shemom "smrti i rođenja" provodi se prema općem pravilu.

Pitanja za samoispitivanje

Koji se sustavi nazivaju sustavima čekanja?

Kako se klasificiraju sustavi čekanja prema njihovoj organizaciji?

Koji se sustavi čekanja nazivaju sustavima s kvarovima, a koji čekaju?

Što se događa sa zahtjevom koji stigne u trenutku kada su svi kanali usluge zauzeti?

Što se smatra mjerom učinkovitosti ekonomski sustav masovna služba?

Koji su pokazatelji učinkovitosti sustava čekanja?

Što služi kao početni podatak za izračun pokazatelja rada sustava čekanja?

Koji su ulazni podaci potrebni za modeliranje sustava čekanja?

Kroz koje se rezultate modeliranja sustava čekanja iskazuju svi pokazatelji njegove učinkovitosti?

Koji su glavni parametri za modeliranje sustava čekanja?

Što su tokovi zahtjeva za uslugu?

Koji su mehanizmi usluge?

Što opisuje grafikon stanja sustava čekanja

Što je potrebno za izgradnju grafikona stanja sustava čekanja?

Što je grafikon stanja sustava čekanja sa shemom smrti i rođenja?

Koliki je broj stanja u grafu stanja sustava čekanja?

Kakav je oblik sustava jednadžbi za određivanje vjerojatnosti stanja sustava čekanja?

Koje je opće pravilo za izračunavanje vjerojatnosti bilo kojeg stanja sustava čekanja?

Primjeri rješavanja problema

1. Izgradite grafikon stanja sustava čekanja i navedite glavne ovisnosti njegovih indikatora performansi.

a) n-kanalni QS s kvarovima (Erlangov problem)

Glavni parametri:

kanali,

intenzitet protoka,

Intenzitet usluge.

Moguća stanja sustava:

Svi kanali su zauzeti (aplikacije u sustavu).

Grafikon stanja:

Relativna propusnost,

Vjerojatnost neuspjeha,

Prosječan broj zauzetih kanala.

b) n-kanalni QS sa m- ograničeni red čekanja

Moguća stanja sustava:

Svi kanali su besplatni (nula zahtjeva u sustavu);

Jedan kanal je zauzet, ostali su slobodni (jedan zahtjev u sustavu);

Dva kanala su zauzeta, ostali su slobodni (dvije aplikacije u sustavu);

...................................................................................

Svi kanali su zauzeti, dvije aplikacije su u redu;

Svi kanali su zauzeti, aplikacije su u redu.

Grafikon stanja:

c) Jednokanalni QS s neograničenim redom

Moguća stanja sustava:

Svi kanali su besplatni (nula zahtjeva u sustavu);

Kanal je zauzet, nula zahtjeva u redu;

Kanal je zauzet, jedna aplikacija je u redu;

...................................................................................

Kanal je zauzet, aplikacija je u redu;

....................................................................................

Grafikon stanja:

Pokazatelji performansi sustava:

Prosječno vrijeme zadržavanja aplikacije u sustavu ,

Apsolutna propusnost,

Relativna propusnost.

G) n-kanalni QS s neograničenim redom

Moguća stanja sustava:

Svi kanali su besplatni (nula zahtjeva u sustavu);

Jedan kanal je zauzet, ostali su slobodni (jedan zahtjev u sustavu);

Dva kanala su zauzeta, ostali su slobodni (dvije aplikacije u sustavu);

...................................................................................

Svi kanali su zauzeti (zahtjevi u sustavu), nula zahtjeva u redu čekanja;

Svi kanali su zauzeti, jedna aplikacija je u redu;

....................................................................................

Svi kanali su zauzeti, aplikacije su u redu;

....................................................................................

Grafikon stanja:

Pokazatelji performansi sustava:

Prosječan broj zauzetih kanala,

Prosječan broj prijava u sustavu ,

Prosječan broj prijava u redu ,

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

2. Računalni centar ima tri računala. Centar u prosjeku dobiva četiri zadatka na sat za rješavanje. Prosječno vrijeme rješavanja jednog problema je pola sata. Računalni centar prihvaća i stavlja u red čekanja za rješavanje najviše tri zadatka. Potrebno je procijeniti učinkovitost centra.

RIJEŠENJE. Iz uvjeta je jasno da imamo višekanalni QS s ograničenim redom:

Broj kanala;

Intenzitet protoka prijava (zadatak / sat);

Vrijeme usluge za jednu aplikaciju (sat / zadatak), intenzitet usluge (zadatak / sat);

Dužina čekanja.

Popis mogućih stanja:

Nema aplikacija, svi kanali su besplatni;

Jedan kanal je zauzet, dva su slobodna;

Dva kanala su zauzeta, jedan je slobodan;

Tri kanala su zauzeta;

Tri kanala su zauzeta, jedna aplikacija je u redu;

Tri kanala su zauzeta, dvije aplikacije su u redu;

Tri kanala su zauzeta, tri aplikacije su u redu.

Grafikon stanja:

Izračunajte vjerojatnost stanja:

Indikator performansi:

Vjerojatnost odbijanja (sva tri računala su zauzeta i tri aplikacije su u redu čekanja)

Relativna propusnost

Apsolutna propusnost

Prosječan broj zauzetih računala

3. (Problem s upotrebom QS-a s kvarovima.) Postoje tri kontrolera koji rade u QCD-u trgovine. Ako dio stigne u Odjel kontrole kvalitete kada su svi inspektori zauzeti servisiranjem prethodno zaprimljenih dijelova, tada ostaje neprovjeren. Prosječan broj dijelova koji stignu u odjel kontrole kvalitete tijekom jednog sata je 24, prosječno vrijeme koje jedan inspektor utroši na servisiranje jednog dijela je 5 minuta. Odredite vjerojatnost da će dio proći odjel kontrole kvalitete bez servisa, koliko su upravljači opterećeni i koliko ih je potrebno isporučiti da bi (* - zadana vrijednost).

RIJEŠENJE. Prema uvjetu problema, dakle .

1) Vjerojatnost prekida uslužnih kanala:

3) Vjerojatnost usluge:

4) Prosjek zaposlena u servisiranju kanali:

5) Udio kanala koje usluga zauzima:

6) Apsolutna propusnost:

U . Provodeći slične izračune za , dobivamo

Budući da , nakon izrade izračuna za , dobivamo

ODGOVOR. Postoji 21% šanse da će dio proći kroz QCD neservisiran, a inspektori će biti 53% zauzeti servisiranjem.

Za pružanje razine usluge preko 95% potrebno je najmanje pet kontrolera.

4. (Problem s korištenjem QS-a s br ograničeno očekivanje.) Štedionica ima tri šalterska kontrolora () za opsluživanje štediše. Tijek štediša ulazi u štedionicu intenzitetom od ljudi na sat. Prosječno trajanje usluge kontrolora-blagajnika jednog deponenta min.

Odrediti karakteristike štedionice kao objekta QS-a.

RIJEŠENJE. Intenzitet protoka usluga, intenzitet opterećenja.

1) Vjerojatnost zastoja kontrolora-blagajnika tijekom radnog dana (vidi prethodni zadatak br. 3):

2) Vjerojatnost da se svi kontrolori na blagajni pronađu zauzeti:

3) Vjerojatnost čekanja u redu:

4) Prosječan broj prijava u redu čekanja:

5) Prosječno vrijeme čekanja na zahtjev u redu čekanja:

min.

6) Prosječno vrijeme boravka prijave u CMO-u:

7) Prosječan broj besplatnih kanala:

8) Stopa popunjenosti servisnih kanala:

9) Prosječan broj posjetitelja u štedionici:

ODGOVOR. Vjerojatnost zastoja za blagajnike je 21% radnog vremena, vjerojatnost da posjetitelj bude u redu je 11,8%, prosječan broj posjetitelja u redu je 0,236 ljudi, prosječno vrijeme čekanja posjetitelja servisa je 0,472 minute.

5. (Problem s korištenjem QS-a s čekanjem i ograničenom duljinom reda.) Trgovina prima rano povrće iz prigradskih staklenika. Stižu kamioni s teretom drugačije vrijeme s intenzitetom strojeva po danu. Pomoćne prostorije i oprema za pripremu povrća za prodaju omogućuju preradu i skladištenje robe koju dovoze dva vozila (). U prodavaonici postoje tri pakirnice () od kojih svaka u prosjeku može obraditi robu s jednog stroja sat vremena.Radni dan za smjenski rad je 12 sati.

Utvrditi koliki bi trebao biti kapacitet pomoćnih prostorija da bi bila vjerojatnost potpune obrade robe.

RIJEŠENJE. Odredimo intenzitet utovara pakera:

Automatski/dan

1) Pronađite vjerojatnost zastoja za pakirače u nedostatku strojeva (aplikacije):

gdje je 0!=1.0.

2) Vjerojatnost uskraćivanja usluge:

3) Vjerojatnost usluge:

Jer , izvodimo slične izračune za , dobivamo), dok će vjerojatnost potpune obrade robe biti .

Zadaci za samostalan rad

Za svaku od sljedećih situacija odredite:

a) kojoj klasi QS objekt pripada;

b) broj kanala;

c) duljina čekanja;

d) intenzitet protoka prijava;

e) stopa usluge po kanalu;

f) broj svih stanja QS objekta.

U svojim odgovorima navedite vrijednosti za svaku stavku koristeći sljedeće kratice i dimenzije:

a) TOE - jedan kanal s kvarovima; MO - višekanalni s kvarovima; OJO - jednokanalno čekanje s ograničenim redom; OZHN - jednokanalni s čekanjem s neograničenim redom; MJO - višekanalno čekanje s ograničenim redom; MZHN - višekanalno čekanje s neograničenim redom;

b) =… (jedinice);

c) =… (jedinice);

d) =xxx/xxx(jedinice/min);

e) =xxx/xxx(jedinice/min);

f) (jedinice).

1. Dežurni u gradskoj upravi ima pet telefona. Telefonski pozivi prima intenzitetom od 90 prijava na sat, prosječno trajanje razgovora je 2 minute.

2. Na parkingu kod trgovine postoje 3 mjesta od kojih je svako rezervirano za jedan automobil. Automobili na parkiralište stižu brzinom od 20 automobila na sat. Dužina zadržavanja automobila na parkiralištu je prosječno 15 minuta. Parkiranje na kolniku nije dopušteno.

3. ATS poduzeća ne pruža više od 5 pregovora u isto vrijeme. Prosječno trajanje razgovora je 1 minuta. Stanica prima prosječno 10 poziva u sekundi.

4. Teretna riječna luka prima prosječno 6 brodova za suhi teret dnevno. U luci postoje 3 dizalice, od kojih svaka opslužuje 1 brod za suhi teret u prosjeku 8 sati.Dizalice rade 24 sata dnevno. Na ramdi su brodovi za suhi teret koji čekaju uslugu.

5. U službi hitne pomoći sela, 3 dispečera dežuraju 24 sata dnevno, servisirajući 3 telefona. Ako je zahtjev za pozivanje liječnika pacijentu primljen kada su dispečeri zauzeti, tada se pretplatnik odbija. Protok prijava je 4 poziva u minuti. Proces prijave u prosjeku traje 1,5 minuta.

6. Frizerski salon ima 4 majstora. Dolazni tok posjetitelja ima intenzitet od 5 osoba na sat. Prosječno vrijeme usluge za jednog klijenta je 40 minuta. Duljina čekanja usluge smatra se neograničenom.

7. Na benzinskoj postaji postavljena su 2 aparata za točenje benzina. U blizini stanice nalazi se platforma za 2 automobila za čekanje na točenje goriva. U prosjeku svake 3 minute na kolodvor stiže jedan automobil. Prosječno vrijeme servisiranja jednog stroja je 2 minute.

8. Na kolodvoru rade tri obrtnika u radionici potrošačkih usluga. Ako klijent uđe u radionicu kada su svi majstori zauzeti, tada napušta radionicu ne čekajući uslugu. Prosječan broj klijenata koji posjećuju radionicu u 1 satu je 20. Prosječno vrijeme koje majstor utroši na posluživanje jednog klijenta je 6 minuta.

9. PBX sela ne pruža više od 5 poziva u isto vrijeme. Prosječno vrijeme pregovora je oko 3 minute. Pozivi na stanicu stižu u prosjeku nakon 2 minute.

10. Na benzinskoj postaji (benzinskoj postaji) postoje 3 kolone. Mjesto na stanici gdje automobili čekaju na dopunu gorivom može primiti najviše jedan automobil, a ako je zauzeto, tada sljedeći automobil koji stigne na stanicu ne stoji u redu, već prelazi na susjednu stanicu. U prosjeku automobili stižu na stanicu svake 2 minute. Proces punjenja jednog stroja traje prosječno 2,5 minute.

11. Ulaz mali dućan kupce opslužuju dva prodavača. Prosječno vrijeme usluge za jednog kupca je 4 minute. Intenzitet protoka kupaca je 3 osobe u minuti. Kapacitet trgovine je takav da u redu ne može biti više od 5 osoba istovremeno. Kupac koji dođe u prepunu trgovinu kad je već 5 ljudi u redu ne čeka vani i odlazi.

12. željeznička stanica Dacha selo opslužuje blagajna s dva prozora. Vikendom, kada stanovništvo aktivno koristi željeznicu, intenzitet protoka putnika je 0,9 ljudi / min. Blagajnik u prosjeku potroši 2 minute na posluživanje putnika.

Za svaku od QS opcija navedenih u QS opcijama, intenzitet protoka prijava jednak je i intenzitetu usluge po jednom kanalu. Potreban:

Napravite popis mogućih stanja;

Konstruirajte graf stanja prema shemi "smrt i razmnožavanje".

U svom odgovoru za svaki zadatak označite:

Broj stanja sustava;

Intenzitet prijelaza iz zadnjeg stanja u pretposljednje.

Opcija broj 1

1. jednokanalni QS s redom od 1 zahtjeva

2. 2-kanalni QS s kvarovima (Erlang problem)

3. 31-kanalni QS s 1 ograničenim redom čekanja

5. 31-kanalni QS s neograničenim redom

Opcija broj 2

1. jednokanalni QS s redom od 2 zahtjeva

2. 3-kanalni QS s kvarovima (Erlang problem)

3. 30-kanalni QS s 2-ograničenim redom čekanja