Che materia stai cercando?

Anteprima

ESTRATTO DOCUMENTO

λ

Teorema: si consideri un processo di nascita e morte con coefficiente di natalità e coefficienti di mortalità

i

μ .

j

Sul grafo precedentemente visto ora introduciamo t e t , ovvero due tagli

1 2

Scriviamo le equazioni dei flussi che attraversano questi tagli, che chiameremo equazioni di bilancio

dettagliato

Tali equazioni più dettagliate implicano quelle del bilancio globale viste prima. λ

Consideriamo ora il processo più semplice possibile: quello delle sole nascite, avente coefficiente =λ

n

μ

costante e =0. So che tale processo è un processo di Poisson In tale processo le equazioni di Kolmogorov

n

sono le seguenti:

In tale maniera abbiamo dimostrato che un processo di sole nascite coincide con un processo di Poisson. La

stessa cosa vale per un processo di sole morti.

ESERCIZIO 1

Un negozio ha un’unica cassa servita da una cassiera che provvede anche a confezionare pacchi. I clienti

arrivano alla cassa con frequenza media di 30 l’ora e il tempo occorrente perché la cassiera faccia il conto

della spesa, confezioni il pacco e riceva il pagamento dal cliente è in media di 2 minuti. Inoltre, ogni volta

che alla cassa vi sono 3 o più clienti, il proprietario del negozio aiuta la cassiera a confezionare i pacchi e in

questo modo il tempo medio per servire un cliente diventa pari a 1 minuto. Costruire un modello basato su

processi di nascita e morte che rappresenti la situazione descritta determinando la distribuzione stazionaria.

a. Calcolare inoltre la probabilità che presso la cassa ci siano almeno di 3 clienti

SVOLGIMENTO

Consideriamo come unità di misura l’ora. Quello che evolve all’interno del sistema è il numero di utenti alla

μ è il tempo che passa tra l’uscita di un cliente e quella di un altro

cassa. Gli arrivi non dipendono da n. n

cliente, ovvero il l’intertempo, dato μ

dal tempo di servizio. Il dipende dallo stato del sistema, infatti

n

vengono serviti in media 30 clienti l’ora se i clienti nel negozio sono meno di 2, mentre vengono serviti in

media 60 clienti nel negozio se i clienti sono 3 o più di tre. Determiniamo la distribuzione stazionaria.

ESERCIZIO 2

Si consideri un processo di nascita e morte con i coefficienti di natalità e mortalità illustrati sotto.

Determinare sotto quali condizioni questo processo raggiunge lo stato stazionario e calcolarne l’espressione

λ μ.

di p e p in funzione di e

0 n

SVOLGIMENTO

ESERCIZIO 3

ESERCIZIO 4

CAPITOLO 4

I processi di nascita e morte permettono di studiare il comportamento di un sistema a coda. Il modello più

semplice corrisponde al caso in cui vi è un processo di nascita e morte con coefficienti di natalità e mortalità

λ μ,

costanti e pari rispettivamente a e quindi non dipendenti da n. Questa situazione corrisponde facilmente

al caso M/M/1.

Sistemi a coda basati su processi di nascita e morte

Assumendo che un sistema abbia riaggiusto l’equilibrio (stazionario) è possibile calcolare ed ottenere le

misure di prestazione di un sistema di code rappresentato da un processo di nascita e morte. Infatti ottenuti i

q

valori delle p delle probabilità di equilibrio si possono calcolare il valore di N e quello di N .

n

Ora il passo successivo consiste nell’applicare q

la legge di Little per ottenere i valori T e T . Nel fare questo

λ,

dobbiamo prestare attenzione che costante nella legge di Little, rappresenta la frequenza media degli

λ

arrivi. Se può variare con lo stato n, il valore della frequenza media degli arrivi deve essere calcolato. Ciò

n λ

può essere fatto facilmente ricordando che rappresenta la frequenza media di arrivo quando nel sistema ci

n

sono n utenti e p è la probabilità che n utenti siano presenti nel sistema e quindi la frequenza media effettiva

n

degli arrivi sarà data da:

Determinato tale valore è possibile applicare la legge di Little e ricavare gli altri due parametri che

cercavamo.

Vediamo ora una proprietà di cui godono tutti i sistemi a code con arrivi poissoniani.

