Sistemi Servizio Simulazione - uniroma1.itroma/didattica/SSS11-12/parteL.pdf2 TEORIA DELLE CODE...

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 2011-12

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.

Le metodologie della simulazione saranno studiate in termini generali e con rife-

rimenti specifici ai sistemi di servizio. Al termine verrà introdotto l’utilizzo di un

ambiente software specializzato 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

conoscenza 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 (ele-

menti di statistica inferenziale saranno comunque riportati in queste note).

Al termine di ciascuna delle due parti è riportata una bibliografia essenziale.

M. Roma – Sistemi di Servizio e Simulazione – SAPIENZA Università di Roma – a.a. 2011-2012

iv PREFAZIONE

Molte utili informazioni sulla Teoria delle code sono disponibili sul sito

http://web2.uwindsor.ca/math/hlynka/queue.html.


Introduzione

Un sistema può essere definito come una collezione di entità (macchine, persone,

etc.) che agiscono e interagiscono per il raggiungimento di uno scopo. Per stu-

diare “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̀

oggi 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 pre-

fissato al quale devono appartenere le variabili1. I modelli matematici sono in

grado di rappresentare moltissime e diverse realtà del mondo reale, e permettono

di ottenere efficientemente una soluzione ottima del problema considerato, o co-

munque soluzioni 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

1Lo studente ha acquisito una buona familiarità con modelli di questo tipo nei corsi di Ricerca Operativa


vi INTRODUZIONE

“replicare” le caratteristiche del problema 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

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 funzionale

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 effettuare la validazione del modello matematico in alterna-tiva alla sperimentazione diretta che spesso risulta impraticabile o troppo

costosa;

• permette di analizzare e studiare modelli stocastici, ovvero modelli in cuialcune grandezze sono influenzate da fenomeni di natura aleatoria.

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,

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 studi-

are 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 simu-

lazione saranno studiate in termini generali e al termine della parte metodologica

verrà introdotto l’uso di un “simulatore ad eventi discreti”, ovvero un ambiente

software specializzato che permette di implementare modelli di simulazione. Si

tratta di ARENA c© prodotto dalla Rockwell Software, un simulatore oggi larga-

mente utilizzato, che attraverso un’interfaccia grafica consente sia di realizzare

un modello di simulazione, sia di effettuare i diversi run di una simulazione e

di analizzare i risultati ottenuti. È possibile scaricare gratuitamente la “student

edition” di ARENA c©.


1Teoria delle code

L’esperienza quotidiana ci mette in continuo rapporto con la necessità di richiedere

l’erogazione di un servizio a soggetti o enti 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


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.


GENERALITÀ 3

1.1 GENERALITÀ

Un Sistema di Servizio (o sistema a coda) è una struttura caratterizzata dall’arrivo

casuale di utenti detti clienti ciascuno dei quali richiede lo svolgimento di un’ope- Sistema di

Serviziorazione 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 soddis-

fare 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 sis-

tema, 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 analitica-

mente, ma quando le tipologie sono più complicate come, ad esempio, più code

presenti 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.


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)

potrebbe sembrare abbastanza astratta e applicabile solamente ad alcuni casi

particolari. Al contrario, i sistemi a coda presentano un vasto campo di appli-

cazione 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 rapp-

resentabili mediante sistemi a coda. Si pensi, ad esempio, agli autoveicoli

in attesa ai caselli autostradali o ai semafori, agli autocarri o alle navi in

attesa di essere caricati o scaricati, agli aerei in attesa di decollare o at-

terrare. 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, pacchetti

di dati vengono trasmessi lungo le connessioni da un nodo al successivo con


GENERALITÀ 5

possibilità di attesa (buffering) quando la domanda in ingresso eccede la ca-

pacità. 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:

• PopolazioneI 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 serventiIn 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 arrivoIn un sistema a coda deve essere specificato lo schema di arrivo che de-

scrive 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,


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 diinterarrivo 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 servizioLo 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 aleato-

ria 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 dis-

tribuzione 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 sistemaIl 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 codaLa disciplina della coda specifica l’ordine rispetto al quale gli utenti vengono

serviti. Le più comunemente usate sono basate sui seguenti criteri: FIFOCriteri

