Model M/M/1

De Viquipèdia
Dreceres ràpides: navegació, cerca

El M/M/1 és un model en teoria de cues que considera un únic servidor i població infinita. Pot ser utilitzar per a aproximar sistemes senzills.

M/M/1 schema

Seguint la notació de Kendall, indica un sistema on:

  • les arribades són un procés de Poisson;
  • el temps del servei segueix la distribució exponencial;
  • només hi ha un únic servidor;
  • la llargada de la cua en la qual esperen els usuaris que arriben és infinita;
  • la població d'usuaris disponibles per unir-se al sistema és infinita.

Anàlisi[modifica | modifica el codi]

Un sistema així es pot modelar com un procés de naixements-morts, on cada estat representa el nombre d'usuaris al sistema. Com que el sistema té una cua infinita i població il·limitada, el nombre d'estats que el sistema pot ocupar és infinit: són l'estat 0 (no hi ha cap usuari al sistema), l'estat 1 (hi ha un usuari), l'estat 2 (hi ha dos usuaris), etc. Ja que la cua mai s'emplenarà i la població és infinita, la taxa de natalitat (taxa d'arribades), λ, és constant per a cada estat. La taxa de mortalitat (taxa de servei), μ, també és constant per a tots els estats (excepte l'estat 0). De fet, independentment de l'estat, podem només podem trobar dos esdeveniments:

  • Arriba un nou usuari. Així, si el sistema està a l'estat k, passa a l'estat k + 1 amb taxa λ.
  • Un usuari abandona el sistema. Així, si el sistema està a l'estat k, passa a l'estat k − 1 (o k si k és 0) amb taxa μ.

Ara és fàcil veure que el sistema només és estable si λ < μ. De fet, si la taxa de mortalitat és inferior a la taxa de naixements, el terme mig d'usuaris a la cua creixerà a l'infinit, és a dir, el sistema no estarà equilibrat.

Aquest model pot revelar mesures de rendiment interessants sobre el sistema observat; per exemple:

  • El temps mig que un usuari passa al sistema
  • El temps mig que un usuari passa esperant a la cua
  • El nombre esperat d'usuaris al sistema
  • El nombre esperat d'usuaris a la cua
  • El rendiment (nombre d'usuaris servits per unitat de temps).

Solucions estacionàries[modifica | modifica el codi]

Podem definir \scriptstyle \rho\,=\,\tfrac{\lambda}{\mu}.

La probabilitat que el sistema estigui en l'estat i es pot calcular de la següent manera:

\mbox{Prob}(q=i)=\pi_i=(1-\rho)\rho^i.\,

Amb aquesta informació, ens és possible trobar diverses mesures de rendiment. Per exemple:

  • El nombre esperat d'usuaris en el sistema, N:
\overline N=\frac{\rho}{1-\rho}, i la seva variància:
\sigma^2_N = \frac{\rho}{(1 - \rho)^2}
  • El nombre esperat de peticions fetes al servidor:
\overline N_S = \lambda \overline x = \rho
  • El nombre esperat de peticions a la cua:
\overline N_Q = \frac{\rho^2}{1 - \rho}
  • El temps d'espera total (considerant el temps a la cua i la durada del servei):
T=\frac{1}{\mu-\lambda}.
  • El temps esperat que una petició romangui a la cua:
W = \frac{\overline N_Q}{\lambda} = T - \overline x = T - \frac{1}{\mu} = \frac{\rho}{\mu - \lambda}

Exemple[modifica | modifica el codi]

Hi ha moltes situacions on es pot fer ús del model M/M/1. Per exemple, podem imaginar una oficina de correus amb un sol empleat i, per tant, una sola cua. La clientela arriba, s'uneix a la cua, és servida i abandona el sistema. Si les arribades són un procés de Poisson i el temps de servei és exponencial, és possible utilitzar un model M/M/1, podent així calcular fàcilment el nombre esperat de persones a la cua, les probabilitats que hagin d'esperar durant un temps determinat, etc.