Introduzione
VI
prestazione, si basano sullo studio dell’evoluzione di opportuni processi stocastici
definiti a partire dalle caratteristiche del modello. Per una classe molto importante di
modelli a rete di code, la classe delle reti Markoviane, il comportamento in
condizioni di stazionarietà è analizzabile esattamente mediante lo studio del processo
Markoviano associato alla rete. Gli indici di prestazione per le reti Markoviane si
possono ricavare, sotto opportune ipotesi, dalla soluzione del sistema di equazioni di
bilanciamento relative al processo. La dimensione di questo sistema lineare coincide
con il numero di stati del processo Markoviano associato alla rete. Poiché il numero
degli stati del processo Markoviano risulta dipendere esponenzialmente dai parametri
della rete, la complessità, sia di tempo che di spazio, di questo tipo di analisi risulta
talmente elevata da limitarne notevolmente l’applicabilità [Per94].
Per una sottoclasse delle reti Markoviane, le reti in forma-prodotto, sono state
derivate, partendo principalmente dalle proprietà del processo Markoviano associato,
delle forme chiuse, dette appunto forme prodotto, per la soluzione del sistema di
equazioni di bilanciamento [Bal94b]. Per i modelli di reti di code con blocco in
forma-prodotto, che tuttavia costituiscono una ristretta classe, sono stati proposti in
letteratura efficienti algoritmi per la valutazione di un insieme di indici di prestazione
la complessità computazionale è polinomiale nel numero di componenti del modello
[Bal95].
I metodi analitici approssimati consentono una valutazione approssimata degli
indici di prestazione ad un costo, sia di spazio che di tempo, relativamente basso. I
principi su cui si basano i metodi approssimati sono molto diversi tra loro. Alcuni
metodi, ad esempio, si basano sull’analisi di un modello semplificato rispetto
all’originale, altri metodi invece sfruttano delle proprietà particolari di alcune classi
di modelli.
La maggior parte dei metodi analitici approssimati sono metodi euristici,
ovvero metodi per i quali non è possibile stabilire a priori una limitazione per l’errore
introdotto.
L’interesse verso i metodi analitici approssimati è giustificato principalmente
dalla difficoltà di generare risultati esatti, mediante i metodi analitici esatti, o stime
con un’accuratezza controllabile, ottenibili con metodi di simulazione.
La credibilità dei risultati forniti dai metodi approssimati deve essere tuttavia
valutata attentamente mediante un’analisi sperimentale che, oltre a determinare il
livello di accuratezza, è utile per individuare delle proprietà tipiche del metodo che
consentono di definire i migliori casi di applicabilità per il metodo stesso.
Questa tesi offre una rassegna ed un dettagliato confronto tra alcuni tra i più
interessanti metodi per l’analisi approssimata di modelli a reti di code con blocco
Introduzione
VII
presenti in letteratura. In totale vengono presentati dieci metodi approssimati di cui
quattro per modelli a rete di code aperte e sei per modelli a rete di code chiuse.
Il lavoro è articolato in due fasi: nella prima fase i metodi presentati vengono
analizzati ed implementati, nella seconda fase per ognuno di questi metodi viene
fornita una valutazione complessiva basata su un’analisi sperimentale.
Nella fase di analisi ed implementazione ogni metodo viene prima descritto ed
analizzato nel dettaglio, evidenziando le caratteristiche dell’approssimazione
introdotta, e successivamente viene illustrata l’implementazione proposta, mettendo
in luce i vari aspetti tecnici ad essa connessi e fornendo una valutazione della
complessità, sia di tempo che di spazio, dell’algoritmo.
Nella fase di valutazione ogni metodo viene valutato su una specifica classe di
test che tiene conto sia delle caratteristiche generali del modello che delle proprietà
particolari del metodo.
In alcuni casi viene inoltre fornita un’analisi comparativa tra metodi che
consentono l’analisi di una stessa classe di modelli.
Le difficoltà principali affrontate in questo lavoro sono legate sia ai problemi
tipici dell’implementazione di algoritmi di calcolo numerico, quali, ad esempio, il
controllo delle instabilità numeriche, sia alla definizione di una opportuna
metodologia per l’analisi dei risultati.
Il lavoro svolto ha in sostanza due obiettivi. Il primo è quello di fornire un
insieme di algoritmi che consentono un’analisi approssimata di una vasta classe di
modelli a reti di code con blocco.
Il secondo obiettivo è quello di fornire una valutazione complessiva dei metodi
utile per comprenderne la validità effettiva e soprattutto per individuarne i limiti alla
loro applicabilità.
Tutto il software sviluppato in questo lavoro, che comprende, oltre agli
algoritmi che implementano i metodi descritti, anche un generatore di modelli di
simulazione scritto per effettuare validazioni nel lavoro di analisi sperimentale, va ad
integrare un ambiente di analisi esatta sviluppato in un precedente lavoro [Ila96].
Il pacchetto software, denominato QNBA (Queuing Network with Blocking
Analyzer), presenta caratteristiche di modularità che consentono di estendere
semplicemente l’ambiente di analisi ad altri metodi sia esatti che approssimati.
Questa tesi è organizzata in cinque capitoli.
Nel primo capitolo vengono introdotti i modelli a rete di code in generale,
focalizzando in particolare l’attenzione sui modelli di reti con capacità finita delle
code. Vengono inoltre presentati alcuni esempi di applicazione dei modelli a reti di
code con blocco.
Introduzione
VIII
Nel secondo capitolo sono descritte le principali tecniche di analisi dei modelli
a reti di code. Particolare attenzione è stata dedicata ai metodi analitici esatti in
quanto offrono degli spunti fondamentali per lo sviluppo dei metodi approssimati. A
conclusione del capitolo vengono riportate alcune importanti proprietà di equivalenza
del modelli a rete di code.
Nel terzo capitolo vengono presentati quattro metodi per l’analisi approssimata
di modelli a rete di code aperti con blocco. Il capitolo è organizzato in due parti
principali: nella prima parte vengono presentati due metodi per modelli a topologia
tandem, e nella seconda parte sono presentati due metodi per modelli a topologie più
generali. La presentazione del metodo è articolata in tre fasi: la fase di descrizione,
dove il metodo viene descritto formalmente, la fase di implementazione, dove viene
descritto l’algoritmo che implementa il metodo, e la fase di analisi dei risultati, dove
vengono riportati i risultati dell’analisi sperimentale. Viene inoltre presentata
un’analisi comparativa tra due diversi metodi per reti a topologia tandem.
Nel quarto capitolo vengono presentati sei metodi per l’analisi approssimata di
modelli a rete di code chiusi con blocco. I primi tre metodi presentati sono relativi a
modelli a topologia ciclica, gli altri tre metodi consentono l’analisi di modelli a
topologia arbitraria. Il capitolo è organizzato come il precedente. Vengono
presentate, infine, tre analisi comparative tra diversi metodi.
Nel quinto ed ultimo capitolo viene descritto l’ambiente per l’analisi di reti di
code con blocco QNBA. Ogni singola funzionalità dell’analizzatore viene descritta
riportando, inoltre, gli aspetti implementativi più rilevanti. In conclusione vengono
descritte le modalità esatte di utilizzo dell’analizzatore ed alcuni esempi pratici.
Il modello
1
&$3,72/235,02
,OPRGHOOR
,QWURGX]LRQH
La classe di modelli basati sulla teoria delle code si presta allo studio di tutti
quei sistemi reali nei quali l’accesso alle risorse da parte dei clienti (o utenti) del
sistema può creare fenomeni di congestione e quindi di accodamento [Kle76, Per94].
Nei sistemi reali di questo tipo il numero massimo di clienti a cui è consentito
accodarsi in attesa di accedere ad una risorsa (capacità della risorsa) è
necessariamente finito. Questo aspetto, a seconda delle caratteristiche del sistema,
può influenzarne il comportamento in maniera più o meno rilevante. Esempi tipici di
sistemi di questo tipo sono i sistemi di elaborazione, i sistemi di produzione, sistemi
di comunicazione e di traffico. In un sistema di elaborazione, ad esempio, le sue
risorse, come i processori, le memorie e i canali I/O, sono soggette a richieste di
utilizzo (i clienti) da parte di utenti o programmi. Nei sistemi di produzione, invece,
le risorse sono tipicamente delle macchine adibite alla lavorazione di prodotti i quali
costituiscono i clienti del sistema. Nei sistemi di comunicazione le risorse sono i
canali di comunicazione, mentre i messaggi costituiscono i clienti del sistema.
Analogamente nei sistemi di traffico le risorse sono le vie di comunicazione e i mezzi
di trasporto (treni, vetture o aerei) sono i clienti del sistema.
Per lo studio di quei sistemi in cui le capacità delle risorse risultano
caratterizzare in qualche modo l’evoluzione del sistema, sono stati introdotti i
modelli di code a capacità finita. In questo lavoro ci occupiamo di una particolare
classe di modelli basati sulla teoria delle code ovvero dei modelli a UHWLGLFRGH e ci
concentriamo in particolare sulla sottoclasse di modelli a reti di code con capacità
finita delle code. Questi modelli, grazie soprattutto alla loro flessibilità, si prestano
allo studio di diverse classi di sistemi reali come sistemi di produzione, traffico e
comunicazione ed inoltre offrono un valido strumento per la valutazione delle
prestazioni di sistemi di elaborazione.
Il modello
2
),*85$6LVWHPDDFRGDVLQJROD
In questo capitolo introduciamo i modelli a reti di code. Analizziamo prima di
tutto i modelli a coda singola introducendo così gli elementi e i concetti fondamentali
per la trattazione dei modelli a reti di code. Successivamente ci occupiamo dei
modelli a reti di code nei loro diversi aspetti concentrandoci in particolare sui
modelli a reti di code con code a capacità limitata. Infine riportiamo alcune
significative applicazioni per questi modelli.
0RGHOOLDFRGDVLQJROD
Il modello più semplice che possiamo studiare nella teoria delle code è quello
costituito da una coda singola, illustrato nella figura 1. Immaginiamo un sistema
costituito da un distributore di servizi e da un flusso di clienti che intende usufruire di
tali servizi. Se uno o più clienti arrivano mentre il distributore è occupato, essi sono
costretti ad attendere il loro servizio andando così a formare una coda. Ciò che ci
interessa è l’evolversi nel tempo di questo sistema.
Per l’analisi di questo modello, sono chiaramente necessarie delle
informazioni legate alle caratteristiche del distributore di servizi e del flusso dei
clienti. Consideriamo perciò modelli stocastici nei quali le grandezze sono
rappresentate da variabili aleatorie. Da un punto di vista formale possiamo descrivere
completamente il modello a coda singola (o semplicemente coda) con una quintupla
(A,B,s,c,D), A/B/s/c/D secondo la notazione introdotta da Kendall [Ken53], dove:
A: denota la distribuzione di probabilità relativa al processo di arrivo dei
clienti
B: denota la distribuzione di probabilità relativa al processo di servizio del
distributore di servizi
s: è il numero di serventi nel distributore di servizi ed è un intero positivo
c: è la capacità della coda ed è un intero non negativo
D: denota la disciplina di servizio applicata ai clienti in coda
In particolare A è la distribuzione di probabilità della variabile aleatoria (v.a.) X che
Il modello
3
indica il tempo che intercorre tra due arrivi successivi, e B è la distribuzione di
probabilità della variabile aleatoria Y che indica il tempo di servizio. Queste
distribuzioni possono essere generali e permettono di modellare diverse situazioni
reali. Tuttavia, nei modelli analitici risolvibili efficientemente, le distribuzioni
utilizzate appartengono a particolari classi. Questo è dovuto al fatto che per
distribuzioni generali esistono pochi risultati teorici, ovvero pochi metodi che
consentono un’analisi esatta del modello. Le principali distribuzioni che trattiamo
sono:
x Esponenziale negativa (M). Se ad esempio il tempo di interarrivo (o di
servizio) è una v.a. X con distribuzione esponenziale di parametro O, la
funzione di distribuzione dei tempi di interarrivo è data da:
prob(Xdt) = 1-e- t con t>0 e O5+
Il valore medio 1/O è l’unico parametro necessario per descrivere tale
distribuzione. La distribuzione esponenziale è detta anche distribuzione
Markoviana per la sua proprietà di assenza di memoria. In virtù di questa
proprietà abbiamo, ad esempio, che la probabilità che un cliente completi il
proprio servizio ad un istante t è indipendente dal tempo di servizio già
utilizzato dal cliente.
x Fasi esponenziali (PHn). Per descrivere questa importante famiglia di
distribuzioni [Per94] facciamo riferimento alla distribuzione dei tempi di
servizio di un sistema a coda singola. Nell’entità di servizio abbiamo un
numero n di fasi dove la fase i ha distribuzione esponenziale di parametro Pi,
1didn. Un cliente inizia il proprio servizio dalla fase i con probabilità Di,
1didn. Una volta completato questo servizio il cliente si sposta sulla fase j con
),*85$(VHPSLRGLHQWLWjGLVHUYL]LRDIDVLHVSRQHQ]LDOL
Il modello
4
),*85$(QWLWjGLVHUYL]LR&R[LDQDDQIDVL
probabilità aij, 1di,jdn, oppure con probabilità ai0 completa il suo servizio.
Devono valere le seguenti condizioni per le probabilità:
D
i
i
n
i
a
¦ ¦ dd
1
01 1 e a con 1 i nij
j=1
n
Per una descrizione completa di una distribuzione a n fasi esponenziali sono
quindi necessari n2+2n-1 parametri, cioè n2+n-1 probabilità e n valori medi
relativi alle fasi esponenziali. La figura 2 illustra un esempio di entità di
servizio a 5 fasi esponenziali. Le distribuzioni a fasi esponenziali sono
chiaramente una generalizzazione della distribuzione esponenziale che può
essere vista come una distribuzione ad una sola fase. Poiché le n fasi
esponenziali sono indipendenti tra loro, le distribuzioni a fasi ereditano dalla
distribuzione esponenziale la proprietà Markoviana. Tra le distribuzioni a fasi
esponenziali di particolare interesse per questo lavoro vi sono quella &R[LDQD e
quella ,SHUHVSRQHQ]LDOH.
Nella distribuzione Coxiana le fasi sono disposte serialmente come illustrato
nella figura 3. Un cliente inizia il proprio servizio dalla prima fase e di qui con
probabilità a1 prosegue verso la fase 2, mentre con probabilità 1-a1 completa il
servizio. Dalla seconda fase si ripete il procedimento e completata
),*85$(QWLWjGLVHUYL]LR,SHUHVSRQHQ]LDOHDQIDVL
Il modello
5
),*85$'LVWULEX]LRQH*(FRQSDUDPHWULUHP
eventualmente anche l’ultima fase del servizio, il cliente termina il suo
servizio. Per descrivere una distribuzione Coxiana a n fasi denotata da Cn sono
sufficienti per quanto visto 2n-1 parametri, ovvero i tassi Pi con 1didn, e le
probabilità ai con 1di<n. L’interesse verso la famiglia di distribuzioni Coxiane
è dovuto, oltre al fatto che essa consente di modellare molte situazioni reali,
anche al fatto che una distribuzione di probabilità arbitraria può essere
approssimata da una opportuna distribuzione Coxiana. Più precisamente ogni
distribuzione con trasformata di Laplace razionale può essere rappresentata
esattamente da una distribuzione Coxiana [Per94]. Nella figura 4 è
rappresentata un’entità di servizio di tipo Iperesponenziale a n fasi denotata da
Hn. In questo caso il cliente con probabilità Di, 1didn, riceve un servizio
esponenziale con tasso Pi e quindi esce dall’entità di servizio. Per descrivere
questa distribuzione sono quindi necessari 2n-1 parametri: n-1 probabilità Di
(una è ricavabile delle altre) e i tassi Pi con 1didn
x Esponenziale Generalizzata (GE). Si tratta di una diversa generalizzazione
della distribuzione esponenziale [Per94, Kou89a]. In un servizio di tipo GE un
cliente riceve con probabilità r un servizio esponenziale di parametro rm,
mentre con probabilità 1-r non riceve alcun servizio (fig. 5). Se 1/P e C sono
rispettivamente valore medio e coefficiente di variazione della distribuzione
GE allora m e r sono dati da:
m = e P r
C
2
12
dove assumiamo che C2>1. La distribuzione GE risulta della forma:
Il modello
6
prob e
( )X t
C
t
Cd
1
2
12
2
12
con t 0 e P5+
Ricordiamo che il coefficiente di variazione è definito come rapporto tra la
radice della varianza e il valore medio, di conseguenza una distribuzione GE è
completamente determinata dai suoi primi due momenti. La distribuzione
esponenziale è chiaramente un caso particolare della distribuzione
generalizzata esponenziale con lo stesso valore medio e ponendo il coefficiente
di variazione uguale a 1.
I momenti della distribuzione, oltre a fornire i parametri caratterizzanti, forniscono
informazioni parziali sulla distribuzione stessa. Per le distribuzioni esponenziali
facciamo spesso riferimento come parametro al reciproco del valore medio, che
indichiamo con O per i processi di arrivo e P per quelli di servizio, che indica
rispettivamente il tasso medio di arrivo e di servizio.
Una volta stabilite le caratteristiche del modello, possiamo occuparci di
studiarne il comportamento. Lo strumento principale per tale studio è il SURFHVVR
VWRFDVWLFR. Un processo stocastico è definito come una famiglia di v.a. {Xt °tT}
definite in uno spazio di probabilità :. Le v.a. Xt si ottengono in corrispondenza di
un parametro t variabile nell’insieme T. L’insieme T può essere discreto o continuo,
si parla in tal caso di processi stocastici rispettivamente a WHPSRGLVFUHWR e a WHPSR
FRQWLQXR. Le v.a. Xt assumono valori, detti stati delle v.a., in un insieme E detto
VSD]LRGHJOLVWDWL. Anche lo spazio degli stati può essere discreto o continuo. Una
volta che vengono definiti opportunamente tutti i parametri del processo,
l’evoluzione del sistema nel tempo si riconduce all’evoluzione, cioè al variare di t,
del processo stocastico. In particolare possiamo pensare che gli stati del processo
rappresentino tutte le possibili situazioni in cui il sistema si può trovare, allora
l’evoluzione del processo stocastico, che è descritta dalle distribuzioni di probabilità
relative alle v.a. Xt, corrisponde all’evoluzione nel tempo del sistema. Il nostro
interesse sarà esclusivamente rivolto sui processi stocastici con uno spazio degli stati
discreto e a tempo continuo. Una particolare classe di processi stocastici per cui
l’analisi risulta relativamente semplice è quella dei processi di Markov (o processi
Markoviani) [Kle76]. Questi processi godono della proprietà di assenza di memoria
in virtù della quale l’evoluzione del processo ad un certo tempo t non tiene conto di
ciò che è avvenuto nei tempi precedenti. Per un processo di Markov a tempo
continuo e con uno spazio degli stati discreto si ha, per ogni sequenza di valori
Il modello
7
t0<t1<...<tn<t, per ogni n>0 e per ogni j,i0,..,inE:
prob{Xt=j:Xt0=i0,...,Xtn=in}=prob{ Xt=j:Xtn=in}
Per i processi Markoviani sono possibili due analisi dell’evoluzione: l’DQDOLVL
WUDQVLHQWH che è relativa ad un orizzonte temporale finito e l’DQDOLVLVWD]LRQDULD,
l’unica che consideriamo in questo lavoro, che è invece relativa al comportamento in
condizioni di equilibrio. L’analisi transiente fornisce la distribuzione di probabilità di
stato del processo dipendente dal tempo e dallo stato iniziale, mentre quella
stazionaria fornisce la distribuzione di probabilità di stato indipendente dal tempo.
L’analisi stazionaria di un processo Markoviano a tempo continuo è relativamente
semplice. Sia Q una matrice di cardinalità E¨», detta JHQHUDWRUHLQILQLWHVLPDOH R
PDWULFHGHLWDVVLGLWUDQVL]LRQH, i cui elementi hanno il seguente significato:
q S S
tasso di transizione to S allo stato S
q S S
S S S
S SS S S
( )
dallo sta
- ( )
S
,
,
, ,
,
c c
cc
®°°¯
c zc
c ¦ E E
Se il sistema modellato dal processo Markoviano raggiunge l’equilibrio, esiste una
distribuzione stazionaria per gli stati del processo stesso. Sia SS la probabilità che il
sistema si trovi nello stato S ad un istante di tempo arbitrario. E’ stato dimostrato
[Kle76] che sotto opportune ipotesi il vettore S con componenti SS, con SE, si
ottiene come soluzione della seguente equazione matriciale:
QS = (1.1)
dove è un vettore di zeri di dimensione E¨», soggetto alla condizione di
normalizzazione:
SsS¦ E 1 (1.2)
Una particolare categoria di processi Markoviani, che si presta a modellare
diversi sistemi a coda singola, è quella dei SURFHVVLQDVFLWDPRUWH. Questi processi
hanno la particolarità che transizioni sono ammesse solo tra stati “adiacenti”. In
particolare E=1 e le uniche transizioni ammesse sono dallo stato i agli stati i+1 e i-1,
con iE. Un processo Markoviano a spazio discreto può essere rappresentato dal
Il modello
8
'LDJUDPPDGHJOLVWDWLSHUXQDFRGD0 1)&)6
GLDJUDPPDGHJOLVWDWL che è un grafo i cui nodi rappresentano gli stati del processo e
gli archi indicano le possibili transizioni tra stati e sono etichettati con i relativi tassi
di transizione. La classe dei processi Markoviani consente di modellare una vasta
classe di sistemi basati sulla teoria delle code. In particolare con modelli aventi
distribuzioni di servizio e interarrivo esponenziali e Coxiane, in virtù della proprietà
di assenza di memoria di tali distribuzioni, possiamo sempre ricorrere a
processiMarkoviani. In generale, nel caso di modelli con distribuzioni delle variabili
aleatorie non esponenziali o Coxiane, l’ evoluzione può essere descritta da processi
stocastici non necessariamente Markoviani e la cui analisi risulta assai più
complessa.
La definizione degli elementi che caratterizzano il processo Markoviano,
ovvero la matrice Q e lo spazio E, dipende chiaramente delle caratteristiche del
sistema che intendiamo studiare. Consideriamo a titolo di esempio una coda del tipo
M/M/1/N/FCFS in cui la distribuzione dei tempi di interarrivo è esponenziale con
tasso O, la distribuzione dei tempi di servizio è anch’ essa esponenziale ma con tasso
P ed il singolo servente ha una disciplina di servizio FCFS, ovvero il servizio dei
clienti avviene nell’ ordine di arrivo. Possiamo definire uno stato S per tale modello
semplicemente come il numero di clienti presenti nella coda. Per descrivere
l’ evoluzione nel tempo di tale modello, definiamo un semplice processo Markoviano
omogeneo a spazio discreto e a tempo continuo. Lo spazio degli stati E di questo
processo è dato semplicemente dall’ insieme di naturali ^ `0 1, ,..., N . Si può dimostrare
[Kle76] che tale processo fa’ parte della particolare categoria dei processi nascita-
morte. La figura 4 mostra il diagramma degli stati associato a tale processo.
Il generatore infinitesimale è dato da:
Q
ª
¬
«
«
«
«
«
«
º
¼
»
»
»
»
»
»
O P
O O P P
O O P P
O P
( )
( )
0
0
2 2 2
Il modello
9
Dal sistema lineare (1.1) otteniamo :
S OPSn n= con n = 1,..,N
1
ovvero:
S S OPn = con n = 1,..,N
n
0
§
©¨
·
¹¸
dove S0 è ricavato dalla condizione di normalizzazione (1.2):
S O
P
0
0
1
§
©¨
·
¹¸ ¦ iiN
Per processi Markoviani a tempo continuo la cui soluzione è definita dal
sistema di equazioni (1.1) si fa ricorso alle diverse tecniche numeriche proposte in
letteratura per le soluzioni di sistemi lineari [Bin88, Bev87]. Tuttavia la complessità
computazionale e di spazio di memoria di tali tecniche è tale da restringerne
l’applicabilità al caso di spazio E di dimensioni relativamente piccole.
0RGHOOLDUHWHGLFRGH
Un modello più complesso di quello appena descritto è quello costituito da più
code collegate tra loro a formare unaUHWHGLFRGH. Tale modello rappresenta il
sistema come un insieme di risorse interconnesse utilizzate da un insieme di utenti.
Intuitivamente una rete di code può essere vista come un grafo orientato i cui nodi
rappresentano un sistema a coda singola, detti anche FHQWULGLVHUYL]LR, e gli archi i
possibili spostamenti che un cliente può effettuare all’interno della rete da un centro
di servizio ad un altro.
La complessità di questo modello dipende dalle diverse proprietà che
definiamo sia per le singole code che per la rete nella sua interezza. L’evolversi di
questo modello nel tempo è determinato sia dal comportamento delle singole code e
sia dall’interazione tra di esse.
Consideriamo un grafo (rete) con M nodi etichettati che rappresentano
altrettanti centri di servizio costituiti da un’area di servizio vero e proprio e da una
Il modello
10
coda. Ad un arco del grafo (i,j) che unisce i nodi i e j, con 1di,jdM, è associato un
valore pij che denota la probabilità che un cliente, una volta terminato il servizio al
nodo i, si diriga al nodo j. Inoltre con probabilità pi0, un cliente, terminato il servizio
al nodo i, lascia la rete definitivamente. Analogamente possiamo definire p0i la
probabilità che un cliente giunga al nodo i dall’esterno della rete, si parla in questo
caso di DUULYLHVRJHQL Generalmente si assume che i processi di arrivo esogeni siano
di Poisson con parametro O. Nella rappresentazione grafica di una rete normalmente
si considerano solo gli archi a cui è associato un valore pij non nullo. La struttura
della rete è quindi completamente descritta dalla PDWULFHGHOOHSUREDELOLWjGL
WUDQVL]LRQH3, quadrata di ordine M, i cui elementi sono le probabilità pij, 1di,jdM, e
dalle probabilità pi0 e p0i, con 1didM. Per la condizione di normalizzazione delle
probabilità, vale:
p + p = 1 con 1
ij
j=1
M
i0 ¦ ddi M
Definiamo ora il vettore H = (e1,e2,...,eM) le cui componenti si ricavano come
soluzione del seguente sistema lineare:
e = p + e p con 1
i 0i j ji
j=1
MO ¦ ddi M (1.3)
Tale sistema è detto delle HTXD]LRQLGLWUDIILFR della rete. Le componenti ei
rappresentano i WDVVLGLYLVLWD al nodo i, ovvero il tasso relativo con cui i clienti
giungono al nodo i. Possiamo osservare che nel caso in cui pi0=0 e p0i=0, per 1didM,
il sistema lineare (1.3) è omogeneo e non ammette un’unica soluzione. La matrice P
di attraversamento della rete, e quindi anche la rete stessa, viene detta UHYHUVLELOH se
si verificano le condizioni eipij=ejpji e Op0i=eipi0 con 1di,jdM. Sostanzialmente, una
rete reversibile è caratterizzata dal fatto che invertendo la direzione del flusso dei
clienti, cioè invertendo l’orientamento degli archi nel grafo, il suo comportamento
non cambia [Kel79].
Per descrivere il comportamento di questo modello, assumiamo che in un
generico istante di tempo questo si trovi in uno stato S definito dalla M-upla
(S1,S2,..,SM), la cui componente Si indica lo stato del centro di servizio i, 1didM. Sia
inoltre E l’insieme degli stati ammissibili, insieme che può anche essere infinito. La
particolare definizione di uno stato Si dipende anche dalle caratteristiche del centro di
Il modello
11
servizio, oltre che da quelle dell’ intera rete. Tra le informazioni contenute nella
definizione di uno stato è incluso il numero di clienti presenti nella coda. Una
possibile definizione di uno stato S
i
, che tiene conto anche della condizione di
funzionamento del servente stesso oltre che del numero di clienti nella coda, è data
ad esempio dalla coppia (n
i
,b
i
) dove n
i
denota il numero di clienti nella coda e b
i
vale
1 se il centro di servizio è attivo, cioè sta servendo qualche cliente, e vale 0 se il
centro di servizio non è attivo. La definizione dettagliata e completa dello stato S
i
deve tener conto delle caratteristiche operative del nodo e del meccanismo di blocco.
L’ evolversi del modello in condizioni di equilibrio è descritto della funzione di
distribuzione stazionaria di probabilità di stato della rete.
Analizziamo ora le diverse tipologie di reti di code attraverso gli elementi che
le caratterizzano e le proprietà delle reti stesse.
Reti aperte e chiuse. Una prima distinzione è tra reti di code aperte e chiuse. Si
parla di UHWLDSHUWH quando è possibile l’ interazione con l’ esterno della rete,
ovvero se vi è un flusso di clienti che dall’ esterno entra nella rete e viceversa in
uscita dalla rete verso l’ esterno. Formalmente la rete è aperta se p
0i
>0 e p
i0
>0
per qualche i, 1didM (0 indica convenzionalmente l’ esterno). Le UHWLFKLXVH
sono invece reti prive di interazioni con l’ esterno, quindi al loro interno circola
un numero costante e non nullo di clienti. Formalmente la rete è chiusa se p
0i
=0
e p
i0
=0 per ogni i, 1didM. Accanto a questi due modelli principali, esistono
diverse possibili varianti legate ad eventuali vincoli sul numero di clienti
presenti nella rete. Possiamo quindi definire reti aperte con limitazioni al
numero complessivo di clienti presenti contemporaneamente nella rete
(popolazione della rete), e reti aperte o chiuse con vincoli di popolazione su
porzioni delle reti stesse (sottoreti). Tali vincoli possono essere delle
limitazioni sia inferiori che superiori.
Centri di servizio. Come definito nel paragrafo precedente, i centri di servizio
sono delle code caratterizzate da quintuple A/B/s/c/D. Consideriamo solamente
modelli a rete di code omogenee ovvero dove le distribuzioni di arrivo e di
servizio, come anche le discipline di servizio, sono dello stesso tipo per tutti i
centri di servizio. I parametri rimanenti possono dipendere dal singolo centro di
servizio. Relativamente ai parametri che descrivono le distribuzioni di arrivo e
di servizio in un centro di servizio, questi possono essere dipendenti dallo stato
in cui sui trova il centro stesso.
Ricevi informazioni sui nostri servizi, sulle offerte e non perdere news e consigli su università e lavoro.