Proprietà PASTA. Un sistema che si suppone sia caratterizzato da arrivi poissoniani gode della proprietà

detta Poisson Arrivals See Times Average. Tale proprietà afferma che tutti gli utenti che arrivano al sisma di

cosce trovano, in media, nel sistema la stessa situazione che vedrebbe un osservatore esterno, che osserva il

sistema in un determinato momento arbitrario t.

Proprietá PASTA: sia dato un sistema a coda con arrivi poissoniani. Allora la probabilità che un utente

arriva nel sistema al tempo t trovi il sistema allo stato k è uguale alla probabilità che il ssifema sia allo stato k

al tempo t.

Dimostrazione

Abbiamo appena definito la distribuzione stazionaria come segue, determinando anche che p come la

k

quantità di tempo che il sistema si trova nello stato k. Poiché per la proprietà PASTA si ha che a (t)=p (t),

k k

passando per il limite si ha che a =p .

k k

Sistemi M/M/s

Questi tipi di sistemi possono essere rappresentati come processi di nascita e morte; infatti se il sistema ha un

solo servente (s=1) allora è rappresentabile mediante un processo di nascita e morte con coefficiente di

λ μ μ.

natalità =λ e con coefficiente di mortalità pari a = Se il sistema invece ha s>1 serventi, il sistema sarà

n n μ

sempre rappresentabile mediante un processo di nascita e morte, ma il coefficiente di mortalità non potrà

n

essere espresso in maniera semplice come nel caso precedente. Abbiamo infatti già visto che quando la

μ,

velocità di servizio media di ciascun server è pari a la velocità media di servizio complessivo quando si

hanno n serventi occupati è pari a nμ. Si avrà allora che

Sistemi M/M/1 ρ= λ/μ ρ π

Assumiamo in tale tipo di sistemi che <1 (dove con abbiamo chiamato ). In tale caso infatti è

n

soddisfatta la condizione di esistenza dello stato stazionario, poiché 0<ρ<1 e risulta che

Una volta calcolate le p risulta possibile calcolare tutti i parametri del sistema

n

ESERCIZIO 1

In un aeroporto con una sola pista chiede di atterrare in media un aereo ogni 6 minuti e la distribuzione degli

intervalli di tempo tra due richieste successive è esponenziale. Gli aerei vengono autorizzati ad atterrare dal

controllore del traffico aereo sulla base del criterio primo arrivato, primo servito (FIFO). Gli aerei che non

possono atterrare immediatamente per la congestione del traffico vengono inseriti in un circuito di attesa. Il

tempo necessario per l’atterraggio è distribuito esponenzialmente con un valore medio pari a 4 minuti.

Determinare:

a. Il numero medio di aerei tenuti contemporaneamente sotto controllo dal controllo del traffico aereo

b. Il numero medio di aerei che si trovano nel circuito di attesa

c. Il tempo medio passato nel circuito di attesa

d. La probabilità che nel circuito di attesa ci siano più di 3 aerei

SVOLGIMENTO

Vediamo una proposizione. w

Proposizione: in un sistema M/M/1 con disciplina di coda FIFO, il tempo di permanenza nel sistema t è

μ-λ. w -(μ-λ)t

distribuito esponenzialmente con parametro P(t >t)= e , t>=0.

DIMOSTRAZIONE

Supponiamo che l’utente che arrivi trovi già un certo numero n di utenti presenti nel sistema. Se n=0 il tempo

di permanenza nel sistema dell’utente che è arrivato risulterà pari a al tempo di servizio. Nel caso in cui,

invece, n>=1 il nuovo utente che arriva trova un utente che sta usufruendo del servizio e n-1 utenti in coda.

Per poter uscire dal sistema, questo nuovo utente che arriva dovrà aspettare

• I tempi di servizio degli n-1 utenti che sono in coda, tempi tutti distribuiti esponenzialmente di

μ

parametro

• Il tempo di completamento del servizio dell’utente che sta usufruendo del servizio che per la

μ

proprietà di assenza di memoria è distribuito esponenzialmente di parametro

• Il tempo del proprio servizio, ovvero il tempo necessario per espletare il servizio relativo al nuovo

μ.

utente che arriva che è distribuito esponenzialmente di parametro

Quindi l’utente che entra nel sistema dovrà aspettare n+1 μ.

