Coda M/M/1

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

Una coda M/M/1 è un processo stocastico a valori nei 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=\left(\begin{array}{cc}-\lambda & \lambda \\ \mu & -(\mu +\lambda )& \lambda \\ & \mu & -(\mu +\lambda )& \lambda \\ & & \mu & -(\mu +\lambda )& \lambda & \\ & & & & \ddots \end{array}\right)$

Proprietà

Il processo è stabile solo se $\lambda <\mu$. Se in media vi sono più arrivi di quanti il sistema può servirne, la coda crescerà indefinitivamente e non ci sarà equilibrio. Se chiamiamo $\rho =\frac{\lambda }{\mu }$, la condizione diventa $\rho <1$. Imponendo questa condizione, si ha che

• La distribuzione stazionaria del processo è geometrica di parametro $\rho$

${\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}^{\mathrm{\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}^{\mathrm{\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 }$

Bibliografia

• Template:Cita libro

Voci correlate

• Processo di nascita e morte
• Processo markoviano
• Legge di Little
• Coda M/M/c