Coda M/M/c

Da Wikipedia, l'enciclopedia libera.

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[modifica | modifica wikitesto]

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 \le k \le c \\
  c\mu, & \mbox{se } c \le k 
\end{cases}


Proprietà[modifica | modifica wikitesto]

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

\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 \le k \le c \\[10pt]
  \pi_0\dfrac{\rho^k c^c}{c!}, & \mbox{se } c \le k 
\end{cases}
  • La probabilità di non trovare nessun server libero è data da
\mathbb P(K \ge c) = \pi_{c_+} = \sum^\infty_{k=c} \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[modifica | modifica wikitesto]

È 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
 \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}

Voci correlate[modifica | modifica wikitesto]

Bibliografia[modifica | modifica wikitesto]

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