3. Esercitazioni di Teoria delle code - Politecnico di...

Matematica III

5 Esercitazioni di teoria delle code

© Politecnico di Torino Pagina 1 di 33 Data ultima revisione 29/06/01 Autori: Roberto Tadei,Guido Perboli

Politecnico di Torino CeTeM

3. Esercitazioni di Teoria delle code

Matematica III




Previsione degli effetti di una decisione

• Si individuano due tipologie di problemi: • statici: il problema non varia nel breve periodo • dinamici: il problema varia

• Come si procede? • Si analizzano tempi e modalità di attesa degli

utenti in diverse code. • Si cerca la correlazione tra il numero di arrivi e il

numero di servizi. • Se i problemi sono semplificabili si risolvono per

via analitica, altrimenti si procede alla simulazione.

Matematica III




Ottimizzazione del sistema di servizio

• Ottimizzare un sistema di servizio significa: minimizzare la somma dei costi dovuti all’attesa dell’utenza e dei costi dovuti all’attivazione del servizio.

Matematica III




Andamenti qualitativi dei costi di un sistema di servizio

Costo medio di attesa

Efficienza del servizio

Costo medio del servizio


Costo fisso

Costo medio


Somma dei costi

Il costo fisso è dovuto all’esistenza

del servizio

Ottimizzare è posizionarsi sul

minimo

Matematica III




tempo di interarrivo

tempo di servizio

numero di server capacità del sistema di servizio

cardinalità della popolazione da cui provengono gli arrivi

disciplina della coda

u/v/w/x/y/z

Notazione di Kendall

Matematica III




Notazioni

• πn(t) : probabilità che ci siano n utenti nel sistema di servizio all’istante t

• : funzione generatrice di probabi- lità di πn(t) • : valore medio del numero di

utenti presenti nel sistema di servizio

( ) ( )∑∞

=

−=Π0

,n

nn ztzt π

( ) ( )1

,

=

Π−=

zdzztd

tN

Matematica III




Notazioni (cont .) • λ(t) : frequenza di inter-arrivo • µ(t) : frequenza di servizio • L(t) = N(t) - ρ(t) : lunghezza media della coda ove

� è il fattore di utilizzo

( ) ( )( )tt

tµλ

ρ =

Matematica III




Risultato di Little

In un sistema di servizio stazionario valgono le seguenti relazioni:

N(t) = ∆Tt(t)λ(t)

L(t) = ∆Tc(t)λ(t) ove

∆Tt(t) : valore atteso del tempo speso da un utente nel sistema di servizio

∆Tc(t) : valore atteso del tempo speso da un utente in coda

Matematica III




M/M/1 • Legge degli arrivi e dei servizi di tipo poissoniano • Supponiamo λx=λ e µx=µ, costanti. • Condizione di ergodicità:

� ρ = λ\µ < 1

• Probabilità di avere x utenti nel sistema: � πx = ρx(1−ρ)

• Probabilità di non avere attesa: � π0 = 1−ρ

Matematica III




M/M/1 (continua)

• Probabilità di avere almeno h utenti nel sistema: • All’equilibrio :

h

hi

ih ρρρπ =−=≥ ∑∞

