Teoria cozilor în exemple. Modelul teoriei cozilor în management. Vechi mecanism de așteptare a locurilor de muncă

Această teorie reprezintă o secțiune specială a teoriei proceselor aleatoare și folosește în principal aparatul teoriei probabilităților. Primele publicații în acest domeniu datează din anii 20. secolul XX și aparțin danezului A. Erlang, care a fost angajat în cercetarea funcționării centralelor telefonice - QS tipic, în care momentele apelului sunt aleatorii, faptul că abonatul sau toate canalele sunt ocupate și durata conversației . Ulterior, teoria cozilor a fost dezvoltată în lucrările multor matematicieni sovietici și străini.

Teoria cozilor de așteptare este o ramură a teoriei probabilităților care studiază modele matematice ale diferitelor tipuri de sisteme de așteptare reale. Aceste modele reprezintă procese aleatorii de tip special, care sunt uneori numite procese de service. Cel mai adesea, se folosește o definiție descriptivă a acestor procese, deoarece construcția lor formală se dovedește a fi foarte complexă și nu întotdeauna eficientă.

Teoria de așteptare folosește în principal aparatul teoriei probabilităților. Sarcinile principale ale teoriei cozilor constau de obicei în studierea, pe baza proprietăților „locale” ale proceselor aleatorii luate în considerare, a caracteristicilor staționare ale acestora (dacă există) sau a comportamentului acestor caracteristici pe o perioadă lungă de timp. Unul dintre principalele obiective finale ale cercetării în acest domeniu este de a selecta cea mai rezonabilă organizare a sistemelor de așteptare.

Sistemele de așteptare (QS) sunt sisteme care primesc cereri de serviciu în momente aleatorii, iar cererile primite sunt deservite folosind canalele de servicii disponibile pentru sistem.

Din perspectiva modelării procesului de așteptare, situațiile în care se formează cozi de aplicații (cerințe) pentru serviciu apar după cum urmează. După ce a ajuns la sistemul de deservire, cererea se alătură la coada altor solicitări (primite anterior). Canalul de servicii selectează o solicitare dintre cei din coadă pentru a începe să o deservească. După finalizarea procedurii de deservire a următoarei cereri, canalul de servicii începe să deservească următoarea cerere, dacă există una în blocul de așteptare.

Ciclul de funcționare al unui sistem de așteptare de acest fel se repetă de multe ori pe toată perioada de funcționare a sistemului de service. Se presupune că trecerea sistemului la deservirea următoarei solicitări după finalizarea deservirii cererii anterioare are loc instantaneu, la momente aleatorii.

Exemple de sisteme de așteptare includ: magazine, bănci, ateliere de reparații, oficii poștale, stații de service auto, stații de reparații auto, calculatoare personale care deservesc aplicațiile primite sau cerințele pentru rezolvarea anumitor probleme, firme de audit, departamente de inspecție fiscală implicate în acceptarea și verificarea raportării curente. de întreprinderi, centrale telefonice etc.

Componentele principale ale unui sistem de așteptare de orice tip sunt:

fluxul de intrare al cerințelor primite sau al solicitărilor de servicii;

disciplina la coada;

mecanism de service.

Fluxul cerințelor de intrare. Pentru a descrie fluxul de intrare, este necesar să se precizeze o lege probabilistică care să determine succesiunea momentelor de primire a cererilor de serviciu și să se indice numărul de astfel de solicitări în fiecare sosire ulterioară. În acest caz, de regulă, ele operează cu conceptul de „distribuție probabilistică a momentelor de primire a cerințelor”. Atât cerințele individuale, cât și cele de grup pot fi primite aici (cerințele sunt primite în grupuri în sistem). În acest din urmă caz, vorbim de obicei despre un sistem de așteptare cu servicii de grup paralel.

Disciplina la coada- aceasta este o componentă importantă a sistemului de așteptare; determină principiul conform căruia cerințele care ajung la intrarea sistemului de service 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;
• - vino ultimul, fii servit primul;
• - selectarea aleatorie a aplicațiilor;
• - selectia aplicatiilor pe criterii de prioritate;
• - limitarea timpului de așteptare pentru momentul deservirii (există o coadă cu un timp de așteptare limitat pentru serviciu, care este asociată cu conceptul de „lungime permisă de coadă”).

Mecanism de service determinate de caracteristicile procedurii de service în sine și de structura sistemului de servicii. Caracteristicile unei proceduri de service includ: durata procedurii de service și numărul de cerințe îndeplinite ca urmare a fiecărei astfel de proceduri. Pentru a descrie analitic caracteristicile unei proceduri de service, este utilizat conceptul de „distribuție probabilistică a timpului pentru cerințele 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 necesar să se țină cont și de probabilitatea ca dispozitivul de service să plece după un anumit interval de timp limitat.

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ă apar servicii paralele.

Un sistem de service poate consta din mai multe tipuri diferite de canale de service prin care trebuie să treacă fiecare cerință de service, adică, în sistemul de service, procedurile de service sunt implementate secvențial. Mecanismul de service determină caracteristicile fluxului de cereri de ieșire (servite).

După ce am examinat principalele componente ale sistemelor de servicii, putem afirma că 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);
• - distributia probabilistica a duratei de serviciu;
• - configurarea sistemului de service (servire paralelă, secvențială sau paralel-secvențială);
• - numărul și productivitatea canalelor de servicii;
• - disciplina la coada;
• - puterea sursei cerinţelor.

Principalele criterii de eficacitate a funcționării sistemelor de așteptare, în funcție de natura problemei care se rezolvă, pot fi:

• - probabilitatea deservirii imediate a unei aplicații primite;
• - probabilitatea refuzului de a deservi o aplicație primită;
• - debitul relativ și absolut al sistemului;
• - procentul mediu de cereri care au fost refuzate serviciul;
• - timpul mediu de așteptare la coadă;
• - lungimea medie a cozii;
• - venitul mediu din exploatarea sistemului pe unitatea de timp etc.

Subiect Teoria stării de așteptare 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.

Indiferent de natura procesului care are loc în sistemul de așteptare, există două tipuri principale de QS:

