Sistemi di servizio e simulazione - Teoria - prof.Massimo Roma

Sistemi di servizio e simulazione - Teoria

Notazione di Kendall A/B/s/c/p/Z q

AB schemi di arrivo e servizio (M,E ,D,G). s serventi, c capacità (N +clienti serviti al momento), p

k

popolazione di potenziali clienti, Z schema di CODA (FIFO LCFS SIRO PRI)

Legge di Little

In un sistema a coda in condizioni stazionarie vale N=λT. DIM: per via grafica, assunzioni: 1 servente, FIFO,

a(t) utenti arrivati fino al tempo t, b(t) serviti fino al tempo t: n(t)=a(t)-b(t) [0,t]. Il tempo di permanenza

degli utenti nel sistema è rappresentato dall’area compresa tra i diagrammi a(t) e b(t):

() ()

∑ ∑

( )= + ( − )

. Ovvero la somma dei tempi di permanenza di tutti gli utenti

∫ =1 =()+1

0

(primo termine utenti usciti prima di t, secondo utenti ancora nel sistema al tempo t). Dividiamo per t

()

∫ ()

0 = ∗

entrambi i membri e dividiamo e moltiplichiamo per a(t) il secondo membro, otteniamo:

() ()

∑ ∑

+ (−)

=1 =()+1 . Ovvero N =λ T̴ . per t che tende all’infinito otteniamo N=λT.

t t t

()

T(t) e T̴ (t) differiscono nel fatto che T̴ non considera il tempo passato nel sistema dopo t per gli utenti non

ancora usciti al tempo t, per t all’infinito la differenza è trascurabile. q q

1,

(vale per G/G/s, vale solo se ρ≤ per ogni disciplina di coda, è quello effettivo, segue che N =λT

Counting process 0}

È un processo stocastico {X(t),t≥ in cui X(t) indica il numero di eventi accaduti fino al tempo t. Proprietà:

()

0 ∀ ≥ 0 ≤ ()

1) x(t) è a valori interi 2) X(t)≥ 3) Se s≤ 4)per s<t, X(t)-X(s) è il

numero di eventi accaduti in {s,t}

Counting process ad incrementi indipendenti

Il numero di eventi in intervalli di tempo diversi sono indipendenti

Counting process ad incrementi stazionari

Se la distribuzione del numero degli eventi in un certo intervallo di tempo dipende solo dall’ampiezza

dell’intervallo (quindi non da dove sono collocati).

Processo di Poisson (2 definizioni equivalenti)

Un counting process si dice di Poisson di parametro λ se valgono le seguenti proprietà:

1) X(0)=0 2) processo ad incrementi indipendenti 3) il numero degli eventi in un intervallo di

()

− λt

0:

ampiezza t X(s+t)-X(s) P

̴ oisson(λt), ovvero per ogni s,t≥ P(X(s+t)-X(s)=n)= !

0

Un Counting process è un processo di Poisson se e solo se per ogni t≥

1) X(0)=0 2) processo ad incrementi indipendenti 3) P(X(t+Δt)-X(t)=1)=λΔt+θ(Δt) 4) P(X(t+Δt)-

X(t)≥2)= θ(Δt)

Teorema che lega Poisson alla distribuzione esponenziale

Sono equivalenti le due affermazioni:

0}

1) {X(t),t≥ è un processo di Poisson di tasso λ −

( )

≤ = 1 −

2) Le variabili Ti (intertempi di arrivo) sono IID ̴ exp(λt) ovvero:

Se gli intertempi di arrivo tra 2 arrivi sono distribuiti esponenzialmente allora si ha un processo di Poisson.

Assenza di memoria perché il counting process è ad incrementi indipendenti e stazionari.

Invarianza per aggregazione e disaggregazione di processi di Poisson

0}

Se {X(t),t≥ è un processo di Poisson di parametro λ i processi disaggregati X1(t)…Xn(t) sono processi di

Poisson di parametri λpi dove pi è la probabilità dell’accadimento dell’evento di tipo i-esimo con

=1 =1

∑ ∑

= 1

. Viceversa X(t)=X1(t)+…+Xn(t) è un processo di Poisson di parametro λ=

1

Proprietà di Markov 0}

Un processo stocastico {X(t),t≥ a tempo continuo e a stato discreto gode della proprietà di Markov se:

(( )

≤ ) = + = /X(s)=i).

