Logistica del Trasporto Marittimo: Teoria delle Code e Processo di Poisson

Introduzione alla Teoria delle Code

RUM
UN
STUDI
CAS
MESS
N
Corso di Laurea in Scienze e Tecnologie della Navigazione
A.A. 2021-2022
Insegnamento di
LOGISTICA DEL TRASPORTO MARITTIMO
Teoria delle code
prof. Massimo Di Gangi
ing. Antonio Polimeni
antonio.polimeni1@unime.itINTRODUZIONE
Elementi di Teoria delle Code
Simulazione dei terminali
Un flusso di clienti in arrivo nel sistema chiede di
essere servito da una risorsa per un determinato
tempo di servizio.
Poiché i canali serventi sono generalmente in numero
limitato, l'istante di arrivo dei clienti è casuale e,
inoltre, essi richiedono un servizio la cui durata può
non essere costante, una parte dei clienti dovrà
attendere in coda.

Simulazione dei Terminali

INTRODUZIONE
Elementi di Teoria delle Code
Simulazione dei terminali
In generale, un terminale è costituito da un insieme di
punti di servizio per gli utenti che possono essere disposti
in:
/
serie
V
parallelo
misti (serie-parallelo o parallelo-serie)

Esempi di Punti di Servizio nei Terminali

INTRODUZIONE
Elementi di Teoria delle Code
Simulazione dei terminali
pista di decollo
procedure di decollo
gate imbarco
scale mobili di accesso
percorsi di accesso agli imbarchi
controlli sicurezza
check-in
biglietteria

Definizione del Problema nella Teoria delle Code

INTRODUZIONE
Elementi di Teoria delle Code
Definizione del problema
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 considerato
Esempio: 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
coda
Esempio: barriera autostradale (unico canale)
arrivano 400 veic/h
capacità 180 veic./h -> 220 veic/h in coda

Tassi di Arrivo e Servizio Deterministic

INTRODUZIONE
Elementi di Teoria delle Code
Definizione del problema
Siano:
a tasso di arrivo medio dei clienti nel sistema
o tasso di servizio medio per cliente
deterministici e sia o > a.
il cliente trova sempre il sistema vuoto e il server libero
Es.
a = 3 clienti/min
o = 1/15 cliente/sec
clienti
1
3
2
1
20 40 60 80 100
sec

Tassi di Arrivo e Servizio Stocastici

INTRODUZIONE
Elementi di Teoria delle Code
Definizione del problema
Siano:
a tasso di arrivo medio dei clienti nel sistema
o tasso di servizio medio per cliente
e sia o > a .
Numero di clienti in arrivo e tempo di servizio sono stocastici.
il cliente può trovare il server occupato e in questo caso deve
attendere in coda finche esso non si libera.
clienti
tempo di attesa
1
3
2
1
sec
20 40 60 80 100

Condizioni di Sovrasaturazione

INTRODUZIONE
Elementi di Teoria delle Code
Definizione del problema
tasso medio degli arrivi > tasso medio di servizio
(condizioni di sovrasaturazione)
Se queste condizioni permangono nel tempo la coda cresce
indefinitivamente
ora
Arrivi
[veicoli]
Capacità
[veicoli]
Coda
[veicoli]
1
400
180
220
2
400
180
440
3
400
180
660
4
400
180
880
5
400
180
1100
6
400
180
1320
7
400
180
1540
8
400
180
1760
9
400
180
1980
10
400
180
2200
condizioni di sovrasaturazione
2500
1980
1760
2000
1540
1320
1500
1100
880
=1000
660
440
220
500
0
1
2
3
4
5
6
7
8
9
10
tempo (h)
coda (veic.)

Condizioni di Sottosaturazione

INTRODUZIONE
Elementi di Teoria delle Code
Definizione del problema
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
300
ora
Arrivi
[veicoli]
Capacita
[veicoli]
Coda
[veicoli]
260
240
250
.200
180
-150
3
200
180
260
90
100
4
100
180
180
5
90
180
90
20
0
6
90
180
0
0
1
2
3
4
5
6
tempo (h)
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
1
200
180
20
2
400
180
240
coda (velc.)
50

Obiettivo e Capacità del Sistema

INTRODUZIONE
Elementi di Teoria delle Code
Obiettivo
Dimensionare la capacità dei punti di servizio per:
V
evitare fenomeni di sovrasaturazione
contenere i tempi di attesa entro standard prefissati
capacità di un punto di servizio # capacità del sistema
Sistema S con più punti di servizio p IN SERIE
CAPS = capacità del sistema S
capp = capacità del punto di servizio p
CAPS = minp [capp] VpES
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.

Simulazione e Modelli dei Terminali

INTRODUZIONE
Elementi di Teoria delle Code
Simulazione dei terminali
Lo studio dei terminali di trasporto, e dei singoli punti di servizio al
suo interno, può essere effettuato utilizzando:
modelli analitici (teoria delle code)
modelli sperimentali (simulazione)Elementi di Teoria delle Code

I Sistemi a Barriera

I sistemi a barriera
Canali
serventi
1
1
utenti
2
Utenti serviti
321
3
coda
4
Caratteristiche del sistema
modello degli arrivi
meccanismo del servizio
1
disciplina della codaElementi di Teoria delle Code

Modello degli Arrivi

Modello degli arrivi
Unità
serventi
1
1
utenti
2
Utenti serviti
3 21
3
coda
4
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 distribuzioneElementi di Teoria delle Code

