Coda M/M/1

Da Wikipedia, l'enciclopedia libera.

In teoria delle code, una coda M/M/1 rappresenta la lunghezza di una coda in un sistema composto da un singolo server, in cui gli arrivi sono determinati da un processo di Poisson e i tempi servizio hanno distribuzione esponenziale. Il nome è dovuto alla Notazione di Kendall.

Definizione[modifica | modifica wikitesto]

Un coda M/M/1 è un processo stocastico definito sui numeri naturali, dove il valore ad un tempo fissato corrisponde al numero di utenti nel sistema, inclusi quelli che stanno ricevendo il servizio.

  • Gli arrivi sono determinati da un processo di Poisson di intensità λ, e spostano il processo da uno stato i a quello successivo i+1
  • I tempi di servizio hanno distribuzione esponenziale di parametro μ
  • Il server non può essere occupato da più utenti nello stesso momento. Quando il servizio finisce, l'utente lascia la coda e il processo si sposta dallo stato i al precedente i-1
  • Non c'è nessun limite al numero di utenti che può contenere il sistema.

Il processo può essere descritto come una catena di Markov a tempo continuo, in particolare da un processo di nascita e morte con generatore

Q=\begin{pmatrix}
-\lambda & \lambda \\
\mu & -(\mu+\lambda) & \lambda \\
&\mu & -(\mu+\lambda) & \lambda \\
&&\mu & -(\mu+\lambda) & \lambda &\\
&&&&\ddots
\end{pmatrix}

Proprietà[modifica | modifica wikitesto]

Il processo è stabile solo se λ<μ. Se in media vi sono più arrivi di quanti il sistema può servirne, la coda crescerà indefinitivamente e non ci sarà equilibrio. Se chiamiamo ρ=λ/μ, la condizione diventa ρ<1. Imponendo questa condizione, si ha che

\pi_i=(1-\rho)\rho^i.
  • La probabilità di avere n o più utenti nel processo è data da \rho^n
  • Il numero medio di utenti nel sistema è
L_s=\sum_{k=0}^{\infty}{k\pi_i} = \frac{\rho}{1-\rho}
  • Il tempo medio passato da un utente nel sistema è ottenibile utilizzando la legge di Little:
W_s=\frac{L_s}{\lambda}=\frac{1}{\mu - \lambda}
  • Il numero medio di utenti in coda è
L_q=\sum_{k=1}^{\infty}{(k-1)\pi_i}=\frac{\rho^2}{1-\rho}
  • Il tempo medio passato da un utente in coda è
W_q=\frac{L_q}{\lambda}=W_s-\frac{1}{\mu}=\frac{\rho}{\mu - \lambda}

Voci correlate[modifica | modifica wikitesto]

Bibliografia[modifica | modifica wikitesto]

Kleinrock Leonard, Queueing Systems Volume 1: Theory, John Wiley & Sons, 1975.