7. Teoria delle Code
Una coda è costituita da 3 componenti fondamentali:
• i serventi
• i clienti
• uno spazio in cui i clienti attendono di essere
serviti (coda di attesa).
serv. 1
clienti in
arrivo
coda di
attesa
serv. 2
clienti in
uscita
serv. m
1
Esempi: sistemi di comunicazione, di trasporto,
sistemi informatici, ecc.
Funzionamento
• Un cliente (o utente) entra nella risorsa.
• Se vi sono serventi liberi, entra in un sistema di
servizio, altrimenti si mette in coda.
• Non appena un servente si libera, se vi sono clienti in
coda, uno di essi viene scelto ed entra nel
sistema di servizio.
2
Le caratteristiche peculiari di un sistema a coda
sono le seguenti:
• Modalità degli arrivi.
L’intervallo di tempo tra due arrivi
consecutivi è detto tempo di inter-arrivo.
Questo può essere
deterministico
stocastico
con distribuzione
esponenziale o meno
3
• Modalità di servizio.
Il tempo per servire un utente viene detto
tempo di servizio.
Questo può essere
deterministico
stocastico
con distribuzione
esponenziale o meno
4
N.B.
Un sistema a coda è detto markoviano quando il
tempo di inter-arrivo e il tempo di servizio hanno
una distribuzione esponenziale.
Equivalentemente, possiamo dire che il sistema è
markoviano se e solo se il processo degli arrivi e il
processo dei servizi sono Poissoniani.
In generale questo non è vero.
5
• Numero di serventi (m).
Può essere:
- m = 1 : servente singolo,
- m > 1 : servente multiplo,
- m =  : infiniti serventi.
Si noti che in ogni caso, ogni servente può
servire un solo utente alla volta.
6
• Capacità della coda.
Indica il numero massimo di utenti che
possono stare nella coda d’attesa. Può
essere:
- K  N+ : capacità finita,
- K =  : capacità infinita.
Si noti che nel caso in cui la coda abbia una
capacità finita, se un utente arriva quando
la coda è piena, tale utente viene respinto.
7
• Dimensione della popolazione.
Indica il numero di potenziali clienti.
Si assume quasi sempre che tale
numero sia pari ad .
• Disciplina di coda (o politica di servizio).
Indica la politica con cui gli utenti in coda
vengono ammessi al sistema di servizio. Ad es.,
• FIFO (first in-first out)
• LIFO (last in - first out)
• SIRO (service in random order)
• GD (general discipline, tutti gli altri casi).
8
Notazione di Kendall: descrive una coda in una
risorsa come una stringa di 6 campi:
A/B/m/K/N/
dove:
• A indica la modalità degli arrivi: A  {D,M,G}
(D: arrivi deterministici, M: tempi di interarrivo con distribuzione esponenziale -->
processo markoviano, G : tempi di interarrivo con distribuzione qualunque).
• B indica la modalità di servizio : B  {D,M,G}
• m indica il numero dei serventi: m  N+  {+}
9
• K indica la capacità della coda d’attesa :
K  N+  {+}
• N indica la dimensione della popolazione :
N  N+  {+}
•  indica la disciplina della coda :   { FIFO,
LIFO, SIRO, GD}.
N.B. Solitamente gli ultimi 3 campi si omettono
nel caso in cui sia K = N =  e  = FIFO.
10
Grandezze caratteristiche:
• x(t)  N : numero di utenti nella risorsa
all’istante di tempo t.
• i(t)  [0,1] : probabilità che il numero di utenti
nella risorsa sia i all’istante t.
• x(t)  R0+ : numero atteso di utenti nella risorsa
all’istante t:

x (t)   i  Πi (t)
i0
• (z,t) : funzione generatrice di probabilità
associata a i(t):

Π(z, t)   Πi (t)  z i
i 0
11
• xc(t)  N : numero di utenti in coda all’istante t.
se x(t)  m
x c (t)  0

x c (t)  x(t)  m se x(t)  m
x c (t)  K
• i(t)  [0,1] : probabilità di avere i utenti in
coda all’istante t.
• xc(t)  R0+ : numero atteso di utenti in coda
all’istante t:

ˆ (t)
xc (t)   i  Π
i
i0
• (z,t) : funzione generatrice di probabilità
associata a i(t):

ˆ
ˆ (t)  z i
Π(z, t)   Π
i
i 0
12
• (t)  R0+ : tasso di arrivo, ossia numero medio
di arrivi nell’unità di tempo all’istante t.
Chiaramente 1/(t) rappresenta il tempo
medio di inter-arrivo all’istante t.
• (t)  R0+ : tasso di servizio, ossia numero medio
di servizi nell’unità di tempo all’istante t.
Chiaramente 1/(t) rappresenta il tempo
medio di servizio all’istante t.
• (t) = (t)/m(t) : intensità di traffico all’istante t.
• c(t) : tempo medio speso in coda all’istante t.
• (t) : tempo medio speso nella risorsa all’istante t.
13
Legge di Little
Se un sistema a coda è ergodico , in condizioni
di regime valgono le seguenti relazioni:
x=·
xc =  · c
14
Nel seguito esamineremo il comportamento dei
seguenti sistemi a regime:
• M/M/1
(risorsa classica)
• M/M/1
con scoraggiamento degli arrivi
• M/M/1/K (coda con capacità limitata)
• M/M/m
(coda con un numero finito m di serventi)
• M/M/
(coda con un numero di serventi infinito)
In tutti i casi ipotizzeremo che i processi siano
ergodici.
15
M/M/1



tasso di
uscita
Può essere descritto come un processo nascita-morte
in cui:
•  (tasso di nascita) non dipende dallo stato;
•  (tasso di morte) non dipende dallo stato
processo omogeneo e uniforme
16

0

1


2

3

Lo stato è pari ad x(t), ossia al numero di utenti nella
risorsa al tempo t.
Poiché il processo è illimitato e per ipotesi anche
ergodico, deve aversi che
λ
ρ  1
μ
Per definizione infine, i tempi di inter-arrivo e di
servizio sono distribuiti esponenzialmente.
17
Usando la teoria vista in precedenza, possiamo
calcolare i seguenti parametri significativi.
Probabilità che vi siano i utenti nella risorsa a regime
Πi  ρi  (1  ρ)
i0
Fattore di utilizzo della risorsa a regime
υ  1  Π0  1  (1  ρ)  ρ
18
Tasso di uscita a regime (ossia produttività del
servente a regime)
η  (1  Π0 )μ  ρμ  λ
Numero medio di utenti nella risorsa a regime
ρ
x
(1  ρ)
19
Tempo medio di attraversamento della risorsa a
regime (ossia tempo mediamente speso nella risorsa
a regime)
x
1
  
λ μ (1  ρ)
Tempo medio di servizio a regime
1
s 
μ
20
Numero medio di utenti in coda a regime
Essendo la coda a servente singolo:
 = c + 1 / ,
per cui per la Legge di Little ( = x/, c = xc/) ,
x = xc +  / 
λ
ρ
ρ2
xc  x   x  ρ 
ρ 
μ
(1  ρ)
(1  ρ)
Numero medio di serventi occupati a regime
ρ
ρ2
xs  x - xc 
ρ
1-ρ 1-ρ
21
Fattore di utilizzo del servente
a regime
xs
~
ρ
ρ
m
Tempo medio speso in coda a regime
xc
ρ2
ρ
c  

λ λ (1  ρ) μ (1  ρ)
È facile quindi osservare che per   1, x,  e
c  .
22
M/M/1 con scoraggiamento degli arrivi

ing


abb
I tassi di arrivo e di servizio hanno distribuzione
esponenziale con parametri caratteristici  e 
rispettivamente.
Ipotesi: più la coda è lunga, più un utente si scoraggia.
ing decresce al crescere del numero di utenti nella
risorsa.
23
Per descrivere questa coda come un processo
nascita-morte facciamo le seguenti ipotesi:
1. Il tasso delle nascite i a partire dallo stato i è:
λ
λi 
i0
i1
ossia decresce secondo una legge iperbolica
all’aumentare del numero di clienti nella risorsa.
2. Il tasso delle morti  è pari al tasso di servizio
qualunque sia il numero di utenti nella risorsa.
24