• - sisteme cu refuzuri, în care o aplicație care intră în sistem într-un moment în care toate canalele sunt ocupate este respinsă și iese imediat din coadă;
• - sisteme cu waiting (queuing), în care o solicitare care sosește într-un moment în care toate canalele de servicii sunt ocupate este plasată într-o coadă și așteaptă până când unul dintre canale este liber.

Sistemele de așteptare cu așteptare sunt împărțite în sisteme cu așteptare limitată și sisteme cu așteptare nelimitată.

Sistemele de așteptare limitată pot limita:

• - lungimea cozii;
• - timpul petrecut la coadă.

În sistemele cu așteptare nelimitată, o aplicație aflată într-o coadă așteaptă serviciul pentru un timp nelimitat, de ex. pana iti vine randul.

Pe baza numărului de canale de servicii, QS sunt împărțite în următoarele grupuri:

SMO cu un singur canal. Este format dintr-o coadă și un dispozitiv de service. Termenul „cale unică” înseamnă că există o singură cale care duce la dispozitivul de service.

QS multicanal. Deservirea următoarei solicitări poate începe înainte de încheierea deservirii cererii anterioare. Fiecare canal acționează ca un dispozitiv de serviciu independent.

Pe baza gamei de obiecte deservite, se disting două tipuri.

QS închis. Un sistem de așteptare închisă este un sistem de așteptare în care cererile deservite pot fi returnate în sistem și reintroduse pentru service. Exemple de sistem închis sunt atelierele de reparații și casele de economii.

Deschideți SMO. Pentru un QS deschis, se presupune că populația inițială este atât de mare încât o modificare a dimensiunii acesteia, ca urmare a sosirii sau întoarcerii unei cereri deservite către populația inițială, nu are un impact semnificativ asupra probabilității apariției următoarea cerere. coadă matematică monofazată

Dacă dispozitivele de serviciu sunt conectate în paralel, atunci un astfel de serviciu se numește monofazat, iar dacă dispozitivele sunt conectate în serie, atunci este multifazat (o serie de operații secvențiale).

Sisteme de așteptare monofazate - Sunt sisteme omogene care efectuează aceeași operațiune de service.

Sistem multifazic de asteptare - Acestea sunt sisteme în care canalele de servicii sunt aranjate secvențial și efectuează diverse operațiuni de service. Un exemplu de QS multifazic sunt stațiile de service auto.

Clasificarea dată a QS este condiționată. În practică, cel mai adesea QS-urile acționează ca sisteme mixte. De exemplu, cererile așteaptă ca serviciul să înceapă până la un anumit punct, după care sistemul începe să funcționeze ca un sistem cu defecțiuni.

În 1953, G. Kendall a propus notații de definiție standard care sunt folosite de cercetători fără modificări. Pentru QS monofazat, simbolismul lui Kendall este următorul:

A/B/n/m 2.1

Unde A și B sunt fluxul de intrare și, respectiv, fluxul de servicii,

n - numărul de canale, n 1,

m este capacitatea de stocare.

Fluxurile de evenimente aleatoare pot lua diferite forme:

• - M - distribuția exponențială a duratelor intervalelor de primire a cererilor sau duratelor serviciului (index M din cuvântul definitoriu proces Markov, adică unul când comportamentul procesului după timpul t depinde doar de starea procesului la momentul t și nu nu depinde de comportamentul înainte de timpul t),
• - D - distribuția deterministă a duratelor intervalelor de primire a cererilor sau a duratelor de servicii,
• - Ek - flux Erlang de ordinul k-lea pe durata intervalelor dintre sosiri de cereri sau durate de servicii,
• - GI - flux recurent (duratele intervalelor sunt independente statistic și au aceeași distribuție),
• - G - tip general de distribuție.

Apoi, în simbolurile Kendall, în loc de A și B, simbolul unuia dintre fluxurile menționate este înlocuit, de exemplu:

M/M/1 - fluxuri exponențiale cu un canal de serviciu și capacitate nelimitată.

D/GI/5/10 - flux de intrare determinist, flux de servicii recurente, QS multicanal cu 5 canale identice, capacitate de stocare 10 etc.

3. Teoria cozilor

Definiți caracteristicile de sosire ale sistemelor liniare de așteptare

Cunoștințele de bază despre liniile de servicii se numesc teoria cozilor de așteptare.

Costurile serviciilor cresc pe măsură ce o firmă încearcă să-și crească nivelul de servicii. Managerii unui astfel de centru de service pot varia capacitatea prin plasarea mașinilor și a personalului în stații de service speciale și pot preveni sau reduce cozile inutil de lungi. În depozitele magazinelor alimentare, managerii și angajații pot lucra în spatele ghișeului atunci când este necesar. La bănci și aeroporturi, lucrătorii cu normă parțială pot fi chemați să ajute. Pe măsură ce serviciul se îmbunătățește (de exemplu, se accelerează), timpul petrecut în așteptarea serviciului scade, așa cum arată linia descrescătoare. Costurile de așteptare pot reflecta pierderea productivității lucrătorilor în timp ce uneltele sau mașinile lor așteaptă reparații sau pot fi pur și simplu costul pierderii clienților din cauza serviciului slab și a cozilor lungi. În astfel de sisteme de servicii (de exemplu, în ambulanțele de urgență), costul așteptărilor lungi poate fi insuportabil de mare.

Orez. 1. Relația dintre costurile de așteptare și costurile de servicii

O prezentare generală a celor trei părți ale sistemelor liniare de așteptare sau cozi:

1) sosiri sau intrări în sistem;

2) disciplina la coadă, sau sistemul de așteptare însuși;

3) echipamente de service.

Aceste trei componente au anumite caracteristici care trebuie studiate înainte de a putea fi dezvoltate modele matematice de așteptare.

Caracteristici de sosire. Sursa de intrare care generează sosiri sau clienți ai unui sistem de servicii are trei caracteristici principale. Trei caracteristici importante sunt dimensiunea sursei, modelele de sosire în sistemul de așteptare și comportamentul de sosire.

