teoria delle code - Università degli studi di Genova

INDICE
Corso di Laurea Triennale in INGEGNERIA GESTIONALE
Anno Accademico 2012/13
MODELLI E METODI PER L’AUTOMAZIONE
IL SISTEMA CODA
Prof. Davide GIGLIO
★ Definizioni e proprietà generali
★ Indici di prestazione
★ Leggi fondamentali
★ Code deterministiche
CODE MARKOVIANE
TEORIA DELLE CODE
★ Coda M/M/1
★ Coda M/M/m
★ Coda M/M/∞
★ Coda M/M/1/K
CODE NON MARKOVIANE
TEORIA DELLE CODE
MODELLI E METODI
PER L’AUTOMAZIONE
1
TEORIA DELLE CODE
LA TEORIA DELLE CODE
MODELLI E METODI
PER L’AUTOMAZIONE
2
IL SISTEMA CODA
★ La teoria delle code si propone di sviluppare modelli per lo studio dei
fenomeni di attesa che si possono manifestare in presenza di una
domanda di servizio
★ Dal punto di vista fisico, un sistema coda (o, semplicemente, coda) è un
sistema costituito da uno o più servitori (identici), capaci di fornire un
servizio, e da una fila di attesa capace di accogliere i clienti che non
possono essere serviti immediatamente
★ Quando la domanda stessa e/o la capacità di erogazione del servizio
sono soggetti ad aleatorietà, si possono infatti verificare situazioni
temporanee in cui chi fornisce il servizio non ha la possibilità di soddisfare
immediatamente le richieste
ARRIVI
PARTENZE
FILA DI
ATTESA
★ La teoria delle code trova applicazione nei
• sistemi di produzione
• sistemi di elaborazione
• sistemi di comunicazione / trasmissione dati
• sistemi di trasporto
• ...
SERVITORE
RAPPRESENTAZIONE SCHEMATICA DI UN SISTEMA CODA
★ I clienti si assumono tutti appartenenti alla stessa classe. I clienti che si
trovano in coda vengono serviti in accordo a determinate discipline di
servizio. Si assume che ogni cliente lasci immediatamente la coda dopo
che il suo servizio è stato completato
★ Dal punto di vista dinamico, una coda è costituita essenzialmente da due
processi: il processo di arrivo dei clienti e il processo di servizio
TEORIA DELLE CODE
MODELLI E METODI
PER L’AUTOMAZIONE
3
TEORIA DELLE CODE
MODELLI E METODI
PER L’AUTOMAZIONE
4
IL SISTEMA CODA
IL SISTEMA CODA
★ Il processo degli arrivi, che descrive il modo secondo cui i clienti si
presentano, è in generale un processo stocastico. Esso è definito in
termini della distribuzione dell’intertempo di arrivo, cioè dell’intervallo
di tempo che intercorre tra l’arrivo di due clienti successivi
★ Un sistema coda è caratterizzato da
➡ una statistica del processo degli arrivi
➡ una statistica del processo dei servizi
➡ il numero di servitori
★ Il processo dei servizi descrive il modo secondo cui ciascun servitore
eroga il servizio; in particolare definisce la durata dello stesso ed è di
solito un processo stocastico. Esso è definito in termini delle
distribuzioni dei tempi di servizio dei diversi servitori
➡ la dimensione del buffer in cui risiedono i clienti in attesa
➡ la popolazione complessiva dei clienti
➡ la disciplina (politica) di servizio
NUMERO DEI SERVITORI
DIMENSIONE DEL BUFFER
A/B/m/K/H
STATISTICA DEGLI ARRIVI
★ Per ottenere modelli analiticamente trattabili di solito si assume che sia il
processo degli arrivi che il processo dei servizi siano processi stazionari,
ovvero che le loro proprietà statistiche non varino nel tempo (tale
ipotesi in certi ambiti può essere molto limitativa)
★ Il processo dei servizi è alimentato dal processo degli arrivi e pertanto
quest’ultimo condiziona il primo (un cliente può essere servito solo se è
già arrivato, non può esistere una coda negativa). Dal punto di vista
statistico, il processo degli arrivi e il processo dei servizi saranno
considerati indipendenti
POPOLAZIONE COMPLESSIVA
STATISTICA DEI SERVIZI
NOTAZIONE DI KENDALL
TEORIA DELLE CODE
MODELLI E METODI
PER L’AUTOMAZIONE
5
TEORIA DELLE CODE
IL SISTEMA CODA
MODELLI E METODI
PER L’AUTOMAZIONE
6
IL SISTEMA CODA
★ I servitori sono in numero noto e costante, fissato a livello di progetto.
Usualmente essi hanno caratteristiche identiche e possono sempre
lavorare in parallelo. I servitori non possono mai rimanere inattivi in
presenza di clienti in coda
★ La popolazione è l’insieme dei potenziali clienti, ovvero l’insieme da cui
arrivano i clienti e a cui tornano dopo essere stati serviti. Essa può
essere finita o infinita. Nel primo caso le modalità di arrivo dei clienti
dipendono dal numero di clienti correntemente nel sistema
• Una tipica situazione in cui si può ritenere che i clienti provengano da una
popolazione finita è quando essi devono presentarsi forniti di (o contenuti in)
determinate strutture disponibili in numero limitato. Ad esempio, in ambiente
manifatturiero, spesso le parti per essere lavorate devono essere poste su
opportuni pallet
★ Anche se vi sono più servitori, in generale in una coda si assume
l’esistenza di un’unica fila di attesa (buffer) comune (quando ogni
servitore ha il suo buffer separato si preferisce pensare ad un insieme di
code; può essere comodo introdurre più buffer in presenza di clienti
provenienti da popolazioni diverse)
★ I clienti di una stessa popolazione sono tra loro indistinguibili. Di
conseguenza si suppone che i clienti provengano da popolazioni differenti
ogniqualvolta debbano essere distinti (ad esempio per priorità o per tipo
di servizio richiesto)
★ La dimensione del buffer può essere finita o infinita. Nel primo caso
essa limita di conseguenza la capacità del sistema, cioè il numero di
clienti in attesa nel buffer più quelli attualmente serviti. I clienti che
arrivano dopo che sia stata saturata tale capacità vengono respinti
• Un classico esempio di sistema a capacità limitata è quello di un centralino
telefonico che può tenere in attesa solo un numero finito di chiamate. In assenza di
centralino la dimensione della coda è addirittura zero, di conseguenza una
chiamata o è servita immediatamente oppure è rifiutata
TEORIA DELLE CODE
MODELLI E METODI
PER L’AUTOMAZIONE
7
TEORIA DELLE CODE
MODELLI E METODI
PER L’AUTOMAZIONE
8
IL SISTEMA CODA
LA NOTAZIONE DI KENDALL
★ La disciplina di servizio specifica quale sarà il prossimo cliente fra
quelli in attesa al momento in cui si libera un servitore.
NUMERO DEI SERVITORI
★ Le discipline di servizio usualmente considerate, in quanto molto comuni
nella realtà e inoltre matematicamente trattabili, sono:
DIMENSIONE DEL BUFFER
A/B/m/K/H
• servizio in ordine di arrivo
STATISTICA DEGLI ARRIVI
FCFS (First Come First Served) o FIFO (First In First Out)
• servizio in ordine inverso di arrivo
POPOLAZIONE COMPLESSIVA
STATISTICA DEI SERVIZI
★ La notazione di Kendall specifica in maniera sintetica gli aspetti che
caratterizzano un sistema coda
LCFS (Last Come First Served) o LIFO (Last In First Out)
• servizio in ordine casuale
SIRO (Service In Random Order)
★ In genere, in questa notazione, non viene indicata la disciplina (politica)
di servizio che si suppone essere FIFO
★ Quando K e H non sono specificati si sottintende che hanno valore infinito
TEORIA DELLE CODE
MODELLI E METODI
PER L’AUTOMAZIONE
9
TEORIA DELLE CODE
LA NOTAZIONE DI KENDALL
MODELLI E METODI
PER L’AUTOMAZIONE
10
INDICI DI PRESTAZIONE
★ Per quanto riguarda la statistica degli arrivi e la statistica dei servizi si
utilizzano le seguenti sigle
M
Markovian (distribuzione esponenziale)
D
Deterministic (distribuzione costante)
N
Normal (distribuzione normale, Gaussiana)
Ek
Erlangian (distribuzione di Erlang di ordine k)
G
General (distribuzione generica)
GI
General Independent (distribuzione generica di eventi indipendenti)
★ La teoria delle code consente di determinare proprietà statistiche di
alcune grandezze di interesse. A tale proposito si consideri la seguente
notazione
Lq (t) Lunghezza della coda all’istante di tempo t (numero di clienti
presenti nel sistema all’istante t , siano essi in servizio o in attesa)
Lw (t) Numero di clienti in attesa all’istante t (equivale a Lq (t) meno il
numero di clienti in servizio all’istante t )
★ La statistica M è caratterizzata da un tempo di interarrivo o un tempo di
servizio con distribuzione esponenziale (“code Markoviane”)
★ M, D, N e Ek saranno intese come distribuzioni di sequenze di variabili
aleatorie indipendenti e identicamente distribuite (“v.a. i.i.d.”)
Tq,i
Tempo complessivo di permanenza nel sistema (tempo di
attesa + tempo di servizio) dell’ i -esimo cliente (arrivato nel sistema)
Tw,i
Tempo di attesa dell’ i -esimo cliente
Ts,i
Tempo di servizio dell’ i -esimo cliente
ai
Istante di arrivo dell’ i -esimo cliente
di
Istante di partenza (dal sistema) dell’ i -esimo cliente
★ G e GI sono relative a pdf su cui non si fa alcuna assunzione
TEORIA DELLE CODE
MODELLI E METODI
PER L’AUTOMAZIONE
11
TEORIA DELLE CODE
MODELLI E METODI
PER L’AUTOMAZIONE
12
INDICI DI PRESTAZIONE
INDICI DI PRESTAZIONE
★ L’obiettivo è determinare, se possibile, attraverso le precedenti
grandezze, i seguenti valori medi
Lq
Lw
Numero medio di clienti nel sistema (sia in
attesa di servizio che riceventi servizio)
Numero medio di clienti in attesa (ovvero
lunghezza media della fila di attesa)
Lq = E[Lq (t)]
★ I valori che sono assunti dagli indici di prestazione precedentemente
elencati dipendono ovviamente dalla struttura della coda (dimensione del
buffer, numero di servitori, tempo medio di servizio, ecc.) e dal tasso di
arrivo dei clienti
Lw = E[Lw (t)]
★ Generalmente si suppone che ogni cliente lasci immediatamente la
coda una volta che il suo servizio è stato completato
Tq
Tempo medio di permanenza dei clienti (sia in
attesa di servizio che riceventi servizio) nel sistema
T q = E[Tq,i ]
Tw
Tempo di attesa medio dei clienti (nella fila di
attesa) prima di essere serviti
T w = E[Tw,i ]
★ Inoltre si suppone che, qualunque sia la statistica usata per la gestione
del sequenziamento del servizio dei clienti in coda, non vi possano mai
essere servitori inattivi e contemporaneamente clienti in attesa
★ Nel caso in cui nel sistema cosa vi siano più servitori, si supporrà che le
politiche di servizio non privilegino alcuno dei servitori
★ Altri indici di prestazione
⇢
Coefficiente di utilizzazione dei servitori (rapporto tra tempo
pn
Probabilità che vi siano a regime n clienti nel sistema
impiegato in servizio e tempo disponibile complessivo)
TEORIA DELLE CODE
MODELLI E METODI
PER L’AUTOMAZIONE
13
TEORIA DELLE CODE
MODELLI E METODI
PER L’AUTOMAZIONE
INDICI DI PRESTAZIONE
INDICI DI PRESTAZIONE
★ Due ovvie relazioni sono
★ Ponendo
Tq,i = Tw,i + Ts,i
Tq,i = di
=
ai
★ Per un sistema a coda con m servitori in parallelo, si definisce
coefficiente di carico ⇢c il rapporto
⇢c =
essendo
14
µ=
1
E[Ta ]
1
E[Ts ]
Frequenza degli arrivi
Frequenza massima di servizio
E[Ts ]
E[Ta ] · m
la precedente relazione diventa
Ts
Variabile aleatoria “tempo di servizio dei clienti”
Ta
Variabile aleatoria “tempo di interarrivo dei clienti”
⇢c =
µ·m
★ Per sistemi con buffer illimitati (in cui quindi i clienti che arrivano non
possono mai essere rifiutati), condizione sufficiente di stabilità è che sia
0  ⇢c < 1
( ⇢c > 1 è condizione sufficiente di instabilità)
TEORIA DELLE CODE
MODELLI E METODI
PER L’AUTOMAZIONE
15
TEORIA DELLE CODE
MODELLI E METODI
PER L’AUTOMAZIONE
16
INDICI DI PRESTAZIONE
INDICI DI PRESTAZIONE
★ Sia ⇡
˜ 0 la probabilità che un generico servitore sia inattivo in un certo
istante selezionato a caso, in condizioni di equilibrio stocastico
★ Qualunque sia il sistema fisico considerato, le problematiche di interesse
generalmente riguardano i costi (o i profitti) coinvolti
(tale probabilità non dipende dal servitore in quanto si è assunto che le politiche di
servizio non privilegiano alcun servitore)
★ I costi sono di solito suddivisi tra costi variabili, funzione di almeno una
delle grandezze che caratterizzano la dinamica del sistema, e costi fissi,
indipendenti dalla dinamica osservata e generalmente funzione della sola
struttura fisica del sistema
★ Il coefficiente di utilizzazione del generico servitore è definito come
⇢=1
⇡
˜0
★ In un sistema coda i costi variabili sono generalmente legati al tempo
di attesa dei clienti mentre i costi fissi sono generalmente legati al
numero di servitori disponibili
★ Il throughput del generico servitore (numero medio di clienti che escono
˜0 ) · µ
dal servitore nell’unità di tempo) è (1 ⇡
★ Il throughput complessivo del sistema è pertanto (1
★ I clienti ritengono fondamentale la riduzione dei tempi di attesa
⇡
˜0 ) · µ · m
★ Il gestore del sistema è perlopiù interessato al massimo sfruttamento
delle risorse (servitori) pur cercando di rispettare le esigenze dei clienti
★ Poiché si assume che il sistema si trovi in condizioni di equilibrio
˜ 0 ) · µ · m e quindi
stocastico si ha = (1 ⇡
⇢=
µ·m
(il coefficiente di utilizzazione corrisponde pertanto
al coefficiente di carico precedentemente definito)
TEORIA DELLE CODE
MODELLI E METODI
PER L’AUTOMAZIONE
17
TEORIA DELLE CODE
LEGGI FONDAMENTALI
18
LEGGI FONDAMENTALI
LEGGE DI LITTLE
Per code del tutto generali possono essere forniti solo pochi risultati
★ Si riferisce a sistemi coda con un generico numero di servitori, in
condizioni di equilibrio stocastico
LEGGE DI LINDLEY
★ La legge di Little, che riguarda il comportamento a regime, definisce un
legame tra il numero medio di clienti presenti nel sistema, tempo medio
di permanenza nel sistema e frequenza degli arrivi. Tale legame è
★ In un sistema coda con un solo servitore e disciplina di servizio FIFO,
si ha
di = max{ai , di
1}
+ Ts,i
Lq =
★ La legge di Lindley riguarda solo il comportamento nel transitorio
TEORIA DELLE CODE
MODELLI E METODI
PER L’AUTOMAZIONE
MODELLI E METODI
PER L’AUTOMAZIONE
Tq
★ La legge di Little è del tutto generale e non prevede, quindi, ipotesi in
relazione alle statistiche dei processi degli arrivi e dei servizi, il numero di
servitori, la politica di servizio, ecc.
19
TEORIA DELLE CODE
MODELLI E METODI
PER L’AUTOMAZIONE
20
LEGGI FONDAMENTALI
LEGGI FONDAMENTALI
LEGGE DI LITTLE
★ Sulla base delle precedenti relazioni e sulla base della legge di Little si ha
★ L’importanza della legge di Little risiede nel fatto che essa vale per
qualsiasi sistema (in equilibrio stocastico) in cui possa essere identificato
un processo di arrivi (di clienti) e possa essere chiaramente individuato un
sistema, distinto da quanto si trova all’esterno
Lq
Tq = Tw + Ts
=
Lw
+
1
µ
e quindi
Lq = Lw +
SISTEMA
µ
Lq = Lw + m ⇢
(si noti che in condizioni di equilibrio in media devono uscire dal sistema tanti clienti
quanti entrano, altrimenti non si ha equilibrio)
★ Si ha pertanto anche
Lw =
Tw
TEORIA DELLE CODE
MODELLI E METODI
PER L’AUTOMAZIONE
21
TEORIA DELLE CODE
CODE DETERMINISTICHE D/D/1
MODELLI E METODI
PER L’AUTOMAZIONE
CODE MARKOVIANE
★ Nelle code deterministiche gli istanti di arrivo dei clienti e i tempi di
espletamento dei servizi richiesti sono noti a priori senza incertezza
★ Una coda markoviana è un sistema coda in cui il processo degli arrivi e
il processo dei servizi sono processi di Poisson
★ In questo caso si possono facilmente determinare le prestazioni del
sistema.
★ Ta e Ts sono quindi variabili aleatorie distribuite in modo esponenziale
★ Un sistema coda di questo tipo corrisponde ad una catena di Markov a
tempo continuo (CTMC) per cui è (potenzialmente) possibile determinare
la distribuzione di probabilità a regime dello stato
★ Se infatti la disciplina di servizio è FIFO, noti con esattezza i valori ai e
Ts,i si possono calcolare attraverso la legge di Lindley gli istanti di
uscita dei clienti dal sistema (ipotizzando d0 = 0 )
★ Inoltre Tw,i = di
ai
22
Ts,i
★ Quindi, per calcolare il numero di clienti nel sistema all’istante t , basta
contare il numero di clienti i per cui ai  t < di
(si considera che un cliente è già nel sistema nell’istante in cui entra mentre non è più
nel sistema nell’istante in cui esce)
★ Il caso totalmente deterministico è però difficile che avvenga nella
realtà. In genere gli arrivi dei clienti e la durata dei servizi sono affetti da
incertezza e sono pertanto modellati come processi stocastici
TEORIA DELLE CODE
MODELLI E METODI
PER L’AUTOMAZIONE
23
TEORIA DELLE CODE
MODELLI E METODI
PER L’AUTOMAZIONE
24
CODA M/M/1
CODA M/M/1
★ E’ la coda markoviana più semplice
★ Sulla base di quanto visto in relazione al processo birth-death a tempo
continuo, si può affermare che, avendo supposto ⇢ < 1 , esiste una
distribuzione di probabilità a regime dello stato
★ Tale tipologia di sistema coda può essere modellata come un processo
birth-death a tempo continuo (CTMC-BD) in cui
•
n
=
Dal punto di vista del sistema coda, esiste un regime se e solo se in media il sistema
ha la potenzialità di servire i clienti più velocemente di quanto essi arrivino (altrimenti
la lunghezza della coda è destinata ad aumentare indefinitamente e quindi non si
raggiunge mai uno stato stazionario)
, n = 0, 1, 2, . . .
• µn = µ , n = 1, 2, 3, . . .
dove e µ sono rispettivamente il tasso medio di interarrivo e il tasso
medio di servizio che caratterizzano il sistema coda
★ Dai risultati ottenuti per il processo birth-death a tempo continuo si ha
L’arrivo di un nuovo cliente in coda può essere infatti interpretato come una nascita;
viceversa la fine di un servizio, quindi l’uscita di un cliente dal sistema, può essere
interpretato come una morte
⇡0 =
1+
★ Si assume che la coda sia “stabile” ovvero
⇢=
µ
1
1 ✓ ◆n =
X
1+
⇡0 = ⇢n ⇡0
,n
⇡n =
<1
TEORIA DELLE CODE
MODELLI E METODI
PER L’AUTOMAZIONE
25
✓ ◆n
µ
1
X
n=1
⇡0 =
1+
MODELLI E METODI
PER L’AUTOMAZIONE
=1
1
⇢
n
1
X
n⇡n =
n=0
⇢
⇢
⇡n = ⇢ ⇡0 = ⇢ (1
n
⇢)
,n
1
1
X
n⇢n (1
⇢) = (1
1
X
n⇢n converge al valore
Lq = (1
⇢)
1
X
n⇢n
n=0
n=0
⇢
(1
⇢)2
=
⇢
1
⇢
⇢
(1
=
⇢)2
e quindi
µ
★ Dalla legge di Little si può calcolare il tempo medio di permanenza nel
sistema
fila di attesa – e tempo medio di permanenza – nel sistema e nella fila di attesa)
Tq =
MODELLI E METODI
PER L’AUTOMAZIONE
⇢)
n=0
★ Con ⇢ < 1 , la serie
★ Sulla base di queste probabilità a regime dello stato è possibile calcolare
gli indici di prestazione di interesse (numero medio di clienti – nel sistema e nella
TEORIA DELLE CODE
26
★ Per quanto riguarda il numero medio di clienti nel sistema (o lunghezza
media della coda)
⇢
1
Lq =
⇢
1
CODA M/M/1
⇢n converge al valore
1
⇢n
n=1
TEORIA DELLE CODE
CODA M/M/1
★ Poiché ⇢ < 1 , la serie
µ
n=1
1
1
X
27
TEORIA DELLE CODE
Lq
=
1
µ
1
⇢
=
1
µ(1
⇢)
=
1
µ
MODELLI E METODI
PER L’AUTOMAZIONE
28
CODA M/M/1
CODA M/M/1
★ Inoltre
Tw = Tq
Ts =
1
µ
1
µ
=
)
µ(µ
=
★ Riassumendo, per quanto riguarda la coda M/M/1, gli indici di prestazione
di interesse assumono i seguenti valori
⇢
µ(1
⇢)
Lq
★ Sempre dalla legge di Little si può calcolare il tempo medio di
permanenza nella fila di attesa
Lw =
Tw =
2
µ(µ
)
=
Lw
⇢2
1
⇢
Tq
⇢
1
⇢
µ
2
⇢2
1
⇢
1
µ(1
)
µ(µ
1
⇢)
µ
⇢)
µ(µ
⇢
Tw
TEORIA DELLE CODE
MODELLI E METODI
PER L’AUTOMAZIONE
29
IL COEFFICIENTE DI UTILIZZAZIONE
µ(1
)
TEORIA DELLE CODE
MODELLI E METODI
PER L’AUTOMAZIONE
30
IL COEFFICIENTE DI UTILIZZAZIONE
★ Per assicurare la stabilità del sistema ci deve essere una probabilità
⇡0 = 1 ⇢ non nulla che il servitore sia inattivo
★ Un incremento di ⇢ non introduce però solo svantaggi
• Se ⇢ aumenta a causa di un maggiore arrivo di clienti, si ha come
conseguenza una maggiore utilizzazione delle risorse disponibili
★ Al crescere di ⇢ aumenta l’occupazione del servitore e quindi la
permanenza media e il numero medio di clienti nel sistema, nonché la
permanenza media e il numero medio di clienti nella fila di attesa
• Se l’aumento di ⇢ è dovuto all’utilizzo di servitori meno veloci,
dovrebbero diminuire i costi di acquisizione degli stessi
★ Nella fase di progettazione di un sistema è quindi necessario fissare ⇢ in
modo da avere un giusto compromesso tra costi, prestazioni (qualità) e
utilizzazione delle risorse
Tq
★ Inoltre, fissato ⇢ , si può dimensionare (sempre in fase di progetto) il
flusso
in modo da avere un tempo di attesa medio in un range
assegnato
Tempo medio di permanenza nel
sistema in funzione del coefficiente
di utilizzazione della macchina
★ Un altro fattore molto importante che è influenzato da ⇢ è il tempo di
raggiungimento del regime
1/µ
⇢
1
TEORIA DELLE CODE
MODELLI E METODI
PER L’AUTOMAZIONE
31
TEORIA DELLE CODE
MODELLI E METODI
PER L’AUTOMAZIONE
32
IL COEFFICIENTE DI UTILIZZAZIONE
CODA M/M/m
★ Il tempo di raggiungimento del regime è il tempo dopo il quale le
statistiche che descrivono il comportamento medio del sistema non
variano più in modo significativo e quindi il processo che descrive la
dinamica della coda può essere ritenuto praticamente stazionario
★ E’ la coda markoviana in cui sono presenti m servitori in parallelo
★ Anche tale tipologia di sistema coda può essere modellata come un
processo birth-death a tempo continuo (CTMC-BD). In questo caso
però i rate di morte non sono indipendenti dallo stato
• con ⇢ = 0.7 il regime è raggiunto dopo meno di un migliaio di clienti
★ Considerando il tasso medio di interarrivo
servizio µ , si ha
• con ⇢ = 0.85 il regime è raggiunto dopo una decina di migliaia di clienti
• con ⇢ > 0.95 il regime è raggiunto dopo diversi milioni di clienti
•
★ E’ legittimo chiedersi se, in presenza di coefficienti di utilizzazione vicini
all’unità, i risultati ottenuti abbiano interesse pratico. Infatti pochi sistemi
mantengono caratteristiche costanti per tempi così lunghi, sia per quanto
riguarda l’arrivo dei clienti che il servizio agli stessi
n
=
• µn =
⇢
e il tasso medio di
, n = 0, 1, 2, . . .
nµ
mµ
se n = 1, 2, . . . , m
se n m
1
★ La dipendenza da n del death-rate µn si spiega con il fatto che più
elevato è il numero di servitori attivi, più elevato deve essere µn , fino
ad un valore di n pari a m
★ Da n = m in poi il numero di servitori attivi rimane costante e quindi
anche µn deve rimanere costante
TEORIA DELLE CODE
MODELLI E METODI
PER L’AUTOMAZIONE
33
TEORIA DELLE CODE
MODELLI E METODI
PER L’AUTOMAZIONE
CODA M/M/m
CODA M/M/m
★ Per quanto riguarda la stabilità della coda, in questo caso è necessario
ipotizzare
⇢=
mµ
★ Le probabilità a regime dello stato che si ottengono sono
<1
⇡0 = "
In questo caso infatti, facendo riferimento alla condizione per cui una CTMC-BD
ammette una distribuzione di probabilità a regime dello stato, esiste j tale che
j (basta prendere un qualunque j
m)
j /µj < 1 per ogni j
★ Sotto tale ipotesi è pertanto possibile determinare le probabilità a regime
dello stato, sfruttando i risultati ottenuti in relazione al processo birthdeath a tempo continuo
⇡n =
★ Si noti che ⇢ rappresenta il coefficiente di utilizzazione di ogni singolo
servitore presente nel sistema coda
TEORIA DELLE CODE
34
MODELLI E METODI
PER L’AUTOMAZIONE
1
1+
m
X1
(m⇢)
n=1
8
(m⇢)n
>
>
⇡
>
0
<
n!
n!
>
>
mm n
>
: ⇡0
⇢
m!
n
+
(m⇢)m
m!
·
1
1
⇢
se n = 1, 2, . . . , m
se n
#
1
m
★ Sulla base di queste probabilità a regime dello stato è possibile calcolare
gli indici di prestazione di interesse a partire dal numero medio di clienti
nel sistema
35
TEORIA DELLE CODE
MODELLI E METODI
PER L’AUTOMAZIONE
36
CODA M/M/m
CODA M/M/m
★ Il numero medio di clienti nel sistema è
Lq =
1
X
n⇡n = m⇢ +
n=0
(m⇢)m
m!
·
★ Nel caso specifico di due servitori (coda M/M/2) si hanno i seguenti indici
di prestazione
⇢
(1
⇢)2
· ⇡0
★ Dalla legge di Little si può calcolare il tempo medio di permanenza nel
sistema, che è
Tq =
Lq
=
1
µ
+
1
µ
·
(m⇢)m
m!
·
⇢)2
· ⇡0
2⇢(1
2⇢n (1
⇡n
TEORIA DELLE CODE
MODELLI E METODI
PER L’AUTOMAZIONE
n
2
⇢)
2 + 4⇢ + 3⇢2
6⇢(1
⇡n
n=1
⇡n
n=2
3
⇢)
2 + 4⇢ +
3⇢2
9⇢2 (1
⇢)
2 + 4⇢ + 3⇢2
9⇢n (1
⇡n
n
⇢)
⇢)
2 + 4⇢ + 3⇢2
TEORIA DELLE CODE
Lq
Lw
Tq
Tw
⇢2
1
⇢2 )
µ(1
⇢2
µ(1
TEORIA DELLE CODE
⇢2 )
MODELLI E METODI
PER L’AUTOMAZIONE
38
CODA M/M/m
★ Sia S la variabile aleatoria che indica il numero di servitori attivi
★ Nel caso specifico di tre servitori (coda M/M/3) si hanno i seguenti indici
di prestazione
2(1
1
1+⇢
CODA M/M/m
⇡0
Tq
Tw
37
2⇢3
Lw
⇢)
⇢2
1+⇢
n=1
★ Da questi due valori si possono determinare, come fatto nel caso di coda
M/M/1, gli indici di prestazione Lw e T w
⇢
1
1+⇢
⇡n
1
m(1
1
⇡0
2⇢
Lq
3⇢(2 + 2⇢
(1
★ Il numero medio di servitori attivi è pertanto
⇢2 )
E[S] =
⇢)(2 + 4⇢ + 3⇢2 )
che risulta essere, con opportuni calcoli
⇢)(2 + 4⇢ +
2 + 2⇢
µ(1
3⇢2 )
1
X
m⇡n
n=m
E[S] = m⇢ =
⇢2
µ
★ Tale valore esprime la cosiddetta “probabilità di blocco”, ovvero la
probabilità che un cliente, al momento del suo arrivo, trovi tutti i
servitori occupati
⇢)(2 + 4⇢ + 3⇢2 )
3⇢3
µ(1
n⇡n +
n=0
9⇢4
µ(1
m
X1
⇢)(2 + 4⇢ + 3⇢2 )
MODELLI E METODI
PER L’AUTOMAZIONE
39
TEORIA DELLE CODE
MODELLI E METODI
PER L’AUTOMAZIONE
40
CODA M/M/∞
CODA M/M/∞
★ Rappresenta il caso limite della coda M/M/m vista in precedenza
★ Ponendo
★ Serve a modellare una situazione in cui ogni cliente non deve mai
attendere nella fila di attesa (quindi T w = 0 e T q = T s )
★ La capacità della coda M/M/∞ è illimitata
•
n
=
= ⇢ (che però non ha più il significato fisico di coefficiente di
carico del sistema) si ottiene dalle equazioni viste per le
CTMC-BD
1
⇡0 =
★ Anche questa classe di sistema coda può essere modellata come un
processo birth-death a tempo continuo (CTMC-BD) in cui
µ
1+
+1
X
n=1
, n = 0, 1, 2, . . .
µ(2µ) . . . (nµ)
dove e µ sono come sempre il tasso medio di interarrivo e il tasso
medio di servizio che caratterizzano il sistema coda
MODELLI E METODI
PER L’AUTOMAZIONE
41
1
µ
⇡0 = e
⇢
⇡n = e
⇢
⇢n
,n
n!
⇡0 =
⇢n
n!
1
e⇢
=e
⇢
n!
⇡0
1
MODELLI E METODI
PER L’AUTOMAZIONE
Lq
42
µ
µ
Lw
★ Dalla legge di Little si ottiene il tempo medio di permanenza nel sistema
=
n
µn · n!
n=1
=
★ Riassumendo, per quanto riguarda la coda M/M/∞, si hanno i seguenti
indici di prestazione
★ Il valor medio di tale distribuzione corrisponde alla lunghezza media
della coda e quindi
Lq
⇡0 =
1+
⇢n
CODA M/M/∞
★ La distribuzione di probabilità a regime dello stato è pertanto una
distribuzione di Poisson
Tq =
n
µ(2µ) . . . (nµ)
TEORIA DELLE CODE
CODA M/M/∞
Lq = ⇢ =
µ
n!
1
+1
X
e quindi
★ In questo caso è evidente che, non essendoci permanenza dei clienti
nella fila di attesa, la coda è stabile qualunque siano i valori e µ
TEORIA DELLE CODE
1+
+1
X
✓ ◆n =
n=1
⇡n =
• µn = nµ , n = 1, 2, 3, . . .
1
=
n
= Ts
Tq
che mette in evidenza come il tempo medio di permanenza nel sistema
coda corrisponda al tempo medio di servizio (non essendoci attesa)
Tw
0
1
µ
0
★ Il modello M/M/∞ può servire a modellare situazioni in cui il servizio è
sostanzialmente un “ritardo puro” e non c’è nessuna linea di attesa
E’ il caso ad esempio del trasporto dei pezzi su un nastro trasportatore
TEORIA DELLE CODE
MODELLI E METODI
PER L’AUTOMAZIONE
43
TEORIA DELLE CODE
MODELLI E METODI
PER L’AUTOMAZIONE
44
CODA M/M/1/K
CODA M/M/1/K
★ Si tratta del caso più semplice di coda con buffer limitato
★ E’ possibile “riaccendere” semplicemente il processo degli arrivi grazie
alla proprietà memoryless che caratterizza la distribuzione esponenziale
di tale processo (processo che comprende sia l’arrivo dei clienti accettati
che l’arrivo dei clienti rigettati)
★ Si suppone che i clienti che arrivano quando il buffer è pieno siano
semplicemente persi
(ciò può essere modellato semplicemente imponendo che il processo degli arrivi si
“azzeri” quando il buffer è pieno e si “riaccende” non appena nel buffer si libera una
posizione)
★ Quando si “riaccende” il processo degli arrivi, ovvero quando un cliente
esce dal sistema liberando quindi una posizione nel sistema, qualunque
sia il tempo trascorso dall’ultimo arrivo (accettato o rigettato), il
tempo residuo che precede il prossimo arrivo ha sempre una
distribuzione esponenziale
★ Anche questa classe di sistema coda può essere modellata come un
processo birth-death a tempo continuo (CTMC-BD) in cui
⇢
0n<K
• n=
0 n
K
⇢
µ 1nK
• µn =
0 n>K
★ E’ evidente che lo stato del sistema è in questo caso finito
★ E’ banale quindi concludere che tutti gli stati sono ricorrenti positivi e
pertanto è possibile determinare la distribuzione di probabilità a regime
dello stato
in cui K è il numero massimo di clienti nel sistema coda (quindi la
dimensione del buffer è K 1 )
TEORIA DELLE CODE
★ La coda M/M/1/K è stabile per definizione (anche in presenza di rapporti
⇢ = /µ
1)
MODELLI E METODI
PER L’AUTOMAZIONE
45
TEORIA DELLE CODE
MODELLI E METODI
PER L’AUTOMAZIONE
CODA M/M/1/K
CODA M/M/1/K
★ Partendo dai risultati ottenuti per le CTMC-BD si ha
1
⇡0 =
1+
K
X
n=1
⇡n =
✓ ◆n =
µ
1
1+
µ
1
✓ ◆K ! =
µ
1
✓ ◆n
µ
1+
★ La coda media risulta in questo caso
1
⇢ 1
⇢
1
⇢
K
=
1
1
⇢
Lq =
⇢K+1
⇡n =
TEORIA DELLE CODE
>
:
1
1
0
⇢
⇢K+1
⇢n
n⇡n =
1
1
⇢
⇢K+1
K
X
n=0
n⇢n =
⇢
1
⇢K+1
"
1
⇢K
1
⇢
K⇢K
#
★ Per determinare T q si può utilizzare la legge di Little. Essa deve però
essere utilizzata tenendo conto del flusso effettivamente entrante nel
sistema (flusso efficace). Esso è
h
i
· Pr{L(t) < K} = 1 Pr{L(t) = K}
e↵ =
"
#
⇢K
1 ⇢K
=
1 (1 ⇢)
=
1 ⇢K+1
1 ⇢K+1
µ
e quindi
8
>
<
K
X
n=0
(solo se n  K in quanto è ovvio che
se n > K si ha sicuramente ⇡n = 0 )
⇡0 = ⇢n ⇡0
46
0nK
★ Il tempo medio di permanenza nel sistema è quindi
"
#
Lq
1
1 ⇢K
K
Tq =
K⇢
=
µ (1 ⇢K ) 1 ⇢
e↵
n>K
MODELLI E METODI
PER L’AUTOMAZIONE
47
TEORIA DELLE CODE
MODELLI E METODI
PER L’AUTOMAZIONE
48
CODA M/M/1/K
CODA M/M/1/K
★ Dai valori Lq e T q si possono determinare, nel modo consueto già visto
in precedenza, gli indici di prestazione Lw e T w
★ Riassumendo, per quanto riguarda la coda M/M/1/K, si hanno i seguenti
indici di prestazione
★ Essendo il sistema in condizioni di equilibrio stocastico, il throughput del
sistema è uguale a e↵
⇢
Lq
1
★ L’utilizzazione del server è
1
⇡0 =
1
1
⇢
⇢K+1
=⇢
1
1
Lw
⇢K
Tq
⇢)
⇢K
1
Tw
⇢K+1
TEORIA DELLE CODE
1
MODELLI E METODI
PER L’AUTOMAZIONE
49
1
1
µ (1
⇢K )
"
1
µ (1
⇢K
1
⇢ 1
⇢K+1
⇢K+1
★ La probabilità di blocco è
⇡K = (1
⇢
⇢K+1
"
"
"
⇢
K⇢
⇢K
1
⇢
1
⇢K
1
⇢
⇢ 1
⇢K )
K
K⇢K
K
K⇢
⇢K
1
#
#
K
K⇢
⇢
TEORIA DELLE CODE
CODE NON MARKOVIANE
#
#
MODELLI E METODI
PER L’AUTOMAZIONE
50
CODA M/G/1
★ Nei modelli non markoviani almeno uno tra l’intertempo di arrivo e il
tempo di servizio non è una variabile aleatoria distribuita in modo
esponenziale
★ La coda M/G/1 ha arrivi poissoniani (con frequenza ), ma tempi di
servizio qualunque, purché indipendenti e omogenei (cioè con la stessa
distribuzione di probabilità) e con media e varianza note
★ In generale, l’utilizzo di una variabile aleatoria distribuita in modo
esponenziale per quanto riguarda l’intertempo di arrivo è accettato nella
maggior parte dei casi. Pertanto si considererà la possibilità che sia il
tempo di servizio ad essere rappresentato da una variabile aleatoria
non esponenziale
µ=
1
E[Ts ]
2
⇥
= Var[Ts ] = E (Ts
★ La condizione di stazionarietà è sempre ⇢ =
µ
<1
E[Ts ])2
⇤
★ Per tale classe di coda, la formula di Khinchine-Pollaczek fornisce la
lunghezza media del buffer
★ In ogni caso, lo studio dei sistemi coda in cui non siano rispettate le
ipotesi di markovianità si presenta assai più complesso di quello nel
caso markoviano
Lw =
★ Ci limiteremo a presentare alcuni risultati in relazione alle code M/G/1,
M/D/1 e M/Ek/1
⇢2 (1 +
2(1
2
µ2 )
⇢)
da cui si possono calcolare, nel modo usuale, i tempi T w = Lw /
T q = T w + 1/µ e la lunghezza Lq = T q
e
★ Si osservi che Lw cresce con
e quindi un servitore “regolare” (ovvero
con bassa varianza del tempo di servizio) ha prestazioni migliori
TEORIA DELLE CODE
MODELLI E METODI
PER L’AUTOMAZIONE
51
TEORIA DELLE CODE
MODELLI E METODI
PER L’AUTOMAZIONE
52
CODA M/D/1
★ La coda M/D/1 ha arrivi poissoniani (con frequenza
servizio costante (uguale a µ )
CODA M/Ek/1
) e tempo di
★ E’ un caso particolare di coda M/G/1 con varianza nulla (
★ La coda M/Ek/1 è utilizzata per modellare casi intermedi in cui, oltre che
la media e la varianza, è nota anche la forma della distribuzione di
probabilità della variabile aleatoria tempo di servizio
= 0)
★ Ek indica che il tempo di servizio è una variabile aleatoria con
distribuzione di Erlang di ordine k
★ In questo caso, la formula di Khinchine-Pollaczek si riduce a
Lw =
⇢2
2(1
f (t) =
⇢)
(kµ)k tk
(k
1
e
kµt
1)!
,t
0
dove k è un intero positivo detto fattore di forma
★ Si osservi che il numero medio di clienti in attesa di servizio è per una
coda M/D/1 la metà che per una coda M/M/1
★ La distribuzione di Erlang di ordine k ha media
1
µ
e varianza
1
kµ2
★ Ek è quindi una variabile aleatoria non negativa che dipende da due
parametri: µ e k , dove il primo determina la media e il secondo
determina la varianza
TEORIA DELLE CODE
MODELLI E METODI
PER L’AUTOMAZIONE
53
TEORIA DELLE CODE
CODA M/Ek/1
MODELLI E METODI
PER L’AUTOMAZIONE
54
CODA M/Ek/1
★ Per k ! 1 la distribuzione di Erlang tende a diventare la distribuzione
normale
k
k
k
k
k
=
=
=
=
=
1
2
4
8
16
★ Un’importante proprietà che riguarda la distribuzione di Erlang e la
distribuzione esponenziale è la seguente
★ La somma
T = T1 + T2 + . . . + Tk
di k variabili aleatorie indipendenti distribuite in modo esponenziale,
ciascuna con media 1/kµ , è una variabile aleatoria con distribuzione di
Erlang di ordine k e parametri µ e k
★ L’importanza di tale proprietà risiede nel fatto che è possibile modellare
un servitore che ha un tempo di servizio che è una variabile aleatoria con
distribuzione di Erlang di ordine k attraverso k code markoviane poste in
successione (in cui però il servitore della prima coda non può iniziare un nuovo
ERLANG PROBABILITY DISTRIBUTION FUNCTION
(al variare del parametro k)
TEORIA DELLE CODE
servizio fino a quando il servitore dell’ultima coda non ha concluso il proprio)
MODELLI E METODI
PER L’AUTOMAZIONE
55
TEORIA DELLE CODE
MODELLI E METODI
PER L’AUTOMAZIONE
56
CODA M/Ek/1
★ Per la coda M/Ek/1 si ricava che
Lw =
(1 + k)
2
µ(µ
)
da cui si possono calcolare, nel modo usuale, i tempi T w = Lw /
T q = T w + 1/µ e la lunghezza Lq = T q
TEORIA DELLE CODE
e
MODELLI E METODI
PER L’AUTOMAZIONE
57