0
/2
1

/3
2

3

Il verificarsi della condizione
ρ
λ
1
μ
è sufficiente per l’ergodicità del processo. Infatti
se tale diseguaglianza è verificata, a maggior
ragione è vero che
λ
 1 per k  1
(k  1) μ
25
Probabilità che a regime vi siano i utenti nella risorsa
Πi1 
i
μ i1
i
μ i1
Πi
i0

ρ
 

μ μ (i  1) (i  1)
i
ρ
ρ2
Π1  ρΠ0 , Π2  Π1  Π0 ,
2
2
ρ
ρ3
Π3  Π2  Π0 , 
3
3!
ρi
Πi  Π0
i!

 Πi  1
i 0
 ρi
ρi
ρ
 Π0  Π0  Π0 e  1
i 0 i!
i 0 i!

26
Π0  e -ρ
ρi -ρ
Πi  e
i0
i!
Fattore di utilizzo della risorsa a regime
  1  Π0  1  e -ρ
Tasso di uscita a regime (ossia produttività del
servente a regime)
η  (1  Π0 )μ  (1  e ρ )μ
27
Tasso di ingresso nella risorsa a regime (ossia
tasso di utenti ammessi nel sistema a regime)
A regime

ing
abb

η λ ing
λ ing μ (1  e ρ )
Tasso di abbandono a regime
λ abb  λ -λ ing  λ -μ (1  e ρ )  μ (ρ - 1  e ρ )
28
Numero medio di utenti nella risorsa a regime.
Usiamo la funzione generatrice di probabilità a regime:
i
ρ
Π(z)   Πi  z i , Πi  e -ρ
i!
i 0
i
 ρi
 ρ 1
Π(z)    z i  e -ρ  e -ρ     e -ρ  e ρ/z  e ρ/z-ρ
i 0 i!
i 0  z  i!

x 
d
 1

Π(z)    2 ρ  e -ρρ/z 
dz
 z
z 1 
z 1
x ρ
All’aumentare dell’intensità del
traffico, la condizione di regime si
raggiunge con un numero di utenti
nella risorsa crescente.
29
Numero medio di utenti in coda a regime
Essendo la coda a servente singolo:
 = c + 1 / ,
per cui per la Legge di Little ( = x/ing, c = xc/ ing) ,
x = xc + ing / 
μ (1 - e -ρ )
xc  x 
 ρ
 ρ  (1 - e -ρ )
μ
μ
λ ing
30
Tempo di attraversamento della risorsa a regime
(ossia tempo mediamente speso nella risorsa a
regime)
x
ρ
 

λ ing μ (1  e ρ )
Tempo medio speso in coda a regime
1
ρ
1 ρ - (1  e ρ )
c   - 
- 
ρ
μ μ (1  e ) μ μ (1  e ρ )
31
Numero medio di serventi occupati a regime
xs  x - xc  ρ - ρ  1 - e -ρ  1 - e -ρ
Fattore di utilizzo del servente
a regime
Tempo medio di servizio a regime
x
ρ~  s  1  e ρ
m
1
s 
μ
32
M/M/1/K (coda con capacità limitata)

ing
K-1


abb
I tassi di arrivo e di servizio hanno distribuzione
esponenziale con parametri caratteristici  e 
rispettivamente.
N.B. Nella notazione di Kendall, K indica il numero di
clienti nella coda d’attesa mentre noi ora stiamo
indicando con K il numero di clienti nell’intera risorsa.
33
Anche questo processo può essere studiato come
un processo di nascita morte in cui:
1. Il tasso delle nascite dipende dallo stato:
λ iK

λi 
 0 iK
2. Il tasso delle morti  è pari al tasso di
servizio qualunque sia il numero di utenti nella
risorsa.
Il sistema è quindi sempre ergodico anche nel caso
in cui non sia verificata la condizione
λ
ρ  1
μ
necessaria nel caso di processi
con un numero di stati infinito.
34


0
1


2

K-1
K

Probabilità di stato a regime
Πi1 

i
μ i1
i
μ i1
ρ
Πi
iK
i0
Π1  ρΠ0
Π  ρΠ  ρ2Π
1
0
 2

