Modele matematice ale sistemelor de aşteptare pentru rezolvarea problemelor economice. Înainte de a începe lucrul, asigurați-vă că nu există daune vizibile la echipament și fire

Imagine 0 - 2 Fluxuri de evenimente (a) și cel mai simplu flux (b)

10.5.2.1. staționaritate

Fluxul se numește staționar , dacă probabilitatea de a lovi unul sau altul număr de evenimente într-o perioadă elementară de timp lungime τ (

Figura 0-2 , A) depinde doar de lungimea secțiunii și nu depinde de locul exact pe ax t aceasta zona este situata.

Staționaritatea fluxului înseamnă uniformitatea acestuia în timp; caracteristicile probabilistice ale unui astfel de flux nu se modifică în timp. În special, așa-numita intensitate (sau „densitate”) a fluxului de evenimente, numărul mediu de evenimente pe unitatea de timp pentru un flux staționar, trebuie să rămână constantă. Acest lucru, desigur, nu înseamnă că numărul real de evenimente care apar pe unitatea de timp este constant; fluxul poate avea concentrații și rarefacții locale. Este important ca pentru un flux staționar aceste concentrații și rarefări să nu fie de natură obișnuită, iar numărul mediu de evenimente care se încadrează într-un singur interval de timp să rămână constant pentru întreaga perioadă luată în considerare.

În practică, există adesea fluxuri de evenimente care (cel puțin pentru o perioadă limitată de timp) pot fi considerate staționare. De exemplu, fluxul de apeluri care sosesc la centrala telefonică, să zicem, în intervalul de la 12 la 13 ore poate fi considerat staționar. Același flux nu va mai fi staționar pentru o zi întreagă (noaptea, intensitatea fluxului de apeluri este mult mai mică decât în ​​timpul zilei). Rețineți că același lucru este și cazul majorității proceselor fizice pe care le numim „staționare”, de fapt, ele sunt staționare doar pentru o perioadă limitată de timp, iar extinderea acestei perioade la infinit este doar un truc convenabil folosit în scopuri de simplificare. .

10.5.2.2. Fără efect secundar

Fluxul evenimentelor se numește flux fără efecte secundare , dacă pentru orice interval de timp care nu se suprapun numărul de evenimente care se încadrează pe unul dintre ele nu depinde de câte evenimente au căzut pe celălalt (sau altele, dacă sunt luate în considerare mai mult de două secțiuni).

În astfel de fluxuri, evenimentele care formează fluxul apar în momente succesive în timp, independent unele de altele. De exemplu, fluxul de pasageri care intră într-o stație de metrou poate fi considerat un flux fără efecte secundare, deoarece motivele care au determinat sosirea unui pasager individual în acest moment particular și nu în altul, de regulă, nu sunt legate de motive similare. pentru alți pasageri. Dacă apare o astfel de dependență, condiția pentru absența unui efect secundar este încălcată.

Luați în considerare, de exemplu, fluxul de trenuri de marfă care circulă de-a lungul unei linii de cale ferată. Dacă, din motive de siguranță, aceștia nu pot să se succedă mai des decât la intervale de timp t0 , atunci există o dependență între evenimentele din flux, iar condiția fără efect secundar este încălcată. Cu toate acestea, dacă intervalul t0 este mic în comparație cu intervalul mediu dintre trenuri, atunci o astfel de încălcare este nesemnificativă.

Imagine 0 - 3 Distribuția Poisson

Luați în considerare pe axă t cel mai simplu flux de evenimente cu intensitatea λ. (Figura 0-2 b) . Ne va interesa un interval de timp aleator T între evenimentele adiacente din acest flux; găsiți legea distribuției sale. Mai întâi, să găsim funcția de distribuție:

F(t) = P(T ( 0-2)

adică probabilitatea ca valoarea lui T va avea o valoare mai mică decâtt. Lăsați deoparte de la începutul intervalului T (puncte t0) segmentul t și găsiți probabilitatea ca intervalul T va fi mai putin t . Pentru a face acest lucru, este necesar ca pentru o secțiune de lungime t , adiacent unui punct t0 , cel puțin un eveniment accesat de fir. Să calculăm probabilitatea acestui lucru F(t) prin probabilitatea evenimentului opus (pe segment t niciun eveniment din flux nu va atinge):

F (t) \u003d 1 - P 0

Probabilitate P 0 găsim prin formula (1), presupunândm = 0:

de unde funcția de distribuție a valorii T va fi:

(0-3)

Pentru a afla densitatea distribuției f(t) variabilă aleatorie T, este necesar să se diferenţieze expresia (0‑1) print:

0-4)

Legea distribuției cu densitatea (0-4) se numește exponențială (sau exponențial ). Valoarea λ se numește parametru lege exemplară.

Figura 0 - 4 Distribuție exponențială

Găsiți caracteristicile numerice ale unei variabile aleatorii T- așteptări matematice (valoare medie) M[t]=mt , şi dispersia D t . Avem

( 0-5)

(integrare pe părți).

Dispersia valorii lui T este:

(0-6)

Extragând rădăcina pătrată a varianței, găsim abaterea standard a variabilei aleatoare T.

Deci, pentru o distribuție exponențială, așteptarea matematică și abaterea standard sunt egale între ele și sunt inverse parametrului λ, unde λ. intensitatea curgerii.

Astfel, aspectul m evenimentele dintr-un interval de timp dat corespunde distribuției Poisson, iar probabilitatea ca intervalele de timp dintre evenimente să fie mai mici decât un număr predeterminat corespunde distribuției exponențiale. Toate acestea sunt doar descrieri diferite ale aceluiași proces stocastic.

QS Exemplul-1 .

Ca exemplu, luați în considerare un sistem bancar în timp real care deservește un număr mare de clienți. În timpul orelor de vârf, cererile de la casierii băncii care lucrează cu clienții formează un flux Poisson și ajung în medie două pe 1 s (λ = 2). Fluxul constă în cererile care ajung cu o rată de 2 cereri pe secundă.

Calculați probabilitatea P ( m ) apariții m mesaje în 1 s. Deoarece λ = 2, din formula anterioară avem

Inlocuind m = 0, 1, 2, 3, obținem următoarele valori (până la patruzecimale):

Figura 0 - 5 Cel mai simplu exemplu de flux

Mai mult de 9 mesaje în 1 s sunt, de asemenea, posibile, dar probabilitatea acestui lucru este foarte mică (aproximativ 0,000046).

Distribuția rezultată poate fi reprezentată ca histogramă (prezentată în figură).

Exemplu de CMO-2.

Un dispozitiv (server) care procesează trei mesaje în 1 secundă.

Să existe un echipament care poate procesa trei mesaje în 1 s (µ=3). În medie, două mesaje sunt primite în 1 secunde și în conformitate c Distribuția Poisson. Ce proporție dintre aceste mesaje va fi procesată imediat după primire?

Probabilitatea ca rata de sosire să fie mai mică sau egală cu 3 s este dată de

Dacă sistemul poate procesa maximum 3 mesaje în 1 s, atunci probabilitatea ca acesta să nu fie supraîncărcat este

Cu alte cuvinte, 85,71% dintre mesaje vor fi difuzate imediat și 14,29% cu o oarecare întârziere. După cum puteți vedea, o întârziere în procesarea unui mesaj pentru un timp mai mare decât timpul de procesare a 3 mesaje va apărea rar. Timpul de procesare a unui mesaj este în medie de 1/3 s. Prin urmare, o întârziere mai mare de 1 s va fi rară, ceea ce este destul de acceptabil pentru majoritatea sistemelor.

Exemplu de CMO 3

· Dacă un casier de bancă este ocupat în 80% din timpul său de lucru, iar restul timpului își petrece așteptarea clienților, atunci el poate fi considerat un dispozitiv cu un factor de utilizare de 0,8.

· Dacă canalul de comunicație este utilizat pentru a transmite simboluri pe 8 biți la o rată de 2400 bps, adică maxim 2400/8 simboluri sunt transmise în 1 s și construim un sistem în care cantitatea totală de date este de 12000 simboluri trimise de la diferite dispozitive prin canal pe minut ocupat (inclusiv sincronizare, caractere de sfârșit de mesaj, caractere de control etc.), atunci rata de utilizare a echipamentului canalului de comunicație în acest minut este egală cu

· Dacă motorul de acces la fișiere în oră aglomerată realizează 9000 de accesări la fișiere, iar timpul per acces este în medie de 300 ms, atunci utilizarea hardware-ului motorului de acces în oră aglomerată este

Conceptul de utilizare a echipamentului va fi folosit destul de des. Cu cât utilizarea echipamentului este mai aproape de 100%, cu atât întârzierea este mai mare și coada este mai lungă.

Folosind formula anterioară, puteți compila tabele cu valorile funcției Poisson, din care puteți determina probabilitatea de a primim sau mai multe mesaje într-o anumită perioadă de timp. De exemplu, dacă o medie de 3,1 mesaje pe secundă [i.e. e. λ = 3.1], atunci probabilitatea de a primi 5 sau mai multe mesaje într-o secundă dată este 0,2018 (pentrum = 5 în tabel). Sau sub formă analitică

Folosind această expresie, analistul de sisteme poate calcula probabilitatea ca sistemul să nu îndeplinească un anumit criteriu de încărcare.

Adesea, calculele inițiale pot fi făcute pentru valorile de încărcare a echipamentului.

p ≤ 0,9

Aceste valori pot fi obținute folosind tabelele Poisson.

Fie din nou rata medie de sosire a mesajelor λ = 3,1 mesaje/s. Din tabele rezultă că probabilitatea de a primi 6 sau mai multe mesaje în 1 s este 0,0943. Prin urmare, acest număr poate fi luat ca un criteriu de încărcare pentru calculele inițiale.

10.6.2. Provocări de proiectare

Având în vedere natura aleatorie a sosirii mesajelor pe dispozitiv, acesta din urmă petrece o parte din timp procesând sau deservind fiecare mesaj, rezultând în formarea de cozi. Coada de la bancă așteaptă eliberarea casierului și a calculatorului (terminalul) acestuia. Coada de mesaje din memoria tampon de intrare a computerului așteaptă să fie procesată de procesor. Coada de solicitări pentru matrice de date așteaptă eliberarea canalelor etc. Se pot forma cozi în toate blocajele sistemului.

Cu cât rata de utilizare a echipamentului este mai mare, cu atât cozile rezultate sunt mai lungi. După cum se va arăta mai jos, este posibil să se proiecteze un sistem care să funcționeze satisfăcător cu un factor de utilizare de ρ = 0,7, dar un factor mai mare decât ρ > 0,9 poate duce la o calitate slabă a serviciului. Cu alte cuvinte, dacă o legătură de date în bloc are o încărcare de 20%, este puțin probabil să aibă o coadă pe el. Dacă se încarcă; este 0,9, atunci, de regulă, se vor forma cozi, uneori foarte mari.

Coeficientul de utilizare a echipamentului este egal cu raportul dintre sarcina pe echipament și sarcina maximă pe care o poate suporta acest echipament sau este egal cu raportul dintre timpul de ocupare a echipamentului și timpul total de funcționare a acestuia.

La proiectarea unui sistem, este obișnuit să se estimeze factorul de utilizare pentru diferite tipuri de echipamente; exemple relevante vor fi date în capitolele ulterioare. Cunoașterea acestor coeficienți vă permite să calculați cozile pentru echipamentul corespunzător.

· Care este lungimea cozii?

· Cât timp va dura?

Întrebările de acest tip pot fi răspunse folosind teoria cozilor.

10.6.3. Sisteme de așteptare, clasele și principalele caracteristici ale acestora

Pentru QS, fluxurile de evenimente sunt fluxuri de cereri, fluxuri de cereri de „serviciu” etc. Dacă aceste fluxuri nu sunt Poisson (procesul Markov), descrierea matematică a proceselor care au loc în QS devine incomparabil mai complexă și necesită un aparat mai greoi, aducerea lui la formule analitice este posibilă doar în cazurile cele mai simple.

Cu toate acestea, aparatul teoriei „Markoviane” a stării de așteptare poate fi util și în cazul în care procesul care are loc în QS este diferit de cel Markov; cu ajutorul acestuia, caracteristicile de eficiență QS pot fi estimate aproximativ. Trebuie remarcat faptul că, cu cât QS-ul este mai complex, cu cât conține mai multe canale de servicii, cu atât formulele aproximative obținute folosind teoria Markov sunt mai precise. În plus, într-o serie de cazuri, pentru a lua decizii în cunoștință de cauză privind gestionarea funcționării QS, nu este deloc necesar să se cunoască exact toate caracteristicile acestuia, adesea destul de aproximative, orientative.

QS sunt clasificate în sisteme cu:

eșecuri (cu pierderi). În astfel de sisteme, o solicitare care sosește în momentul în care toate canalele sunt ocupate primește un „refuz”, părăsește QS și nu participă la procesul de service ulterioar.

aşteptare (cu coadă). În astfel de sisteme, o solicitare care sosește atunci când toate canalele sunt ocupate este pusă în coadă și așteaptă până când unul dintre canale devine liber. Când canalul este liber, una dintre aplicațiile din coadă este acceptată pentru service.

Serviciul (disciplina la coadă) într-un sistem de așteptare poate fi

ordonat (cererile sunt comunicate în ordinea primirii),

· dezordonat(cererile sunt depuse în ordine aleatorie) sau

grămadă (ultima aplicație este selectată prima din coadă).

Prioritate

o cu prioritate statica

o cu prioritate dinamică

(în acest din urmă caz ​​a priori tet poate crește, de exemplu, odată cu timpul de așteptare pentru cerere).

Sistemele cu o coadă sunt împărțite în sisteme

· cu așteptare nelimitată și

· cu limitat aşteptare.

În sistemele cu așteptare nelimitată, fiecare solicitare care sosește în momentul în care nu există canale libere intră în coadă și așteaptă „răbdător” eliberarea canalului care o va accepta pentru service. Orice cerere primită de CMO va fi comunicată mai devreme sau mai târziu.

În sistemele cu așteptare limitată, sunt impuse anumite restricții privind rămânerea aplicației în coadă. Aceste restricții se pot aplica

· lungimea cozii (numărul de aplicații simultan în sistemul de cozi cu o lungime limitată a cozii),

· timpul în care aplicația rămâne în coadă (după o anumită perioadă de așteptare, aplicația iese din coadă, iar sistemul pleacă cu un timp de așteptare limitat),

· timpul total petrecut de aplicație în QS

etc.

În funcție de tipul de QS, la evaluarea eficacității acestuia, pot fi utilizate anumite valori (indicatori de performanță). De exemplu, pentru un QS cu defecțiuni, una dintre cele mai importante caracteristici ale productivității sale este așa-numita lățime de bandă absolută numărul mediu de cereri pe care sistemul le poate deservi pe unitatea de timp.

