1.5.3 Sistemi M/M/s Kroma/didattica/SSS10-11/parteE.pdf · del sistema inﬁnita, ovvero il caso di...

SISTEMI A CODA BASATI SU PROCESSI DI NASCITA E MORTE 61

1.5.3 Sistemi M/M/s/K

Consideriamo ora sistemi in cui c’e un limite K (capacita del sistema limitata)

sul numero di utenti che il sistema puo contenere contemporaneamente. Natu-

ralmente, poiche s e il numero dei serventi, K − s e la capacita massima della

coda. Ad ogni utente che arriva nel sistema quando la coda e piena e negato

l’accesso definitivamente (cliente perso). Questa situazione si puo interpretare

come un processo di nascita e morte in cui il coefficiente di natalita e nullo in

corrispondenza di certi istanti di tempo, ovvero nei casi in cui risulta n ≥ K. Si

ha, quindi,

λn =

{λ per n = 0, 1, . . . ,K − 1

0 per n ≥ K.

Ovviamente si avra pn = 0 per ogni n > K perche non ci possono essere piu di K

utenti nel sistema; inoltre, il sistema raggiunge condizioni di stazionarieta anche

se la condizione ρ < 1 non e verificata in quanto si ha λn = 0 per n ≥ K.

Da un punto di vista pratico, questa situazione di capacita limitata corrisponde

ad avere spazi fisici limitati per l’attesa. Un’altra interpretazione riguarda la

situazione in cui i clienti in arrivo al sistema vedono troppi utenti (K) davanti

a loro e non entrano nel sistema rinunciando definitivamente al servizio; questa

situazione e nota con il nome di balking (rinuncia).

Sistemi M/M/1/K

Consideriamo prima il caso con un singolo servente. In questo caso si ha Sistemi

M/M/1/Kλn =

{λ per n = 0, 1, . . . ,K − 1

0 per n ≥ K,, µn = µ per n = 1, 2, . . . ,K.

Segue immediatamente che risulta

Πn =

(λ

µ

)n

= ρn per n = 1, . . . ,K

0 per n > K

e quindi per ρ = 1 si ottiene

p0 =1

K∑n=0

ρn=

1

1− ρK+1

1− ρ

=1− ρ

1− ρK+1

ed inoltre

pn =

ρnp0 = ρn

(1− ρ

1− ρK+1

)per n = 0, 1, . . . ,K

0 per n > K,

62 TEORIA DELLE CODE

mentre per ρ = 1, per n = 0, 1, . . . ,K si ha pn =1

K + 1.

Possiamo ora calcolare il valore di N . Infatti risulta

N =K∑

n=0

npn =1− ρ

1− ρK+1

K∑n=0

nρn

=1− ρ

1− ρK+1ρ

K∑n=0

dρn

dρ=

1− ρ

1− ρK+1ρd

dρ

(1− ρK+1

1− ρ

)

=ρ

1− ρ− (K + 1)ρK+1

1− ρK+1. (1.5.17)

Si osservi che, ovviamente, se ρ < 1, al tendere di K all’infinito, il valore di N

appena ottenuto tende a ρ/(1−ρ) che infatti e il valore di N nel caso di capacita

del sistema infinita, ovvero il caso di sistemi M/M/1.

Dall’espressione di N si puo facilmente determinare N q come

N q = N − (1− p0).

Si vuole ora applicare il Teorema di Little per ottenere il valori di T e T q. Per

fare cio, poiche λn non e costante, e necessario calcolare la frequenza media

effettiva degli arrivi λ data dalla (1.5.5). Infatti, nel caso dei sistemi di code

M/M/1/K che stiamo trattando, λ non rappresenta la frequenza media effettiva

degli arrivi perche tiene conto anche degli arrivi che non entrano nel sistema

(perche lo trovano nello stato K). Ora, la probabilita che un utente non possa

entrare nel sistema e uguale alla probabilita che nel sistema ci siano K utenti,

ovvero pK ; quindi la probabilita che un utente accede al sistema e 1−pK e quindi,

per la Proposizione 1.3.6 sulla proprieta dei processi di Poisson disaggregati, la

frequenza media effettiva degli arrivi in questo caso risulta pari a (si veda anche

l’Osservazione 1.3.7)

λ = λ(1− pK). (1.5.18)

D’altra parte, applicando la (1.5.5) si ottiene direttamente la (1.5.18).

La probabilita pK e detta fattore di perdita, in quanto rappresenta la frazione diFattore di

perdita clienti che va perduta perche non entra nel sistema. Definendo ϵ = 1 − pK la

(1.5.18) puo essere riscritta

λ = ϵλ, con ϵ < 1.

Questa relazione mette bene in evidenza che soltanto una frazione di potenziali

clienti entra effettivamente nel sistema, mentre la rimanente parte dei clienti viene

persa.

Sempre nel caso singolo servente (s = 1) la frequenza media effettivi degli arrivi

λ puo essere facilmente ottenuta notando che risulta λ/µ = 1−p0 da cui si ricava

λ = µ(1− p0). (1.5.19)


Una semplice verifica mostra che nel caso che stiamo trattando, queste due

espressioni per λ (la (1.5.18) e la (1.5.19)) ovviamente coincidono, ovvero vale

µ(1− p0) = λ(1− pk).

Osservazione 1.5.13 Per quanto riguarda il raggiungimento delle condizioni di

stazionarieta, come abbiamo gia detto, non e richiesto che ρ = λ/µ < 1. Il fatto

che in un sistema con capacita limitata la frequenza media degli arrivi (λ) possa

superare la frequenza media di completamento dei servizi (ovvero λ > µ) e dovuto

ad una proprieta detta di autoregolazione di un sistema che, escludendo un certo

numero di clienti, porta la frequenza effettiva degli arrivi ad essere minore di

quella del completamento dei servizi.

Esempio 1.5.14 Una stazione di servizio ha un’unica pompa di benzina ed un unico addetto.Le automobili arrivano alla stazione di servizio per rifornirsi secondo un processo di Poisson aduna frequenza media di 10 l’ora. Il tempo necessario per servire un’automobile e distribuitoesponenzialmente con un valor medio pari a 2 minuti. La stazione di servizio puo contenere alpiu 4 automobili e sulla strada vige un divieto di fermata, per cui non e consentito attenderefuori della stazione.Determinare:

1. il numero medio di automobili presenti nella stazione di servizio;

2. la probabilita che un’automobile non possa effettuare il rifornimento;

3. il tempo medio di attesa nella stazione di servizio prima di ottenere il servizio.

La stazione di servizio puo essere vista come un sistema di code M/M/1/4, in cui gli utenti sonole automobili e il servente e l’addetto alla pompa di benzina. Assumendo come unita di tempol’ora, si ha λ = 10, µ = 30, ρ = 1/3 e K = 4.

1. Dalla (1.5.17) si ottiene N = 0.4793;

2. la probabilita che un’automobile non possa effettuare il rifornimento e data da p4 chesi puo ricavare come p4 = ρ4p0 = 1/34p0. E necessario, quindi, il calcolo di p0 =(1− 1/3)/(1− 1/35) = 0.6694. Risulta quindi p4 = 0.008264;

3. E necessario determinare λ = (1− p4)λ = 9.9173 per ottenere T = N/λ = 0.04840 da cuiT q = T − 1/µ = 0.015, ovvero il tempo medio di attesa nella stazione di servizio primadi ottenere il servizio e di circa 54 secondi.


Sistemi M/M/s/K multiservente

Consideriamo ora un sistema M/M/s/K multiservente, ovvero s > 1, supponendoSistemi

M/M/s/K che risulti s ≤ K. Questo caso si tratta in maniera analoga al caso M/M/s gia

visto ponendo

λn =

{λ per n = 0, 1, . . . ,K − 1

0 per n ≥ K,

µn =

{nµ per n = 1, 2, . . . , s− 1

sµ per s ≤ n ≤ K.

Si ottengono quindi i seguenti valori per Πn:

Πn =

1

n!

(λ

µ

)n

per n = 1, 2, . . . , s− 1

1

s!

(λ

µ

)s ( λ

sµ

)n−s

=1

s!sn−s

(λ

µ

)n

per n = s, s+ 1, . . . ,K

0 per n > K.

dal quale si ottiene

pn =

1

n!

(λ

µ

)n

p0, per n = 1, 2, . . . , s− 1

1

s!sn−s

(λ

µ

)n

p0, per n = s, s+ 1, . . . ,K

0 per n > K.

dove il valore di p0 discende immediatamente dal caso gia trattato di sistemi

M/M/s tenendo conto che Πn = 0 per n > K e quindi

p0 =1

s−1∑n=0

1

n!

(λ

µ

)n

+1

s!

(λ

µ

)s K∑n=s

(λ

sµ

)n−s.

Analogamente al caso di un sistema di code M/M/s, si puo ottenere la seguente

espressione per N q:

N q =ρ

s!(1− ρ)2

(λ

µ

)s

p0[1− ρK−s − (K − s)ρK−s(1− ρ)

].


Come nel caso M/M/1/K, applicando il Teorema di Little si possono ottenere

i valori di T q, T ad N . Alternativamente, N puo essere anche ottenuto come

segue. Poiche dalla (1.2.22) si ha

N q =∞∑n=s

(n− s)pn =∞∑n=s

npn − s

(1−

s−1∑n=0

pn

),

allora

N =s−1∑n=0

npn +∞∑n=s

npn =s−1∑n=0

npn +N q + s

(1−

s−1∑n=0

pn

).

Concludiamo il paragrafo considerando il caso in cui risulta K = s, ovvero la

capacita massima del sistema uguaglia il numero dei serventi e quindi la coda ha

capacita nulla. Questo significa che, non esistendo la coda, un utente che arriva

quando tutti i serventi sono occupati non entra nel sistema ed e “perso”. Questo

modello e molto utilizzato nella telefonia; infatti se una rete telefonica ha s linee

ed un utente chiama quando tutte le linee sono occupate, riceve il segnale di

occupato e non puo entrare nel sistema costituito dalla rete telefonica. Si tratta

di un sistema di code dove, di fatto, la coda non esiste ed e noto come Erlang Erlang loss

system

K = s

loss system perche studiato dal gia citato A.K. Erlang.

La probabilita che un utente che arriva trova tutti gli s serventi occupati e quindi

e perso puo essere facilmente calcolata in quanto essa e uguale alla probabilita

pK che nel sistema ci siano gia K utenti, che e data da

pK =1

s!

(λ

µ

)s 1s∑

n=0

1

n!

(λ

µ

)n .

Questa formula e nota come formula di Erlang B.

Esercizio 1.5.15 Un porto possiede un terminal cargo al quale arrivano navi porta-containerper le operazioni di carico-scarico che avvengono attraverso apposite gru. Attualmente il termi-nal dispone di una sola gru e quindi il carico-scarico avviene una nave alla volta. Quando unanave arriva e la gru e gia impegnata in operazioni di carico-scarico, essa attende il proprio turnosecondo una disciplina FIFO in una fila di attesa che supponiamo illimitata. Le navi arrivanoal terminal secondo la distribuzione di Poisson con media 3 al giorno e il tempo che una gruimpiega per il carico-scarico di una nave e distribuito esponenzialmente con media 4 ore.

a) Descrivere un sistema a coda che puo rappresentare la situazione descritta specificandodettagliatamente tutte le sue componenti;

b) determinare il numero medio di navi che sono in attesa di effettuare il carico-scarico;

c) determinare il tempo medio che intercorre tra l’arrivo di una nave al terminal e la suafuoriuscita dal terminal stesso dopo il carico-scarico;

d) determinare come e distribuito il numero totale delle navi presenti nel terminal.


