Sistemi a coda con retrials: il caso Mk/Gk/1/r

ismo di servizio, la disciplina della fila d’attesa (cioè l’ordine in cui i clienti
sono serviti) e il numero di coloro che prestano il sevizio (serventi). Si pos-
sono costruire tanti modelli quanti sono i sistemi di attesa che si presentano
variando le condizioni dei loro elementi caratteristici. Tali modelli perme-
ttono di valutare le conseguenze delle diverse alternative al fine di rendere
massima l’efficienza del servizio al minimo costo.
I modelli rappresentativi di sistemi a coda classici non prendono in con-
siderazione, però, un altro aspetto della realtà delle file d’attesa che è quel-
lo del mancato successo di una domanda e, in particolare, del fatto che,
dopo un tempo casuale, tale domanda verrà, quasi certamente, ripetuta.
Un esempio molto semplice, ma altrettanto significativo, è costituito da un
centralino telefonico: è noto a tutti che un utente telefonico che trova la lin-
ea occupata ripete la chiamata finché non ottiene la connessione richiesta.
Non tener conto di questo fattore vuol dire lasciare irrisolti un numero di
problemi molto importanti da un punto di vista pratico.
Una nuova classe di sistemi a coda, i sistemi con utenti ripetenti (o code
con retrials) è stata introdotta per l’analisi di questi nuovi sistemi..
Questa categoria di code è caratterizzata dalla seguente peculiarità: un
cliente che arrivi quando tutti i serventi a lui accessibili sono occupati,
lascia l’area di servizio, ma dopo un tempo casuale ripete la domanda. Tale
caratteristica gioca un ruolo speciale sia nel singolo computer che anche
nelle reti di comunicazione. L’analisi di tali sistemi, però, presenta grandi
difficoltà analitiche ed esistono risultati dettagliati solo per speciali code con
retrials.
In questo lavoro viene studiato il sistema a coda Mk/Gk/1/r con retrial
e flusso d’ingresso multidimensionale.
Nel capitolo 1 si introducono i sistemi a coda e si descrivono i parametri
che li definiscono e gli indici di prestazione. In particolare vengono studiate
e risolte particolari code con distribuzione dei tempi di servizio generale:
M/G/1 ed M/G/1/r.
4
Nel capitolo 2 vengono presentati i sistemi a coda con retrial ed anal-
izzati i principali sistemi a singolo servente come il sistema M/M/1/0 ed
M/G/1/0.
Nel capitolo 3 viene studiato un sistema del tipo Mk/Gk/1/r/s che pre-
senta la seguente caratteristica: un utente che trova tutti i posti occupati
nell’area di attesa si unisce al gruppo di utenti nell’orbita (area di attesa
immaginaria in cui si trovano virtualmente i clienti dopo un tentativo non
riuscito) di capacità limitata per poi ritentare la sua richiesta di servizio. Un
importante risultato raggiunto è che l’analisi di un tale sistema può essere
ridotta all’analisi di in sistema a coda simile con un solo flusso di Poisson.
È stato implementato un algoritmo numerico in Matematica, con cui
sono stati forniti risultati numerici e calcolati importanti indici di presta-
zione.
5
Capitolo 1
La Teoria delle Code
1.1 Introduzione
LaTeoria delle Code (o file d’attesa) è una disciplina della matematica ap-
plicata che si propone di sviluppare modelli per lo studio dei fenomeni d’at-
tesa che si possono manifestare in presenza di una domanda di un servizio.
Quando la domanda stessa e/o la capacità di erogazione del servizio sono
soggette ad aleatorietà, si possono, infatti, verificare situazioni temporanee
in cui chi fornisce il servizio non ha la possibilità di soddisfare immedi-
atamente le richieste. La stessa esperienza comune suggerisce che i campi
di applicazione della teoria delle code sono estremamente numerosi. Ad
esempio sono in generale soggetti ad attese:
- i clienti in banca o in posta;
- le persone in attesa di un taxi o, comunque, le chiamate ad un servizio di
radiotaxi;
- le automobili ad un incrocio;
- gli aerei in attesa di decollare o di atterrare;
- le parti in attesa di essere lavorate;
6
- le macchine in avaria in un’officina;
- i progetti di legge in parlamento;
. . .
ne consegue che i risultati ottenibili della Teoria delle Code trovano
applicazione, ad esempio, nei:
- sistemi di elaborazione;
- sistemi di comunicazione / trasmissione dati;
- sistemi di trasporto;
- sistemi flessibili di lavorazione;
. . .
In particolare i concetti fondamentali della Teoria delle Code venivano
formalizzati nel 1917 da A.K.Erlang (1878 - 1929) proprio per applicarli
nel settore telefonico. L’ingegnere danese dell’azienda telefonica di Cope-
nhagen, per la prima volta, si servì della matematica per risolvere un pro-
blema così pratico: ridurre le file migliorando il servizio. Il suo problema
nacque quando si propose di eliminare la congestione del traffico telefonico
che si verificava con le centrali automatiche. La Teoria delle Code, dunque,
può trovare applicazione non solo nel settore industriale e dei servizi, ma
può portare immediati vantaggi anche alla qualità della vita delle persone
comuni. A dispetto dell’apparente semplicità di formulazioni e di metodi di
risoluzione, è una disciplina complessa che richiede strumenti metodologici
raffinati provenienti dall’analisi matematica, il calcolo delle probabilità e la
statistica.
7
1.2 Il sistema a coda e le sue componenti
Dal punto di vista dinamico una coda è costituita essenzialmente da due
processi stocastici: il processo d’ingresso dei clienti e il processo di
servizio.
Dal punto di vista fisico un sistema a coda è un sistema composto da
un insieme non vuoto di serventi, capaci di fornire un servizio imprecisato,
e da un insieme non vuoto di aree di attesa (buffer) capaci di accogliere
i clienti che non possono essere serviti immediatamente.
I clienti che non trovano un servente libero al loro arrivo si dispongono in
modo ordinato, cioè in coda, e vengono serviti in accordo a determinate dis-
cipline di servizio.Gli elementi che permettono di definire completamente
Servente
Servente
Servente
Fila di Attesa
Coda
Traffico
di Ingresso
Traffico
di Uscita
Servizio
Figura 1-1: struttura di un sistema a coda
il fenomeno d’attesa sono quindi:
- la popolazione dei clienti;
8
- il processo d’ingresso;
- la coda (in senso stretto);
- i serventi;
- il processo di servizio;
- la disciplina di servizio.
La popolazione è l’insieme dei potenziali clienti, ovvero l’insieme da cui
arrivano i clienti e a cui tornano dopo essere stati serviti. Essa può essere
finita o infinita. Nel primo caso le modalità di arrivo dei clienti dipendono
dal numero di loro correntemente nel sistema.
Una tipica situazione in cui si può ritenere che i clienti provengano da
una popolazione finita è quando essi devono presentarsi forniti di (o con-
tenuti in) determinate strutture disponibili in numero limitato; ad esempio
in ambiente manifatturiero spesso le parti per essere lavorate devono essere
poste su opportuni pallet.
I clienti di una stessa popolazione sono tra loro indistinguibili, di con-
seguenza si suppone essi provengano da popolazioni differenti ogni qualvolta
in cui debbano essere distinti, ad esempio per livello di priorità o tipo di
servizio richiesto.
Il processo d’ingresso, che descrive il modo secondo cui i clienti si
presentano, è in generale un processo stocastico. Esso è definito in termini
della distribuzione del tempo di inter-arrivo τ i, cioè dell’intervallo di
tempo che intercorre tra l’arrivo di due clienti successivi l’i-esimo e l’i+1-
esimo, dove i rappresenta l’ordine di presentazione della richiesta di servizio
a partire dall’istante iniziale τ0 di osservazione del sistema.
Consideriamo i tempi di inter-arrivo come variabili aleatorie indipendenti
ed identicamente distribuite le quali definiscono un processo stocastico a
tempo discreto detto processo di ingresso del sistema a coda.
Per ottenere modelli analiticamente trattabili di solito si assume che sia
il processo di arrivo che quello di servizio siano stazionari, ovvero che le
9
loro proprietà statistiche non varino nel tempo. Tale assunzione in certi
ambiti può essere molto limitativa, infatti l’esperienza comune suggerisce
che ad esempio il processo di arrivo dei clienti ad una banca varia durante
le ore della giornata.
Il modello più comunemente usato per questo tipo di processo è di tipo
esponenziale:
fτ (t) =
1
τ¯
e−
1
τ¯ t = λe−λt,
dove τ¯ indica il tempo medio di inter-arrivo e λ è detta frequenza
media di inter-arrivo.
Tale modello esponenziale è il più utilizzato nelle reti di comunicazione
quando il coefficiente di variazione Cτ = στ
τ¯
risulta prossimo all’unità, es-
sendo τ¯ = 1
λ
e σ2τ =
1
λ2
, in caso contrario per la variabile τ¯ si deve assumere
un altro modello. In alcune applicazioni è conveniente assegnare alla τ¯ una
distribuzione caratterizzata attraverso i suoi momenti: τ¯ , τ¯2, τ¯3, ... e si par-
la, allora, di distribuzione generale. Un caso particolare è la distribuzione
deterministica in cui tutti i momenti centrali di ordine superiore al primo
sono nulli, ovvero quando τ¯ è una costante uguale a τ¯∗.
La coda (in senso stretto), ovvero la fila di attesa, è formata dai clienti
presenti nel buffer in attesa di essere serviti. La capacità del buffer può
essere infinita o finita. Nel secondo caso essa limita necessariamente la
capacità del sistema, cioè il numero dei clienti in attesa nel buffer più
quelli che correntemente sono serviti. I clienti, infatti, che arrivano dopo
che sia saturata quest’ultima capacità vengono respinti.
Ad esempio ha capacità di sistema limitata un centralino telefonico che
può tenere in attesa solo un numero finito di chiamate. In assenza di cen-
tralino la dimensione della coda è addirittura zero, di conseguenza una
chiamata o è servita immediatamente o è rifiutata.
I serventi sono in numero noto e costante fissato a livello di progetto.
Usualmente essi hanno caratteristiche identiche, possono sempre lavorare in
10
parallelo, viceversa non possono mai rimanere inattivi in presenza di clienti
in coda. Anche se vi sono più serventi in una coda, in generale, si assume
l’esistenza di un unico buffer comune, quando infatti ogni servente ha il
suo buffer separato si preferisce pensare ad un insieme di code. Può, però,
essere comodo introdurre, almeno logicamente, più buffer in presenza di
clienti provenienti da popolazioni diverse.
Il processo dei servizi descrive il modo secondo cui ciascun servente
eroga il servizio, in particolare definisce la durata dello stesso ed è di solito
un processo stocastico. Esso è definito in termini delle distribuzioni dei
tempi di servizio θi dei diversi serventi cioè il tempo necessario a servire
l’i-esimo utente che entra nel sistema a coda.
Consideriamo i tempi di servizio come delle variabili aleatorie indipen-
denti ed identicamente distribuite che definiscono un processo stocastico a
tempo discreto detto processo di servizio del sistema a coda. Il processo
dei servizi è alimentato dal processo d’ingresso, di conseguenza il processo
d’ingresso è indipendente e condiziona il processo dei servizi. Un cliente,
infatti, può essere servito solo se è già arrivato. Quando non c’è nessuno,
il servente è inattivo e quindi non può avvantaggiarsi in vista d’impegni
futuri. In altre parole un servente non può servire in anticipo clienti non
ancora arrivati. Non può, dunque, esistere una coda negativa.
Questo tipo di processo, generalmente, è supposto essere di tipo espo-
nenziale:
fθ(t) =
1
θ¯
e−
1
θ¯
t = µe−µt,
dove θ¯ è il tempo medio di servizio e µ = 1
θ¯
indica la frequenza media
di servizio.
La scelta della distribuzione esponenziale, a cui corrisponde un coef-
ficiente di variazione unitario, è spesso, però, inadeguata alla rappresen-
tazione delle situazioni reali. Si ricorre, allora, a distribuzioni di tipo analogo
a quelle già considerate nel processo di ingresso.
11
La disciplina di servizio specifica quale sarà il prossimo cliente servito
fra quelli in attesa al momento in cui si libera un servente. Le discipline
di servizio usualmente considerate, sia perché molto comuni nella realtà sia
perché matematicamente trattabili, sono le seguenti:
- servizio in ordine di arrivo FCFS (first-come first-served) o FIFO (first-
in first-out);
- servizio in ordine inverso di arrivo LCFS (last-come first-served) o LIFO
(last-in first-out);
- servizio in ordine casuale SIRO (service in random order);
- servizio basato su classi di priorità (vedi centri di emergenza quali il pron-
to soccorso).
1.2.1 La notazione di Kendall
Nel 1951 D.G. Kendall, nel lavoro “Some Problems in the Theory of Queues”,
usò per la prima volta il termine sistema a coda e introdusse, così, le no-
tazioni base che portano il suo nome, per descrivere un sistema di questo
tipo.
Tutti gli elementi che definiscono una coda sono, dunque, evidenziati
nella seguente notazione A/B/m/L/n/Z detta, per l’appunto, di Kendall,
dove le lettere stanno ad indicare, rispettivamente:
A: la distribuzione degli intertempi d’arrivo;
B: la distribuzione dei tempi di servizio;
m: il numero di serventi;
L: la capacità del sistema (default: infinita);
n: la dimensione della popolazione (default: infinito);
12