Modele matematice ale celor mai simple sisteme de așteptare. Funcțiile p0(t) și p1(t) determină procesul de tranziție într-un QS cu un singur canal și descriu procesul de apropiere exponențială a QS la starea sa limită cu o constantă de timp caracteristică d

23 octombrie 2013 la 14:22

Squeak: Modelarea sistemelor de așteptare

• programare,
• OOP,
• Programare în paralel

Există foarte puține informații despre Habré despre un astfel de limbaj de programare precum Squeak. Voi încerca să vorbesc despre asta în contextul modelării sistemelor de așteptare. Vă voi arăta cum să scrieți o clasă simplă, să îi explic structura și să o utilizați într-un program care va servi cererile prin mai multe canale.

Câteva cuvinte despre Squeak

Squeak este o implementare deschisă, multiplatformă, a limbajului de programare Smalltalk-80, cu tastare dinamică și colectare de gunoi. Interfața este destul de specifică, dar destul de convenabilă pentru depanare și analiză. Squeak îndeplinește pe deplin conceptul de OOP. Totul este alcătuit din obiecte, chiar și din structuri dacă-atunci-altfel, pentru, în timp ce implementate cu ajutorul lor. Întreaga sintaxă se rezumă la trimiterea unui mesaj către obiect sub forma:

<объект> <сообщение>

Orice metodă returnează întotdeauna un obiect și i se poate trimite un mesaj nou.
Squeak este adesea folosit pentru modelarea proceselor, dar poate fi folosit și ca instrument pentru crearea de aplicații multimedia și o varietate de platforme educaționale.

Sisteme de așteptare

Sistemele de așteptare (QS) conțin unul sau mai multe canale care procesează cererile provenite din mai multe surse. Timpul de deservire a fiecărei cereri poate fi fix sau arbitrar, precum și intervalele dintre primirea acestora. Acesta ar putea fi o centrală telefonică, o spălătorie, casierii într-un magazin, un birou de dactilografiere, etc. Arată cam așa:

QS include mai multe surse care intră într-o coadă comună și sunt trimise pentru service pe măsură ce canalele de procesare devin libere. În funcție de caracteristicile specifice ale sistemelor reale, modelul poate conține un număr diferit de surse de aplicații și canale de servicii și poate avea restricții diferite privind lungimea cozii și posibilitatea asociată de pierdere a aplicațiilor (refuzuri).

La modelarea unui QS, problemele de estimare a lungimii medii și maxime a cozii de așteptare, frecvența defecțiunilor serviciului, încărcarea medie a canalelor și determinarea numărului acestora sunt de obicei rezolvate. În funcție de sarcină, modelul include blocuri software pentru colectarea, acumularea și prelucrarea datelor statistice necesare privind comportamentul proceselor. Cele mai utilizate modele de flux de evenimente în analiza QS sunt regulate și Poisson. Cele obișnuite sunt caracterizate de același timp între apariția evenimentelor, iar cele Poisson sunt caracterizate de cele aleatorii.

Puțină matematică

Pentru un flux Poisson, numărul de evenimente X, care se încadrează în intervalul de lungime τ (tau), adiacent punctului t, distribuit conform legii lui Poisson:
Unde a(t, τ)- numărul mediu de evenimente care au loc într-un interval de timp τ .
Numărul mediu de evenimente care au loc pe unitatea de timp este λ(t). Prin urmare, numărul mediu de evenimente într-un interval de timp τ , adiacent momentului de timp t, va fi egal cu:

Timp Tîntre două evenimente λ(t) = const = λ distribuite conform legii:
Densitatea de distribuție a unei variabile aleatoare T are forma:
Pentru a obține secvențe Poisson pseudoaleatoare ale intervalelor de timp t i rezolva ecuatia:
Unde r i- un număr aleatoriu distribuit uniform pe interval.
În cazul nostru, aceasta dă expresia:

Volume întregi ar putea fi scrise prin generarea de numere aleatorii. Aici, pentru a genera numere întregi distribuite uniform pe interval, folosim următorul algoritm:
Unde R i- un alt număr întreg aleatoriu;
R- un număr prim mare (de exemplu 2311);
Q- întreg - limita superioară a intervalului, de exemplu, 2 21 = 2097152;
rem- operația de obținere a restului din împărțirea numerelor întregi.

Valoarea initiala R0 de obicei, setate în mod arbitrar, de exemplu, folosind citirile temporizatorului:
Timp totalSecunde
Pentru a obține numere distribuite uniform pe un interval, folosim operatorul de limbă:

clasa Rand

Pentru a obține numere aleatoare distribuite uniform pe un interval, creăm o clasă - un generator de numere reale:

Float variableWordSubclass: #Rand „nume de clasă” instanceVariableNames: „” „variabile de instanță” classVariableNames: „R” „variabile de clasă” poolDictionaries: „” „dicționare generale” categoria: „Eșantion” „nume categorie”
Metode:

„Inițializare” init R:= Timp totalSeconds.next „Următorul număr pseudo-aleatoriu” următor R:= (R * 2311 + 1) rem: 2097152. ^(R/2097152) asFloat
Pentru a seta starea inițială a senzorului, trimiteți un mesaj Rand init.
Pentru a primi următorul număr aleatoriu pe care îl trimitem rand în continuare.

Programul de procesare a aplicațiilor