=

)1()(

ρρ

µρµ

ρρ

ρρ

−=∆

−=∆

−=

−=

11

111

11

2

ct TT

LN

Matematica III




Esercizio proposto

• Ad un autolavaggio arrivano 8 clienti all’ora, con distribuzione di Poisson. L’autolavaggio può servire 12 clienti all’ora e la coda è di tipo M/M/1.

• I dati precedenti corrispondono a: λ=8 ; µ=12 ; λ\µ < 1

• Si possono determinare tutti i parametri presentati in precedenza, semplicemente applicando le definizioni.

Matematica III




M/M/1 con scoraggiamento degli arrivi

• Ad un casello autostradale non si può sfuggire alla coda, ma ad un autolavaggio sì . Per rappresentare questa possibilità di scelta: µx = µ (i servizi non sono influenzati dalla coda)

utilizzo di fattore : 1

,1 0

µρ

λλ

a

x

e

ax

a

−=

=+

=

Matematica III




M/M/1 con scoraggiamento degli arrivi (continua)

• La funzione di ergodicità cambia. Se anche λ>µ,lo scoraggiamento degli arrivi limita la lunghezza della coda. • Condizione di ergodicità:

• Parametri del sistema di servizio:

0≠µa

λµλ

σµ

µπ µµ

ctctN

aax

x

TTTN

Ta

N

exea

x

∆−∆=∆=∆==

=

=

−−

=L , 1

, ,

, !

1

2

0

Matematica III




M/M/1/k :sistema di servizio con capacità k

Sia inoltre :

( )

( ) x costante

se 0

se costante

∀=

≥<

=

µµ

λ

x

x kx

kxa

µρ

a=

Matematica III




M/M/1/k :sistema di servizio con capacità k

Le probabilità di equilibrio sono date da: • πk rappresenta la probabilità di equilibrio per un

utente di trovare la coda piena ed è detta fattore di perdita nello stato di equilibrio.

( )

k> x 0

k x1

1

1

1

1

10

=

≤−−

=

−−

=

+

+

x

k

x

x

k

π

ρρρ

π

ρρ

π

Matematica III




M/M/ns

• Il sistema è dotato di ns canali di distribuzione del servizio.

• La capacità del sistema è illimitata. • Tutti i canali si considerano uguali

ergodicità di condizione 1

se

se

→<=∧

>≤

=

=

bn

nxbn

nxxb

s

ss

sx

x

λρ

µ

λλ

Matematica III




Esercizio 1

• Calcolare il tempo medio di attesa in coda per una scala mobile dati: • massima portata: 2 passeggeri/gradino • velocità scala: 1 gradino/sec • numero medio di arrivi: 100/min • arrivi poissoniani

• Il problema è modellizzabile M/D/1 (D: la velocità della scala è costante)

Matematica III




Soluzione dell’esercizio 1 • Il tempo medio di attesa è: • Si conosce: λ=100 passeggeri/minuto • Si calcola: µ=120 passeggeri/minuto • Da cui:

−

=∆

µλ

µ 12

1cT

sec5,1min025,0 ==∆ cT

Matematica III




Esercizio 2

• Si determini il numero di caselli necessari ad un’uscita autostradale per avere un numero medio di utenti minore di 5. Il sistema è caratterizzato da: • traffico medio di utenti in uscita distribuito

uniformemente e pari a 8500 veicoli (supposto distribuito uniformemente dalle 7 alle 20)

• la percentuale di utenti viacard è del 50% • il numero medio di servizi/ora ai caselli normali è

120, ai caselli viacard è 600 • Si usi un modello M/M/ns

Matematica III




Soluzione dell’esercizio 2 • Si individuano 2 sistemi separati:

• caselli viacard • caselli normali

• Caselli viacard • I veicoli in una giornata sono 4250. Per cui

λ=4250/13 veicoli/ora = 326,9 veicoli/ora • E’ noto µ=600 veicoli/ora � ρ=λ/µ=0.545 ipotizzando ns=1 • Si può verificare che N<5: N=ρ/(1−ρ)=1.2 veicoli

Matematica III




Soluzione dell’esercizio 2 (continua)

• Caselli normali • Si ha: λ=326,9 veicoli/ora e µ=120 veicoli/ora • Ovviamente 1 o 2 canali non sono sufficienti.

Servono almeno tre canali. • Con 3 canali si ottiene N=9 che non soddisfa le

specifiche. • Si prova con quattro canali ottenendo un valore

minore di 5.

Matematica III




Esercizio 3

• Si ha un sistema caratterizzato da: � λ=12/8 veicoli/ora=1,5 veicoli/ora � µ=1/30 veicoli/minuto=2 veicoli/ora

• Utilizzando un modello M/M/1 si calcoli la lunghezza

media della coda ed il tempo medio di attesa del servizio.

• Con un modello M/M/1;k=4 la probabilità di perdita

del cliente successivo.

Matematica III




Soluzione dell’esercizio 3 • M/M/1 • M/M/1;k

104,01

)1(41

==−−

=+

πρ

ρρπ

k

k

k

oreñ)ì(tÄT

L

211

veicoli 25.21

75,0

2

=−

=

=−

=

==

ρρ

µλ

ρ

Matematica III




Esercizio 4 • Si consideri un sistema di servizio caratterizzato da:

• tempo di inter-arrivo esponenzialmente distribuito e con valore atteso pari a 1/λn , con n=numero di utenti nel sistema di servizio

• tempo di servizio esponenzialmente distribuito con valore atteso pari a 1/µn

• Siano poi:

11

)2( )2.4

)2( )1.4