tempi distribuiti esponenzialmente di parametro

w

Da qui si può calcolare immediatamente il valore atteso della variabile t , ovvero T che è pari a 1/(μ-λ).

Abbiamo inoltre che

Nel caso di sistemi a code M/M/1 si può facilmente determinare la distribuzione di probabilità del tempo di

q

attesa nella coda t di un utente che arriva. q

Proposizione: in un sistema M/M/1 con disciplina di coda FIFO per il tempo di attesa in coda t vale

Dimostriamo tale risultato.

Ragioniamo in maniera analoga al caso precedente. Consideriamo sempre il fatto che il nuovo utente che

arriva non trova altri utenti all’interno del sistema (n=0). Allora tale nuovo utente viene servito

q

immediatamente e quindi t =0. La probabilità che ciò accada è pari a

caso si avrebbe che all’arrivo del nuovo utente c’è un

q

Rimane quindi da determinare P(t >t) per t>0. In tale

numero n non nullo di utenti presenti nel sistema, ovvero n>=1. Il nuovo utente dovrà allora aspettare n

tempi esponenziali prima del proprio servizio. Si avrà allora:

Quello che abbiamo appena dimostrato è che il tempo passato all’interno del sistema segue una distribuzione

esponenziale , mentre quello passato all’interno della cosa no. Se andiamo invece a condizionare il tempo di

q

coda con il fatto che t >=0, allora torna ad essere una distribuzione esponenziale.

ESERCIZIO 2

SVOLGIMENTO

Vediamo ora cosa accade nel caso multiservente. In tale caso sugli arrivi non viene influenzato nulla nel caso

in cui ho un numero di utenti minore del numero dei serventi.

Calcoliamoci anche tutti gli altri parametri nel caso di multiservente

Anche nel caso multiservente possiamo calcolarci la distribuzione di probabilità del tempo di permanenza

all’interno del sistema ed il tempo di permanenza all’interno della coda.

ESERCIZIO 3

Un bar ha due barman ugualmente efficienti, ciascuno dei quali è in grado di servire, in media, 60 clienti

l’ora e i tempi di servizio sono distribuiti esponenzialmente. I clienti entrano nel bar secondo un processo di

100 l’ora. Determinare:

Poisson, con frequenza media di

a. Il numero medio di clienti in attesa di essere serviti

b. Il tempo medio di attesa prima di essere serviti

c. La probabilità che nel bar vi siano più di 5 clienti

d. Se utilizzando un terzo barman è possibile dimezzare il tempo medio di attesa di coda

SVOLGIMENTO

CAPITOLO 5

Sistemi M/M/s/K

Consideriamo ora quei sistemi in cui viene imposta una limitazione circa la capacità, ovvero dove il numero

di utenti non può essere più grande di un determinato valore. Questo vuol dire che se si hanno s serventi, in

coda non si potranno avere più di K-s utenti. Per queste situazioni, infatti, si ha che per n>=K, tale processo

di nascita e morte viene considerato a coefficiente di natalità nullo. La probabilità che il sistema all’istante t

abbia n utenti dove n>K, ovviamente, sarà pari a 0. Questo può essere dovuto o a spazi limitati per il sistema,

oppure anche a fenomeni di balking, ovvero di rinuncia da parte degli utenti. Con il K, si descrive la capacità

del sistema, e non della coda. λ=0,

Se ammettiamo che per determinati valori si possa avere allora da un certo punto in poi avremo che la

serie risulta essere una somma finita, per cui il sistema raggiungerà le condizioni di stazionarietà anche

ρ<1

quando la condizione non risulta verificata (quindi non occorre imporre tale condizione quando si fa

l’analisi).

I sistemi di questo tipo si dicono autoregolanti, in quanto spegne gli arrivi appena raggiunge la sua capacità

massima.

Sistemi M/M/1/K

Consideriamo subito il caso monoservente.

Per calcolare gli altri valori occorre applicare il teorema di Little. Ma per fare ciò, occorre inoltre calcolare la

λ

frequenza media effettiva degli arrivi, data da segnato. La probabilità che un utente non possa entrare nel

sistema è pari alla probabilità che nel sistema ci siano K utenti, ovvero p . Quindi la probabilità che un utente

k

