Coda M/M/1/K
La coda M/M/1/K è una coda con un servente e uno spazio di accomodamento limitato a K-1 utenti.
La coda non può contenere più di K-1 clienti.
Pertanto, lo stato del sistema ( numero clienti ) è limitato a un numero massimo.
In questo caso il tasso di nascita è influenzato dallo stato del sistema.
$$ 0 < j \le K $$
Quindi, il processo degli arrivi ( tasso di nascita ) è
- λj=λ per j<K ( come una coda M/M/1 )
- λj=0 per j≥K ( coda piena )
Il processo delle uscite ( servizio ) è
$$ μ $$
L'intensità del traffico è
$$ δ = \frac{λ}{μ} $$
Una coda con spazio di accodamento limitato è sempre stabile.
Pertanto, non occorre applicare la condizione di stabilità δ <1 delle code M/M/1 con spazio di accodamento illimitato.
Le probabilità di stato a regime sono
$$ π_0 = \frac{1-δ}{1-δ^{K+1}} $$
$$ π_j = δ^j \cdot π_0 $$
A parte il caso particolare δ=1, la probabilità di stato per δ≠1 può essere semplificata in
$$ π_j = \frac{1}{K+1} $$
La probabilità πk è detta probabilità di blocco. E' la probabilità che il sistema e la coda siano pieni. $$ π_k = δ^j \cdot π_0 = δ^j \cdot \frac{1-δ}{1-δ^{K+1}} = \frac{δ^k(1-δ)}{1-δ^{k+1}} $$ dove δ=1/μ $$ π_k = \frac{(1/μ)^k(1-1/μ)}{1-(1/μ)^{k+1}} $$ La probabilità di blocco cresce con il rapporto λ/μ. Inoltre, non è limitata da λ/μ<1 (stabilità coda illimitata) perché nel caso di una coda limitata a K posti gli eventuali clienti in eccesso sono respinti. Il sistema è comunque stabile anche per λ/μ>1.
Come già detto, lo stato del sistema (j) influenza il tasso di arrivo λ effettivo ( λin ).
Per conoscere il numero di clienti che riescono ad accedere al sistema si può usare questa formula.
$$ λ_{in} = \sum_j^∞ λ_j \cdot π_j = λ(1-π_K) $$
Nota. Il tasso λin è sicuramente inferiore a λ perché una parte dei clienti in arrivo sono respinti quando la coda è piena. $$ λ_{rif} = λ -λ_{in} $$
La produttività del sistema è invece pari al tasso di uscita.
$$ η = μ(1-π_0) = λ \cdot \frac{1-δ^K}{1-δ^{K+1}} $$
Il tasso di utilizzo della risorsa è
$$ u = δ \frac{1-δ^k}{1-δ^{k+1}} $$
Il numero medio dei clienti nel sistema è
$$ x = \frac{δ(1-δ^k(k+1) + k \cdot δ^{k+1})}{(1-δ^{k+1})(1-δ)} $$
Il tempo medio di attraversamento è
$$ o = \frac{1-δ^k(k+1)+k \cdot δ^{k+1}}{μ(1-δ^k)(1-δ)} $$
Un esempio pratico
In una coda M/M/1/K devo fare in modo che la percentuale dei clienti rifiutati non superi il 5% degli arrivi.
Devo fare in modo che la probabilità di blocco sia inferiore al 5%
$$ π_k = \frac{(1/μ)^k(1-1/μ)}{1-(1/μ)^{k+1}} < 0.05 $$
Contemporaneamente, devo minimizzare i costi dello spazio di accodamento.
Ogni posizione nella coda costa 60 euro.
Ho due soluzioni tra cui scegliere
- un servente con tasso di servizio m=1.5 clienti/minuto al costo di 300 euro
- un servente con tasso di servizio m=2 clienti/minuto al costo di 400 euro
A questo punto determino lo spazio di accodamento (k) delle due ipotesi
Ipotesi 1
Nel primo caso
$$ \frac{(1/1.5)^k(1-1/1.5)}{1-(1/1.5)^{k+1}} < 0.05 $$
$$ \frac{( \frac{1}{\frac{3}{2}} )^k(1- \frac{1}{\frac{3}{2}} )}{1-( \frac{1}{\frac{3}{2}} )^{k+1}} < 0.05 $$
$$ \frac{( \frac{2}{3} )^k(1- \frac{2}{3} )}{1-( \frac{2}{3} )^{k+1}} < 0.05 $$
$$ \frac{( \frac{2^k}{3^k} ) \cdot (\frac{1}{3} )}{1-( \frac{2}{3} )^{k+1}} < 0.05 $$
$$ \frac{ \frac{2^k}{3^{k+1}} }{ \frac{3^{k+1} - 2^{k+1}}{3^{k+1}} } < 0.05 $$
$$ \frac{2^k}{3^{k+1}} \cdot \frac{3^{k+1}}{3^{k+1} - 2^{k+1}} < 0.05 $$
$$ \frac{2^k}{3^{k+1} - 2^{k+1}} < 0.05 $$
La disequazione è soddisfatta per k=5
k | π_k |
---|---|
0 | 1.0 |
1 | 0.4 |
2 | 0.21 |
3 | 0.12 |
4 | 0.07 |
5 | 0.04 |
La probabilità di blocco è
$$ π_5 = 0.04 $$
Il costo complessivo è
$$ C = 300 + k \cdot 60 = 300 + 5 \cdot 60 = 300 + 300 = 600 € $$
Ipotesi 2
Nel secondo caso
$$ \frac{(\frac{1}{2})^k(1-\frac{1}{2})}{1-(\frac{1}{2})^{k+1}} < 0.05 $$
$$ \frac{(\frac{1^k}{2^k}) \cdot (\frac{1}{2})}{1-\frac{1^{k+1}}{2^{k+1}}} < 0.05 $$
$$ \frac{(\frac{1}{2^{k+1}}) }{\frac{2^{k+1}-1^{k+1}}{2^{k+1}}} < 0.05 $$
$$ \frac{1}{2^{k+1}} \cdot \frac{2^{k+1}}{2^{k+1}-1^{k+1}} < 0.05 $$
$$ \frac{1}{2^{k+1}-1^{k+1}} < 0.05 $$
$$ \frac{1}{2^{k+1}-1} < 0.05 $$
La disequazione è soddisfatta per k=4
k | π_k |
---|---|
1 | 0.33 |
2 | 0.14 |
3 | 0.06 |
4 | 0.03 |
La probabilità di blocco è
$$ π_4 = 0.03 $$
Il costo complessivo è
$$ C = 300 + k \cdot 60 = 400 + 4 \cdot 60 = 400 + 240 = 640 € $$
In conclusione, la prima ipotesi costa di meno ma la seconda ha una probabilità di blocco inferiore.
Pertanto, la scelta dipende dagli obiettivi strategici che ci si pone.
E così via.