Deci, ca exemplu simplu, să facem următoarele. Să presupunem că trebuie să modelăm deservirea unui flux regulat de solicitări dintr-o singură sursă cu un interval de timp aleator între cereri. Există două canale de performanță diferită, permițându-vă să deserviți cererile în 2 și, respectiv, 7 unități de timp. Este necesar să se înregistreze numărul de cereri deservite de fiecare canal pe un interval de 100 de unități de timp.

Cod pentru Squeak

„Declararea variabilelor temporare” | proc1 proc2 t1 t2 s1 s2 sysPriority coada continua r | „Setări inițiale ale variabilei” Rand init. SysTime:= 0. s1:= 0. s2:= 0. t1:= -1. t2:= -1. continua:= adevarat. sysPriority:= Prioritate procesor activeProcess. Coada „Prioritate curentă”:= Semafor nou. „Solicitare model de coadă” „Crearea unui proces - model de canal 1” (Process forContext: [ proc1:= Procesor activeProcess. whileTrue: „Service cycle” [ coada de așteptare. „Așteptați cererea” t1:= SysTime + 2. „Următoarea activare time" s1:= s1 + 1. proc1 suspend. "Suspendați procesul în timp ce așteptați sfârșitul serviciului" ] proc1:= nil. "Eliminați referința la procesul 1" ] prioritate: (sysPriority + 1)) reluare. „Noua prioritate este mai mare decât fundalul” „Crearea unui proces - model de canal 2” (Process forContext: [ proc2:= Procesor activeProcess.. whileTrue: [ coada de așteptare. t2:= SysTime + 7. s2:= s2 + 1 .proc2 suspend. ] .proc2:= nil. ] prioritate: (sysPriority + 1)) reluare. „Continuarea descrierii procesului principal și a modelului sursă” în timp ce Adevărat: [ r:= (Rand următorul * 10) rotunjit. (r = 0) dacă este adevărat: . ((SysTime rem: r) = 0) ifTrue: . „Trimiteți cererea” „Comutați proces de service” (t1 = SysTime) ifTrue: . (t2 = SysTime) ifTrue: . SysTime:= SysTime + 1. „Model time is ticking” ]. „Afișează starea contorului de comenzi” PopUpMenu informează: „proc1: „,(s1 printString),”, proc2: „,(s2 printString). continua:= false.

Când a fost lansat, vedem că procesul 1 a reușit să proceseze 31 de solicitări, iar 2 doar 11:

Clasificare, concepte de bază, elemente de model, calculul caracteristicilor de bază.

La rezolvarea problemelor de organizare rațională a comerțului, serviciilor consumatorilor, depozitare etc. Este foarte util să se interpreteze activitățile structurii de producție ca sisteme de asteptare, adică un sistem în care, pe de o parte, există în mod constant solicitări de efectuare a unor lucrări, iar pe de altă parte, aceste solicitări sunt în mod constant satisfăcute.

Fiecare QS include patru elemente: flux de intrare, coadă, server, flux de ieșire.

Cerinţă(client, aplicație) în QS este fiecare cerere individuală de a efectua orice lucrare.

Serviciu- aceasta este executarea muncii pentru a satisface cerința primită. Obiectul care efectuează deservirea cererilor se numește dispozitiv de serviciu (dispozitiv) sau canal de serviciu.

Timpul de serviciu este perioada în care o cerere de serviciu este satisfăcută, de exemplu. perioada de la începerea serviciului până la finalizarea acesteia. Perioada de la momentul în care o cerere intră în sistem până la începerea serviciului se numește timp de așteptare a serviciului. Timpul de așteptare pentru service, împreună cu timpul de service, constituie timpul în care cererea rămâne în sistem.

SMO-urile sunt clasificate în funcție de diferite criterii.

1. Pe baza numărului de canale de servicii, QS-urile sunt împărțite în cu un singur canal și cu mai multe canale.

2. În funcție de condițiile de așteptare și de cerința începerii service-ului, se face distincție între QS cu pierderi (defecțiuni) și QS cu așteptare.

ÎN QS cu cerințe de pierdere, primite într-un moment în care toate dispozitivele sunt ocupate cu întreținerea, sunt respinse, sunt pierdute pentru acest sistem și nu au niciun efect asupra procesului de întreținere ulterioară. Un exemplu clasic de sistem defect este centrala telefonică - o cerere de conectare este refuzată dacă abonatul apelat este ocupat.

Pentru un sistem cu defecțiuni, principala caracteristică a eficienței operaționale este probabilitatea defecțiunii sau proporția medie a aplicațiilor care rămân neservite.

ÎN QS cu așteptarea cerințelor, care ajunge într-un moment în care toate dispozitivele sunt ocupate cu service, nu părăsește sistemul, ci intră într-o coadă și așteaptă până când unul dintre canale este liber. Când următorul dispozitiv devine disponibil, una dintre solicitările aflate în coadă este imediat acceptată pentru service.

Pentru un QS cu așteptare, principalele caracteristici sunt așteptările matematice privind lungimea cozii și timpul de așteptare.

Un exemplu de sistem de așteptare este procesul de restaurare a televizoarelor într-un atelier de reparații.

Există sisteme care se află între aceste două grupuri ( SMO mixt). Ele se caracterizează prin prezența unor condiții intermediare: restricții pot fi restricții asupra timpului de așteptare pentru începerea serviciului, asupra lungimii cozii etc.

Caracteristicile de performanță pot fi aplicate probabilității de defecțiune atât în ​​sistemele cu pierderi (sau caracteristicile de latență), cât și în sistemele de așteptare.

3. Conform disciplinei de întreținere, sistemele QS sunt împărțite în sisteme cu prioritate în întreținere și sisteme fără prioritate în întreținere.

Cererile pot fi deservite în ordinea în care sunt primite, fie aleatoriu, fie pe baza priorităților stabilite.

4. SMO poate fi monofazat și multifazat.

ÎN fază singulară sisteme, cerințele sunt deservite de canale de un tip (de exemplu, lucrători de aceeași profesie) fără a le transfera de la un canal la altul, în multifazic sisteme astfel de transferuri sunt posibile.

5. Pe baza locației sursei cerințelor, sistemele QS sunt împărțite în deschise (când sursa cerinței este în afara sistemului) și închise (când sursa se află în sistemul însuși).

LA închis Acestea includ sisteme în care fluxul de cereri de intrare este limitat. De exemplu, un maistru a cărui sarcină este să monteze mașinile într-un atelier trebuie să le întrețină periodic. Fiecare mașină ajustată devine o sursă potențială de cerințe de ajustare în viitor. În astfel de sisteme, numărul total de cerințe de circulație este finit și cel mai adesea constant.

Dacă sursa de alimentare are un număr infinit de cerințe, atunci sistemele sunt apelate deschis. Exemple de astfel de sisteme includ magazine, casele de bilete din gări, porturi etc. Pentru aceste sisteme, fluxul de cereri de intrare poate fi considerat nelimitat.

Metodele și modelele de cercetare QS pot fi împărțite în analitice și statistice (modelarea prin simulare a proceselor de așteptare).

Metodele analitice fac posibilă obținerea caracteristicilor unui sistem ca unele funcții ale parametrilor funcționării acestuia. Datorită acestui fapt, devine posibilă efectuarea unei analize calitative a influenței factorilor individuali asupra eficienței QS.

Din nefericire, doar o gamă destul de limitată de probleme din teoria cozilor de așteptare poate fi rezolvată analitic. În ciuda dezvoltării continue a metodelor analitice, în multe cazuri reale, o soluție analitică este fie imposibil de obținut, fie dependențele rezultate se dovedesc a fi atât de complexe încât analiza lor devine o sarcină dificilă în sine. Așadar, pentru a putea folosi metode analitice de soluționare, trebuie să se recurgă la diverse ipoteze simplificatoare, care este într-o oarecare măsură compensată de posibilitatea utilizării unei analize calitative a dependențelor finale (în acest caz, desigur, este necesar ca ipotezele făcute să nu denatureze imaginea reală a procesului).

În prezent, cele mai dezvoltate teoretic și mai convenabile în aplicațiile practice sunt metodele de rezolvare a problemelor de coadă în care fluxul de cerințe este cel mai simplu ( Poisson).

Pentru cel mai simplu flux, frecvența de sosire a cerințelor în sistem respectă legea lui Poisson, adică probabilitatea de a ajunge în timpul t egală cu k cerințe este dată de formula:

unde λ este parametrul de curgere (vezi mai jos).

Cel mai simplu flux are trei proprietăți principale: obișnuit, staționar și lipsă de efect secundar.

Ordinaritatea flux înseamnă imposibilitatea practică a sosirii simultane a două sau mai multe cereri. De exemplu, probabilitatea este destul de mică ca dintr-un grup de mașini deservite de o echipă de reparatori, mai multe utilaje să se defecteze în același timp.

Staționar numit curgere, pentru care așteptarea matematică a numărului de solicitări care intră în sistem pe unitatea de timp (notat cu λ) nu se modifică în timp. Astfel, probabilitatea ca un anumit număr de solicitări să intre în sistem într-o anumită perioadă de timp Δt depinde de valoarea acestuia și nu depinde de începutul numărării sale pe axa timpului.

Fără efect secundarînseamnă că numărul de cereri primite în sistem înainte de timpul t nu determină câte solicitări vor intra în sistem în timpul t + Δt.

De exemplu, dacă o rupere a firului are loc pe un războaie de țesut la un moment dat și este reparată de țesător, atunci acest lucru nu determină dacă va avea loc sau nu o nouă rupere pe acest răzător în momentul următor, cu atât mai puțin. afectează probabilitatea ca o rupere să apară pe alte războaie.

O caracteristică importantă a unui QS este timpul necesar pentru deservirea cerințelor din sistem. Timpul de serviciu este, de regulă, o variabilă aleatorie și, prin urmare, poate fi descris printr-o lege de distribuție. Cea mai utilizată în teorie și, mai ales în aplicații practice, este legea exponențială. Pentru această lege, funcția de distribuție a probabilității are forma:

F(t) = 1 – e -μt ,

acestea. probabilitatea ca timpul de serviciu să nu depășească o anumită valoare t este determinată de formula (1 – e -μt), unde μ este parametrul legii exponențiale a timpului de serviciu pentru cerințele din sistem - reciproca serviciului mediu timp, adica .

Să luăm în considerare modelele analitice ale QS cu așteptări(cel mai comun QS, în care cererile primite când toate unitățile de service sunt ocupate sunt puse în coadă și deservite pe măsură ce unitățile de service sunt eliberate).

Sarcinile cu cozi sunt tipice în mediile de producție, de exemplu, atunci când se organizează lucrări de reglare și reparații, în timpul întreținerii mai multor mașini etc.

Formularea generală a problemei este următoarea.

Sistemul este format din n canale de servire. Fiecare dintre ele poate îndeplini o singură cerință la un moment dat. Sistemul primește un flux simplu (Poisson) de cereri cu parametrul λ. Dacă, în momentul în care sosește următoarea cerere, există deja cel puțin n cereri în sistem pentru service (adică toate canalele sunt ocupate), atunci această solicitare devine în coadă și așteaptă să înceapă deservirea.

Timpul de serviciu al fiecărei cereri t despre este o variabilă aleatoare care se supune unei legi de distribuție exponențială cu parametrul μ.

După cum sa menționat mai sus, QS cu așteptări poate fi împărțit în două grupuri mari: închis și deschis.

Particularitățile funcționării fiecăruia dintre aceste două tipuri de sisteme își impun propria nuanță asupra aparatului matematic utilizat. Calculul caracteristicilor de funcționare ale diferitelor tipuri de QS poate fi efectuat pe baza calculării probabilităților stărilor QS (formule Erlang).

Deoarece sistemul este închis, la declarația problemei ar trebui adăugată o condiție: fluxul de cerințe de intrare este limitat, de exemplu. nu pot exista mai mult de m cerințe în sistemul de servicii în același timp (m este numărul de obiecte care sunt deservite).

Ca principale criterii care caracterizează calitatea funcționării sistemului luat în considerare, vom alege: 1) raportul dintre lungimea medie a cozii de așteptare și cel mai mare număr de cereri localizate simultan în sistemul de deservire - rata de nefuncționare a obiectului deservit; 2) raportul dintre numărul mediu de canale de difuzare inactive și numărul lor total - raportul de inactivitate al canalului deservit.

Să luăm în considerare calculul caracteristicilor probabilistice necesare (indicatorilor de performanță) ale unui QS închis.

1. Probabilitatea ca în sistem să existe k cerințe, cu condiția ca numărul acestora să nu depășească numărul de dispozitive de service n:

P k = α k P 0 , (1 ≤ k ≤ n),

Unde

λ este frecvența (intensitatea) cerințelor care intră în sistem dintr-o singură sursă;

Durata medie de deservire a unei cereri;

m este cel mai mare număr posibil de cerințe situate în sistemul de servire în același timp;

n - numărul de dispozitive de service;

P 0 este probabilitatea ca toate dispozitivele de serviciu să fie libere.

2. Probabilitatea ca în sistem să existe k cereri, cu condiția ca numărul acestora să fie mai mare decât numărul de dispozitive de service:

P k = α k P 0 , (n ≤ k ≤ m),

Unde

3. Probabilitatea ca toate dispozitivele de service să fie libere este determinată de condiție

prin urmare,

4. Numărul mediu de solicitări care așteaptă începerea serviciului (lungime medie a cozii de așteptare):

5. Solicitați rata de nefuncționare în așteptarea serviciului:

6. Probabilitatea ca toate dispozitivele de service să fie ocupate:

7. Numărul mediu de cerințe în sistemul de servire (servit și în așteptare):

8. Rata timpului de nefuncționare complet al cerințelor pentru întreținere și întreținere în așteptare:

9. Timp mediu de nefuncționare a unei cereri în coada de service:

10. Numărul mediu de dispozitive de service gratuit:

11. Raportul de nefuncţionare a dispozitivelor de service:

12. Probabilitatea ca numărul de cereri care așteaptă serviciul să fie mai mare decât un anumit număr B (probabilitatea ca în coada de așteptare să fie mai multe cereri de serviciu):

În multe domenii ale economiei, finanțelor, producției și vieții de zi cu zi, sistemele care implementează executarea repetată a sarcinilor similare joacă un rol important. Se numesc astfel de sisteme sisteme de așteptare ( SMO ). Exemple de QS sunt: ​​bănci de diferite tipuri, organizații de asigurări, inspectorate fiscale, servicii de audit, diverse sisteme de comunicații, complexe de încărcare și descărcare, benzinării, diverse întreprinderi și organizații de servicii.

3.1.1 Informații generale despre sistemele de așteptare

Fiecare QS este conceput pentru a deservi (îndeplinește) un anumit flux de aplicații (cerințe) care ajung la intrarea sistemului, de cele mai multe ori nu în mod regulat, ci în momente aleatorii. De asemenea, serviciul aplicațiilor nu durează un timp constant, prestabilit, ci unul aleatoriu, care depinde de multe motive aleatorii, uneori necunoscute nouă. După deservirea cererii, canalul este eliberat și gata să primească următoarea solicitare. Natura aleatorie a fluxului de aplicații și timpul de întreținere a acestora duce la o sarcină de lucru neuniformă a QS. În unele intervale de timp, solicitările se pot acumula la intrarea QS, ceea ce duce la o supraîncărcare a QS; în alte intervale de timp, când există canale libere (dispozitive de service) la intrarea QS, nu va exista cereri, ceea ce duce la o subîncărcare a QS-ului, adică la inactivitatea canalelor sale. Aplicațiile care se acumulează la intrarea în QS fie „se alătură” la coadă, fie din anumite motive nu pot continua să rămână în coadă, lasă QS-ul neservit.

Figura 3.1 prezintă diagrama QS.

Principalele elemente (caracteristici) ale sistemelor de așteptare sunt:

Unitate de service (bloc),

Fluxul aplicațiilor

Coadăîn așteptarea serviciului (disciplină în coadă).

Unitate de service concepute pentru a desfășura acțiuni conform cerințelor celor care intră în sistem aplicatii.

Orez. 3.1 Diagrama sistemului de așteptare

A doua componentă a sistemelor de așteptare este intrarea fluxul de aplicații. Aplicațiile sunt introduse în sistem aleatoriu. De obicei, se presupune că fluxul de intrare se supune unei legi probabilistice pe durata intervalelor dintre două cereri care sosesc succesiv și se presupune că legea de distribuție rămâne neschimbată pentru un timp destul de lung. Sursa aplicațiilor este nelimitată.

A treia componentă este disciplina la coada. Această caracteristică descrie ordinea cererilor de service care ajung la intrarea sistemului. Deoarece blocul de service, de regulă, are o capacitate limitată, iar aplicațiile ajung neregulat, se creează periodic o coadă de aplicații în așteptarea service-ului și, uneori, sistemul de service este inactiv în așteptarea aplicațiilor.

Caracteristica principală a proceselor de așteptare este aleatorietatea. În acest caz, există două părți care interacționează: cel servit și cel care servește. Comportamentul aleatoriu al cel puțin uneia dintre părți duce la natura aleatorie a procesului de servicii în ansamblu. Sursele aleatoriei în interacțiunea acestor două părți sunt evenimente aleatorii de două tipuri.

1. Apariția unei cereri (cerință) pentru service. Motivul aleatoriei acestui eveniment este adesea natura masivă a nevoii de serviciu.

2. Încheierea service-ului următoarei aplicații. Motivele aleatoriei acestui eveniment sunt atât caracterul aleatoriu al începerii serviciului, cât și durata aleatorie a serviciului în sine.

Aceste evenimente aleatoare constituie un sistem de două fluxuri în QS: fluxul de intrare al aplicațiilor pentru serviciu și fluxul de ieșire al aplicațiilor deservite.

Rezultatul interacțiunii acestor fluxuri de evenimente aleatoare este numărul de aplicații în prezent în QS, care este de obicei numit starea sistemului.

Fiecare QS, în funcție de parametrii săi de natura fluxului de aplicații, de numărul de canale de servicii și de productivitatea acestora și de regulile de organizare a muncii, are o anumită eficiență de operare (debit) care îi permite să facă față cu succes fluxului de aplicatii.

Domeniu special al matematicii aplicate teoria maselorîntreținere (TMO)– se ocupa de analiza proceselor in sistemele de asteptare. Subiectul de studiu al teoriei cozilor este QS.

Scopul teoriei cozilor este de a dezvolta recomandări pentru construirea rațională a QS, organizarea rațională a muncii lor și reglarea fluxului de cereri pentru a asigura o eficiență ridicată a operațiunii QS. Pentru atingerea acestui scop se stabilesc sarcinile teoriei cozilor care constau în stabilirea dependențelor eficacității funcționării QS de organizarea acestuia.

Problemele teoriei cozilor de așteptare sunt de natură de optimizare și vizează în cele din urmă determinarea unei versiuni a sistemului care să asigure un minim de costuri totale de la așteptarea serviciului, pierderea de timp și resurse pentru service și timpul de nefuncționare al unității de service. Cunoașterea acestor caracteristici oferă managerului informații pentru a dezvolta o influență direcționată asupra acestor caracteristici pentru a gestiona eficiența proceselor de așteptare.

Următoarele trei grupuri principale de indicatori (de obicei medii) sunt de obicei selectate ca caracteristici ale eficacității sistemului QS:

Indicatori ai eficacității utilizării QS:

Capacitatea absolută a QS este numărul mediu de solicitări pe care QS-ul le poate servi pe unitatea de timp.

Capacitatea relativă a QS este raportul dintre numărul mediu de cereri deservite de QS pe unitatea de timp și numărul mediu de cereri primite în același timp.

Durata medie a perioadei de angajare a OCM.

Rata de utilizare a QS este ponderea medie a timpului în care QS este ocupat cu solicitările de service etc.

Indicatori de calitate pentru cererile de service:

Timp mediu de așteptare pentru o aplicație în coadă.

Timpul mediu pe care o aplicație rămâne în CMO.

Probabilitatea ca o solicitare să fie refuzată fără a aștepta.

Probabilitatea ca o cerere primită să fie imediat acceptată pentru serviciu.

Legea de distribuție a timpului în care o aplicație rămâne în coadă.

Legea repartizării timpului în care o aplicație rămâne în QS.

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

Numărul mediu de aplicații în CMO etc.

Indicatori ai eficacității perechii „SMO - consumator”, unde „consumator” este înțeles ca întregul set de aplicații sau unele dintre ele

Operațiunile sau eficiența sistemului de așteptare sunt următoarele.

Pentru QS cu eșecuri:

Pentru SMO cu așteptare nelimitată atât debitul absolut cât și cel relativ își pierd sensul, deoarece fiecare solicitare primită va fi deservită mai devreme sau mai târziu. Pentru un astfel de QS, indicatorii importanți sunt:

Pentru Tip mixt QS se folosesc ambele grupe de indicatori: atât relativ cât şi debit absolut, și caracteristicile așteptărilor.

În funcție de scopul operațiunii de coadă, oricare dintre indicatorii dați (sau un set de indicatori) poate fi selectat ca criteriu de eficiență.

Model analitic Un QS este un set de ecuații sau formule care permit determinarea probabilităților stărilor sistemului în timpul funcționării acestuia și calcularea indicatorilor de performanță pe baza caracteristicilor cunoscute ale fluxului de intrare și canalelor de servicii.

Nu există un model analitic general pentru un QS arbitrar. Modelele analitice au fost dezvoltate pentru un număr limitat de cazuri speciale de QS. Modelele analitice care reflectă mai mult sau mai puțin precis sistemele reale sunt de obicei complexe și greu de vizualizat.

Modelarea analitică a unui QS este mult facilitată dacă procesele care au loc în QS sunt markoviane (fluxurile de cereri sunt simple, timpii de service sunt distribuiti exponențial). În acest caz, toate procesele din QS pot fi descrise prin ecuații diferențiale obișnuite, iar în cazul limită, pentru stările staționare, prin ecuații algebrice liniare și, după rezolvarea acestora, se pot determina indicatorii de eficiență selectați.

Să ne uităm la exemple de QS.

2.5.1. QS multicanal cu defecțiuni

Exemplul 2.5. Trei inspectori de trafic verifică borderourile șoferilor de camioane. Dacă cel puțin un inspector este liber, camionul care trece este oprit. Dacă toți inspectorii sunt ocupați, camionul trece fără oprire. Fluxul camioanelor este simplu, timpul de verificare este aleatoriu cu o distribuție exponențială.

Această situație poate fi modelată printr-un QS cu trei canale cu eșecuri (fără coadă). Sistemul este în buclă deschisă, cu solicitări omogene, monofazat, cu canale absolut fiabile.

Descrierea statelor:

Toți inspectorii sunt liberi;

Un inspector este ocupat;

Doi inspectori sunt ocupați;

Trei inspectori sunt ocupați.

Graficul stării sistemului este prezentat în Fig. 2.11.

Orez. 2.11.

Pe grafic: - intensitatea debitului camionului; - intensitatea verificărilor documentelor de către un singur inspector de trafic.

Se efectuează simularea pentru a determina porțiunea de vehicule care nu va fi testată.

Soluţie

Partea necesară a probabilității este probabilitatea de angajare a tuturor celor trei inspectori. Deoarece graficul de stare reprezintă o schemă tipică de „moarte și reproducere”, vom găsi folosirea dependențelor (2.2).

Capacitatea de transfer a acestui post de inspector de trafic poate fi caracterizată debit relativ:

Exemplul 2.6. Pentru a primi și procesa rapoarte de la grupul de recunoaștere, un grup de trei ofițeri a fost numit în departamentul de informații al asociației. Intensitatea estimată a fluxului de rapoarte este de 15 rapoarte pe oră. Timpul mediu pentru procesarea unui raport de către un ofițer este de . Fiecare ofițer poate primi rapoarte de la orice grup de recunoaștere. Ofițerul eliberat procesează ultimul dintre rapoartele primite. Rapoartele primite trebuie procesate cu o probabilitate de cel puțin 95%.

Stabiliți dacă echipa de trei ofițeri desemnată este suficientă pentru a îndeplini sarcina atribuită.

Soluţie

Un grup de ofițeri funcționează ca un CMO cu eșecuri, format din trei canale.

Flux de rapoarte cu intensitate poate fi considerat cel mai simplu, deoarece este totalul mai multor grupuri de recunoaștere. Intensitatea serviciului . Legea distribuției este necunoscută, dar acest lucru este neimportant, deoarece s-a demonstrat că pentru sistemele cu defecțiuni poate fi arbitrară.

Descrierea stărilor și graficul stărilor QS vor fi similare cu cele date în exemplul 2.5.

Deoarece graficul de stare este o schemă de „moarte și reproducere”, există expresii gata făcute pentru probabilitățile limită ale stării:

Atitudinea se numește dată fiind intensitatea fluxului de aplicaţii. Semnificația sa fizică este următoarea: valoarea reprezintă numărul mediu de cereri care ajung la QS în timpul mediu de deservire a unei cereri.

În exemplu .

În QS-ul luat în considerare, apare o defecțiune atunci când toate cele trei canale sunt ocupate, adică. Apoi:

Deoarece probabilitatea de eșecîn procesarea rapoartelor este mai mare de 34% (), atunci este necesar să se mărească personalul grupului. Să dublăm compoziția grupului, adică CMO va avea acum șase canale și să calculăm:

Astfel, doar un grup de șase ofițeri va putea procesa rapoartele primite cu o probabilitate de 95%.

2.5.2. QS multicanal cu așteptare

Exemplul 2.7. La secțiunea de trecere a râului există 15 instalații de trecere similare. Fluxul de echipamente care sosesc la trecere este în medie de 1 unitate/min, timpul mediu de traversare a unei unități de echipament este de 10 minute (inclusiv întoarcerea vehiculului de trecere).

Evaluați principalele caracteristici ale traversării, inclusiv probabilitatea unei traversări imediate imediat după sosirea unității de echipament.

Soluţie

Debit absolut, adică tot ce se apropie de trecere este practic traversat imediat.

Numărul mediu de instalații de trecere în funcțiune:

Rate de utilizare a feribotului și perioade de nefuncționare:

A fost dezvoltat și un program pentru a rezolva exemplul. Se presupune că intervalele de timp pentru care echipamentele ajung la trecere și timpul de trecere sunt distribuite conform unei legi exponențiale.

Ratele de utilizare a traversării după 50 de curse sunt aproape aceleași: .

INTRODUCERE

CAPITOLUL I. FORMULAREA PROBLEMELOR DE SERVICIUL COZII

1.1 Concept general al teoriei cozilor

1.2 Modelarea sistemelor de aşteptare

1.3 Grafice de stare QS

1.4 Procese aleatorii

Capitolul II. ECUAȚII DE DESCRIERE A SISTEMELOR DE COZI

2.1 Ecuații Kolmogorov

2.2 Procese de „naștere - moarte”

2.3 Formularea economică și matematică a problemelor de coadă

Capitolul III. MODELE DE SISTEME DE COZI DE COZI

3.1 QS cu un singur canal cu refuz de serviciu

3.2 QS multicanal cu refuz de serviciu

3.3 Modelul unui sistem de servicii turistice multifazice

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

3.5 QS cu un singur canal cu coadă nelimitată

3.6 QS multicanal cu lungime limitată la coadă

3.7 QS multicanal cu coadă nelimitată

3.8 Analiza sistemului de așteptare a supermarketurilor

CONCLUZIE

Introducere

În prezent, a apărut o mare cantitate de literatură dedicată direct teoriei cozilor, dezvoltării aspectelor sale matematice, precum și diferitelor domenii de aplicare a acesteia - militar, medical, transport, comerț, aviație etc.

Teoria de așteptare se bazează pe teoria probabilității și statistica matematică. Dezvoltarea inițială a teoriei cozilor este asociată cu numele savantului danez A.K. Erlang (1878-1929), cu lucrările sale în domeniul proiectării și exploatării centralelor telefonice.

Teoria cozilor este un domeniu al matematicii aplicate care se ocupă cu analiza proceselor din sistemele de producție, servicii și management în care evenimentele omogene sunt repetate de multe ori, de exemplu, în întreprinderile de servicii pentru consumatori; în sisteme de primire, procesare și transmitere a informațiilor; linii automate de producție etc. O mare contribuție la dezvoltarea acestei teorii a avut-o matematicienii ruși A.Ya. Khinchin, B.V. Gnedenko, A.N. Kolmogorov, E.S. Wentzel et al.

Subiectul teoriei cozilor de așteptare este stabilirea dependențelor între natura fluxului de cereri, numărul de canale de servicii, performanța unui canal individual și serviciul eficient pentru a găsi cele mai bune modalități de gestionare a acestor procese. Problemele teoriei cozilor de așteptare sunt de natură de optimizare și includ în cele din urmă aspectul economic al determinării unei opțiuni de sistem care să asigure un minim de costuri totale de la așteptarea serviciului, pierderea de timp și resurse pentru service și timpul de nefuncționare a canalelor de servicii.

În activitățile comerciale, aplicarea teoriei cozilor de așteptare nu a găsit încă distribuția dorită.

Acest lucru se datorează în principal dificultății de stabilire a sarcinilor, nevoia de înțelegere profundă a conținutului activităților comerciale, precum și instrumente fiabile și precise care permit calcularea diferitelor opțiuni pentru consecințele deciziilor de management în activitățile comerciale.

Capitol eu . Setarea sarcinilor de așteptare

1.1 Conceptul general al teoriei cozilor

Natura serviciilor de masă, în diverse domenii, este foarte subtilă și complexă. Activitatea comercială este asociată cu efectuarea multor operațiuni în etapele de mișcare, de exemplu, masa mărfurilor din sfera producției în sfera consumului. Astfel de operațiuni sunt încărcarea mărfurilor, transportul, descărcarea, depozitarea, procesarea, ambalarea și vânzarea. Pe lângă astfel de operațiuni de bază, procesul de circulație a mărfurilor este însoțit de un număr mare de operațiuni preliminare, pregătitoare, de însoțire, paralele și ulterioare cu documente de plată, containere, bani, mașini, clienți etc.

Fragmentele de activitate comercială enumerate se caracterizează prin sosirea masivă a mărfurilor, banilor și vizitatorilor în momente aleatorii, apoi deservirea lor secvențială (satisfacerea cererilor, solicitărilor, aplicațiilor) prin efectuarea de operațiuni adecvate, al căror timp de execuție este și el aleatoriu. Toate acestea creează denivelări în muncă, dau naștere la subîncărcări, timpi de nefuncționare și supraîncărcări în operațiunile comerciale. Cozile cauzează multe probleme, de exemplu, pentru vizitatorii din cafenele, cantine, restaurante sau șoferii de mașini de la depozitele de mărfuri care așteaptă descărcarea, încărcarea sau documentele. În acest sens, se ridică sarcinile de analiză a opțiunilor existente pentru efectuarea întregului set de operațiuni, de exemplu, podeaua de vânzare a unui supermarket, restaurant sau în ateliere pentru producerea de produse proprii în scopul evaluării muncii lor, identificând verigi slabe. și rezerve pentru elaborarea în ultimă instanță a recomandărilor care vizează creșterea eficienței activităților comerciale.

În plus, apar și alte sarcini legate de crearea, organizarea și planificarea unei noi opțiuni economice, raționale pentru efectuarea multor operațiuni în cadrul platformei comerciale, cofetăriei, toate nivelurile de servicii într-un restaurant, cafenea, cantină, departament de planificare, contabilitate, departamentul de personal etc.

Sarcinile de organizare a serviciilor de masă apar în aproape toate sferele activității umane, de exemplu, vânzătorii care deservesc clienții în magazine, deservesc vizitatorii în unități de alimentație publică, deservesc clienții în întreprinderile de servicii pentru consumatori, furnizarea de convorbiri telefonice la o centrală telefonică, acordarea de îngrijiri medicale pentru pacienţii dintr-o clinică etc. În toate exemplele de mai sus, există necesitatea de a satisface nevoile unui număr mare de consumatori.

Problemele enumerate pot fi rezolvate cu succes folosind metode și modele de teorie a cozilor de așteptare (QST) special create în aceste scopuri. Această teorie explică faptul că este necesar să se servească pe cineva sau ceva, care este definit de conceptul de „cerere de serviciu (cerere)”, iar operațiunile de serviciu sunt efectuate de cineva sau ceva numit canale de servicii (noduri). Rolul cererilor în activitățile comerciale îl au bunurile, vizitatorii, banii, auditorii, documentele, iar rolul canalelor de servicii îl joacă vânzătorii, administratorii, bucătarii, cofetarii, ospătarii, casierii, experții în marfă, încărcătoarele, echipamentele comerciale etc. Este important de remarcat faptul că într-o variantă de realizare, de exemplu, un bucătar în procesul de preparare a mâncărurilor este un canal de serviciu, iar într-o alta el acționează ca o cerere de serviciu, de exemplu către directorul de producție pentru a primi mărfuri.

Aplicațiile, din cauza numărului masiv de chitanțe pentru service, formează fluxuri care sunt numite primite înainte de efectuarea operațiunilor de service și după o posibilă așteptare pentru începerea service-ului, de ex. timpul de inactivitate în serviciul din formularul de coadă curge în canale și apoi se formează un flux de cereri de ieșire. În general, combinația de elemente ale fluxului de cereri de intrare, o coadă, canale de servicii și fluxul de cereri de ieșire formează cel mai simplu sistem de așteptare cu un singur canal - QS.

Un sistem este înțeles ca un set de sisteme interconectate. părți (elemente) care interacționează intenționat. Exemple de astfel de QS simple în activități comerciale sunt locurile de primire și procesare a mărfurilor, centrele de plată pentru clienți din magazine, cafenele, cantine, locuri de muncă pentru economiști, contabili, comercianți, bucătari etc.

Procedura de service este considerată finalizată atunci când cererea de service părăsește sistemul. Durata intervalului de timp necesar implementării procedurii de service depinde în principal de natura solicitării de service, de starea sistemului de servicii în sine și de canalul de serviciu.

Într-adevăr, durata șederii unui cumpărător într-un supermarket depinde, pe de o parte, de calitățile personale ale cumpărătorului, de solicitările acestuia, de gama de bunuri pe care urmează să le achiziționeze și, pe de altă parte, de forma de organizare a serviciului și a personalului de service, ceea ce poate afecta semnificativ șederea cumpărătorului.în supermarket și intensitatea serviciului. De exemplu, stăpânirea metodei „oarbe” de lucru la o casă de marcat de către casierii-controlori a făcut posibilă creșterea debitului nodurilor de plată de 1,3 ori și economisirea timpului petrecut cu decontările cu clienții la fiecare casă de marcat cu mai mult de 1,5 ore. pe zi. Introducerea unui singur centru de plată într-un supermarket oferă beneficii tangibile cumpărătorului. Astfel, dacă cu forma tradițională de plată timpul pentru deservirea unui client a fost în medie de 1,5 minute, atunci odată cu introducerea unei unități de plată unice a fost de 67 de secunde. Dintre acestea, 44 de secunde sunt cheltuite pentru efectuarea unei achiziții în secțiune și 23 de secunde direct pentru plățile pentru achiziții. Dacă cumpărătorul face mai multe achiziții în secțiuni diferite, atunci pierderea de timp se reduce la achiziționarea a două achiziții de 1,4 ori, de trei cu 1,9, de cinci cu 2,9 ori.

Prin cereri de service înțelegem procesul de satisfacere a unei nevoi. Serviciile sunt de natură variată. Cu toate acestea, în toate exemplele, solicitările primite necesită service de către un anumit dispozitiv. În unele cazuri, serviciul este efectuat de o singură persoană (servirea către cumpărător de către un vânzător, în unele - de către un grup de persoane (servirea unui pacient de către o comisie medicală într-o clinică), iar în unele cazuri - prin dispozitive tehnice (vânzarea de apă gazoasă, sandvișuri prin automate) Un set de mijloace pe care le solicită serviciul, se numește canal de servicii.

Dacă canalele de servicii sunt capabile să satisfacă cereri identice, atunci canalele de servicii sunt numite omogene. Un set de canale omogene de servicii se numește sistem de servicii.

Sistemul de așteptare primește un număr mare de solicitări în momente aleatorii, a căror durată de serviciu este, de asemenea, o variabilă aleatorie. Sosirea secvențială a aplicațiilor în sistemul de servicii se numește flux de aplicații de intrare, iar succesiunea de aplicații care părăsesc sistemul de servicii se numește flux de ieșire.