Supponiamo, ora, che lo spazio all’interno del terminal dove le navi attendono il loro turnoprima delle operazioni di carico-scarico sia limitato e non permetta lo stazionamento di piu diquattro navi; le eventuali ulteriori navi che arrivano vengono dirottate presso un altro terminal.

e) descrivere un sistema a coda che rappresenta bene la nuova situazione;

f) spiegare dettagliatamente come si puo ricondurre questo sistema ad un processo di nascitae morte;

g) calcolare il numero medio di navi presenti nel terminal e il tempo medio di attesa in coda;

h) calcolare la probabilita che una nave ha di non poter entrare nel terminal considerato,ovvero di essere dirottata ad altro terminal.


1.5.4 Sistemi M/M/s/ · /U

Si vuole ora considerare il caso in cui la popolazione sia finita, il numero dei

potenziali utenti e finito e pari a U . Naturalmente, se n e il numero degli utenti

presenti nel sistema, i potenziali clienti sono U − n.

Un esempio tipico di questa situazione si ha in un reparto manutenzioni di un

industria. In questo caso, un certo numero di macchine deve essere tenuto in

manutenzione. Tali macchine costituiscono la popolazione finita: ciascuna di esse

entra nel sistema costituito dal reparto manutenzioni quando deve essere riparata

e ne fuoriesce, una volta riparata, andando di nuovo a far parte della popolazione

dei potenziali clienti in quanto potra rientrare nel sistema nel momento in cui si

guasta di nuovo. Un modello che si presta bene a rappresentare una situazione

di questo tipo assume che il tempo che la macchina e al di fuori del sistema

(ovvero il tempo che trascorre da quando la macchina esce dal sistema a quando

rientra) e distribuito esponenzialmente di parametro λ. Quando ci sono n utenti

nel sistema, e quindi U − n utenti sono fuori del sistema, ad un certo istante di

tempo la distribuzione di probabilita del tempo rimanente fino al prossimo arrivo

al sistema coincide con la distribuzione di probabilita del piu piccolo dei tempi

rimanenti per l’ingresso al sistema tra tutti gli utenti che sono fuori del sistema

che sono U − n. Per la Proprieta E2 (assenza di memoria) e la Proprieta E3,

questa distribuzione di probabilita e esponenziale di parametro (U −n)λ. Quindi

anche questo sistema di code puo essere rappresentato mediante un processo

di nascita e morte con coefficiente di natalita pari a λn = (U − n)λ per n =

0, 1, . . . , U − 1 e λn = 0 per n ≥ U in quanto nel sistema non possono esserci