1. Dimensiunea sursei. Dimensiunea de sosire este considerată fie nelimitată (practic infinită), fie limitată (finită). Atunci când numărul de clienți sau de sosiri în orice moment este doar o mică parte din numărul de sosiri potențiale, sursa de sosire este considerată nelimitată sau infinită. În viața practică, exemplele de surse nelimitate includ mașinile de la benzinării, cumpărătorii de la un supermarket și studenții care se înscriu la cursuri la o universitate mare. Majoritatea modelelor de așteptare permit astfel de surse de sosire nelimitate.

Un exemplu de sursă limitată sau finită este un centru de copiere cu doar opt copiatoare, care poate eșua și necesită service.

2. Eșantion de sosire în sistem. Clienții ajung la punctul de service fie conform unui program cunoscut (de exemplu, un pacient la fiecare 15 minute sau un student pentru consultație la fiecare jumătate de oră) sau aleatoriu. Sosirile sunt considerate aleatorii dacă sunt independente unele de altele și apariția lor nu poate fi prezisă cu exactitate.

Adesea, în teoria stării de așteptare, numărul de sosiri pe unitatea de timp poate fi determinat folosind o distribuție de probabilitate cunoscută sub numele de distribuție Poisson. Pentru orice număr dat de sosiri (doi clienți pe oră sau patru camioane pe minut), distribuția Poisson discretă poate fi determinată prin formula:

pentru x=0, 1, 2, 3, 4...

unde P (x) este probabilitatea de sosire x;

x - numărul de sosiri pe unitatea de timp;

a - numărul mediu de sosiri;

e este baza logaritmului natural 2,7183.

Comportamentul de sosire. Majoritatea modelelor de așteptare presupun că clienții care intră sunt „răbdători”. Clienții pacienți sunt persoane sau mașini care stau la coadă până sunt serviți și nu schimbă cozile. Din păcate, viața este mai complicată pentru că oamenii nu au întotdeauna răbdare. Clienții nerăbdători refuză să se înscrie la coadă pentru că este prea lungă, ceea ce nu se potrivește nevoilor și intereselor lor. Un alt tip de clienți nerăbdători sunt cei care, s-au alăturat la coadă, apoi devin nerăbdători și părăsesc coada fără a finaliza acțiunea. Într-adevăr, ambele situații nu fac decât să evidențieze necesitatea teoriei cozilor și a analizei așteptării în cozi.

Definiți caracteristicile de așteptare ale sistemelor liniare de așteptare

Caracteristicile cozii. Linia de așteptare în sine este a doua componentă a sistemului de așteptare. Lungimea cozii poate fi fie limitată, fie nelimitată. O coadă este limitată dacă nu poate, prin lege sau prin limitare fizică, să crească la infinit. Acesta poate fi cazul unui salon de coafură mic care are doar un număr limitat de zone de așteptare. Modelele de cozi analitice discutate în acest capitol funcționează cu cozi de lungime nelimitată. O coadă este nelimitată dacă nu există nicio limită pentru dimensiunea sa, ca în exemplul deservirii mașinilor care sosesc.

A doua caracteristică a cozilor se referă la disciplina cozilor. Aceasta se referă la regula prin care clienții în linie primesc serviciul. Majoritatea sistemelor folosesc o disciplină de așteptare cunoscută sub numele de primul intrat, primul ieșit (F1FO).

Într-un spital sau supermarket la un punct de check-out expres, este posibil ca diferite priorități să nu respecte regula F1FO. Pacienților din spital care sunt grav bolnavi li se poate acorda prioritate pentru îngrijire față de pacienții cu răni ușoare. Clienții cu mai puțin de zece achiziții pot merge la centrul de casă rapidă (dar apoi sunt tratați pe principiul primul venit, primul servit).

Termenul F1FS (primul intrat, primul iesit) este folosit ca substitut pentru F1FO, iar o alta disciplina LIFS (ultimul intrat, primul iesit) este comuna atunci cand materialele sunt aranjate in acest fel. că nu se poate ajunge decât de sus.

Caracteristicile configurațiilor sistemului de service

Configurații de bază ale sistemului de așteptare. Sistemele de servicii sunt de obicei clasificate după numărul de canale, de exemplu numărul de servere, și numărul de faze, numărul de elemente de serviciu care trebuie finalizate.

Sistem de așteptare cu un singur canal - cu un singur server, de exemplu, o bancă care are o singură fereastră de serviciu deschisă sau un punct de service într-un restaurant fast-food. Pe de altă parte, dacă o bancă are mai mulți funcționari și fiecare client așteaptă într-o singură coadă comună la primul slot disponibil, atunci avem un sistem de cozi cu mai multe linii. Majoritatea băncilor de astăzi sunt sisteme de servicii multicanal, la fel ca majoritatea saloanelor de coafură, caselor de bilete de avion și oficiilor poștale.

Un sistem de service monofazat este unul în care clientul primește serviciul de la o singură stație și apoi părăsește sistemul. Un restaurant cu servicii rapide în care persoana care ia comanda aduce și mâncare și primește bani este un sistem monofazat. Deci, în biroul de permis de conducere în care persoana. acceptând aplicația, efectuează și teste și colectează bani, are loc un sistem monofazat. Dacă un restaurant vă cere să plasați o comandă într-o locație, să plătiți la alta și să vă ridicați mâncarea într-o a treia, acesta devine un sistem multifazic. În consecință, dacă agenția de permis de conducere este mare sau foarte ocupată, clientul va trebui probabil să aștepte la coadă pentru a completa cererea (prima oprire de service), apoi să stea din nou pentru test (a doua oprire de service) și, în final, în locul trei plătesc bani.

Așteptarea unui tip de serviciu face parte din viața noastră de zi cu zi. Așteptăm să luăm masa în restaurante, stăm la coadă la casă la magazine și ne aliniem la oficiile poștale. Cozile apar aproape în toate locurile publice: inspectoratele fiscale, birourile de pașapoarte, companiile de asigurări etc. Fenomenul de așteptare este caracteristic nu numai oamenilor: munca la coadă pentru execuție; un grup de avioane de pasageri care așteaptă permisiunea de a ateriza pe aeroport; mașini a căror mișcare este suspendată de un semafor pe traseul lor, nave de marfă care așteaptă încărcarea/descărcarea în port etc.

