sistemi servizio simulazione
TRANSCRIPT
Facolta di Ingegneria dell’Informazione,
Informatica e Statistica
Corso di Laurea Magistrale in
Ingegneria Gestionale
Sistemi di Servizio e Simulazione
Massimo Roma
Dipartimento di Ingegneria Informatica, Automatica e Gestionale“A. Ruberti”
[email protected]://www.dis.uniroma1.it/∼roma
anno accademico 2018-19
Prefazione
Queste note sono redatte in forma di appunti delle lezioni, ad uso degli studenti
del corso di “Sistemi di Servizio e Simulazione” del Corso di Laurea Magistrale in
Ingegneria Gestionale della Facolta di Ingegneria dell’Informazione, Informatica
e Statistica della SAPIENZA – Universita di Roma.
La trattazione e divisa in due parti: nella prima parte viene affrontato lo studio
analitico della Teoria delle code con particolare attenzione ai modelli basati su
processi di nascita e morte; la seconda parte fornisce le basi della Simulazione ad
eventi discreti. Le metodologie della simulazione sono studiate in termini generali
e con riferimenti specifici ai sistemi di servizio. Al termine e introdotto l’utilizzo
di ambienti software specializzati per la simulazione.
Poiche il corso e destinato a studenti che per la prima volta nel loro curriculum di
studi affrontano queste tematiche, la trattazione, pur mantenendo un adeguato
rigore formale, e (per quanto possibile) semplificata nell’esposizione degli argo-
menti e nella formulazione degli esempi. Un’integrazione con gli ulteriori esempi
ed esercizi svolti durante le lezioni e indispensabile, cosı come e auspicabile un
approfondimento con “casi di studio” reali.
Prerequisiti essenziali per una buona comprensione di queste note sono una co-
noscenza di base del calcolo differenziale e degli aspetti modellistici di base della
Ricerca Operativa. Si assumeranno inoltre come noti i concetti base del Calcolo
delle Probabilita e della Statistica, con particolare riferimento alla teoria generale
della probabilita, alle variabili aleatorie, alle distribuzioni di probabilita di uso
frequente, alle leggi di convergenza e alle basi dell’inferenza statistica.
Al termine di ciascuna delle due parti e riportata una bibliografia essenziale.
Molte utili informazioni sulla Teoria delle code sono disponibili sul sito
M. Roma – Sistemi di Servizio e Simulazione – SAPIENZA Universita di Roma – a.a. 2018-2019
iv PREFAZIONE
http://web2.uwindsor.ca/math/hlynka/queue.html,
mentre il sito
http://www.informs-sim.org/
raccoglie l’archivio della maggiore conferenza internazionale sulla simulazione,
la Winter Simulation Conference, che si tiene annualmente dal 1968. Lo stu-
dente puo trovarvi informazioni complete ed aggiornate su molti aspetti della
simulazione.
M. Roma – Sistemi di Servizio e Simulazione – SAPIENZA Universita di Roma – a.a. 2018-2019
Introduzione
Un sistema puo essere definito come una collezione di entita (macchine, perso-
ne, etc.) che agiscono e interagiscono per il raggiungimento di uno scopo. Per
studiare “scientificamente” un sistema, viene di solito costruito un modello che e
utilizzato per tentare di comprendere il comportamento del sistema stesso. L’uso
di modelli come strumento efficace per la soluzione di problemi di decisione e og-
gi ampiamente diffuso. Un modello puo rappresentare situazioni provenienti dal
mondo reale, anche molto complesse e anche influenzate da fenomeni di natura
aleatoria. Di fondamentale importanza e di uso ormai consolidato sono i modelli
matematici (analitici) che rappresentano la realta attraverso variabili e relazioni
logico–matematiche e che descrivono in modo semplificato, ma sempre rigoroso, i
fenomeni del mondo reale che si vogliono considerare. E questo il caso dei modelli
di Programmazione Matematica caratterizzati dalla definizione esplicita di una
funzione obiettivo da massimizzare o minimizzare e da un insieme prefissato al
quale devono appartenere le variabili. I modelli matematici sono in grado di rap-
presentare moltissime e diverse realta del mondo reale, e permettono di ottenere
efficientemente una soluzione ottima del problema considerato, o comunque so-
luzioni molto buone. Tuttavia in alcuni casi le situazioni in esame sono talmente
complesse e le dimensioni talmente elevate da rendere difficile o troppo costoso
l’uso di modelli analitici. In questo caso, uno strumento valido ed efficace per
l’analisi dei problemi e rappresentato dalla simulazione, ovvero dall’utilizzo di un
calcolatore per costruire un modello (modello di simulazione) che permetta di
“replicare” il funzionamento del sistema reale in esame. Questi modelli hanno
la differenza fondamentale rispetto ai modelli analitici di utilizzare il calcolatore
non solo come strumento di calcolo, ma anche come strumento per rappresentare
M. Roma – Sistemi di Servizio e Simulazione – SAPIENZA Universita di Roma – a.a. 2018-2019
vi INTRODUZIONE
le realta in esame. Questo significa che se, ad esempio, in un modello di pro-
grammazione matematica c’e una corrispondenza tra relazioni del modo reale e
relazioni matematiche, in un modello di simulazione c’e corrispondenza funziona-
le tra elementi della realta e l’“oggetto” (struttura dati, sottoprogramma, etc.)
che ne svolte le funzioni.
La simulazione, oltre ad essere alternativa all’uso di modelli analitici, gioca un
ruolo di fondamentale importanza all’interno dell’approccio modellistico per la
soluzione di un problema di decisione, per i seguenti due importanti aspetti:
• permette di analizzare e studiare modelli stocastici, ovvero modelli in cui
alcune grandezze sono influenzate da fenomeni di natura aleatoria;
• permette di effettuare la validazione di un modello matematico in alterna-
tiva alla sperimentazione diretta che spesso risulta impraticabile o troppo
costosa.
In questo contesto, questo corso ha un duplice scopo: da un lato vuole ampliare la
conoscenza dei modelli analitici introducendo i cosiddetti modelli di file d’attesa
(anche detti sistemi a coda), che sono uno strumento essenziale per analizzare
un’importante classe di sistemi stocastici, i sistemi di servizio, che sono strutture
molto diffuse nella vita reale caratterizzate dall’arrivo casuale di utenti ciascuno
dei quali richiede un servizio, con la possibilita di formazioni di una coda (o fila)
di utenti in attesa. Dall’altro, il corso vuole fornire le basi della simulazione come
tecnica che permette di studiare gli effetti di eventuali interventi su una realta
gia esistente, oppure di valutare diverse scelte progettuali di una realta ancora
da costruire. Le tecniche di simulazione saranno studiate in termini generali e al
termine della parte metodologica verra introdotto l’uso di ambienti software spe-
cializzati (comunemente chiamati “simulatori”) che permettono di realizzare mo-
delli di simulazione. Si tratta di ARENAr http://www.arenasimulation.com
prodotto dalla Rockwell Automation, un simulatore oggi largamente utilizzato,
che attraverso un’interfaccia grafica consente sia di implementare un modello di
simulazione, sia di effettuare i diversi run di una simulazione e di analizzare i
risultati ottenuti. Verra inoltre introdotto l’uso di un simulatore di piu recen-
te generazione SIMIOTM
http://www.simio.com prodotto dalla SIMIO LCC. Si
tratta di un simulatore basato su “oggetti intelligenti” che una volta costrui-
ti, possono essere riutilizzati in progetti diversi. Esso rappresenta un passaggio
dal paradigma della simulazione “process oriented” a quello della simulazione
“objects oriented”. Questi simulatori sono dotati di strumenti di animazione e
visualizzazione 3D che permettono di osservare bene il funzionamento del sistema
reale.
M. Roma – Sistemi di Servizio e Simulazione – SAPIENZA Universita di Roma – a.a. 2018-2019
1Teoria delle code
L’esperienza quotidiana ci mette in continuo rapporto con la necessita di richie-
dere l’erogazione di un servizio a soggetti o entita con la possibilita che si crei una
fila (o coda) in attesa di essere serviti. Questo accade perche il servizio richiede
un certo tempo per essere espletato e perche l’arrivo di coloro che richiedono il
servizio e casuale. Una struttura di questo tipo, ovvero con arrivo casuale di
clienti che richiedono lo svolgimento di un servizio viene chiamato Sistema di
Servizio. Esempi di sistemi di servizio sono molto numerosi anche nella realta
quotidiana come i distributori di benzina, gli sportelli degli uffici postali o delle
banche, le casse di un supermercato; esempi di situazioni di code per ottenere
un servizio sono anche gli aerei in attesa del decollo o dell’atterraggio, le parti
in attesa di essere lavorate all’interno di un impianto di produzione, i computer
in un sistema di comunicazione in attesa di ricevere o trasmettere dati e molte
altre. Tuttavia, dover aspettare non e solo fonte di disagio personale, ma se si
considera l’ammontare totale delle ore che un popolo di una nazione spreca in
attesa in code esso e un importante fattore della qualita della vita e dell’economia
della nazione. L’impatto degli eccessivi tempi di attesa va anche oltre la semplice
attesa di persone che sono in fila: in un impianto di produzione una macchina
in avaria che e in attesa di essere riparata causa una perdita nella produzione;
ritardi in una rete di telecomunicazioni dovute a linee sature puo causare mal
funzionamenti; aerei in attesa del decollo possono seriamente alterare gli orari
dei voli con conseguenti disguidi per le compagnie aeree e per i passeggeri.
La teoria delle code (o file d’attesa) studia i fenomeni di attesa che si possono
verificare quando si richiede un servizio. Come si e visto negli esempi precedenti,
i suoi i campi di applicazione oltre ad essere quelli legati alla vita quotidiana,
riguardano anche i sistemi di elaborazione, i sistemi di trasmissione dati, i sistemi
M. Roma – Sistemi di Servizio e Simulazione – SAPIENZA Universita di Roma – a.a. 2018-2019
2 TEORIA DELLE CODE
flessibili di lavorazione, i sistemi di trasporto e molti altri. Quindi oltre che
migliorare la qualita della vita delle persone, la teoria delle code trova applicazione
nel settore industriale, dei servizi e moltissimi altri.
Dal punto di vista storico, la formulazione del primo problema di teoria delle
code risale al 1908, quando A.K. Erlang, un ingegnere impiegato presso la Danish
Telephone Company di Copenaghen, ritenuto il fondatore della teoria delle code,
voleva studiare come dimensionare centrali telefoniche allo scopo di mantenere
ad un valore ragionevolmente basso il numero delle chiamate che non potevano
essere connesse (chiamate perse) perche il centralino era occupato.
M. Roma – Sistemi di Servizio e Simulazione – SAPIENZA Universita di Roma – a.a. 2018-2019
GENERALITA 3
1.1 GENERALITA
Un Sistema di Servizio (o sistema a coda) e una struttura caratterizzata dal-
l’arrivo casuale di utenti detti clienti ciascuno dei quali richiede lo svolgimento Sistema di
Serviziodi un’operazione che viene detta servizio. L’operazione e svolta da un’unita che
viene detta servente (server) (o stazione di servizio) che puo servire un utente alla
volta. Poiche gli arrivi degli utenti che richiedono il servizio e casuale e poiche
il tempo necessario per espletare il servizio dal parte del servente e non nullo, si
possono verificare situazioni temporanee in cui il servente non ha la possibilita di
soddisfare immediatamente le richieste con conseguente generazione di una fila o
coda di clienti in attesa di essere serviti.
Il servente puo essere uno solo (singolo canale) oppure ci puo essere piu di un
servente. Gli utenti che arrivano al sistema attendono in fila se tutti i serventi
sono impegnati, poi vengono serviti ed infine lasciano il sistema. Si tenga conto
del fatto che, di solito, chi gestisce il servizio ricava un utile dall’effettuazione del
servizio stesso, e quindi si adoperera affinche i clienti non vengano scoraggiati da
attese eccessive rinunciando al servizio o rivolgendosi altrove, overo non fornendo
alcun utile al gestore; d’altra parte, il gestore per ovviare a questo inconveniente
potrebbe aumentare il numero dei serventi, ma questo implica un aumento dei
costi ed inoltre l’aumento degli operatori addetti al servizio potrebbe non essere
assolutamente conveniente se questi, tranne nei momenti di maggiore richiesta,
rimangono inattivi per lunghi periodi.
Lo scopo della teoria della code e quello di valutare alcune grandezze (misure
di prestazione) sulle quali basarsi per dimensionare il sistema di servizio. Esse
possono essere la lunghezza media della coda, il numero medio di utenti presenti
nel sistema, la durata media del tempo passato nella coda. Ovvero, deve poter
fornire una risposta a domande tipiche riguardanti misure di prestazione del si-
stema, fra le quali: quanto tempo un cliente si prevede che aspetti in fila prima
di essere servito ? Qual e la probabilita che un cliente aspetti piu di un tempo
prefissato prima di essere servito ? Qual e l’utilizzazione che ci si aspetta dei
serventi e il tempo che essi sono occupati ? Qual e la probabilita che la coda
superi una certa lunghezza ?
Sistemi con tipologie abbastanza semplici possono essere analizzati analiticamen-
te, ma quando le tipologie sono piu complicate come, ad esempio, piu code pre-
senti nel sistema, relative ad operazioni diverse, effettuate da serventi diversi, e
tali che tutte le operazioni devono essere effettuate affinche il servizio richiesto sia
espletato, un’analisi analitica non e sempre possibile e l’utilizzo della simulazione
e in questo caso indispensabile per l’analisi delle prestazioni del sistema.
M. Roma – Sistemi di Servizio e Simulazione – SAPIENZA Universita di Roma – a.a. 2018-2019
4 TEORIA DELLE CODE
1.1.1 Esempi reali di sistemi a coda
La descrizione fino ad ora fornita di un sistema di servizio (sistema a coda) po-
trebbe sembrare abbastanza astratta e applicabile solamente ad alcuni casi par-
ticolari. Al contrario, i sistemi a coda presentano un vasto campo di applicazione
in differenti contesti. Riportiamo di seguito alcune situazioni in cui la teoria delle
code puo essere applicata con successo.
• Sistemi di servizi commerciali.
Nell’esperienza quotidiana ci sono molte situazioni in cui clienti ricevono un
servizio da una organizzazione commerciale con frequente formazione di fila
d’attesa; esempi sono le casse di un supermercato, gli uffici postali, l’ingresso
ad un museo, le biglietterie ferroviarie, l’anagrafe, gli uffici commerciali
pubblici aperti al pubblico e moltissimi altri.
• Sistemi di servizi sociali.
Anche nell’espletamento dei servizi sociali in molte situazioni la formazione
di file d’attesa e spesso inevitabile. Ad esempio, i servizi ospedalieri (servizio
radiografico, laboratorio di analisi cliniche, visite specialistiche), il servizio
ambulatoriale del medico di base, oppure, in generale, uffici pubblici che
forniscono un servizio sociale. Anche il sistema giudiziario puo essere visto
come un sistema a coda in cui le corti sono i serventi e gli utenti sono i
processi in attesa di essere celebrati. Il sistema legislativo e un sistema di
file d’attesa dove i progetti di legge in attesa di essere discussi rappresentano
gli utenti del sistema.
• Sistemi di trasporto.
I sistemi di trasporto rappresentano un’importante classe di sistemi rappre-
sentabili mediante sistemi a coda. Si pensi, ad esempio, agli autoveicoli in
attesa ai caselli autostradali o ai semafori, agli autocarri o alle navi in atte-
sa di essere caricati o scaricati, agli aerei in attesa di decollare o atterrare.
Un altro esempio puo essere rappresentato dai parcheggi per auto, dove i
serventi sono gli spazi per il parcheggio. Altri casi sono rappresentati dai
taxi, dagli ascensori, dalle autopompe dei vigili del fuoco.
• Sistemi di produzione.
Nei sistemi industriali molto spesso si creano situazioni di attesa da parte di
componenti che devono essere lavorati da linee di produzione. Altri esempi
sono rappresentati dai centri di assemblaggio o dai sistemi di manutenzione
in cui gli operai rappresentano i serventi e le macchine da sottoporre a
manutenzione i clienti.
• Sistemi di comunicazione.
Nelle reti di comunicazioni, ad esempio quelle di trasmissione dati, pacchet-
ti di dati vengono trasmessi lungo le connessioni da un nodo al successivo
M. Roma – Sistemi di Servizio e Simulazione – SAPIENZA Universita di Roma – a.a. 2018-2019
GENERALITA 5
con possibilita di attesa (buffering) quando la domanda in ingresso ecce-
de la capacita. Situazioni di attesa possono anche verificarsi nel calcolo
parallelo in cui piu calcolatori connessi effettuano elaborazioni in parallelo
con necessita di scambiarsi dati. Altri esempi sono rappresentati dai call–
center, dove gli operatori rappresentano i serventi e gli utenti sono coloro
che chiamano e che possono essere messi in attesa fino al momento in cui
c’e un operatore disponibile.
Naturalmente ogni lista di casi reali non puo essere esaustiva, ma gli esempi
riportati rappresentano situazioni caratteristiche e dovrebbero suggerire il fatto
che i sistemi a coda pervadono la vita reale in molti e diversi settori della societa.
1.1.2 Componenti di un sistema di servizio
Da un punto di vista fisico, un sistema di servizio e composto da un insieme (non
vuoto) di serventi, da un insieme (non vuoto) di aree di attesa (chiamate anche
buffer) che accolgono i clienti in attesa di essere serviti.
Un sistema di servizio puo essere schematizzato nelle seguenti componenti carat-
teristiche:
• Popolazione
I potenziali clienti fanno parte della cosiddetta popolazione degli utenti (o
input source). I clienti di una popolazione sono indistinguibili e la carat- Popolazione
degli utentiteristica principale di una popolazione e la dimensione, che rappresenta il
numero totale dei distinti potenziali clienti che richiedono un servizio. Si
puo assumere che la dimensione sia finita o infinita. Per semplicita di ana-
lisi, spesso si assumera che la dimensione sia infinita anche quando essa e
finita purche sufficientemente grande. Il caso finito e piu difficile da trattare
perche il numero dei clienti nel sistema influenza il numero dei clienti che
sono al di fuori del sistema. Tuttavia l’assunzione di popolazione finita e
necessaria in alcuni casi.
• Numero dei serventi
In un sistema a coda deve essere noto il numero dei serventi che indichiamo Numero dei
serventi scon s. Infatti, in generale, vi possono essere uno o piu serventi e nel caso in
cui vi sono piu serventi e necessario distinguere se lavorano “in parallelo”
o “in serie”.
• Schema di arrivo
In un sistema a coda deve essere specificato lo schema di arrivo che descri-
ve il modo secondo il quale i clienti si presentano a richiedere il servizio.
Esso e definito in termini di intervalli di tempo tra due arrivi successivi di
clienti nel sistema (tempo di interarrivo). Questo schema puo essere deter-
ministico oppure puo essere rappresentato da una variabile aleatoria che,
M. Roma – Sistemi di Servizio e Simulazione – SAPIENZA Universita di Roma – a.a. 2018-2019
6 TEORIA DELLE CODE
in riferimento all’i-esimo cliente che entra nel sistema, indichiamo con tai ,
ovvero tai rappresenta il tempo che intercorre tra l’arrivo del cliente (i− 1)-Tempo di
interarrivo tai esimo e il cliente i-esimo. Degli intertempi di arrivo si suppone nota la
distribuzione di probabilita.
Altri due aspetti meno comuni possono anche presentarsi: la rinuncia di
un utente in arrivo in conseguenza del fatto che la coda e troppo lunga
(balking); l’arrivo degli utenti in gruppo.
• Schema di servizio
Lo schema di servizio descrive il modo secondo il quale ciascun servente
eroga il servizio. Esso e specificato in termini del tempo di servizio, ovveroTempo di
servizio tsi del tempo necessario ad un servente per “servire” un utente. Il tempo di
servizio puo essere deterministico, ma piu spesso esso e una variabile alea-
toria che, in riferimento al cliente i-esimo indichiamo con tsi . Dei tempi di
servizio si suppone nota la distribuzione di probabilita.
Un’assunzione comune e che, nel caso di piu serventi, essi operano con il
medesimo schema di servizio, ovvero il tempo di servizio ha la stessa distri-
buzione di probabilita. Esiste anche la possibilita di avere i clienti serviti
da una sequenza di serventi, ovvero un cliente per essere completamento
servito richiede l’intervento di piu serventi in successione.
• Capacita del sistema
Il valore massimo che puo assumere la variabile associata al numero di
utenti presenti nel sistema si definisce capacita del sistema, e corrispondeCapacita
del sistema al numero massimo di utenti che possono essere contemporaneamente nel
sistema, comprendendo sia gli utenti in attesa in coda, sia quelli che stanno
fruendo del servizio.
• Disciplina della coda
La disciplina della coda specifica l’ordine rispetto al quale gli utenti vengono
serviti. Le piu comunemente usate sono basate sui seguenti criteri: FIFOCriteri FI-
FO, LIFO,
SIRO
(“first in first out”)1 che corrisponde al servizio degli utenti nell’ordine in
cui arrivano; LIFO (“last in first out”)2 che corrisponde a servire per primo
l’ultimo cliente arrivato; SIRO (“service in random order”) che consiste
nel servire gli utenti scegliendoli a caso; infine, possono esistere criteri di
priorita (PRI) che consistono nel classificare gli utenti in base a classi di
priorita, servendo per primi quelli della classe di priorita piu alta.
Indichiamo con tqi la variabile aleatoria rappresentante il tempo passatoTempo in
coda tqi dall’i-esimo utente nella coda prima di iniziare ad usufruire del servizio.
1Anche indicato con FCFS (“first came first served”)2Anche indicato con LCLS (“last came last served”)
M. Roma – Sistemi di Servizio e Simulazione – SAPIENZA Universita di Roma – a.a. 2018-2019
GENERALITA 7
Il processo base che avviene in un sistema a coda e il seguente: clienti che richie-
dono un servizio sono generati nel tempo dalla popolazione, entrano nel sistema
e raggiungono la coda. Ad un certo momento, un cliente viene selezionato dal-
la coda secondo la disciplina della coda. Il servizio richiesto e effettuato da un Tempo di
permanenza
nel sistema
servente e successivamente a cio il cliente lascia il sistema. Quindi se indichiamo
con twi il tempo passato complessivamente dall’i-esimo utente nel sistema si ha
twi = tqi + tsi . (1.1.1)
Rappresentazioni schematiche di sistemi a coda sono riportati nella Figura 1.1.1
e nella Figura 1.1.2.
Coda
Serventi
Popolazione
Figura 1.1.1 Schema di un sistema a coda con una sola coda e tre serventi in parallelo
Coda
Serventi
Popolazione
Coda
Figura 1.1.2 Schema di un sistema a coda con due code e quattro serventi in parallelo
M. Roma – Sistemi di Servizio e Simulazione – SAPIENZA Universita di Roma – a.a. 2018-2019
8 TEORIA DELLE CODE
Naturalmente un servente non deve essere necessariamente un singolo individuo,
ma puo essere costituito da un gruppo di persone che lavorano simultaneamente
per il cliente (si pensi, ad esempio, agli operai di un officina di riparazione che
lavorano contemporaneamente per effettuare riparazioni ad apparati in avaria).
Inoltre, i serventi non devono essere necessariamente delle persone: infatti, in
molti casi sono macchine, dispositivi elettronici, etc. Analogamente, un cliente
non deve essere necessariamente un individuo, ma puo essere un articolo in attesa
di essere lavorato da una macchina oppure un automobile in attesa di essere
revisionata, etc.
Nel trattare la teoria delle code, un’assunzione che di solito viene fatta e che noi
assumeremo sempre soddisfatta riguarda il fatto che gli intertempi di arrivo taisono indipendenti e identicamente distribuiti e che anche i tempi di servizio tsisono indipendenti e identicamente distribuiti.
1.1.3 Notazione di Kendall
E stata definita una notazione per indicare sinteticamente le caratteristiche prin-
cipali di un sistema di servizio (o a coda); la notazione, chiamata notazione di
Kendall, consiste in sigle separate dal simbolo /, del tipo
A/B/s/c/p/Z
dove
A rappresenta lo schema di arrivo, ovvero la distribuzione di probabilita degli
intertempi di arrivo;
B rappresenta lo schema di servizio, ovvero la distribuzione di probabilita dei
tempi di servizio;
s rappresenta il numero di serventi ;
c rappresenta la capacita del sistema;
p rappresenta la dimensione della popolazione;
Z rappresenta la disciplina della coda.
Le ultime tre componenti possono non essere specificate, assumendo, i seguenti
valori di default: in mancanza della componente c si assume che la capacita
del sistema sia infinita; se non e specificata la componente p si assume che la
popolazione sia infinita; se non e presente la componente Z si assume che la
disciplina della coda sia FIFO.
Le componenti s, c e p sono numeri interi non negativi. Per quanto riguarda le
distribuzioni di probabilita dello schema di arrivo e di servizio, quelle che vengono
piu frequentemente assunte sono la distribuzione esponenziale, la distribuzione
M. Roma – Sistemi di Servizio e Simulazione – SAPIENZA Universita di Roma – a.a. 2018-2019
GENERALITA 9
costante (degenere) o tempi deterministici, la distribuzione di Erlang di ordine k.
Queste vengono indicate in termini delle componenti A e B, nel seguente modo:
M indica la distribuzione esponenziale;
D indica la distribuzione costante (degenere) o tempi deterministici;
Ek indica la distribuzione di Erlang di ordine k;
G indica una distribuzione generica che, per quanto riguarda gli intertempi
di arrivo, puo essere sostituita dalla sigla GI ad indicare un distribuzione
generica di eventi indipendenti.
Molto frequente e l’uso di notazioni del tipo M/M/1 (ovvero con solamente tre
caratteri) che, come abbiamo gia detto, corrisponde ad avere la capacita del
sistema infinita, la popolazione infinita e la disciplina della coda basata sul cri-
terio FIFO (ovvero corrisponderebbe a scrivere M/M/1/∞/∞/FIFO o anche
M/M/1/ · / · /FIFO); tale modello M/M/1 assume che sia gli intertempi di ar-
rivo, sia i tempi di servizio hanno distribuzione esponenziale e che e presente un
solo servente. La notazione M/G/1 indica, ad esempio, un modello con intertem-
pi di arrivo distribuiti esponenzialmente e non pone nessuna specificazione sulla
distribuzione dei tempi di servizio.
Esempio 1.1.1 Nell’ufficio accettazione di un corriere espresso ci sono quattro operatori
addetti a ricevere plichi destinati a spedizioni internazionali che lavorano indipendente-
mente l’uno dall’altro. Da un’analisi statistica effettuata negli ultimi mesi, si e eviden-
ziato che il tempo che passa tra l’ingresso nell’ufficio di un cliente e il successivo puo
essere assunto distribuito esponenzialmente con media 3 minuti. Quando un cliente arri-
va preleva un numero di ordine e, se tutti gli operatori sono occupati, aspetta all’interno
dell’ufficio che se ne liberi uno per essere servito. Gli operatori addetti alla ricezione dei
plichi espletano la procedura di accettazione immettendo su un terminale i dati del mit-
tente e del destinatario, apponendo un codice a barre sul plico e consegnando al cliente
una ricevuta. Si suppone che gli operatori abbiano la stessa rapidita di esecuzione della
procedura la cui durata puo essere supposta distribuita esponenzialmente con media 6
minuti.
Il sistema a coda che descrive questa situazione e rappresentato dall’ufficio accettazione
nel quale operano in parallelo quattro serventi (gli operatori). Gli utenti che richiedono
il servizio sono i clienti che entrano nell’ufficio e la popolazione puo essere considerata
infinita. Poiche sia i tempi di interarrivo dei clienti, sia i tempi di servizio dei serventi
sono distriuiti esponenzialmente, e la disciplina della coda e di tipo FIFO, il sistema puo
essere rappresentato con la notazione M/M/4.
Se inoltre si suppone che all’interno dell’ufficio lo spazio per l’attesa del proprio turno da
parte dei clienti sia abbastanza piccolo da non permettere che vi siano piu di 10 clienti,
M. Roma – Sistemi di Servizio e Simulazione – SAPIENZA Universita di Roma – a.a. 2018-2019
10 TEORIA DELLE CODE
allora il sistema diventerebbe a capacita limitata e puo essere rappresentato con la no-
tazione M/M/4/14.
Se infine si suppone che pagando una tariffa maggiorata un cliente puo essere servito
senza dover fare la fila, allora il sistema avrebbe uno schema della coda basato su criteri
di priorita e puo essere rappresentato con la notazione M/M/4/14/ · /PRI.
Esempio 1.1.2 In un’industria manifatturiera ci sono due operai addetti a collaudare
apparati appena usciti da una linea di produzione. Tali pezzi vengono immessi diretta-
mente dalla linea di produzione in un grande contenitore da dove i due operai prelevano
a caso un apparato per volta per collaudarlo. I due operai lavorano indipendentemente
l’uno dall’altro e attualmente la linea e regolata per produrre un apparato ogni 4 minuti.
Il tempo che ciascun operatore impiega a collaudare un apparato e distribuito esponen-
zialmente con media 5 minuti.
Il sistema a coda che descrive questa situazione e rappresentato dal reparto dove lavora-
no i due operai che sono quindi i serventi che lavorano in parallelo. Gli utenti sono gli
apparati il cui arrivo al sistema e rappresentato dall’uscita dalla linea di produzione e il
grande contenitore rappresenta il buffer di attesa in coda. Lo schema di scelta dalla coda
e inoltre causale. Se si puo supporre che il contenitore sia sufficientemente grande da
contenere un numero molto elevato di apparati, ovvero costituisca un buffer teoricamente
infinito, il sistema puo essere rappresentato con la notazione D/M/2/ · / · /SIRO, avendo
assunto che la produzione continua della linea permetta di assumere che la popolazione
sia infinita.
Esempio 1.1.3 Un’azienda di noleggio bus, ha una flotta di 250 veicoli tra pullman,
pulmini e pullman gran turismo. La manutenzione ordinaria e straordinaria di questi
veicoli e effettuata da un’officina interna all’azienda dove vengono indirizzati i veicoli che
ne necessitano. In tale officina si possono effettuare riparazioni solamente ad un veicolo
per volta e quindi, se un veicolo arriva quando la squadra degli operai dell’officina e gia
impegnata a lavorare su un altro veicolo, il nuovo veicolo viene messo in un deposito
interno all’officina in attesa del suo turno. Attualmente l’azienda non adotta politiche
di priorita sulle riparazioni e quindi vengono riparati i veicoli secondo l’ordine con cui
questi arrivano all’officina. Al momento non si conosce la distribuzione di probabilita
dei tempi di interarrivo dei veicoli all’officina, mentre e noto che il tempo necessario per
effettuare la manutenzione su un veicolo e distribuito esponenzialmente con media 3 ore.
Il sistema a coda che descrive questa situazione e rappresentato dall’officina che opera
con un solo servente (la squadra di operai). Gli utenti sono i veicoli e, poiche solamente
i 250 veicoli dell’azienda possono essere riparati nell’officina, la popolazione in questo
caso deve essere considerata finita e pari a 250. La disciplina della coda e di tipo FIFO.
Poiche non e specificata la distribuzione dei tempi di interarrivo mentre i tempi di servizio
sono distribuiti esponenzialmente, il sistema puo essere rappresentato con la notazione
G/M/1/ · /250.
Se poi si assume che il deposito in cui i veicoli aspettano di essere riparati ha una capienza
massima di 10 veicoli, il modello diventa G/M/1/11/250.
M. Roma – Sistemi di Servizio e Simulazione – SAPIENZA Universita di Roma – a.a. 2018-2019
PROBLEMATICHE DI INTERESSE E RELAZIONI FONDAMENTALI 11
1.2 PROBLEMATICHE DI INTERESSE E RELAZIONI FONDAMENTALI
Le problematiche di interesse nello studio di un sistema a coda riguardano le
prestazioni del sistema. In particolare, il gestore o il progettista di un sistema
di servizio vuole dimensionare il sistema in modo da ottimizzarne le prestazioni.
Naturalmente, ci sono due punti di vista: i clienti vorranno minimizzare i tempi
di attesa, mentre il gestore del sistema di servizio sara interessato a sfruttare al
meglio le risorse del sistema stesso, cioe i serventi, in modo da minimizzare i suoi
costi o massimizzare i suoi profitti; da parte del gestore c’e comunque sempre
da prendere in considerazione il costo indiretto dovuto all’eventuale mancato
guadagno dovuto al fatto che, se i tempi di attesa sono troppo lunghi, gli utenti
potrebbero rinunciare al servizio e rivolgersi altrove.
Si e quindi interessati a determinare le distribuzioni di probabilita di alcune
variabili aleatorie che caratterizzano le prestazioni del sistema in relazione alla
coda di utenti che si forma. Una volta note queste distribuzioni si puo risalire
ai costi che ne conseguono, ovvero il costo del personale e delle attrezzature del
sistema di servizio da parte del gestore o il costo del tempo passato in attesa da
parte dei clienti.
Salvo diversa specificazione, in presenza di piu serventi, assumeremo sempre che
gli s serventi lavorino in parallelo.
1.2.1 Definizioni e notazioni standard
Introdurremo ora alcune definizioni e notazioni standard che vengono di solito
adottate nell’analisi delle prestazione di un sistema a coda e che utilizzeremo nel
seguito.
Si definisce frequenza media degli arrivi dei clienti nel sistema il numero medio di Frequenza
media degli
arrivi
arrivi di utenti nell’unita di tempo. Indicheremo con λ la frequenza media degli
arrivi.
Si definisce velocita di servizio (o tasso di servizio) il numero medio di utenti per Velocita di
servizioil quali e espletato il servizio nell’unita di tempo. Indicheremo con µ la velocita
di servizio.
Si definisce fattore di utilizzazione dei serventi ρ il rapporto tra la frequenza media Fattore di
utilizzazione
dei serven-
ti
degli arrivi e la velocita del servizio moltiplicata per il numero dei serventi, ovvero
ρ =λ
sµ,
che rappresenta la frazione di tempo che i serventi sono occupati, in quanto tale
rapporto e la frazione della capacita di servizio che ha il sistema (sµ) che e
utilizzata in media dai clienti che arrivano (λ).
M. Roma – Sistemi di Servizio e Simulazione – SAPIENZA Universita di Roma – a.a. 2018-2019
12 TEORIA DELLE CODE
Per quanto riguarda la frequenza media degli arrivi λ e la velocita del servizio µ,
indicati con E(tai ) e E(tsi ) i valori attesi delle variabili aleatorie tai e tsi ovviamente
si ha
λ =1
E(tai )e µ =
1
E(tsi ).
Naturalmente, sia λ sia µ potrebbero non essere costanti al variare del numero di
utenti presenti nel sistema. In questi casi, se k denota il numero di utenti presenti
nel sistema, verranno denotate con λk e µk.
Esempio 1.2.1 Si consideri nuovamente il sistema dell’Esempio 1.1.1. Si puo completa-
re la definizione formale del sistema a coda che lo rappresenta specificando che in questo
caso si ha λ = 20 e µ = 10 se si prende come unita di tempo l’ora, oppure λ = 1/3 e
µ = 1/6 se si prende come unita di tempo il minuto. Poiche il numero dei serventi s e
pari a 4, il fattore di utilizzazione dei serventi risulta ρ = 1/2.
Esempio 1.2.2 Si consideri nuovamente il sistema dell’Esempio 1.1.2. Si puo completa-
re la definizione formale del sistema a coda che lo rappresenta specificando che in questo
caso si ha λ = 15 e µ = 12 se si prende come unita di tempo l’ora, oppure λ = 1/4 e
µ = 1/5 se si prende come unita di tempo il minuto. Poiche il numero dei serventi s e
pari a 2, il fattore di utilizzazione dei serventi risulta ρ = 5/8.
Anche con l’ausilio di questi due esempi, dovrebbe essere chiaro che per specifi-
care in maniera completa un sistema a coda e necessario fornire la notazione di
Kendall che lo rappresenta e i parametri λ e µ, ovvero le caratteristiche fisiche
del sistema e le sue logiche di funzionamento insieme alla definizione dei due pro-
cessi fondamentali che lo caratterizzano: il processo degli arrivi e il processo del
servizio con i parametri relativi.
Si definisce stato di un sistema a coda al tempo t il numero di clienti presenti nelStato di un
sistema a
coda n(t)
sistema ed e quindi dato dalla somma del numero dei clienti che sono nella fila di
attesa e il numero dei serventi attivi. Indicheremo con n(t) lo stato del sistema
a coda al tempo t.
Si definisce lunghezza della coda al tempo t il numero di clienti che sono in attesaLunghezza
della coda
nq(t)
del servizio, ovvero nella fila d’attesa. Indicheremo con nq(t) la lunghezza della
coda al tempo t.
Per quanto riguarda la lunghezza della coda nq(t), essa naturalmente dipende da
s e da n(t) ed in particolare vale
nq(t) =
{0 se n(t) ≤ sn(t)− s se n(t) > s.
Si osservi che nel definire le grandezze che caratterizzano i sistemi a coda, non
si ha a che fare solamente con variabili aleatorie, ma con processi stocastici in
M. Roma – Sistemi di Servizio e Simulazione – SAPIENZA Universita di Roma – a.a. 2018-2019
PROBLEMATICHE DI INTERESSE E RELAZIONI FONDAMENTALI 13
quanto e presente una dipendenza da un parametro. Ovvero, formalmente, lo
stato del sistema e la lunghezza della coda, rispettivamente {n(t)} e {nq(t)} sono
processi stocastici a tempo continuo.
D’altra parte le famiglie di variabili aleatorie {twi } e {tqi } che definiscono rispet-
tivamente i tempi di permanenza nel sistema e i tempi di permanenza nella coda
sono processi stocastici a tempo discreto.
Infine, anche la probabilita che nel sistema siano presenti k utenti dipende dal
tempo, ovvero si deve definire pk(t) la probabilita che lo stato del sistema al Probabilita
pk(t)tempo t sia k.
1.2.2 Misure di prestazione
Nell’analisi di un sistema di servizio vengono prese in considerazione alcune gran-
dezze fondamentali come misure di prestazione. Nella maggior parte dei casi di
interesse si e interessati a valutare queste grandezze assumendo che il sistema ab-
bia raggiunto una situazione di regime e cio avviene quando il sistema e stato in
funzione per un tempo sufficientemente grande. Infatti, quando un sistema ha ini-
ziato da poco ad essere operativo, lo stato del sistema sara fortemente influenzato
dallo stato iniziale e dal tempo che e trascorso dall’attivazione del sistema stesso.
In questo caso il sistema e detto in condizioni transitorie. Tuttavia, in molti Condizioni
transitoriecasi, trascorso un tempo sufficientemente grande, il sistema diviene indipendente
dallo stato iniziale e si dice che il sistema ha raggiunto condizioni stazionarie o
equilibrio (steady–state). Si osservi subito che questo non puo accadere se risulta Condizioni
stazionarieρ ≥ 1 nel qual caso lo stato del sistema cresce indefinitivamente nel tempo. Per
un sistema in condizioni stazionarie la distribuzione di probabilita dello stato del
sistema rimane la stessa nel tempo.
La teoria delle code analizza principalmente sistemi in condizioni di stazionarieta;
il caso di sistema in condizioni transitorie e piu difficile da analizzare analitica-
mente e, anche se esistono alcuni risultati validi in questo caso, essi non verrano
considerati. La maggior parte dei sistemi a coda di interesse raggiungono una
situazione di equilibrio, indipendentemente dalla stato iniziale. Tratteremo sola-
mente questi sistemi e quindi formalmente assumeremo che esista finito il seguente
limite
limt→∞
pk(t) = pk, k = 0, 1, . . . , (1.2.1)
dove pk si intende come la probabilita limite che il sistema contenga k utenti in
un istante arbitrariamente grande. Questo, ovviamente, non significa che avendo
assunto che pk non dipenda piu dal tempo il sistema rimanga sempre in questa
situazione limite. Le probabilita pk devono essere interpretate come probabilita a
lungo termine, ovvero descrivono bene la probabilita che siano presenti k in un
sistema che ha raggiunto la stazionarieta.
M. Roma – Sistemi di Servizio e Simulazione – SAPIENZA Universita di Roma – a.a. 2018-2019
14 TEORIA DELLE CODE
Per effettuare l’analisi di un sistema in condizioni di stazionarieta si fa uso delle
seguenti quantita fondamentali:
N : numero medio degli utenti nel sistema
N q : numero medio degli utenti nella coda
T : tempo medio passato da un utente nel sistema
T q : tempo medio passato da un utente nella coda.
Esaminiamo, ora, come queste quantita possono essere definite formalmente,
chiarendo il loro significato.
Dalla definizione di valore atteso si ricava immediatamente
E(n(t)) =∞∑k=0
kpk(t) (1.2.2)
E(nq(t)) =
∞∑k=s+1
(k − s)pk(t). (1.2.3)
Se inoltre indichiamo con ftwi (t) e ftqi (t) rispettivamente le densita di probabi-
lita delle variabili aleatorie continue twi (tempo passato nel sistema) e tqi (tempo
passato nella coda), si ha
E(twi ) =
∫ ∞0
t ftwi (t)dt (1.2.4)
E(tqi ) =
∫ ∞0
t ftqi (t)dt. (1.2.5)
A questo punto, utilizzando la (1.2.1), siamo in grado di definire N , il numero
medio di utenti presenti nel sistema, come
N = limt→∞
E(n(t)) =∞∑k=0
kpk. (1.2.6)
Considerazioni analoghe valgono per la definizione di N q, il numero medio di
utenti in coda, ovvero
N q = limt→∞
E(nq(t)) =
∞∑k=s+1
(k − s)pk.
Per quanto riguarda il tempo di permanenza nel sistema, twi che definisce il tempo
che l’i-esimo utente passa nel sistema (tempo in coda e tempo del servizio),
tipicamente il valore atteso E(twi ), al tendere di i all’infinito, tende ad un valore
di equilibrio che denotiamo con T , ovvero definiamo
T = limi→∞
E(twi ).
M. Roma – Sistemi di Servizio e Simulazione – SAPIENZA Universita di Roma – a.a. 2018-2019
PROBLEMATICHE DI INTERESSE E RELAZIONI FONDAMENTALI 15
Un discorso analogo vale per il tempo tqi passato in coda da ciascun utente, ovvero
definiamo
T q = limi→∞
E(tqi ).
Forniamo, ora, una interpretazione grafica delle quantita appena definite. A tale
scopo, consideriamo, un intervallo prefissato [0, t] e siano a(t) e b(t) rispettiva-
mente il numero totale degli utenti arrivati nel sistema e il numero totale degli
utenti serviti e quindi usciti dal sistema in funzione del tempo t. Per semplicita,
ci riferiremo ad un sistema con un singolo servente e con disciplina della coda FI-
FO, ma i risultati che otterremo sono validi (e facilmente ottenibili) per qualsiasi
tipo di sistema a coda. Consideriamo i diagrammi di a(t) e b(t) nell’intervallo
prefissato [0, t] riportati nella Figura 1.2.2, assumendo che n(0) = 0, ovvero che
all’istante t = 0 nessun utente e presente nel sistema.
1
2
3
4
5
6
7
8
a(t)
b(t)
t
n(t)
wt2
wt1
t 1 t 2
Figura 1.2.1 Illustrazione di una coda
Sull’asse delle ascisse, le ti, i = 1, 2, . . . rappresentano gli istanti di arrivo al
sistema di un utente. Ad ogni istante di tempo t, ovviamente risulta n(t) =
a(t) − b(t). Relativamente all’intervallo [0, t] possiamo considerare le seguenti
medie temporali
Nt =1
t
∫ t
0n(τ)dτ (1.2.7)
Tt =1
a(t)
a(t)∑i=1
twi (1.2.8)
λt =a(t)
t. (1.2.9)
M. Roma – Sistemi di Servizio e Simulazione – SAPIENZA Universita di Roma – a.a. 2018-2019
16 TEORIA DELLE CODE
Nt rappresenta la media di n(t) nell’intervallo [0, t]; Tt rappresenta il tempo medio
di permanenza di un utente nel sistema ottenuto come rapporto tra somma dei
tempi di permanenza di ciascun utente nel sistema e il numero totale a(t) di
utenti arrivati nel sistema al tempo t; λt rappresenta la frequenza media degli
arrivi, ovvero il numero di arrivi nell’unita di tempo.
E importante osservare che la maggior parte dei sistemi a coda di interesse so-
no ergodici. Senza entrare in alcun dettaglio su questa proprieta, diciamo solo
che l’ergodicita e la proprieta per la quale le medie statistiche convergono quasi
ovunque (ovvero con probabilita 1) alle medie temporali. Nel caso delle misure di
prestazione che stiamo esaminando, questa proprieta implica che per t sufficiente-
mente grande, vale l’uguaglianza tra le medie temporali Nt e Tt e i corrispondenti
valori attesi N e T , ovvero che valgono le seguenti uguaglianze
limt→∞
Nt = limt→∞
E(n(t)) (1.2.10)
limt→∞
Tt = limi→∞
E(twi ) (1.2.11)
con probabilita 1.
Ripetendo questi ragionamenti relativamente ai soli utenti in coda, si possono
definire
N qt =
1
t
∫ t
0nq(τ)dτ
T qt =1
a(t)
a(t)∑i=1
tqi
e analogamente ad N nella (1.2.10) si puo ottenere N q come
limt→∞
N qt = lim
t→∞E(nq(t)), (1.2.12)
e analogamente a T nella (1.2.11) si puo ottenere T q come
limt→∞
T qt = limi→∞
E(tqi ), (1.2.13)
dove le uguaglianze valgono con probabilita 1.
Per quanto riguarda la frequenza media degli arrivi nell’intervallo [0, t] supporre-
mo che valga
λ = limt→∞
λt = limt→∞
E (a(t))
t. (1.2.14)
Nel proseguio della trattazione assumeremo che i limiti presenti nelle (1.2.10),
(1.2.11), (1.2.12), (1.2.13) e (1.2.14) esistano e siano finiti.
M. Roma – Sistemi di Servizio e Simulazione – SAPIENZA Universita di Roma – a.a. 2018-2019
PROBLEMATICHE DI INTERESSE E RELAZIONI FONDAMENTALI 17
1.2.3 Relazioni fondamentali
Esistono importanti relazioni che legano le quantita , N , T e N q, T q in un
sistema a coda in condizioni stazionarie. La prima relazione che analizziamo e
uno dei risultati piu generali e utile della teoria delle code. E nota come teorema Teorema di
Littledi Little dal nome di John D. C. Little che per primo nel 1961 ne diede una
formulazione rigorosa [Little, 1961]. Successivamente sono state proposte altre
dimostrazioni di questo risultato in ipotesi del tutto generali. Per una rassegna di
queste dimostrazioni si possono consultare i riferimenti [El-Taha, Stidham, 1999],
[Whitt, 1991], [Wolff, 2011]. Tale risultato, anche detto legge (o formula) di Little
e il seguente:
Teorema 1.2.1 In un sistema a coda in condizioni stazionarie vale la seguente
relazione
N = λT (1.2.15)
Dimostrazione: Forniamo solamente una giustificazione per via grafica di questa
formula assumendo che sia presente un solo servente e che ogni cliente e servito
nell’ordine in cui arriva (FIFO); una giustificazione simile puo essere fornita nel
caso generale in cui l’ordine dei servizi e arbitrario (per ogni approfondimento si
veda il paragrafo 5.2 di [Cooper, 1981]).
Consideriamo i diagrammi di a(t) (numero totale degli utenti arrivati nel sistema
al tempo t) e di b(t) (numero totale degli utenti serviti e quindi usciti dal sistema
al tempo t) riportati nella Figura 1.2.2 nell’intervallo prefissato [0, t]. L’area
racchiusa tra i due diagrammi e data da∫ t
0n(τ)dτ (1.2.16)
o, equivalentemente dab(t)∑i=1
twi +
a(t)∑i=b(t)+1
(t− ti). (1.2.17)
Quest’ultima espressione dell’area rappresenta anche la somma dei tempi di per-
manenza nel sistema di tutti gli utenti fino al tempo t dove il primo termine
considera i tempi degli utenti entrati e usciti dal sistema prima del tempo t, men-
tre il secondo termine considera i tempi degli utenti che al tempo t sono entrati
nel sistema ma non ancora usciti.
Uguagliando e dividendo per t la (1.2.16) e la (1.2.17) si ha
∫ t
0n(τ)dτ
t=
b(t)∑i=1
twi +
a(t)∑i=b(t)+1
(t− ti)
t. (1.2.18)
M. Roma – Sistemi di Servizio e Simulazione – SAPIENZA Universita di Roma – a.a. 2018-2019
18 TEORIA DELLE CODE
Moltiplicando e dividendo per a(t) il secondo membro della (1.2.18) si ha
∫ t
0n(τ)dτ
t=a(t)
t
b(t)∑i=1
twi +
a(t)∑i=b(t)+1
(t− ti)
a(t). (1.2.19)
Ora, definendo Tt =
b(t)∑i=1
twi +
a(t)∑i=b(t)+1
(t− ti)
/a(t), la (1.2.19) puo essere
riscritta nella forma
Nt = λtTt. (1.2.20)
Si osservi ora che la Tt definita in (1.2.8) e la Tt differiscono per il solo fatto
che Tt include il tempo totale passato nel sistema da tutti gli utenti arrivati da
1 fino a b(t), ma non considera il tempo passato nel sistema dopo il tempo t
per quegli utenti che sono ancora nel sistema al tempo t; infatti questo tempo
risulta invece conteggiato nella Tt. Siamo ora interessati a passare al limite per
t → ∞ nella (1.2.19). A questo scopo osserviamo che assumendo che Nt tenda
ad un valore N finito, la differenza tra Tt e Tt puo essere trascurata in quanto
molto piccola rispetto alla somma dei tempi degli utenti arrivati da 1 fino a b(t).
Quindi, passando al limite per t → ∞ nella (1.2.19), utilizzando la (1.2.10), la
(1.2.11) e la (1.2.14) si ottiene N = λT che la formula di Little (1.2.15).
Osservazione 1.2.3 Si osservi che nella dimostrazione del Teorema di Little si
e fatto uso solamente delle quantita Nt, Tt e λt e del fatto che i limiti
limt→∞
Nt = N, limt→∞
Tt = T, limt→∞
λt = λ
esistano e siano finiti. Questo significa che il teorema continua a valere anche
se le uguaglianza tra medie temporali e medie stocastiche date dalle (1.2.10) e
(1.2.11) non dovessero valere. In questo caso, pero, le quantita N e T possono
solamente essere interpretate come medie temporali a lungo termine e non come
valori attesi delle corrispondenti variabili aleatorie.
Osservazione 1.2.4 E importante ribadire che la formula di Little ha una vali-
dita del tutto generale ed in particolare si osservi che:
• e indipendente dalle distribuzioni di probabilita dei tempi di interarrivo e
dei tempi di servizio (sistemi G/G/s).
• e indipendente dalla disciplina del servizio (la dimostrazione si riferisce al
solo caso di disciplina FIFO solo per semplicita);
• e valida per sistemi in condizioni stazionarie;
M. Roma – Sistemi di Servizio e Simulazione – SAPIENZA Universita di Roma – a.a. 2018-2019
PROBLEMATICHE DI INTERESSE E RELAZIONI FONDAMENTALI 19
• la frequenza λ deve essere la frequenza effettiva, ovvero la frequenza degli
ingressi effettivi nel sistema. Come si vedra in seguito, per alcune tipologie
di sistemi a coda (come ad esempio i sistemi a capacita limitata) poiche e
prevista la possibilita di rinuncia al servizio, la frequenza media degli arrivi
potrebbe non coincidere con la frequenza degli ingressi effettivi.
Ripetendo le considerazioni fatte nella dimostrazione del Teorema di Little, ma
sostituendo i diagrammi di a(t) e b(t) rispettivamente con i diagrammi che rap-
presentano il numero degli utenti che arrivano alla coda e il numero totale degli
utenti che escono dalla coda (e non dal sistema) si ottiene l’analoga relazione per
quanto riguarda la coda ovvero
N q = λT q (1.2.21)
Una terza importante relazione lega il valore atteso del tempo passato da un
utente nel sistema e il valore atteso del tempo passato nella coda. Vale infatti
T = T q +1
µ(1.2.22)
Questa relazione puo essere ricavata dal fatto che, per ogni singolo utente vale la
(1.1.1), ovvero twi = tqi +tsi , dove ricordiamo che twi e il tempo passato nel sistema,
tqi e il tempo passato nella coda e tsi e il tempo di servizio. Passando ai valori
attesi nella (1.1.1) e poi effettuando il limite per i→∞, si ottiene la (1.2.22).
Le tre relazioni ora ottenute (1.2.15), (1.2.21), (1.2.22) costituiscono le relazioni
fondamentali tra le quantita N , T e N q, T q e sono del tutto generali, nel senso che
valgono per qualsiasi sistema di code senza alcuna ipotesi sulle sue caratteristiche.
Esse sono molto importanti perche permettono di determinare tutte le quattro
quantita fondamentali una volta nota una di esse.
Si osservi che poiche risulta
N q =∞∑k=s
(k − s)pk =∞∑k=s
kpk − s
(1−
s−1∑k=0
pk
), (1.2.23)
nel caso di unico servente si puo ottenere facilmente una relazione tra N , N q e la
probabilita p0 che nel sistema non vi siano utenti, ovvero che il sistema sia allo
stato zero; infatti per s = 1 la (1.2.23) diventa
N q = N − (1− p0). (1.2.24)
M. Roma – Sistemi di Servizio e Simulazione – SAPIENZA Universita di Roma – a.a. 2018-2019
20 TEORIA DELLE CODE
Siamo ora in grado di ricavare, sempre nel caso di un unico servente, una relazione
tra il fattore di utilizzazione del servente ρ = λ/µ e p0.
Proposizione 1.2.5 In un sistema a coda con un unico servente in condizioni
stazionarie vale la seguente relazione
ρ = 1− p0. (1.2.25)
Dimostrazione: Moltiplicando ambo i membri della (1.2.22) per λ si ha
λT = λT q + λ/µ,
che per le relazioni fondamentali equivale a
N = N q + ρ. (1.2.26)
Ora sostituendo il valore di N q dato dalla (1.2.24) nella (1.2.26) si ottiene la
(1.2.25).
La relazione (1.2.25) ha una interpretazione immediata; infatti, poiche p0 e la
probabilita che nel sistema non vi siano utenti e che quindi il servente e inoperoso,
il complemento ad 1 di p0 rappresenta l’operosita del servente.
Questi risultati, ed in particolare la formula di Little hanno una interpretazione
immediata in riferimento a casi molto semplici; ad esempio, il traffico cittadino
nelle ore di punta si muove piu lentamente (ovvero T e grande) e le strade sono
piu affollate (ovvero N e grande). Analogamente in un fast–food, (ovvero in un
sistema con T piccolo) le sale possono essere piu piccole (ovvero N e piccolo) di
quelle di un ristorante tradizionale a parita di frequenza di arrivo dei clienti.
Sottolineamo l’importanza di disporre dei valori della probabilita pk per effettuare
l’analisi di un sistema a coda. Infatti, conoscendo pk utilizzando le (1.2.2), (1.2.3),
il Teorema di Little (1.2.15), la (1.2.21) e la (1.2.22) si possono determinare tutte
le grandezze che sono le misure di prestazione del sistema.
Per approfondimenti sulla Legge di Little, sui suoi sviluppi recenti e sulle sue
applicazioni recenti si rimanda all’articolo:
Little, John D.C.. (2011). Little’s Law as viewed on its 50th anniversary.
Operations Research, vol. 59, n. 3, 2011, pp. 536–549.
Concludiamo questo paragrafo riportando l’abstract della Distinguished Lecture
dal titolo Applications of Little’s Law che John D.C. Little ha tenuto presso
l’Aula Magna della SAPIENZA Universita di Roma in occasione del congresso
26th EURO–INFORMS, European Conference on Operational Research tenutosi
a Roma nel luglio 2013:
M. Roma – Sistemi di Servizio e Simulazione – SAPIENZA Universita di Roma – a.a. 2018-2019
PROBLEMATICHE DI INTERESSE E RELAZIONI FONDAMENTALI 21
APPLICATIONS OF LITTLE’S LAW
John D.C. Little
MIT Sloan School of Management, Mass. Inst. of Tech.
Cambridge, MA, United States
Queues are everywhere. We shall show pictures of them. Some queues contain peo-
ple, others contain things, and still others elephants. Generically, we call them all items.
Some pictures of queues are particularly interesting, or display obvious difficulties, or
are funny. Little’s Law (LL) is a property of queues. LL’s simple equation contains
three parameters. Expressed in words: (the average number of items in a queuing system
(usually denoted, L) = the arrival rate of items to the system (denoted by the Greek let-
ter, λ) × (the average time an item spends in the system (denoted W ). Thus, L = λW ,
is Little’s Law. You can tell that Little’s Law must be useful because, although it is a
simple mathematical theorem, over the years, it has acquired a distinctive name. I did
not name it. On the other hand, I haven’t objected to its name. After showing pictures
of various styles of queues, we shall prove Little’s Law in a simple but important case.
Not only do we prove it, we give a physical intuition as to why it is true. Note also
that it is exactly true. That’s the law. LL has many applications, mostly unreported.
This spring I ran a course with the title of this talk “Applications of Little’s Law.” I
sought out several guests who had applied it themselves. My colleague, Richard Larson,
told how he used LL to analyze the MIT appointment process with its input of assistant
professors and output of faculty retirements. He sought and found policy implications.
John Carrier, a consultant in the Boston area, has analyzed a medium sized furniture
maker in Kentucky that was in financial trouble. He amazed me by finding values for
LL parameters from the financial statements of the company. He used these to argue
for cutting down the number of line items in the company’s catalog, thereby saving se-
tup costs, shortening product lead times, and overcoming the cost advantages of foreign
competitors by providing faster service. Profits increased substantially. Mike George, a
long time entrepreneur and advocate of building manufacturing operations centered on
LL, sold his consulting firm, which did this, to Accenture for over $100 million. He has
now bought two manufacturing companies to run himself. Not only has he already made
them more profitable, but he also plans to collect operational data to test his scientific
theories about ways to make LL-centered manufacturing more efficient. Finally, I shall
try to make generalizations about what makes Little’s Law useful so that it can work for
you.
Plenary session – IFORS Distinguished Lecture
EURO–INFORMS – Rome 2013
Book of abstracts, p. 360.
M. Roma – Sistemi di Servizio e Simulazione – SAPIENZA Universita di Roma – a.a. 2018-2019
22 TEORIA DELLE CODE
1.3 MODELLI STOCASTICI DEI PROCESSI DI ARRIVO E DI SERVIZIO
Da quanto visto nei precedenti paragrafi, emerge chiaramente come un sistema di
code sia caratterizzato fondamentalmente da due processi stocastici : il processo
degli arrivi caratterizzato dalla distribuzione di probabilita dei tempi di interar-
rivo e il processo di servizio caratterizzato dalla distribuzione di probabilita dei
tempi di servizio.
Per definire un sistema di code e necessario specificare entrambe le distribuzioni
ora menzionate. In un sistema reale queste distribuzioni possono assumere qual-
siasi forma e per formulare un modello basato su un sistema di code che rappre-
senti un sistema reale e necessario che le distribuzioni di probabilita assunte nella
costruzione del modello siano quanto piu possibile realistiche. Al tempo stesso
esse devono essere sufficientemente semplici e matematicamente trattabili. Sulla
base di queste considerazioni la distribuzione di probabilita che maggiormente
viene presa in considerazione nella teoria delle code e la distribuzione esponenzia-
le. Cercheremo di chiarire i motivi di questa scelta attraverso l’illustrazione delle
proprieta di cui questa distribuzione gode. La principale riguarda la cosiddetta
“assenza di memoria”. Formalizzeremo questa proprieta mostrando anche che la
distribuzione esponenziale e l’unica distribuzione che gode di questa proprieta.
Per quanto riguarda l’applicazione alla teoria delle code, tale proprieta e molto
utile perche un arrivo in un sistema di code non e influenzato da quando si e
verificato l’ultimo arrivo e cosı anche per il tempo di servizio, il tempo mancante
al completamento puo essere indipendente da quando il servizio e iniziato.
Infine introdurremo il processo di Poisson, di fondamentale importanza per rap-
presentare il processo degli arrivi, descrivendo le sue proprieta fondamentali.
1.3.1 La distribuzione esponenziale e le sue proprieta
Ricordiamo innanzitutto che una variabile aleatoria continua X ha una distribu-
zione esponenziale con parametro α se la sua densita di probabilita fX(t) e data
da
fX(t) =
{αe−αt per t ≥ 0
0 per t < 0.
La funzione di distribuzione e
FX(t) = P (X ≤ t) =
{1− e−αt per t ≥ 0
0 per t < 0
e valore atteso e varianza sono date da
E(X) =1
α, V ar(X) =
1
α2.
Per comprendere bene quali implicazioni ha su un modello di code l’assunzione
che le distribuzioni dei tempi sono esponenziali, riportiamo alcune ben note pro-
M. Roma – Sistemi di Servizio e Simulazione – SAPIENZA Universita di Roma – a.a. 2018-2019
MODELLI STOCASTICI DEI PROCESSI DI ARRIVO E DI SERVIZIO 23
prieta fondamentali della distribuzione esponenziale. Sia quindi X una variabile
aleatoria avente distribuzione esponenziale ed fX(t) la corrispondente densita di
probabilita.
Proprieta E1: La densita di probabilita fX(t) e una funzione strettamente
decrescente di t (t ≥ 0)
Questa proprieta discende immediatamente dalla definizione della fX(t). Una
immediata conseguenza di questa proprieta e che, per ogni ∆t > 0 e t > 0 risulta
P (0 ≤ X ≤ ∆t) > P (t ≤ X ≤ t+ ∆t) . (1.3.1)
Questa conseguenza si ottiene ricordando che P (a ≤ X ≤ b) =
∫ b
afX(x)dx
rappresenta l’area racchiusa tra l’asse delle ascisse e il grafico della fX(t).
La (1.3.1) puo essere interpretata nel senso che e maggiore la probabilita che la
X assuma valori prossimi allo zero. In un modello di code, se X rappresenta
il tempo di servizio, il fatto che questa proprieta sia ragionevole dipende molto
dalla tipologia del servizio stesso. In alcuni casi, puo essere vero che il tempo del
servizio sia di solito molto breve con pochi casi in cui il servizio e piu lungo.
Proprieta E2: Assenza di memoria. Per ogni t > 0 e s > 0, vale la
seguente uguaglianza
P(X > s+ t
∣∣∣ X > s)
= P (X > t) . (1.3.2)
Questa proprieta si ottiene facilmente ricordando che P (X > x) = 1− FX(x) =
e−αx. Infatti, poche l’evento (X > s+ t) implica l’evento (X > s) risulta
P(X > s+ t
∣∣∣ X > s)
=P (X > s+ t,X > s)
P (X > s)=
=P (X > s+ t)
P (X > s)= e−αt = P (X > t). (1.3.3)
Questa proprieta puo essere interpretata come assenza di memoria nel senso che
se, ad esempio, il tempo di durata di un’apparecchiatura e distribuito esponen-
zialmente, allora un apparecchiatura che e gia in uso da un certo numero di ore
e “buona” tanto quanto una nuova in termini di tempo totale di durata prima
della sua rottura, ovvero l’apparecchiatura “non ricorda” di essere stata gia in
uso per un certo numero di ore.
M. Roma – Sistemi di Servizio e Simulazione – SAPIENZA Universita di Roma – a.a. 2018-2019
24 TEORIA DELLE CODE
Nell’ambito della teoria delle code, questa proprieta si puo interpretare nel seguen-
te modo: la distribuzione di probabilita del tempo che rimane fino ad un evento
(arrivo o completamento del servizio) e sempre la stessa indipendentemente da
quanto tempo e trascorso, ovvero il processo “dimentica” il passato. Per quanto
riguarda gli i tempi di interarrivo, questa proprieta descrive la situazione comune
in cui il tempo fino al prossimo arrivo non e assolutamente influenzato da quando
si e verificato l’ultimo arrivo. Per quanto riguarda i tempi di servizio questa pro-
prieta puo essere interpretata nel senso che il tempo mancante al completamento
di un servizio puo essere indipendente da quando il servizio e iniziato.
E importante notare che la distribuzione esponenziale e l’unica distribuzione con-
tinua che gode della Proprieta E2. Questo si dimostra facilmente nel seguente
modo: vogliamo far vedere che se X e una variabile aleatoria per la quale vale la
Proprieta E2, allora X e distribuita esponenzialmente. Innanzitutto osserviamo
che la relazione di assenza di memoria (1.3.2) per la (1.3.3) puo essere riscritta
P (X > s+ t) = P (X > s)P (X > t). (1.3.4)
Se ora introduciamo la funzione S(x) = P (X > x) = 1−FX(x), la (1.3.4) equivale
a scrivere
S(s+ t) = S(s)S(t),
ovvero S(x) soddisfa l’equazione funzionale
g(x+ y) = g(x)g(y). (1.3.5)
Poiche e noto che l’equazione (1.3.5) ammette come unica soluzione continua da
destra g(x) = e−αx, la dimostrazione e completata. Infatti risulta S(x) = e−αx
ovvero
FX(t) = 1− e−αt
e quindi X e distribuita esponenzialmente.
Proprieta E3: Siano X1, X2, . . . , Xn variabili aleatorie indipendenti di-
stribuite esponenzialmente con parametri α1, α2, . . . , αn. Sia Y la varia-
bile aleatoria definita da Y = min {X1, X2, . . . , Xn}. Y e distribuita
esponenzialmente con parametro α =
n∑i=1
αi.
Questa proprieta discende immediatamente dal fatto che per l’indipendenza vale
M. Roma – Sistemi di Servizio e Simulazione – SAPIENZA Universita di Roma – a.a. 2018-2019
MODELLI STOCASTICI DEI PROCESSI DI ARRIVO E DI SERVIZIO 25
P (Y > t) = P (X1 > t,X2 > t, . . . ,Xn > t)
= P (X1 > t)P (X2 > t) · · ·P (Xn > t)
= e−α1te−α2t · · · e−αnt
= e−∑ni=1 αit.
Si noti che se Xi rappresenta il tempo mancante fino a che accada un certo evento,
Y rappresenta il tempo fino a che il primo degli eventi accada.
La Proprieta E3 ha una importante interpretazione per quanto riguarda i tempi
di servizio. Supponiamo infatti di avere s serventi in parallelo ciascuno dei quali
ha tempi di servizio distribuiti esponenzialmente con lo stesso parametro µ. In
questo caso, sia r ≤ s il numero dei serventi che stanno attualmente fornendo il
servizio, e Xi il tempo che rimane per il completamento del servizio da parte di
ciascun servente (i = 1, . . . , r). Si ha che Xi, per la Proprieta E2 e distribuita
esponenzialmente con parametro αi = µ e Y che rappresenta il tempo fino al
prossimo completamento di un servizio ha distribuzione esponenziale con para-
metro rµ. Cio significa che un sistema di code con piu serventi in parallelo che
stanno attualmente operando (continuously busy servers), ciascuno con tempo
di servizio distribuito esponenzialmente di parametro µ, si comporta come un si-
stema a singolo servente con tempo di servizio distribuito esponenzialmente con
parametro rµ.
Proprieta E4: Sia X una variabile aleatoria distribuita esponenzialmente
di parametro α. Per ogni t > 0 vale
P(X ≤ t+ ∆t
∣∣∣ X > t)
= α∆t+ o(∆t)
dove o(∆t) indica un infinitesimo di ordine superiore a ∆t.
Questa proposizione si ottiene facilmente dal fatto che per ogni t ≥ 0 risulta
P (X ≤ t+ ∆t|X > t) = 1− P (X > t+ ∆t|X > t) = 1− P (X > ∆t) =
= P (X ≤ ∆t) = 1− e−α∆t
e utilizzando lo sviluppo in serie dell’esponenziale si ha
P (X ≤ t+ ∆t|X > t) = 1− 1 + α∆t+ o(∆t) = α∆t+ o(∆t).
Quindi, in virtu di questa proprieta, per piccoli valori di ∆t, si ha
P(X ≤ t+ ∆t
∣∣∣ X > t)≈ α∆t.
M. Roma – Sistemi di Servizio e Simulazione – SAPIENZA Universita di Roma – a.a. 2018-2019
26 TEORIA DELLE CODE
Interpretando X come tempo dall’ultimo evento (arrivo o completamento del
servizio) fino al prossimo evento, supponiamo che un tempo t sia gia passato
senza che l’evento sia accaduto. Dalla Proprieta E2 sappiamo che la probabilita
che l’evento accadra entro il prossimo intervallo di tempo di lunghezza fissata
∆t e una costante indipendentemente dal valore di t. La Proprieta E4 afferma
inoltre che quando il valore di ∆t e piccolo, questa probabilita costante puo
essere approssimata da α∆t, ovvero questa probabilita e proporzionale a ∆t di
un fattore α.
Proprieta E5: Siano date k variabili aleatorie X1, X2, . . . , Xk indipenden-
ti aventi identica distribuzione esponenziale di parametro α. Allora la loro
somma
Sk = X1 +X2 + · · ·+Xk
ha la seguente densita di probabilita
fSk(t) =αk
(k − 1)!e−αttk−1.
La dimostrazione di questa proprieta puo essere fatta per induzione. Infatti essa
e banalmente vera per k = 1. Supponiamo quindi che sia vera per k − 1, ovvero
che
fX1+···+Xk−1(t) =
αk−1
(k − 2)!e−αttk−2 = αe−αt
(αt)k−2
(k − 2)!
e dimostriamo che vale per k. Infatti si ha
fSk(t) = fX1+···+Xk−1+Xk(t) =
∫ ∞0
fXk(t− s) fX1+···+Xk−1(s)ds
=
∫ t
0αe−α(t−s)αe−αs
(αs)k−2
(k − 2)!ds
= αe−αt
(k − 2)!
∫ t
0(αs)k−2αds
= αe−αt(αt)k−1
(k − 1)!.
Per quanto riguarda un sistema di code, la Proprieta E5 puo essere interpretata
nel senso che se il servizio richiesto da un cliente richiede l’impiego di k serventi in
serie i cui tempi di servizio sono identicamente distribuiti esponenzialmente con
parametro α (oppure l’impiego dello stesso servente k volte), il tempo di servizio
totale seguira la distribuzione della somma dei tempi servizio.
M. Roma – Sistemi di Servizio e Simulazione – SAPIENZA Universita di Roma – a.a. 2018-2019
MODELLI STOCASTICI DEI PROCESSI DI ARRIVO E DI SERVIZIO 27
La distribuzione di probabilita avente per densita di probabilita la fSk si chiama
distribuzione di Erlang di parametri α e k che, ad eccezione della restrizione
dell’interezza di k, coincide con la distribuzione Gamma.
1.3.2 Il processo di Poisson
In questo paragrafo introduciamo il processo di Poisson che ha, in generale, una
grande importanza per due aspetti fondamentali: innanzitutto molti fenomeni
fisici possono essere rappresentati attraverso tale processo; inoltre, il processo di
Poisson gode di interessanti ed utili proprieta che consentono numerose semplifi-
cazioni nella trattazione analitica. In riferimento alla teoria delle code, il processo
di Poisson e un importante strumento per la modellizzazione dei processi di ar-
rivo. Prima di definire un processo di Poisson, introduciamo un concetto che
risultera molto utile nel seguito.
Definizione 1.3.1 Un processo stocastico {X(t), t ≥ 0} e detto processo di
conteggio (counting process) se X(t) rappresenta il numero totale di eventi
che accadono fino all’istante t.
E un processo che “conta” il numero totale di aventi accaduti fino al tempo t. Si
tratta di un processo stocastico a tempo continuo e a stati discreti. Esempi di
processi di conteggio sono:
a) il numero delle persone entrate in un supermercato fino al tempo t
b) il numero di persone nate fino al tempo t
c) il numero di goal realizzati da un giocatore nella sua carriera fino al tempo t
Non e invece un processo di conteggio il numero delle persone presenti in un
supermercato al tempo t.
Si verifica immediatamente che per un processo di conteggio valgono le seguenti
proprieta:
1. X(t) ≥ 0 per ogni t ≥ 0
2. X(t) e a valori interi
3. se s ≤ t allora X(s) ≤ X(t)
4. per s < t, X(t) − X(s) e il numero degli eventi che sono accaduti nell’in-
tervallo (s, t).
M. Roma – Sistemi di Servizio e Simulazione – SAPIENZA Universita di Roma – a.a. 2018-2019
28 TEORIA DELLE CODE
Riportiamo, di seguito, due definizioni che introducono due concetti caratteriz-
zanti un processo di conteggio.
Definizione 1.3.2 Un processo di conteggio ha incrementi indipendenti se
il numero degli eventi che accadono in intervalli di tempo disgiunti sono
indipendenti.
Quindi gli incrementi indipendenti corrispondono all’indipendenza delle variabili
aleatorie X(s+ ∆s)−X(s) e X(s′+ ∆s′)−X(s′) se gli in intervalli (s , s+ ∆s)
e (s′ , s′ + ∆s′) sono due intervalli disgiunti.
L’assunzione che un processo ha incrementi indipendenti e ragionevole per l’esem-
pio a), ma forse non lo e per l’esempio b) perche se X(t) e molto grande, il numero
di nascite tra t e t+ ∆t tende ad essere grande. Nell’esempio c) potrebbe essere
ragionevole.
Definizione 1.3.3 Un processo di conteggio ha incrementi stazionari se la
distribuzione del numero degli eventi che accadono in un intervallo di tempo
dipende solo dall’ampiezza dell’intervallo.
Quindi un processo ha incrementi stazionari se il numero degli eventi nell’interval-
lo (t, t+∆t) ha la stessa distribuzione per ogni t > 0, ovvero, per ogni ∆s fissato,
e per ogni s, s′ ≥ 0, le variabili aleatorie X(s+ ∆s)−X(s) e X(s′ + ∆s)−X(s′)
hanno la stessa distribuzione di probabilita.
L’assunzione che un processo ha incrementi stazionari sarebbe ragionevole nell’e-
sempio a) solo se non ci fossero orari di punta con maggiore afflusso. Nell’esempio
b) sarebbe ragionevole solamente se la popolazione della terra fosse costante,
mentre nell’esempio c) non e ragionevole perche il giocatore invecchia col passare
degli anni !
M. Roma – Sistemi di Servizio e Simulazione – SAPIENZA Universita di Roma – a.a. 2018-2019
MODELLI STOCASTICI DEI PROCESSI DI ARRIVO E DI SERVIZIO 29
Definizione 1.3.4 Un processo di conteggio {X(t), t ≥ 0} e un processo di
Poisson di tasso λ > 0 se valgono
i) X(0) = 0
ii) il processo ha incrementi indipendenti
iii) il numero di eventi che accadono in ogni intervallo di tempo di ampiezza
t (dato da X(s+ t)−X(s) ) ha distribuzione di Poisson di parametro
λt, ovvero per ogni s, t ≥ 0 risulta
P (X(s+ t)−X(s) = n) = e−λt(λt)n
n!, n = 0, 1, . . . (1.3.6)
Ovviamente la iii) implica che un processo di Poisson ha incrementi stazionari ed
inoltre vale E (X(t)) = λt e questa e la ragione per cui λ e anche detta frequenza
media alla quale gli eventi accadono.
Riportiamo di seguito una definizione equivalente di processo di Poisson che puo
risultare piu agevole da applicare in alcuni casi.
Definizione 1.3.5 Un processo di conteggio X(t) e un processo di Poisson
se e solo se per ogni t ≥ 0 valgono
i) X(0) = 0
ii) il processo ha incrementi indipendenti
iii) P (X(t+ ∆t)−X(t) = 1) = λ∆t+ o(∆t)
iv) P (X(t+ ∆t)−X(t) ≥ 2) = o(∆t)
La iii) afferma che per ogni t, la probabilita che un evento accada nell’intervallo
(t, t + ∆t) e proporzionale secondo il parametro λ all’ampiezza dell’intervallo a
meno di un infinitesimo di ordine superiore a ∆t, mentre la iv) afferma che la
probabilita che due o piu eventi accadano nell’intervallo suddetto e pari a o(∆t).
Le due definizioni ora fornite (Definizione 1.3.4 e Definizione 1.3.5) di processo
di Poisson sono equivalenti. La dimostrazione di questa equivalenza e piuttosto
tecnica e viene omessa per brevita e si rimanda, ad esempio, a [Ross, 2003a] o a
[Billingsley, 1979].
Passiamo ora a considerare una importantissima relazione che esiste tra distri-
buzione esponenziale e processo di Poisson. A tale scopo consideriamo una suc-
cessione di eventi. Sia T1 il tempo di attesa affinche si verifichi il primo evento e
M. Roma – Sistemi di Servizio e Simulazione – SAPIENZA Universita di Roma – a.a. 2018-2019
30 TEORIA DELLE CODE
per k ≥ 1 sia Tk il tempo di attesa tra l’evento (k− 1)–esimo e l’evento k–esimo,
ovvero
{Tk, k ≥ 1} (1.3.7)
e la successione di variabili aleatorie degli intertempi tra due eventi successivi
(cioe degli intervalli di tempo tra due eventi successivi). Se definiamo
Sn = T1 + T2 + · · ·+ Tn,
si ha che Sn rappresenta il tempo necessario affinche l’evento n–esimo accada
(dove, convenzionalmente, si pone S0 = 0).
Torniamo ora a considerare il processo {X(t), t ≥ 0} del numero degli eventi che
accadono nell’intervallo [0,t]. In termini di Sn, esso puo essere scritto come
X(t) = max{n | Sn ≤ t}, (1.3.8)
ed inoltre valgono le seguenti coincidenze tra eventi:
{X(t) ≥ n} = {Sn ≤ t}
ed inoltre
{X(t) = n} = {X(t) ≥ n} ∩ {X(t) < n+ 1} = {Sn ≤ t} ∩ {Sn+1 > t}.
Teorema 1.3.1 Sono equivalenti le seguenti affermazioni:
i) il processo {X(t), t ≥ 0} definito in (1.3.8) e un processo di Poisson
di tasso λ.
ii) le variabili Ti definite in (1.3.7) sono indipendenti, identicamente di-
stribuite con distribuzione esponenziale di parametro λt, ovvero
P (Ti ≤ t) = 1− e−λt, i = 1, 2, . . .
Anche in questo caso omettiamo per brevita la verifica di questo risultato per il
quale si fa riferimento, ad esempio, a [Ross, 2003a] e [Billingsley, 1979].
In virtu di questo risultato, poiche le Ti sono variabili aleatorie indipendenti,
identicamente distribuite con distribuzione esponenziale, abbiamo gia dimostrato
(cfr. Proprieta E5) che Sn ha distribuzione di Erlang di parametri λ e n.
Il risultato del Teorema 1.3.1 si puo intuitivamente dedurre dal fatto che l’assun-
zione degli incrementi stazionari e indipendenti di fondo equivale al fatto che il
M. Roma – Sistemi di Servizio e Simulazione – SAPIENZA Universita di Roma – a.a. 2018-2019
MODELLI STOCASTICI DEI PROCESSI DI ARRIVO E DI SERVIZIO 31
processo, in ogni istante Si, effettua un “restart”, cioe il processo da ogni punto
e indipendente da tutto cio che accade prima (incrementi indipendenti) ed ha la
stessa distribuzione del processo originale (incrementi stazionari); in altre parole,
il processo non ha memoria e quindi gli intertempi tra due eventi successivi devono
essere distribuiti esponenzialmente.
Il Teorema 1.3.1 evidenzia l’importante equivalenza tra il fatto che il numero di
punti che cadono in un intervallo prefissato di lunghezza t ha distribuzione di
Poisson e il fatto che le lunghezze degli intervalli che separano punti contigui
hanno identica distribuzione esponenziale. Questa proprieta e particolarmente
utile per descrivere il comportamento probabilistico degli arrivi in un sistema
di code quando gli intertempi di arrivo sono distribuiti esponenzialmente con
parametro λ. In questo caso X(t) rappresenta il numero di arrivi fino al tempo t,
dove λ e la frequenza media degli arrivi. Percio, nel caso di tempi di interarrivo
esponenziali, si dice anche che si hanno arrivi secondo un processo di Poisson di Arrivi
poissonianiparametro λ (arrivi poissoniani).
Si puo ragionare in maniera analoga per quanto riguarda i tempi di servizio,
definendo X(t) come il numero dei servizi portati a termine in un tempo t.
Analizziamo ora un’ulteriore proprieta del processo di Poisson importante nell’am-
bito della teoria delle code. Sia {X(t), t ≥ 0} un processo di Poisson di parametro
λ e supponiamo che ogni evento che accade possa essere classificato di tipo A o
di tipo B. Supponiamo inoltre che ciascun evento sia di tipo A con probabilita p
e di tipo B con probabilita 1− p, indipendentemente da tutti gli altri eventi. Ad
esempio i clienti che arrivano in un negozio possono essere classificati in uomini
con probabilita 12
e donne con probabilita 12. Si indichi con XA(t) e con XB(t)
rispettivamente il numero degli eventi di tipo A e di tipo B che accadono in [0, t]
(ovviamente risulta X(t) = XA(t) + XB(t) ). Il processo X(t) prende nome di
processo aggregato e i due processi XA(t) e XB(t) prendono nome di processi
componenti o processi disaggregati. Questo si generalizza ad un numero finito di
processi componenti. Infatti, sia {X(t), t ≥ 0} un processo di Poison di tasso λ.
Supponiamo di classificare ogni evento come evento di tipo 1, 2, . . . , k con pro-
babilita rispettivamente p1, p2, . . . , pk, con∑k
i=1 pi = 1. Siano X1(t), . . . , Xk(t)
i processi componenti che contano il numero di eventi rispettivamente di classe
1, 2, . . . , k accaduti fino al tempo t. Allora vale la seguente proposizione.
Proposizione 1.3.6 Se {X(t), t ≥ 0} e un processo di Poisson, allora i pro-
cessi componenti X1(t), . . . , Xk(t) sono processi di Poisson di tasso rispetti-
vamente λ1 = λp1, λ2 = λp2, . . . , λk = λpk. Inoltre i processi componenti
sono indipendenti.
M. Roma – Sistemi di Servizio e Simulazione – SAPIENZA Universita di Roma – a.a. 2018-2019
32 TEORIA DELLE CODE
Si verifica, inoltre facilmente che vale anche il viceversa del risultato della Pro-
posizione 1.3.6, come riportato nella seguente proposizione.
Proposizione 1.3.7 Se X1(t), . . . , Xk(t) sono processi di Poisson in-
dipendenti di tasso rispettivamente λ1, . . . , λk, aggregati in un unico
processo
X(t) = X1(t) + . . .+Xk(t),
si ha che X(t) e un processo di Poisson di tasso λ = λ1 + · · ·+ λk.
Nell’ambito della teoria delle code il risultato della Proposizione 1.3.7 puo essere
cosı interpretata: supponiamo che ci siano un certo numero r di differenti tipi di
clienti tali che i clienti di ciascun tipo arrivano secondo un processo di Poisson
di parametro λi, (i = 1, . . . , r). Assumendo che i processi siano indipendenti, la
proprieta afferma che il processo di arrivo aggregato, ovvero il processo di arrivo
di tutti i clienti senza tener conto del tipo, e ancora un processo di Poisson di
parametro λ =r∑i=1
λi.
Osservazione 1.3.8 Il risultato della Proposizione 1.3.6 ha la seguente impor-
tante applicazione nello studio dei sistemi di code. Supponiamo che i clienti
arrivano al sistema di code secondo un processo di Poisson di parametro λ e che
ci sia la possibilita che alcuni clienti rinuncino ad entrare nel sistema (ad esempio
se vedono la coda molto lunga). E quindi possibile caratterizzare gli utenti se-
condo due tipi: quelli che entrano nel sistema (con probabilita p) e quelli che non
entrano nel sistema (con probabilita 1 − p). Il risultato della Proposizione 1.3.6
permette di affermare che ciascun tipo di cliente arriva al sistema secondo un
processo di Poisson di tasso rispettivamente λp e λ(1 − p). Percio il modello
poissoniano puo continuare ad essere utilizzato per studiare il sistema a coda
relativamente ai soli clienti che effettivamente entrano nel sistema.
1.3.3 Altri modelli per processi di arrivo
Abbiamo visto come il modello poissoniano sia adatto a rappresentare il proces-
so degli arrivi in un sistema di code. Infatti, in molti casi, esso costituisce un
modello molto aderente alla realta. Tuttavia, esistono casi in cui il modello pois-
soniano non puo essere adottato ed e necessario considerare anche altre tipologie
di processi di arrivi. Ricordiamo infatti, le caratteristiche che vengono assunte
considerando il modello poissoniano:
M. Roma – Sistemi di Servizio e Simulazione – SAPIENZA Universita di Roma – a.a. 2018-2019
MODELLI STOCASTICI DEI PROCESSI DI ARRIVO E DI SERVIZIO 33
1. gli utenti arrivano al sistema uno alla volta,
2. il processo ha incrementi indipendenti,
3. il proceso ha incrementi stazionari.
La prima proprieta esclude ovviamente gli arrivi in gruppi. La seconda proprieta
afferma che il numero degli arrivi nell’intervallo (t, t+s] e indipendente dal numero
di arrivi prima di t e anche dai tempi in cui questi arrivi si sono verificati; questa
proprieta potrebbe essere violata se, ad esempio, un numero molto elevato di
arrivi nell’intervallo di tempo [0, t] puo causare il fenomeno di “balking”, ovvero
la rinuncia all’ingresso nel sistema da parte di alcuni utenti nell’intervallo di
tempo (t, t+ s] perche il sistema e molto affollato. Per affrontare tale problema,
in realta, e sufficiente applicare il risultato della Proposizione 1.3.6 come descritto
nell’Osservazione 1.3.8 e quindi non c’e la necessita di introdurre nuove tipologie
di modelli per il processo degli arrivi.
Anche la terza proprieta potrebbe essere in generale violata perche essa implica
che la frequenza degli arrivi non dipende dal tempo t, e quindi, ad esempio,
dall’orario della giornata; invece, in molti casi, e noto che la frequenza media
degli arrivi λ puo variare con il tempo e quindi si puo avere λ = λ(t).
Queste considerazioni ci portano a considerare altri modelli per i processi di arrivi
per affrontare le situazioni descritte al primo e al terzo punto:
• il processo di Poisson composto, ovvero arrivi in gruppi (batch);
• il processo di Poisson non stazionario, ovvero un processo di Poisson in cui
il parametro λ varia al variare del tempo t.
Il processo di Poisson composto (arrivi in gruppi)
In alcuni sistemi reali gli utenti possono arrivare in gruppi e non uno alla volta.
Per trattare questo caso e sufficiente definire X(t) come il numero dei gruppi di
utenti che arrivano fino al tempo t. Se i tempi di interarrivo dei gruppi sono
variabili aleatorie indipendenti identicamente distribuite secondo la distribuzione
esponenziale, si puo anche in questa situazione utilizzare un modello Poissoniano
cercando poi una distribuzione discreta che rappresenti la dimensione dei gruppi.
Si assume cosı che i gruppi arrivano secondo un processo di Poisson e che il numero
degli utenti in ciascun gruppo e una variabile aleatoria discreta. Formalmente si
definisce Y (t) come il numero totale di utenti individuali arrivati fino al tempo t
e gi il numero degli utenti che fanno parte dell’i-esimo gruppo e si ha
Y (t) =
X(t)∑i=1
gi , t ≥ 0.
M. Roma – Sistemi di Servizio e Simulazione – SAPIENZA Universita di Roma – a.a. 2018-2019
34 TEORIA DELLE CODE
Il processo di Poisson non stazionario
In molti sistemi reali la frequenza media degli arrivi puo dipendere dal tempo e
in questo caso i tempi di interarrivo Tk non sono identicamente distribuiti. Un
modello comunemente utilizzato in queste situazioni e il cosiddetto processo di
Poisson non stazionario o processo di Poisson non omogeneo.
Definizione 1.3.9 Un processo di conteggio X(t) e un processo di Poisson
non stazionario se e solo se per ogni t ≥ 0 valgono
i) X(0) = 0
ii) il processo ha incrementi indipendenti
iii) P (X(t+ ∆t)−X(t) = 1) = λ(t)∆t+ o(∆t)
iv) P (X(t+ ∆t)−X(t) ≥ 2) = o(∆t)
La funzione λ(t) prende nome di funzione intensita e sara tanto piu grande negli
intervalli nei quali il numero atteso degli arrivi e grande. Data la funzione λ(t),
si puo definire la funzione Λ(t) =
∫ t
0λ(y)dy.
Si riporta di seguito un risultato che mostra che la distribuzione del numero degli
arrivi nell’intervallo (s, s+ t] per un processo di Poisson non stazionario dipende
da s e da t, mentre, come sappiamo, in un processo di Poisson esso dipende
solamente dall’ampiezza dell’intervallo.
Teorema 1.3.2 Sia {X(t), t ≥ 0} un processo di Poisson non stazionario.
Allora risulta
P (X(s+ t)−X(s) = n) = e−b(s,t)[b(s, t)]n
n!, n = 0, 1, . . .
dove b(s, t) = Λ(s+ t)− Λ(s) =∫ s+ts λ(y)dy.
Sulla base di questo risultato si ha che X(s+ t)−X(s) e una variabile aleatoria
distribuita secondo Poisson con media b(s, t) = Λ(s+t)−Λ(s) e la Λ(t) e chiamata
funzione valore medio del processo di Poisson non omogeneo.
E utile confrontare questo teorema con la Definizione 1.3.5 di processo di Pois-
son osservando come in un processo di Poisson non stazionario sia esplicita la
dipendenza da s.
M. Roma – Sistemi di Servizio e Simulazione – SAPIENZA Universita di Roma – a.a. 2018-2019