FIFO,

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”)


GENERALITÀ 7

Il processo base che avviene in un sistema a coda è il seguente: clienti che

richiedono un servizio sono generati nel tempo dalla popolazione, entrano nel

sistema e raggiungono la coda. Ad un certo momento, un cliente viene selezion-

ato dalla coda secondo la disciplina della coda. Il servizio richiesto è effettuato da Tempo di

permanenza

nel sistema

un servente e successivamente a ciò il cliente lascia il sistema. Quindi se indichi-

amo con twi il tempo passato complessivamente dall’i-esimo utente nel sistema si

ha

twi = tqi + t

si . (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

Fig. 1.1.1 Schema di un sistema a coda con una sola coda e tre serventi in parallelo

Coda

Serventi

Popolazione

Coda

Fig. 1.1.2 Schema di un sistema a coda con due code e quattro serventi in parallelo


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


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

sigle) che, come abbiamo già detto, corrisponde ad avere la capacità del sistema

infinita, la popolazione infinita e la disciplina della coda basata sul criterio FIFO

(ovvero corrisponderebbe a scrivere M/M/1/∞/∞/FIFO); tale modello M/M/1assume che sia gli intertempi di arrivo, 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 intertempi di arrivo distribuiti esponenzialmente e non

pone nessuna specificazione sulla distribuzione dei tempi di servizio.


10 TEORIA DELLE CODE

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 diFrequenza

media degli

arrivi

arrivi di utenti nell’unità di tempo. Indicheremo con λ la frequenza media degli

arrivi.

Si definisce velocità di servizio il numero medio di utenti per il quali è espletatoVelocità di

servizio il servizio nell’unità di tempo. Indicheremo con µ la velocità di servizio.

Si definisce fattore di utilizzazione dei serventi ρ il rapporto tra la frequenza mediaFattore di

utilizzazione

dei serventi

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 (λ).


PROBLEMATICHE DI INTERESSE E RELAZIONI FONDAMENTALI 11

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 t

ai e t

si 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 Supponiamo che in un sistema di servizio l’intervallo di tempo tra due arrivi

successivi di clienti (tempi di interarrivo) siano rispettivamente 3′, 7′, 4′, 10′ e 6′ come illustrato

nella Figura 1.2.1. Quindi nei 30 minuti presi in esame abbiamo un tempo medio di interarrivo

pari a 6 minuti. Perciò il numero medio di arrivi di utenti nell’unità di tempo è di 5 in 30

minuti, ovvero 1/6, quindi λ = 0.1666 utenti al minuto. Analogamente se il numero medio di

utenti per il quali è espletato il servizio è pari a 4 al minuto, ovvero µ = 4, allora il tempo medio

di servizio è 1/4 di minuto.

30’

3’ 7’ 4’ 10’ 6’

1 2 3 4 5

Fig. 1.2.1 Schema degli arrivi dell’Esempio 1.2.1

Si definisce stato di un sistema a coda al tempo t il numero di clienti presenti nel Stato 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 attesa Lunghezza

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.



1.2.2 Misure di prestazione

Nell’analisi di un sistema di servizio vengono prese in considerazione alcune

grandezze fondamentali come misure di prestazione. Nella maggior parte dei

casi di interesse si è interessati a valutare queste grandezze assumendo che il sis-

tema abbia 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 iniziato da poco ad essere operativo, lo stato del sistema sarà forte-

mente 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.Condizioni

transitorie Tuttavia, in molti casi, trascorso un tempo sufficientemente grande, il sistema

diviene indipendente dallo stato iniziale e si dice che il sistema ha raggiunto con-

dizioni stazionarie o equilibrio (steady–state). Si osservi subito che questo nonCondizioni

stazionarie può accadere se risulta ρ ≥ 1 nel qual caso lo stato del sistema cresce indefiniti-vamente 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. Per effettuare l’analisi di un sistema in condizioni di stazionarietà si

fa uso delle seguenti quantità fondamentali:

pk : probabilità che k utenti siano presenti nel sistema

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.

Innanzitutto 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 quanto è presente una dipendenza da un parametro. Ovvero, formal-

mente, {n(t)} e {nq(t)} sono processi stocastici a tempo continuo e le famiglie divariabili aleatorie {twi } e {tqi } sono processi stocastici a tempo discreto.Inoltre, 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