Studiul cozilor în sistemele de așteptare (QS) ne permite să stabilim criteriile de funcționare a sistemului de service, dintre care cele mai semnificative sunt timpul mediu de așteptare în coadă și lungimea medie a cozii. Aceste informații sunt apoi utilizate pentru a selecta nivelul adecvat de serviciu, așa cum este demonstrat în exemplul următor.

Exemplu 2.6.1. Persoanele fizice care depun declarații de impozit pe venit se plâng de serviciul lent. În această unitate lucrează în prezent trei inspectori fiscali. În urma calculelor, formulele pentru care vom avea în vedere mai jos, s-a descoperit următoarea relație între numărul de inspectori și timpul de așteptare pentru serviciu.

Număr de inspectori 1 2 3 4 5 6 7

Timp mediu de așteptare 80,2 50,3 34,9 24,8 14.912,9 9,4

______(minute) _______________________________________

Datele arată că, cu trei inspectori angajați în prezent, timpul mediu de așteptare pentru serviciu este de aproximativ 35 de minute. Potrivit vizitatorilor, o așteptare de 15 minute ar fi acceptabilă. După cum reiese din aceleași date, timpul mediu de așteptare devine mai mic de 15 minute dacă numărul de inspectori este mai mare sau egal cu cinci.

Rezultatele studiului sistemului de servicii pot fi folosite și pentru a optimiza un model de cost care minimizează suma costurilor asociate cu furnizarea de servicii și pierderile din cauza întârzierilor în livrarea acestora. În fig. Figura 2.6.1 prezintă un model de cost tipic al unui sistem de servicii, în care costurile serviciilor cresc pe măsură ce nivelul acestuia crește. În același timp, pierderile datorate întârzierilor în prestarea serviciilor scad pe măsură ce nivelul serviciului crește.

Nivel de servicii

Principala problemă asociată cu utilizarea modelelor de cost este dificultatea de a estima pierderile pe unitatea de timp din cauza întârzierilor în furnizarea serviciilor.

Problemele de coadă apar când cereri de servicii (sau cerințe) nu poate fi efectuată din cauza ocupației personal de întreținere (echipamente) sau ea însăși sistem de service se dovedește a fi inactiv din cauza lipsei de aplicații. La modelarea acestor probleme se folosesc concepte fundamentale ale teoriei probabilităților, deoarece fluxul de cereri sau durata serviciului, sau ambele, sunt aleatorii. La rezolvarea acestor probleme este necesar să se determine fie numărul optim de canale de servire, fie debitul optim (sau să se găsească momentele de sosire a cererilor).

Se mai numește și clasa de modele potrivite pentru rezolvarea unor astfel de probleme teoria cozilor.

Această teorie reprezintă o secțiune specială a teoriei proceselor aleatoare și folosește în principal aparatul teoriei probabilităților. Primele publicații în acest domeniu datează din anii 20. secolul XX și aparțin danezului A. Erlang, care a fost angajat în cercetarea funcționării centralelor telefonice - QS tipic, în care momentele apelului sunt aleatorii, faptul că abonatul sau toate canalele sunt ocupate și durata conversației . Ulterior, teoria cozii a fost dezvoltată în lucrările lui K. Palm, F. Pollachek, A. Ya. Khinchin, B. V. Gnedenko, A. Kofman, R. Kruon, T. Saaty și alți matematicieni interni și străini.

La rezolvarea problemelor legate de cozi, sunt posibile două situații:

a) numărul de comenzi este prea mare; apare timp lung de așteptare (cantitate insuficientă de echipamente de service);

b) se primesc un număr insuficient de comenzi; Are locul de oprire a echipamentului (exces de echipament).

Este necesar să se găsească echilibrul optim între pierderile cauzate de nefuncţionarea echipamentelor şi pierderile datorate aşteptării.

Elementele principale ale QS sunt fluxul de intrare al aplicațiilor, coada pentru service, sistemul de service (mecanismul) și fluxul de ieșire al aplicațiilor. Rolul cererilor (cereri, apeluri) pot fi clienții dintr-un magazin, convorbiri telefonice, trenuri care se apropie de un nod feroviar, vagoane aflate în descărcare, mașini la o stație de service, avioane care așteaptă permisiunea de decolare, un teanc de bușteni la încărcarea pe vehicule. . Rolul dispozitivelor de deservire (canale, linii) este jucat de vânzătorii sau casierii dintr-un magazin, ofițerii vamali, mașinile de pompieri, pistele, examinatorii și echipajele de reparații.

Pe baza naturii procesului aleator care are loc în QS, sistemele se disting între Markov și non-Markov.

Procesul aleatoriu este numit Markovian, dacă pentru orice moment t, caracteristicile probabilistice ale procesului în viitor depind numai de starea lui la momentul dat t și nu depind de când și cum a ajuns sistemul în această stare. Modelele discutate mai jos aparțin sistemelor Markov.

În cazul proceselor non-Markov, problemele studierii sistemelor QS devin semnificativ mai complicate și necesită utilizarea modelării statistice și a metodelor numerice folosind un calculator.

Teoria cozilor

secţiunea teoriei cozilor de aşteptare (vezi Teoria cozilor de aşteptare). O.T. studiază sisteme în care solicitările care găsesc sistemul ocupat nu se pierd, ci așteaptă ca acesta să devină liber și apoi sunt deservite într-o ordine sau alta (adeseori acordând prioritate anumitor categorii de solicitări). Concluzii Otomanii sunt folosiți pentru planificarea rațională a sistemelor de așteptare. Din punct de vedere matematic, problemele O. t. pot fi incluse în teoria proceselor aleatoare (Vezi Procesul aleator), iar răspunsurile sunt adesea exprimate în termeni de transformări Laplace (Vezi transformarea Laplace). caracteristicile cerute. Utilizarea metodelor statistice este necesară chiar și în cele mai simple cazuri pentru o înțelegere corectă a tiparelor statistice care apar în sistemele de așteptare.