acceda al sistema è 1-p , e quindi, la frequenza media effettiva degli arrivi in questo caso risulta essere pari a

k

La probabilità p viene denominata fattore di perdita, poiché rappresenta la frazione di utenti che va perdita

K

perché non entra nel sistema.

ESERCIZIO 1

Una stazione di servizi ha un’unica pompa di benzina ed un unico addetto. Le automobili arrivano alla

rifornirsi secondo un processo di Poisson ad una frequenza media di 10 l’ora. Il

stazione di servizio per

tempo necessario per servire un’automobile è distribuito esponenzialmente con un valore medio pari a 2

minuti. La stazione di servizio può contenere al più 4 automobili e sulla strada vige un divieto di fermata, per

cui non è consentito attendere fuori dalla stazione. Determinare:

a. Il numero medio di automobili presenti nella stazione di servizio

La probabilità che un’automobile non possa effettuare il rifornimento

b.

c. Il tempo medio di attesa nella stazione di servizio prima di ottenere il servizio

SVOLGIMENTO

Sistemi M/M/s/K multiservente

Consideriamo tali sistemi sopponendo che s<=K. In questo caso si avrà:

Vediamo ora il caso in cui K=s, ovvero il caso in cui la coda ha capacità nulla. Tale modello risulta molto

usato nell’ambito della telefonia. Tale sistema a coda in cui la coda non esiste viene denominato come

Erlang loss system. In tale sistema la probabilità che un utente che arriva trova tutti gli s serventi occupati

può essere facilmente calcolata, in quanto è pari alla probabilità p che nel sistema ci siano già K utenti ed è:

K

ESERCIZIO 2

Un porto possiede un terminal targo al quale arrivano navi porta-container per le operazioni di carico-scarico

che avvengono attraverso apposite gru. Attualmente il terminal dispone di una sola gru e quindi il carico-

scarico avviene una nave alla volta. Quando una nave arriva e la gru è già impegnata in operazioni di

scarico-carico essa attende il proprio turno secondo una disciplina FIFO in una fila di attesa che supponiamo

illimitata. Le navi arrivano al terminal secondo la distribuzione di Poisson con media 3 al giorno e il tempo

che una gru impiega per il carico-scarico di una nave è distribuito esponenzialmente con media 4 ore.

Supponiamo che lo spazio nel terminal dove le navi attendono il proprio turno sia limitato e non permetta lo

stazionamento di più di 4 navi.

a. Descrivere il sistema a coda che può rappresentare la situazione

b. Determinare il numero medio di navi che sono in attesa di effettuare il carico-scarico

c. Determinare il tempo medio di attesa in coda.

SVOLGIMENTO

Sistemi M/M/s/-/U

Concentriamo ora la nostra attenzione sul caso in cui si abbia popolazione finita, in cui quindi il numero dei

potenziali utenti risulta finito e pari a N. Gli utenti presenti nel sistema saranno pari a n e gli utenti che

potenzialmente potrebbero entrare nel sistema sono pari a U-n. Quando risulta questo, ad un certo istante di

tempo la distribuzione di probabilità del tempo rimanente fino al prossimo arrivo al sistema coincide con la

distribuzione di probabilità del più piccolo dei tempi rimanenti per l’ingresso al sistema tutti gli utenti che

sono al di fuori del sistema, che sono come già detto U-n. Tale processo allora può essere anche esso

λ

rappresentato mediante un processo di nascita e morte con coefficiente di natalità pari a = (U-n)λ per

n

n=0,1,…, U-1 λ

e =0 per n>=U, poiché in questo sistema per definizione del sistema stesso non vi possono

n ρ>=1.

essere più di U utenti. Un tale sistema raggiunge condizioni di stazionarietà anche se risulta che

Vediamo subito i parametri nel caso monoservente.

Consideriamo ora invece il caso multiservente.

Sistemi con velocità di servizi e frequenza di arrivo dipendenti dallo stato del sistema

Vogliamo ora analizzare un caso in cui la velocità media del servizio non risulta costante è sempre uguale.

vedono che la fila d’attesa

Sono situazioni reali in cui ad esempio i serventi sono persone fisiche, che quando

si fa molto lunga tendono a lavorare incrementando la loro velocità di servizio.

Partiamo come sempre dal considerare prima il caso monoservente. μ