Împreună cu absolutul este adesea considerat debit relativ QS este ponderea medie a cererilor primite deservite de sistem (raportul dintre numărul mediu de cereri deservite de sistem pe unitatea de timp și numărul mediu de cereri primite în acest timp).

Pe lângă debitul absolut și relativ în analiza QS cu eșecuri, putem, în funcție de sarcina studiului, să fim interesați de alte caracteristici, de exemplu:

· numărul mediu de canale ocupate;

· timpul de nefuncționare relativ mediu al sistemului ca întreg și al unui canal individual

etc.

QS-urile așteptate au caracteristici ușor diferite. Evident, pentru un QS cu timp de așteptare nelimitat, atât debitul absolut cât și cel relativ își pierd sensul, deoarece fiecare revendicare ajunge mai devreme.sau mai târziu va fi servit. Pentru un astfel de QS, caracteristicile importante sunt:

· numărul mediu de aplicații din coadă;

· numărul mediu de aplicații din sistem (în coadă și în service);

· timpul mediu de așteptare pentru o aplicație în coadă;

· timpul mediu petrecut de o aplicație în sistem (în coadă și în service);

precum și alte caracteristici ale așteptării.

Pentru un QS cu așteptare limitată, ambele grupuri de caracteristici sunt de interes: atât debitul absolut și relativ, cât și caracteristicile de așteptare.

Pentru a analiza procesul care are loc în QS, este esențial să cunoașteți principalii parametri ai sistemului: numărul de canale P, intensitatea debitului de aplicareλ , performanța fiecărui canal (numărul mediu de cereri μ deservite de canal pe unitatea de timp), condițiile de formare a cozii (restricții, dacă există).

În funcție de valorile acestor parametri, sunt exprimate caracteristicile eficienței operațiunii QS.

10.6.4. Formule pentru calcularea caracteristicilor QS pentru cazul service-ului cu un singur dispozitiv

Figura 0 - 6 Modelul unui sistem de așteptare cu coadă

Astfel de cozi pot fi create prin mesaje la intrarea procesorului care așteaptă să fie procesate. Acestea pot apărea în timpul funcționării stațiilor de abonat conectate la un canal de comunicație multipunct. În mod similar, la benzinării se formează cozi de mașini. Totuși, dacă există mai multe intrări în serviciu, avem o coadă cu multe dispozitive și analiza devine mai complicată.

Luați în considerare cazul celui mai simplu flux de cereri de servicii.

Scopul teoriei de așteptare prezentată este de a aproxima dimensiunea medie a cozii de așteptare, precum și timpul mediu petrecut de mesajele care așteaptă în cozi. De asemenea, este de dorit să se estimeze cât de des coada depășește o anumită lungime. Aceste informații ne vor permite să calculăm, de exemplu, cantitatea necesară de memorie tampon pentru stocarea cozilor de mesaje și a programelor aferente, numărul necesar de linii de comunicație, dimensiunile tampon necesare pentru hub-uri etc. Va fi posibil să se estimeze timpii de răspuns.

Fiecare dintre caracteristici variază în funcție de mijloacele folosite.

Luați în considerare o coadă cu un singur server. La proiectarea unui sistem de calcul, majoritatea cozilor de acest tip sunt calculate folosind formulele de mai sus. factor de variație a timpului de serviciu

Formula Khinchin-Polachek este utilizată pentru a calcula lungimile cozilor în proiectarea sistemelor informaționale. Se folosește în cazul unei distribuții exponențiale a timpului de sosire pentru orice distribuție a timpului de serviciu și orice disciplină de control, atâta timp cât alegerea următorului mesaj pentru serviciu nu depinde de timpul de serviciu.

La proiectarea sistemelor, există astfel de situații când apar cozi când disciplina de control depinde, fără îndoială, de timpul de service. De exemplu, în unele cazuri, putem alege să folosim mai întâi mesaje mai scurte pentru serviciu, pentru a obține un timp mediu de serviciu mai rapid. Atunci când gestionați o linie de comunicație, este posibil să acordați o prioritate mai mare mesajelor de intrare decât mesajelor de ieșire, deoarece primele sunt mai scurte. În astfel de cazuri, nu mai este necesară utilizarea ecuației lui Khinchin

Majoritatea timpilor de service în sistemele informaționale se află undeva între aceste două cazuri. Perioadele de service care sunt constante sunt rare. Chiar și timpul de acces la hard disk nu este constant din cauza poziției diferite a matricelor de date pe suprafață. Un exemplu care ilustrează cazul timpului de serviciu constant este ocuparea liniei de comunicație pentru transmiterea mesajelor de lungime fixă.

Pe de altă parte, răspândirea timpului de serviciu nu este la fel de mare ca în cazul unei distribuții arbitrare sau exponențiale, adică,σs rar atinge valorit s. Acest caz este uneori considerat „cel mai rău caz și, prin urmare, se folosesc formule care se referă la distribuția exponențială a timpilor de serviciu. Un astfel de calcul poate da dimensiuni oarecum supraestimate ale cozilor și timpilor de așteptare în ele, dar această eroare nu este cel puțin periculoasă.

Distribuția exponențială a timpilor de serviciu nu este cu siguranță cel mai rău caz cu care trebuie să se confrunte în realitate. Cu toate acestea, dacă timpii de serviciu obținuți din calculul cozilor se dovedesc a fi mai prost repartizați decât timpii distribuiți exponențial, acesta este adesea un semnal de avertizare pentru dezvoltator. Dacă abaterea standard este mai mare decât valoarea medie, atunci este de obicei necesară corectarea calculelor.

Luați în considerare următorul exemplu. Există șase tipuri de mesaje cu timpi de serviciu de 15, 20, 25, 30, 35 și 300. Numărul de mesaje pentru fiecare tip este același. Abaterea standard a acestor timpi este ceva mai mare decât media lor. Valoarea ultimului timp de service este mult mai mare decât celelalte. Acest lucru va face ca mesajele să fie în coadă mult mai mult decât dacă timpii de service ar fi de aceeași ordine. În acest caz, la proiectare, este indicat să luați măsuri pentru a reduce lungimea cozii. De exemplu, dacă aceste numere sunt legate de lungimea mesajelor, atunci poate că mesajele foarte lungi ar trebui împărțite în părți.

10.6.6. Exemplu de calcul

La proiectarea unui sistem bancar, este de dorit să se cunoască numărul de clienți care vor trebui să stea la coadă pentru un casier în orele de vârf.

Timpul de răspuns al sistemului și abaterea sa standard sunt calculate luând în considerare timpul de introducere a datelor de la stația de lucru, imprimare și procesare a documentelor.

Acțiunile casieriei au fost cronometrate. Timpul de serviciu ts este egal cu timpul total petrecut de casier pe client. Rata de utilizare a casierului ρ este proporţională cu timpul angajării acestuia. Dacă λ este numărul de clienți în orele de vârf, atunci ρ pentru casierie este

Să presupunem că sunt 30 de clienți pe oră în orele de vârf. În medie, un casier petrece 1,5 minute per client. Apoi

ρ = (1,5 * 30) / 60 = 0,75

adică casieria este folosită de 75%.

Numărul de oameni în rând poate fi estimat rapid folosind grafice. Din ele rezultă că dacă ρ = 0,75, atunci numărul mediu nq de oamenila linie la casă se află între 1,88 și 3,0 în funcție de abaterea standard pt t s .

Să presupunem că măsurarea abaterii standard pentru ts a dat o valoare de 0,5 min. Apoi

σ s = 0,33 t s

Din graficul din prima figură, constatăm că nq = 2,0, adică, în medie, doi clienți vor aștepta la casă.

Timpul total pe care un client îl petrece la casă poate fi găsit ca

t ∑ = t q + t s = 2,5 min + 1,5 min = 4 min

unde t s se calculează folosind formula Khinchin-Polachek.

10.6.7. factor de câștig

Analizând curbele din cifre, vedem că atunci când echipamentul care deservește coada este folosit mai mult de 80%, curbele încep să crească într-un ritm alarmant. Acest fapt este foarte important în proiectarea sistemelor de transmisie a datelor. Dacă proiectăm un sistem cu mai mult de 80% de utilizare a hardware-ului, atunci o ușoară creștere a traficului poate duce la o scădere drastică a performanței sistemului sau chiar la blocarea acestuia.

O creștere a traficului de intrare cu un număr mic de x%. duce la o creștere a dimensiunii cozii cu aproximativ

Dacă rata de utilizare a echipamentului este de 50%, atunci această creștere este egală cu 4ts% pentru distribuția exponențială a timpului de serviciu. Dar dacă utilizarea echipamentului este de 90%, atunci creșterea dimensiunii cozii este de 100%, adică de 25 de ori mai mult. O ușoară creștere a încărcăturii la utilizarea echipamentelor cu 90% duce la o creștere de 25 de ori a dimensiunilor cozilor de așteptare, comparativ cu cazul utilizării echipamentelor cu 50%.

În mod similar, timpul de coadă crește cu

Cu un timp de serviciu distribuit exponențial, această valoare are valoarea 4 t s2 pentru utilizarea echipamentului egală cu 50% și 100 t s2 pentru un coeficient de 90%, adică din nou de 25 de ori mai rău.

În plus, pentru factorii de utilizare a echipamentelor mici, efectul modificărilor σs asupra dimensiunii cozii este nesemnificativ. Cu toate acestea, pentru coeficienți mari, modificarea σ s afectează foarte mult dimensiunea cozii. Prin urmare, atunci când se proiectează sisteme cu utilizare ridicată a echipamentelor, este de dorit să se obțină informații precise despre parametruσ s. Inexactitatea ipotezei privind exponenţialitatea distribuţiei lui tseste cel mai vizibil la valori mari ale lui ρ. Mai mult, dacă timpul de serviciu crește brusc, ceea ce este posibil în canalele de comunicare la transmiterea mesajelor lungi, atunci în cazul unui ρ mare, se formează o coadă semnificativă.

Luat în considerare în prelegerea anterioară, un proces aleator Markov cu stări discrete și timp continuu are loc în sistemele de așteptare (QS).

Sisteme de așteptare - sunt sisteme în care cererile de servicii sunt primite la momente aleatorii, în timp ce cererile primite sunt deservite folosind canalele de servicii disponibile sistemului.

Exemple de sisteme de așteptare sunt:

• noduri de decontare și numerar în bănci, întreprinderi;
• calculatoare personale care servesc aplicații primite sau cerințe pentru rezolvarea anumitor probleme;
• service-uri auto; benzinărie;
• firme de audit;
• departamentele de inspecție fiscală implicate în acceptarea și verificarea raportării curente a întreprinderilor;
• centrale telefonice etc.

	Noduri	Cerințe
Spital	ordinele	Pacienții
Productie
Aeroport	Ieșiri pe pistă Puncte de înregistrare	Pasagerii

Luați în considerare schema de funcționare QS (Fig. 1). Sistemul constă dintr-un generator de cereri, un dispecer și un nod de serviciu, un nod de contabilizare a eșecului (terminator, distrugător de cereri). Un nod de serviciu poate avea în general mai multe canale de servicii.

Orez. unu

1. Generator de aplicații – un obiect care generează aplicații: o stradă, un atelier cu unități instalate. Intrarea este fluxul de aplicare(fluxul de clienți către magazin, fluxul de unități sparte (mașini, mașini-unelte) pentru reparații, fluxul de vizitatori către garderobă, fluxul de mașini către benzinării etc.).
2. Dispecer – o persoană sau un dispozitiv care știe ce să facă cu biletul. Un nod care reglementează și direcționează cererile către canalele de servicii. Dispecer:

• acceptă cereri;
• formează o coadă dacă toate canalele sunt ocupate;
• îi direcționează către canalele de servicii, dacă există;
• refuză cererile (din diverse motive);
• primește informații de la nodul de serviciu despre canalele gratuite;
• ține evidența timpului sistemului.

1. Întoarce-te - cere acumulator. Este posibil ca coada să nu existe.
2. Nod de serviciu constă dintr-un număr finit de canale de servicii. Fiecare canal are 3 stări: liber, ocupat, inactiv. Dacă toate canalele sunt ocupate, atunci puteți veni cu o strategie cui să transferați aplicația.
3. Refuz de la serviciu apare dacă toate canalele sunt ocupate (unele dintre ele pot să nu funcționeze).

Pe lângă aceste elemente de bază în QS, unele surse disting și următoarele componente:

terminator - distrugător de tranzacții;

depozit - depozitarea resurselor și a produselor finite;

cont contabil - pentru efectuarea operațiunilor de tip „înregistrare”;

manager - manager de resurse;

Clasificarea CMO

Prima diviziune (prin prezența cozilor):

• CMO cu eșecuri;
• CMO cu o coadă.

LA CMO cu eșecuri o solicitare care sosește în momentul în care toate canalele sunt ocupate este respinsă, părăsește QS-ul și nu este servită în continuare.

LA CMO cu o coadă o aplicație care ajunge într-un moment în care toate canalele sunt ocupate nu pleacă, ci sta la coadă și așteaptă o oportunitate pentru a fi servită.

QS cu cozi sunt împărțite în diferite tipuri în funcție de modul în care este organizată coada - limitat sau nelimitat. Restricțiile se pot referi atât la lungimea cozii, cât și la timpul de așteptare, „disciplina de serviciu”.

Deci, de exemplu, sunt luate în considerare următoarele QS:

• QS cu cereri nerăbdătoare (lungimea cozii și timpul de service sunt limitate);
• QS cu serviciu prioritar, adică unele aplicații sunt servite în afara rândului etc.

Tipurile de restricții la coadă pot fi combinate.

O altă clasificare împarte OCM în funcție de sursa aplicațiilor. Sistemul în sine sau un mediu extern care există independent de sistem poate genera aplicații (cerințe).

Desigur, fluxul de cereri generate de sistemul însuși va depinde de sistem și de starea acestuia.

În plus, SMO-urile sunt împărțite în deschis CMO și închis SMO.

Într-un QS deschis, caracteristicile fluxului de aplicații nu depind de starea QS-ului în sine (cate canale sunt ocupate). Într-un QS închis, ele depind. De exemplu, dacă un muncitor întreține un grup de mașini care din când în când necesită ajustare, atunci intensitatea fluxului de „cerințe” de la mașini depinde de câte dintre ele sunt deja în stare bună și așteaptă ajustarea.

Un exemplu de sistem închis: eliberarea unui salariu de către un casier la o întreprindere.

După numărul de canale, QS-urile sunt împărțite în:

• cu un singur canal;
• multicanal.

Caracteristicile sistemului de aşteptare

Principalele caracteristici ale unui sistem de așteptare de orice fel sunt:

• fluxul de intrare al cerințelor primite sau al solicitărilor de servicii;
• disciplina la coada;
• mecanism de service.

Flux de intrare de cerințe