Exemplu. Să existe un singur dispozitiv de serviciu care primește un flux aleatoriu de solicitări. Dacă dispozitivul este liber atunci când se primește o solicitare, acesta începe imediat să fie deservit. În caz contrar, este pus în coadă și dispozitivul deservește cererile una după alta, în ordinea în care au fost primite. Lăsa A - numărul mediu de cereri primite în timpul unui serviciu, A T este durata perioadei de ocupare, adică perioada de timp din momentul în care dispozitivul este ocupat de o anumită cerere care găsește dispozitivul liber, până în primul moment în care dispozitivul este eliberat complet. O.T. arată că în ipotezele naturale așteptările matematice T egală m= 1/(1 - a), iar varianța este (1 + A) m 3(deci când a = 0,8 valorile corespunzătoare sunt 5 și 225). Astfel, pentru un dispozitiv de service „bine încărcat” (adică pentru o valoare apropiată de 1), valoarea medie m variabilă aleatorie T este o caracteristică foarte nesigură T.

Lit.: Gnedenko B.V., Kovalenko I.N., Introducere în teoria cozilor, M., 1966; Sisteme de servicii prioritare, M., 1973.

Yu. V. Prohorov.

Marea Enciclopedie Sovietică. - M.: Enciclopedia Sovietică. 1969-1978 .

• Eyebright
• Următoarele sarcini ale guvernului sovietic

Vedeți ce este „Teoria cozilor” în alte dicționare:

TEORIA COZILOR- la matematică, o secțiune a teoriei cozilor de așteptare, în care sunt studiate sisteme în care solicitările care găsesc sistemul ocupat nu se pierd, ci se așteaptă să fie eliberat și apoi sunt deservite într-o ordine sau alta... Dicţionar enciclopedic mare

teoria cozilor- (matematică), o secțiune a teoriei cozilor de așteptare, în care sunt studiate sistemele în care solicitările care găsesc sistemul ocupat nu se pierd, ci se așteaptă ca acesta să fie eliberat și apoi sunt deservite într-o ordine sau alta. * * * TEORIA COZILOR TEORIA COZIILOR, în... ... Dicţionar enciclopedic

TEORIA COZILOR- vezi Teoria cozilor... Big Enciclopedic Polytechnic Dictionary

TEORIA COZILOR- secțiunea teoriei cozilor de așteptare. O.t. studiază sistemele în care solicitările care găsesc sistemul ocupat nu se pierd, ci așteaptă ca acesta să fie eliberat și apoi sunt deservite într-o ordine sau alta (adesea cu prioritate acordată anumitor... ... Enciclopedie matematică

TEORIA COZILOR- (matematică), o secțiune a teoriei cozilor în care sunt studiate sistemele în care solicitările care găsesc sistemul ocupat nu se pierd, ci se așteaptă să fie eliberat și apoi sunt deservite într-o ordine sau alta... Științele naturii. Dicţionar enciclopedic

Teoria cozilor- (teoria cozilor de așteptare) o secțiune a teoriei probabilităților, al cărei scop cercetării este alegerea rațională a structurii sistemului de servicii și a procesului de serviciu bazat pe studiul fluxului de cereri de servicii care intră și ies din sistem ... ... Wikipedia

teoria cozilor- - teoria cozilor O secțiune de cercetare operațională care examinează diferite procese din economie, precum și în comunicațiile telefonice, asistența medicală și altele... ... Ghidul tehnic al traducătorului

Teoria cozilor

Teoria cozilor- o secțiune de cercetare operațională care ia în considerare diverse procese din economie, precum și din comunicațiile telefonice, asistența medicală și alte domenii ca procese de servicii, i.e. satisfacție pentru ceea ce...... Dicționar economic și matematic

Teoria cozilor- vezi Teoria cozilor... Dicționar economic și matematic

Cărți

• Logistica și teoria cozilor de așteptare
• Logistica și teoria cozilor, Ryzhikov Yu.I.. Manualul examinează starea actuală a teoriei logisticii, discută elementele unui model matematic de gestionare a stocurilor și elementele de bază ale metodelor numerice ale teoriei cozilor de așteptare;...

Ministerul Educației și Științei al Federației Ruse

Agenția Federală pentru Educație

Instituția de Învățământ de Stat de Învățământ Profesional Superior „Universitatea Tehnică de Stat Ural - UPI”

Teoria cozilor. Modele de formare a cozilor și metode de estimare a dimensiunii medii a cozii.

După disciplină: Teoria proceselor și sistemelor informaționale

Ekaterinburg, 2007

INTRODUCERE
1. PROBLEMA ERLANG CLASIC
1.1. Scrierea ecuațiilor
1.2. Definiția unei soluții staționare
1.3. Câteva rezultate pregătitoare
1.4. Definirea funcției de distribuție a duratei de așteptare
1.5. Timp mediu de așteptare
2. DECLARAȚIA PROBLEMEI
2.1. Model matematic
2.2. Rezolvarea problemei
2.3. Analiza rezultatelor
BIBLIOGRAFIE

Introducere.

În multe domenii ale activității practice umane, ne confruntăm cu nevoia de a rămâne într-o stare de anticipare. Situații asemănătoare apar la cozi, la casele de bilete, pe aeroporturile mari, când personalul de întreținere a aeronavelor așteaptă permisiunea de decolare sau aterizare, la centralele telefonice în așteptarea liberării liniei unui abonat, în atelierele de reparații, în așteptarea reparațiilor la mașini și echipamente, în depozitele organizațiilor în timp ce aștepta descărcarea sau încărcarea vehiculelor.

În teoria sistemelor de așteptare, obiectul deservit este numit cerinţă. În general, o cerință este de obicei înțeleasă ca o solicitare pentru a satisface o anumită nevoie, de exemplu, o conversație cu un abonat, aterizarea unui avion, cumpărarea unui bilet, primirea materialelor dintr-un depozit.

Instrumentele care servesc cerințelor sunt numite dispozitive de service sau canale de servicii. De exemplu, acestea includ canale de comunicații telefonice, piste de aterizare, reparatori, casierii de bilete, puncte de încărcare și descărcare la baze și depozite.

Sistemele de referință de masă așteptate sunt cele mai utilizate. Aceste sisteme sunt definite în același mod ca și sistemele cu flux de intrare limitat. Ele pot fi împărțite în două grupe:

1) Închis- 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.

