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

1. un servente con tasso di servizio m=1.5 clienti/minuto al costo di 300 euro
2. 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.