Pentru a descrie fluxul de intrare, trebuie să setați o lege probabilistică care determină succesiunea momentelor de primire a cerințelor de serviciu,și indicați numărul de astfel de cereri în fiecare chitanță obișnuită. În acest caz, de regulă, ele operează cu conceptul de „repartizare probabilistică a momentelor de primire a cerințelor”. Aici poți acționa ca cerințe individuale și de grup (numărul de astfel de creanțe în fiecare chitanță succesivă). În acest din urmă caz, vorbim de obicei despre un sistem de așteptare cu serviciu de grup paralel.

A i– timpul de sosire între cerințe – variabile aleatoare independente distribuite identic;

E(A) este ora medie de sosire (MO);

λ=1/E(A)- intensitatea primirii cerinţelor;

Caracteristicile fluxului de intrare:

1. O lege probabilistică care determină succesiunea momentelor de primire a cerințelor de serviciu.
2. Numărul de cereri din fiecare sosire următoare pentru fluxuri multicast.

Disciplina la coada

Întoarce-te - un set de cerințe care așteaptă să fie deservite.

Coada are un nume.

Disciplina la coada determină principiul conform căruia cererile care ajung la intrarea sistemului de service sunt conectate din coadă la procedura de service. Cele mai frecvent utilizate discipline de coadă sunt definite de următoarele reguli:

• primul venit, primul servit;

primul intrat primul ieşit (FIFO)

cel mai comun tip de coadă.

Ce structură de date este potrivită pentru a descrie o astfel de coadă? Matricea este proastă (limitată). Puteți utiliza o structură LIST.

Lista are un început și un sfârșit. Lista constă din intrări. O intrare este o celulă de listă. Aplicația ajunge la sfârșitul listei și este selectată pentru service de la începutul listei. Intrarea constă dintr-o descriere a aplicației și un link (un index al cine se află în spatele acesteia). În plus, dacă coada are o limită de timp, atunci trebuie specificată și limita de timp.

Voi, ca programatori, ar trebui să puteți face liste cu două fețe, unilaterale.

Listează acțiuni:

• introduceți în coadă;
• ia de la început;
• eliminați din listă după expirarea timpului.
• ultimul venit, primul servit LIFO (clemă pentru cartuş, fundătură la gară, a intrat într-o maşină plină).

O structură cunoscută sub numele de STACK. Poate fi descris printr-o structură matrice sau listă;

• selecția aleatorie a aplicațiilor;
• selectarea cererilor pe criteriu de prioritate.

Fiecare aplicație se caracterizează, printre altele, printr-un nivel de prioritate și, la sosire, este plasată nu la coada cozii, ci la sfârșitul grupului său de prioritate. Dispeceratul sortează după prioritate.

Caracteristicile cozii

• prescripţietimp de asteptare momentul apariției serviciului (există o coadă cu un timp limitat de așteptare pentru serviciu, care este asociat cu conceptul de „lungime admisibilă a cozii”);
• lungimea cozii.

Mecanism de service

Mecanism de service este determinată de caracteristicile procedurii de service în sine și de structura sistemului de servicii. Procedurile de service includ:

• numărul de canale de servicii ( N);
• durata procedurii de service (distribuirea probabilistică a duratei de serviciu a cerinţelor);
• numărul de cerințe îndeplinite ca urmare a implementării fiecărei astfel de proceduri (pentru aplicațiile de grup);
• probabilitatea de defecțiune a canalului de servire;
• structura sistemului de servicii.

Pentru o descriere analitică a caracteristicilor procedurii de service se utilizează conceptul de „distribuție probabilistică a timpului de serviciu al cerințelor”.

Si– timpul de service i a-a cerință;

E(S)– timpul mediu de service;

μ=1/E(S)- viteza de solicitare a serviciului.

Trebuie remarcat faptul că timpul pentru deservirea unei aplicații depinde de natura aplicației în sine sau de cerințele clientului și de starea și capacitățile sistemului de service. În unele cazuri este de asemenea necesar să se țină cont probabilitatea de defectare a canalului de serviciu după un anumit interval de timp limitat. Această caracteristică poate fi modelată ca un flux de eșecuri care intră în QS și au prioritate față de toate celelalte solicitări.

Factor de utilizare QS

Nμ – rata de service în sistem când toate dispozitivele de service sunt ocupate.

ρ=λ/( Nμ) se numește Factor de utilizare QS , arată câte resurse de sistem sunt utilizate.

Structura sistemului de servicii

Structura sistemului de servicii este determinată de numărul și aranjarea reciprocă a canalelor de servicii (mecanisme, dispozitive etc.). În primul rând, trebuie subliniat că un sistem de servicii poate avea nu un canal de servicii, ci mai multe; un sistem de acest fel este capabil să satisfacă mai multe cerinţe simultan. În acest caz, toate canalele de servicii oferă aceleași servicii și, prin urmare, se poate susține că există serviciu paralel .

Exemplu. Case de marcat in magazin.

Sistemul de servicii poate consta din mai multe tipuri diferite de canale de servicii prin care trebuie să treacă fiecare cerință de service, adică în sistemul de servicii procedurile de service al cerințelor sunt implementate secvenţial . Mecanismul serviciului definește caracteristicile fluxului de cereri de ieșire (servite).

Exemplu. Comisia medicală.

Serviciu combinat - deservirea depozitelor la banca de economii: mai întâi controlorul, apoi casierul. De regulă, 2 controlori per casier.

Asa de, funcționalitatea oricărui sistem de așteptare este determinată de următorii factori principali :

• repartizarea probabilistica a momentelor de primire a cererilor de servicii (singure sau grup);
• cerinţe de capacitate sursă;
• distribuția probabilistică a duratei serviciului;
• configurarea sistemului de servicii (serviciu paralel, serial sau paralel-serial);
• numărul și performanța canalelor de difuzare;
• disciplina la coada.

Principalele criterii de eficacitate a funcționării QS

La fel de principalele criterii de eficacitate a funcţionării sistemelor de aşteptare În funcție de natura problemei care se rezolvă, pot exista:

• probabilitatea de deservire imediată a aplicației primite (serviciu P =K obs /K post);
• probabilitatea de refuzare a serviciului cererii primite (P otk =K otk /K post);

Este evident că R obl + P otk =1.

Fluxuri, întârzieri, service. Formula Pollacek-Khinchin

Întârziere – unul dintre criteriile serviciului QS, timpul petrecut de cerere în anticiparea serviciului.

D i– întârziere în coada de cereri i;

W i \u003d D i + S i– timpul petrecut în sistemul cerinței i.

(cu probabilitatea 1) este întârzierea medie stabilită a unei cereri în coadă;

(cu probabilitatea 1) este timpul mediu în stare de echilibru pe care cerința îl petrece în QS (în așteptare).

Q(t) - numărul de cereri din coadă la un moment dat t;

