1 7. Teoria delle Code Una coda è costituita da 3 componenti fondamentali: i serventi i clienti uno...

1

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).

coda di attesa

clienti in arrivo

clienti in uscita

serv. 1

serv. 2

serv. m

2

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.

Esempi: sistemi di comunicazione, di trasporto, sistemi informatici, ecc.

3

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

4

• Modalità di servizio.

Il tempo per servire un utente viene detto tempo di servizio.

Questo può essere

deterministico stocastico

con distribuzione esponenziale o meno

5

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.

6

• 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.

7

• 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.

8

• 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).

9

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 inter- arrivo con distribuzione esponenziale -->

processo markoviano, G : tempi di inter-arrivo con distribuzione qualunque).

• B indica la modalità di servizio : B {D,M,G}

• m indica il numero dei serventi: m N+ {+}

10

• 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.

11

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:

• (z,t) : funzione generatrice di probabilità associata a i(t):

0ii(t)Πi(t)x

0i

ii z(t)Πt)Π(z,

12

• xc(t) N : numero di utenti in coda all’istante t.

• 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:

• (z,t) : funzione generatrice di probabilità associata a i(t):

K(t)xmx(t)semx(t)(t)xmx(t)se0(t)x

c

c

c

0iic (t)Πi(t)x ˆ

0i

ii z(t)Πt)(z,Π ˆˆ

13

• (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.

14

Legge di Little

Se un sistema a coda è ergodico , in condizioni di regime valgono le seguenti relazioni:

x = ·

xc = · c

15

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.

16

M/M/1

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

tasso di uscita

17

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.

18

Usando la teoria vista in precedenza, possiamo calcolare i seguenti parametri significativi.

Probabilità che vi siano i utenti nella risorsa a regime

0iρ)ρΠ ii 1(

Fattore di utilizzo della risorsa a regime

ρρ)(11Π1 0 υ

19

Tasso di uscita a regime (ossia produttività del servente a regime)

λμμη ρ)Π(1 0

ρ)(1ρ

x

Numero medio di utenti nella risorsa a regime

20

Tempo medio di attraversamento della risorsa a regime (ossia tempo mediamente speso nella risorsa a regime)

ρ)(11x

μλ

Tempo medio di servizio a regime

μ1

s

21

ρ)(1ρ

ρρ)(1

ρρxxx

2

c

μλ

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 + /

Numero medio di serventi occupati a regime

ρρ-1

ρ-

ρ-1ρ

x-xx2

cs

22

Tempo medio speso in coda a regime

ρ)(1ρ

ρ)(1ρx 2

cc

μλλ

È facile quindi osservare che per 1, x, e c .

Fattore di utilizzo del servente a regime

ρmx

ρ s ~

23

M/M/1 con scoraggiamento degli arrivi

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.

ing

abb

24

Per descrivere questa coda come un processo nascita-morte facciamo le seguenti ipotesi:

1. Il tasso delle nascite i a partire dallo stato i è:

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.

0i1ii

λ

λ

25

0 1 2 3

/2 /3

Il verificarsi della condizione

è sufficiente per l’ergodicità del processo. Infatti se tale diseguaglianza è verificata, a maggior ragione è vero che

1ρ μλ

1kper11)(k

μλ

26

Probabilità che a regime vi siano i utenti nella risorsa

,

,,

μμμ

μ

0

3

23

0

2

1201

i

1i

i

i1i

i1i

Π3!ρ

Π3ρ

Π

Π2ρ

Π2ρ

ΠρΠΠ

1)(iρ

1)(i

0iΠΠ

1

1

ρ0

0i

i

00i

0

i0i

i

0

i

i

eΠi!ρ

ΠΠi!ρ

Π

Πi!ρ

Π

27

0iei!ρ

Π

eΠ

ρ-i

i

ρ-0


ρ-0 e1Π1


μμη )e(1)Π(1 ρ0

28

Tasso di ingresso nella risorsa a regime (ossia tasso di utenti ammessi nel sistema a regime)

ing

abb

A regimeingλη

)e(1 ρing

μλ

Tasso di abbandono a regime

)e1-(ρ)e(1 ρρingabb

μμ-λλ-λλ

29

Numero medio di utenti nella risorsa a regime.

Usiamo la funzione generatrice di probabilità a regime:

ρ-ρ/zρ/zρ-

0i

iρ-ρ-i

0i

i

ρ-i

ii

0ii

eeei!1

zρ

eezi!ρ

Π(z)

ei!ρ

Π,zΠΠ(z)

1z

ρ/zρ-2

1z

eρz1

Π(z)dzd

x

ρx All’aumentare dell’intensità del traffico, la condizione di regime si raggiunge con un numero di utenti nella risorsa crescente.

30

)e-(1ρ)e-(1

ρxx ρ-ρ-

ingc

μμ

μ

λ


Essendo la coda a servente singolo:

= c + 1 / ,

per cui per la Legge di Little ( = x/ing, c = xc/

ing) ,

x = xc + ing /

31


)e(1)e(1-ρ

-)e(1

ρ- ρ

ρ

ρc

μμ1

μμ1

Tempo di attraversamento della risorsa a regime (ossia tempo mediamente speso nella risorsa a regime)

)e(1ρx

ρing

μλ

32


ρ-ρ-cs e-1e-1ρ-ρx-xx

Fattore di utilizzo del servente a regime

ρs e1mx

ρ ~

Tempo medio di servizio a regimeμ1

s

33

M/M/1/K (coda con capacità limitata)

ing

abb

K-1


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.

34

Anche questo processo può essere studiato come un processo di nascita morte in cui:

1. Il tasso delle nascite dipende dallo stato:

2. Il tasso delle morti è pari al tasso di servizio qualunque sia il numero di utenti nella risorsa.

Ki0Ki

iλ

λ

Il sistema è quindi sempre ergodico anche nel caso in cui non sia verificata la condizione

necessaria nel caso di processi con un numero di stati

infinito.

1ρ μλ

35

0 1 2 K

K-1

Probabilità di stato a regime

Ki0ΠKi0ΠρΠ

ΠρρΠΠρΠΠ

Kiρ

0iΠΠ

i

0i

i

02

12

01

1i

i

i1i

i1i

μ

μ

36

1Πρ-1

ρ-1ρΠ1Π 0

K

0i

1Ki

0

K

0ii

1K0 ρ-1ρ-1

Π

Ki0

Ki0ρρ-1ρ-1

Πi

1Ki

37

Fattore di utilizzo della risorsa a regime coincidente con il fattore di utilizzo del servente a regime

1K

K

1K0 ρρρ(

ρρ

1Π1ρ

1

)1

1

1~

> è , > è la probabilità che il servente lavori


1K

K

0 ρ-1ρ

ρ)Π(1 -1λμ~μη

38

Tasso di ingresso nella risorsa a regime (ossia tasso di utenti ammessi nel sistema a regime)

ing

abb

A regimeingλη

1K

K

ing ρ-1ρ-1

λλ

Tasso di rifiuto (o di abbandono) a regime

1K

K

1K

K

ingabb ρ-1ρ-1

ρ-1ρ-1

ρ -1λμ-λλ-λλ

39

1K

K

abb ρ-1ρ)-(1ρ

λλ

Numero medio di utenti nella risorsa a regime.

Usiamo la funzione generatrice di probabilità a regime:

K

0i

i

1Ki

1K

K

0i

iiK

0ii z

ρρ1ρ1

zρ1ρ1

ρzΠΠ(z)

Per il tasso di abbandono .

40

ρ/z1ρ/z)1

ρ1ρ1

zΠΠ(z)1K

1Ki

K

0ii

(

ρ))(1ρ(1)ρKρ1)ρ(K(1

Π(z)dzd

x 1K

1KK

1z

2K1x

Kρx lim

0ρx lim

ρ

0ρ

/

41

Tempo medio di attraversamento della risorsa a regime (ossia tempo mediamente speso nella risorsa a regime)

)ρρ)(1(1Kρ1)ρ(K-1x

K

1KK

ing

μλ

μ/

μ/

Kρ lim

1ρ lim

ρ

0ρ

42



)ρρ)(1(11)ρ-KρK-ρ(11K

K1-K

c

μ

)(μ

)ρρ)(1(11)ρ-KρK-(1ρ

x K

K1-K2

ingcc )(

λ

43


1K

K

s ρ-1ρ-1

ρρmρx ~~

Tempo medio di servizio a regimeμ1

s

44

M/M/m


Anche questo processo può essere studiato come un processo di nascita-morte in cui:

1. Il tasso delle nascite non dipende dallo stato:

2. Il tasso di morte dipende dal numero di utenti nella risorsa, ossia

dove indica il tasso di servizio di ogni servente.

ii λλ

mimmii

i μμ

μ

45

Il sistema è ergodico se quando tutto i serventi lavorano contemporaneamente, essi sono in grado di smaltire gli utenti in arrivo, ossia se

1mm

ρ ing

μλ

μ

λ

Rappresentazione grafica:

0 1 m+1

m

m

m

m-1

2

(m-1)

m

46


0i per

ΠΠΠ i1i

i1i

i1i

μμ

m2

1m1m2m

2m

mmm1m

1m

0m

m

m

03

3

223

3

02

2

112

2

001

1

ΠρΠm

ΠΠ

ρΠΠm

ΠΠ

Πm

Π

Π3

Π3

ΠΠ

Π2

Π2

ΠΠ

ΠΠΠ

μμ

μμ

μ!

μ!μμ

μμμ

μμ

47

0

m2

2m

0

m

1m

0

m

m

0

3

3

0

2

2

01

Πm!ρ)m

ρΠ

Πm!ρ)m