2) 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 stații, porturi etc. Pentru aceste sisteme, fluxul de cereri de intrare poate fi considerat nelimitat.

Elementele principale ale QS sunt: ​​fluxul de cerințe de intrare, coada de cerințe, dispozitivele de deservire (canale) și fluxul de ieșire de cerințe.

Acest lucru poate fi descris astfel:

https://pandia.ru/text/78/375/images/image001_340.jpg" width="61" height="19"> Flux de intrare Coadă

Dispozitive de service Flux de ieșire

Studiul QS începe cu analiza fluxului de cerințe de intrare. Fluxul de cerințe de intrare este o colecție de cerințe care intră în sistem și care trebuie deservite. Fluxul de cerințe de intrare este studiat pentru a stabili tiparele acestui flux și pentru a îmbunătăți în continuare calitatea serviciului.

În cele mai multe cazuri, fluxul de intrare este incontrolabil și depinde de o serie de factori aleatori. Numărul de cereri care sosesc pe unitatea de timp este o variabilă aleatorie. O variabilă aleatorie este, de asemenea, intervalul de timp dintre cererile adiacente primite. Cu toate acestea, se presupune că numărul mediu de cereri primite pe unitatea de timp și intervalul de timp mediu dintre cererile adiacente primite sunt date.

Numărul mediu de cereri care intră în sistemul de servicii pe unitatea de timp se numește rata de sosire a cererii și este determinat de următoarea relație:

Unde T- valoarea medie a intervalului dintre sosirea cererilor ulterioare.

Pentru multe procese reale, fluxul de cerințe este destul de bine descris de legea distribuției Poisson. Un astfel de flux se numește cel mai simplu.

Cel mai simplu flux are următoarele proprietăți importante:

1) Proprietate staționaritate, care exprimă invarianța regimului de curgere probabilistică în timp. Aceasta înseamnă că numărul de solicitări care intră în sistem la intervale de timp egale ar trebui, în medie, să fie constant. De exemplu, numărul de mașini care sosesc pentru încărcare în medie pe zi ar trebui să fie același pentru diferite perioade de timp, de exemplu, la începutul și la sfârșitul unui deceniu.

2) Nici un efect secundar, care determină independența reciprocă a primirii unuia sau altuia număr de cereri de serviciu în perioade de timp care nu se suprapun. Aceasta înseamnă că numărul de solicitări care sosesc într-o anumită perioadă de timp nu depinde de numărul de solicitări deservite în perioada anterioară. De exemplu, numărul de vehicule care sosesc pentru materiale în a zecea zi a lunii este independent de numărul de vehicule deservite în a patra sau în orice altă zi anterioară a lunii.

3) Proprietatea banalitate, care exprimă imposibilitatea practică a sosirii simultane a două sau mai multe solicitări (probabilitatea unui astfel de eveniment este nemăsurat de mică în raport cu perioada de timp considerată, când aceasta din urmă tinde spre zero).

Prima lucrare matematică asupra sistemelor de cozi de așteptare a apărut la începutul secolului XX. Acestea au fost strâns legate de problemele practice legate de problemele deservirii liniilor telefonice, determinarea numărului optim de casierie și de vânzători în întreprinderile comerciale și elaborarea unor reguli de calcul a stocurilor în magazine suficiente pentru funcționarea lor neîntreruptă. Printre aceste lucrări, cercetarea savantului danez ocupă un loc deosebit de important.

1. Problema Erlang clasică.

Luați în considerare problema clasică Erlang: m dispozitive identice primesc un flux simplu de solicitări de intensitate l. Dacă în momentul în care sosește cererea există cel puțin un dispozitiv gratuit, acesta începe imediat să fie deservit. Dacă toate dispozitivele sunt ocupate, atunci cererea nou sosită devine la coadă în spatele tuturor acelor solicitări care au ajuns mai devreme și nu au început încă să fie deservite. Dispozitivul eliberat începe imediat să deservească următoarea solicitare, dacă există o coadă. Fiecare cerere este deservită de un singur dispozitiv și fiecare dispozitiv servește cel mult o cerere în orice moment.

Durata serviciului este o variabilă aleatoare cu aceeași distribuție de probabilitate F(x).

In spate X luați timpul (ore, minute etc.).

Se presupune că atunci când X ³ 0

F(x) = 1 - e-mX

Unde m> 0 - constantă.

Erlang a rezolvat această problemă, ținând cont de formularea întrebărilor care au apărut până atunci în domeniul telefoniei.

Selectarea unei distribuții de probabilitate F(x) a descrie activitățile de servicii nu a fost produsă întâmplător. Cert este că în această ipoteză problema admite o soluție simplă care descrie cursul procesului care ne interesează cu o acuratețe satisfăcătoare pentru practică. Vom vedea că distribuția de probabilitate F(x) joacă un rol excepțional în teoria cozilor, care se datorează în mare parte următoarei proprietăți:

Cu o distribuție exponențială a duratei de întreținere, distribuția activității părții rămase a lucrărilor de întreținere nu depinde de cât timp a fost deja derulată.

Într-adevăr, să gras)înseamnă probabilitatea ca un serviciu care a fost deja în desfășurare de ceva timp A, va dura nu mai puțin de t. Presupunând că durata serviciului este distribuită exponențial, f0(t)=e-mt.

f0 (A)= e- mA Șif0 (A+ t)= e- m(A+1) .

Și ca întotdeauna

f0(a+t) = f0(a) fa(t), Acea e-m(a+t)=e-mAf0(t)

prin urmare

fa(t) = e-mt= fo(t).

Cererea a fost dovedită.

Fără îndoială că într-o situație reală, timpul indicativ de serviciu este, de regulă, doar o aproximare grosieră a realității. Astfel, de multe ori timpul de service nu poate fi mai mic de o anumită valoare. Presupunerea distribuției probabilităților F(x) conduce la faptul că o proporție semnificativă de cerințe au nevoie doar de o operațiune pe termen scurt apropiată de 0. Mai târziu ne confruntăm cu sarcina de a ne elibera de constrângerea inutilă impusă de ipoteza distribuției probabilităților. F(x). Necesitatea acestui lucru era deja clară pentru Erlang însuși și, într-o serie de lucrări, a făcut eforturi pentru a găsi alte distribuții de succes pentru durata serviciului. În special, li s-a oferit așa-numitul distribuție Erlang, a cărei densitate de distribuție este dată de formula