tempo t sia k. Ora, dalla definizione di valore atteso di una variabile aleatoria

discreta si ricava immediatamente

E(n(t)) =∞∑

k=0

kpk(t) (1.2.1)



E(nq(t)) =∞∑

k=s+1

(k − s)pk(t). (1.2.2)

Se inoltre indichiamo con ftwi (t) e ftqi(t) rispettivamente le densità di probabilità

delle variabili aleatorie continue twi (tempo passato nel sistema) e tqi (tempo pas-

sato nella coda), si ha

E(twi ) =

∫ ∞

0t ftwi (t)dt (1.2.3)

E(tqi ) =

∫ ∞

0t ftqi

(t)dt. (1.2.4)

Siamo interessati ai casi in cui, per valori di t molto grandi, le probabilità pk(t)

rimangano intorno ad un valore. La maggior parte dei sistemi a coda di interesse

raggiungono una situazione di equilibrio, indipendentemente dalla stato iniziale.

Assumeremo, quindi, che esista il seguente limite

limt→∞

pk(t) = pk, k = 0, 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 condizioni stazionarie.

A questo punto 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.5)

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 ).

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

FIFO, ma i risultati che otterremo sono validi (e facilmente ottenibili) per qualsi-

asi 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.

1

2

3

4

5

6

7

8

a(t)

b(t)

t

n(t)

wt2wt1

t 1 t 2

Fig. 1.2.2 Illustrazione di una coda

Ad ogni istante di tempo t, ovviamente risulta n(t) = a(t)− b(t). Relativamenteall’intervallo [0, t] possiamo considerare le seguenti medie temporali

Nt =1

t

∫ t

0n(τ)dτ (1.2.6)

Tt =1

a(t)

a(t)∑

i=1

twi (1.2.7)

λt =a(t)

t. (1.2.8)

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.



La maggior parte dei sistemi a coda di interesse sono ergodici nel senso che vale

inoltre la seguente uguaglianza3

limt→∞

Nt = limt→∞

E(n(t)) (1.2.9)

con probabilità 1. Ovvero, per t sufficientemente grande, vale l’uguaglianza tra

la media temporale Nt e il valore atteso N . Analogamente, vale anche

limt→∞

Tt = limi→∞

E(twi ) (1.2.10)

con probabilità 1.

Si osservi che le (1.2.9) e (1.2.10) rappresentano uguaglianze tra medie temporali

a lungo termine rappresentate da limt→∞Nt e da limt→∞ Tt e medie stocastiche

date dai valori attesi.

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.9) si può ottenere N q come

limt→∞

N qt = limt→∞E(nq(t)) (1.2.11)

e analogamente a T nella (1.2.10) si può ottenere T q come

limt→∞

T qt = limi→∞

E(tqi ), (1.2.12)

dove le uguaglianze valgono con probabilità 1.

Per quanto riguarda la frequenza media degli arrivi nell’intervallo [0, t] suppor-

remo che valga

λ = limt→∞

λt = limt→∞

E (a(t))

t, (1.2.13)

avendo assunto che tali limiti esistano.

3Non viene fornita una rigorosa giustificazione matematica delle assunzioni che seguono in quanto sareb-

bero richiesti strumenti matematici tecnici che vanno oltre lo scopo di queste note



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 diTeorema di

Little Little dal nome di J. D. C. Little che per primo nel 1961 ne diede una formu-

lazione rigorosa. Successivamente ci sono stati numerosi tentativi di semplificare

la dimostrazione di questo risultato. Nel 1974 S. Stidham ne ha fornito una di-

mostrazione semplice e rigorosa in ipotesi del tutto generali. Tale risultato, anche

detto formula (o legge) 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.14)

Dimostrazione: Forniamo solamente una giustificazione per via grafica di questa

formula assumendo 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.15)

o, equivalentemente da

b(t)∑

i=1

twi +

a(t)∑

i=b(t)+1

(t− ti). (1.2.16)

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.15) e la (1.2.16) si ha

∫ t

0n(τ)dτ

t=

b(t)∑

i=1

twi +

a(t)∑

i=b(t)+1

(t− ti)

