Appunti di Sistemi di servizio e simulazione, parte sistemi di servizio, prof. Massimo Roma, La Sapienza, ingegneria gestionale

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