ρΠ

Πm!ρ)m

Π

Π3!ρ)m

Π

Π2!ρ)m

Π

Πρ)mΠ

(

(

(

(

((

miΠ

m!ρm

miΠi!ρ)m

Π

0

im

0

i

i

(

48

ρ)(1m!ρ)(m

i!ρ)(m

1Π

1Πρ)(1m!

ρ)(mi!ρ)(m

Πρm!ρ)(m

i!ρ)(m

Πm!

ρmi!ρ)(m

1ΠΠΠ

m1m

0i

i0

0

m1m

0i

i

00i

im1m

0i

i

0mi

im1m

0i

i

mii

1m

0ii

0ii

49


m)Pr(xmΠix i

1m

0is

Si dimostra che ρmxs μλ

Fattore di utilizzo di un singolo servente a regime

ρmx

ρ s ~

50

Tasso di uscita a regime

λ


Si dimostra che 02

1mm

Πρ)m!

ρmρmx

1(

Tempo medio di attraversamento della risorsa a regime

λx

51


ρm-xx-xx sc

Tempo medio di attesa in coda a regime

μλ1x

c

52

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:

2. Il tasso di morte dipende dal numero di utenti nella risorsa, ossia

dove indica il tasso di servizio di ogni servente.

ii λλ

iii μμ

53

Il processo è ergodico , > 0.

Rappresentazione grafica:

0 1 2 3

2 3

4


0i perΠ1)(i

1ρΠ

1)(iΠΠ iii

1i

i1i

μμ

54

0

i

i

0

3

23

0

2

12

01

Πi!ρ

Π

Π3!ρ

Π3ρ

Π

Π2!ρ

Π2ρ

Π

ΠρΠ

0iei!ρ

Π

eΠ

1eΠi!ρ

Π

1Π

ρ-i

i

ρ-0

ρ0

0i

i

0

0ii

55

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.


ρ0 e1Π-1 υ

56

Tasso di uscita 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.

57

Tempo medio di attraversamento della risorsa a regime

μλλ1ρx

Tempo medio in coda a regime 0c

Lunghezza media della coda a regime

0x cc λ

58

Fattore di utilizzo di un singolo servente a regime

0ρ ~


ρxs

Tempo medio di servizio a regime

μ1

s

1 7. Teoria delle Code Una coda è costituita da 3 componenti fondamentali: i serventi i clienti uno...

Documents

Transcript of 1 7. Teoria delle Code Una coda è costituita da 3 componenti fondamentali: i serventi i clienti uno...