In tale caso supponiamo dapprima che la velocità di servizio sia dipendente dallo stato: denotiamo come

1

la velocità media di servizio in condizioni normali, quando un solo utente è presente all’interno del sistema.

μ μ

c

Si definisce inoltre = n dove c risulta essere una costante positiva. Assumiamo arrivi poissoniani di

n 1,

λ λ

parametro e tempi di servizio distribuiti esponenzialmente di parametro =λ e teniamo conto che la

n

condizione per l’esistenza dello stato stazionario è soddisfatta anche per c>0. Da questo si ottiene che:

Vediamo ora la situazione in cui solo la frequenza di arrivo dipende dallo stato. È questo il caso dei

cosiddetti arrivi rallentati, in cui si prevede un rallentamento progressivo degli arrivi in rapporto al numero

dei clienti presenti nel sistema. Un modello rappresentate bene tale situazione si ha supponendo che i tempi

μ

di servizio siano distribuiti esponenzialmente di parametro costante e che gli arrivi siano poissoniani, con

parametro non costante e dato dalla seguente funzione

λ indica la frequenza media degli arrivi in condizioni di coda vuota; b risulta essere una costante positiva. Si

0

ha che in questi casi la condizione per l’esistenza dello stato stazionario è soddisfatta per ogni b>0. Si ottiene

inoltre che

Un modello generale si ottiene combinando i due modelli appena discussi

Nel caso multiservente, invece, si ha:

Sistemi M/M/infinito

Consideriamo ora sistemi in cui si ammetta di avere infiniti serventi. Tale sistema rappresenta in maniera

ottimale il caso di self-service. Anche tali sistemi possono essere rappresentati mediante un processo di

nascita e morte come segue.

Modelli di code con disciplina della coda basata su criteri di priorità

Ci sono sistemi in cui l’ordine rispetto a cui gli utenti in coda vengono selezionati è basato sulla priorità ad

essi assegnata. Per semplicità, per trattare questo caso, supponiamo che il valore atteso è sempre lo stesso per

ogni classe di priorità, mentre la frequenza media degli arrivi può differire a seconda delle classi di priorità

λ

ed indicheremo con la frequenza degli arrivi degli utenti appartenenti alla classe k. Indicheremo con nc il

k

numero delle classi di priorità, intendendo con 1la classe avente la priorità più alta. Esisteranno due tipologie

di classi:

1) Sistemi con priorità con interruzione del servizio, in cui può accadere che un ad un utente sia

interrotto il servizio per l’arrivo nel sistema di un altro utente con priorità superiore rispetto a quella

dell’utente che sta usufruendo del servizio. Inoltre se l’utente poi riscelto nella coda è un utente al

quale era stato precedentemente interrotto il servizio, ci sono due possibilità

i. Viene eseguita solo la parte mancante del servizio

ii. Il servizio ricomincia da capo

Poiché il tempo di servizio è distribuito esponenzialmente, da un punto di vista

probabilistico non risulta rilevante che il servizio interrotto riprenda dal punto in cui

era cessato, oppure dall’inizio per la proprietà dell’assenza della memoria.

2) Sistemi con priorità senza interruzione del servizio, in cui il servizio non può essere interrotto, ma

deve essere portato a termine.

Per entrambi i modelli la distinzione tra clienti in differenti classi non influenza la distribuzione degli arrivi

di tutti gli utenti. Inoltre, poiché tutti i tempi di servizi sono distribuiti esponenzialmente, i due modelli sono

identici al modello M/M/s fatta accezione per l’ordine in cui vengono serviti i clienti. Per analizzare sistemi

di questo tipo occorre introdurre le prestazioni relative ad ogni classe. μ,

Considerando un sistema con s serventi e con velocità media di servizio pari a indipendentemente dalla

λ

classe di priorità, mentre indicheremo con la frequenza media di arrivo per gli utenti della classe i-esima.

i

Si noti che aggregando i processi di arrivo si ottiene sempre un processo di Poisson di parametro pari a

Sistemi a coda con distribuzioni non esponenziali

Dobbiamo considerare che nella realtà esistono casi in cui le assunzioni fini ad ora fatte non sono soddisfatte.

In alcuni casi, infatti, si può avere situazioni di arrivi programmati e non casuali e analogamente ci possono

essere situazioni in cui il tempo di servizio è regolato da schemi prestabiliti e non approssimabili ad una