Unde, m> 0 și k este un număr întreg pozitiv.

Distribuția Erlang este distribuția sumei k termeni independenți, fiecare dintre acestea având o distribuție de probabilitate F(x)

Să notăm pentru cazul distribuției probabilităților F(x) prin h cere timp de serviciu. Atunci durata medie a serviciului este

Această egalitate ne oferă o modalitate de a estima parametrul m din datele experimentale. După cum se poate calcula cu ușurință, variația duratei serviciului este

1. Întocmirea ecuaţiilor.

Un sistem de așteptare în cazul unui flux simplu și al timpului de serviciu exponențial este un proces aleatoriu Markov.

Să găsim acele ecuații care satisfac probabilitățile Pk(t). Una dintre ecuații este evidentă și anume pentru fiecare t

Să găsim mai întâi probabilitatea ca în acest moment t+h toate dispozitivele sunt gratuite. Acest lucru se poate întâmpla în următoarele moduri:

Pe moment t toate dispozitivele erau gratuite și în timp h nu au fost primite noi cereri;

Pe moment t un dispozitiv a fost ocupat cu deservirea solicitării, toate celelalte dispozitive sunt gratuite; pe parcursul h serviciul cererii a fost finalizat și nu au fost primite noi cereri.

Alte posibilități, precum: două sau trei aparate au fost ocupate și în timpul timpului h lucrarea la ele a fost finalizată - există o posibilitate Oh), cât de ușor este să te convingi de asta.

Probabilitatea primului dintre aceste evenimente este egală cu

probabilitatea celui de-al doilea eveniment

Prin urmare,

De aici, evident, ajungem la ecuație

Să trecem acum la compilarea ecuațiilor pentru Pk(t) la k³ 1. Să luăm în considerare separat două cazuri diferite:

1) Lasă mai întâi 1 £ k< m. Enumerăm doar stările esențiale din care se poate ajunge la stat Ek pe moment t+h. Aceste stări sunt:

Pe moment t Ek, în timpul h nu s-au primit solicitări noi și nici un dispozitiv nu a finalizat întreținerea. Probabilitatea acestui eveniment este

Pe moment t sistemul era într-o stare Ek-1, pe parcursul h a sosit o nouă solicitare, dar niciuna dintre solicitările anterior în așteptare nu a fost finalizată cu serviciul. Probabilitatea acestui eveniment este

Pe moment t sistemul era într-o stare Ek+1, pe parcursul h nu au fost primite cereri noi, dar o cerere a fost rezolvată. Probabilitatea acestui lucru este egală

Toate celelalte posibilități imaginabile de tranziție la stat Ek pe o perioadă de timp h au o probabilitate egală cu 0(h).

Punând împreună probabilitățile găsite, obținem următoarele

egalitate:

Transformările simple ne conduc la următoarea ecuație

pentru 1 k £< m:

2) Raționament similar pentru k ³ m duce la ecuație

Pentru a determina probabilitățile Pk(t) avem un sistem infinit de ecuații diferențiale. Soluția sa prezintă dificultăți tehnice incontestabile.

2. Determinarea unei soluţii staţionare.

În teoria cozilor de așteptare, doar o soluție în stare de echilibru pentru t® ¥ . Existența unor astfel de soluții este stabilită de așa-numitele teoreme ergodice. În problema luată în considerare, se dovedește că există probabilități limitative sau, așa cum se spune de obicei, staționare. Să introducem notația pentru ele Pk. Rețineți că atunci când t® ¥ .

Cele de mai sus ne permit să concluzionam că ecuațiile

pentru probabilitățile staționare iau următoarea formă:

la 1 £ k< m

la k³ m

La aceste ecuații se adaugă o condiție de normalizare

Pentru a rezolva sistemul algebric infinit rezultat, introducem următoarea notație:

la 1 £ k< m

la k³ m

Sistemul de ecuații din aceste notații ia următoarea formă:

z1 = 0, zk - zk+1 = 0 la k³ 1

De aici rezultă că pentru toți k³ 1 zk = 0

adică când 1 £ k< m

kmPk =lPk-1

iar la k³ m

mmPk=lPk-1

Pentru comoditatea notării, să introducem notația

r= l/ m.

Ecuația kmPk =lPk-1 ne permite să concluzionam că atunci când 1 £ k< m

Pentru k ³ m din ecuație mmPk=lPk-1 găsim că

prin urmare, la k³ m

Rămâne de găsit P0. Pentru a face acest lucru, înlocuim expresiile pentru Pk rezultat.

Ca urmare

Astfel, suma infinită între paranteze pătrate poate fi găsită numai dacă

r < m

atunci în această situație găsim egalitatea

Dacă condiția r < m nu este satisfăcută, adică dacă r ³ m, atunci seria din paranteza pătrată a ecuației pentru determinarea P0 diverge și, prin urmare, P0 ar trebui să fie egal cu 0..gif" width="71" height="44 src=">pentru toate k³ 1 se dovedește Pk = 0.

Metodele teoriei lanțului Markov ne permit să concluzionam că pentru r ³ m, în timp, coada tinde spre ¥ în probabilitate.

3. Câteva rezultate pregătitoare.

Pentru o sarcină de așteptare, principala caracteristică a calității serviciului este durata de așteptare necesară pentru a începe serviciul. Durata de așteptare este o variabilă aleatorie, pe care o notăm cu literă g. Să luăm acum în considerare doar problema determinării distribuției probabilității a duratei de așteptare într-un proces de serviciu deja stabilit. Să notăm în continuare prin P{ g > t} probabilitatea ca timpul de așteptare să depășească t, si prin Pk{ g > t} probabilitatea inegalității indicată între paranteze, cu condiția ca la momentul sosirii cererii să fie deja o persoană în coadă k cerințe. În virtutea formulei probabilității totale, avem egalitatea

P{ g > t} = .