Πi  ρiΠ0
0 iK
Π  0
i K
 i
35
K
 Πi  1
i 0
K 1
1
ρ
Π0   ρi 
Π0  1
1-ρ
i 0
K
1-ρ
Π0 
1 - ρK 1
 1 - ρ  ρi 0  i  K

Πi  1 - ρK 1
0
i K
36
Fattore di utilizzo della risorsa a regime
coincidente con il fattore di utilizzo del servente
a regime
K
1

ρ
ρ(
1

ρ
)
  ρ~  1  Π0  1 

1  ρK 1 1  ρK 1
> è , > è la probabilità che il servente lavori
Tasso di uscita a regime (ossia produttività del
servente a regime)
K
1
ρ
η  (1  Π0 )μ  ρ~μ  λ 
1 - ρK 1
37
Tasso di ingresso nella risorsa a regime (ossia
tasso di utenti ammessi nel sistema a regime)
A regime

abb
ing

η λ ing
λ ing
1 - ρK
λ 
1 - ρK 1
Tasso di rifiuto (o di abbandono) a regime
λ abb  λ -λ ing
 1 - ρK 
1 - ρK

 λ -μ ρ 
 λ 1 K 1
K 1 
1-ρ
 1-ρ 
38
λ abb
 ρK (1 - ρ) 

 λ 
K 1 
 1-ρ

Per    il tasso di abbandono  .
Numero medio di utenti nella risorsa a regime.
Usiamo la funzione generatrice di probabilità a
regime:
i
1ρ
1ρ K ρ
i
i
i
Π(z)   Πi  z   ρ 
z 

K 1
K 1   
1ρ
1ρ
i 0
i 0
i 0  z 
K
K
39
K 1
1

ρ
1

(
ρ/z)
Π(z)   Πi  z i 

K 1
1  ρ/z
1ρ
i 0
K
d
(1  (K  1)ρK  KρK 1 )ρ
x   Π(z) 
K 1
dz
(1

ρ
)(1  ρ)
z 1
lim x ρ   0
ρ0
lim x ρ   K
ρ
x 1  K / 2
40
Tempo medio di attraversamento della risorsa a
regime (ossia tempo mediamente speso nella risorsa
a regime)
 
x
λ ing
1 - (K  1)ρK  KρK 1

μ (1  ρ)(1  ρK )
lim  ρ   1 / μ
ρ 0
lim  ρ   K / μ
ρ 
41
Tempo medio speso in coda a regime
1 ρ(1 - K ρK-1  (K - 1)ρK )
c    
μ
μ (1  ρ)(1  ρK )
Numero medio di utenti in coda a regime
xc  c λ ing
ρ2 (1 - K ρK-1  (K - 1)ρK )

(1  ρ)(1  ρK )
42
Numero medio di serventi occupati a regime
K
1
ρ
xs  ρ~  m  ρ~  ρ
1 - ρK 1
Tempo medio di servizio a regime
1
s 
μ
43
M/M/m
I tassi di arrivo e di servizio hanno distribuzione
esponenziale con parametri caratteristici  e 
rispettivamente.
Anche questo processo può essere studiato come un
processo di nascita-morte in cui:
1. Il tasso delle nascite non dipende dallo stato:
λ i λ
i
2. Il tasso di morte dipende dal numero di utenti
nella risorsa, ossia
i μ
im
μ i  
 m μ i  m
dove  indica il tasso di servizio di ogni servente.
44
Il sistema è ergodico se quando tutto i serventi
lavorano contemporaneamente, essi sono in grado
di smaltire gli utenti in arrivo, ossia se
ρ
λ ing
m μ

λ
1
m μ
Rappresentazione grafica:

0

2


m
m-1
1


(m-1)
m

m+1
m
m
45
Probabilità di stato a regime
Πi1 
i
μ i1
per i  0
Πi 

μ i1
Πi



Π1  μ Π0  μ Π0
1

2




Π2  μ Π1  2 μ Π1  2 μ 2 Π0
2

3




Π3  μ Π2  3μ Π2  3!μ 3 Π0
3



m

Π 
Π0
m
m