distribuzione esponenziale. Il processo corrispondente a tali situazioni, in generale, non è un processo

descrivibile mediante processi di nascita e morte. Inizieremo la trattazione di tali modelli eliminando

l’assunzione secondo cui si ha a che fare con una distribuzione esponenziale per i tempi di servizio.

Sistemi M/G/1 is

Assumiamo non vi sia alcuna assunzione sulla distribuzione di probabilità dei tempi di servizio t . Per

analizzare tali sistemi utilizzeremo il metodo basato sui tempi residui di servizio. Assumeremo solo di

σ 2

conoscere la media 1/μ e la varianza della distribuzione dei tempi di servizio. Esiste un teorema che ci

fornisce il valore per il tempo medio di attesa nella coda. Tale risultato, noto come formula di Pollaczek-

q

Kintchine esprime la T in funzione del momento secondo del tempo di servizio.

λ

Teorema: si consideri un sistema M/G/1 in condizioni di stazionarietà. Sia La frequenza media degli arrivi

σ 2

e siano 1/μ e rispettivamente media e varianza dei tempi di servizio. Si ha allora che:

Vediamo la dimostrazione di tale risultato q

Ora possiamo ricavarci tutte le misure di prestazione. Tutte a partire in primo luogo dalla T .

Sistemi M/D/s σ 2

Tali tipi di sistemi a code assumono che i tempi di servizio siano costanti. Ovviamente risulta =0.

Nel caso monoservente si avrà che:

Sistemi M/E /s

K

Vedi slide del professore pag 90-91

ESERCIZIO 1

Una banca ha 5 cassieri ciascuno di essi ha una coda davanti a sé di clienti. I clienti che arrivano scelgono

di essere serviti. Gli arrivi dei clienti sono poissoniani con media di 40 l’ora ed i

una coda a caso e aspettano

tempi di servizio di ciascun cassiere sono esponenziali con media di 5 minuti, la banca sta ipotizzando di

passare ad un sistema a coda unica in cui ogni cliente viene servito dal primo cassiere che si libera.

Determinare l’effetto del cambiamento sul tempo medio di attesa in coda.

SVOLGIMENTO

Ogni fila può essere trattata come un sistema indipendente a coda. Quindi considereremo 5 sistemi di tipo

M/M/1.

ESERCIZIO 2

Un piccolo albergo dispone di 5 camere. Si è dedotto che i clienti arrivano casualmente, ovvero abbiamo

arrivi poissoniani con media di 3 al giorno. La loro permanenza media è di un giorno ed è distribuita

anch’essa esponenzialmente. Determinare:

La probabilità che nell’albergo non vi sia nessun cliente

a. La probabilità che un cliente arrivi e trovi l’albergo pieno d quindi se ne deve andare

b. Il numero medio di clienti nell’albergo

c.

SVOLGIMENTO

CAPITOLO 6

Nella realtà risulta che i sistemi possono presentare sotto forma di più sistemi a coda connessi fra di loro e si

parla quindi di reti di code. In particolare una rete di code può essere descritta come un grafo orientato,

composto da un certo numero di nodi(m) ciascuno dei quali rappresenta un sistema a coda e gli archi

rappresentano le rotte seguite dagli utenti da un sistema all’altro. In tale contesto può anche succedere gli

utenti possono ritornare presso nodi già visitati. Da ora avremo a che fare con una rete di sistemi e non con

un singolo sistema. Tali reti si distinguono in due categorie:

• Reti aperte dove sono possibili gli ingressi di utenti alla rete dall’esterno e le uscite degli utenti della

rete verso l’esterno

• Reti chiuse in cui il numero degli utenti all’interno della rete è fissato e gli utenti circolano

all’interno del sistema rete senza che ci sia la possibilità di ingressi dall’esterno o uscite verso

l’esterno.

Per caratterizzare una rete di code occorre fornire:

• Topologia della rete

• Distribuzione di probabilità dei tempi di interarrivo degli utenti presso i nodi che prevedono ingressi

di utenti

• Distribuzioni di probabilità dei tempi di servizio presso ciascun nodo costituente la rete

• Regole di instradamento …,n

Lo stato della rete in questo caso viene descritto mediante un vettore n=(n ).

1, m

