Code, teoria delle

Enciclopedia della Matematica (2013)

code, teoria delle


code, teoria delle settore della ricerca operativa che studia i processi in cui si formano liste d’attesa. Tali liste si formano perché più unità (o clienti) vogliono accedere a un servizio che è erogato con risorse limitate e la cui fornitura richiede un tempo non necessariamente costante e non del tutto prevedibile (è dunque una variabile aleatoria); la richiesta di servizio non può quindi essere immediatamente soddisfatta. I clienti, che arrivano in istanti successivi di tempo, anch’essi aleatori, si dispongono quindi in coda, in attesa dell’erogazione del servizio. Scopo della teoria è la gestione dei sistemi di coda, l’ottimizzazione, la valutazione economica e la soddisfazione del cliente. La teoria ha preso le mosse da problemi connessi con i servizi telefonici; le sue prime formulazioni in termini matematici sono dovute ad Agner Krarup Erlang (1878-1929), ingegnere danese della Compagnia dei telefoni di Copenaghen, che pubblicò un primo lavoro su tale materia nel 1909. La teoria delle code, poiché esamina l’evoluzione nel tempo di variabili aleatorie, si situa all’interno dello studio dei processi stocastici, è parte della teoria della probabilità, ha connessioni con la statistica e trova applicazioni a numerosi problemi di natura sia scientifica sia organizzativa (file di persone agli uffici postali, code di automobili ai caselli autostradali, liste di attesa in ospedali e ambulatori, gestione dei trasporti).

Componenti di un sistema di coda sono la popolazione (insieme dei potenziali clienti), che può essere finita o infinita, gli arrivi dei clienti, la coda (i clienti in attesa di usufruire del servizio) e i servizi. Gli arrivi dei clienti possono essere singoli, in gruppo, programmati o casuali; altra caratteristica degli arrivi è il tempo che intercorre tra l’arrivo di un cliente e un altro (interarrivi) e il tasso medio degli arrivi, cioè il numero medio degli arrivi nell’unità di tempo. Se si indica con λ il tasso medio di arrivo, il tempo medio di interarrivo è 1/ λ. La legge più comune per la distribuzione di probabilità dei tempi di interarrivo è la legge esponenziale in funzione del tempo ƒ(t) = λe−λt.

Lo stato di una coda dipende dal numero di clienti presenti nel sistema, dalla distribuzione di probabilità del tempo di servizio, dal tempo trascorso dall’ultimo arrivo e, per ogni servizio in corso, dal tempo trascorso dall’inizio del servizio.

Per rappresentare le caratteristiche di una coda si usa la notazione detta di Kendall: A/B/c/K/m/Z. I sei parametri indicano:

• A: la distribuzione dei tempi degli interarrivi;

• B: la distribuzione dei tempi dei servizi;

• c: il numero di canali di servizi (per esempio il numero di sportelli in un ufficio postale);

• K: la capacità del sistema (il numero massimo di clienti ammissibili, oltre il quale i nuovi arrivi sono rifiutati);

• m: la numerosità della popolazione in arrivo;

• Z: l’ordine di priorità di smaltimento della coda.

I parametri A e B possono assumere uno dei seguenti valori: M (se la distribuzione è markoviana, cioè esponenziale negativa come descritto sopra), D (se la distribuzione è deterministica), Ek (distribuzione di Erlang di ordine k, valore atteso e previsione del tempo in cui si può verificare il k-esimo successo in un processo con distribuzione di Poisson), G (generica). Il parametro indicato con Z, cioè la modalità di smaltimento delle unità in coda, può essere differente a seconda del problema: può essere di tipo fifo (first in - first out: il primo in coda è il primo a essere servito, come per esempio negli uffici postali), di tipo lifo (last in - last out: l’ultimo arrivato è il primo a uscire dalla coda, come nelle pile di dati), di tipo prioritario (come per esempio nelle sale d’attesa di pronto soccorso, dove si stabiliscono priorità sulla base di un primo esame di urgenza) o di tipo casuale (per esempio con estrazione).

Lo studio della teoria delle code permette di determinare alcuni indici di prestazione, strettamente legati ai costi e ai profitti, come il numero medio dei clienti in attesa del servizio, il tempo di attesa medio dei clienti nel sistema e il fattore di utilizzo del servizio.

TAG

Distribuzione di probabilità

Agner krarup erlang

Processi stocastici

Teoria delle code

Ricerca operativa