t. (1.2.17)



Moltiplicando e dividendo per a(t) il secondo membro della (1.2.17) 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.18)

Ora, definendo T̃t =

b(t)∑

i=1

twi +

a(t)∑

i=b(t)+1

(t− ti)/a(t), la (1.2.18) può essere

riscritta nella forma

Nt = λtT̃t. (1.2.19)

Si osservi ora che la Tt definita in (1.2.11) e la T̃t differiscono per il solo fatto

che T̃t 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.18). A questo scopo osserviamo che assumendo che Nt tendaad un valore N finito, la differenza tra Tt e T̃t 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.18), utilizzando la (1.2.9), la(1.2.10) e la (1.2.13) si ottiene N = λT che la formula di Little (1.2.14).

Osservazione 1.2.2 Si osservi che nella dimostrazione del Teorema di Little si

è fatto uso solamente delle quantità Nt, Tt e λt e del fatto che limt→∞Nt = N ,

limt→∞ Tt = T e limt→∞ λt = λ. Questo significa che il teorema continua a valere

anche se le uguaglianza tra medie temporali e medie stocastiche date dalle (1.2.9)

e (1.2.10) 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.3 È importante ribadire che la formula di Little ha una va-

lidità del tutto generale ed in particolare si osservi che:

• è indipendente dalle distribuzioni di probabilità dei tempi di interarrivo edei tempi di servizio (sistemi G/G/s).

• è indipendente dalla disciplina del servizio (la dimostrazione si riferisce alsolo caso di disciplina FIFO solo per semplicità);

• è valida per sistemi in condizioni stazionarie;

• la frequenza λ deve essere la frequenza effettiva, ovvero la frequenza degliingressi 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.20)

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.21)

Questa relazione può essere ricavata dal fatto che, per ogni singolo utente vale la

(1.1.1), ovvero twi = tqi +t

si , dove ricordiamo che t

wi 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.21).

Le tre relazioni ora ottenute (1.2.14), (1.2.20), (1.2.21) 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.22)

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.22) diventa

N q = N − (1− p0). (1.2.23)

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.4 In un sistema a coda con un unico servente in condizioni

stazionarie vale la seguente relazione

ρ = 1− p0. (1.2.24)

Dimostrazione: Moltiplicando ambo i membri della (1.2.21) per λ si ha

λT = λT q + λ/µ,

che per le relazioni fondamentali equivale a

N = N q + ρ. (1.2.25)

Ora sostituendo il valore di N q dato dalla (1.2.23) nella (1.2.25) si ottiene la

(1.2.24).

La relazione (1.2.24) 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.

Esempio 1.2.5 Consideriamo un sistema di controllo di flusso di dati su rete che deve inviare

pacchetti supponendo che il tempo dell’acnowledgement sia trascurabile. Sulla rete devono

trovarsi N pacchetti quindi non appena il pacchetto i è arrivato a destinazione, il pacchetto

i + N è immediatamento introdotto nella rete. Poiché il numero di pacchetti nel sistema è

sempre N la formula di Little ci permette di affermare che la frequenza di arrivo dei pacchetti

nel sistema λ e il tempo medio di permanenza di un pacchetto nella rete sono collegati dalla

relazione N = λT . Quindi se nella rete c’è congestione e T aumenta, λ deve diminuire. Inoltre se

la rete è congestionata e in grado di consegnare solo λ pacchetti per unità di tempo, aumentando

N avrebbe come risultato solamente un aumento del tempo di permanenza nella rete T .

Si deve comunque prestare molta attenzione nell’applicare la formula di Little

ad alcuni casi particolari, alla luce di quanto riportato nella Osservazione 1.2.2.

Riportiamo di seguito un esempio in cui il sistema non raggiunge l’equilibrio.



Esempio 1.2.6 Un pacchetto arriva su un linea di trasmissione ogni k secondi (il primo pac-

chetto arriva al tempo 0). Tutti i pacchetti hanno stessa lunghezza e richiedono αk secondi

per la trasmissione con α < 1. Il tempo affinché un pacchetto arrivi a destinazione è pari a p

secondi. La frequenza di arrivo è λ = 1/k e poiché i pacchetti arrivano ad intervalli regolari, non