piu di U utenti. Un tale sistema, poiche risulta λn = 0 per n > U , raggiunge

condizioni di stazionarieta anche se ρ ≥ 1.

Sistemi M/M/1/ · /UConsideriamo ora il caso singolo servente, ovvero s = 1. Per rappresentare questo Sistema

M/M/1/·/Ucaso con un processo di nascita e morte e sufficiente prendere

λn =

{(U − n)λ per n = 0, 1, . . . , U − 1

0 per n ≥ U,

µn = µ per n = 1, 2, . . .

Il diagramma di transizione di stato in questo caso e riportato in Figura 1.5.2.

Si ottiene immediatamente

Πn =

U(U − 1)(U − 2) · · · (U − n+ 1)

(λ

µ

)n

=U !

(U − n)!

(λ

µ

)n

per n ≤ U

0 per n > U.


0 1 …

λ)1( −U λ)1( +−nU λ

µ µ

λU

…1−n n 1−U U

µ µ

Fig. 1.5.2 Diagramma di transizione di stato per un sistema M/M/1/ · /U

Risulta quindi

p0 =1

U∑n=0

U !

(U − n)!

(λ

µ

)n(1.5.20)

ed inoltre

pn =

U !

(U − n)!

(λ

µ

)n

p0 per n = 0, 1, . . . , U

0 per n > U.

Calcoliamo ora i valori delle misure di prestazione iniziando da N . Utilizzando

la (1.5.20) si ha

N =U∑

n=0

npn =U∑

n=0

nU !

(U − n)!

(λ

µ

)n

p0

=U∑

n=0

(U − U + n)U !

(U − n)!

(λ

µ

)n

p0

= Up0

U∑n=0

U !

(U − n)!

(λ

µ

)n

−U−1∑n=0

U !

(U − n− 1)!

(λ

µ

)n

p0

= U −U∑

n=1

U !

(U − n)!

(λ

µ

)n−1

p0

= U − µ

λ

U∑n=1

U !

(U − n)!

(λ

µ

)n

p0

= U − µ

λ

U∑n=1

pn = U − µ

λ(1− p0).


Ora, per applicare il Teorema di Little e necessario determinare il valore della

frequenza media effettiva degli arrivi λ data da

λ =∞∑n=0

λnpn =U∑

n=0

(U − n)λpn = λUU∑

n=0

pn − λU∑

n=0

npn = λ(U −N)

e che analogamente al caso di sistemi M/M/1/K si puo scrivere nella forma

µ(1− p0). Quindi di ha

T =N

λ=

N

µ(1− p0)=

U

µ(1− p0)− 1

λ

N q = N − (1− p0) = U − µ

λ(1− p0)− (1− p0) = U − µ+ λ

λ(1− p0)

T q = T − 1

µ=

U

µ(1− p0)− 1

λ− 1

µ.

Sistemi M/M/s/·/U multiservente

Consideriamo, ora il caso di sistemi M/M/s/·/U multiservente, ovvero con s > 1. Sistemi

M/M/s/·/UAnche in questo caso e possibile rappresentare il sistema con un processo di

nascita e morte con i seguenti coefficienti di natalita e di mortalita:

λn =

{(U − n)λ per n = 0, 1, . . . , U − 1

0 per n ≥ U

µn =

{nµ per n = 1, 2, . . . , s− 1

sµ per n = s, s+ 1, . . .

Si ha

Πn =

U !

(U − n)!n!

(λ

µ

)n

per n = 1, 2, . . . , s− 1

U !

(U − n)!s!sn−s

(λ

µ

)n

per n = s, s+ 1, . . . , U

0 per n > U.

dal quale si ottiene

pn =

U !

(U − n)!n!

(λ

µ

)n

p0, per n = 1, 2, . . . , s− 1

U !

(U − n)!s!sn−s

(λ

µ

)n

p0, per n = s, s+ 1, . . . , U

0 per n > U.


dove

p0 =1

s−1∑n=0

U !

(U − n)!n!

(λ

µ

)n

+U∑

n=s

U !

(U − n)!s!sn−s

(λ

µ

)n.

Per quanto riguarda le misure di prestazione, risulta ovviamente

N q =U∑

n=s

(n− s)pn

e non si dispone di una forma compatta per l’espressione della N q; per quanto

riguarda N si ha

N =s−1∑n=0

npn +N q + s

(1−

s−1∑n=0

pn

).

I valori di T e di T q si ricavano come nel caso del singolo servente. Vista la

difficolta di calcolo di questi valori di prestazioni, sono disponibili tavole che

riportano i valori numerici per questa tipologia di sistema di code sia a singolo

servente sia multiservente.

Esercizio 1.5.16 In un’azienda ci sono 5 operatori addetti alla gestione amministrativa dell’azien-da stessa. Essi operano indipendentemente, e possono avvalersi, uno alla volta, della consulenzadi un esperto contabile. In media, il tempo che trascorre dalla conclusione di una consulenzarichiesta da un operatore fino alla richiesta di consulenza successiva e distribuito esponenzial-mente con media 7 ore. La durata della consulenza puo variare anche in maniera significativa,in quanto l’esperto puo aver bisogno di tempi diversi prima di poter dare una risposta al que-sito posto da un operatore; si assuma che tali tempi siano distribuiti esponenzialmente conmedia 1 ora. Inoltre, l’esperto che sta lavorando su un quesito posto da un operatore, nonpuo interrompere il suo lavoro e puo inziare una nuova consulenza solo dopo aver terminato laprecedente.

a) Descrivere un sistema di code che rappresenti la situazione descritta.

b) Descrivere come si puo ricondurre questa situazione ad un processo di nascita e morte.

Inoltre, determinare:

c) quanti operatori, in media, sono in attesa di poter avere la consulenza dell’esperto, ovveroin attesa che l’esperto inizi a lavorare al proprio quesito;

d) quanto tempo, in media, un operatore aspetta quando ha deciso di richiedere una con-sulenza prima di poter sottoporre il suo quesito all’esperto;

e) quanto tempo, in media, passa tra la richiesta di consulenza da parte di un operatore el’ottenimento della risposta al questito sottoposto all’esperto;

f) il valore della frequenza media effettiva con la quale gli operatori chiedono la consulenzaall’esperto, spiegando il suo significato;

g) la probabilita che l’esperto e inoperoso;

h) la probabilita che ad un operatore che necessiti di una consulenza, sia richiesto di aspettareun tempo non nullo prima che l’esperto inizi a lavorare al suo quesito.


1.5.5 Sistemi con velocita di servizio e frequenza di arrivo dipendenti dallo stato

Fino ad ora nello studio dei vari modelli di code, si e sempre assunto che la

velocita media del servizio µ e costante e non dipende dal numero degli utenti

presenti nel sistema. Tuttavia, nelle situazioni reali questo puo non essere sempre

vero, specialmente se i serventi sono delle persone fisiche che e possibile tendano a

lavorare piu in fretta di quanto fanno normalmente se vedono la fila d’attesa molto

lunga. Ovvero, c’e un incremento della velocita media di servizio in conseguenza

