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

Desen 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 ca un anumit număr de evenimente să se producă într-un segment de timp elementar lungime τ (

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

Curgerea staționară înseamnă uniformitatea sa în timp; caracteristicile probabilistice ale unui astfel de flux nu se modifică în funcţie de 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 condensări și rarefacții locale. Este important ca pentru un flux staționar aceste condensări și rarefacții să nu fie de natură obișnuită, iar numărul mediu de evenimente care se încadrează într-o singură perioadă 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, un flux de apeluri care sosesc la o centrală telefonică, să zicem, între 12 și 13 ore, poate fi considerat fix. Același flux nu va mai fi staționar pentru o zi întreagă (noaptea intensitatea fluxului de apel 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”; în realitate, ele sunt staționare doar pe o perioadă limitată de timp, iar extinderea acestei regiuni la infinit este doar o tehnică convenabilă utilizată în acest scop. de simplificare.

10.5.2.2. Nici un efect secundar

Un flux de evenimente se numește flux fără efecte secundare , dacă pentru perioade de timp care nu se suprapun, numărul de evenimente care se încadrează pe una dintre ele nu depinde de câte evenimente cad pe cealaltă (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 la un moment dat și nu la altul nu sunt, de regulă, legate de motive similare pentru alți pasageri. Dacă apare o astfel de dependență, condiția pentru absența efectelor secundare este încălcată.

Luați în considerare, de exemplu, un flux de trenuri de marfă de-a lungul unei linii de cale ferată. Daca, din cauza conditiilor de siguranta, nu se pot urma mai des decat la intervale t 0 , atunci există o dependență între evenimentele din flux, iar condiția fără efect secundar este încălcată. Cu toate acestea, dacă intervalul t 0 este mic în comparație cu intervalul mediu dintre trenuri, atunci o astfel de încălcare este nesemnificativă.

Desen 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 intervalul de timp aleator T dintre evenimentele vecine din acest flux; Să-i găsim legea distribuției. Mai întâi, să găsim funcția de distribuție:

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

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

F (t) = 1 - P 0

Probabilitate P 0 găsim din 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 ). Mărimea λ se numește parametru legea demonstrativă.

Figura 0 - 4 Distribuție exponențială

Să găsim caracteristicile numerice ale unei variabile aleatorii T- așteptări matematice (valoare medie) M [ t ]= m t , și varianța Dt. Avem

( 0-5)

(integrare pe părți).

Dispersia valorii T este:

(0-6)

Luâ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 inverse parametrului λ, unde λ. intensitatea curgerii.

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

Exemplu SMO-1 .

Ca exemplu, luați în considerare un sistem bancar care funcționează în timp real și 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 cereri care ajung la o intensitate de 2 cereri pe secundă.

Să calculăm probabilitatea P ( m ) aspectul m mesaje în 1 s. Deoarece λ = 2, atunci din formula anterioară avem

Inlocuind m = 0, 1, 2, 3, obținem următoarele valori (cu o precizie de patruzecimale):

Figura 0 - 5 Exemplu de flux simplu

Este posibil să primiți mai mult de 9 mesaje într-o secundă, dar probabilitatea acestui lucru este foarte mică (aproximativ 0,000046).

Distribuția rezultată poate fi prezentată sub forma unei histograme (prezentată în figură).

Exemplu SMO-2.

Un dispozitiv (server) care procesează trei mesaje pe 1s.

Să existe un echipament care poate procesa trei mesaje în 1 s (µ=3). În medie, două mesaje sunt primite pe 1s și în conformitate cu 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ă un sistem 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, iar 14,29% vor fi servite 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 pentru 1 mesaj este în medie de 1/3 s. Prin urmare, o întârziere mai mare de 1 s va fi o apariție rară, ceea ce este destul de acceptabil pentru majoritatea sistemelor.

Exemplu SMO- 3

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

· Dacă un canal 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 trimis de la diferite dispozitive prin canalul de comunicație pe minut de cea mai mare sarcină (inclusiv sincronizare, simboluri de sfârșit de mesaj, control etc.), atunci rata de utilizare a echipamentului canalului de comunicație în acest minut este egală cu

· Dacă un motor de acces la fișiere realizează 9.000 de accesări la fișiere într-o oră aglomerată, iar timpul mediu per acces este de 300 ms, atunci rata de utilizare a hardware-ului la ora de vârf a motorului de acces este

Conceptul de utilizare a echipamentelor 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 cozile sunt mai lungi.

Folosind formula anterioară, puteți crea tabele cu valorile funcției Poisson, din care puteți determina probabilitatea de sosirem sau mai multe mesaje într-o anumită perioadă de timp. De exemplu, dacă există 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, un analist 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 sarcinii echipamentului

ρ ≤ 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 într-o secundă este de 0,0943. Prin urmare, acest număr poate fi luat ca un criteriu de încărcare pentru calculele inițiale.

10.6.2. Sarcini de proiectare

Dacă mesajele ajung aleatoriu la dispozitiv, dispozitivul își petrece o parte din timp procesând sau deservind fiecare mesaj, ceea ce duce la formarea de cozi. O coadă la bancă așteaptă eliberarea casierului și a calculatorului său (terminal). O coadă de mesaje în memoria tampon de intrare a computerului așteaptă procesarea de către procesor. O coadă de solicitări pentru matrice de date așteaptă ca canalele să devină libere etc. Se pot forma cozi la toate blocajele din sistem.

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 de funcționare satisfăcător cu un factor de utilizare de ρ = 0,7, dar un coeficient care depășește ρ > 0,9 poate duce la o deteriorare a calității 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.

Factorul de utilizare a echipamentului este egal cu raportul dintre sarcina pe echipament și sarcina maximă pe care o poate suporta acest echipament sau 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 următoare. Cunoașterea acestor coeficienți vă permite să calculați cozile pentru echipamentul corespunzător.

· Care este lungimea cozii?

· Cât timp va dura?

La aceste tipuri de întrebări se poate răspunde folosind teoria cozilor.

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

Pentru un QS, fluxurile de evenimente sunt fluxuri de aplicații, fluxuri de aplicații 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ă o mai greoaie. aparat, aducerea lui la formule analitice sunt posibile numai în cazurile cele mai simple.

Cu toate acestea, aparatul teoriei „Markovian” poate fi util și în cazul în care procesul care are loc în QS este diferit de cel Markovian; cu ajutorul acestuia, caracteristicile de performanță ale QS pot fi aproximativ evaluate. Trebuie menționat că, cu cât QS-ul este mai complex, cu atât are 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ă cu privire la gestionarea funcționării QS, nu este necesară cunoașterea exactă a tuturor caracteristicilor acestuia, adesea sunt suficiente doar cunoștințe aproximative, aproximative.

QS sunt clasificate în sisteme cu:

· eșecuri (cu pierderi). În astfel de sisteme, o solicitare primită într-un moment î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 la un moment în care toate canalele sunt ocupate este pusă în coadă și așteaptă până când unul dintre canale devine liber. Când canalul este eliberat, una dintre solicitările din coadă este acceptată pentru service.

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

· comandat (cererile sunt procesate în ordinea în care sunt primite),

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

· stivuite (ultima cerere este selectată prima din coadă).

· Prioritate

o cu prioritate statica

o cu prioritate dinamică

(în acest din urmă caz, anterior tet poate crește, de exemplu, odată cu durata de așteptare a unei cereri).

Sistemele de cozi 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 într-un moment în care nu există canale gratuite intră într-o coadă și așteaptă „răbdător” ca canalul să devină disponibil și îl acceptă pentru serviciu. Orice cerere primită de CMO va fi deservită mai devreme sau mai târziu.

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

· lungimea cozii (numărul de aplicații simultan în coadă într-un sistem cu o lungime limitată a cozii),

· timpul petrecut de aplicație în coadă (după o anumită perioadă de ședere în coadă, aplicația iese din coadă, iar sistemul cu un timp de așteptare limitat pleacă),

· timpul total de ședere a cererii în OCM

etc.

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

Alături de absolut, este adesea considerat debit relativ QS este ponderea medie a aplicațiilor primite deservite de sistem (raportul dintre numărul mediu de aplicații deservite de sistem pe unitatea de timp și numărul mediu de cereri primite în acest timp).

Pe lângă debitul absolut și relativ, atunci când analizăm un QS cu defecțiuni, în funcție de sarcina de cercetare, ne pot interesa și alte caracteristici, de exemplu:

· numărul mediu de canale ocupate;

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

etc.

Întrebările cu așteptări au caracteristici ușor diferite. Evident, pentru un QS cu așteptare nelimitată, atât debitul absolut cât și cel relativ își pierd sensul, deoarece fiecare cerere primită este devremesau va fi servit mai târziu. Pentru un astfel de QS, caracteristicile importante sunt:

· numărul mediu de aplicații în 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 pe care o aplicație rămâne î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 fluxului de aplicațiiλ , performanța fiecărui canal (numărul mediu de cereri μ deservite de canal pe unitatea de timp), condițiile pentru formarea unei cozi (restricții, dacă există).

În funcție de valorile acestor parametri, sunt exprimate caracteristicile de performanță ale QS.

10.6.4. Formule pentru calcularea caracteristicilor QS-ului pentru cazul deservirii 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ă procesarea. Acestea pot apărea în timpul funcționării punctelor 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 mult de o intrare în serviciu, avem o coadă cu multe dispozitive și analiza devine mai complicată.

Să luăm î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 recomandabil să estimați cât de des depășește coada 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 corespunzătoare, 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 date. coeficientul de variație a timpului de serviciu

Formula Khinchin-Polacek este utilizată pentru a calcula lungimile cozilor la proiectarea sistemelor informaționale. Se folosește în cazul distribuției 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ă situații în care apar cozi când disciplina de management depinde, fără îndoială, de timpul de service. De exemplu, în unele cazuri, putem selecta mesaje mai scurte pentru serviciul prioritar pentru a obține un timp mediu de serviciu mai mic. Când controlați o linie de comunicație, puteți atribui 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. Timpii de întreținere egali cu o valoare constantă sunt rari. Nici măcar timpul de acces pe hard disk nu este constant din cauza pozițiilor diferite ale matricelor de date pe suprafață. Un exemplu care ilustrează cazul timpului de serviciu constant este ocuparea unei linii de comunicație pentru a transmite mesaje de lungime fixă.

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

O distribuție exponențială a timpilor de serviciu nu este, desigur, cel mai rău caz de rezolvat în realitate. Cu toate acestea, dacă timpii de serviciu obținuți din calculele de așteptare se dovedesc a fi distribuiti mai rău decât timpii distribuiți exponențial, acesta este adesea un semn de avertizare pentru proiectant. Dacă abaterea standard este mai mare decât media, atunci este de obicei necesară ajustarea 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 de fiecare tip este același. Abaterea standard a timpilor indicați este puțin mai mare decât media lor. Valoarea ultimului timp de service este mult mai mare decât altele. Acest lucru va face ca mesajele să rămână în coadă mult mai mult decât dacă timpii de serviciu ar fi de același ordin de mărime. Î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 ar putea merita împărțirea mesajelor foarte lungi î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, tipărire și execuție 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 ocupat. Dacă λ este numărul de clienți în orele de vârf, atunci ρ pentru casier este egal cu

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

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

adică casieria este folosită la 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 oameniîntr-o linie de checkout se află între 1,88 și 3,0 în funcție de abaterea standard pt ts .

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 casa de marcat.

Timpul total petrecut de un client la casa de marcat poate fi găsit ca

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

unde t s calculat folosind formula Khinchin-Polacek.

10.6.7. Factorul de câștig

Analizând curbele prezentate în figuri, observăm 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 la 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 scăderea performanței sistemului sau chiar la blocarea acestuia.

Creșterea traficului de intrare cu un număr mic x%. duce la o creștere a dimensiunilor cozilor de așteptare 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ă rata de utilizare a hardware-ului este de 90%, atunci creșterea dimensiunii cozii este de 100%, care este de 25 de ori mai mare. O ușoară creștere a încărcăturii la utilizarea echipamentului cu 90% are ca rezultat 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 petrecut la coadă crește cu

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

În plus, pentru rate scăzute de utilizare a echipamentelor, efectul modificărilor σs asupra dimensiunii cozii este neglijabil. Cu toate acestea, pentru coeficienți mari, modificarea în σ 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 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 atunci când se transmit mesaje lungi, atunci în cazul unui ρ mare se va forma o coadă semnificativă.

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

Sisteme de așteptare – acestea sunt sisteme care primesc cereri de serviciu în momente aleatorii, iar cererile primite sunt deservite folosind canalele de servicii disponibile sistemului.

Exemple de sisteme de așteptare includ:

• unități de decontare în numerar în bănci și întreprinderi;
• calculatoare personale care servesc aplicații primite sau cerințe pentru rezolvarea anumitor probleme;
• stații de service auto; benzinărie;
• firme de audit;
• departamentele de inspecție fiscală responsabile cu acceptarea și verificarea raportărilor curente ale întreprinderilor;
• centrale telefonice etc.

	Noduri	Cerințe
Spital	Comandante	Pacienții
Productie
Aeroport	Ieșiri pe piste Puncte de înregistrare	Pasagerii

Să luăm în considerare diagrama de funcționare a QS (Fig. 1). Sistemul este format dintr-un generator de cereri, un dispecer și o unitate de service, o unitate de contabilizare a defecțiunilor (terminator, distrugător de comenzi). În general, un nod de serviciu poate avea mai multe canale de servicii.

Orez. 1

1. Generator de aplicații – cereri generatoare de obiecte: stradal, atelier cu unitati instalate. Intrarea este fluxul de aplicații(flux de clienți către magazin, flux de unități sparte (mașini, mașini) pentru reparații, flux de vizitatori către garderobă, flux de mașini către benzinărie etc.).
2. Dispecer – o persoană sau un dispozitiv care știe ce să facă cu aplicația. 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ă gratuite;
• refuză cererile (din diverse motive);
• primește informații de la nodul serviciului despre canalele gratuite;
• monitorizează timpul de funcționare al sistemului.

1. Coadă – acumulator de aplicare. Este posibil să nu existe coadă.
2. Centru de service constă dintr-un număr finit de canale de servicii. Fiecare canal are 3 stări: liber, ocupat, nu funcționează. Dacă toate canalele sunt ocupate, atunci puteți veni cu o strategie pentru cine să transferați solicitarea.
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ă din QS, unele surse evidențiază și următoarele componente:

terminator – distrugător de tranzacții;

depozit – depozitarea resurselor și a produselor finite;

cont contabil – pentru efectuarea de tranzacții de tip „înregistrare”;

manager – manager de resurse;

Clasificarea SMO

Prima diviziune (pe baza prezenței cozilor):

• QS cu defecțiuni;
• SMO cu o coadă.

ÎN QS cu eșecuri o aplicație primită într-un moment în care toate canalele sunt ocupate este respinsă, părăsește QS și nu este deservită în viitor.

ÎN Coadă cu coadă o aplicație care ajunge într-un moment în care toate canalele sunt ocupate nu pleacă, ci se pune la coadă și așteaptă să fie servită oportunitatea.

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 pot viza atât lungimea cozii, cât și timpul de așteptare, „disciplina de serviciu”.

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

• CMO cu cereri nerăbdătoare (lungimea cozii și timpul de service sunt limitate);
• QS cu serviciu prioritar, adică unele solicitări sunt deservite î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. Aplicațiile (cerințele) pot fi generate de sistemul în sine sau de un mediu extern care există independent de sistem.

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 - depind. De exemplu, dacă un lucrător deservește un grup de mașini care necesită ajustare din când în când, atunci intensitatea fluxului de „cereri” de la mașini depinde de câte dintre ele sunt deja operaționale și așteaptă ajustarea.

Un exemplu de sistem închis: un casier care emite salarii la o întreprindere.

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

• cu un singur canal;
• multicanal.

Caracteristicile unui sistem de așteptare

Principalele caracteristici ale oricărui tip de sistem de așteptare sunt:

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

Flux de cerințe de intrare

Pentru a descrie fluxul de intrare, trebuie să specificați o lege probabilistică care determină succesiunea momentelor în care sunt primite cererile de serviciu,și indicați numărul de astfel de cerințe în fiecare chitanță ulterioară. În acest caz, de regulă, ele operează cu conceptul de „distribuție probabilistică a momentelor de primire a cerințelor”. Aici ei pot face următoarele: cerințe individuale și de grup (numărul de astfel de cerințe în fiecare chitanță obișnuită). În acest din urmă caz, vorbim de obicei despre un sistem de așteptare cu servicii de grup paralel.

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

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

λ=1/E(A)– intensitatea primirii cererilor;

Caracteristicile fluxului de intrare:

1. O lege probabilistică care determină succesiunea momentelor în care se primesc cererile de serviciu.
2. Numărul de solicitări în fiecare sosire următoare pentru fluxuri de grup.

Disciplina la coada

Coadă – un set de cerințe care așteaptă serviciul.

Coada are un nume.

Disciplina la coada definește principiul conform căruia cerințele care ajung la intrarea sistemului de servire sunt conectate de la 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 înregistrare este o celulă de listă. Aplicația ajunge la sfârșitul listei și este selectată pentru service de la începutul listei. Înregistrarea constă din caracteristicile aplicației și un link (indicatorul cine se află în spatele acesteia). În plus, dacă coada are o limită de timp de așteptare, atunci trebuie indicat și timpul maxim de așteptare.

În calitate de programatori, ar trebui să puteți face liste cu două direcții și un singur sens.

Listează acțiuni:

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

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

• selectarea aleatorie a aplicațiilor;
• selectarea cererilor pe baza criteriilor de prioritate.

Fiecare aplicație se caracterizează, printre altele, prin nivelul său de prioritate și la primire 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 serviciului (există o coadă cu un timp de așteptare limitat pentru serviciu, care este asociat cu conceptul de „lungime permisă a cozii”);
• lungimea cozii.

Mecanism de service

Mecanism de service determinate de caracteristicile procedurii de service în sine și de structura sistemului de servicii. Caracteristicile procedurii de întreținere includ:

• numărul de canale de servicii ( N);
• durata procedurii de service (distribuirea probabilă a timpului pentru cerințele de service);
• numărul de cerințe îndeplinite ca urmare a fiecărei astfel de proceduri (pentru cererile de grup);
• probabilitatea defecțiunii canalului de serviciu;
• structura sistemului de servicii.

Pentru a descrie analitic caracteristicile unei proceduri de service, este utilizat conceptul de „distribuție probabilistică a timpului pentru cerințele de service”.

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

E(S)– timpul mediu de service;

μ=1/E(S)– rapiditatea cererilor de service.

Trebuie remarcat faptul că timpul necesar 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 defecțiunii canalului de serviciu după o anumită perioadă limitată de timp. Această caracteristică poate fi modelată ca un flux de eșecuri care intră în QS și au prioritate față de toate celelalte solicitări.

Rata de utilizare QS

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

ρ=λ/( Nμ) – numit coeficientul de utilizare a QS , arată câte resurse de sistem sunt utilizate.

Structura sistemului de servicii

Structura sistemului de servicii este determinată de numărul și poziția relativă a canalelor de servicii (mecanisme, dispozitive etc.). În primul rând, trebuie subliniat că un sistem de servicii poate avea mai multe canale de servicii, dar mai multe; Acest tip de sistem 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 argumenta că 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 în mod consecvent . Mecanismul de service determină caracteristicile fluxului de cereri de ieșire (servite).

Exemplu. Comisia medicala.

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 serviciu (singure sau grup);
• puterea sursei cerințelor;
• distribuția probabilistică a duratei serviciului;
• configurarea sistemului de deservire (serviciu paralel, secvenţial sau paralel-secvenţial);
• numărul și productivitatea canalelor de servicii;
• disciplina la coada.

Principalele criterii de eficacitate a funcționării QS

La fel de principalele criterii de eficacitate a sistemelor de aşteptare În funcție de natura problemei care se rezolvă, pot apărea următoarele:

• probabilitatea deservirii imediate a unei aplicații primite (P obsl = K obs / K post);
• probabilitatea refuzului de a deservi o aplicație primită (P deschis = K deschis / K post);

Evident, P obsl + P deschis =1.

Fluxuri, întârzieri, întreținere. Formula Pollacheck–Khinchin

Întârziere – unul dintre criteriile pentru deservirea QS este timpul petrecut de aplicație în așteptarea serviciului.

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

W i =D i +S i– timpul necesar în sistem i.

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

(cu probabilitate 1) – timpul mediu stabilit în care cerința se află în QS (în așteptare).

Q(t) – numărul de cereri aflate în coadă la un moment dat t;

L(t)– numărul de cerințe din sistem la un moment dat t(Q(t) plus numărul de cerințe care sunt deservite la un moment dat t.

Apoi indicatorii (dacă există)

(cu probabilitate 1) – numărul mediu în stare de echilibru de cereri din coadă în timp;

(cu probabilitatea 1) – numărul mediu de solicitări în regim de echilibru în sistem în timp.

Rețineți că ρ<1 – обязательное условие существования d, w, QȘi Lîntr-un sistem de coadă.

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

Cele mai generale și necesare rezultate pentru sistemele de așteptare includ ecuații 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 cereri ș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, putem vorbi și despre caracteristici precum:

• capacitatea absolută a sistemului – А=Р obsl *λ;
• capacitatea relativă a sistemului -

Un alt exemplu interesant (și ilustrativ) de soluție analitică – calcularea întârzierii medii la starea staționară într-o coadă 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) este mai mare, atunci suprasarcina (în acest caz măsurată 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 serviciu 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 a cozii.

Subiectul teoriei cozilor este de a stabili o relație între factorii care determină funcționalitatea sistemului de așteptare și eficiența funcționării acestuia. În majoritatea cazurilor, toți parametrii care descriu sistemele de așteptare sunt variabile sau funcții aleatorii, prin urmare aceste sisteme aparțin sistemelor 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 aleatoriu , care apar în sistemul de așteptare (QS), se disting Sisteme markoviane și non-markoviene . În sistemele Markov, fluxul de cerințe de intrare și fluxul de ieșire al cerințelor deservite (aplicații) 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, așa că cele mai multe dintre aplicațiile binecunoscute ale teoriei cozilor de așteptare folosesc schema Markov. În cazul proceselor non-Markov, problemele studierii sistemelor de așteptare devin semnificativ mai complicate și necesită utilizarea modelării statistice și a metodelor numerice folosind un computer.

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

QS-ul sugerează că există poteci tipice(canale de servicii) prin care trec în timpul procesului de prelucrare aplicatii. Se spune în mod obișnuit 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 de așteptare a serviciului. Unele aplicații pot fi deservite de canale, în timp ce altele pot refuza acest lucru. Este important ca cererile, din punct de vedere al sistemului, să fie abstracte: sunt ceva ce vrea să fie deservit, adică să meargă într-un anumit sens în sistem. Canalele sunt, de asemenea, o abstractizare: ele sunt cele care servesc cererile.

Solicitările pot ajunge inegal, canalele pot servi diferite solicitări în momente diferite și așa mai departe, numărul de solicitări 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 cauză-efect în ele. Prin urmare, este general acceptat că întreținerea în sisteme complexe este aleatorie.

Exemple de CMO (a se vedea Tabelul 30.1) includ: ruta de autobuz și transportul de pasageri; transportoare de producție pentru prelucrarea pieselor; o escadrilă de aeronave 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 Rută de autobuz și transport de pasageri Pasagerii Autobuze Transportor de producție pentru prelucrarea pieselor Piese, componente Masini-unelte, depozite O escadrilă de avioane care zboară pe teritoriu străin, care este „servită” de tunuri antiaeriene de apărare aeriană Avioane Tunuri antiaeriene, radare, săgeți, obuze Teava și cornul mitralierei, care „servesc” cartușele Butoi, corn Sarcini electrice care se deplasează într-un dispozitiv Cascade de 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 trase numere aleatorii care simulează momentele RANDOM ale apariției comenzilor și timpul deservirii acestora în canale. Dar luate împreună, aceste numere aleatoare sunt, desigur, subordonate statistic modele.

De exemplu, să se spună: „în medie, aplicațiile ajung în cantitate de 5 bucăți pe oră”. Aceasta înseamnă că timpii dintre sosirea a două cereri î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 la o altă oră această sumă, de exemplu, poate fi egală cu 0,9); doar daca pentru destul de mult timp media acestor numere se va apropia de o oră.

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

Deci, sistemul este testat cu semnale de intrare aleatorii, supuse unei anumite legi statistice, iar rezultatul este indicatorii statistici mediați pe timpul luat în considerare sau pe numărul de experimente. Anterior, î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 standard dintr-un set mic de elemente (canal, sursă de solicitări, coadă, cerere, disciplină de serviciu, stivă, inel etc.), ceea ce vă permite să simulați aceste sarcini. tipic cale. Pentru a face acest lucru, un model de sistem este asamblat de la un constructor de astfel de elemente. Nu contează ce sistem specific 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; Există calde (încep să deservească o solicitare în momentul în care aceasta intră în canal) și reci (canalul are nevoie de timp pentru a se pregăti înainte de a începe întreținerea). Surse de comandă - generează comenzi în momente aleatorii, conform unei legi statistice specificate de utilizator. Aplicațiile, cunoscute și ca clienți, intră în sistem (generate de sursele de aplicații), trec prin elementele acestuia (sunt deservite) și îl lasă deservit 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 de bunăvoie. Fluxuri de formulare de aplicații - un flux de aplicații la intrarea sistemului, un flux de aplicații deservite, un flux de aplicații respinse. Un flux este caracterizat 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 mărime statistică.

Cozile sunt caracterizate de regulile de așteptare (disciplina serviciului), numărul de locuri în coadă (numărul maxim de clienți care pot fi în coadă) și structura cozii (relația dintre locurile din coadă). Există cozi limitate și nelimitate. Să enumerăm cele mai importante discipline de întreținere. FIFO (First In, First Out - first in, first out): dacă cererea este prima care ajunge în coadă, atunci va fi prima care va merge la service. LIFO (Last In, First Out - last in, first out): dacă cererea a ajuns ultima în coadă, atunci va fi primul care va merge la service (exemplu - cartușe în cornul unei mitraliere). SF (Short Forward): acele cereri din coadă care au un timp de service mai scurt sunt deservite mai întâi.

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

Să fie două magazine. În magazinul nr. 1, serviciul se efectuează pe principiul primul venit, primul servit, adică aici este implementată disciplina de servicii FIFO (vezi Fig. 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 achiziționează un produs bucată, vânzătorul va petrece mai puțin timp pentru service decât atunci când achiziționează, să zicem, produse în vrac care necesită manipulări suplimentare (alegerea, cântărirea, calcularea prețului etc.). Timp de asteptare t așteptat arată cât timp va dura până când următorul cumpărător va fi servit de vânzător.

În magazinul nr. 2 este implementată disciplina SF (vezi fig. 30.4), ceea ce înseamnă că mărfurile pe bucată pot fi achiziționate din timp, încă 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 va cumpăra un produs bucată, astfel încât timpul său de service este scurt - 0,5 minute. Dacă acest client vine la magazinul nr. 1, va fi obligat să stea la coadă 8 minute întregi, în timp ce la magazinul nr. 2 va fi servit imediat, în afara rândului. Astfel, timpul mediu de service pentru fiecare client într-un magazin cu disciplină de service FIFO va fi de 4 minute, iar într-un magazin cu disciplină de service HF - doar 2,8 minute. Iar beneficiul social, 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 înțelegere aprofundată a resurselor de performanță și eficiență ale sistemelor pe care le proiectează, care sunt ascunse în optimizarea parametrilor, structurilor și disciplinelor de întreținere. Modelarea ajută la identificarea acestor rezerve ascunse.

Atunci când se analizează rezultatele modelării, este de asemenea important să se indice interesele și măsura în care acestea sunt îndeplinite. Se face o distincție între interesele clientului și interesele proprietarului sistemului. Rețineți că aceste interese nu coincid întotdeauna.

Performanța QS poate fi judecată prin indicatori. Cele mai populare dintre ele:

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

debitul sistemului;

probabilitatea ca unui client să i se refuze serviciul;

probabilitatea de angajare 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 pentru fiecare 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 pentru deservirea unei aplicații;

timpul mediu pe care o aplicație rămâne în sistem.

Calitatea sistemului rezultat trebuie judecată după totalitatea valorilor indicatorului. Atunci când se analizează rezultatele modelării (indicatorilor), este de asemenea important să se acorde atenție intereselor clientului și intereselor proprietarului sistemului, adică unul sau altul indicator trebuie să fie minimizat sau maximizat, precum și gradul de implementare a acestora. . Rețineți că cel mai adesea interesele clientului și ale proprietarului nu coincid între ele sau nu coincid întotdeauna. Vom nota mai jos indicatorii H = { h 1 , h 2 , …} .

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

Exemplu. Benzinărie (benzinărie).

1. Enunțarea problemei. În fig. Figura 30.5 prezintă structura benzinăriei. Să luăm în considerare metoda de modelare a unui QS folosind exemplul său și planul de cercetare a acestuia. Șoferii care trec pe lângă benzinăriile pe drum ar putea dori să-și umple vehiculul. Nu toți șoferii doresc să beneficieze de service (umpleți mașina cu benzină); Să presupunem că din întregul flux de mașini, în medie, 5 mașini vin la benzinărie pe oră.

La o benzinărie există două coloane identice, performanța statistică a fiecăreia 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ă pompele sunt ocupate, alte mașini pot aștepta service în acest loc, dar nu mai mult de două odată. Vom considera coada generală. De îndată ce una dintre coloane este liberă, prima mașină din coadă își poate lua locul pe coloană (în timp ce a doua mașină se deplasează pe primul loc în coadă). Dacă apare o a treia mașină și toate locurile (sunt două) din coadă sunt ocupate, atunci serviciul este refuzat, deoarece statul pe drum este interzis (vezi indicatoarele rutiere lângă benzinărie). 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ă întreținere î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 sub forma unei diagrame echivalente, iar prin adăugarea valorilor și a denumirilor caracteristicilor fiecărui element al QS, în cele din urmă obțineți diagrama prezentată în fig. 30.6.

2. Metoda de cercetare SMO. În exemplul nostru, vom aplica principiul postării secvențiale a comenzilor (pentru detalii despre principiile modelării, vezi prelegerea 32). Ideea sa este că o aplicație este trecută prin întregul sistem de la intrare până la ieșire și numai după aceea se modelează următoarea aplicație.

Pentru claritate, să construim o diagramă de timp a operației QS, reflectând pe fiecare linie (axa timpului t) starea unui element individual al sistemului. Există la fel de multe linii de timp câte locuri diferite în QS și fluxuri. În exemplul nostru, există 7 dintre ele (un flux de cereri, un fir de așteptare pe primul loc în coadă, un fir de așteptare pe locul al doilea în coadă, un flux de servicii în canalul 1, un flux de servicii în canalul 2 , un flux de cereri deservite de sistem, un flux de cereri respinse).

Pentru a genera ora de sosire a cererilor, folosim formula pentru calcularea intervalului dintre timpii de sosire a două evenimente aleatoare (vezi. prelegerea 28):

În această formulă, valoarea debitului λ trebuie specificat (înainte de aceasta trebuie determinat experimental la instalație 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ă selecție specială).

Sarcină. Generați un flux de 10 evenimente aleatoare cu o rată a evenimentelor de 5 bucăți/oră.

Rezolvarea problemei. Să luăm numere aleatoare distribuite uniform în intervalul de la 0 la 1 (vezi. 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 determină distanța dintre două evenimente aleatoare după cum urmează: t= –Ln(r рр)/ λ . Atunci, având în vedere că λ = 5, avem distante intre doua evenimente invecinate aleatoare: 0,68, 0,21, 0,31, 0,12 ore. Adică apar evenimente: mai întâi - în momentul de timp t= 0, al doilea - în momentul de timp t= 0,68, a treia - la momentul de timp t= 0,89, al patrulea - la momentul respectiv t= 1,20, a cincea - la momentul de timp t= 1,32 și așa mai departe. Evenimente - sosirea comenzilor 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, deoarece în acest moment canalele sunt libere, este setat să deservească 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 servicii μ 1 sau μ 2, în funcție de canalul care deservește cererea. Găsim pe diagramă momentul încheierii serviciului, amânând timpul de serviciu generat din momentul începerii serviciului și coborâm cererea la linia „Servit”.

Aplicația a mers până la CMO. Acum, conform principiului postării secvențiale a comenzilor, este posibilă și simularea traseului 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ă într-o coadă. În fig. 30.7 este o cerere cu numărul 3. Rețineți că, în funcție de condițiile problemei, spre deosebire de canale, cererile nu sunt în coadă pentru un timp aleatoriu, ci așteaptă ca unul dintre canale să devină liber. După ce canalul este eliberat, cererea este ridicată la linia canalului corespunzător și deservirea acestuia este organizată acolo.

Dacă toate locurile din coadă sunt ocupate în momentul sosirii următoarei cereri, atunci cererea trebuie trimisă la linia „Refuzată”. În fig. 30.7 este numărul cererii 6.

Procedura de simulare a întreținerii aplicației continuă pentru un timp de observare. 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 ei aleg T n, egal cu 50-100 sau mai multe ore, deși uneori este mai bine să măsurați această valoare după numărul de cereri analizate.

Cercetarea analitică a sistemelor de așteptare (QS) este o alternativă de abordare la modelarea prin simulare și constă în obținerea de formule pentru calcularea parametrilor de ieșire ai QS și apoi înlocuirea valorilor argumentelor în aceste formule în fiecare experiment individual.

Modelele QS iau în considerare următoarele obiecte:

1) cereri de servicii (tranzacții);

2) dispozitive de service (OA) sau instrumente.

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

Exemple de probleme luate în considerare în teoria cozilor de așteptare includ: potrivirea capacității unei surse de mesaje 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.

O solicitare poate fi fie într-o stare de serviciu, fie într-o stare de serviciu în așteptare.

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

Starea QS este caracterizată de un set de stări ale dispozitivelor de service și solicitări. O schimbare de stare într-un QS se numește eveniment.

Modelele QS sunt folosite pentru a studia procesele care au loc în sistem atunci când fluxurile de cereri sunt transmise intrărilor. Aceste procese sunt o succesiune de evenimente.

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

Performanţă

Lățimea de bandă

Probabilitatea refuzului serviciului

Durata medie de service;

Factorul de sarcină al echipamentului (OA).

Aplicațiile pot fi comenzi pentru producția de produse, probleme rezolvate într-un sistem informatic, clienți în bănci, mărfuri primite pentru transport etc. Evident, parametrii aplicațiilor care intră în sistem sunt variabile aleatorii iar în timpul cercetării sau proiectării doar legile lor de distribuție. .

În acest sens, analiza funcționării la nivel de sistem este, de regulă, de natură statistică. Este convenabil să se adopte teoria coadă ca un aparat de modelare matematică și să se utilizeze sistemele de așteptare ca modele de sisteme la acest nivel.

Cele mai simple modele de QS

În cel mai simplu caz, QS-ul este un dispozitiv numit service aparat (SA), cu cozi de solicitări la intrări.

MODEL DE SERVICIU CLIENȚI (Fig. 5.1)

Orez. 5.1. Model QS cu defecțiuni:

0 – sursa cererilor;

1 – dispozitiv de service;

A– fluxul de intrare al cererilor de serviciu;

V– fluxul de ieșire al cererilor servite;

Cu– fluxul de ieșire al cererilor neprocesate.

În acest model, nu există un acumulator de cerere la intrarea OA. Dacă o solicitare sosește de la sursa 0 într-un moment în care OA este ocupat cu deservirea cererii anterioare, atunci cererea nou sosită părăsește sistemul (din moment ce i se refuză serviciul) și se pierde (flux Cu).

M o d e l d e p o r m e n t i n e (Fig. 5.2)

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

(N– 1) – numărul de aplicații care pot încăpea în depozit

În acest model există un acumulator de cerere la intrarea OA. Dacă o solicitare sosește de la sursa 0 într-un moment în care OA este ocupat cu deservirea cererii anterioare, atunci cererea nou sosită ajunge în unitatea de stocare, unde așteaptă o perioadă nedefinită de timp până când OA devine liberă.

MODEL DE SERVICE CU TIMP LIMITAT

o w i d a n i a (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 singur OA, ci mai multe. Aplicațiile, cu excepția cazului în care este specificat în mod specific, pot fi depuse la orice OA fără serviciu. Nu există un dispozitiv de stocare, așa că acest model include proprietățile modelului prezentat în Fig. 5.1: refuzul de a deservi o aplicație înseamnă pierderea irecuperabilă a acesteia (acest lucru are loc numai dacă, la momentul sosirii acestei aplicații, Toate OA sunt ocupate).

Timp de așteptare (Fig. 5.5)

Orez. 5.6. Model multicanal de SMO cu așteptări și restabilire a OA:

e– dispozitive de service care sunt nefuncționale;

f– echipamente de service recondiționate

Acest model are proprietățile modelelor prezentate în Fig. 5.2 și 5.4 și, în plus, proprietăți care fac posibilă luarea în considerare a posibilelor defecțiuni aleatorii ale OA, care în acest caz ajung la unitatea de reparații 2, unde rămân pentru perioade aleatorii de timp petrecute la restaurarea lor, iar apoi revin din nou la unitatea de service 1.

MODEL MULTI-CANALE DE SMO CU LIMITATE

TIMPUL DE ASTEPTARE SI RECUPERAREA OA (Fig. 5.7)

Orez. 5.7. Model QS multicanal cu latență limitată și recuperare OA

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

Trimiteți-vă munca bună în baza de cunoștințe este simplu. Utilizați 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. REGULI DE SIGURANȚĂ

CONCLUZIE

LISTA DE REFERINȚE UTILIZATE

INTRODUCERE

Recent, într-o varietate de domenii de practică, a apărut nevoia de a rezolva diverse probleme probabilistice legate de funcționarea așa-numitelor sisteme de așteptare (QS).

Exemple de astfel de sisteme includ: centrale telefonice, ateliere de reparații, case de bilete, standuri de taxi, coafor etc.

Tema acestui proiect de curs este tocmai soluția la o astfel de problemă.

Totuși, în problema propusă se va studia un QS în care sunt luate în considerare 2 fluxuri de solicitări, dintre care unul are prioritate.

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

Prin urmare, soluția la această problemă se bazează nu pe o descriere 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 procesului de producție în timp; - Furnizați principalele opțiuni pentru reducerea duratei ciclului de producție;

Efectuează o analiză a metodelor de management al procesului de producție la întreprindere;

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

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

Consolidarea cunoștințelor teoretice și dobândirea de abilități în aplicarea lor practică;

Raportul conține o introducere, trei capitole, o concluzie, o listă de referințe și anexe.

Al doilea capitol discută 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 servi orice aplicații (cerințe) care ajung la el în momente aleatorii. Orice dispozitiv direct implicat în solicitările de service se numește canal de servicii (sau „dispozitiv”). SMO-urile pot fi fie cu un singur canal, fie cu mai multe canale.

Există QS cu eșecuri și QS cu o coadă. Într-un QS cu refuzuri, o aplicație care ajunge într-un moment în care toate canalele sunt ocupate primește un refuz, părăsește QS-ul și, ulterior, nu participă la activitatea sa. Într-un QS cu o coadă, o solicitare care sosește când 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 limitat sau nelimitat. La m=0, QS-ul cu o coadă se transformă într-un QS cu eșecuri. Coada poate avea restricții nu numai asupra numărului de aplicații care se află în ea (lungimea cozii), ci și asupra timpului de așteptare (astfel de QS-uri sunt numite „sisteme cu clienți nerăbdători”).

Studiul 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 un QS, această ipoteză înseamnă că atât fluxul de cereri, cât și fluxul de servicii sunt cele mai simple. Fluxul de servicii este înțeles ca un flux de cereri deservite una după alta de un canal ocupat continuu. Acest flux se dovedește a fi cel mai simplu doar dacă timpul de deservire a cererii tobsl 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 cele mai simple se numește cel mai simplu QS.

Dacă toate fluxurile de evenimente sunt cele mai simple, atunci procesul care are loc în QS este un proces aleator Markov cu stări discrete și timp continuu. Dacă sunt îndeplinite 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 procesorului - memoria principală, canalul de intrare-ieșire etc.

Un sistem de calcul în ansamblu este o colecție de subsisteme interconectate, a căror interacțiune este probabilistică în natură. O aplicație pentru rezolvarea unei anumite probleme de intrare într-un sistem de calcul parcurge o succesiune de etape de numărare, accesarea dispozitivelor de stocare externe și a dispozitivelor 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 informatic.

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

Sarcinile teoriei cozilor de așteptare 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 n, distribuția timpului de serviciu etc. .) și caracteristicile de performanță ale QS. Astfel de caracteristici pot fi luate în considerare, de exemplu, următoarele:

Numărul mediu de cereri A deservite de QS pe unitatea de timp sau capacitatea absolută a QS;

Probabilitatea de a deservi o cerere Q primită sau capacitatea relativă a QS; Q = A/l;

Probabilitatea de eșec a Rotk, i.e. probabilitatea ca cererea primită să nu fie deservită și să fie refuzată; Rotk= 1 - Q;

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

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

Timpul mediu pe care o aplicație rămâne în QS (în coadă sau în service);

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

Numărul mediu de canale ocupate.

În general, toate aceste caracteristici depind de timp. Dar multe sisteme de autoservire funcționează în condiții constante pentru o perioadă destul de lungă și, prin urmare, reușește să li se stabilească un regim apropiat de staționar.

Ne aflăm aici pe tot parcursul, fără a prevedea acest lucru în mod specific de fiecare dată, 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 care ajung la el nu depinde de starea QS-ului în sine.

Pentru orice QS deschis în modul staționar de limitare, timpul mediu de ședere al unei cereri în sistem este exprimat prin numărul mediu de revendicări din sistem folosind formula lui Little:

unde l este intensitatea fluxului de aplicații.

O formulă similară (numită și formula lui Little) raportează timpul mediu pe care o aplicație îl petrece în coadă și numărul mediu de aplicații din coadă:

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

Subliniem în 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 aplicații și servicii este ca acestea să fie staționare.

În mod similar, formula care exprimă numărul mediu de canale ocupate prin capacitatea absolută A are un sens universal pentru QS deschis:

unde este intensitatea fluxului de servicii.

Multe probleme ale teoriei cozilor de așteptare referitoare la cel mai simplu QS sunt rezolvate folosind schema de moarte și reproducere.

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ă;

· durata medie de ședere în serviciul de sănătate;

lungimea medie a cozii;

· numărul mediu de cereri la OCM;

· numărul de canale de servicii;

· intensitatea fluxului de intrare al aplicațiilor;

· intensitatea serviciului;

· intensitatea sarcinii;

· factor de încărcare;

· debit relativ;

· debit absolut;

· ponderea timpului de nefuncţionare QS;

· ponderea aplicațiilor deservite;

· ponderea aplicațiilor pierdute;

· numărul mediu de canale ocupate;

· număr mediu de canale gratuite;

· factor de încărcare canal;

· timpul mediu de oprire a canalelor.

1 . 2 Modelarea sistemelor de asteptare

Tranzițiile unui QS de la o stare la alta au loc sub influența unor evenimente foarte specifice - primirea aplicațiilor și service-ul acestora. Succesiunea evenimentelor care au loc unul după altul în momente aleatorii 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, cumpărători, apeluri telefonice, negocieri. Comportamentul unui sistem este de obicei determinat nu de unul, ci de mai multe fluxuri de evenimente. De exemplu, serviciul pentru clienți într-un magazin este determinat de fluxul de clienți și fluxul de servicii; în aceste fluxuri, momentele în care apar clienții, timpul de așteptare la coadă și timpul petrecut deservind fiecare client 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ă în caracteristicile lor.

Un flux de evenimente se numește regulat dacă evenimentele se succed la intervale predeterminate și strict definite. Acest flux este ideal și este foarte rar întâlnit î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 la începutul timpului. 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 o valoare constantă. În practică, fluxurile pot fi de obicei considerate staționare doar pe o anumită perioadă limitată de timp. De obicei, fluxul de clienți, de exemplu, într-un magazin, se modifică semnificativ în timpul zilei de lucru. Cu toate acestea, se pot identifica 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ă într-unul dintre intervalele de timp alese arbitrar nu depinde de numărul de evenimente care se încadrează într-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 au loc î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 determinat 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 ca două sau mai multe evenimente să se producă simultan într-o perioadă foarte scurtă de timp este neglijabilă în comparație cu probabilitatea ca un singur eveniment să se producă. Î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 are simultan proprietățile staționarității, ordinarității și absenței consecințelor, 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 se dovedește a fi cea mai simplă. Prin urmare, în special, cel mai simplu flux joacă un rol special printre alte fluxuri existente.

Să considerăm un anumit 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 fluxului obișnuit de evenimente, probabilitatea p ar trebui să fie o valoare suficient de mică, iar i ar trebui să fie un număr suficient de mare, deoarece sunt luate în considerare fenomenele de masă.

În aceste condiții, pentru a calcula probabilitatea ca un anumit număr de evenimente m să apară într-o perioadă de timp t, puteți utiliza formula Poisson:

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

unde valoarea a = pr este numărul mediu de evenimente care se încadrează într-o perioadă de timp t, care poate fi determinată prin intensitatea fluxului de evenimente X după cum urmează: a = l f

Dimensiunea intensității fluxului X este numărul mediu de evenimente pe unitatea de timp. Există următoarea legătură între p și l, p și f:

n= l t; p= f/t

unde t este întreaga perioadă de timp în care se ia în considerare 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 cumulativă F(t) este probabilitatea ca valoarea T să fie mai mică decât timpul t.

F(t)=P(T

Conform condiției, niciun eveniment nu ar trebui să aibă loc î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 în intervalul de timp (0; t), unde nu a avut loc niciun eveniment, adică. 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 de expansiune în puteri ale lui?t, atunci probabilitatea ca cel puțin un eveniment să se producă într-o perioadă mică de timp?t este

P(T

Obținem densitatea de distribuție a intervalului de timp dintre două evenimente consecutive 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ă, puteți obține caracteristicile numerice ale variabilei aleatoare T: așteptarea matematică M (T), varianța D (T) și abaterea standard y (T).

M(T)= l??0 t*e-лt*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 egal cu 1/l, iar abaterea sa standard este, de asemenea, egală cu 1/l, l unde, este intensitatea a fluxului, 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 primite pentru serviciu într-o perioadă de timp t să fie egal cu k este determinată de legea lui Poisson:

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

unde l este intensitatea fluxului de cereri, numărul mediu de evenimente din QS pe unitatea de timp, de exemplu [persoană/min; rub./oră; controale/ora; document/zi; kg./oră; t./an].

Pentru un astfel de flux de cereri, timpul dintre două cereri învecinate T este distribuit exponențial cu densitatea de probabilitate:

ѓ(t)= l e-l t.

Timpul de așteptare aleatoriu t în coada de pornire a serviciului 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 Toch 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 cereri deservite pe unitatea de timp:

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

unde t obs este timpul mediu pentru cererile de service.

O caracteristică importantă a QS, care combină indicatorii l și µ, este intensitatea sarcinii: c = l/ µ, care arată gradul de coordonare a fluxurilor de intrare și ieșire a cererilor canalului de serviciu și determină stabilitatea sistemului de așteptare. .

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 Palma atunci când în acest flux intervalele de timp dintre evenimentele succesive T1, T2, ..., Tk ..., Tn sunt variabile aleatoare independente, distribuite identic, 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 fluxului Palm este așa-numitul flux Erlang.

Acest flux se obține prin „subțierea” celui mai simplu flux. Această „subțiere” se realizează prin selectarea evenimentelor din cel mai simplu flux conform unei anumite reguli.

De exemplu, fiind de acord să luăm în considerare numai fiecare al doilea eveniment care formează cel 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 trei etc.

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

Orice studiu al unui sistem de așteptare începe cu studierea a ceea ce trebuie deservit, prin urmare, cu studierea fluxului de aplicații de intrare și a caracteristicilor acestuia.

Întrucât momentele de timp t și intervalele de timp de primire a cererilor f, atunci durata operațiunilor de service t obs și timpul de așteptare în coada toch, precum și lungimea cozii loch sunt variabile aleatorii, atunci, prin urmare, caracteristicile starea QS-urilor sunt de natură probabilistică, iar pentru a le descrie este necesar să se aplice metode și modele ale teoriei cozilor de așteptare.

Caracteristicile enumerate mai sus k, f, l, Loch, Toch, v, tobs, µ, p, Pk 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 indicatori ai activității comerciale.

1 . 3 Cel mai simplu QS cu eșecuri

Un QS cu n canale cu defecțiuni primește cel mai simplu flux de cereri cu intensitatea n; timpul de service este indicativ pentru parametru. Stările QS-ului sunt numerotate în funcție de numărul de solicitări localizate în 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 finale ale stărilor sunt exprimate prin formulele Erlang:

unde s=l/m.

Caracteristici de eficienta:

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

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

(distribuția Poisson) și

,

dintre care primul poate fi exprimat prin al doilea:

Folosind aceste funcții, formulele Erlang (1*) pot fi rescrise sub formă

.

1.4 QS cu un singur canal cu defecțiuni

Să analizăm un QS simplu monocanal cu defecțiuni de serviciu, care primește un flux Poisson de cereri cu intensitatea l, iar service-ul are loc sub influența unui flux Poisson cu intensitatea m.

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

Tranzițiile QS de la o stare S0 la alta S1 au loc sub influența fluxului de intrare al cererilor cu intensitatea l, iar tranziția inversă are loc sub influența fluxului de serviciu cu intensitatea m.

Să scriem sistemul de ecuații diferențiale Kolmogorov pentru probabilitățile de stare conform regulilor menționate 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 p0(0)=1, p1(0)=0.

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

Atunci este ușor să obțineți o expresie pentru probabilitatea determinării probabilității de ocupare a canalului:

Probabilitatea p0(t) scade în timp și în limita la t>? tinde spre valoare

iar probabilitatea p1(t) în acelaşi timp creşte de la 0, tinzând spre limita la t>? la dimensiune

Aceste limite de probabilitate pot fi obținute direct din ecuațiile Kolmogorov, prevăzute

Funcțiile р0(t) și р1(t) definesc procesul tranzitoriu într-un QS cu un singur canal și descriu procesul de apropiere 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 de tranziție în QS se termină într-un timp egal cu 3f.

Probabilitatea p0(t) determină capacitatea relativă a QS, care determină proporția aplicațiilor deservite în raport cu numărul total de aplicații 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, o medie de l aplicații ajung pe unitatea de timp, iar lr0 aplicații sunt deservite.

Apoi, ponderea aplicațiilor deservite în raport cu întregul flux de aplicații va fi determinată de valoare

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

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

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

iar numărul total de aplicații neservite este egal cu

Exemple de QS cu un singur canal cu refuzuri de servicii sunt: ​​un birou de comenzi într-un magazin, o cameră de control a unei întreprinderi de transport auto, un birou de depozit, un birou de conducere al unei societăți comerciale, cu care se stabilește comunicarea prin telefon.

1.5 QS multicanal cu defecțiuni

În activitățile comerciale, exemple de QS multicanal sunt birourile întreprinderilor comerciale cu mai multe canale telefonice; un birou de asistență gratuit pentru disponibilitatea celor mai ieftine mașini în magazinele auto din Moscova are 7 numere de telefon și, după cum se știe, este foarte greu să suni și să obții 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 și profitul.

Companiile de turism care vând pachete turistice au două, trei, patru sau mai multe canale, cum ar fi Express-Line.

Să considerăm un QS multicanal cu defecțiuni de serviciu a cărui intrare primește un flux Poisson de cereri cu intensitatea l.

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

S0 - toate canalele sunt libere k=0,

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

S2 - doar două canale sunt ocupate, 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 al cererilor cu intensitatea l și invers - sub influența fluxului de cereri de deservire cu intensitatea m.

Pentru ca sistemul să treacă de la starea Sk la Sk-1, nu contează ce canal este eliberat, prin urmare fluxul de evenimente care transferă QS are o intensitate de km, prin urmare, fluxul de evenimente care transferă sistemul de la Sn. la Sn-1 are o intensitate de nm.

Așa se formulează clasica problemă Erlang, numită după inginerul și matematicianul danez care a fondat teoria cozilor.

Procesul aleatoriu care are loc în QS este un caz special al procesului „naștere-moarte” și este descris de un sistem de ecuații diferențiale Erlang, care fac posibilă obținerea de expresii pentru probabilitățile limită ale stării sistemului luat în considerare, numite formule Erlang:

.

Calculând toate probabilitățile de stări ale unui QS cu n canale 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, prin urmare:

Rotk+Robs=1

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

Q = Pobs = 1-Rotk = 1-Pn

Capacitatea absolută a QS poate fi determinată prin formulă

A=l*Robs

Probabilitatea serviciului sau proporția de cereri deservite determină capacitatea relativă a QS, care poate fi determinată folosind o altă formulă:

Din această expresie se poate determina numărul mediu de solicitări în serviciu sau, ceea ce este la fel, numărul mediu de canale ocupate de serviciu

Rata de ocupare a canalelor în funcție de serviciu este determinată de raportul dintre numărul mediu de canale ocupate și numărul lor total

Probabilitatea ca canalele să fie ocupate de serviciu, care ia în considerare timpul mediu de ocupare pentru canalele ocupate și timpul de inactivitate, este determinată după cum urmează:

Din această expresie puteți determina timpul mediu de întrerupere a canalelor

Timpul mediu pe care o cerere rămâne în sistem în stare de echilibru este determinat de formula lui Little

Tsmo= nz/l.

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

În activitățile comerciale, QS cu așteptare (în coadă) este mai frecventă.

Să considerăm 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 primită într-un moment în care toate locurile din coadă sunt ocupate nu este acceptată pentru service, nu se înscrie î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 serviciu „naștere - moarte”; 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 serviciu 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 ulterioară este respinsă.

Pentru a descrie procesul QS aleatoriu, puteți utiliza regulile și formulele menționate anterior. Să scriem expresii care determină probabilitățile limită ale stărilor:

Expresia pentru p0 poate fi scrisă într-un mod mai simplu în acest caz, folosind faptul că numitorul conține o progresie geometrică relativ la p, apoi după transformări 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 deja considerat cu un singur canal cu refuzuri de serviciu.

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

po = m / (l+m)

Și în cazul l = m are valoarea p0 = 1 / 2.

Să determinăm principalele caracteristici ale unui QS cu un singur canal cu așteptare: debit 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ă.

O aplicație este respinsă dacă ajunge într-un moment în care QS-ul este deja în starea Sm+1 și, prin urmare, toate locurile din coadă sunt ocupate și un canal deservește

Prin urmare, probabilitatea de eșec este determinată de probabilitatea de apariție

Sm+1 afirmă:

Ptk = pm+1 = сm+1 * p0

Debitul relativ, sau ponderea cererilor deservite care sosesc pe unitatea de timp, este determinată de expresie

Q = 1- rotk = 1- cm+1 * p0

debitul absolut este:

Numărul mediu de aplicații L din coada de serviciu este determinat de așteptarea matematică a variabilei aleatoare k - numărul de aplicații din coadă

Variabila aleatorie 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 coada sunt ocupate

Probabilitățile acestor valori sunt determinate de probabilitățile corespunzătoare de stări, începând cu starea S2. Legea distribuției unei variabile aleatoare discrete k este prezentată 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 special când p = 1, când toate probabilitățile pk sunt egale, puteți folosi expresia pentru suma termenilor seriei numerice

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

Apoi obținem formula

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

Folosind raționamente și transformări similare, se poate demonstra că timpul mediu de așteptare pentru deservirea unei cereri într-o coadă este determinat de formulele lui Little.

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

Acest rezultat, când se dovedește că Toc ~ 1/l, poate părea ciudat: odată cu creșterea intensității fluxului de aplicații, lungimea cozii pare să crească și timpul mediu de așteptare scade. 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 aplicație primită de QS într-un moment în care toate canalele sunt ocupate este respinsă și, prin urmare, timpul său de „așteptare” în QS este zero. Acest lucru duce în cazul general (pentru p? 1) la o scădere a Tochromost l, deoarece ponderea unor astfel de solicitări crește odată cu creșterea l.

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

Când k este suficient de mare, probabilitatea pk tinde spre zero. Prin urmare, debitul relativ va fi Q = 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

Punctul = Loch/A

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

Nu este dificil să se determine că ponderea aplicațiilor deservite și, respectiv, debitul absolut, sunt în medie c și m, cu toate acestea, o creștere nelimitată a cozii de așteptare și, prin urmare, timpul de așteptare în ea duce la faptul că, după unele timp aplicațiile încep să se acumuleze în coadă pentru un timp nedefinit.

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

Lsmo= m+1 ;2

Tsmo= Lsmo; la p?1

Și apoi, timpul mediu pe care o cerere rămâne î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ățile comerciale, de exemplu, un director comercial acționează ca un CMO cu un singur canal cu așteptare nelimitată, deoarece el, de regulă, este obligat să deservească cereri de diferite naturi: documente, convorbiri telefonice, întâlniri și conversații cu subalternii, reprezentanții inspectoratul fiscal, poliția, experții în mărfuri, comercianții, furnizorii de produse și rezolvă problemele din sfera mărfurilor-financiare cu un grad ridicat de responsabilitate financiară, care este asociată cu îndeplinirea obligatorie a cererilor care uneori așteaptă cu nerăbdare îndeplinirea cerințelor lor și erorile de servicii incorecte sunt, de regulă, foarte semnificative 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 bunuri destinate vânzării. În această situație, vânzătorii acționează ca canale de deservire a mărfurilor.

Dacă numărul de bunuri destinate 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 pentru serviciu, care primește un flux Poisson de cereri cu intensitatea l și intensitatea serviciului?.

Mai mult, o solicitare primită într-un moment în care canalul este ocupat cu service este pusă într-o coadă și așteaptă serviciul.

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

Numărul de stări posibile este infinit:

Canalul este liber, nu există coadă, ;

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

Canal ocupat, o cerere în coadă, ;

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

Modele pentru estimarea probabilității stărilor QS cu o coadă nelimitată pot fi obținute din formulele alocate pentru QS cu o coadă nelimitată prin trecerea la limita la 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, care scade la infinit la, care determină modul de funcționare în regim de echilibru al QS, cu coada la, poate crește la infinit în timp.

Deoarece în QS-ul luat în considerare nu există nicio restricție privind lungimea cozii, orice cerere poate fi servită, prin urmare, debitul relativ, respectiv, debitul absolut

Probabilitatea ca k aplicații să fie în coadă este:

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

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

Timpul mediu pe care o aplicație rămâne în sistem -

Timpul mediu pe care o aplicație rămâne în sistem -

Dacă într-un QS cu un singur canal cu așteptare intensitatea solicitărilor primite este mai mare decât intensitatea serviciului, atunci coada va crește constant. În acest sens, analiza sistemelor QS stabile 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 cereri primite de sistem care pot fi înregistrate.

Toate canalele sunt gratuite;

Numai un canal (oricare) este ocupat;

Doar două canale (oricare) sunt ocupate;

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ă solicitări sunt la coadă,

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

Trecerea QS la o stare cu numere mari este determinată de fluxul de solicitări de intrare cu intensitate, în timp ce, în funcție de condiție, la deservirea acestor solicitări participă canale identice cu o intensitate egală a fluxului de servicii pentru fiecare canal. În acest caz, intensitatea totală a fluxului de serviciu crește odată cu conectarea noilor canale până la o stare când toate cele n canale sunt ocupate. Odată cu apariția cozii, intensitatea serviciului crește și mai mult, deoarece a atins deja o valoare 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 aplicație nou primită găsește cel puțin cerințele în sistem, de exemplu. când există cerințe în sistem.

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

Prin urmare, probabilitatea formării unei cozi este:

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

Debitul relativ va fi egal cu:

Debit absolut -

Numărul mediu de canale ocupate -

Numărul mediu de canale inactive -

Factor de ocupare (utilizare) canal -

Rata timpului de nefuncţionare a canalului -

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

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

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

Timpul mediu de ședere 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 de coadă nelimitată, care primește un flux de cereri cu intensitate și care are intensitatea 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, fără coadă;

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

S - toate n canalele sunt ocupate, r aplicații sunt în coadă, k=n+r,

Obținem probabilitățile de stare 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 ряд сходится, что определяет установившийся стационарный режим работы СМО.

Fără coadă

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

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

timpul mediu de așteptare la coadă -

numărul mediu de cereri la CMO -

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

Această probabilitate determină procentul mediu 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 de serviciu

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

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

Numărul mediu de aplicații în coadă și serviciul în așteptare este:

Timp 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 dacă, totuși, lungimea medie a cozii și timpul mediu de așteptare pentru clienți pentru a începe serviciul cresc în sistem și, prin urmare, sistemul de service va funcționa instabil.

1.10 Algoritm de modelare QS

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

Serviciu pe două canale;

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

Stabilirea orelor de primire și deservire a aplicațiilor:

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

· Sunt specificate tarifele de primire si deservire a cererilor;

Funcționarea QS-ului considerat:

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

Dacă în momentul primirii unei noi solicitări cel puțin un canal este liber, atunci cererea primită este primită pentru serviciu;

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

Disciplina de serviciu:

Prioritatea Ordinelor I: dacă sistemul este ocupat (ambele canale servesc comenzi), iar unul dintre canale este ocupat de Ordinul II, Ordinul I preia Ordinul II; Solicitarea II lasă sistemul neservit;

Dacă până la sosirea cererii II ambele canale sunt ocupate, cererea II nu este deservită;

Dacă până la sosirea Comanda I, ambele canale deservesc Comenzile I, Comanda I primită lasă sistemul neservit;

Sarcina de modelare: cunoașterea parametrilor fluxurilor de intrare de cereri, simularea comportamentului sistemului și calcularea principalelor caracteristici ale eficacității acestuia. Prin schimbarea valorii lui T de la valori mai mici la valori mai mari (intervalul de timp în care are loc un proces aleatoriu de primire a cererilor de fluxuri 1 și 2 în QS pentru service), puteți găsi modificări în criteriul eficienței operaționale. și selectaț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 de funcționare al sistemului, valorile intensității fluxurilor aplicației; numărul de implementări ale sistemului;

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

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

Calculăm criteriul pentru eficacitatea 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;(Intensitate)

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ă ordinea a apărut)

Î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 + rotund(60/(n));

Figura 2. Dependența OPPS de timp

WRITELN("INTRODUCEȚI NUMĂRUL DE IMPLEMENTĂRI AL SMO");

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

CANAL1:= GRATUIT; CANAL2:= GRATUIT;

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

servit1:= 0; ne_servit1:= 0;

servit2:= 0; nu_servit2:= 0;

write("Introduceți ora studiului SMO - 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(servid1) else inc(served2);

CANAL2:= GRATUIT;

writeln("Canalul 2 a finalizat cererea");

Figura 3. Graficul probabilității de defecțiune a sistemului în funcție de timp

writeln("Solicitare1 primită");

dacă CANAL1 = GRATUIT atunci

începe CANAL1:= REVENȚIUNEA1; tc1:= F(t,n1); writeln("Canalul 1 a acceptat 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 cererea1 în loc de cererea2"); 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 cererea1 în loc de cererea2"); Sfârşit

else begin inc(not_served1); writeln("cererea 1 nu este deservită"); Sfârşit;

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

writeln("Solicitarea2 primită");

dacă CANAL1 = GRATUIT atunci

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

altfel dacă CANAL2 = GRATUIT atunci

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

else begin inc(not_served2); writeln("cererea2 nu este deservită"); Sfârşit;

S:= servit1 + nu_servit1 + servit2 + nu_servit2;

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

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

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

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

writeln("Solicitari servite: ",servite1+servite2);

writeln("Solicitări neservite: ",ne_deservite1+ne_servite2);

(writeln("Intensitatea cererilor care intră în sistem: ",(servite1+servite2)/_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 funcționării QS-ului

Orele de funcționare SMO

Cereri primite

Aplicații servite

Nu au fost primite cereri

Debit absolut al sistemului

Debitul relativ al sistemului

CAPITOLUL 3.NORME DE SIGURANȚĂ

Dispoziții generale

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

· Î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.

· Lucrarea elevilor în laboratorul 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 dispozitivele periferice trebuie așezate într-o poziție stabilă pe mese.

· Studenților le este strict interzis să intre în dispozitive. Puteți porni dispozitivele numai cu permisiunea profesorului.

Când se lucrează la o clasă de calculatoare, este interzis:

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

2. Întârzie la cursuri.

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

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

5. Așezați obiecte străine la locul de muncă.

6. Ridică-te în timp ce lucrezi, întoarce-te, vorbește cu vecinul tău.

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

8. Încălcați procedura 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 unitatea 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 și a tastaturii.

4. Încercați să depanați singur defecțiunile echipamentului.

5. Lucrați cu haine umede ș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 numele și parola dvs.;

8. Respectați modul de funcționare (în conformitate cu Normele și Standardele sanitare);

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

10. Dacă există o deteriorare accentuată a sănătății (dureri la nivelul ochilor, o deteriorare accentuată a vizibilității, incapacitatea de a concentra sau ascuți privirea, durere la degete și mâini, creșterea bătăilor inimii), părăsiți imediat locul de muncă, raportați incidentul la profesorul și consultați un medic;

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

12. Terminați lucrarea cu permisiunea profesorului.

13. Predați lucrarea finalizată.

14. Închideți toate programele active și opriți corect computerul.

15. Puneti in ordine locul de munca.

16. Ofițerul de serviciu ar trebui să verifice dacă biroul este pregătit pentru următoarea lecție.

La exploatarea echipamentului, trebuie să vă atenționați la: - electrocutare;

- avarii mecanice, leziuni

În caz de urgență:

1. Dacă se detectează scântei, apare un miros de ars sau sunt detectate alte probleme, ar trebui să încetați imediat lucrul și să anunțați profesorul.

2. Dacă cineva este lovit de un șoc electric, este necesar să: opriți lucrul și să vă deplasați la o distanță sigură; opriți tensiunea (la tabloul de distribuție al cabinetului); informează profesorul; Procedați cu primul ajutor și chemați un medic.

3. In caz de incendiu este necesar: oprirea lucrarilor si inceperea evacuarii; anunta profesorul si suna la pompieri (tel. 01); opriți tensiunea (la tabloul de distribuție al cabinetului); Se procedează la stingerea incendiului cu un stingător (este interzis să se stingă cu apă.

Documente similare

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

lucru curs, adăugat 09/07/2009


Conceptul de sistem de așteptare, esența și caracteristicile sale. Teoria cozilor de așteptare ca una dintre ramurile teoriei probabilităților, probleme luate în considerare. Conceptul și caracteristicile unui proces aleator, tipurile și modelele acestuia. Serviciu de așteptare.

lucrare de curs, adăugată 15.02.2009


Optimizarea controlului fluxului de cereri î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 este un domeniu al matematicii aplicate care analizează procesele din sistemele de producție în care evenimentele omogene se repetă de multe ori. Determinarea parametrilor unui sistem de asteptare cu caracteristici constante.

lucru curs, 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ții Kolmogorov. Limitarea probabilităților stărilor. Procese de moarte și reproducere.

rezumat, adăugat la 01.08.2013


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

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 unui sistem cu defecțiuni cu un sistem mixt corespunzător. Avantajele trecerii la un sistem cu proprietăți mixte.

lucrare de curs, adăugată 25.02.2012


Elaborarea unui model de simulare și calcularea indicatorilor de performanță ai unui sistem de așteptare pe baza unor parametri dați. Compararea indicatorilor de eficiență cu cei obținuți prin rezolvarea numerică a ecuațiilor Kolmogorov pentru probabilitățile stărilor sistemului.

lucrare curs, adaugat 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. Un sistem cu o limitare a duratei aplicației.

lucrare curs, adăugată 26.01.2014


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