Il primo risultato che ci interessa è quello che va sotto il nome di teorema di Burke, e riguarda un sistema di

tipo M/M/s. Vediamo l’enunciato di tale teorema. λ

Teorema: si consideri un sistema M/M/s con s>=1 con frequenza media di arrivo pari a in condizioni di

stazionarietà. Allora valgono i due seguenti risultati: λ

1. Il processo delle partenze dal sistema è un processo di Poisson di parametro

2. In ogni istante di tempo t, il numero di utenti presenti nel sistema è indipendente dalla sequenza dei

tempi di partenza prima di t

Quello che risulta da tale teorema risulta intuitivo: la prima condizione mi sta dicendo che dato un sistema

M/M/s, gli arrivi sono poissoniani, allora anche le partenze dal sistema risultano un processo di Poisson.

Questo vuole anche dire che se gli utenti escono da un sistema M/M/s ed entrano in un altro sistema a coda,

gli arrivi a questo secondo sistema risulteranno anch’essi poissoniani. Questo vuol dire che assumendo che i

tempi di servizio del secondo sistema siano distribuiti esponenzialmente, il sistema a coda del secondo nodo

si comporta come un sistema M/M/s e può essere studianti indipendentemente dal primo nodo.

Detto questo quindi possiamo affermare che si può collegare in una rete sistemi a coda M/M/s, purché non vi

siano cicli.

Serie di code

Consideriamo ora la più semplice rete di code possibile.

Tale rete è costituita da un generico numero di nodi m collocati in serie, in cui non vi sono limiti sul capacita

della coda di ogni singolo sistema componente la rete. Questo è un esempio di reti quali ad esempio quelle

dei sistemi manifatturieri. Assumiamo che al sistema arrivino utenti secondo un processo di Poisson di

λ

parametro e che in ciascun sistema componente ci siano s serventi, ciascuno operante con tempi di servizio

i

μ

distribuiti esponenzialmente con parametro . Si assuma inoltre che i tempi di servizio siano indipendenti. In

i

condizioni stazionarie, per il teorema di Burke, si ha che ciascuno dei sistemi ha arrivi poissoniani con

λ

parametro e quindi i sistemi possono essere analizzati come tanti sistemi M/M/s isolati.

i

Il caso più semplice corrisponde al caso di due sistemi in serie (detti sistemi tandem) con singolo servente

ciascuno. In questo tipo di sistema si dimostra facilmente che la probabilità congiunta che n utenti siano

1

utenti sono presenti all’interno del secondo sistema è data da:

presenti nel primo sistema e che n 2

Estendendo tale ragionamento al caso generale si ottiene che:

La soluzione che abbiamo scritto è quella che si chiama soluzione in forma prodotto. Tale risultato comporta

che il tempo medio totale di permanenza nell’intero sistema ed il numero medio di utenti presenti nella rete

possono calcolare semplicemente sommando le corrispondenti quantità calcolate in riferimento ai singoli

sistemi. Le considerazioni fatte fino ad ora, però, non valgono nel caso di si parla di sistemi a coda con

capacità limitata e finita.

ESEMPIO 1

Supponiamo di avere un sistema formato da due stazioni di lavoro monoserventi in serie: la prima è una

stazione di lavorazione, la seconda di collaudo. I pezzi arrivano alla prima stazione secondo un processo di

Poisson con media 10 l’ora. I tempi di servizio dei serventi sono distribuiti esponenzialmente con media

di 12 e 15 pezzi l’ora.

rispettivamente

SVOLGIMENTO

Reti di Jackson aperte

All’interno di una rete di Jackson aperta gli utenti possono visitare i nodi in un ordine qualsiasi e in ogni

nodo ci possono essere utenti che arrivano sia dall’esterno sia da altri nodi. Si ha la seguente definizione: una

rete di code aperta si dice rete di Jackson aperta se:

Gli arrivi dall’esterno della rete ad un nodo i della rete sono poissoniani di parametro γ

1. >0 per

i

almeno un i,

2. I tempi di servizio di ciascun servente degli s serventi presenti ad ogni nodo i sono indipendenti e

i

μ

distribuiti esponenzialmente di parametro ,

i

3. Le probabilità che un utente che ha completato il servizio al nodo i si rechi presso il successivo nodo

j è pari a p ed è indipendente dallo stato del sistema.