della presenza di molti utenti in coda.

Un’altra situazione che potrebbe presentarsi quando la coda e lunga, consiste in

un decremento della frequenza media degli arrivi indotto dal sistema stesso che

nella pratica potrebbe essere realizzato dirottando altrove utenti quando la coda

e molto lunga. Vediamo come e possibile costruire modelli che tengano conto di

queste situazioni.

Caso singolo servente

Iniziamo considerando un sistema di code con servente singolo. Supponiamo

dapprima che la sola velocita di servizio sia dipendente dallo stato. Per tener Velocita di

servizio

dipendente

dallo stato

conto del fatto che tale velocita puo cambiare al variare dello stato, denotiamo

con µ1 la velocita media di servizio in condizioni normali, ovvero con un solo

utente nel sistema (coda vuota) e definiamo µn come segue:

µn = ncµ1, per n = 1, 2, . . . , (1.5.21)

dove c e una costante positiva.

Assumiamo che gli arrivi siano poissoniani di parametro λ e i tempi di servizio

siano distribuiti esponenzialmente di parametro µn dato dalla (1.5.21). Si possono

applicare i risultati sui processi di nascita e morte con λn = λ, tenendo conto che

la condizione per l’esistenza dello stato stazionario e soddisfatta per ogni c > 0.

Si ottiene

Πn =1

(n!)c

(λ

µ1

)n

, n = 1, 2, . . .

da cui si ha

pn =1

(n!)c

(λ

µ1

)n

p0

con

p0 =1

∞∑n=0

1

(n!)c

(λ

µ1

)n

dalle quale si possono ottenere i valori delle misure di prestazione. Tuttavia non

sono disponibili espressioni analitiche delle serie che compaiono nelle formule, per


cui sono stati tabulati valori approssimati per p0 ed N per diversi valori di c e

λ/µ1 troncando le serie a somme finite.

Un interessante caso particolare si ha in corrispondenza della scelta c = 1. In

questo caso si ha µn = nµ e

p0 = e− λ

µ1 , pn =1

n!

(λ

µ1

)n

e− λ

µ1 .

Riprenderemo in esame questo caso nel succesivo paragrafo 1.5.6.

Esaminiamo ora la situazione in cui la sola frequenza di arrivo dipende dalloFrequenza di

arrivo

dipendente

dallo stato

stato. Supponiamo quindi di avere una decrescita della frequenza media degli

arrivi, ad esempio in presenza di una coda molto lunga. Questo caso e anche

detto ad “arrivi rallentati” in quanto prevede il rallentamento progressivo degli

arrivi in rapporto al numero dei clienti presenti nel sistema. Un modello che puo

rappresentare bene questa situazione si ottiene assumendo che i tempi di servizio

siano distribuiti esponenzialmente di parametro costante µ e che gli arrivi siano

poissoniani con parametro non costante e dato da

λn =1

(n+ 1)bλ0 per n = 0, 1, . . . ,

dove λ0 e la frequenza media di arrivo in condizioni normali, ovvero con la coda

vuota, e b e una costante positiva. Analogamente al caso precedente della velocita

di servizio dipendente dallo stato, si possono applicare i risultati sui processi

di nascita e morte tenendo conto che la condizione per l’esistenza dello stato

stazionario e soddisfatta per ogni b > 0, ottenendo

Πn =1

(n!)b

(λ0

µ

)n

, n = 1, 2, . . .

da cui si ha

pn =1

(n!)b

(λ0

µ

)n

p0

con

p0 =1

∞∑n=0

1

(n!)b

(λ0

µ

)n

dalle quale si possono ottenere i valori delle misure di prestazione. Anche in

questo caso un interessante caso particolare si ha in corrispondenza della scelta

b = 1.


Un modello generale si ottiene combinando i due modelli ora discussi ovvero

ponendo

λn =λ0

(n+ 1)b

µn = naµ1.

Analogamente ai casi precedenti si ha

Πn =1

(n!)a+b

(λ0

µ1

)n

, n = 1, 2, . . .

da cui si ottiene

pn =1

(n!)a+b

(λ0

µ1

)n

p0

con

p0 =1

∞∑n=0

1

(n!)a+b

(λ0

µ1

)n .

Quindi si hanno gli stessi risultati gia ottenuti nel primo dei due casi considerati,

sostituendo c con a+ b e λ/µ1 con λ0/µ1 e si possono utilizzare i valori tabulati

per determinare p0 ed N .

Caso multiservente

Passiamo ora al caso di piu serventi considerando direttamente l’ultimo dei mo-

delli trattati nel caso singolo servente, ovvero quello piu generale ottenuto come Caso

multi-

servente

combinazione del modello che tiene conto dell’aumento della velocita media di

servizio e del modello che tiene conto della diminuzione della frequenza media

di arrivo. Nel caso in cui si hanno s > 1 serventi, la variazione di λn e di µn

dipendera da n/s, ovvero dal numero di utenti per servente e quindi di ha

λn =

λ0 per n ≤ s− 1

λ0(n+ 1

s

)bper n ≥ s

µn =

nµ1 per n ≤ s(n

s

)a

sµ1 per n > s


da cui

Πn =

1

n!

(λ0

µ1

)n

per n = 1, . . . s

1

n!

(λ0

µ1

)n 1

s!(n!/s!)cs(1−c)(n−s)per n = s+ 1, . . .

dove c = a + b. I valori di p0, N , N q sono stati tabulati per diversi valori di c,

di λ0, di µ1 e s. Sono stati inoltre realizzati grafici che riportano i valori di p0e di N al variare di λ0/(sµ1) e che possono risultare molto utili per determinare

valori approssimati delle misure di prestazioni.

Esempio 1.5.17 Si consideri di nuovo il problema della gestione di un pronto soccorso di unospedale esaminato nell’Esempio 1.5.9. Un modello piu aderente alla realta di quelli visti finoad ora per questo problema dovrebbe infatti considerare il fatto che il tempo che un medicoimpiega per curare un pazienze che arriva al pronto soccorso, potrebbe tendere realisticamentea diminuire all’aumentare del numero dei pazienti che sono in fila di attesa. Questo perche insituazioni di affollamento il medico incarica un infermiere di completare il trattamento e passaad un nuovo paziente. Supponiamo, in questa nuova ottica, che il tempo che il medico passain media a curare un paziente sia di 24 minuti se non c’e nessun altro paziente che aspetta,mentre questo tempo diventa di 12 minuti se ci sono 5 o piu pazienti in coda (ovvero 6 utentinel sistema). Quindi si ha µ1 = 5/2 e µ6 = 5. Da cui, poiche assumiamo µ6 = 6cµ1 si hac = 0.386. Poiche lo scopo e sempre quello di confrontare le due alternative date da un solomedico (s = 1) e due medici (s = 2), vogliamo ricavare le misure di prestazione di questo sistemain corrispondenza di questi due valori di s. Innanzitutto osserviamo che

λ0

