Comments
Description
Transcript
07S - Reti di Code
Corso di Laurea Triennale in INGEGNERIA GESTIONALE Anno Accademico 2012/13 MODELLI E METODI PER L’AUTOMAZIONE Prof. Davide GIGLIO RETI DI CODE RETI DI CODE MODELLI E METODI PER L’AUTOMAZIONE 1 INDICE RETI DI CODE MARKOVIANE APERTE ★ Modello di Jackson RETI DI CODE MARKOVIANE CHIUSE ★ Modello di Gordon e Newell ★ Metodo di Denning e Buzen METODI APPROSSIMATI PER RETI DI CODE NON MARKOVIANE ★ Mean Value Analysis (MVA) RETI DI CODE MODELLI E METODI PER L’AUTOMAZIONE 2 RETI DI CODE MARKOVIANE ★ Le reti di code markoviane sono sistemi costituiti da più sistemi coda, ciascuno di essi caratterizzato da servitori con tempi di servizio con distribuzione esponenziale ★ Nelle reti di code aperte sono consentiti arrivi dall’esterno: in questo caso i tempi di interarrivo dei clienti (dall’esterno) sono supposti caratterizzati da una distribuzione esponenziale ★ Nelle reti di code chiuse non sono consentiti arrivi dall’esterno (vi è un numero costante di clienti che circola nel sistema) ★ I modelli di reti di code markoviane più utilizzati sono • modello di Jackson (modello di rete aperta) • modello di Gordon-Newell (modello di rete chiusa) RETI DI CODE MODELLI E METODI PER L’AUTOMAZIONE 3 RETI DI CODE MARKOVIANE ★ L’ipotesi di markovianità è in realtà troppo restrittiva e rende di fatto poco realistica l’applicazione delle reti di code markoviane (e dei risultati ad esse relativi) in diversi ambiti applicativi come, ad esempio, quello dei processi manifatturieri ★ Tuttavia questi modelli, anche se non completamente congruenti con le caratteristiche di un sistema reale, possono essere utilizzati in una prima fase di progetto per il dimensionamento di massima del sistema, sfruttando l’efficienza computazionale che li contraddistingue (se paragonati all’impiego di tecniche basate sulla simulazione) ★ Una volta determinato, di regola dopo una serie di tentativi, tale dimensionamento, deve comunque essere effettuata una verifica di tipo simulativo, tenendo presenti tutte le caratteristiche del sistema reale RETI DI CODE MODELLI E METODI PER L’AUTOMAZIONE 4 MODELLO DI JACKSON Il modello di Jackson di rete di code aperta è definito nel modo seguente 1. I clienti appartengono tutti alla stessa classe 2. La rete di code è composta da N nodi ciascuno corrispondente ad una singola coda con un insieme di servitori identici in parallelo Sia mi il numero di servitori del nodo (macchina) i -esimo 3. Il tempo di servizio di ciascuno dei servitori del nodo i -esimo è una variabile aleatoria distribuita in modo esponenziale (con parametro µi ) 4. In un certo numero di nodi della rete ha luogo il processo di arrivo dei clienti dall’esterno; ciascuno di tali processi è un processo di Poisson Sia i il parametro che caratterizza il processo degli arrivi al nodo i RETI DI CODE MODELLI E METODI PER L’AUTOMAZIONE 5 MODELLO DI JACKSON 5. Dopo aver completato il servizio presso il nodo i-esimo, ciascun cliente può: • essere trasferito ad un altro nodo j (eventualmente j = i ), con tempo di trasferimento nullo, con probabilità ri,j • uscire dal sistema, con probabilità ri,0 E’ così definito il processo di instradamento. Naturalmente deve essere ri,0 + N X ri,j = 1 i = 1, . . . , N j=1 6. I buffer delle linee di attesa ad ogni nodo hanno dimensione infinita 7. Tutti i processi stocastici (di arrivo, di servizio, di instradamento) corrispondono a sequenze di variabili aleatorie indipendenti e identicamente distribuite (i.i.d.); i processi stocastici suddetti sono inoltre a due a due mutuamente indipendenti 8. La popolazione complessiva dei clienti è infinita RETI DI CODE MODELLI E METODI PER L’AUTOMAZIONE 6 MODELLO DI JACKSON ★ Nel modello di Jackson, il processo complessivo degli arrivi al nodo i -esimo (comprendendo quindi gli arrivi provenienti dall’esterno e quelli provenienti dall’interno) è un processo stocastico caratterizzato da un rate di arrivi medio dato da ⇤i = i + N X j=1 ej rj,i ⇤ e j il rate di uscite medio dal nodo j essendo ⇤ ★ In condizioni di equilibrio stocastico, il rate di arrivi medio in ingresso e quello in uscita saranno uguali per ogni nodo ei ⇤i = ⇤ i = 1, . . . , N ★ Si ha pertanto l’equazione di bilancio dei flussi ⇤i = i + N X rj,i ⇤j j=1 RETI DI CODE MODELLI E METODI PER L’AUTOMAZIONE 7 MODELLO DI JACKSON ★ L’equazione di bilancio dei flussi ⇤i = i + N X rj,i ⇤j j=1 scritta per ogni nodo i , costituisce un sistema lineare di N equazioni in N incognite ★ Tale sistema può essere risolto allo scopo di determinare il rate di arrivo medio (complessivo) di ogni nodo ★ In tutti i nodi in cui non vi sono arrivi dall’esterno si avrà i =0 ★ Inoltre, è evidente che, in condizioni di equilibrio stocastico, il rate di arrivo medio coinciderà con il flusso medio dei clienti, per il nodo considerato RETI DI CODE MODELLI E METODI PER L’AUTOMAZIONE 8 TEOREMA DI JACKSON ✹ TEOREMA ✹ Sia data una rete di code aperta corrispondente al modello di Jackson. Si risolva allora il sistema costituito dalle equazioni di bilancio dei flussi, determinando le quantità ⇤i , i = 1, . . . , N . Se risulta ⇤i mi µi <1 8 i = 1, . . . , N allora il sistema può essere rappresentato con una CTMC irriducibile con tutti gli stati ricorrenti positivi La distribuzione di probabilità a regime dello stato è data da ⇡(n1 , n2 , . . . , nN ) = Pr{L1 = n1 , L2 = n2 , . . . , LN = nN } = = ⇡1 (n1 ) · ⇡2 (n2 ) · . . . · ⇡N (nN )} • Li è il numero di clienti presenti nel nodo i -esimo • ⇡i (ni ) è identica alla distribuzione di probabilità dello stato a regime di una coda M/M/mi , caratterizzata dai parametri ⇤i , µi e mi RETI DI CODE MODELLI E METODI PER L’AUTOMAZIONE 9 TEOREMA DI JACKSON Pertanto ⇡i (0) = " ⇡i (ni ) = essendo ⇢i = RETI DI CODE 1 1+ m 1 i X ni =1 (mi ⇢i )ni ni ! 8 ni (m ⇢ ) i i > > ⇡ (0) > < i ni ! mi > > m > i : ⇡i (0) i ⇢n mi ! i + (mi ⇢i )mi mi ! · 1 1 ⇢i # ni = 1, 2, . . . , mi ni 1 mi ⇤i mi µi MODELLI E METODI PER L’AUTOMAZIONE 10 TEOREMA DI JACKSON Il teorema di Jackson ha il seguente importante significato ★ In una rete di code aperta corrispondente al modello di Jackson, purché sia soddisfatta la condizione di stabilità ⇢i = ⇤i /mi µi < 1 , il sistema raggiunge una condizione di equilibrio stocastico in cui la distribuzione di probabilità congiunta è caratterizzata da una “struttura prodotto”, cioè da una struttura tale da risultare il prodotto di distribuzioni di probabilità marginali (cioè relative ad un’unica variabile) ★ Inoltre, come si è visto, ciascuna di tali distribuzioni di probabilità marginali corrisponde semplicemente alla distribuzione di probabilità a regime di una coda M/M/mi ★ La possibilità di determinare la probabilità congiunta consente la determinazione di diversi indici di prestazione caratterizzanti il comportamento della rete di code aperta RETI DI CODE MODELLI E METODI PER L’AUTOMAZIONE 11 MODELLO DI GORDON-NEWELL Il modello di Gordon-Newell è identico al modello di Jackson, se non per le ipotesi seguenti 1. = 0 8 i , cioè non vi è alcun processo di arrivo dei clienti dall’esterno (gli arrivi provengono tutti dai nodi della rete); inoltre ri,0 = 0 8 i , cioè i clienti non possono lasciare il sistema una volta completato il servizio su un certo nodo della rete i Ciò vuol dire che vi è un numero costante di clienti nel sistema (dal punto di vista pratico, quando un cliente completa il suo ciclo complessivo di servizi, esso viene sostituito da un altro cliente che invece deve ancora iniziare il suo ciclo) 2. La matrice di routing, il cui generico elemento è ri,j , non può essere trasformata, attraverso semplici permutazioni di riga e di colonna, in una A | 0 matrice avente la struttura B , con A e C sottomatrici quadrate | C Ciò vuol dire che non è possibile isolare una parte del sistema in cui i clienti possono solo entrare, senza potere più uscire RETI DI CODE MODELLI E METODI PER L’AUTOMAZIONE 12 TEOREMA DI GORDON-NEWELL ✹ TEOREMA ✹ Sia data una rete di code chiusa corrispondente al modello di GordonNewell. Il sistema può essere rappresentato con una CTMC irriducibile con spazio degli stati finito. La cardinalità di tale spazio è |S| = ✓ N +K K ◆ 1 = ✓ N +K 1 N 1 ◆ dove K è il numero costante di clienti nella rete di code chiusa Esiste pertanto una distribuzione di probabilità dello stato a regime che è data da N Y xi ni ⇡(n1 , n2 , . . . , nN ) = C (ni ) i=1 i essendo le funzioni i (ni ) date da ⇢ ni ! ni = 1, 2, . . . , mi i (ni ) = mi i mi ! mn ni mi i RETI DI CODE 1 i = 1, . . . , N MODELLI E METODI PER L’AUTOMAZIONE 13 TEOREMA DI GORDON-NEWELL ✹ TEOREMA ✹ (continuazione) Le costanti xi sono determinate risolvendo (a meno di una costante arbitraria) il sistema lineare omogeneo µi xi = N X i = 1, . . . , N rj,i µj xj j=1 La costante C è una costante di normalizzazione determinata come 1 C= X n2S N Y i=1 xi ni i (ni ) ! dove n = col(n1 , n2 , . . . , nN ) RETI DI CODE MODELLI E METODI PER L’AUTOMAZIONE 14 TEOREMA DI GORDON-NEWELL ★ La costante di normalizzazione ha la funzione di imporre che sia X ⇡(n1 , n2 , . . . , nN ) = 1 n2S indipendentemente dalla indeterminazione che caratterizza la risoluzione del sistema lineare omogeneo che fornisce le ★ La determinazione della costante di normalizzazione richiede purtroppo la determinazione completa dello spazio degli stati S , la cui cardinalità può essere piuttosto elevata, anche per N e K non elevati ★ La distribuzione di probabilità congiunta fornita dal teorema di GordonNewell è ancora espressa in forma prodotto ★ Questa volta però i singoli fattori non sono distribuzioni di probabilità marginali, in quanto le variabili aleatorie n1 , n2 , . . . , nN non possono più essere considerate come variabili aleatorie indipendenti (principalmente per il fatto che si ha un numero fisso di clienti) RETI DI CODE MODELLI E METODI PER L’AUTOMAZIONE 15 TEOREMA DI GORDON-NEWELL ★ La probabilità marginale ⇡i (ni ) può comunque essere calcolata dalla probabilità congiunta ⇡(n1 , n2 , . . . , nN ) ⇡i (s) = X ⇡(n) n2⌘ i (s) con ⌘ i (s) = ⇢ (n1 , n2 , . . . , nN ) : N X ni = K , ni = s i=1 ★ Una volta determinate le probabilità marginali è possibile calcolare gli indici di prestazione di interesse RETI DI CODE MODELLI E METODI PER L’AUTOMAZIONE 16 MODELLO DI GORDON-NEWELL ★ La lunghezza di coda media del nodo i -esimo è data da Lq i = K X s ⇡i (s) s=1 ★ Il coefficiente di carico relativo al nodo i -esimo è sempre ⇢i = ⇤i mi µi che però non può essere calcolato direttamente non essendo disponibili le quantità ⇤i (flussi in ingresso/uscita delle singole code) ★ Il coefficiente di carico corrisponde però a 1 ⇡ ˜ i (0) , dove ⇡ ˜ i (0) è la probabilità che un generico servitore nel nodo i -esimo sia inattivo in un istante selezionato a caso (in condizioni di equilibrio stocastico) ★ La quantità ⇡ ˜ i (0) può sempre essere ricavata dalla distribuzione marginale ⇡i (ni ) ˜ i (0) = ⇡i (0) • se mi = 1 si ha ⇡ ˜ i (0) = ⇡i (0) + 1/2 · ⇡i (1) • se mi = 2 si ha ⇡ ˜ i (0) = ⇡i (0) + 2/3 · ⇡i (1) + 1/3 · ⇡i (2) • se mi = 3 si ha ⇡ RETI DI CODE MODELLI E METODI PER L’AUTOMAZIONE 17 MODELLO DI GORDON-NEWELL ★ Una volta note le quantità ⇡ ˜ i (0) è possibile calcolare i coefficienti di ˜ i (0) e quindi i flussi ⇤i carico ⇢i = 1 ⇡ ★ Dal punto di vista pratico è sufficiente determinare una sola delle quantità ⇤i , i = 1, . . . , N , per determinarle tutte sulla base della risoluzione del sistema lineare omogeneo N X ⇤i = rj,i ⇤j i = 1, . . . , N j=1 che è risolubile a meno di una costante arbitraria ★ Una volta determinato l’insieme delle ⇤i , i = 1, . . . , N , è immediato calcolare il throughput dell’intero sistema. Esso infatti deve essere inteso come il flusso in uscita dal sistema dei clienti per cui è stato completato il ciclo dei servizi ovvero il flusso in uscita dalle macchine che generano prodotti finiti ★ Essendo noto e costante il numero di clienti nel sistema, una volta calcolato il throughput è immediato ottenere, con la legge di Little, il tempo medio di permanenza nel sistema del generico cliente RETI DI CODE MODELLI E METODI PER L’AUTOMAZIONE 18 METODO DI DENNING E BUZEN ★ Il bisogno di considerare l’intero spazio degli stati e i conseguenti problemi computazionali nascono dalla necessità di calcolare la costante di normalizzazione C ★ Il metodo di Denning e Buzen fornisce un modo operativo più efficiente per il calcolo della costante di normalizzazione ★ Si consideri una rete di code markoviane chiusa che soddisfa il modello di Gordon-Newell composta da risorse tutte monoserver mi = 1 8 i = 1, . . . , N ★ E’ banale verificare che in questo caso risulta i (ni ) =1 8 i = 1, . . . , N ★ Pertanto, la distribuzione di probabilità congiunta fornita dal teorema di Gordon-Newell può essere scritta come ⇡(n1 , n2 , . . . , nN ) = C N Y xi ni i=1 RETI DI CODE MODELLI E METODI PER L’AUTOMAZIONE 19 METODO DI DENNING E BUZEN ★ Le costanti xi possono essere calcolate risolvendo (a meno di una costante arbitraria) il sistema lineare omogeneo N X µi xi = rj,i µj xj i = 1, . . . , N j=1 (come specificato dal teorema di Gordon-Newell) ★ Tale sistema è analogo a quello che fornisce (per le reti di code chiuse e sempre a meno di una costante arbitraria) i flussi ⇤i in ingresso ai vari nodi della rete. Si può pertanto porre µi xi = ⇤i e quindi xi = ⇤i µi i = 1, . . . , N da cui ⇡(n1 , n2 , . . . , nN ) = C N Y i=1 RETI DI CODE ✓ ⇤i µi ◆ni MODELLI E METODI PER L’AUTOMAZIONE 20 METODO DI DENNING E BUZEN ★ Per superare l’indeterminatezza dovuta alla risoluzione di sistemi lineari omogenei, si consideri, tra le risorse del sistema quella che rappresenta la macchina di carico/scarico Si noti che se tale risorsa non è formalmente presente nel sistema, si può sempre considerare una risorsa fittizia, con tempo di servizio nullo, che assume il ruolo di macchina di carico/scarico ★ Per semplificare la notazione, sia la macchina di carico/scarico rappresentata dal nodo “ 0 ” (a prescindere se corrisponde ad una risorsa fisica o ad una risorsa fittizia) e siano le altre risorse del sistema rappresentate, come prima, dai nodi da “ 1” a “N ” Seguendo questa notazione, il numero di risorse complessive è quindi N + 1. Il nodo “0” può corrispondere o meno ad una risorsa reale ★ Per come è stata definita, la macchina di carico/scarico è tale che tutti i clienti passano una e una sola volta da essa ★ Inoltre, il flusso ⇤0 che attraversa tale macchina corrisponde al throughput del sistema RETI DI CODE MODELLI E METODI PER L’AUTOMAZIONE 21 METODO DI DENNING E BUZEN ★ Si considerino le equazioni di conservazione dei flussi, che possono essere risolte a meno di una costante arbitraria N X ⇤i = rj,i ⇤j i = 0, 1, . . . , N j=0 e si risolvano considerando il throughput ⇤0 come costante arbitraria ★ Tutti gli altri flussi nel sistema possono pertanto essere espressi come ⇤i = Vi ⇤0 i = 0, 1, . . . , N dove il coefficiente Vi (“visit count”) è il valor medio della variabile aleatoria “numero di passaggi di un cliente generico attraverso il nodo i ” Generalmente Vi assume valori positivi (sia minori che maggiori di 1); non è esclusa la possibilità che Vi sia nullo RETI DI CODE MODELLI E METODI PER L’AUTOMAZIONE 22 METODO DI DENNING E BUZEN ★ I visit count possono essere determinati a priori ★ Sulla base di quanto visto, dividendo l’equazione di conservazione dei flussi per il throughput ⇤0 e considerando il fatto che dalla macchina di carico/scarico i clienti passano una e una sola volta, si ottiene il seguente sistema lineare non omogeneo 8 V0 = 1 > > < N X > rj,i Vj > : Vi = i = 1, . . . , N j=0 ★ Si ha inoltre xi = Vi µi ⇤0 i = 0, . . . , N (se la macchina di carico/scarico è fittizia risulta x0 = 0 ) RETI DI CODE MODELLI E METODI PER L’AUTOMAZIONE 23 METODO DI DENNING E BUZEN ★ La distribuzione di probabilità congiunta diventa (considerando il nuovo formalismo che include il nodo “0”) ⇡(n0 , n1 , . . . , nN ) = C ◆ni N ✓ Y Vi i=0 µi ⇤0 ni = C · ◆ni N ✓ Y Vi i=0 µi · N ✓ i Y Vi n0 n1 nN = C · ⇤0 · ⇤0 · . . . · ⇤0 · µi i=0 ◆ni N ✓ Y Vi K = C ⇤0 · µi i=0 h N Y ⇤0 ni = i=0 ◆ni = che può essere scritta come ⇡(n0 , n1 , . . . , nN ) = G(N, K) · N Y i=0 ✓ Vi µi ◆ni in cui la costante G(N, K) è indipendente da (n0 , n1 , . . . , nN ) RETI DI CODE MODELLI E METODI PER L’AUTOMAZIONE 24 TEOREMA DI DENNING E BUZEN ✹ TEOREMA ✹ Con riferimento ad una rete di code chiusa, corrispondente al modello di Gordon-Newell, in cui mi = 1 8 i = 0, . . . , N , la distribuzione congiunta di probabilità dello stato a regime ⇡(n0 , n1 , . . . , nN ) può essere espressa come ◆ni N ✓ Y Vi ⇡(n0 , n1 , . . . , nN ) = G(N, K) · µi i=0 dove la costante G(N, K) può essere determinata attraverso il procedimento ricorsivo G(i, j) = G(i 1, j) + Vi µi · G(i, j 1) i = 1, . . . , N j = 1, . . . , K arrestato naturalmente ai valori i = N e j = K e inizializzato con G(0, j) = RETI DI CODE ✓ V0 µ0 ◆j 8 j = 0, . . . , K G(i, 0) = 1 8 i = 0, . . . , N MODELLI E METODI PER L’AUTOMAZIONE 25 TEOREMA DI DENNING E BUZEN ★ Il teorema di Denning e Buzen fornisce un metodo computazionalmente assai efficiente per la determinazione della costante di normalizzazione G(N, K) HHH ★ La complessità della procedura iterativa che fornisce G(N, K) è polinomiale ★ Non è più necessario determinare tutti gli stati del sistema per ottenere la probabilità congiunta relativa ad un certo stato ★ La determinazione di G(N, K) richiede la preventiva determinazione delle costanti Vi che dipendono da µi e da ri,j . Pertanto, è evidente come la costante di normalizzazione dipenda da tali valori che caratterizzano il sistema RETI DI CODE MODELLI E METODI PER L’AUTOMAZIONE 26 METODO DI DENNING E BUZEN ★ Il throughput del sistema può essere espresso come ⇤0 = G(N, K 1) G(N, K) ★ La probabilità che nel nodo N vi siano h clienti è ⇡N (h) = Pr nN = h = ✓ VN µN ◆h · G(N 1, K h) G(N, K) Se si vuole conoscere la probabilità ⇡j (h) di avere h clienti in un altro nodo j della rete, bisogna ricalcolare la costante G(N, K) considerando il nodo j come ultimo nodo della rete (ovvero come “nodo N ”) RETI DI CODE MODELLI E METODI PER L’AUTOMAZIONE 27 METODO DI DENNING E BUZEN ★ Il numero medio di clienti nel nodo i è Lq i = K X h ⇡i (h) h=0 ★ Il tempo medio di permanenza nel nodo i è Tqi = Lq i ⇤i con ⇤i = Vi ⇤0 ★ Il nodo “bottleneck” è il nodo i? per cui µi? Vi? RETI DI CODE = min i=0,...,N ⇢ µi Vi MODELLI E METODI PER L’AUTOMAZIONE 28 METODO DI DENNING E BUZEN Λ0 (K) min i=1,...,N ! µi Vi " K THROUGHPUT IN FUNZIONE DEL NUMERO DI CLIENTI NEL SISTEMA RETI DI CODE MODELLI E METODI PER L’AUTOMAZIONE 29 MEAN VALUE ANALYSIS (MVA) ★ E’ un metodo di analisi approssimato applicabile a reti di code chiuse non markoviane Essendo un metodo approssimato viene bene per effettuare un’analisi preliminare delle prestazioni del sistema. I risultati dovranno poi essere validati attraverso esperimenti simulativi ★ La mean-value-analysis (nella versione di Schweitzewr-Bard) si basa sulla stima (approssimata) del tempo medio di attesa del cliente generico al nodo i-esimo ★ Nell’ipotesi che tutti i nodi siano mono-server, tale tempo di attesa viene stimato come pari a Twi = 1 K K Lq i T s i i = 1, . . . , N in cui K è il numero complessivo (costante) di clienti nel sistema RETI DI CODE MODELLI E METODI PER L’AUTOMAZIONE 30 MEAN VALUE ANALYSIS (MVA) ★ La scelta di questa stima è motivata dall’assunzione che il termine (K 1)/K serva a “ridurre” la lunghezza di coda media Lq i del fattore sufficiente ad impedire che si tenga conto dell’attesa del servitore da parte del generico cliente (di cui si vuole stimare il tempo medio di attesa) in una coda di cui esso fa parte Questa approssimazione è totalmente euristica e non può essere in alcun modo giustificata dal punto di vista analitico ★ Se si accetta questa approssimazione, diventa possibile stimare il tempo medio complessivo di permanenza nel nodo i -esimo come Tqi = Twi + Tsi RETI DI CODE K = Tsi 1 + 1 K Lq i i = 1, . . . , N MODELLI E METODI PER L’AUTOMAZIONE 31 MEAN VALUE ANALYSIS (MVA) ★ Se si considerano i visit count, forniti dalla risoluzione del sistema 8 V = 1 0 > > < N X > rj,i Vj > : Vi = i = 1, . . . , N j=0 (come nel metodo di Denning e Buzen), il tempo complessivo di permanenza nel sistema può essere valutato come ⌧ = N X Vi T q i i=1 ★ Ne consegue che, usando la legge di Little, il throughput del sistema può essere calcolato come ⇤0 = K/⌧ RETI DI CODE MODELLI E METODI PER L’AUTOMAZIONE 32 MEAN VALUE ANALYSIS (MVA) ★ Noto ⇤0 possono essere determinati i flussi ⇤i = Vi ⇤0 i = 1, . . . , N e quindi, sempre applicando la legge di Little, si possono ottenere le code medie Lq i = Vi T q i i = 1, . . . , N ★ Si noti che la prima formula vista (stima del tempo medio di attesa nel buffer) presupponeva la conoscenza della lunghezza di coda media Lq i , che però viene calcolata solo alla fine con l’ultima formula vista ★ Si può pertanto predisporre un algoritmo iterativo per l’analisi (approssimata) delle prestazioni di una rete di code chiusa RETI DI CODE MODELLI E METODI PER L’AUTOMAZIONE 33 MEAN VALUE ANALYSIS (MVA) ✹ALGORITMO✹ (Mean-Value-Analysis secondo Schweitzer-Bard) STEP 1 Si inizializzano le code medie con i valori Lq i , i = 1, . . . , N STEP 2 Si calcolano i tempi medi T q i , i = 1, . . . , N , sulla base delle Lq i , (per mezzo della formula vista in precedenza) STEP 3 Si calcola il throughput ⇤0 (facendo uso dei visit count, come visto in precedenza) STEP 4 Si calcolano nuove stime delle code new Lq i = ⇤0 Vi T q i , i = 1, . . . , N STEP 5 new Lq i < ✏ , 8 i = 1, . . . , N , allora stop. Altrimenti Se Lq i new Lq i Lq i , i = 1, . . . , N , e si ritorna al passo 2 RETI DI CODE si pone MODELLI E METODI PER L’AUTOMAZIONE 34 MEAN VALUE ANALYSIS (MVA) ★ Non vi è alcuna garanzia a priori sulla convergenza dell’algoritmo, né sul livello di approssimazione della stima degli indici di prestazione ottenuta in convergenza ★ Tuttavia, in letteratura sono riportate numerose applicazioni dell’algoritmo nelle quali la convergenza si raggiunge abbastanza rapidamente ★ Inoltre, il livello di approssimazione delle stime ottenute è generalmente buono rispetto alle stime accurate ottenibili mediante esperimenti simulativi (l’errore di approssimazione è inferiore al 20%-30%) RETI DI CODE MODELLI E METODI PER L’AUTOMAZIONE 35