ELEMENTI DI TEORIA DELLE CODE - uniroma2.it · ed il numero di utenti che può essere servito...

ELEMENTI DI TEORIA DELLE CODEELEMENTI DI TEORIA DELLE CODE

corso diTerminali per i Trasporti e la Logistica

ELEMENTI DI TEORIA DELLE CODEELEMENTI DI TEORIA DELLE CODE

Umberto [email protected]

INTRODUZIONE Elementi di Teoria delle Code

In generale, un terminale è costituito da un insieme di punti di servizio per gli utenti che possono essere disposti in:

� serie

� parallelo

� misti (serie-parallelo o parallelo-serie)

Simulazione dei terminali

U. Crisalli - Terminali per i Trasporti e la Logistica 2

� misti (serie-parallelo o parallelo-serie)



gate imbarco

scale mobili di accessopercorsi di accesso agli imbarchi

� � � � �

pista di decollo

procedure di decollo

gate imbarco

scale mobili di accessopercorsi di accesso agli imbarchi

� � � � �

pista di decollo

procedure di decollo


check-in

controlli sicurezza

percorsi di accesso agli imbarchi

biglietteria

………….

check-in

controlli sicurezza

percorsi di accesso agli imbarchi

biglietteria

………….

INTRODUZIONE

In ogni punto di servizio vengono svolte delle attività che:

� richiedono un certo tempo di servizio � capacità� impegnano delle risorse

capacità: massimo numero di utenti che è possibile servire nel periodo di riferimento consideratoEs. barriera autostradale (unico canale)

Definizione del problemaElementi di Teoria delle Code


Es. barriera autostradale (unico canale)tempo medio di servizio 3 veic./min � capacità del punto di servizio 180 veic./h

tasso medio degli arrivi: numero medio di utenti in arrivo nel sistema

tasso medio degli arrivi > tasso medio di servizio � codaEs. barriera autostradale (unico canale)arrivano 400 veic/hcapacità 180 veic./h � 220 veic/h in coda


tasso medio degli arrivi > tasso medio di servizio(condizioni di sovrasaturazione)

Se queste condizioni permangono nel tempo la coda cresce indefinitivamente

ora arrivi capacità codaveic. veic. veic.

Definizione del problema


condizioni di sovrasaturazione

220440

660880

11001320

15401760

1980

0

500

1000

1500

2000

2500

1 2 3 4 5 6 7 8 9 10tempo (h)

coda

(ve

ic.)

veic. veic. veic.1 400 180 2202 400 180 4403 400 180 6604 400 180 8805 400 180 11006 400 180 13207 400 180 15408 400 180 17609 400 180 1980

10 400 180 2200


La coda può essere smaltita solo se

tasso medio degli arrivi < tasso medio di servizio(condizioni di sottosaturazione)

Se permangono queste condizioni, dopo un certo periodo di tempo, la coda può essere smaltita.



90

180

260240

200

0

50

100

150

200

250

300

1 2 3 4 5 6tempo (h)

coda

(ve

ic.)

ora arrivi capacità codaveic. veic. veic.

1 200 180 202 400 180 2403 200 180 2604 100 180 1805 90 180 906 90 180 0


Si noti che, essendo il numero di arrivi ed il tempo di servizio delle variabili aleatorie, anche in condizioni di sottosaturazione può generarsi una coda


Esempio (1/2)0<arrivi<60 sec. 0<Ts<30 sec.

arrivi servizio5 30

sistema ad un unico canale


50 1299 24

139 12199 28256 28285 26293 25300 6359 25

0

1

2

1 9 17 25 33 41 49 57 65 73 81 89 97 105

113

121

129

137

145

153

161

169

177

185

tempo (sec)

cum

ulat

a ar

rivi

…….

30 12 24 12


Si noti che, essendo il numero di arrivi ed il tempo di servizio delle variabili aleatorie, anche in condizioni di sottosaturazione può generarsi una coda


Esempio (2/2)

0<arrivi<60 sec. 0<Ts<30 sec.arrivi servizio