sµ1={0.8 per s = 10.4 per s = 2.

Dai valori tabulati o dai grafici si ricavano i seguenti valori per p0 e N :

• per s = 1, p0 = 0.367 e N = 1.251;

• per s = 2, p0 = 0.440 e N = 0.864.

Calcoliamo i valori di Nq, T e T q nei due casi:

• per s = 1 si ottieneNq = N−(1−p0) = 0.618, T = Nλ = 0.6255 ore e T q = Nq/λ = 0.309ore;

• per s = 2 si ottiene p1 = (λ0/µ1)p0 = 0.352, Nq = N − p1 − 2(1 − p0 − p1) = 0.096,T = N/λ = 0.432 ore e T q = Nq/λ = 0.048 ore.

Si puo inoltre calcolare la probabilita di attendere in coda un tempo non nullo, ovvero P (T q > 0);

• per s = 1 si ha P (T q > 0) = 1− p0 = 0.633;

• per s = 2 si ha P (T q > 0) = 1− p0 − p1 = 0.208.

Anche dall’analisi dei risultati ottenuti con questo nuovo modello si deduce che l’utilizzo di unsolo medico non permette di avere un servizio efficiente nel pronto soccorso.


1.5.6 Sistemi M/M/∞

Consideriamo, ora, un altro modello di sistemi di code che presenti arrivi poisso-

niani di parametro λ e tempi di servizio distribuiti esponenzialmente con parame-

tro µ, assumendo di avere infiniti serventi. Questo modello teorico corrisponde

al caso in cui un servente e immediatamente disponibile all’arrivo di un utente.

Risulta utile a studiare situazioni in cui un sistema presenta un servizio “self

service”, ovvero gli utenti che arrivano si servono da soli senza dover aspettare.

Tali sistemi sono frequenti nella realta e possono essere rappresentanti anch’essi

attraverso un processo di nascita e morte con

λn = λ per n = 0, 1, . . .

µn = nµ per n = 1, 2, . . .

Si ottiene

Πn =1

n!

(λ

µ

)n

n = 1, 2, . . .

e la condizione di esistenza dello stato stazionario e verificata per qualsiasi valore

di λ e µ. Si tratta, quindi, di un caso particolare di sistema con velocita di servizio

dipende dallo stato esaminato nel paragrafo precedente; possiamo facilmente os-

servare che quindi un sistema in cui la velocita di servizio dipende linearmente

dallo stato si comporta come un sistema con servente immediatamente disponi-

bile.

Naturalmente si ha

p0 =1

∞∑n=0

1

n!

(λ

µ

)n = e−λ

µ ,

pn =1

n!

(λ

µ

)n

e−λ

µ .

Quindi, in condizioni di stazionarieta, il numero degli utenti presenti nel sistema

e distribuito secondo Poisson di parametro λ/µ e quindi risulta

N =λ

µ

ed inoltre, ovviamente, N q = 0 e T q = 0, in quanto non sono previste attese in

coda. Segue che

T = T q +1

µ=

1

µ,

ovvero il valor medio del tempo di permanenza nel sistema coincide con il valore

atteso del tempo di servizio 1/µ.


1.6 SISTEMI A CODA CON DISTRIBUZIONI NON ESPONENZIALI

Fino ad ora abbiamo considerato modelli di code basati su processi di nascita e

morte, con tempi di interarrivo e tempi di servizio distribuiti esponenzialmente e

abbiamo analizzato le importanti proprieta di tali modelli e il loro efficace uso nel

rappresentare situazioni reali. Tuttavia, esistono casi reali in cui le assunzioni fino

ad ora fatte non sono soddisfatte. Ad esempio, sappiamo che gli arrivi secondo

Poisson approssimano bene gli arrivi casuali che rappresentano una ragionevole

assunzione in moltissime situazioni; tuttavia in alcuni casi, si possono invece

avere situazioni di arrivi programmati e non piu casuali. Analogamente, non sono

infrequenti situazioni in cui i tempi di servizio sono regolati da schemi prestabiliti

che non sono approssimati bene da una distribuzione esponenziale.

Per queste ragioni, in questo paragrafo verrano esaminati modelli di code che

utilizzano distribuzioni diverse da quella esponenziale. L’analisi di questi modelli

risulta, in genere, molto piu difficile dell’analisi compiuta fino ad ora sui sistemi

basati su distribuzioni esponenziali in quanto il processo corrispondente ad un

tale modello non e piu, in generale, un processo di nascite e morte.

Inizieremo questa trattazione rimuovendo la sola assunzione di avere una dis-

tribuzione esponenziale dei tempi di servizio e quindi considerando modelli gen-

erali M/G/s e la loro particolarizzazione ai modelli M/D/s e M/Ek/s. Successi-

vamente considereremo modelli che non abbiano arrivi poissoniani.

1.6.1 Sistemi M/G/1

Consideriamo sistemi di code in cui gli arrivi sono di tipo poissoniano e i tempi di

servizio siano indipendenti, identicamente distribuiti, supponendo che non ci sia

alcuna assunzione sulla distribuzione di probabilita di tali tempi di servizio tsi .

Osserviamo innanzitutto che la proprieta PASTA vista nel paragrafo 1.5.1 valida

per ogni sistema con arrivi poissoniani, ovviamente, continua a valere anche nel

caso che stiamo esaminando.

Passiamo ora allo studio analitico dei sistemi M/G/1. Esistono diversi metodi di

analisi; utilizzeremo, nel seguito, quello basato sui tempi residui del servizio. As-

sumeremo solamente di conoscere la media 1/µ e la varianza σ2 della distribuzione

dei tempi di servizio.

Nonostante non sia stata fatta alcuna assunzione sulla distribuzione dei tempi di

servizio, esiste un risultato generale che fornisce il valore per il tempo medio di

attesa nella coda T q. Tale risultato e noto come formula di Pollaczek–KintchineFormula di

Pollaczek–

Kintchine

ed esprime la T q in funzione del momento secondo del tempo di servizio E((tsi )

2).

Naturalmente, vale

E((tsi )

2)= V ar(tsi ) + [E(tsi )]

2 = σ2 + 1/µ2. (1.6.1)

Riportiamo tale formula nel teorema che segue.

SISTEMI A CODA CON DISTRIBUZIONI NON ESPONENZIALI 77

Teorema 1.6.1 Si consideri un sistema M/G/1 in condizioni di stazionarieta.

Sia λ la frequenza media degli arrivi e siano 1/µ e σ2 rispettivamente la media

e la varianza dei tempi di servizio. Allora si ha

T q = λσ2 + 1/µ2

2(1− ρ).

Dimostrazione: Supponiamo che la disciplina della coda sia di tipo FIFO. In-

dichiamo con Ri il tempo residuo al completamento del servizio visto dall’i-esimo

utente quando arriva (ovvero, se un utente j sta usufruendo del servizio quando

arriva l’utente i arriva, Ri e il tempo necessario affinche sia completato il servizio

sull’utente j). Indichiamo, inoltre, con nqi il numero degli utenti trovati nella

coda dall’i-esimo utente quando arriva.

Naturalmente risulta

tqi = Ri +i−1∑

j=i−nqi

tsj . (1.6.2)

Prendendo il valore atteso6 ad entrambi i membri della (1.6.2), si ha

E(tqi ) = E(Ri) + E(tsj)E(nqi ) = E(Ri) +

1

µE(nq

i ). (1.6.3)

Si osservi che la Ri e la nqi sono quantita viste dall’utente che arriva, ma, poiche

gli arrivi sono poissoniani, tali quantita coincidono con le corripsondenti quantita

viste da un osservatore esterno che osserva il sistema in un istante arbitrario.

Passando al limite per i → ∞ nella (1.6.3), assumendo che questi limiti esistano,

si ha

T q = R+1

µN q, (1.6.4)

dove R e il tempo residuo medio (a regime) definito da R = limi→∞

E(Ri). Ora,

poiche risulta N q = λT q, dalla (1.6.4) si ha

T q = R+λ

µT q

da cui si ottiene

T q =R

1− ρ. (1.6.5)

6Si utilizza un noto risultato di teoria della probabilita secondo il quale, avendo X1, . . . , Xm variabilialeatorie indipendendenti, identicamente distribuite, con media comune E(X) ed m e una variabilealeatoria che puo assumere valori 0, 1, . . ., allora

E(X1 + · · ·+Xm) = E(X)E(m)


)(τR

st1

st1st2

st2

τt

Fig. 1.6.1 Grafico del tempo residuo

Per completare la dimostrazione rimane da calcolare il valore di R. Effettueremo

questo calcolo con l’ausilio di un grafico. Riportiamo, infatti, in Figura 1.6.1 il

grafico del tempo residuo del servizio R(τ) in funzione del tempo τ , ovvero il

tempo che rimane per il completamento del servizio del cliente che sta usufru-

endo del servizio al tempo τ , assumendo R(0) = 0. Ovviamente, quando un

nuovo servizio di durata tsi inizia, R(τ) ha valore tsi , poi decresce linearmente.

Consideriamo, ora, un istante di tempo t per il quale risulti R(t) = 0 e indichi-

amo con D(t) il numero di arrivi (ovvero di partenze) nell’intervallo [0, t]. La

media temporale di R(τ) nell’intervallo [0, t] e data da

1

t

∫ t

0R(τ)dτ.

Poiche

∫ t

0R(τ)dτ rappresenta l’area della superficie racchiusa tra la funzione

R(τ) e l’asse delle ascisse, tale area e anche uguale alla somma delle aree dei

triangoli, ovvero da

D(t)∑i=1

1

2(tsi )

2. Risulta quindi

1

t

∫ t

0R(τ)dτ =

1

t

D(t)∑i=1

1

2(tsi )

2. (1.6.6)


Ora, moltiplicando e dividendo per D(t) al secondo membro della (1.6.6) si ha

1

t

∫ t

0R(τ)dτ =

1

2

D(t)

t

D(t)∑i=1

(tsi )2

D(t)(1.6.7)

e passando al limite per t → ∞ nella (1.6.7) (assumendo che i limiti esistano) si

ha

limt→∞

1

t

∫ t

0R(τ)dτ =

1

2limt→∞

D(t)

tlimt→∞

D(t)∑i=1

(tsi )2

D(t). (1.6.8)

Ora, poiche per t sufficientemente grande vale l’uguaglianza tra media temporale

e valore atteso, si ha

limt→∞

1

t

∫ t

0R(τ)dτ = lim

i→∞E(Ri) = R,

ed inoltre

limt→∞

D(t)

t= λ.

Infine, per la legge forte dei grandi numeri, si ha

limt→∞

D(t)∑i=1

(tsi )2

D(t)= E

((tsi )

2).

Quindi la (1.6.8) diventa

R =1

2λE

((tsi )

2)

e sostituendo questo valore di R ora ottenuto nella (1.6.5), utilizzando la (1.6.1)

la dimostrazione e completata.

Osservazione 1.6.1 Abbiamo derivato la formula di Pollaczek–Kintchine as-

sumendo che la disciplina della coda sia di tipo FIFO, ma la formula rimane

valida in generale comunque si scelga la disciplina della coda purche essa sia in-

dipendente dal tempo di servizio richiesto. Non e invece valida se l’ordine con

cui si accede al servizio dipende dal tempo si servizio.

Una volta determinato il valore di T q dalla formula di Pollaczek–Kintchine, si

possono determinare i valori delle altre misure di prestazione, ovvero

N q = λT q =λ2σ2 + ρ2

2(1− ρ)

N = N q + ρ =λ2σ2 + ρ2

2(1− ρ)+ ρ

T =N

λ=

λσ2 + λ/µ2

2(1− ρ)+

1

µ.


Osservazione 1.6.2 Se consideriamo un sistema di code M/M/1 come caso par-

ticolare di un sistema M/G/1, si ha σ2 = 1/µ2 e quindi l’applicazione della

formula di Pollaczek–Kintchine fornisce per T q il valore T q = λ/[µ(µ − λ)] che

naturalmente coincide con l’espressione di T q gia determinata nel caso di sistema

M/M/1.

Osservazione 1.6.3 Osservando l’espressione di T q, N q ed N si vede che a

parita di λ e µ, queste grandezze aumentano all’aumentare della varianza del

tempo di servizio σ2. Da questo punto di vista, la situazione ideale (ovvero

quella che minimizza queste grandezze) si otterrebbe con σ2 = 0 che si ha con

tempi di servizio costanti, ovvero per sistemi di tipo M/D/1. Si tenga presente

che, a parita di valore atteso, si puo intervenire sui tempi di servizio per renderli

piu regolari possibile (ovvero rendendo la varianza piccola). Questo e molto

importante perche mostra che la “regolarita” del servizio assume una grande

importanza da questo punto di vista, e che quindi non e sufficiente considerare

la velocita media del servizio.

La grande flessibilita dei modelli M/G/1 li rende molto utili, ma il prezzo da pa-

gare per questa loro generalita sta nel fatto che, purtroppo, non sono disponibili,

nel caso generale, risultati per sistemi multiservente, ovvero per sistemi M/G/s

con s > 1.

Nel seguito esaminiamo due casi particolari importanti: i sistemi M/D/s e i

sistemi M/Ek/s.

Sistemi M/D/s

I sistemi di code M/D/s assumono tempi di servizio costanti; essi forniscono unSistemi

M/D/s buon modello per situazioni in cui il servizio e effettuato sempre attraverso una

medesima procedura. Naturalmente risulta σ2 = 0.

Per quanto riguarda il caso singolo servente (s = 1), i valori delle misure di

prestazione si ottengono dal caso generale di sistemi M/G/1 ponendo σ2 = 0. In

particolare, si avra:

T q =1

2

λ

µ(µ− λ)

N q =1

2

ρ2

1− ρ

N =ρ2

2(1− ρ)+ ρ

T =λ/µ2

2(1− ρ)+

1

µ.

Soffermandoci ad osservare i valori di T q e di N q si vede che essi risultano pari

esattamente alla meta dei valori corrispondenti per un sistema di code M/M/1


(dove σ2 = 1/µ2). Questo evidenzia il fatto che una diminuzione di σ2 porta ad

un notevole miglioramento (diminuzione) di T q e di N q.

Per quanto riguarda il caso multiservente, (s > 1) esiste un metodo per deter-

minare la distribuzione di probabilita del numero degli utenti nel sistema, in

condizioni di stazionarieta, ma esso esula dallo scopo di queste note perche molto

tecnico e particolare. Esistono anche in questo caso risultati tabulati e grafici

dell’andamento di N in funzione di ρ = λ/(sµ).

Sistemi M/Ek/s

In termini di deviazione standard (σ), i sistemi M/D/s e M/M/s rappresentano Sistemi

M/Ek/sdue situazioni estreme: i primi assumono che non ci siano variazioni nei tempi di

servizio, (infatti σ = 0), mentre i secondi assumono tempi di servizio distribuiti

esponenzialmente con una variazione che puo essere anche molto grande (σ =

1/µ). Tra questi due casi estremi si colloca una distribuzione importante per la

quale risulta 0 < σ < 1/µ e che rappresenta bene i tempi di servizio in molte

situazioni reali: si tratta della distribuzione di Erlang (Ek) di parametri k e µ a

media 1/µ, la cui densita di probabilita e data da

f(t) =(µk)k

(k − 1)!tk−1e−kµt, t ≥ 0.

Una tale distribuzione di probabilita ha varianza pari a 1/(kµ2) e deviazione

standard σ pari a 1/(√kµ) e quindi se i tempi di servizio seguono questa dis-

tribuzione, il parametro k rappresenta una sorta di “grado di variabilita” dei

tempi di servizio.

Richiamiamo il fatto che la sua importanza deriva da due punti fondamentali:

• e una famiglia di distribuzioni a due parametri e quindi con scelte opportune

si riesce ad approssimare bene un tempo di servizio reale ed inoltre per

k = 1 si ottiene la distribuzione esponenziale e per k → ∞ essa tende alla

distribuzione degenere (σ → 0);

• dalla Proprieta E5 della distribuzione esponenziale, si ha che la somma di k

variabili indipendenti, identicamente distribuite esponenzialmente ciascuna

con media 1/(kµ), ha distribuzione di Erlang Ek. Quindi se un servizio si

compone di k operazioni successive a ciascuna delle quali e associato un

tempo di servizio distribuito esponenzialmente con media 1/(kµ), allora il

tempo di servizio complessivo segue la distribuzione di Erlang Ek.

Per quanto riguarda il caso singolo servente (s = 1) dalle formule generali per

un sistema M/G/1 si ottengono i valori delle misure di prestazione per sistemi

M/Ek/1 ponendo σ2 = 1/(kµ2), ovvero

T q =1 + k

2k

λ

µ(µ− λ)


N q =1 + k

2k

λ2

µ(µ− λ)

T = T q +1

µ=

1 + k

2k

λ

µ(µ− λ)+

1

µ

N = λT =1 + k

2k

λ2

µ(µ− λ)+

λ

µ.

Per quanto riguarda il caso multiservente (s > 1), non e possibile ottenere ana-

liticamente la distribuzione di probabilita del numero degli utenti presenti nel sis-

tema in condizioni di stazionarieta. Tuttavia, anche in questo caso sono disponi-

bili valori tabulati e grafici di N al variare di ρ = 1/(sµ).

1.6.2 Sistemi con arrivi non poissoniani

Concludiamo questo paragrafo con alcuni cenni ai sistemi di code che non presen-

tano arrivi secondo Poisson. Infatti, come abbiamo gia visto per quanto riguarda

i tempi di servizio, anche il processo degli arrivi potrebbe non essere casuale,

ma essere programmato in una qualche forma. Possiamo pertanto considerare

modelli dei seguenti tipi:

• GI/M/s : non impongono restrizioni sul processo degli arrivi;

• D/M/s : gli arrivi sono ad intervalli regolari;

• Ek/M/s : gli arrivi seguono la distribuzione di Erlang Ek.

Per tutti i tre tipi ora menzionati si e assunto che i tempi di servizio sono dis-

tribuiti esponenzialmente. Tuttavia e possibile considerare anche modelli ancora

piu generali come Em/Ek/s, Ek/D/s, D/Ek/s.

La trattazione di questi modelli esula dallo scopo di queste note e pertanto essi

non verranno trattati.

MODELLI DI CODE CON DISCIPLINA DELLA CODA BASATA SU CRITERI DI PRIORITA 83

1.7 MODELLI DI CODE CON DISCIPLINA DELLA CODA BASATA SU

CRITERI DI PRIORITA

Nella realta si possono presentare situazioni in cui in un sistema di servizio la

disciplina della coda e basata su criteri di priorita, ovvero l’ordine rispetto al quale

gli utenti in coda vengono selezionati e basato sulla priorita ad essi assegnata.

Situazioni reali in cui questo puo accadere sono molteplici: si pensi, ad esempio,

all’esigenza in un pronto soccorso di intervenire prima sui pazienti piu gravi,

oppure a situazioni in cui utenti “importanti” hanno la precedenza su altri.

L’analisi e piuttosto complicata e in questo paragrafo ci limiteremo a consider-

are modelli nei quali si assume che, per ogni classe di priorita, gli arrivi siano

poissoniani e che i tempi di servizio siano esponenziali; inoltre, per semplicita,

assumeremo che il valore atteso del tempo di servizio e lo stesso per ogni classe

di priorita, mentre la frequenza media degli arrivi puo differire a seconda delle

classi di priorita. Indicheremo, inoltre, con nc il numero delle classi di priorita,

intendendo che la classe 1 e quella con la piu alta priorita; la selezione dalla coda

avviene scegliendo un utente nella classe di priorita piu alta e, all’interno della

classe, con il criterio FIFO.

Esistono due tipologie di questi sistemi di code:

• sistemi con priorita con interruzione del servizio (priorita con diritto di

prelazione),

• sistemi con priorita senza interruzione del servizio (priorita senza diritto di

prelazione).

Nel caso di sistemi con interruzione del servizio puo accadere che ad un utente Priorita

interrut-

tiva

sia interrotto il servizio (facendolo ritornare in coda) per l’arrivo nel sistema di

un’altro utente con priorita superiore rispetto a quella dell’utente che sta usufru-

endo del servizio, ovvero il servente e tenuto ad iniziare immediatamente il servizio

al nuovo utente con priorita piu elevata. Al termine del servizio, verra effettuata

un’altra selezione dalla coda. Se l’utente prescelto e uno di quelli ai quali era

stato precedentemente interrotto il servizio, ci sono due possibilita: viene ese-

guita soltanto la parte mancante per il completamento del servizio (preemptive

resume systems), oppure il servizio deve ricominciare dall’inizio (preemptive re-

peat systems). Poiche il tempo di servizio e distribuito esponenzialmente, da un

punto di vista probabilistico, non e rilevante che il servizio interrotto riprenda dal

punto in cui era cessato oppure dall’inizio per la proprieta di assenza di memoria

della distribuzione esponenziale.

Nel caso di sistemi con priorita senza interruzione del servizio il servizio non puo Priorita

non inter-

ruttiva

essere interrotto, ma deve essere portato a termine.

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

la distribuzione degli arrivi di tutti gli utenti, ovvero degli arrivi aggregati senza


tenere conto delle classi; infatti, per la Proposizione 1.3.6, un processo risultante

dall’aggregazione di processi di Poisson e ancora un processo di Poisson. Inoltre,

poiche tutti i tempi di servizio sono distribuiti esponenzialmente, i due modelli

(con priorita con o senza interruzione del servizio) sono identici al modello M/M/s

fatta eccezione per l’ordine in cui vengono serviti gli utenti, e quindi continuano

a valere le espressioni per N , N q, T e T q ottenute per quel modello. Si osservi,

pero, che T q potrebbe non essere piu il valore atteso del tempo passato in coda

se il servizio viene interrotto con conseguente ulteriore permanenza in coda.

Inoltre cambia la distribuzione dei tempi di attesa che era stata ottenuta in rifer-

imento ad una disciplina di selezione dalla coda di tipo FIFO. Con la disciplina

della coda basata su criteri di priorita, questa distribuzione ha una varianza piu

grande perche i tempi di attesa degli utenti in classi di priorita alta tendono ad

essere piu brevi di quelli con una disciplina di tipo FIFO, mentre quelli degli

utenti in classi di priorita piu basse tendono ad essere piu lunghi. Analogamente,

l’insieme degli utenti presenti nel sistema tendera ad essere per la maggior parte

composto da utenti delle classi di priorita piu basse, in accordo con lo spirito

dei sistemi di code con priorita, ovvero con l’intento di migliorare le misure di

prestazione per gli utenti delle classi di priorita piu alte a scapito, eventualmente,

delle prestazioni per gli utenti nelle classi piu basse.

Per analizzare sistemi di questo tipo dobbiamo introdurre misure di prestazione

relative ad ogni classe; faremo cio inserendo un pedice alle notazioni gia adottate

per indicarne la classe di riferimento; quindi Tk indichera il valore atteso del

tempo passato nel sistema dagli utenti della k-esima classe di priorita e notazioni

analoghe si adotteranno per Nk, Tqk e N q

k .

Consideriamo un sistema con s serventi supponendo che velocita media di servizio

sia pari a µ indipendente dalla classe di priorita, mentre per quanto riguarda il

processo degli arrivi, indicheremo con λi, i = 1, . . . , nc, la frequenza media di

arrivo per gli utenti della classe i-esima. Per la Proposizione 1.3.6 dei processi

di Poisson, aggregando i vari processi di arrivo, ovvero non distinguendo tra le

classi di priorita, si ottiene ancora un processo di Poisson di parametro

λ =nc∑i=1

λi.

Inoltre si assume che∑k

i=1 λi < sµ in modo che la classe di priorita k-esima possa

raggiungere condizioni di stazionarieta.

Si riportano di seguito le espressioni delle misure di prestazione (relative a cias-

cuna classe di priorita) nelle due tipologie di sistemi di code con disciplina della

coda basata su criteri di priorita.

Sistemi con priorita senza interruzione del servizio

Consideriamo il caso in cui non sono consentite interruzioni di un servizio. In

MODELLI DI CODE CON DISCIPLINA DELLA CODA BASATA SU CRITERI DI PRIORITA 85

questo caso, l’espressione per T qk e la seguente

T qk =

1

abk−1bk, k = 1, . . . , nc,

dove

a = s!sµ− λ(λ

µ

)s

s−1∑j=0

1

j!

(λ

µ

)j

+ sµ,

b0 = 1, bk = 1−

k∑i=1

λi

sµ. (1.7.1)

Ad ogni singola classe di priorita si applica il Teorema di Little e si ha

N qk = λkT

qk , k = 1, . . . , nc.

Risulta inoltre

Tk = T qk +

1

µ

Nk = λkTk.

Sistemi con priorita con interruzione del servizio

Consideriamo ora un sistema in cui si prevede l’interruzione di un servizio per

l’arrivo di un utente con priorita piu alta di quella dell’utente che sta usufruendo

del servizio.

Nel caso si singolo servente, ovvero s = 1, si ha la seguente espressione per Tk:

Tk =

1

µ

bk−1bk, k = 1, . . . , nc,

dove le bk sono gia state definite in (1.7.1).

Nel caso multiservente, ovvero s > 1, per determinare Tk si usa una procedura

iterativa che illustriamo di seguito. Tale procedura e basata sul fatto che i tempi

di permanenza nel sistema per gli utenti di una certa classe di priorita non sono

influenzati dalla presenza di utenti nelle classi di priorita piu basse. Quindi il

valore di T1 sara lo stesso per ogni valore di λ2, λ3, . . . , λnc, e quindi anche per

λ2 = λ3 = · · · = λnc = 0. Questo vuol dire che T1 deve essere uguale al valore

T corrispondente ad una sola classe per un sistema M/M/s con λ = λ1 e quindi

si puo calcolare facilmente. Calcolato T1, si prendono in considerazione le prime

due classi di priorita, la prima e la seconda. Anche in questo caso i tempi di

permanenza nel sistema dei clienti di queste due classi non sono influenzati dagli


utenti nelle classi inferiori che quindi possono essere ignorati. Sia T1,2 il valore

atteso del tempo di permanenza nel sistema per gli utenti che arrivano e che

appartengono alle due classi che stiamo considerando; la probabilita che essi

appartengano alla prima classe e p1 = λ1/(λ1 + λ2), mentre la probabilita che

appartengano alla seconda classe e p2 = λ2/(λ1 + λ2). Si ha quindi

T1,2 = p1T1 + p2T2. (1.7.2)

Ora, poche i valori attesi dei tempi sono uguali per ogni disciplina della coda,

il valore di T1,2 deve essere uguale al valore di T per un sistema M/M/s con

λ = λ1+λ2 e quindi si puo calcolare facilmente. Noti T1,2 e T1, si ricava T2 dalla

(1.7.2). Analogamente, si itera il procedimento alle prime tre classi: si indica

con T1,3 il valore atteso del tempo di permanenza del sistema per gli utenti delle

prime tre classi di priorita; la probabilita che essi appartengano rispettivamente

alla prima, alla seconda e alla terza classe e p1 = λ1/(λ1 + λ2 + λ3), p2 =

λ2/(λ1 + λ2 + λ3) e p3 = λ3/(λ1 + λ2 + λ3), da cui

T1,3 = p1T1 + p2T2 + p3T3. (1.7.3)

Inoltre T1,3 deve essere uguale al valore di T per un sistema M/M/s con λ =

λ1 + λ2 + λ3 e quindi si ricava facilmente il suo valore. Noti T1, T2 e T1,3 dalla

(1.7.3) si ricava T3. Iterando il procedimento si ottengono i valori di Tk, per

k = 1, 2, . . . , nc.

In entrambi i casi (singolo e multiservente) una volta determinata T k, per ogni

k = 1, , . . . nc si ricavano.

Nk = λkTk

T qk = Tk −

1

µ

N qk = λkT

qk .

1.5.3 Sistemi M/M/s Kroma/didattica/SSS10-11/parteE.pdf · del sistema inﬁnita, ovvero il caso di...

Documents

Transcript of 1.5.3 Sistemi M/M/s Kroma/didattica/SSS10-11/parteE.pdf · del sistema inﬁnita, ovvero il caso di...