L(t)– numărul de clienți în sistem simultan t(Q(t) plus numărul de cerințe care sunt în serviciu la momentul respectiv t.

Apoi exponenți (dacă există)

(cu probabilitatea 1) este numărul mediu de cereri în stare de echilibru în coadă;

(cu probabilitatea 1) este numărul mediu de cereri în stare de echilibru din sistem.

Rețineți că ρ<1 – обязательное условие существования d, w, Qși Lîn sistemul de aşteptare.

Dacă ne amintim că ρ= λ/( Nμ), atunci este clar că dacă intensitatea primirii cererilor este mai mare decât Nμ, apoi ρ>1, și este firesc ca sistemul să nu poată face față unui astfel de flux de aplicații și, prin urmare, nu se poate vorbi de d, w, Qși L.

Cele mai generale și necesare rezultate pentru sistemele de așteptare includ ecuațiile de conservare

Trebuie remarcat faptul că criteriile de mai sus pentru evaluarea performanței sistemului pot fi calculate analitic pentru sistemele de așteptare. M/M/N(N>1), adică sisteme cu fluxuri Markov de clienți și servicii. Pentru M/G/ l pentru orice distribuție Gși pentru alte sisteme. În general, distribuția timpului între sosiri, distribuția timpului de serviciu sau ambele trebuie să fie exponențială (sau un fel de distribuție Erlang exponențială de ordinul k) pentru ca o soluție analitică să fie posibilă.

În plus, puteți vorbi și despre caracteristici precum:

• debitul absolut al sistemului – А=Р serviciu *λ;
• debitul relativ al sistemului -

Un alt exemplu interesant (și ilustrativ) de soluție analitică – calculul întârzierii medii la cozi de aşteptare pentru un sistem de aşteptare M/G/ 1 după formula:

.

În Rusia, această formulă este cunoscută ca formula Pollacek. – Khinchin, în străinătate această formulă este asociată cu numele de Ross.

Astfel, dacă E(S) are o valoare mai mare, apoi suprasarcina (măsurată în acest caz ca d) va fi mai mare; ceea ce este de așteptat. Formula relevă și un fapt mai puțin evident: aglomerația crește și atunci când variabilitatea distribuției timpului de serviciu crește, chiar dacă timpul mediu de serviciu rămâne același. Intuitiv, acest lucru poate fi explicat după cum urmează: variația variabilei aleatoare a timpului de service poate lua o valoare mare (deoarece trebuie să fie pozitivă), adică singurul dispozitiv de service va fi ocupat mult timp, ceea ce va duce la o creștere în coada de așteptare.

Subiectul teoriei cozilor este de a stabili relația dintre factorii care determină funcționalitatea sistemului de așteptare și eficiența funcționării acestuia. În cele mai multe cazuri, toți parametrii care descriu sistemele de așteptare sunt variabile sau funcții aleatorii, astfel încât aceste sisteme sunt denumite sisteme stocastice.

Natura aleatorie a fluxului de aplicații (cerințe), precum și, în cazul general, durata serviciului duce la faptul că în sistemul de așteptare are loc un proces aleatoriu. Prin natura procesului aleator care apar într-un sistem de așteptare (QS) se disting Sisteme Markov și non-Markov . În sistemele Markov, fluxul de cereri de intrare și fluxul de ieșire de cereri deservite (revendicări) sunt Poisson. Fluxurile Poisson facilitează descrierea și construirea unui model matematic al unui sistem de așteptare. Aceste modele au soluții destul de simple, astfel încât cele mai multe dintre aplicațiile binecunoscute ale teoriei cozilor de așteptare folosesc schema Markov. În cazul proceselor non-markoviene, problemele studierii sistemelor de coadă devin mult mai complicate și necesită utilizarea modelării statistice, a metodelor numerice folosind un calculator.

O clasă mare de sisteme care sunt greu de studiat analitic, dar care sunt bine studiate prin metode de modelare statistică, se reduce la sisteme de așteptare (QS).

SMO implică că există căi de probă(canale de servicii) prin care aplicatii. Se obișnuiește să se spună că aplicațiile servit canale. Canalele pot fi diferite ca scop, caracteristici, pot fi combinate în diferite combinații; aplicațiile pot fi în cozi și în așteptare pentru service. O parte din aplicații pot fi deservite de canale, iar unele pot refuza să facă acest lucru. Este important ca cererile, din punct de vedere al sistemului, să fie abstracte: asta se dorește să fie deservit, adică să parcurgă un anumit drum în sistem. Canalele sunt, de asemenea, o abstractizare: ele sunt cele care servesc cererile.

Aplicațiile pot veni neuniform, canalele pot servi diferite aplicații în momente diferite și așa mai departe, numărul de aplicații este întotdeauna foarte mare. Toate acestea fac ca astfel de sisteme să fie dificil de studiat și de gestionat și nu este posibil să urmăriți toate relațiile cauzale din ele. Prin urmare, este acceptată ideea că întreținerea în sisteme complexe este aleatorie.

Exemple de QS (a se vedea Tabelul 30.1) sunt: ​​ruta de autobuz și transportul de pasageri; transportoare de producție pentru prelucrarea pieselor; o escadrilă de avioane care zboară pe teritoriu străin, care este „servită” de tunuri antiaeriene de apărare aeriană; țeava și cornul mitralierei, care „servesc” cartușele; sarcini electrice care se deplasează într-un dispozitiv etc.

Tabelul 30.1. Exemple de sisteme de așteptare

Aplicații Canale Ruta cu autobuzul si transportul pasagerilor Pasagerii Autobuze Transportor de productie pentru prelucrarea pieselor Detalii, noduri Masini-unelte, depozite O escadrilă de avioane care zboară pe un teritoriu străin, care este „deservită” de tunuri antiaeriene de apărare aeriană Avioane Tunuri antiaeriene, radare, săgeți, obuze Țava și cornul mitralierei, care „servesc” cartușele Butoi, corn Sarcini electrice care se deplasează într-un dispozitiv Cascade dispozitive tehnice

Dar toate aceste sisteme sunt combinate într-o singură clasă de QS, deoarece abordarea studiului lor este aceeași. Constă în faptul că, în primul rând, cu ajutorul unui generator de numere aleatorii, sunt redate numere aleatorii, care imită momentele RANDOM ale apariției aplicațiilor și timpul de servire a acestora în canale. Dar luate împreună, aceste numere aleatorii sunt, desigur, supuse statistic modele.

De exemplu, să spunem: „aplicațiile vin în medie în cantitate de 5 bucăți pe oră”. Aceasta înseamnă că intervalele dintre sosirea a două revendicări învecinate sunt aleatorii, de exemplu: 0,1; 0,3; 0,1; 0,4; 0,2, așa cum se arată în Fig. 30,1, dar în total dau o medie de 1 (rețineți că în exemplu acesta nu este exact 1, ci 1,1 - dar într-o altă oră această sumă, de exemplu, poate fi egală cu 0,9); doar daca pentru un timp suficient de lung media acestor numere se va apropia de o oră.

Rezultatul (de exemplu, debitul sistemului), desigur, va fi, de asemenea, o variabilă aleatorie pe intervale de timp separate. Dar măsurată pe o perioadă lungă de timp, această valoare va corespunde deja, în medie, soluției exacte. Adică, pentru a caracteriza QS, ei sunt interesați de răspunsuri în sens statistic.

Deci, sistemul este testat cu semnale aleatorii de intrare supuse unei anumite legi statistice și, ca urmare, indicatorii statistici sunt luați în medie pe timpul luat în considerare sau după numărul de experimente. Mai devreme, în prelegeri 21(cm. orez. 21.1), am dezvoltat deja o schemă pentru un astfel de experiment statistic (vezi Fig. 30.2).

În al doilea rând, toate modelele QS sunt asamblate într-un mod tipic dintr-un set mic de elemente (canal, sursă de solicitare, coadă, cerere, disciplină de serviciu, stivă, inel și așa mai departe), ceea ce permite simularea acestor sarcini. tipic manieră. Pentru a face acest lucru, modelul de sistem este asamblat de la constructorul unor astfel de elemente. Nu contează ce sistem anume este studiat, este important ca diagrama sistemului să fie asamblată din aceleași elemente. Desigur, structura circuitului va fi întotdeauna diferită.

Să enumerăm câteva concepte de bază ale QS.

Canalele sunt ceea ce servește; sunt fierbinți (încep să deservească cererea în momentul în care aceasta intră în canal) și reci (canalul are nevoie de timp pentru a se pregăti pentru a începe service-ul). Surse de solicitari - genereaza cereri in momente aleatorii, conform unei legi statistice specificate de utilizator. Aplicațiile, sunt și clienți, intră în sistem (generat de sursele aplicațiilor), trec prin elementele acestuia (servite), îl lasă servit sau nemulțumit. Sunt aplicații nerăbdătoare – cei care s-au săturat să aștepte sau să fie în sistem și care părăsesc CMO-ul de bună voie. Aplicații formează fluxuri - un flux de aplicații la intrarea sistemului, un flux de aplicații deservite, un flux de aplicații respinse. Fluxul se caracterizează prin numărul de aplicații de un anumit tip, observat într-un anumit loc al QS pe unitatea de timp (oră, zi, lună), adică debitul este o valoare statistică.

Cozile se caracterizează prin regulile de așteptare (disciplina de serviciu), numărul de locuri în coadă (câți clienți pot fi în coadă cel mult), structura cozii (conexiunea dintre locurile din coadă). Există cozi limitate și nelimitate. Să enumerăm cele mai importante discipline de serviciu. FIFO (First In, First Out - first in, first out): dacă aplicația este prima care intră în coadă, atunci va fi prima care va pleca în service. LIFO (Last In, First Out - last in, first out): dacă aplicația a fost ultima din coadă, atunci va fi prima care va merge la service (de exemplu, cartușe în claxonul mașinii). SF (Short Forward - short forward): acele aplicații din coadă care au cel mai scurt timp de serviciu sunt servite primele.

Să dăm un exemplu izbitor care arată cum alegerea corectă a uneia sau alteia discipline de servicii vă permite să obțineți economii de timp concrete.

Să fie două magazine. În magazinul nr. 1, serviciul este efectuat pe principiul primul venit, primul servit, adică aici este implementată disciplina de servicii FIFO (vezi Figura 30.3).

Timp de service t serviciu în fig. 30.3 arată cât timp va petrece vânzătorul pentru deservirea unui cumpărător. Este clar că atunci când cumpără mărfuri cu bucată, vânzătorul va petrece mai puțin timp pentru serviciu decât atunci când cumpără, să zicem, produse în vrac care necesită manipulări suplimentare (ridicarea, cântărirea, calcularea prețului etc.). Timp de asteptare t așteptat arată, după ce oră următorul cumpărător va fi servit de vânzător.

Magazinul #2 implementează disciplina SF (vezi Figura 30.4), ceea ce înseamnă că mărfurile piese pot fi cumpărate la rândul lor, din timpul serviciului t serviciu o astfel de achiziție este mică.

După cum se poate observa din ambele cifre, ultimul (al cincilea) cumpărător urmează să cumpere o bucată de bunuri, astfel încât timpul de serviciu este mic - 0,5 minute. Dacă acest client vine în magazinul numărul 1, va fi obligat să stea la coadă 8 minute întregi, în timp ce în magazinul numărul 2 va fi servit imediat, fără rând. Astfel, timpul mediu de service pentru fiecare dintre clienții dintr-un magazin cu disciplină de service FIFO va fi de 4 minute, iar într-un magazin cu disciplină de service FIFO, va fi de doar 2,8 minute. Iar în beneficiul public, economiile de timp vor fi: (1 - 2,8/4) · 100% = 30 la sută! Deci, 30% din timp economisit pentru societate - și acest lucru se datorează doar alegerii corecte a disciplinei de serviciu.

Specialistul în sisteme trebuie să aibă o bună înțelegere a resurselor de performanță și eficiență ale sistemelor pe care le proiectează, ascunse în optimizarea parametrilor, structurilor și disciplinelor de întreținere. Modelarea ajută la dezvăluirea acestor rezerve ascunse.

Atunci când se analizează rezultatele simulării, este de asemenea important să se indice interesele și gradul de implementare a acestora. Distingeți între interesele clientului și interesele proprietarului sistemului. Rețineți că aceste interese nu coincid întotdeauna.

Puteți judeca rezultatele activității CMO după indicatori. Cele mai populare dintre ele:

probabilitatea de servicii pentru clienți de către sistem;

debitul sistemului;

probabilitatea refuzului serviciului către client;

probabilitatea de ocupare a fiecărui canal și a tuturor împreună;

timpul mediu ocupat al fiecărui canal;

probabilitatea de ocupare a tuturor canalelor;

numărul mediu de canale ocupate;

probabilitatea de oprire a fiecărui canal;

probabilitatea de oprire a întregului sistem;

numărul mediu de aplicații din coadă;

timpul mediu de așteptare pentru o aplicație în coadă;

timpul mediu de serviciu al aplicației;

timpul mediu petrecut de aplicație în sistem.

Este necesar să se judece calitatea sistemului rezultat în funcție de totalitatea valorilor indicatorilor. Atunci când se analizează rezultatele (indicatorilor) simulării, este important să se acorde atenție intereselor clientului și intereselor proprietarului sistemului, adică este necesar să se minimizeze sau să maximizeze acest sau acel indicator, precum și gradul a implementării lor. Rețineți că cel mai adesea interesele clientului și ale proprietarului nu coincid între ele sau nu coincid întotdeauna. Indicatorii vor fi indicați în continuare H = { h 1 , h 2 , …} .

Parametrii QS pot fi: intensitatea fluxului de aplicații, intensitatea fluxului de serviciu, timpul mediu în care aplicația este pregătită să aștepte serviciul în coadă, numărul de canale de servicii, disciplina serviciului și curând. Parametrii sunt cei care afectează performanța sistemului. Parametrii vor fi notați mai jos ca R = { r 1 , r 2 , …} .

Exemplu. Benzinărie (benzinărie).

1. Enunțarea problemei. Pe fig. 30.5 arată planul benzinăriei. Să luăm în considerare metoda de modelare QS pe exemplul ei și pe planul cercetării sale. Șoferii care trec pe lângă benzinăriile de pe drum ar putea dori să-și umple mașina. Nu toți șoferii la rând doresc să fie întreținuți (alimentați mașina cu benzină); Să zicem că din întregul flux de mașini vin în medie 5 mașini pe oră la benzinărie.

La benzinărie există două dozatoare identice, performanța statistică a fiecăruia dintre ele fiind cunoscută. Prima coloană deservește în medie 1 mașină pe oră, a doua în medie - 3 mașini pe oră. Proprietarul benzinăriei a asfaltat un loc pentru mașini unde pot aștepta service-ul. Dacă coloanele sunt ocupate, alte mașini pot aștepta service în acest loc, dar nu mai mult de două odată. Coada va fi considerată generală. De îndată ce una dintre coloane devine liberă, prima mașină din coadă își poate lua locul pe coloană (în acest caz, a doua mașină se deplasează pe primul loc în coadă). Dacă apare o a treia mașină și toate locurile (două dintre ele) din coadă sunt ocupate, atunci serviciul este refuzat, deoarece este interzis să stați pe drum (vezi indicatoarele rutiere în apropierea benzinăriilor). O astfel de mașină părăsește sistemul pentru totdeauna și, ca potențial client, este pierdută pentru proprietarul benzinăriei. Puteți complica sarcina luând în considerare casa de marcat (un alt canal de servicii, unde trebuie să ajungeți după ce ați servit într-una dintre coloane) și coada la aceasta și așa mai departe. Dar, în cea mai simplă versiune, este evident că căile de flux ale aplicațiilor prin QS pot fi descrise ca o diagramă echivalentă, iar prin adăugarea valorilor și a denumirilor caracteristicilor fiecărui element al QS, obținem în sfârșit diagrama prezentat în Fig. 30.6.

2. Metoda de cercetare a QS. În exemplul nostru, vom aplica principiul postării secvențiale a cererilor (pentru detalii despre principiile modelării, vezi Fig. prelegerea 32). Ideea lui este ca aplicatia sa fie transportata prin intregul sistem de la intrare pana la iesire, si abia dupa aceea se incepe modelarea urmatoarei aplicatii.

Pentru claritate, vom construi o diagramă de timp a operațiunii QS, reflectând pe fiecare riglă (axa timpului t) starea unui element individual al sistemului. Există atâtea cronologie câte locuri sunt diferite în QS, fluxuri. În exemplul nostru, există 7 dintre ele (fluxul de cereri, fluxul de așteptare pe primul loc în coadă, fluxul de așteptare pe locul doi în coadă, fluxul de servicii în canalul 1, fluxul de servicii în canalul 2, fluxul de cereri deservite de sistem, fluxul de cereri refuzate).

Pentru a genera ora de sosire a cererilor, folosim formula de calcul a intervalului dintre momentele de sosire a două evenimente aleatoare (vezi Fig. prelegerea 28):

În această formulă, cantitatea de flux λ trebuie specificat (înainte de aceasta, trebuie determinat experimental pe obiect ca medie statistică), r- număr aleatoriu distribuit uniform de la 0 la 1 din RNG sau Mese, în care numerele aleatorii trebuie luate pe rând (fără a alege special).

O sarcină. Generați un flux de 10 evenimente aleatoare cu o rată a evenimentelor de 5 evenimente pe oră.

Rezolvarea problemei. Să luăm numere aleatoare distribuite uniform în intervalul de la 0 la 1 (vezi Fig. masa) și calculați logaritmii lor naturali (vezi Tabelul 30.2).

Tabelul 30.2. Fragment dintr-un tabel de numere aleatoare și logaritmii lor

r pp ln(r pp )

Formula fluxului Poisson definește distanța dintre două evenimente aleatoare după cum urmează: t= –Ln(r рр)/ λ . Atunci, având în vedere că λ = 5 , avem distanțele dintre două evenimente aleatoare vecine: 0,68, 0,21, 0,31, 0,12 ore. Adică apar evenimente: primul - la un moment dat t= 0 , al doilea - la momentul de timp t= 0,68, al treilea - la momentul respectiv t= 0,89, al patrulea - la timp t= 1,20, a cincea - la timp t= 1,32 și așa mai departe. Evenimente - sosirea aplicațiilor se va reflecta pe prima linie (vezi Fig. 30.7).

Orez. 30.7. Diagrama temporală a funcționării QS

Prima solicitare este preluată și, întrucât canalele sunt libere în acest moment, este setat pentru service pe primul canal. Aplicația 1 este transferată pe linia „1 canal”.

Timpul de serviciu în canal este, de asemenea, aleatoriu și este calculat folosind o formulă similară:

unde rolul intensităţii este jucat de mărimea fluxului de serviciu μ 1 sau μ 2, în funcție de canalul care deservește cererea. Momentul încheierii serviciului îl găsim pe diagramă, amânând timpul de serviciu generat din momentul începerii serviciului și coborâm cererea la linia „Servit”.

Aplicația a trecut prin CMO până la capăt. Acum este posibil, conform principiului postării secvențiale a comenzilor, să se simuleze și calea celui de-al doilea ordin.

Dacă la un moment dat se dovedește că ambele canale sunt ocupate, atunci cererea ar trebui să fie plasată în coadă. Pe fig. 30.7 este cererea cu numărul 3. Rețineți că, conform condițiilor sarcinii, în coadă, spre deosebire de canale, cererile nu sunt localizate aleatoriu, ci așteaptă ca unul dintre canale să devină liber. După eliberarea canalului, cererea este mutată pe linia canalului corespunzător și deservirea acesteia este organizată acolo.

Dacă toate locurile din coadă în momentul sosirii următoarei aplicații sunt ocupate, atunci cererea trebuie trimisă la linia „Refusă”. Pe fig. 30.7 este oferta numărul 6.

Procedura de simulare a deservirii cererilor este continuata un timp de observatie T n. Cu cât acest timp este mai lung, cu atât rezultatele simulării vor fi mai precise în viitor. În realitate, pentru sisteme simple alege T n, egal cu 50-100 sau mai multe ore, deși uneori este mai bine să măsurați această valoare prin numărul de aplicații luate în considerare.

Studiul analitic al sistemelor de așteptare (QS) este o abordare alternativă a modelării simulării și constă în obținerea de formule pentru calcularea parametrilor de ieșire ai QS cu înlocuirea ulterioară a valorilor argumentului în aceste formule în fiecare experiment individual.

În modelele QS, sunt luate în considerare următoarele obiecte:

1) cereri de servicii (tranzacții);

2) dispozitive de serviciu (OA) sau dispozitive.

Sarcina practică a teoriei cozilor este legată de studiul operațiilor efectuate de aceste obiecte și constă din elemente separate care sunt influențate de factori aleatori.

Ca exemplu al problemelor avute în vedere în teoria cozilor de aşteptare, se pot cita: potrivirea debitului unei surse de mesaj cu un canal de transmisie a datelor, analiza fluxului optim de transport urban, calcularea capacităţii unei săli de aşteptare pentru pasageri dintr-un aeroport. , etc.

Solicitarea poate fi fie în starea de serviciu, fie în starea de service în așteptare.

Dispozitivul de service poate fi fie ocupat cu service, fie gratuit.

Starea QS este caracterizată de un set de stări ale dispozitivelor și solicitărilor de serviciu. Schimbarea stărilor în QS se numește eveniment.

Modelele QS sunt folosite pentru a studia procesele care au loc în sistem, atunci când sunt aplicate intrărilor fluxurilor de aplicații. Aceste procese sunt o succesiune de evenimente.

Cei mai importanți parametri de ieșire ai QS

Performanţă

Lățimea de bandă

Probabilitatea de refuzare a serviciului

Durata medie de service;

Factorul de sarcină al echipamentului (OA).

Aplicațiile pot fi comenzi pentru producția de produse, sarcini rezolvate într-un sistem informatic, clienți în bănci, mărfuri care sosesc pentru transport etc. Este evident că parametrii aplicațiilor care intră în sistem sunt variabile aleatorii și doar parametrii acestora pot fi cunoscuți pe parcursul cercetare sau proiectare.legi de distribuţie.

În acest sens, analiza funcționării la nivel de sistem este, de regulă, de natură statistică. Este convenabil să luăm teoria stării de așteptare ca instrument de modelare matematică și să folosiți sistemele de așteptare ca modele de sisteme la acest nivel.

Cele mai simple modele QS

În cel mai simplu caz, QS-ul este un dispozitiv numit service device (OA), cu cozi de aplicații la intrări.

M o d e l o n s e r e n t e r e s e n c a ţie (Fig. 5.1)

Orez. 5.1. Model QS cu defecțiuni:

0 – sursa cererii;

1 - dispozitiv de service;

A– fluxul de intrare al cererilor de serviciu;

în este fluxul de ieșire al cererilor deservite;

Cu este fluxul de ieșire al cererilor neservite.

În acest model, nu există un acumulator de revendicare la intrarea OA. Dacă o revendicare sosește de la sursa 0 în momentul în care AA este ocupat cu repararea revendicării anterioare, atunci revendicarea nou sosită iese din sistem (pentru că i s-a refuzat serviciul) și se pierde (fluxul) Cu).