5 30

4

CODA

sistema ad un unico canale


5 3050 1299 24

139 12199 28256 28285 26293 25300 6359 25 0

1

2

31

90

19

8

20

6

21

4

22

2

23

0

23

8

24

6

25

4

26

2

27

0

27

8

28

6

29

4

30

2

31

0

31

8

32

6

33

4

34

2

35

0

35

8

36

6

37

4

38

2

39

0

39

8

tempo (sec.)

cum

ulat

a ar

rivi

………..

25

6

26

CODA

2828 25


Dimensionare la capacità dei punti di servizio per:

�evitare fenomeni di sovrasaturazione

�contenere i tempi di attesa entro standard prefissati

capacità di un punto di servizio ≠≠≠≠ capacità del sistema

Obiettivo


Sistema S con più punti di servizio p IN SERIECAPS = capacità del sistema S

capp = capacità del punto di servizio p

CAPS = minp [capp] ∀p∈S

La capacità di un sistema costituito da punti di servizio in serie è pari alla più bassa delle capacità dei singoli punti di servizio che compongono il sistema.


Lo studio dei terminali di trasporto, e dei singoli punti di servizio al suo interno, può essere effettuata utilizzando:

� modelli analitici (teoria delle code)



� modelli sperimentali (simulazione)


I sistemi a barriera


Caratteristiche del sistema

�modello degli arrivi

�meccanismo del servizio

�disciplina della coda

Elementi di Teoria delle Code

Modello degli arrivi

Occorre definire:� il “tempo intercorrente tra un istante qualsiasi e un arrivo

successivo”


� il “numero di arrivi in un intervallo fissato di tempo t”

��variabili aleatorie con una data distribuzione


Modello degli arrivi alla Poisson (1/3)

Una successione nel tempo di arrivi prende il nome di processo di Poisson con parametro α quando:

�la probabilità che si verifichi un arrivo nell'intervallo (t, t+δt), al tendere di δt a 0 è proporzionale all'ampiezza δt dell'intervallo tramite α, a meno di un infinitesimo di ordine superiore, ovvero:


infinitesimo di ordine superiore, ovvero:

….. (continua)

( )[ ] ( )tOt1tt,tNproblim0t

δ+αδ==δ+→δ


Modello degli arrivi alla Poisson (2/3)Una successione nel tempo di arrivi prende il nome di processo

di Poisson con parametro α quando:

�la probabilità che si verifichi più di un arrivo tende ad un infinitesimo di ordine superiore:

( )[ ] ( )tO1tt,tNproblim δ=>δ+


e quindi la probabilità che non si verifichi alcun arrivo è:

….. (continua)

( )[ ] ( )tO1tt,tNproblim0t

δ=>δ+→δ

( )[ ] t10tt,tNproblim0t

αδ−==δ+→δ


Modello degli arrivi alla Poisson (3/3)

Una successione nel tempo di arrivi prende il nome di processo di Poisson con parametro α quando:

�la probabilità di un arrivo nell'intervallo (t, t+δt) è indipendente da ciò che è accaduto negli intervalli precedenti (la probabilità condizionata è uguale alla probabilità semplice):


alla probabilità semplice):

….. (continua)

( ) ( )[ ] ( )[ ] ( )tOt1tt,tNprobit,ttN/1tt,tNproblim0t

δ+αδ==δ+==δ−=δ+→δ


Se il processo degli arrivi degli utenti è un processo di Poisson con tasso medio αααα

��

�il “numero di arrivi in un intervallo fissato di tempo t” è una v.a. discreta di Poisson

Modello degli arrivi alla Poisson


�Il “tempo intercorrente tra un istante qualsiasi e un arrivo successivo” è una v.a. continua esponenziale negativa con media l/α

��

arrivi completamente casuali


Meccanismo di servizio�numero di canali serventi

�tempo di servizio ts�Tempi di servizio costanti (approccio deterministico)

