8. Reti di Code

Nella maggior parte dei processi produttivi risulta troppo restrittivo considerare una sola risorsa.

Esempio: linea tandem

Carla Seatzu, 18 Marzo 2008

1

arriviµ1 µv

partenze

Vi sono diverse stazioni in cui una parte meccanica deve venire pulita, verniciata, lucidata, asciugata, ecc.

Esempio: linea con riciclo

arrivi dall’esterno

µ1 µ2partenze

riciclo

2

Vi sono due macchine in cascata. La prima esegue una certa operazione e la seconda verifica che tale operazione sia stata eseguita correttamente. Nel caso in cui vi sia qualche imperfezione nella lavorazione, questa deve essere eseguita nuovamente.

Le reti di code vengono distinte in

reti di code aperte reti di code chiuse

Vi sono arrivi dall’esterno e Il sistema è isolato: non

3

Vi sono arrivi dall’esterno e vi sono parti che vengono instradate al di fuori del sistema.

Il sistema è isolato: non vi sono né arrivi dall’esterno né parti che vengono instradate al di fuori del sistema.

Esempio: rete di code aperta

µ1 µ2 µ3

Esempio: rete di code chiusa

4

Esempio: rete di code chiusa

µ1 µ2

Come visto in precedenza la teoria delle code consente di calcolare in modo sistematico le grandezze caratteristiche a regime delle risorse ergodiche nel caso in cui sia i tempi di inter-arrivo che i tempi di servizio sono esponenziali.

Tali risultati non sono in genere applicabili alle reti

5

Tali risultati non sono in genere applicabili alle reti di code in cui gli arrivi in alcune risorse sono strettamente legati alle uscite delle altre risorse e non godono quindi necessariamente della proprietà di markovianeità.

Esiste tuttavia un importante teorema relativo alle code M/M/m che consente di utilizzare nello studio delle reti di code M/M/m i risultati visti in precedenza.

Teorema di Burke: In una risorsa M/M/mergodica e a regime, il processo di uscita è un

6

ergodica e a regime, il processo di uscita è un processo poissoniano caratterizzato dallo stesso parametro del processo di ingresso.

λ λµ

µ

Esempio: linea tandem a due stati con risorse M/M/1

λµ1 µ2

λ

La risorsa 2 vede in ingresso degli arrivi poissoniani che sono l’uscita dalla risorsa 1.

7

che sono l’uscita dalla risorsa 1.