M o d e l d e c e c r i o n e s e c i r iilor (Fig. 5.2)

Orez. 5.2. Model QS cu așteptări

(N– 1) - numarul de aplicatii care pot incapea in acumulator

Acest model are un acumulator de revendicare la intrarea OA. Dacă un client sosește de la sursa 0 în momentul în care CA este ocupată cu deservirea clientului anterior, atunci clientul nou sosit intră în acumulator, unde așteaptă la nesfârșit până când CA devine liberă.

MODEL DE SERVICIU CU DURĂ LIMITATĂ

w i d a n y (Fig. 5.3)

Orez. 5.4. Model QS multicanal cu defecțiuni:

n- numărul de dispozitive de serviciu (dispozitive) identice

În acest model, nu există un OA, ci mai multe. Cererile, cu excepția cazului în care se specifică altfel, pot fi depuse la orice AB care nu deține servicii. Nu există stocare, așa că acest model include proprietățile modelului prezentat în Fig. 5.1: refuzul serviciului aplicației înseamnă pierderea irecuperabilă a acesteia (acest lucru se întâmplă numai dacă la momentul sosirii acestei aplicații toate OA sunt ocupate).

u a t i n t o m e (Fig. 5.5)

Orez. 5.6. Model QS multicanal cu OA de așteptare și recuperare:

e- dispozitive de service care sunt nefuncționale;

f– vehicule de service restaurate

Acest model are proprietățile modelelor prezentate în Fig. 5.2 și 5.4, precum și proprietățile care permit luarea în considerare a eventualelor defecțiuni aleatorii ale OA, care în acest caz intră în blocul de reparații 2, unde stau perioade aleatorii de timp petrecute la restaurarea lor, iar apoi revin la blocul de servicii 1 din nou.

M i n o n a l m o l l Q O

OA timp de așteptare și recuperare (Fig. 5.7)

Orez. 5.7. Model QS multicanal cu timp limitat de așteptare și recuperare OA

Acest model este destul de complex, deoarece ia în considerare simultan proprietățile a două modele, nu cele mai simple (Figurile 5.5 și 5.6).

Trimiteți-vă munca bună în baza de cunoștințe este simplu. Foloseste formularul de mai jos

Studenții, studenții absolvenți, tinerii oameni de știință care folosesc baza de cunoștințe în studiile și munca lor vă vor fi foarte recunoscători.

postat pe http://allbest.ru

INTRODUCERE

CAPITOLUL 1. PARTEA TEORETICĂ

1.1 Sisteme de așteptare cu defecțiuni

1.2 Modelarea sistemelor de aşteptare

1.3 Cel mai simplu QS cu eșecuri

1.4 QS cu un singur canal cu defecțiuni

1.5 QS multicanal cu defecțiuni

1.6 QS cu un singur canal cu lungime limitată la coadă

1.7 QS cu un singur canal cu coadă nelimitată

1.8 QS multicanal cu lungime limitată la coadă

1.9 QS multicanal cu coadă nelimitată

1.10 Algoritm de modelare QS

CAPITOLUL 2. PARTEA PRACTICĂ

CAPITOLUL 3. REGULAMENTE DE SIGURANȚĂ

CONCLUZIE

LISTA LITERATURII UTILIZATE

INTRODUCERE

Recent, în diverse domenii de practică, a devenit necesară rezolvarea diferitelor probleme probabilistice legate de funcționarea așa-numitelor sisteme de așteptare (QS).

Exemple de astfel de sisteme sunt: ​​centrale telefonice, ateliere de reparații, case de bilete, stații de taxi, coafor etc.

Tema acestui proiect de curs este tocmai soluția unei astfel de probleme.

Totuși, în problema propusă se va investiga un QS, în care sunt luate în considerare 2 fluxuri de aplicații, dintre care unul prioritar.

De asemenea, procesele luate în considerare sunt non-markoviene, deoarece factorul timp este important.

Prin urmare, soluția acestei probleme se bazează nu pe descrierea analitică a sistemului, ci pe modelarea statistică.

Scopul lucrării de curs este de a modela procesul de producție pe baza reprezentării echipamentului principal ca sistem de așteptare.

Pentru atingerea scopului au fost stabilite următoarele sarcini: - Analiza caracteristicilor managementului procesului de producție; - Luați în considerare organizarea în timp a procesului de producție; - Oferiți principalele opțiuni de reducere a duratei ciclului de producție;

Să analizeze metodele de conducere a procesului de producție la întreprindere;

Luați în considerare caracteristicile modelării procesului de producție folosind teoria QS;

Elaborați un model al procesului de producție și evaluați principalele caracteristici ale QS, prezentați perspectivele pentru implementarea ulterioară a software-ului acestuia.

Consolidarea cunoștințelor teoretice și obținerea deprinderilor pentru aplicarea lor practică;

Raportul conține o introducere, trei capitole, o concluzie, o listă de referințe, aplicații.

Al doilea capitol tratează materialele teoretice ale sistemului de așteptare. Și în al treilea calculăm problema sistemelor de așteptare.

CAPITOLUL 1. PARTEA TEORETICĂ

1.1 Sisteme de așteptareceșecuri

Un sistem de așteptare (QS) este orice sistem conceput pentru a răspunde oricăror solicitări (cerințe) care ajung la el în momente aleatorii. Orice dispozitiv care este direct implicat în solicitările de service se numește canal de serviciu (sau „dispozitiv”). CMO-urile sunt atât cu un singur canal, cât și cu mai multe canale.

Există QS cu eșecuri și QS cu o coadă. Într-un QS cu refuzuri, o solicitare care sosește în momentul în care toate canalele sunt ocupate primește un refuz, părăsește QS-ul și apoi nu participă la funcționarea acestuia. Într-un QS cu coadă, o cerere care sosește în momentul în care toate canalele sunt ocupate nu părăsește QS-ul, ci intră în coadă și așteaptă până când un canal devine liber. Numărul de locuri din coada m poate fi atât limitat, cât și nelimitat. Când m=0, un QS cu o coadă se transformă într-un QS cu eșecuri. O coadă poate fi limitată nu numai de numărul de solicitări care se află în ea (lungimea cozii), ci și de timpul de așteptare (astfel de QS-uri sunt numite „sisteme cu clienți nerăbdători”).

Un studiu analitic al unui QS este cel mai simplu dacă toate fluxurile de evenimente care îl transferă de la o stare la alta sunt cele mai simple (Poisson staționar). Aceasta înseamnă că intervalele de timp dintre evenimentele din fluxuri au o distribuție exponențială cu un parametru egal cu intensitatea fluxului corespunzător. Pentru QS, această ipoteză înseamnă că atât fluxul de cereri, cât și fluxul de servicii sunt cele mai simple. Un flux de servicii este înțeles ca un flux de cereri servite una după alta de un canal ocupat continuu. Acest flux se dovedește a fi cel mai simplu doar dacă timpul de serviciu al cererii tservice este o variabilă aleatorie cu o distribuție exponențială. Parametrul acestei distribuții m este reciproca timpului mediu de serviciu:

În loc de expresia „fluxul de service este cel mai simplu”, ei spun adesea „timpul de service este orientativ”. Orice QS în care toate fluxurile sunt simple se numește QS simplu.

Dacă toate fluxurile de evenimente sunt simple, atunci procesul care are loc în QS este un proces aleator Markov cu stări discrete și timp continuu. În anumite condiții pentru acest proces, există un regim staționar final, în care atât probabilitățile stărilor, cât și alte caracteristici ale procesului nu depind de timp.

Modelele QS sunt convenabile pentru descrierea subsistemelor individuale ale sistemelor de calcul moderne, cum ar fi subsistemul procesor-memorie principală, canalul de intrare-ieșire etc.

Sistemul de calcul în ansamblu este un set de subsisteme interconectate, a căror interacțiune este de natură probabilistică. O aplicație pentru rezolvarea unei anumite probleme care intră în sistemul de calcul parcurge o succesiune de etape de numărare, accesând dispozitive de stocare externe și dispozitive de intrare-ieșire.

După finalizarea unei anumite secvențe de astfel de etape, numărul și durata cărora depind de complexitatea programului, cererea este considerată deservită și părăsește sistemul de calcul.

Astfel, sistemul de calcul în ansamblu poate fi reprezentat printr-un set de QS, fiecare dintre acestea afișând procesul de funcționare a unui dispozitiv separat sau a unui grup de dispozitive de același tip care fac parte din sistem.

Sarcinile teoriei cozilor sunt de a găsi probabilitățile diferitelor stări ale QS, precum și de a stabili relația dintre parametrii dați (numărul de canale n, intensitatea fluxului de cereri l, distribuția timpului de serviciu, etc.) și caracteristicile de performanță ale QS. Astfel de caracteristici pot fi considerate, de exemplu, următoarele:

Numărul mediu de aplicații A deservite de QS pe unitatea de timp sau debitul absolut al QS;

Probabilitatea de a deservi cererea de intrare Q sau debitul relativ al QS; Q \u003d A / l;

Probabilitatea de eșec Rothk, adică probabilitatea ca cererea primită să nu fie comunicată și să fie respinsă; Rotk = 1 - Q;

Numărul mediu de aplicații în QS (servite sau în așteptare la coadă);

Numărul mediu de aplicații din coadă;

Timpul mediu petrecut de o aplicație în CMO (în coadă sau în service);

Timpul mediu pe care o aplicație îl petrece în coadă;

Numărul mediu de canale ocupate.

În cazul general, toate aceste caracteristici depind de timp. Dar multe QS-uri funcționează în condiții constante pentru o perioadă destul de lungă și, prin urmare, un regim apropiat de staționar are timp să fie stabilit pentru ele.

Suntem peste tot aici, fără a specifica acest lucru de fiecare dată în mod specific, vom calcula probabilitățile finale ale stărilor și caracteristicile finale ale eficienței QS legate de modul staționar limitator al funcționării acestuia.

Un QS este numit deschis dacă intensitatea fluxului de aplicații de intrare nu depinde de starea QS-ului în sine.

Pentru orice QS deschis în modul staționar de limitare, timpul mediu de rezidență al unui client în sistem este exprimat în termeni de număr mediu de clienți din sistem folosind formula Little:

unde l este intensitatea fluxului de aplicații.

O formulă similară (numită și formula lui Little) raportează timpul mediu petrecut de un bilet într-o coadă și numărul mediu de bilete într-o coadă:

Formulele lui Little sunt foarte utile, deoarece vă permit să calculați nu atât caracteristicile de eficiență (timpul mediu de ședere și numărul mediu de clienți), ci doar unul dintre ele.

Subliniem în mod special că formulele (1) și (2) sunt valabile pentru orice QS deschis (monocanal, multicanal, pentru orice tip de fluxuri de cerere și fluxuri de servicii); singura cerință pentru fluxurile de clienți și serviciile este ca acestea să fie staționare.

În mod similar, formula care exprimă numărul mediu de canale ocupate prin lățimea de bandă absolută A are o valoare universală pentru QS deschis:

unde este intensitatea fluxului de servicii.

Foarte multe probleme ale teoriei cozii de aşteptare, referitoare la cel mai simplu QS, sunt rezolvate folosind schema morţii şi reproducerii.

Probabilitățile finale ale stărilor sunt exprimate prin formulele:

Sul caracteristicile sistemelor de așteptare pot fi reprezentate după cum urmează:

· timpul mediu de service;

timpul mediu de așteptare la coadă;

Timpul mediu petrecut în SMO;

Lungimea medie a cozii

· numărul mediu de cereri în CMO;

numărul de canale de servicii;

intensitatea fluxului de intrare al aplicațiilor;

intensitatea serviciului;

intensitatea sarcinii;

Factor de încărcare

Debit relativ;

Debitul absolut

ponderea timpului de nefuncţionare QS;

ponderea aplicațiilor deservite;

proporția cererilor pierdute;

numărul mediu de canale ocupate;

numărul mediu de canale gratuite;

factorul de încărcare a canalului;

timpul mediu de inactivitate al canalelor.

1 . 2 Modelarea sistemelor de asteptare

Tranzițiile QS de la o stare la alta au loc sub influența unor evenimente bine definite - primirea aplicațiilor și service-ul acestora. Secvența de apariție a evenimentelor care urmează unul după altul în momente aleatorii de timp formează așa-numitul flux de evenimente. Exemple de astfel de fluxuri în activități comerciale sunt fluxurile de natură variată - mărfuri, bani, documente, transport, clienți, clienți, apeluri telefonice, negocieri. Comportamentul sistemului este de obicei determinat nu de unul, ci de mai multe fluxuri de evenimente simultan. De exemplu, serviciul pentru clienți într-un magazin este determinat de fluxul de clienți și de fluxul de servicii; în aceste fluxuri, momentele de apariție a cumpărătorilor, timpul petrecut la coadă și timpul petrecut în deservirea fiecărui cumpărător sunt aleatorii.

În acest caz, principala trăsătură caracteristică a fluxurilor este distribuția probabilistică a timpului între evenimentele învecinate. Există diverse fluxuri care diferă prin caracteristicile lor.

Un flux de evenimente se numește regulat dacă evenimentele din el urmează unul după altul la intervale de timp predeterminate și strict definite. Un astfel de flux este ideal și este foarte rar în practică. Mai des există fluxuri neregulate care nu au proprietatea de regularitate.

Un flux de evenimente se numește staționar dacă probabilitatea ca orice număr de evenimente să se încadreze într-un interval de timp depinde doar de lungimea acestui interval și nu depinde de cât de departe este situat acest interval de punctul de referință de timp. Staționaritatea unui flux înseamnă că caracteristicile sale probabilistice sunt independente de timp; în special, intensitatea unui astfel de flux este numărul mediu de evenimente pe unitatea de timp și rămâne constantă. În practică, fluxurile pot fi de obicei considerate staționare doar pentru un anumit interval de timp limitat. De obicei, fluxul de clienți, de exemplu, într-un magazin se schimbă semnificativ în timpul zilei de lucru. Cu toate acestea, este posibil să se evidențieze anumite intervale de timp în care acest flux poate fi considerat staționar, având o intensitate constantă.

Un flux de evenimente se numește flux fără consecințe dacă numărul de evenimente care se încadrează pe unul dintre intervalele de timp alese arbitrar nu depinde de numărul de evenimente care se încadrează pe un alt interval, de asemenea, ales arbitrar, cu condiția ca aceste intervale să nu se intersecteze. Într-un flux fără consecințe, evenimentele apar în momente succesive, independent unele de altele. De exemplu, fluxul de clienți care intră într-un magazin poate fi considerat un flux fără consecințe, deoarece motivele care au dus la sosirea fiecăruia dintre ei nu sunt legate de motive similare pentru alți clienți.