c’è tempo di attesa in coda quindi il tempo T che un pacchetto rimane nel sistema è T = αk+p.

Applicando la formula di Little si ottiene N = λT = α+ p/k.

Questo esempio necessita di una corretta interpretazione in quanto nel sistema

descritto n(t) è una funzione deterministica del tempo t e non converge a nessun

valore, quindi non si raggiunge la condizione di equilibrio. Tuttavia, la formula

di Little può avere una valida interpretazione anche in questo caso, nel senso che

N non può essere inteso come nella (1.2.5), ma solamente come media temporale

su tempi lunghi ovvero N = limt→∞

∫ t0 n(τ)dτ

t.

Concludiamo questo paragrafo soffermandoci sull’importanza di disporre dei va-

lori della probabilità pk per effettuare l’analisi di un sistema a coda. Infatti,Importante

conoscere

pk

conoscendo pk utilizzando le (1.2.1), (1.2.2), il Teorema di Little (1.2.14), la

(1.2.20) e la (1.2.21) si possono determinare tutte le grandezze che sono le misure

di prestazione del sistema.


MODELLI STOCASTICI DEI PROCESSI DI ARRIVO E DI SERVIZIO 21

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 esponen-

ziale. Cercheremo di chiarire i motivi di questa scelta attraverso l’illustrazione

delle proprietà di cui questa distribuzione gode. La principale riguarda la cosid-

detta “assenza di memoria”. Formalizzeremo questa proprietà mostrando anche

che la distribuzione esponenziale è l’unica distribuzione che gode di questa pro-

prietà. 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 T ha una distribu-

zione esponenziale con parametro α se la sua densità di probabilità fT (t) è data

da

fT (t) =