Ogni singola risorsa può venire studiata separatamente.

)ρ(1ρ

x)ρ(1

ρx

2

22

1

11

−=

−=

Numero medio di utenti nelle singole risorse a regime

)ρ(1ρ

)ρ(1ρ

xxx2

2

1

121

−+

−=+=

Numero medio di utenti nella rete a regime

Tempo medio di attraversamento della rete a regime

8

)ρ(11

)ρ(11

2211 −+

−=+=

µµ21 ϑϑϑ

Reti di Code Markoviane Aperte

Sono costituite da v risorse M/M/m.

La i-esima risorsa ha tasso di servizio µi e tasso di ingresso complessivo λi .

Il processo degli arrivi dall’esterno è poissoniano per ciascuna risorsa. Indichiamo con λiin quello relativo

9

ciascuna risorsa. Indichiamo con λi quello relativo alla i-esima risorsa.

All’uscita dalla i-esima risorsa il cliente viene instradato alla risorsa j-esima con probabilità rijoppure viene instradato all’esterno con probabilità ri0. Chiaramente per ogni i, risulta

∑ ==

v

0jijr 1

Esempio: rete aperta composta da tre risorse M/M/1

µ1 µ2 µ3λ1 λ2 λ3

λ1in λ2

in λ3in

0.5 0.5 0.5

0.50.5 0.5

10

v=3, λ1in = λ2in = 7, λ3

in = 14

+=

+=

+=

2in33

1in22

3in11

0.5

0.5

0.5

λλλ

λλλ

λλλValgono inoltre le seguenti relazioni:

In generale, data una rete aperta markoviana con v risorse, possiamo scrivere v equazioni del tipo

Equazioni di traffico della rete.j

v

1jji

inii r λλλ ∑ ⋅+=

=

11

Le probabilità rij vengono dette probabilità di instradamento o di routing.

Introducendo i vettori riga

[ ] [ ]inv

in1

inv1 λλλλλλ ⋯⋯ ==

e definendo

=

1v11

rr

rrR

⋯ Matrice di routing

12

le equazioni di traffico possono essere riscritte in forma matriciale come

vvv1 rr

Rin ⋅+= λλλ

routing

da cui risulta che 1-in R)(I −⋅=λλ

Per quanto riguarda l’ergodicità di una rete apertavale il seguente

Teorema: Una rete aperta è ergodica se e solo se è ergodica ogni singola risorsa.

13

ergodica ogni singola risorsa.

Si dimostra che se una rete è ergodica la matrice(I-R) è non singolare (condizione necessaria per l’ergodicità della rete).

Essendo tale condizione solo necessaria, può aversi che det(I-R) ≠ 0 senza che la rete sia ergodica.

λµ1 µ2

λ

Esempio

14

0R)det(I101-1R-I00

10R ≠−

=

=

Tale sistema non è però ergodico per ogni valore di λ, µ1 e µ2. Ad esempio non lo è se λ > µ1 oppure λ > µ2 .

Definiamo stato di una rete di code con v risorse, un vettore riga x con v componenti, la cui i-esima componente x(i) rappresenta il numero di utenti nella i-esima risorsa.

[ ]x(v)x(1)x ⋯=

La probabilità di stato di una rete di code è definita

15

La probabilità di stato di una rete di code è definita come

)xx(v),,xPr(x(1))x,,Π(x v1v1 === ⋯⋯

Teorema di Jackson: In una rete aperta di code M/M/m, ergodica e a regime

1. la probabilità che vi siano xi utenti nella i-esima risorsa può ricavarsi come se la risorsa fosse isolata e avesse tasso di arrivo λi, dove λ i è soluzione di

1-in R)(I−⋅=λλ iΠ si calcola

16

2. la probabilità che la rete sia nello stato

[ ]v1 xxx ⋯=

è)) vv11v1 (xΠ(xΠ)x,,Π(x ⋯⋯ =

con le formule viste per le code isolate.

Si dice anche che le reti di code M/M/m aperte ed ergodiche godono della forma prodotto.

Le risorse sono pertanto stocasticamente indipendenti.

17

Se una rete è ergodica

vale ancora la Legge di Little

Sia λin il tasso medio degli arrivi a regime nella rete e λiin il tasso medio degli arrivi a regime nella i-esima

risorsa

Legge di Little in grande

∑==

v

1i

ini

in λλ

Sia x il numero medio di utenti a regime nella rete e xiil numero medio di utenti a regime nella i-esima risorsa

18

∑==

v

1iixx

il numero medio di utenti a regime nella i-esima risorsa

ϑ⋅= inx λ

dove ϑ indica il tempo medio di attraversamento dell’intera rete di code.

Esempio: rete aperta composta da tre risorse M/M/1

µ1 µ2 µ3λ1 λ2 λ3

λ1in λ2

in λ3in

0.5 0.5 0.5

0.50.5 0.5

19

λ1in = λ2in = 7, λ3

in = 14

=

000.50.50000.50

R

=

8/72/74/74/78/72/72/74/78/7

R)-(I 1-

[ ]221618=λ

Siano

µ1 = 20, µ2 = 32, µ3 = 33

allora ρ1 = 9/10, ρ2 = 1/2, ρ3 = 2/3.

Inoltre

20

))) vv2211321 (xΠ(xΠ(xΠ)x,x,Π(x ⋅⋅=

e poiché vale la forma prodotto

321 x33

x22

x11321 ρρρρρρ)x,x,Π(x )1()1()1( −⋅−⋅−=

12)ρ(1

ρ

)ρ(1ρ

)ρ(1ρ

xxxx3

3

2

2

1

1321 =

−+

−+

−=++=

λ1in = λ1in + λ2in + λ3in = 7 + 7 + 14 = 28

2812x

in ==λ

ϑ Tempo medio di attraversamento dell’intera

21

28inλ attraversamento dell’intera rete.

Reti di Code Markoviane Chiuse

Non vi sono arrivi dall’esterno, pertanto λiin = 0, per ogni i = 1, … , v.

Non vi sono partenze verso l’esterno, ossia ri0 = 0, per ogni i = 1, … , v.

22

Il numero di clienti all’interno del sistema rimane costante.

Lo spazio di stato di una rete chiusa con v risorse e n utenti è finito e si denota con N v,n.

Esempio: v=2, n=3.

1)!(vn!

1)!n(vn

1nv)card(N nv,−

−+=

−+=

N v,n = { (3,0), (2,1), (1,2), (0,3) }

23

41!3!

4!)card(N 2,3 ==

Studiando le reti di code aperte Markoviane abbiamo visto che, se queste sono ergodiche, possono essere studiate esaminando le singole risorse singolarmente poiché in virtù del teorema di Jackson le singole risorse sono stocasticamente indipendenti.

Nelle reti chiuse invece questo non è più vero e le

24

Nelle reti chiuse invece questo non è più vero e le risorse non sono più indipendenti. Infatti:

∑ ==

v

1ii nx ossia il numero di utenti nella

rete è costante.

Una possibilità per studiare una rete di code Markoviane chiuse consiste nell’associare ad essa una particolare catena di Markov a tempo continuo.

Sia

il generico stato della rete.

Costruiamo un grafo con tanti vertici quanti sono gli stati della rete.

][ vjk1 xxxxx ⋯⋯⋯=

25

stati della rete.]11[ vjk1 xxxx ⋯⋯⋯ +−

][ vjk1 xxxx ⋯⋯⋯

γk,xk rkj

La frequenza con cui un utente passa dalla k-esima alla j-esima risorsa è pari a

γk,xk rkj

dove

• rkj rappresenta la probabilità che un utente che esce dalla k-esima risorsa vada alla j-esima,

26

esce dalla k-esima risorsa vada alla j-esima,

• γk,xk rappresenta il tasso delle partenze dalla k-esima risorsa quando in essa vi sono xk utenti.

Esempio

µ1 µ2

1-p

p

v=2, n=3 4)card(N 2,3 =

27

v=2, n=3 2,3

La rete può trovarsi in 4 diversi stati.

La prima risorsa ha un solo servente, la seconda ne ha 2 (m1=1, m2=2).

Catena di Markov associata alla rete di code chiusa

µ1 µ1

3,0 2,1

0,3 1,2

µ1

p µ2

2 p µ2

2 p µ2

x1 x2

x4 x3

28

Poiché il grafo associato a tale CMTC ammette un’unica componente ergodica possiamo concludere che la rete è ergodica.

Nello studio di questa rete possiamo quindi applicare i risultati visti per le CMTC.

2 p µ2

Sia µ1 = 10, µ2 = 6, p = 0.5

− − =

−

10 10 0 0

3 13 0 10Q

0 6 -16 10

0 0 6 6

=

= 2501509027Π

0QΠl

29

=

∑ =

=

517250

517150

51790

51727

Π1Π0QΠ

li il,

l

Distribuzione limite

Alternativamente possiamo basarci sulle equazioni di traffico della rete:

j

v

1jjii r λλ ∑ ⋅=

=

che in forma matriciale possono essere scritte come

30

R⋅= λλ dove R è la matrice di routing che gode della seguente proprietà

La matrice R associata ad una rete di code chiusa ha sempre un autovalore = 1.

Teorema: Una rete di code markoviane chiusa è ergodica se e solo se:

• l’autovalore = 1 di R è semplice.

Questo teorema è molto importante perché ci permette di stabilire se una rete è ergodica semplicemente calcolando gli autovalori della

31

semplicemente calcolando gli autovalori della matrice R che ha dimensioni pari al numero di risorse.

Se invece associamo alla rete una CMTC e applichiamo il criterio degli autovalori dobbiamo determinare gli autovalori di Q che ha dimensioni pari al numero di stati.

Esempio

µ1 µ2

1-p

p

-p-1p1-I-Rp-1p

10R == λλ

32

p1

p)1)(-(I)-det(R

-p-1p1-I-Rp-1p

10R

1,2 −=

+=

=

=

λ

λλλ

λλ

λ

sempre ergodica

Vediamo ora come calcolare le probabilità di stato a regime utilizzando le equazioni di traffico della rete.

Diamo prima le seguenti definizioni preliminari.

• Sia soluzione di λ~ R⋅= λλ

v,1,iρ i…==

λ~

33

v,1,iρi

ii …==µ

λ

coefficiente di traffico della i-esima risorsa

• βi(xi) è una funzione che dipende dal numero di serventi della i-esima risorsa

⇒ Se la i-esima risorsa è a servente singolo

ixiii ρ)(x =β

⇒ Se la i-esima risorsa ha mi serventi

<xi mxseρ i

34

≥

<

=

− iimxii

xi

iii

i

ii

mxsem!m

ρ

mxsexρ

)(x

ii

i

!β

Teorema di Gordon e Newell: In una rete di code markoviane chiusa ed ergodica, la distribuzione di probabilità di stato a regime è

)(xΠC1

)x,,x,Π(x ii

v

1iv21 β

=

⋅=…

35

dove C è una costante di normalizzazioneche si determina imponendo che

1]

=∑∈

)x,,x,Π(x v21Nx,,x,[x nv,v21

…

…

Osservazioni

1) La probabilità di stato a regime è anche nel caso delle reti chiuse nella forma prodotto.

Tuttavia in questo caso le variabili di stato aleatorie xi non sono indipendenti e quindi non è possibile scrivere la probabilità come prodotto delle v probabilità marginali.

36

probabilità marginali.

2) La determinazione della costante di normalizzazione C richiede l’enumerazione di tutti i possibili stati della rete e risulta pertanto non agevole poiché la cardinalità dello spazio di stato risulta molto elevata anche per piccoli valori di n e v.

Esempio

µ1 µ2

1-p

p

Sia n=3, µ1 = 10, µ2 = 6, p = 0.5.

37

31

ρ101

ρ

21

0.50.510

p-1p10R

21 ==

=

=

= λ

~

≥

<=

=

−2xse

2

ρ

2xseρ)(x

ρ)(x

21x

x2

2x

2

22

x111

2

2

2

1

β

β

β β β β= = = =1 1 1 1(0) 1 (1) 1/10 (2) 1/100 (3) 1/1000

38

β β β β= = = =2 2 2 2(0) 1 (1) 1/3 (3) 1/18 (3) 1/108

108C1

C(3)β(0)β

Π(0,3)180C1

C(2)β(1)β

Π(1,2)

300C1

C(1)β(2)β

Π(2,1)1000C1

C(0)β(3)β

Π(3,0)

2121

2121

====

====

8147156

C

1Π(0,3)Π(1,2)Π(2,1)Π(3,0)

=

=+++

=

=

51790

Π(2,1)

51727

Π(3,0)

39

=

=

517250

Π(0,3)

517150

Π(1,2)

517

Tale distribuzione coincide con quella trovata associando una CMTC alla rete.