m!μ



Πm1 
Πm 
Πm  ρΠm
μ m1
mμ




Πm1 
Πm1  ρ2Πm
Πm2 
μ m 2
mμ

46

Π1  (m  ρ) Π0

(m  ρ)2
Π0
Π2 
2!

3
ρ)

m
(
Π 
Π0
 3
3!


m
ρ)

m
(
Π 
Π0
m

m!

(m  ρ)m
Π0
Πm1  ρ
m!

m
ρ)

m
(

2
Π0
ρ

Π
 m 2
m!


 (m  ρ)i
 i! Π0 i  m
Πi   m i
m  ρ Π0 i  m
 m!
47

m1

i 0
i 0
i m
 Πi   Πi   Πi  1
 m1 (m  ρ)i  mm  ρi 
 
 Π0 

im m! 
 i0 i!
 m1 (m  ρ)i (m  ρ)m  i 
 

 ρ  Π0 
m! i0 
 i0 i!
 m1 (m  ρ)i (m  ρ)m 
 
 Π0  1

m!  (1  ρ) 
 i0 i!
Π0 
1
(m  ρ)i (m  ρ)m


i!
m!  (1  ρ)
i 0
m1
48
Numero medio di serventi occupati a regime
m1
xs   i  Πi  m  Pr(x  m)
i 0
Si dimostra che
xs 
λ
 m ρ
μ
Fattore di utilizzo di un singolo servente a regime
x
ρ~  s  ρ
m
49
Tasso di uscita a regime
 λ
Numero medio di utenti nella risorsa a regime
Si dimostra che
mm  ρm1
x  mρ 
Π0
2
m! (1  ρ)
Tempo medio di attraversamento della risorsa
a regime
x
 
λ
50
Numero medio di utenti in coda a regime
xc  x - xs  x - m  ρ
Tempo medio di attesa in coda a regime
x 1
c  
λ μ
51
M/M/
Questo tipo di risorsa è particolarmente semplice da
studiare in quanto il numero di utenti nella coda
d’attesa è sempre pari a 0 essendovi infiniti serventi.
Anche questo processo può essere studiato come un
processo di nascita-morte in cui:
1. Il tasso delle nascite non dipende dallo stato:
λ i λ
i
2. Il tasso di morte dipende dal numero di utenti
nella risorsa, ossia
μ i  i μ
i
dove  indica il tasso di servizio di ogni servente.
52
Il processo è ergodico  ,  > 0.
Rappresentazione grafica:

0


1
2
3
2


3
4
Probabilità di stato a regime
Πi1 
i
μ i1
Πi 

(i  1)μ
Πi  ρ
1
Πi
(i  1)
per i  0
53
Π1  ρ Π0

ρ
ρ2
Π2  Π1  Π0
2
2!


ρ
ρ3
Π3  Π2  Π0
3
3!


ρi

Πi  i! Π0

 Πi  1
i 0
ρi
Π0  Π0 e ρ  1
i 0 i!

Π0  e -ρ
ρi -ρ
Πi  e
i!
i0
54
Osservazione: La probabilità di stato a regime
coincide in questo caso con quella relativa ad una
risorsa M/M/1 con scoraggiamento degli arrivi.
Naturalmente il comportamento della risorsa è però
completamente diverso. Ciò evidenzia chiaramente
come la probabilità di stato a regime, vista
singolarmente, non sia rappresentativa.
Fattore di utilizzo della risorsa a regime
υ  1 - Π0  1  e ρ
55
Tasso di uscita a regime
η λ
Numero medio di utenti nella risorsa a regime
Si dimostra che
x ρ
N.B. È chiaramente lo stesso della risorsa M/M/1
con scoraggiamento degli arrivi in quanto sono le
stesse le probabilità di stato a regime.
56
Tempo medio di attraversamento della risorsa
a regime
x ρ 1
   
λ λ μ
Tempo medio in coda a regime
c  0
Lunghezza media della coda a regime
xc  c λ  0
57
Numero medio di serventi occupati a regime
xs  ρ
Tempo medio di servizio a regime
1
s 
μ
Fattore di utilizzo di un singolo servente a regime
ρ~  0
58