P(X(s+t)=j/X(s)=i, X(u)=iu, 0≤ s presente, s+t futuri X(u) pssato. La

probabilità che X assuma un certo valore nel futuro dipende solo dal valore assunto nel presente.

Catena di Markov

Processo stocastico a tempo continuo a spazio discreto che gode della proprietà di Markov

Proposizione: una catena di Markov a tempo continuo ha i tempi di permanenza negli stati distribuiti

esponenzialmente

DIM: chiamiamo Ti la variabile aleatoria che dà il tempo passato nello stato i, lo stato futuro dipende solo

dallo stato corrente, i tempi residui di permanenza devono avere solo la dipendenza dal presente. Possiamo

() = ( > +

scrivere che: P(Ti>s+t/Ti>s)=f(t) (deve dipendere solo da t non anche da s), si ha quindi:

)/( )

/ > ) = ( > + , > > = ( > + )/( > ). ( > +

facciamo il m.c.m

) = ( > )(), prendiamo s=0 P(Ti>0)=1 (cioè se il tempo che passa tra un evento ed il successivo è

( > ) = ( > 0)() () = ( > ),

nullo allora non ci sono stati eventi). Allora quindi

( > + ) = ( > )( > ).

sostituendo f(t) sopra si ottiene che questa ci dà l’assenza di

memoria delle Ti, l’unica distribuzione che ne gode è l’esponenziale, quindi Ti esponenziali, cvd

Catena di Markov a tempo continuo omogenea

Se le probabilità di transizione non dipendono dall’istante t ma solo da Δt.

Processo di Nascita e morte

Catena di markov a tempo continuo omogenea per la quale valgono le relazioni: (λ coefficiente di natalità e

μ di mortalità) 0

p (Δt)=λ Δt+θ(Δt), n≥

n,n+1 n 1

p (Δt)=μ Δt+θ(Δt), n≥

n,n-1 n 2

p (Δt)= θ(Δt), |m-n|≥

n,m

Un processo di sole nascite con λ costante è un processo di Poisson

DIM: un processo di nascita e morte è una catena di Markov quindi ha i tempi di permanenza negli stati

distribuiti esponenzialmente. Se abbiamo sole nascite il tempo tra un evento e un altro è il tempo di

interarrivo, se questo è esponenziale allora si ha un processo di Poisson.

0() 00(),

= − = 0

{

Equazioni di Kolmogorov: () 1()) (),

(

= − − ≥ 1

Equazioni di Kolmogorov

Le equazioni di Kolmogorov dicono come evolve pn(t) al variare di t. note le probabilità di transizione

p (Δt) per ogni n,m possiamo calcolare pn(t) attraverso un sistema di equazioni differenziali che con la

n,m

distribuzione stazionaria si riduce ad un sistema algebrico. Applicando il teorema delle probabilità totali

abbiamo: (Pn,n è p )

n,n

∑ ∑ ()()

P(N(t + Δt) = n/ ,

pn(t+Δt) = P(N(t+Δt)=n)= N(t)=i)P(N(t)=i) = =0

=0

1:

nel caso n≥ Pn(t+Δt) = Pn-1,n(Δt) + Pn,n(Δt)Pn(t) + Pn+1,n(Δt)Pn+1(t) + θ(Δt) = λ ΔtPn-1(t) + [1-

n-1

(λn+μn)Δt]Pn(t) + μ ΔtPn+1(t) + θ(Δt). Portiamo ora al primo membro Pn(t) e dividiamo per Δt ambo i

n+1

membri:

(+)− () ()

=λ Pn-1(t) – (λn+μn)Pn(t) + μ Pn+1(t) +

n-1 n+1

Per n=0 si ha: P0(t+Δt) = P00(Δ)P0(t) + P1,0(Δt)P1(t) + θ(Δ) = (1-λ0Δt)P0(t) + μ1ΔtP1(t) + θ(Δt). Facciamo i

0(+)– 0()

passaggi analoghi a prima (portiamo un membro a sinistra e dividiamo per Δt): = -λ0P0(t) +

()

μ1P1(t) + 2

0

Passando al limite per Δt→ otteniamo:

0() 11() 00(),

= − = 0

{

() 1()) ( )() 1()),

( (

= − 1 − − + + + 1 + ≥ 1

Equazioni differenziali che regolano la probabilità che lo stato sia n al variare di t. infinite equazioni

differenziali, possiamo garantire l’esistenza delle soluzioni sotto opportune condizioni iniziali Pn(0). Il

sistema ha matrice tridiagonale quindi si risolve per ricorsione.

Soluzione stazionaria delle equazioni di Kolmogorov

Facciamo tendere t all’infinito nelle equazioni, cade la dipendenza da t, otteniamo quindi un sistema

−00 + 11 = 0, = 0

{

algebrico. risolvendo ricorsivamente per

( 1) ( ) ( 1)

− 1 − − + + + 1 + = 0, ≥ 1

n=0,1,2.. si ottiene la soluzione stazionaria delle equazioni di Kolmogorov:

1

0 = , =0

−1

∏

=0

1+∑

=1 ∏ la condizione stazionaria esiste quando la sommatoria al

=1

−1

∏

=0

= ∗ 0, ≥1

∏

{ =1

denominatore di P0 converge, cioè <inf. 11 = 0

{

Equazioni di bilancio globale: ( 1) ( 1)

− 1 − + + 1 + = +

Poisson Arrivals See Times Average PASTA:

Dato un sistema a coda con arrivi poissoniani la probabilità che un utente che arriva nel sistema al tempo t

trovi il sistma allo stato k è uguale alla probabilità che il sistema sia allo stato k al tempo t, ovvero:

a (t)=p (t).

k k

DIM: sia {X(t), t>=0} un processo di poisson di sole nascite che descrive gli arrivi. Per le probabilità

(() | (

lim = +

composte: a (t)=P{un utente arriva al tempo t e trova il sistema nello stato k} =

k →0

|

((+)−()=1 ()=)(()=) 1((+)−()=1)(()=)

) ()

− = 1) lim = lim =

= ((+)−()=1) ((+)−()=1)

→0 →0

(() )

= = p (t)

k

Questo risultato non dipende dal tipo di sistema di servizio ma soltanto dai processi di arrivo.

Proposizione: in un sistema M/M/1 con disciplina della coda FIFO il tempo di permanenza nel sistema è

−(−)

w 0.

distribuito esponenzialmente di parametro μ-λ: P(