Înainte de a transforma această formulă într-o formă convenabilă pentru utilizare, să pregătim câteva de care avem nevoie pentru informații suplimentare.

Să calculăm acum probabilitatea ca toate dispozitivele să fie ocupate la un moment dat. Evident, această probabilitate este egală cu

4. Determinarea funcției de distribuție a duratei de așteptare.

Dacă în momentul primirii cererile erau deja în coadă k - m solicitări, apoi, deoarece serviciul are loc în ordinea priorității, o cerere nou primită trebuie să aștepte până când este deservită

k – m + 1 cerințe.

Lăsa qs(t)înseamnă probabilitatea ca într-o perioadă de timp t dupa ce am primit cererea care ne interesa, serviciul s-a terminat exact S cerințe. Este clar că k³ m exista egalitate

Deoarece distribuția duratelor de servicii se presupune a fi orientativă și independentă nici de câte cereri sunt în coadă și nici de cât de lungi sunt duratele de servicii ale altor solicitări, atunci probabilitatea de a nu finaliza un singur serviciu în timpul t (adică, probabilitatea că niciunul dintre dispozitive nu va fi eliberat) este egal cu

Dacă toate dispozitivele sunt ocupate cu service și există încă o coadă suficientă de cereri care așteaptă să fie deservite, atunci fluxul de solicitări deservite va fi cel mai simplu. Într-adevăr, în acest caz, toate cele trei condiții - staționaritate, absența efectelor secundare și banalitatea - sunt îndeplinite. Probabilitatea de a elibera exact s dispozitive într-o perioadă de timp t este egală (acest lucru poate fi arătat și printr-un calcul simplu)

prin urmare

Dar probabilitățile Pk sunt cunoscute:

Folosind transformări evidente, reducem partea dreaptă a ultimei egalități la formă

Din formule Și rezultă că , deci pentru t>0

.

Este de la sine înțeles că la or<0 .

Funcţie are la punct t = 0 o discontinuitate egală cu probabilitatea de a găsi toate dispozitivele ocupate.

5. Timp mediu de așteptare.

Formula ne permite să găsim toate caracteristicile numerice ale duratei de așteptare care ne interesează. În special, așteptarea matematică a timpului de așteptare pentru începerea serviciului sau, după cum preferă să spună, timpul mediu de așteptare este egală cu

Calculele simple duc la formula

Varianta lui g este egală cu

.

Formula oferă timpul mediu de așteptare pentru o cerere. Să găsim pierderea medie de timp prin cererile care ajung la sistemul de service într-o perioadă de timp T. Pe parcursul T intră în sistem lT cerințe în medie; pierderea lor totală de timp de așteptare este în medie egală cu

Să prezentăm câteva mici calcule aritmetice care ne vor arăta cât de repede crește pierderea totală de timp în așteptare odată cu modificarea valorii lui . În acest caz, ne limităm la cazul T = 1 și luăm în considerare doar cele mai mici valori ale lui m: t = 1 și m = 2.

La t=1 datorită (20)

La R= 0,1; 0,3; 0,5; Valoarea 0,9 este de aproximativ 0,011; 0,267; 0,500; 1,633; 8.100.

La m= 2 din cauza (24)

La = 0,1; 1,0; 1,5; valoarea 1,9 este de aproximativ 00003; 0,333; 1.350; 17.537.

Datele prezentate ilustrează faptul binecunoscut al sensibilității relativ ridicate a sistemelor de service, deja destul de puternic încărcate, la creșterea sarcinii. Consumatorul simte imediat o creștere semnificativă a timpului de așteptare. Acest fapt trebuie luat în considerare la calcularea sarcinii echipamentului în sistemele de așteptare.

Formularea problemei.

La stația de service (STS) pentru autoturisme există 7 locuri de muncă de service clienți. Potrivit statisticilor, pe oră se primesc 2 solicitări de service autoturisme. Timpul mediu pentru întreținerea unei aplicații este de 3 ore și 24 de minute.

Dacă un client care sosește găsește tot personalul care lucrează ocupat la stația de service, atunci se pune la coadă și așteaptă până când un loc de muncă devine liber.

Fiecare maestru, la un moment dat, nu poate servi mai mult de un client. Clientul deservit părăsește stația de service.

Analizați structura și procesul de întreținere a stațiilor de service. Acest lucru necesită dezvoltarea indicatorilor de performanță pentru sistemele de așteptare. De exemplu, trebuie să știți: probabilitatea ca k dispozitive să fie ocupate sau libere; distribuția probabilităților de dispozitive libere sau ocupate de la serviciu; probabilitatea ca un anumit număr de cereri să fie în coadă; probabilitatea ca timpul de așteptare în coadă să depășească unul specificat. Indicatorii care caracterizează funcționarea eficientă a sistemului în medie includ: lungimea medie a cozii; numărul mediu de dispozitive ocupate; factor de încărcare a sistemului.

1. Model matematic.

Avem un sistem de așteptare format din n = 7 dispozitive identice, care primește un flux de cereri α = 2, intensitate β = 0,29411(1/h).

Cu cel mai simplu flux de cereri, distribuția cererilor care intră în sistem respectă legea distribuției Poisson:

probabilitatea DIV_ADBLOCK171">

unde https://pandia.ru/text/78/375/images/image057_47.gif" width="231 height=25" height="25">

unde https://pandia.ru/text/78/375/images/image059_45.gif" width="15 height=28" height="28">.gif" width="716 height=299" height="299 „>

Fig.1. Cerință în sistem.

Lăsa Dt– o perioadă de timp destul de scurtă. Probabilitatea ca în QS în timp Dt nu va fi primită o singură cerere:

Probabilitatea ca QS să primească o cerere în timpul Dt:

Probabilitatea ca în timpul Dt QS să primească două sau mai multe solicitări:

Probabilitatea ca cererea să fie deservită în timpul Dt:

Probabilitatea ca două sau mai multe cereri să fie servite în timpul Dt:

Probabilitatea ca în timpul Dt să fie deservită una dintre k cerințele din sistem se găsește după cum urmează:

https://pandia.ru/text/78/375/images/image069_37.gif" width="381 height=48" height="48">;