{αe−αt per t ≥ 00 per t < 0.

La funzione di distribuzione è

FT (t) = P (T ≤ t) ={1− e−αt per t ≥ 00 per t < 0

e valore atteso e varianza sono date da

E(T ) =1

α, V ar(T ) =

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-



prietà fondamentali della distribuzione esponenziale. Sia quindi T una variabile

aleatoria avente distribuzione esponenziale ed fT (t) la corrispondente densità di

probabilità.

Proprietà E1: La densità di probabilità fT (t) è una funzione strettamente

decrescente di t (t ≥ 0)

Questa proprietà discende immediatamente dalla definizione della fT (t). Una

immediata conseguenza di questa proprietà è che, per ogni ∆t > 0 e t > 0 risulta

P (0 ≤ T ≤ ∆t) > P (t ≤ T ≤ t+∆t) . (1.3.1)

Questa conseguenza si ottiene ricordando che P (a ≤ T ≤ b) =∫ b

afT (x)dx rap-

presenta l’area racchiusa tra l’asse delle ascisse e il grafico della fT (t).

La (1.3.1) può essere interpretata nel senso che è maggiore la probabilità che

la T assuma valori prossimi allo zero. In un modello di code, se T 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 è 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(T > s+ t

∣∣∣ T > s)= P (T > t) . (1.3.2)

Questa proprietà si ottiene facilmente ricordando che P (T > x) = 1 − FT (x) =e−αx. Infatti, poché l’evento (T > s+ t) implica l’evento (T > s) risulta

P(T > s+ t

∣∣∣ T > s)

=P (T > s+ t, T > s)

P (T > s)=

=P (T > s+ t)

P (T > s)= e−αt = P (T > 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.



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 intertempi di arrivo, 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 T è una variabile aleatoria per la quale vale la

Proprietà E2, allora T è distribuita esponenzialmente. Innanzitutto osserviamo

che la relazione di assenza di memoria (1.3.2) per la (1.3.3) può essere riscritta

P (T > s+ t) = P (T > s)P (T > t). (1.3.4)

Se ora introduciamo la funzione S(x) = P (T > x) = 1−FT (x), la (1.3.4) equivalea 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

FT (t) = 1− e−αt

e quindi T è distribuita esponenzialmente.

Proprietà E3: Siano T1, T2, . . . , Tn variabili aleatorie indipendenti distri-

buite esponenzialmente con parametri α1, α2, . . . , αn. Sia U la variabile

aleatoria definita da U = min {T1, T2, . . . , Tn}. U è distribuita esponenzial-

mente con parametro α =n∑

i=1

αi.

Questa proprietà discende immediatamente dal fatto che per l’indipendenza vale



P (U > t) = P (T1 > t, T2 > t, . . . , Tn > t)

= P (T1 > t)P (T2 > t) · · ·P (Tn > t)= e−α1te−α2t · · · e−αnt

= e−∑n

i=1αit.

Si noti che se Ti rappresenta il tempo mancante fino a che accada un certo evento,

U 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 ilservizio, e Ti il tempo che rimane per il completamento del servizio da parte di

ciascun servente (i = 1, . . . , r). Si ha che Ti, per la Proprietà E2 è distribuita espo-

nenzialmente con parametro αi = µ e U che rappresenta il tempo fino al prossimo

completamento di un servizio ha distribuzione esponenziale con parametro rµ.

Ciò significa che un sistema di code con più serventi in parallelo che stanno at-

tualmente operando (continuously busy servers), ciascuno con tempo di servizio

distribuito esponenzialmente di parametro µ, si comporta come un sistema a sin-

golo servente con tempo di servizio distribuito esponenzialmente con parametro

rµ.

Proprietà E4: Sia T una variabile aleatoria distribuita esponenzialmente di

parametro α. Per ogni t > 0 vale

P(T ≤ t+∆t

∣∣∣ T > 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 (T ≤ t+∆t|T > t) = 1− P (T > t+∆t|T > t) = 1− P (T > ∆t) == P (T ≤ ∆t) = 1− e−α∆t

e utilizzando lo sviluppo in serie dell’esponenziale si ha

P (T ≤ t+∆t|T > t) = 1− 1 + α∆t+ o(∆t) = α∆t+ o(∆t).

Quindi, in virtù di questa proprietà, per piccoli valori di ∆t, si ha

P(T ≤ t+∆t

∣∣∣ T > t)≈ α∆t.



Interpretando T 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 T1, T2, . . . , Tk indipendenti

aventi identica distribuzione esponenziale di parametro α. Allora la loro

somma

Sk = T1 + T2 + · · ·+ Tkha 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, ovveroche

fT1+···+Tk−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) = fT1+···+Tk−1+Tk(t) =

∫ ∞

0fTk(t− s) fT1+···+Tk−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.



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 diconteggio (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’intervallo(s, t).



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 in-

dipendenti.

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’intervallo

(t, t+∆t) ha la stessa distribuzione per ogni t > 0.

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 !

Definizione 1.3.4 Un processo di conteggio {X(t), t ≥ 0} è un processo diPoisson 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


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

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 cheaccadono 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 Poissondi tasso λ.

ii) le variabili Ti definite in (1.3.7) sono indipendenti, identicamente di-

stribuite con distribuzione esponenziale di parametro λ, 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

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. Adesempio i clienti che arrivano in un negozio possono essere classificati in uomini

con probabilità 12e donne con probabilità 1

2. 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.

Si verifica, inoltre facilmente che se X1(t), . . . ,Xk(t) sono processi di Poisson

indipendenti 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.6 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.7 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.6permette di affermare che ciascun tipo di cliente arriva al sistema secondo un

processo di Poisson di tasso rispettivamente λp e λ(1 − p). Perciò il modellopoissoniano 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 pro-

cesso 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:

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.7.

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:

• il processo di Poisson non stazionario, ovvero un processo di Poisson in cuiil parametro λ varia al variare del tempo t;

• il processo di Poisson composto, ovvero arrivi in gruppi (batch).



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.8 Processo di Poisson non stazionario

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


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 aleatoriadistribuita secondo Poisson con media b(s, t) = Λ(s+t)−Λ(s) e la Λ(t) è chiamatafunzione 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.



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.



1.4 PROCESSI DI NASCITA E MORTE

Molti sistemi a coda possono essere ben rappresentati mediante i cosiddetti pro-

cessi di nascita e morte che sono importanti processi in teoria della probabilità

che hanno applicazioni in diverse aree. In particolare, l’evoluzione nel tempo

del numero degli utenti presenti in un sistema di servizio può essere descritta

attraverso un tale processo ed inoltre la determinazione delle probabilità che nel

sistema siano presenti n utenti (pn), che come abbiamo sottolineato alla fine del

paragrafo 1.2.3 è di fondamentale importanza, risulta facile se l’evoluzione nel

tempo dello stato di un sistema è rappresentato attraverso un processo di nascita

e morte.

Informalmente, dato un insieme di persone o oggetti (aventi caratteristica co-

mune), si dice che si verifica una nascita ogni qualvolta un nuovo membro si

aggiunge all’insieme e una morte quando un membro lascia l’insieme. Si parla di

processo di sole nascite se si verificano solamente nascite e non morti e di processo

di sole morti se si verificano solamente morti e non nascite.

Nel contesto della teoria delle code una nascita si riferirà ad un arrivo di un

utente nel sistema e una morte si riferirà ad una uscita di utente dal sistema

(dopo che il servizio sia stato espletato).

In questo paragrafo, dopo aver definito formalmente un processo di nascita e

morte esamineremo le proprietà fondamentali di questi processi; successivamente

queste proprietà saranno applicate per la determinazione delle misure di presta-

zione nel caso dei sistemi a coda più significativi.

1.4.1 Caratterizzazione dei processi di nascita e morte

Supponiamo che N(t) sia un processo stocastico a tempo continuo e con spazio

degli stati discreto costituito dai numeri interi non negativi. N(t) può essere in-

terpretato come il numero dei membri di un certo insieme al tempo t. Indichiamo

con pn(t) la probabilità che al tempo t lo stato sia n ovvero che al tempo t ci

siano n elementi nell’insieme, cioè pn(t) = P (N(t) = n).

Definiamo con pn,m(∆t) la probabilità che il processo raggiunga lo stato m alProbabilità

di transizio-

ne

tempo t+∆t condizionata al fatto che al tempo t si trova nello stato n,

pn,m(∆t) = P(N(t+∆t) = m

∣∣∣ N(t) = n).

Tale probabilità pn,m(∆t) prende nome di probabilità di transizione e può essere

interpretata come la probabilità che l’insieme, costituito da n elementi al tempo

t, sia costituito da m elementi al tempo t+∆t.

Introduciamo, ora, formalmente il concetto di processo di nascita e morte.


PROCESSI DI NASCITA E MORTE 35

Definizione 1.4.1 Processo di nascita e morte

Un processo stocastico N(t) che assume solamente valori interi non negativi

si dice processo di nascita e morte se le probabilità di transizione pn,m(∆t)

non dipendono esplicitamente dal tempo t, dipendono solo dal valore dello

stato al tempo t e non dai valori assunti in istanti precedenti e soddisfano le

seguenti condizioni:

pn,n+1(∆t) = λn∆t+ o(∆t) per n ≥ 0pn,n−1(∆t) = µn∆t+ o(∆t) per n ≥ 1 (1.4.1)pn,m(∆t) = o(∆t) per |m− n| ≥ 2

dove λn ≥ 0, µn ≥ 0 e o(∆t) è un infinitesimo di ordine superiore a ∆t.

La dipendenza dal valore dello stato attuale e non da quelli passati è un con- Proprietà

di Markovcetto che viene formalizzato come proprietà di Markov4. Le condizioni (1.4.1)

possono essere interpretate nel seguente modo: a meno di infinitesimi di ordine

superiore a ∆t, la probabilità che nell’intervallo [t, t+∆t] si verifichi una nascita

non dipende da t, ma è proporzionale all’ampiezza dell’intervallo (ovvero alla du-

rata ∆t) secondo un coefficiente che può dipendere dallo stato attuale, ma non

da quelli passati. Analogamente, la probabilità che nell’intervallo [t, t + ∆t] si

verifichi una morte è proporzionale alla durata ∆t secondo un coefficiente che

può dipendere dallo stato attuale, ma non da quelli passati. Il coefficiente λn Coefficiente

di natalità

e mortalità

è chiamato coefficiente di natalità, i

Sistemi Servizio Simulazione - uniroma1.itroma/didattica/SSS11-12/parteL.pdf2 TEORIA DELLE CODE...

Documents

Transcript of Sistemi Servizio Simulazione - uniroma1.itroma/didattica/SSS11-12/parteL.pdf2 TEORIA DELLE CODE...