Un flux de evenimente se numește obișnuit dacă probabilitatea de a lovi două sau mai multe evenimente simultan pentru o perioadă foarte scurtă de timp este neglijabilă în comparație cu probabilitatea de a atinge un singur eveniment. Într-un flux obișnuit, evenimentele au loc unul câte unul, mai degrabă decât de două sau de mai multe ori. Dacă un flux posedă simultan proprietățile staționarității, ordinarității și absența unei consecințe, atunci un astfel de flux se numește cel mai simplu (sau Poisson) flux de evenimente. Descrierea matematică a impactului unui astfel de flux asupra sistemelor este cea mai simplă. Prin urmare, în special, cel mai simplu flux joacă un rol special printre alte fluxuri existente.

Luați în considerare un interval de timp t pe axa timpului. Să presupunem că probabilitatea ca un eveniment aleator să se încadreze în acest interval este p, iar numărul total de evenimente posibile este n. În prezența proprietății unui flux obișnuit de evenimente, probabilitatea p trebuie să fie o valoare suficient de mică, iar i un număr suficient de mare, deoarece sunt considerate fenomene de masă.

În aceste condiții, pentru a calcula probabilitatea de a atinge un anumit număr de evenimente t într-un interval de timp t, puteți utiliza formula Poisson:

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

unde valoarea a \u003d pr este numărul mediu de evenimente care se încadrează în intervalul de timp t, care poate fi determinat prin intensitatea fluxului de evenimente X, după cum urmează: a \u003d l f

Dimensiunea intensității fluxului X este numărul mediu de evenimente pe unitatea de timp. Între p și l, p și f există următoarea relație:

n= l t; p= f/t

unde t este întreaga perioadă de timp pe care se consideră acţiunea fluxului de evenimente.

Este necesar să se determine distribuția intervalului de timp T între evenimente dintr-un astfel de flux. Deoarece aceasta este o variabilă aleatoare, să găsim funcția de distribuție a acesteia. După cum se știe din teoria probabilității, funcția de distribuție integrală F(t) este probabilitatea ca valoarea T să fie mai mică decât timpul t.