ij

Il processo delle partenze del sistema sotto opportune ipotesi, è un processo poissoniano come quello delle

entrate (nascite). Siamo arrivati a vedere che la probabilità congiunta si fattorizza nel prodotto delle singole

probabilità.

Dove possiamo vedere una complicazione se pensiamo a un ciclo? Le partenze da questo sistema sono

anche’esse poissoniane. Le uscite del sistema sono un processo che si disaggrega tra coloro che vanno fuori

dalla rete e le entità che invece tornano nel nodo 1. Tale processo iniziale si compone da 2 processi

poissoniani. Questo ciclo perché allora dovrebbe crearci problemi? Noi abbiamo studiato che la

composizione di due processi di Poisson o più ci da un processo di Poisson, sotto l’ipotesi che vi sia

indipendenza tra i processi. Non possiamo quindi applicare in tale caso il risultato, poiché i due processi di

Poisson che stiamo considerando non sono indipendenti. Questo quindi ci fa concludere che i cicli ci fanno

all’entrata dei nodi. Per studiare tali tipi di processi è necessario introdurre delle

perdere la poissonianitá

classi di reti, che si chiamano reti di Jackson.

Rete di Jackson (aperta)

Una rete si configura come una rete di Jackson se:

• γ

Arrivi alla rete poissoniani di parametro i

• I tempi di servizio di ciascuno degli s serventi presenti in un nodo i sono indipendenti e distribuiti

i

μ

esponenzialmente di parametro i

• Le p (probabilità di routing dal nodo i al nodo j) sono note ed indipendenti dallo stato della rete.

ij

Queste p solitamente vengono rappresentate anche in una forma matriciale, ovvero spesso si costruisce

ij

quella che si chiama matrice di routing.

λ?

Per ogni noto j come sarà fatto il λ

Questo non è altro che un sistema lineare non omogeneo che ha come variabili i . Chiamiamo:

i

Dividiamo ora il caso multiservente e monoservente.

Caso monoservente

s =1

j

Teorema di Jackson (reti aperte): sia data una rete aperta di Jackson con m nodi, ciascun a singolo

servente. La distribuzione di probabilità congiunta che la rete si trovi allo stato n, dove n=(n n ) si

1,…, m

…p jnj

fattorizza nel prodotto delle probabilità marginali P(n)= p p , dove p = p (1-ρ ).

n1 n2 nm nj j

L’ipotesi in tale caso è che abbiamo una rete di Jackson, il risultato ci dice che possiamo studiare la rete

come tanti sistemi M/M/1. Il fatto che le p sono fatte nel modo scritto sopra è ciò che dobbiamo andare a

nj

dimostrare. Dimostriamo questo risultato

Dobbiamo andare a riprendere un’equazione di bilancio dettagliato

Facciamo questa cosa per tutti i nodi presenti.

Per il teorema di Jackson una rete di Jackson aperta può essere studiata considerando m sistemi M/M/1, con


ACQUISTATO

2 volte

PAGINE

61

PESO

9.55 MB

AUTORE

dianarsl

PUBBLICATO

6 mesi fa


DETTAGLI
Corso di laurea: Corso di laurea in ingegneria gestionale
SSD:
A.A.: 2018-2019

I contenuti di questa pagina costituiscono rielaborazioni personali del Publisher dianarsl di informazioni apprese con la frequenza delle lezioni di Sistemi di servizio e simulazione e studio autonomo di eventuali libri di riferimento in preparazione dell'esame finale o della tesi. Non devono intendersi come materiale ufficiale dell'università La Sapienza - Uniroma1 o del prof Roma Massimo.

Acquista con carta o conto PayPal

Scarica il file tutte le volte che vuoi

Paga con un conto PayPal per usufruire della garanzia Soddisfatto o rimborsato

Recensioni
Ti è piaciuto questo appunto? Valutalo!

Altri appunti di Sistemi di servizio e simulazione

Appunti del corso Sistemi di servizio e simulazione, prof Massimo Roma, Parte simulazione
Appunto
Appunti Ottimizzazione Combinatoria Gestionale, Sapienza
Appunto
Ottimizzazione Combinatoria - Domande e Risposte Esame
Appunto
Probabilità - Distribuzioni, Rette di Regressione, Vettore Aleatorio
Appunto