il tempo di servizio vale ts per tutti gli utenti ed il tasso medio di servizio, ed il numero di utenti che può essere servito nell’unità di tempo è pari a 1/ts


�Tempi di servizio variabili (approccio stocastico)

il tempo di servizio è una variabile aleatoria, di cui occorre definire la distribuzione. Spesso ci si può ricondurre alle leggi di probabilità di Erlang(e quindi all’esponenziale negativa nel caso K=1);se ts è il tempo medio di servizio, il tasso medio di servizio è 1/ ts

Se i tempi di servizio sono distribuiti secondo una esponenziale negativa, il processo delle partenze è un processo di Poisson di parametro σ = 1/ ts


� sistemi ad un canale� accesso al servizio in ordine di arrivo (FIFO);

� accesso in modo casuale;

� l’ultimo arrivato è il primo servito (LIFO);

� esistono utenti che hanno priorità rispetto agli altri.

Disciplina della coda


� sistemi a più canali� unica coda con accesso al primo canale libero;

� una coda per ogni canale

� con scelta libera da parte degli utenti

� con scelta vincolata da regole predeterminate(ad esempio suddivisione per lettera alfabetica)


A/B/m; n/Cdove:� A indica il modello degli arrivi

(M=arrivi alla Poisson)

� B indica il modello di servizio

Denominazione dei sistemi(Codice Kendall)


� B indica il modello di servizio(M=tempi di servizio esponenziali negativi; EK=tempi di servizio alla Erlang con parametro K)

� m indica il numero di canali di servizio;

� n il numero massimo di utenti che possono essere accolti in coda;

� C indica la disciplina del servizio(FIFO, LIFO, RIFO, ecc.)

Ad esempio: M/M/1; ∞/FIFO


Definizioni:

� intensità di traffico ρρρρ :

ρ = α / σ

Variabili di sistema


dove:

� α = tasso medio di arrivo per canale;

� σ = 1/ ts tasso medio di servizio (capacità o potenzialità)


Per un casello autostradale con un solo posto di esazionesi ha un tasso medio di arrivo 3 veicoli al minuto e un tasso medio di serviziodi 6 veicoli al minuto……..(continua)

unico canale servente

Esempio


unico canale servente

α = 3

σ = 6

��ρ = α / σ = 0.5


Definizioni:� tempo di attesa wA:

tempo intercorrente tra l’ingresso dell’utente nel sistema e l’inizio del servizio

Variabili di sistema


� tempo di permanenza nel sistema ws:tempo intercorrente tra l’arrivo dell’utente e la fine del servizio

��ws = wA + ts


Variabili di sistemaDefinizioni:

� = numero medio di utenti nel sistema

� = numero medio di utenti in attesa

� = tempo medio di permanenza nel sistema

� = tempo medio di attesa

sn

An

sw

Aw


��α= /nw ssα= /nw AA

ssA tww −=ρ−= sA nn


Misura delle caratteristiche di funzionamento del sistema

Dato un punto di funzionamento del sistema occorre determinare:

�media e distribuzione dei tempi di attesa wA;

�media e distribuzione del numero ns di utenti presenti nel sistema ed nA presenti in coda ad ogni istante;


sistema ed nA presenti in coda ad ogni istante;

�media e distribuzione dei tempi in cui i canali sono occupati da utenti.

RISULTATI DELLA TEORIA DELLE CODE Elementi di Teoria delle Code

Equazioni di equilibrio del sistema[M/M/1; ∞,FIFO]

Pn(t) = probabilità che il sistema si trovi alla stato An al tempo t

la probabilità che nell’intervallo (t, t+δt) il sistema passi dallo stato:

� An ��An+1 è pari a αδt;

� An � An-1 è pari a σδt


� An � An-1 è pari a σδt

� An � An+2 è pari a 0

� An � An-2 è pari a 0

si può verificare solo uno dei seguenti eventi:� 1 arrivo, con probabilità αδt

� 1 partenza, con probabilità σδt,

� 0 arrivi e 0 partenze, con probabilità 1 - (αδt + σδt)


