Analisi di una coda
L'analisi di una fila d'attesa studia il funzionamento e le prestazioni del sistema.
Lo scopo dell'analisi di una fila d'attesa (coda) è determinare la probabilità Pn(t) dei vari stati nel tempo.
Il calcolo è abbastanza semplice se la coda si trova in condizioni di stazionarità. Viceversa, è molto complesso.
Pertanto, è molto utile determinare le condizioni di stazionarietà del sistema.
Una volta trovate le probabilità Pn(t), posso calcolare il valore atteso N del numero di clienti nel sistema.
$$ N=E(n)= \sum_{n=1}^{∞} nP_n $$
il valore atteso del numero dei clienti in coda
$$ L=E(l)= \sum_{n=1}^{∞} (n-s)P_n $$
Nota. Il numero dei clienti n comprende sia i clienti in coda e sia quelli che stanno usufruendo del servizio. Pertanto, per trovare i soli clienti in coda è sufficiente togliere da n il numero dei serventi s.
E' utile calcolare anche il valore atteso del tempo trascorso nel sistema W e in coda Wq.
$$ W = E(t_w) = \int_0^{∞} t \cdot f_{tw}(t) dt $$
$$ W_q = E(t_q) = \int_0^{∞} t \cdot f_{tq}(t) dt $$
Nota. ftw e ftq sono le funzioni di densità della probabilità del tempo trascorso nel sistema W e in coda.
Le variabili del sistema a coda
Le principali grandezze di un sistema a coda sono
- ak istante di arrivo del k-esimo cliente
- pk istante di partenza del k-esimo cliente
- oc,k tempo di attesa in coda del k-esimo cliente
- os,k tempo di serviio del k-esimo cliente
- ok tempo di permanenza nel sistema del k-esimo cliente
- oa tempo tra due clienti successivi
- x(t) numero di clienti nel sistema nell'istante t
- xc(t) numero di clienti in coda nell'istante t
Nota. Vale la seguente relazione $$ o_k=o_{c,k}+o_{s,k}=p_k-a_k $$
La variabile x(t) è la variabile di stato del sistema.
Il numero di clienti nel sistema x(t) è uguale alla differenza tra il numero totale di arrivi e di partenze dall'istante iniziale t0 fino all'istante t.
La distribuzione di stato nell'istante successivo al k-esimo evento di partenza di un cliente è
$$ π_j+ = \lim_{k \rightarrow ∞} P\{ x(p_k+)=j \} $$
La distribuzione di stato nell'istante precedente al k-esimo evento di arrivo di un cliente è
$$ π_j- = \lim_{k \rightarrow ∞} P\{ x(a_k-)=j \} $$
Le condizioni di stazionarietà
Un sistema a coda è stabile se le distribuzioni di stato sono stazionarie $$ π_j =\lim_{t \rightarrow ∞} P \{ x(t)=j \} $$ e soddisfano la proprietà $$ \sum_{j=0}^{∞} π_j = 1 $$
In tale circostanza le distribuzioni sono uguali
$$ π_j+ = π_j- $$
per ogni j
Esempio
In un sistema arriva un cliente ogni 4 minuti e il tempo di servizio è di 3 minuti.
In questo caso, il cliente che arriva trova sempre la coda vuota, usufruisce del servizio e se ne va un minuto prima che arrivi il successivo cliente.
In ogni istante t lo stato del sistema può essere x(t)=1 oppure x(t)=0.
Pertanto, il sistema non è stazionario e non è stabile.
Le relazioni fondamentali
Il numero medio dei clienti N nel sistema è uguale al numero medio degli arrivi (λ) per il tempo speso nel sistema da un cliente W.
$$ N=λ \cdot W $$
Nota. Se le ipotesi di ergodicidità non sono soddisfatte, la relazione non è indipendente dal tempo e va scritta in quest'altra forma. $$ N(t)=λ(t) \cdot W(t) $$
La lunghezza della coda è determinata dal numero medio di arrivi nel sistema (λ) per il tempo di attesa in coda Wq.
$$ L=λ \cdot Wq $$
Il numero medio del tempo trascorso nel sistema da un cliente (W) è uguale al tempo di attesa in coda (Wq)
$$ W=W_q+\frac{1}{μ} $$
L'intensità di traffico
L'intensità di traffico ( o coefficiente di carico δ ) si ottiene con il rapporto tra il tasso medio di arrivo dei clienti (λ) e il tasso medio di servizio (μ).
$$ δ = \frac{λ}{μ} $$
Se lo spazio di accodamento è illimitato, la coda è stabile se l'intensità di traffico (δ) è compresa tra 0 e 1.
$$ 0 \le δ \le 1 $$
perché garantisce l'ergodicità del sistema.
La variabile δ misura anche la percentuale di tempo in cui il servitore non è inattivo.
Pertanto, misura il grado di utilizzazione delle risorse (v) ossia la percentuale di tempo in cui il servitore è occupato.
$$ v = δ = 1 - π_0 $$
Dove π0 è la probabilità che sia vuota la coda in condizioni stazionarie.
La produttività del servitore
La produttività del servitore è determinata dalla seguente formula
$$ η= μ(1-π_0) $$
che indica il tasso di uscita dei clienti servizi in condizioni di equilibrio.
Se il sistema è in equilibrio, il tasso di uscita deve eguagliare il tasso di arrivo dei clienti (l).
$$ λ = η $$
Nota. Questa condizione di equilibrio spiega la formula dell'intensità di carico $$ v = δ = 1-π_0 $$ Infatti, con λ=η si ottiene $$ δ= \frac{λ}{μ} $$ $$ g= \frac{μ(1-π_0)}{μ} = (1-π_0) $$
Se i servitori sono più di uno (m) le formule della produttività diventano
$$ η= m \cdot μ(1-π_0) $$
$$ δ = \frac{λ}{μ \cdot m} $$
L'equazione di Lindley
L'equazione di Lindley determina l'istante di tempo dk in cui il k-esimo cliente lascia il sistema dopo essere stato servito. $$ d_k = \max \{ a_k, d_{k-1} \} + o_{s,k} $$
Dove ak è l'istante di arrivo del k-esimo cliente, dk-1 è l'istante in cui il cliente che precedede (k-1) lascia il sistema e os,k è il tempo di erogazione del servizio.
Nota. Se il servitore è subito libero, l'equazione prende come istante a_k. Viceversa, se c'è già una coda allora prende dk-1 (il precedessore k-1-esimo cliente lascia il sistema) perché è sicuramente superiore ad ak.
Analisi a regime
Posso condurre l'analisi di una coda in due ambiti
- nella fase transitoria, quando il sistema cerca di raggiungere uno stato di equilibrio
- nella fase a regime, nel lungo periodo, per sapere se il sistema ha raggiunto l'equilibrio oppure no.
Generalmente, quando si parla di analisi di una coda si intende "a regime".
La legge di Little
In condizioni di equilibrio stocastico, il numero medio dei clienti (xm), il tasso medio di arrivo dei clienti (λ) e il tempo medio di permanenza dei clienti (v) sono collegati dalla seguente relazione $$ x_m =λ \cdot v $$
Dove
$$ x_m=E[x(t)]\\ λ=E[A(t)] \\ v=E[v_k] $$
E' abbastanza evidente che il numero medio dei clienti nel sistema si riduce abbassando il tempo medio di permanenza dei clienti (v) nel servizio o riducendo il tasso medio di arrivo (λ).
Questa relazione è applicabile a qualsiasi sistema a coda, indipendentemente dalle caratteristiche del sistema.
Esempio
In una banca entrano 12 clienti ogni ora (λ=12) e ci sono in media 6 clienti in ogni istante (xm=6).
Usando la legge di Little posso trovare il tempo di permanenza.
$$ v = \frac{x_m}{λ} = 6 / 12 = 0.30 ore
In media ogni cliente permane mezz'ora nella banca, dal momento in cui entra a quello in cui esce.
E così via.
