Coda M/M/c

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

Definizione

Un coda M/M/c è 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 tutti distribuzione esponenziale di parametro μ
• I server non possono essere occupati 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 ci possono essere server fermi se sono presenti utenti in coda
• 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 di parametri:

$\lambda _{k}=\lambda ,\ \forall k$

$\mu _{k}={\begin{cases}k\mu ,&{\mbox{se }}0\leq k\leq c\\c\mu ,&{\mbox{se }}c\leq k\end{cases}}$

Proprietà

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

• La distribuzione stazionaria del processo è data da

$\pi _{0}=\left[\sum _{k=0}^{c-1}{\frac {(c\rho )^{k}}{k!}}+{\frac {(c\rho )^{c}}{c!}}{\frac {1}{1-\rho }}\right]^{-1}$

$\pi _{k}={\begin{cases}\pi _{0}{\dfrac {(c\rho )^{k}}{k!}},&{\mbox{se }}0\leq k\leq c\\[10pt]\pi _{0}{\dfrac {\rho ^{k}c^{c}}{c!}},&{\mbox{se }}c\leq k\end{cases}}$

• La probabilità di non trovare nessun server libero è data da

$\mathbb {P} (K\geq c)=\pi _{c_{+}}=\sum _{k=c}^{\infty }\pi _{k}={\frac {(c\rho )^{c}}{c!(1-\rho )}}\pi _{0}$

• Il numero medio di utenti nel sistema è

$L_{s}=c\rho +{\frac {\rho }{1-\rho }}\pi _{c_{+}}$

• Il numero medio di utenti in coda è

$L_{q}={\frac {\rho }{1-\rho }}\pi _{c_{+}}$

• Il tempo medio passato da un utente in coda è

$W_{q}={\frac {\rho }{\lambda (1-\rho )}}\pi _{c_{+}}$

• Il tempo medio passato da un utente nel sistema è

$W_{s}={\frac {\rho }{\lambda (1-\rho )}}\pi _{c_{+}}+{\frac {1}{\mu }}$

Infiniti server

È possibile anche studiare il caso a infiniti server, ovvero la coda M/M/∞. In questo modello ogni utente viene servito appena entra nel sistema, e non vi è quindi alcuna coda. In questo caso il processo di nascita e morte adatto è quello con parametri

$\lambda _{k}=\lambda ,\ \forall k$

$\mu _{k}=k\mu ,\ \forall k$

• La distribuzione stazionaria è una distribuzione di Poisson di parametro λ/μ:

$\pi _{k}={\frac {(\lambda /\mu )^{k}e^{-\lambda /\mu }}{k!}}$

• Il tempo medio passato nella coda è solamente il tempo medio di servizio:

$W_{s}={\frac {1}{\mu }}$

• Il numero medio di utenti nel sistema è

$L_{s}={\frac {\lambda }{\mu }}$

Bibliografia

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

Voci correlate

• Processo di nascita e morte
• Processo markoviano
• Legge di Little