F(t)=P(T

Conform condiției, nu trebuie să apară niciun eveniment în timpul T și cel puțin un eveniment ar trebui să apară în intervalul de timp t. Această probabilitate este calculată folosind probabilitatea evenimentului opus pe intervalul de timp (0; t), în care niciun eveniment nu a căzut, i.e. m = 0, atunci

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

Pentru mic?t, se poate obține o formulă aproximativă obținută prin înlocuirea funcției e-Xt, cu doar doi termeni ai expansiunii într-o serie în puteri?t, apoi probabilitatea de a lovi cel puțin un eveniment într-un interval de timp mic? t este

P(T

Densitatea de distribuție a intervalului de timp dintre două evenimente succesive se obține prin diferențierea F(t) în funcție de timp,

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

Folosind funcția de densitate de distribuție obținută se pot obține caracteristicile numerice ale variabilei aleatoare T: așteptarea matematică M (T), varianța D (T) și abaterea standard y (T).

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

De aici putem trage următoarea concluzie: intervalul de timp mediu T dintre oricare două evenimente învecinate în cel mai simplu debit este în medie 1/l, iar abaterea sa standard este tot de 1/l, unde, este intensitatea debitului, adică. numărul mediu de evenimente care au loc pe unitatea de timp. Legea de distribuție a unei variabile aleatoare cu astfel de proprietăți M(T) = T se numește exponențială (sau exponențială), iar valoarea l este un parametru al acestei legi exponențiale. Astfel, pentru cel mai simplu flux, așteptarea matematică a intervalului de timp dintre evenimentele învecinate este egală cu abaterea sa standard. În acest caz, probabilitatea ca numărul de cereri sosite pentru deservire într-un interval de timp t să fie egal cu k este determinată de legea Poisson:

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

unde l - intensitatea fluxului de aplicații, numărul mediu de evenimente din QS pe unitatea de timp, de exemplu [persoană / min; rub./oră; controale/ora; documente/zi; kg./oră; tone/an] .

Pentru un astfel de flux de aplicații, timpul dintre două aplicații învecinate T este distribuit exponențial cu o densitate de probabilitate:

ѓ(t)= l e-l t.

Timpul de așteptare aleatoriu în coada de pornire a serviciului t poate fi considerat, de asemenea, distribuit exponențial:

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

unde v este intensitatea fluxului de trecere la coadă, determinată de numărul mediu de aplicații care trec pentru serviciu pe unitatea de timp:

v=1/punct,

unde To este timpul mediu de așteptare pentru serviciu în coadă.

Fluxul de ieșire al cererilor este asociat cu fluxul de servicii din canal, unde durata serviciului tobs este, de asemenea, o variabilă aleatorie și în multe cazuri se supune unei legi de distribuție exponențială cu o densitate de probabilitate:

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

unde µ este intensitatea fluxului de serviciu, adică numărul mediu de solicitări servite pe unitatea de timp:

µ=1/ t obs[oameni/min; rub./oră; controale/ora; documente/zi; kg./oră; tone/an] ,

unde t obs este timpul mediu pentru întreținerea aplicațiilor.

O caracteristică importantă a QS, care combină indicatorii l și µ , este intensitatea sarcinii: с= l/ µ, care arată gradul de coordonare a fluxurilor de intrare și ieșire ale solicitărilor canalului de serviciu și determină stabilitatea sistem de coadă.

Pe lângă conceptul de cel mai simplu flux de evenimente, este adesea necesar să se utilizeze conceptele de fluxuri de alte tipuri. Un flux de evenimente se numește flux Palm atunci când în acest flux intervalele de timp dintre evenimentele succesive T1, T2, ..., Tk ..., Tn sunt variabile aleatoare independente, distribuite egal, dar spre deosebire de cel mai simplu flux, ele sunt nu neapărat distribuite după o lege exponenţială. Cel mai simplu flux este un caz special al fluxului Palm.

Un caz special important al pârâului Palm este așa-numitul pârâu Erlang.

Acest flux se obține prin „subțierea” celui mai simplu flux. O astfel de „subțiere” se realizează prin selectarea evenimentelor dintr-un flux simplu, conform unei anumite reguli.

De exemplu, dacă suntem de acord să luăm în considerare doar fiecare al doilea eveniment din elementele celui mai simplu flux, obținem un flux Erlang de ordinul doi. Dacă luăm doar fiecare al treilea eveniment, atunci se formează un flux Erlang de ordinul al treilea și așa mai departe.

Este posibil să obțineți fluxuri Erlang de orice ordin k-lea. Evident, cel mai simplu flux este fluxul Erlang de ordinul întâi.

Orice studiu al unui sistem de așteptare începe cu un studiu a ceea ce trebuie deservit și, prin urmare, cu o examinare a fluxului de clienți care intră și a caracteristicilor acestuia.

Întrucât momentele de timp t și intervalele de timp pentru primirea cererilor φ, atunci durata operațiunilor de service t obs și timpul de așteptare în coada toch, precum și lungimea cozii lch sunt variabile aleatorii, atunci, deci, caracteristicile a stării QS sunt de natură probabilistică, iar descrierea lor ar trebui să fie aplicate metode și modele de teorie a cozilor.

Caracteristicile k, f, l, Loch, Toch, v, tobs, µ, p, Pk enumerate mai sus sunt cele mai comune pentru QS, care sunt de obicei doar o parte din funcția obiectiv, deoarece este, de asemenea, necesar să se ia în considerare indicatorii de activitate comercială.

1 . 3 Cel mai simplu QS cu eșecuri

Un QS cu canale n cu defecțiuni primește cel mai simplu flux de aplicații cu intensitatea l; timpul de service - indicativ cu un parametru. Stările QS sunt numerotate în funcție de numărul de solicitări din QS (din cauza absenței unei cozi, aceasta coincide cu numărul de canale ocupate):

S0 - QS este gratuit;

S1 - un canal este ocupat, restul sunt libere;

...;

S k- ocupat k canale, restul sunt gratuite (1 kn);

…;

S n- toata lumea este ocupata n canale.

Probabilitățile de stare finală sunt exprimate prin formulele Erlang:

unde s=l/m.

Caracteristici de performanta:

A=(1-p n); Q=1-p n; Pp = p n; =(1-p n).

Pentru valori mari P probabilitățile de stare (1*) pot fi calculate convenabil folosind funcții tabulate:

(distribuția Poisson) și

,

dintre care primul poate fi exprimat în termenii celui de-al doilea:

Folosind aceste funcții, formulele Erlang (1*) pot fi rescrise ca

.

1.4 QS cu un singur canal cu defecțiuni

Să analizăm un QS simplu cu un singur canal cu refuzuri de serviciu, care primește un flux Poisson de cereri cu intensitatea l, iar serviciul are loc sub acțiunea unui flux Poisson cu intensitatea m.

Funcționarea unui QS cu un singur canal n=1 poate fi reprezentată ca un grafic de stare etichetat (3.1).

Tranzițiile QS de la o stare S0 la alta S1 au loc sub acțiunea unui flux de intrare de cereri cu intensitatea l, iar tranziția inversă are loc sub acțiunea unui flux de serviciu cu intensitatea m.

Să scriem sistemul de ecuații diferențiale Kolmogorov pentru probabilitățile de stare conform regulilor de mai sus:

De unde obținem ecuația diferențială pentru determinarea probabilității p0(t) a stării S0:

Această ecuație poate fi rezolvată în condiții inițiale în ipoteza că sistemul în momentul t=0 era în starea S0, apoi р0(0)=1, р1(0)=0.

În acest caz, soluția ecuației diferențiale ne permite să determinăm probabilitatea ca canalul să fie liber și să nu fie ocupat cu serviciul:

Atunci nu este dificil să obțineți o expresie pentru probabilitatea de a determina probabilitatea ca canalul să fie ocupat:

Probabilitatea p0(t) scade cu timpul si in limita la t>? tinde la dimensiune

iar probabilitatea p1(t) crește în același timp de la 0, tinzând spre limită ca t>? la valoare

Aceste limite de probabilitate pot fi obținute direct din ecuațiile Kolmogorov în condiție

Funcțiile p0(t) și p1(t) determină procesul tranzitoriu într-un QS cu un singur canal și descriu procesul de aproximare exponențială a QS la starea sa limită cu o caracteristică constantă de timp a sistemului luat în considerare.

Cu suficientă precizie pentru practică, putem presupune că procesul tranzitoriu în QS se termină într-un timp egal cu 3f.

Probabilitatea p0(t) determină debitul relativ al QS, care determină proporția de cereri deservite în raport cu numărul total de cereri primite, pe unitatea de timp.

Într-adevăr, p0(t) este probabilitatea ca o cerere care sosește la momentul t să fie acceptată pentru serviciu. În total, l solicitările ajung în medie pe unitatea de timp, iar cererile lp0 sunt deservite de la acestea.

Apoi, ponderea cererilor deservite în raport cu întregul flux de cereri este determinată de valoare

În limita la t>? practic deja la t>3f valoarea debitului relativ va fi egală cu

Debitul absolut, care determină numărul de cereri servite pe unitatea de timp în limita pentru t>?, este egal cu:

În consecință, ponderea cererilor care au fost respinse este, în aceleași condiții limitative:

iar numărul total de solicitări neservite este egal cu

Exemple de QS monocanal cu refuz de serviciu sunt: ​​ghiseul de comenzi din magazin, camera de control a unei firme de transport, biroul de depozit, biroul de conducere al unei societati comerciale, cu care se stabileste comunicarea telefonica.

1.5 QS multicanal cu defecțiuni

În activitățile comerciale, exemple de CMO multicanal sunt birourile întreprinderilor comerciale cu mai multe canale telefonice, un serviciu de referință gratuit pentru disponibilitatea celor mai ieftine mașini în magazinele auto din Moscova are 7 numere de telefon și, după cum știți, este foarte greu de trecut și de a obține ajutor.

În consecință, magazinele auto pierd clienți, oportunitatea de a crește numărul de mașini vândute și veniturile din vânzări, cifra de afaceri, profitul.

Companiile de turism au două, trei, patru sau mai multe canale, cum ar fi Express-Line.

Să considerăm un QS multicanal cu refuzuri de serviciu, care primește un flux Poisson de cereri cu intensitatea l.

Fluxul de serviciu din fiecare canal are o intensitate m. Pe baza numărului de solicitări QS, se determină stările lui Sk, reprezentate sub formă de grafic etichetat:

S0 - toate canalele sunt libere k=0,

S1 - doar un canal este ocupat, k=1,

S2 - sunt ocupate doar două canale, k=2,

Canalele Sk - k sunt ocupate,

Sn - toate cele n canale sunt ocupate, k= n.

Stările unui QS multicanal se schimbă brusc în momente aleatorii. Trecerea de la o stare, de exemplu, S0 la S1, are loc sub influența fluxului de intrare de cereri cu intensitatea l și invers - sub influența fluxului de cereri de deservire cu intensitatea m.

Pentru trecerea sistemului de la starea Sk la Sk-1, nu contează care dintre canale este eliberat, prin urmare fluxul de evenimente care transferă QS are o intensitate km, prin urmare, fluxul de evenimente care transferă sistemul de la Sn la Sn-1 are o intensitate nm.

Așa se formulează problema clasică Erlang, numită după inginerul - matematicianul danez - fondator al teoriei cozilor.

Un proces aleatoriu care are loc într-un QS este un caz special al procesului „naștere-moarte” și este descris de un sistem de ecuații diferențiale Erlang, care permit obținerea de expresii pentru probabilitățile limită ale stării sistemului în cauză, numite formulele Erlang:

.

După ce s-au calculat toate probabilitățile stărilor QS pe canal n cu defecțiuni p0, p1, p2, ..., pk, ..., pn, putem găsi caracteristicile sistemului de servicii.

Probabilitatea de refuzare a serviciului este determinată de probabilitatea ca o solicitare de serviciu primită să găsească toate n canalele ocupate, sistemul va fi în starea Sn:

k=n.

În sistemele cu defecțiuni, evenimentele de defecțiune și întreținere constituie un grup complet de evenimente, deci:

Rothk+Robs=1

Pe această bază, debitul relativ este determinat de formulă

Q \u003d Pobs \u003d 1-Rotk \u003d 1-Pn

Debitul absolut al QS poate fi determinat prin formulă

A=L*Robs

Probabilitatea serviciului sau proporția de cereri deservite determină debitul relativ al QS, care poate fi determinat și printr-o altă formulă:

Din această expresie se poate determina numărul mediu de aplicații aflate în service sau, ceea ce este la fel, numărul mediu de canale ocupate de service

Rata de ocupare a canalului este determinată de raportul dintre numărul mediu de canale ocupate și numărul lor total

Probabilitatea de ocupare a canalului de către serviciu, care ia în considerare timpul mediu de ocupare tload și timpul de inactivitate tpr a canalelor, este determinată după cum urmează:

Din această expresie, puteți determina timpul mediu de inactivitate al canalelor

Timpul mediu de rezidență al aplicației în sistem în regim de echilibru este determinat de formula lui Little

Tsmo \u003d nz / l.

1.6 QS cu un singur canal cu lungime limitată la coadă

În activitățile comerciale, QS cu așteptare (coadă) sunt mai frecvente.

Luați în considerare un QS simplu cu un singur canal cu o coadă limitată, în care numărul de locuri din coada m este o valoare fixă. În consecință, o aplicație care sosește în momentul în care toate locurile din coadă sunt ocupate nu este acceptată pentru service, nu intră în coadă și părăsește sistemul.

Graficul acestui QS este prezentat în Fig. 3.4 și coincide cu graficul din fig. 2.1 descriind procesul „naștere – moarte”, cu diferența că în prezența unui singur canal.

Graficul etichetat al procesului de „naștere – moarte” a serviciului, toate intensitățile fluxurilor de servicii sunt egale

Stările QS pot fi reprezentate după cum urmează:

S0 - canalul de servicii este gratuit,

S, - canalul de servicii este ocupat, dar nu există coadă,

S2 - canalul de serviciu este ocupat, există o solicitare în coadă,

S3 - canalul de servicii este ocupat, există două solicitări în coadă,

Sm+1 - canalul de serviciu este ocupat, toate cele m locuri din coadă sunt ocupate, orice cerere următoare este respinsă.

Pentru a descrie procesul aleatoriu al QS, se pot folosi regulile și formulele menționate anterior. Să scriem expresiile care definesc probabilitățile limită ale stărilor:

Expresia pentru p0 poate fi scrisă în acest caz într-un mod mai simplu, folosind faptul că numitorul este o progresie geometrică față de p, apoi după transformările corespunzătoare obținem:

c= (1- Cu)

Această formulă este valabilă pentru toate p, altele decât 1, dar dacă p = 1, atunci p0 = 1/(m + 2), iar toate celelalte probabilități sunt, de asemenea, egale cu 1/(m + 2).

Dacă presupunem m = 0, atunci trecem de la considerarea unui QS cu un singur canal cu așteptare la QS cu un singur canal deja considerat cu refuzuri de serviciu.

Într-adevăr, expresia probabilității marginale p0 în cazul m = 0 are forma:

po \u003d m / (l + m)

Și în cazul lui l \u003d m, are valoarea p0 \u003d 1 / 2.

Să definim principalele caracteristici ale unui QS cu un singur canal cu așteptare: debitul relativ și absolut, probabilitatea de eșec, precum și lungimea medie a cozii și timpul mediu de așteptare pentru o aplicație în coadă.

Solicitarea este respinsă dacă ajunge în momentul în care QS-ul este deja în starea Sm + 1 și, prin urmare, toate locurile din coadă sunt ocupate și un canal servește

Prin urmare, probabilitatea de defecțiune este determinată de probabilitatea de apariție

Sm+1 afirmă:

Potc = pm+1 = cm+1 * p0

Debitul relativ, sau proporția de cereri deservite care sosesc pe unitatea de timp, este determinată de expresie

Q \u003d 1- potk \u003d 1- cm + 1 * p0

lățimea de bandă absolută este:

Numărul mediu de aplicații L aflate în coada de servicii este determinat de așteptarea matematică a variabilei aleatoare k - numărul de aplicații aflate în coadă

variabila aleatoare k ia doar următoarele valori întregi:

1 - există o aplicație în coadă,

2 - există două aplicații în coadă,

t-toate locurile din coadă sunt ocupate

Probabilitățile acestor valori sunt determinate de probabilitățile de stare corespunzătoare, începând de la starea S2. Legea distribuției unei variabile aleatoare discrete k este descrisă după cum urmează:

Tabelul 1. Legea distribuției unei variabile aleatoare discrete

Așteptările matematice ale acestei variabile aleatoare sunt:

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

În cazul general, pentru p = 1, această sumă poate fi transformată, folosind modele de progresie geometrică, într-o formă mai convenabilă:

Loch = p2 * 1-pm * (l-m*p+1)*p0

În cazul particular la p = 1, când toate probabilitățile pk se dovedesc a fi egale, se poate folosi expresia pentru suma termenilor seriei numerice

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

Apoi obținem formula

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

Aplicând raționamente și transformări similare, se poate demonstra că timpul mediu de așteptare pentru deservirea unei cereri și a unei coade este determinat de formulele lui Little.

Punctul \u003d Loch / A (la p? 1) și T1och \u003d L "och / A (la p \u003d 1).

Un astfel de rezultat, atunci când se dovedește că Tox ~ 1/l, poate părea ciudat: odată cu creșterea intensității fluxului de cereri, se pare că lungimea cozii ar trebui să crească, iar timpul mediu de așteptare să scadă. Cu toate acestea, trebuie avut în vedere că, în primul rând, valoarea lui Loch este o funcție a lui l și m și, în al doilea rând, QS-ul luat în considerare are o lungime limitată a cozii de cel mult m aplicații.

O solicitare care ajunge la QS într-un moment în care toate canalele sunt ocupate este respinsă și, în consecință, timpul său de „așteptare” în QS este zero. Acest lucru duce în cazul general (pentru p? 1) la o scădere a Tochrostom l, deoarece proporția acestor aplicații crește odată cu creșterea lui l.

Dacă renunțăm la restricția privind lungimea cozii, i.e. aspira m--> >?, apoi cazuri p< 1 и р?1 начинают существенно различаться. Записанные выше формулы для вероятностей состояний преобразуются в случае р < 1 к виду

Pentru k suficient de mare, probabilitatea pk tinde spre zero. Prin urmare, debitul relativ va fi Q \u003d 1, iar debitul absolut va fi egal cu A - l Q - l, prin urmare, toate cererile primite sunt deservite, iar lungimea medie a cozii va fi egală cu:

Loch = p2 1-p

și timpul mediu de așteptare conform formulei lui Little

Punct \u003d Loch / A

În limita p<< 1 получаем Точ = с / м т.е. среднее время ожидания быстро уменьшается с увеличением интенсивности потока обслуживания. В противном случае при р? 1 оказывается, что в СМО отсутствует установившийся режим. Обслуживание не успевает за потоком заявок, и очередь неограниченно растет со временем (при t >?). Prin urmare, probabilitățile limită ale stărilor nu pot fi determinate: pentru Q= 1 ele sunt egale cu zero. De fapt, CMO nu își îndeplinește funcțiile, deoarece nu este capabil să deservească toate aplicațiile primite.

Este ușor de determinat că ponderea cererilor deservite și, respectiv, debitul absolut, medie c și m, cu toate acestea, o creștere nelimitată a cozii și, în consecință, timpul de așteptare în ea, duce la faptul că, după un timp , cererile încep să se acumuleze în coadă pentru un timp nelimitat.

Ca una dintre caracteristicile QS-ului, se folosește timpul mediu Tsmo al șederii aplicației în QS, inclusiv timpul mediu petrecut în coadă și timpul mediu de service. Această valoare este calculată prin formulele lui Little: dacă lungimea cozii este limitată, numărul mediu de aplicații din coadă este egal cu:

Lmo= m+1 ;2

tsmo= Lsmo; la p?1

Și apoi timpul mediu de rezidență al cererii în sistemul de așteptare (atât în ​​coadă, cât și în serviciu) este egal cu:

tsmo= m+1 la p ?1 2m

1.7 QS cu un singur canal cu coadă nelimitată

În activități comerciale, de exemplu, un director comercial este un QS cu un singur canal cu așteptare nelimitată, deoarece el, de regulă, este obligat să deservească aplicații de altă natură: documente, convorbiri telefonice, întâlniri și conversații cu subalterni, reprezentanți ai inspectoratul fiscal, poliția, experții în mărfuri, comercianții, furnizorii de produse și rezolvă problemele din sfera mărfurilor și financiare cu un grad ridicat de responsabilitate financiară, care este asociată cu îndeplinirea obligatorie a cererilor care uneori așteaptă cu nerăbdare ca cerințele lor să fie îndeplinite, iar erorile de service necorespunzătoare sunt de obicei foarte tangibile din punct de vedere economic. Modelul de întreținere a defecțiunilor Markov

În același timp, mărfurile importate pentru vânzare (servire), în timp ce se află în depozit, formează o coadă pentru service (vânzare).

Lungimea cozii este numărul de articole care urmează să fie vândute. În această situație, vânzătorii acționează ca canale de servire a mărfurilor.

Dacă cantitatea de mărfuri destinată vânzării este mare, atunci în acest caz avem de-a face cu un caz tipic de QS cu așteptare.

Să considerăm cel mai simplu QS cu un singur canal cu așteptare de serviciu, care primește un flux Poisson de cereri cu intensitatea l și intensitatea serviciului λ.

Mai mult, cererea primită în momentul în care canalul este ocupat cu service este pusă în coadă și așteaptă service.

Graficul de stare etichetat al unui astfel de sistem este prezentat în fig. 3.5

Numărul de stări posibile ale acestuia este infinit:

Canalul este liber, nu există coadă, ;

Canalul este ocupat cu servicii, nu există coadă, ;

Canalul este ocupat, o cerere în coadă, ;

Canalul este ocupat, aplicația este în coadă.

Modele pentru estimarea probabilității stărilor unui QS cu o coadă nelimitată pot fi obținute din formule izolate pentru un QS cu o coadă nelimitată prin trecerea la limită când m>?:

Trebuie remarcat faptul că pentru un QS cu o lungime limitată a cozii în formulă

există o progresie geometrică cu primul termen 1 și numitorul.

O astfel de succesiune este suma unui număr infinit de termeni la.

Această sumă converge dacă progresia, în scădere infinită la, care determină funcționarea în regim de echilibru a QS, cu la , coada la în timp poate crește la infinit.

Deoarece nu există o limită a lungimii cozii în QS-ul considerat, atunci orice aplicație poate fi servită, prin urmare, debitul relativ, respectiv, debitul absolut

Probabilitatea de a fi în coadă pentru k aplicații este egală cu:

Numărul mediu de aplicații în coadă -

Numărul mediu de aplicații în sistem -

Timpul mediu de rezidență al unei aplicații în sistem -

Timpul mediu de rezidență al unei aplicații cu sistemul -

Dacă într-un QS cu un singur canal cu așteptare, intensitatea primirii cererilor este mai mare decât intensitatea serviciului, atunci coada va crește constant. În acest sens, de cel mai mare interes este analiza QS stabil care funcționează în regim staționar la.

1.8 QS multicanal cu lungime limitată la coadă

Să considerăm un QS multicanal, a cărui intrare primește un flux Poisson de cereri cu intensitate, iar intensitatea serviciului fiecărui canal este, numărul maxim posibil de locuri în coadă este limitat de m. Stările discrete ale QS sunt determinate de numărul de aplicații care au intrat în sistem, care pot fi înregistrate.

Toate canalele sunt gratuite, ;

Este ocupat un singur canal (orice), ;

Sunt ocupate doar două canale (oricare), ;

Toate canalele sunt ocupate.

În timp ce QS se află în oricare dintre aceste stări, nu există nicio coadă. După ce toate canalele de servicii sunt ocupate, solicitările ulterioare formează o coadă, determinând astfel starea ulterioară a sistemului:

Toate canalele sunt ocupate și o aplicație este în coadă,

Toate canalele sunt ocupate și două aplicații sunt în coadă,

Toate canalele sunt ocupate și toate locurile din coadă sunt ocupate,

Trecerea QS la o stare cu numere mai mari este determinată de fluxul de cereri de intrare cu intensitate, în timp ce, prin condiție, aceste cereri sunt deservite de aceleași canale cu intensitatea fluxului de serviciu egală pentru fiecare canal. În acest caz, intensitatea totală a fluxului de serviciu crește odată cu conectarea noilor canale până la o astfel de stare când toate n canalele sunt ocupate. Odată cu apariția cozii, intensitatea serviciului crește mai mult, deoarece a atins deja valoarea maximă egală cu.

Să scriem expresii pentru probabilitățile limită ale stărilor:

Expresia pentru poate fi transformată folosind formula de progresie geometrică pentru suma termenilor cu numitor:

Formarea unei cozi este posibilă atunci când o cerere nou primită găsește în sistem nu mai puțin decât cerințele, de exemplu. când vor exista cerințe în sistem.

Aceste evenimente sunt independente, astfel încât probabilitatea ca toate canalele să fie ocupate este egală cu suma probabilităților respective.

Prin urmare, probabilitatea de a forma o coadă este egală cu:

Probabilitatea de refuzare a serviciului apare atunci când toate canalele și toate locurile din coadă sunt ocupate:

Debitul relativ va fi egal cu:

Lățimea de bandă absolută -

Numărul mediu de canale ocupate -

Numărul mediu de canale inactive -

Coeficientul de ocupare (utilizare) al canalelor -

Raportul timpului de nefuncționare a canalului -

Numărul mediu de aplicații din cozi -

Dacă această formulă ia o formă diferită -

Timpul mediu de așteptare într-o coadă este dat de formulele lui Little -

Timpul mediu de rezidență al unei aplicații în QS, ca și pentru un QS cu un singur canal, este mai mare decât timpul mediu de așteptare în coadă cu timpul mediu de serviciu, care este egal, deoarece aplicația este întotdeauna deservită de un singur canal:

1.9 QS multicanal cu coadă nelimitată

Să luăm în considerare un QS multicanal cu așteptare și o lungime nelimitată a cozii, care primește un flux de cereri cu intensitate și care are o intensitate de serviciu a fiecărui canal.

Graficul stărilor etichetat este prezentat în Figura 3.7. Are un număr infinit de stări:

S - toate canalele sunt libere, k=0;

S - un canal este ocupat, restul sunt libere, k=1;

S - două canale sunt ocupate, restul sunt libere, k=2;

S - toate cele n canale sunt ocupate, k=n, nu există coadă;

S - toate cele n canale sunt ocupate, o cerere este în coadă, k=n+1,

S - toate n canalele sunt ocupate, r cereri sunt în coadă, k=n+r,

Obținem probabilitățile stărilor din formulele pentru un QS multicanal cu o coadă limitată la trecerea la limita la m.

De remarcat că suma progresiei geometrice în expresia pentru p diverge la nivelul de încărcare p/n>1, coada va crește la nesfârșit, iar la p/n<1 ряд сходится, что определяет установившийся стационарный режим работы СМО.

nici o coadă

Deoarece nu poate exista refuz de serviciu în astfel de sisteme, caracteristicile de debit sunt:

numărul mediu de aplicații în coadă -

timpul mediu de așteptare la coadă -

numărul mediu de aplicații în CMO -

Probabilitatea ca QS-ul să fie într-o stare în care nu există cereri și niciun canal nu este ocupat este determinată de expresia

Această probabilitate determină fracțiunea medie a timpului de nefuncționare a canalului de servicii. Probabilitatea de a fi ocupat cu deservirea k solicitări -

Pe această bază, este posibil să se determine probabilitatea sau proporția de timp în care toate canalele sunt ocupate cu serviciul

Dacă toate canalele sunt deja ocupate de serviciu, atunci probabilitatea stării este determinată de expresie

Probabilitatea de a fi în coadă este egală cu probabilitatea de a găsi toate canalele deja ocupate cu serviciul

Numărul mediu de cereri din coadă și de așteptare pentru serviciu este egal cu:

Timpul mediu de așteptare pentru o aplicație în coadă conform formulei lui Little:

și în sistem

numărul mediu de canale ocupate de serviciu:

numărul mediu de canale gratuite:

rata de ocupare a canalului de servicii:

Este important de menționat că parametrul caracterizează gradul de coordonare a fluxului de intrare, de exemplu, clienții dintr-un magazin cu intensitatea fluxului de servicii. Procesul de service va fi stabil la Dacă, totuși, lungimea medie a cozii și timpul mediu de așteptare pentru clienți pentru a începe serviciul vor crește în sistem și, prin urmare, QS-ul va funcționa instabil.

1.10 Algoritm de modelare QS

QS-ul luat în considerare în problemă este un QS cu:

Serviciu dublu canal;

Un flux de intrare cu două canale (are 2 intrări, dintre care una primește un flux aleator de Cereri I, cealaltă intrare primește un flux de Cereri II).

Stabilirea orelor de primire și de comunicare a cererilor:

· Timpii de primire și deservire a cererilor sunt generați aleatoriu cu o anumită lege de distribuție exponențială;

· Se stabilește intensitatea primirii și deservirii cererilor;

Funcționarea QS-ului considerat:

Fiecare canal servește câte o solicitare la un moment dat;

Dacă cel puțin un canal este liber în momentul în care sosește o nouă solicitare, atunci cererea primită intră în serviciu;

Dacă nu există aplicații, atunci sistemul este inactiv.

Disciplina de serviciu:

Prioritatea Cererilor I: dacă sistemul este ocupat (ambele canale servesc cereri), iar unul dintre canale este ocupat de Cererea II, Cererea I preempțiază Cererea II; Aplicația II lasă sistemul neservit;

Dacă ambele canale sunt ocupate până la sosirea Cererii II, Cererea II nu este servită;

Dacă până la momentul sosirii Cererii I ambele canale deservesc Cererile I, Cererea I primită lasă sistemul neservit;

Sarcina de modelare: cunoașterea parametrilor fluxurilor de intrare ale aplicațiilor, simularea comportamentului sistemului și calcularea principalelor caracteristici ale eficienței acestuia. Prin schimbarea valorii lui T de la valori mai mici la valori mari (intervalul de timp în care are loc un proces aleatoriu de primire a cererilor din fluxurile 1 și 2 în QS pentru serviciu), este posibil să se găsească modificări ale performanței criteriu și alegeți-l pe cel optim.

Criterii pentru eficacitatea funcționării QS:

· Probabilitatea de eșec;

· Debit relativ;

· Debit absolut;

Principiul modelării:

Introducem condițiile inițiale: timpul total al sistemului, valorile intensităților fluxurilor de cereri; numărul de implementări ale sistemului;

Generăm momentele de timp la care sosesc cererile, succesiunea de sosire a Cererilor I a Cererilor II, timpul de serviciu al fiecărei cereri primite;

Numărăm câte cereri au fost depuse și câte au fost respinse;

Calculăm criteriul de eficiență al QS;

CAPITOL2 . PARTEA PRACTICĂ

Figura 1. Dependența OPSS de timp

PROGRAM CAN_SMO;

CANAL = (GRATUIT, CLAIM1, CLAIM2);

INTENSITATE = cuvânt;

STATISTICĂ = cuvânt;

CHANNAL1, CHANNAL2: CHANNAL;(Canale)

T_, t, tc1, tc2: TIMP; (Timp)

l1, l2, n1, n2: INTENSITATE;(Intensități)

servit1, nu_servit1,

servit2, not_servit2,

S: STATISTICA; (Statistici)

M,N:INTEGER;(număr de implementări)

FUNCȚIE W(t: TIMP; l: INTENSITATE) : boolean;(Determină dacă a apărut o comandă)

Începe (după intensitatea debitului l)

dacă întâmplător< l/60 then W:= TRUE else W:= FALSE;

FUNCȚIA F(t: TIME; n: INTENSITY) : TIME;(Determină cât timp va fi procesată cererea)

Începe (în funcție de intensitatea solicitărilor de service n)

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

Figura 2. Dependența OPPS de timp

WRITELN("INTRODUCEȚI NUMĂRUL DE IMPLEMENTĂRI DE LUCRU QS");

writeln(M, "a-a implementare");

CANAL1:= GRATUIT; CANAL2:= GRATUIT;

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

server1:= 0; ne_servit1:= 0;

server2:= 0; ne_servit2:= 0;

scrie ("Introduceți timpul de studiu QS - T: "); readln(_T_);

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

CANAL1:= GRATUIT;

writeln("Canalul 1 a finalizat cererea");

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

CANAL2:= GRATUIT;

writeln("Canalul 2 a finalizat cererea");

Figura 3. Graficul probabilității de defecțiune a sistemului din când în când

writeln("Solicitare primită1");

daca CANAL1 = GRATUIT atunci

începe CANAL1:= REVENȚIUNEA1; tc1:= F(t,n1); writeln("Canalul1 a primit cererea1"); Sfârşit

altfel dacă CANAL2 = GRATUIT atunci

începe CANAL 2:= REVENȚIUNEA1; tc2:= F(t,n1); writeln("Canalul 2 a acceptat cererea1"); Sfârşit

altfel, dacă CANAL1 = REVENȚIE2 atunci

începe CANAL1:= REVENȚIUNEA1; tc1:= F(t,n1); inc(ne_servit2); writeln("Canalul 1 a acceptat biletul 1 în loc de biletul 2"); Sfârşit

altfel, dacă CHANNAL2 = CLAIM2 atunci

începe CANAL 2:= REVENȚIUNEA1; tc2:= F(t,n1); inc(ne_servit2); writeln("Canalul 2 a acceptat biletul 1 în loc de biletul 2"); Sfârşit

else begin inc(not_served1); writeln("cererea1 nu a fost servită"); Sfârşit;

Figura 4. Dependența numărului de cereri la timp

writeln("Solicitare2 primită");

daca CANAL1 = GRATUIT atunci

începe CHANNAL1:= CLAIM2; tc1:= F(t,n2); writeln("Canalul1 a acceptat cererea2");end

altfel dacă CANAL2 = GRATUIT atunci

începe CANAL2:= REVENȚIUNEA2; tc2:= F(t,n2); writeln("Canal2 a acceptat cererea2");end

else begin inc(not_served2); writeln("cererea2 nu a fost servită"); Sfârşit;

S:= servit1 + nu_servit1 + servit2 + nu_servit2;

writeln("Timp de operare QS",_T_);

writeln("servit de canal1: " ,servit1);

writeln("servit de canal2: ",servit2);

writeln("Solicitări primite: ",S);

writeln("Comenzi servite: ",servit1+servit2);

writeln("Nu au fost deservite cereri: ",ne_servite1+ne_servite2);

(writeln("Intensitatea cererilor care intră în sistem: ",(servit1+servit2)/_T_:2:3);)

writeln("Debitul absolut al sistemului: ",(servit1+servit2)/T:2:3);

writeln("Probabilitatea de eșec: ",(ne_servit1+ne_servit2)/S*100:2:1,"%");

writeln("Debitul relativ al sistemului: ",(servit1+servit2)/S:2:3);

writeln("simularea terminată");

Tabelul 2. Rezultatele lucrării QS

Caracteristicile QS

Orele de funcționare

Aplicații primite

Aplicații servite

Aplicațiile nu au fost servite

Debitul absolut al sistemului

Debitul relativ al sistemului

CAPITOLUL 3REGULI DE SIGURANȚĂ

Dispoziții generale

· Persoanele care sunt familiarizate cu instrucțiunile de siguranță și regulile de conduită au voie să lucreze în clasa de calculatoare.

· În caz de încălcare a instrucțiunilor, elevul este suspendat de la muncă și are voie să învețe numai cu permisiunea scrisă a profesorului.

· Munca elevilor la o oră de informatică este permisă numai în prezența unui profesor (inginer, asistent de laborator).

· Amintiți-vă că fiecare elev este responsabil pentru starea locului său de muncă și pentru siguranța echipamentului amplasat pe acesta.

Înainte de a începe lucrul:

· Înainte de a începe lucrul, asigurați-vă că nu există daune vizibile la echipament și fire. Calculatoarele și perifericele trebuie așezate pe mese într-o poziție stabilă.

· Elevilor le este strict interzis să intre în interiorul dispozitivelor. Puteți porni dispozitivele numai cu permisiunea profesorului.

Când lucrați într-o clasă de informatică, este interzis:

1. Intrarea și ieșirea din sala de clasă fără permisiunea profesorului.

2. Întârzierea la cursuri.

3. Să intre în clasă cu pantofi murdari și umezi, haine prăfuite, în sezonul rece în îmbrăcăminte exterioară.

4. Lucrați la computer cu mâinile ude.

5. Pune obiecte străine la locul de muncă.

6. Ridică-te în timpul serviciului, întoarce-te, vorbește cu un vecin.

7. Porniți și opriți echipamentul fără permisiunea profesorului.

8. Încălcați ordinea de pornire și oprire a echipamentului.

9. Atingeți tastatura și mouse-ul când computerul este oprit, mutați mobilierul și echipamentul.

10. Atingeți ecranul de afișare, cablurile, firele de conectare, conectorii, ștecherele și prizele.

11. Apropiați-vă de locul de muncă al profesorului fără permisiune

Principala amenințare pentru sănătatea umană atunci când lucrați cu un computer este amenințarea cu șoc electric. Prin urmare, este interzis:

1. Lucrați la echipamente care prezintă defecte vizibile. Deschideți blocul de sistem.

2. Conectați sau deconectați cablurile, atingeți conectorii cablurilor de conectare, firele și prizele, dispozitivele de împământare.

3. Atingeți ecranul și partea din spate a monitorului, tastatura.

4. Încercați să depanați singur echipamentul.

5. Lucrați cu haine ude și mâinile ude

6. Îndeplinește cerințele profesorului și asistentului de laborator; Păstrați liniștea și ordinea;

7. În timp ce sunteți online, lucrați numai sub propriul nume și parolă;

8. Respectați modul de funcționare (conform Regulilor și Reglementărilor Sanitare);

9. Începeți și terminați munca numai cu permisiunea profesorului.

10. În cazul unei deteriorări accentuate a sănătății (apariția durerii în ochi, o deteriorare accentuată a vizibilității, incapacitatea de a se concentra sau de a se concentra asupra clarității, apariția durerii în degete și mâini, creșterea ritmului cardiac), imediat părăsiți locul de muncă, raportați incidentul profesorului și consultați un medic;

11. Păstrați locul de muncă curat.

12. Terminați lucrarea cu permisiunea profesorului.

13. Preda lucrările finalizate.

14. Închideți toate programele active și închideți grațios computerul.

15. Puneti in ordine locul de munca.

16. Ofițerului de serviciu să verifice pregătirea biroului pentru următoarea lecție.

În timpul funcționării echipamentului este necesar să se țină cont de: - electrocutare;

- deteriorări mecanice, traumatisme

În caz de urgență:

1. Dacă sunt detectate scântei, un miros de ars sau alte probleme, opriți imediat munca și informați profesorul despre aceasta.

2. Dacă cineva este lovit de un curent electric, este necesar: să nu mai lucreze și să se deplaseze la o distanță sigură; opriți tensiunea (pe tabloul de distribuție al dulapului); informează profesorul începe primul ajutor și cheamă un medic.

3. In caz de incendiu este necesar: oprirea lucrarilor si inceperea evacuarii; anunta profesorul si cheama pompierii (tel. 01); opriți tensiunea (pe tabloul de distribuție al dulapului); începeți stingerea incendiului cu un stingător (este interzisă stingerea incendiului cu apă.

Documente similare

Teoria matematică a stării de așteptare ca ramură a teoriei proceselor aleatorii. Sisteme de așteptare pentru aplicațiile care sosesc la intervale. Deschideți rețeaua Markov, cazul ei non-Markovian, găsirea probabilităților staționare.

lucrare de termen, adăugată 09/07/2009


Conceptul de sistem de așteptare, esența și caracteristicile acestuia. Teoria de așteptare ca una dintre secțiunile teoriei probabilităților, problemele luate în considerare. Conceptul și caracteristicile unui proces aleatoriu, tipurile și modelele acestuia. Serviciu cu așteptare.

lucrare de termen, adăugată 15.02.2009


Optimizarea controlului fluxului de clienți în rețelele de așteptare. Metode de stabilire a dependențelor între natura cerințelor, numărul de canale de servicii, productivitatea și eficiența acestora. teoria grafurilor; Ecuația Kolmogorov, fluxuri de evenimente.

test, adaugat 07.01.2015


Teoria cozilor de așteptare este o zonă a matematicii aplicate care analizează procesele din sistemele de producție în care evenimentele omogene se repetă de multe ori. Determinarea parametrilor sistemului de asteptare cu caracteristici neschimbate.

lucrare de termen, adăugată 01/08/2009


Definirea unui proces aleator și a caracteristicilor acestuia. Concepte de bază ale teoriei cozilor. Conceptul unui proces aleator Markov. Fluxuri de evenimente. Ecuațiile lui Kolmogorov. Limitarea probabilităților stărilor. Procesele de moarte și reproducere.

rezumat, adăugat la 01.08.2013


Distribuție staționară de probabilitate. Construirea de modele matematice, grafice de tranziții. Obținerea unei ecuații de echilibru pentru sistemele de așteptare cu un număr diferit de servere, diferite tipuri de cerințe și cozi limitate la servere.

teză, adăugată 23.12.2012


Analiza eficacității celor mai simple sisteme de așteptare, calculul indicatorilor lor tehnici și economici. Compararea performanței sistemului cu defecțiunile cu un sistem mixt corespunzător. Avantajele tranziției la un sistem cu proprietăți mixte.

lucrare de termen, adăugată 25.02.2012


Întocmirea unui model de simulare și calcularea indicatorilor de performanță ai sistemului de așteptare în funcție de parametrii dați. Compararea indicatorilor de performanță cu cei obținuți prin rezolvarea numerică a ecuațiilor Kolmogorov pentru probabilitățile stărilor sistemului.

lucrare de termen, adăugată 17.12.2009


Exemple de procese de reproducere și moarte în cazul celor mai simple sisteme de așteptare. Așteptări matematice pentru un sistem de așteptare. Flux suplimentar și un număr infinit de dispozitive. Sistem cu o limită a timpului de ședere a aplicației.

lucrare de termen, adăugată 26.01.2014


Câteva probleme matematice în teoria întreținerii sistemelor complexe. Organizarea serviciului cu informații limitate despre fiabilitatea sistemului. Algoritmi pentru funcționarea în siguranță a sistemului și găsirea timpului pentru întreținerea preventivă planificată a sistemelor.