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.

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

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

Il processo è stabile solo se ${\displaystyle \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 ${\displaystyle \rho ={\frac {\lambda }{\mu }}}$, la condizione diventa ${\displaystyle \rho <1}$. Imponendo questa condizione, si ha che

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

${\displaystyle \pi _{i}=(1-\rho )\rho ^{i}.}$

• La probabilità di avere ${\displaystyle n}$ o più utenti nel processo è data da ${\displaystyle \rho ^{n}}$
• Il numero medio di utenti nel sistema è

${\displaystyle 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:

${\displaystyle W_{s}={\frac {L_{s}}{\lambda }}={\frac {1}{\mu -\lambda }}}$

• Il numero medio di utenti in coda è

${\displaystyle L_{q}=\sum _{k=1}^{\infty }{(k-1)\pi _{i}}={\frac {\rho ^{2}}{1-\rho }}}$

• Il tempo medio passato da un utente in coda è

${\displaystyle W_{q}={\frac {L_{q}}{\lambda }}=W_{s}-{\frac {1}{\mu }}={\frac {\rho }{\mu -\lambda }}}$

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

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

Portale Ingegneria

Portale Matematica

Portale Telematica