Modello degli Arrivi alla Poisson - Parte 1

Modello degli arrivi alla Poisson - 1
Una successione nel tempo di arrivi prende il nome di
processo di Poisson con parametro a quando:
la probabilità che si verifichi un arrivo nell'intervallo
(t, t+At), al tendere di At a 0, è proporzionale
all'ampiezza At dell'intervallo tramite a, a meno di un
infinitesimo di ordine superiore, ovvero:
lim
At->0
prob[N(t, t + At) = 1]= a At + 0(At)
segue ....Elementi di Teoria delle Code

Modello degli Arrivi alla Poisson - Parte 2

Modello degli arrivi alla Poisson - 2
la probabilità che si verifichi più di un arrivo tende ad un
infinitesimo di ordine superiore:
prob[N(t, t + At) > 1]= 0(At)
lim
At->0
V
e quindi la probabilità che non si verifichi alcun arrivo è:
lim
At->0
prob[N(t, t + 4t) = 0]= 1 - a At
segue ....Elementi di Teoria delle Code

Modello degli Arrivi alla Poisson - Parte 3

Modello degli arrivi alla Poisson - 3
V
la probabilità di un arrivo nell'intervallo (t, t+At), è indipendente
da ciò che è accaduto negli intervalli precedenti (la probabilità
condizionata è uguale alla probabilità semplice):
lim prob[N(t, t + At) = 1 / N(t, t - At) = 1 ]= prob[N(t, t + At) = 1]= a At + 0(At)
At->0
segue ....Elementi di Teoria delle Code

Meccanismo di Servizio

Meccanismo di servizio
V
numero di canali serventi
tempo di servizio ts
Unità
serventi
r
+ 1
utenti
2
Utenti serviti
321
3
coda
+ 4
/
Tempi di servizio costanti (approccio deterministico)
il tempo di servizio vale ts per tutti gli utenti ed il numero di utenti che
può essere servito nell'unità di tempo e pari a 1/t,
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 t, è il tempo medio di servizio, il tasso medio di servizio è 1/ t,
Se i tempi di servizio sono distribuiti secondo una esponenziale negativa,
il processo delle partenze e un processo di Poisson di parametro a = 1/ t,Elementi di Teoria delle Code

Disciplina della Coda

Disciplina della coda
Unità
serventi
r
1
uten
+ 2
Utenti serviti
321
3
coda
+ 4
V
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.
sistemi a più canali
unica coda con accesso al primo canale libero;
" una coda per ogni canale
o
con scelta libera da parte degli utenti
o
con scelta vincolata da regole predeterminate (ad esempio
suddivisione per lettera alfabetica)Elementi di Teoria delle Code

Denominazione dei Sistemi (Codice Kendall)

Denominazione dei sistemi
(Codice Kendall)
A/B/m; (n)/C
dove:
V
A indica il modello degli arrivi
(M=arrivi alla Poisson)
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, BIFO, ecc.)
Ad esempio: M/M/1; /FIFOElementi di Teoria delle Code

Variabili di Sistema

Variabili di sistema
Definizioni:
V
Intensità di traffico p:
p = a/o
dove:
a tasso medio di arrivo per canale
· o = 1/t tasso medio di servizio (capacità o potenzialità)Elementi di Teoria delle Code

Esempio di Calcolo dell'Intensità di Traffico

Esempio
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.
unico canale servente
a = 3
o = 6
p = a/6 = 0.5Elementi di Teoria delle Code

Definizioni di Tempo di Attesa e Permanenza

Variabili di sistema
Definizioni:
V
tempo di attesa wA:
· tempo intercorrente tra l'ingresso dell'utente nel sistema e
l'inizio del servizio
V
tempo di permanenza nel sistema w,:
" tempo intercorrente tra l'arrivo dell'utente e la fine del
servizio
WS=WA+tsElementi di Teoria delle Code

Definizioni di Numero Medio di Utenti

Variabili di sistema
Definizioni:
V
ns = numero medio di utenti nel sistema
n = numero medio di utenti in attesa
Ws = tempo medio di permanenza nel sistema
V
WA = tempo medio di attesaElementi di Teoria delle Code

Misura delle Caratteristiche di Funzionamento

Misura delle caratteristiche di
funzionamento del sistema
Dato un punto di funzionamento del sistema occorre determinare:
V
media e distribuzione dei tempi di attesa WA;
1
media e distribuzione del numero ns di utenti presenti nel
sistema ed na presenti in coda ad ogni istante;
1
media e distribuzione dei tempi in cui i canali sono occupati da
utenti.Elementi di Teoria delle Code

Equazioni di Equilibrio del Sistema M/M/1

Equazioni di equilibrio del sistema
[M/M/1; %,FIFO]
Il sistema sia in uno stato al A, al tempo t. L'evoluzione del sistema tra due
stati consecutivi che distano temporalmente At viene governata dal
verificarsi di uno dei seguenti eventi:
V
Arrivo di un utente, con probabilità aAt
v Partenza di un utente, con probabilità oAt,
/
Nessun arrivo e nessuna partenza, con probabilità 1 - (alt + oAt)
Definito uno stato del sistema con n utenti presenti ciò può verificarsi solo
se:
V
nello stato precedente c'erano n-1 utenti e si è verificato un arrivo
nello stato precedente c'erano n+1 utenti e si è verificata una
partenza
nello stato precedente c'erano n utenti e non ci sono stati né arrivi né
partenze
(continua ... )