sistema in equilibrio� …=Pn(t-1) = Pn(t) =…= Pn

( ) [ ] ( ) ( ) ttP+ttP+t)+(-1tP = )t+(tP 1+n1-nnn σδ⋅αδ⋅δ⋅σα⋅δ( ) ( )( ) ( ) ( )σ+α+σ+α−= +− tPtPtP

dttdP

1n1nnn

Equazioni di equilibrio del sistema[M/M/1; ∞,FIFO]

RISULTATI DELLA TEORIA DELLE CODE


Equazioni di equilibrio:0PP 10 =σ+α−

( ) 0PPP 201 =σ+α+σ+α−............................................................................................................................

............................................................................................................................

( ) 0PPP 1n1nn =σ+α+σ+α− +−

∑ =1Pi

n0n PP ρ=�


Sistemi ad unico canale [M/M/1; ∞,FIFO]

arrivi alla Poisson e tempi di servizio esponenziali


α = tasso medio arriviσ = tasso medio servizi

n0n PP ρ=

1PP0n

n0

0nn =∑ ρ=∑

∞

=

∞

=

=∑ρ∞ 1n


( )ρ−=∑ρ

∞

= 11

0n

n per 1≤ρ

ρ−= 1P0

nn )1(P ρ⋅ρ−=

poiché

�

�





� numero medio di elementi nel sistema

( ) ( )ρ−ρ=∑ ρρ−=∑=

∞

=

∞

= 11nnPn

0n0nns n

ρ∞

VARIABILI DI SISTEMA


�numero medio di elementi in attesa

( )20n 1n n

ρ−ρ=∑ ρ

∞

=

( ) ( )ρ−ρ=ρ−=−⋅−=

1nP11nn

2s0sa

essendo





� funzione di distribuzione FN dei numero di elementi nel sistema


( ) [ ] ( ) 1rr

0n

nr

0nnN 11PrnPrF +

==ρ−=∑ρρ−=∑=≤=


� probabilità di avere più di N utenti in attesa

� probabilità PA di attendere

2+NsA =1)+N > P(n= N)>P(n ρ

= 1) > (n P= P 2sA ρ





� tempo medio di permanenza nel sistema


( ) α⋅ρ−ρ=α⋅= 111nw ss


� tempo medio di permanenza in attesa

( ) α⋅ρ−ρ=α⋅= 111nw ss

( ) α⋅ρ−ρ= 11w 2A





� K-mo percentile del numero di elementi nel sistema


( ) [ ] 100/krnPrFN =≤=


[ ] 1- K/100)/ln-ln(l=r

K/100-1=

K/100=-1

1+r

1+r

ρρ

ρ

( ) [ ] 100/krnPrFN =≤=


Per un casello autostradale con un solo posto di esazione si ha un tasso medio di arrivo 3 veicoli al minuto e un tasso medio di servizio di 6 veicoli al minuto: nell’ipotesi che gli arrivi costituiscano un processo di Poissone che i tempi di servizio siano distribuiti in modo esponenziale negativocalcolare:

Esempio


�il numero medio di elementi nel sistema ed in attesa

�il tempo medio di permanenza nel sistema ed in attesa

�la probabilità che ci siano 1,3,5 veicoli nel sistema

�la probabilità di attendere

�la probabilità di avere in attesa più di 1,2,3 veicoli

sw Awsn an

ESEMPIO Elementi di Teoria delle Code

E’ possibile calcolare:

�numero medio di elementi nel sistema


arrivi alla Poisson e tempi di servizio esponenzialiEsempio (1/4)


�numero medio di elementi in attesa

( )ρ−ρ=

1ns ( ) .veic 1

5.015.0

ns =−

=

( )ρ−ρ=

1n

2A ( ) veic.5.0

5.015.0

n2

A =−

=



�tempo medio di permanenza nel sistema ρ 1

sw

15.0



ESEMPIO


�tempo medio di permanenza in attesa

α⋅

ρ−ρ= 1

1ws min33.0

31

5.015.0

ws =⋅−

=

α⋅

ρ−ρ= 1

1w

2

A min 166.031

5.015.0

w2

A =⋅−

=

Aw



� Probabilità che ci siano n elementi nel sisteman 1



ESEMPIO


funzione di distribuzione FNs dei numero di elementi nel sistema

( ) [ ] 1rsN 1rnPrF

s+ρ−=≤=

nn )1(P ρ⋅ρ−= 25.05.0)5.01(P 1

1 =⋅−=0625.05.0)5.01(P 3

3 =⋅−=0156.05.0)5.01(P 5

5 =⋅−=



�probabilità di avere più di N utenti in attesa



ESEMPIO


�probabilità PA di attendere

= 1) > (n P = P 2sA ρ 0.25 0.5= P 2

A =

2+NsA =1)+N > P(n = N)>P(n ρ 125.00.5 = 1)>P(n 2+1

A =0625.00.5 = 2)>P(n 2+2

A =031.00.5 = 3)>P(n 2+3

A =


Modifiche ai sistemi di coda

� Modifiche al meccanismo degli arrivi

� Modifiche al meccanismo di servizio

� Modifica alla disciplina della coda

APPLICAZIONI


� Modifica alla disciplina della coda


Modifiche ai sistemi di coda Meccanismi di arrivo� riduzione del tasso medio degli arrivi

(ad es. escludendo alcune categorie di utenti)

� controllo dei tempi di arrivo con un sistema ad appuntamento

APPLICAZIONI


� modifica al tasso di arrivo cercando di ottenere un flusso più regolare( ad. es. cercando di appiattire i fenomeni di punta)

� incoraggiare o scoraggiare gli utenti a seconda della lunghezza della coda


Modifiche ai sistemi di coda Meccanismi di servizio

� diminuire il tempo media di servizio

� ridurre il coefficiente di variazione del tempo di servizio

� ridurre i tempi di servizio in maniera più sensibile nei periodi

APPLICAZIONI


� ridurre i tempi di servizio in maniera più sensibile nei periodi di punta

� aumentare la capacità del servizio quando si osserva una congestione elevata o quando ci si aspetta un numero di utenti maggiore del numero media


Modifiche ai sistemi di coda Disciplina della coda

� dare o togliere la priorità agli utenti più importanti

� dare priorità agli utenti con tempi di servizio più corti

APPLICAZIONI


� distribuire gli utenti alle varie code a seconda dei presunti tempi di servizio

� cambiare la disposizione di serventi


Modifiche ai sistemi di coda APPLICAZIONI


a = tempi di arrivo e di servizio costantib = arrivi costanti e tempi di servizio esponenzialic= arrivi casuali e tempi di servizio costantid = arrivi casuali e tempi di servizio esponenziali


( )[ ]( )ρ−

+ρ+ρ=α−

σ+α

+α=12

C1t12

ttn

2v

2

s

2s

22

sss

( )2s

2

ss

ttw s

σ+α

+=

= varianza di ts

= coeff. variazione

2sσ

vC

Sistemi ad unico canale arrivi alla Poisson e tempi di servizio qualsiasi


( )sss

t12tw s

α−+=


= 02sσ

Sistemi ad unico canale arrivi alla Poisson e tempi di servizio costanti

( ) ( )ρ−ρ+ρ=

α−

α+α=

12t12

ttn

2

s

22

ss s


( ) ( )ρ−αρ+=

ρ−ρ+=

12t

12t

tw2

ss

ss


SISTEMI REALI

��

impossibilità di ricavare formulazioni analitiche in forma chiusa,

Risultati della teoria delle code Limiti


impossibilità di ricavare formulazioni analitiche in forma chiusa,a meno di notevoli approssimazioni

��

SIMULAZIONE

Date post:	15-Feb-2019
Category:	Documents
Upload:	lamduong
View:	214 times
Download:	0 times

ELEMENTI DI TEORIA DELLE CODE - uniroma2.it · ed il numero di utenti che può essere servito...

Documents