+=−+−+

==

+=

iai

aai

ib

ai

i

i

i

i

µ

λµλ

Matematica III




Esercizio 4 (continua)

• Si calcolino: • le probabilità di equilibrio e la condizione di

ergodicità sotto la quale queste probabilità esistono e sono univoche

• la relativa funzione generatrice delle probabilità di equilibrio

• il valore atteso per il numero di utenti nel sistema di servizio nello stato di equilibrio

• la probabilità di trovare non più di h utenti nello stato di equilibrio

Matematica III




Soluzione dell’esercizio 4.1

• Dato che λi e µi sono funzioni crescenti di i si può introdurre:

• Si possono quindi calcolare le probabilità:

ba

ii

i

ii =

++

==+

ρρµλ

ρ con , 1

2

1

∑∏

∏

∑∏∞

=

−

=

−

=

∞

=

−

=

+=

+=

1

1

0

1

0

1

1

0

0

1

,

1

1

h

h

jj

i

jj

i

h

h

jj ρ

ρπ

ρπ

Matematica III




Soluzione dell’esercizio 4.1 (continua)

• Tenendo conto che:

si possono ricavare le probabilità di equilibrio :

ii

jj i ρρ )1(

1

0

+=∏−

=

2

20

)1()1(

)1(

ρρπ

ρπ

−+=

−=i

i i

Matematica III




Soluzione dell’esercizio 4.1 (continua) • La funzione generatrice delle probabilità d’equilibrio

risulta: da cui il valore atteso N, per il numero di utenti nello

stato di equilibrio:

( ) ( )21

2

0

2

)1(

)1(11)(

−

∞

=

−

−−

=+−=Π ∑z

zizi

ii

ρρ

ρρ

ρρ

ρ−

=Π

−== 1

2)()(

1zdzzd

N

Matematica III





• La probabilità di avere meno di h utenti nel sistema vale:

( ) ( )21

0

2

0

)1()2(1

11)Pr(

++

==

+++−=

=−+==≤ ∑∑hh

h

n

nh

nn

hh

nhn

ρρ

ρρπ

Matematica III




Soluzione dell’esercizio 4.2

• Si può introdurre la seguente notazione: • Si possono quindi calcolare le probabilità:

( )( )( ) a

iii

i

ii =

−++−+

==+

ρρ

ρρµλ

ρ con , 12

2

1

∑∏

∏

∑∏∞

=

−

=

−

=

∞

=

−

=

+=

+=

1

1

0

1

0

1

1

0

0

1 ,

1

1

h

h

jj

i

jj

i

h

h

jj ρ

ρπ

ρπ

Matematica III




Soluzione dell’esercizio 4.2 (continua) • Tenendo conto che:

si possono ricavare le probabilità di equilibrio :

( )( ) ( )ρ

ρρρ

−+−+

=∏−

= 1!1

11

0 iiii

jj

( )!1!

11

0

+−=

−=+

ii

ii

i

ρρπ

ρπ

Matematica III





• La funzione generatrice delle probabilità d’equilibrio risulta:

da cui il valore atteso N, per il numero di utenti nello

stato di equilibrio:

( ) ( ) zezzii

z z

i

iii

+−=

+

−=Π−

∑∞

=

−+

1

1!1!

)(0

1ρρρ

0)(

)(1

=Π

−==zdz

zdN ρ

Matematica III





• La probabilità di avere meno di h utenti nel sistema vale:

( ) ( )!11

!1!)Pr(

1

0

1

0 +−=

+

−==≤+

=

+

=∑∑ hnn

hnhh

n

nnh

nn

ρρρπ

3. Esercitazioni di Teoria delle code - Politecnico di...

Documents

Transcript of 3. Esercitazioni di Teoria delle code - Politecnico di...