La t. delle c. o delle file di attesa è un argomento di ricerca operativa che solo recentemente è stato visto nella sua importanza. Che cosa sia una coda è noto a tutti, dato che l'insegna l'esperienza quotidiana. Si fa la coda per pagare il pedaggio all'ingresso delle autostrade, sotto i semafori, nei negozi affollati, ecc. Nei paesi anglosassoni poi la coda sembra una istituzione nazionale. Il problema delle code o, come si dice anche più esattamente, delle code d'attesa è però ben più vasto. Così gli aerei che giungono ad un aeroporto affollato fanno la coda in attesa che si liberi la pista d'atterraggio; le navi che devono essere caricate o scaricate fanno la coda, un manufatto su una linea di montaggio fa la coda davanti alla macchina o all'operaio che deve compiere una certa operazione, le chiamate telefoniche fanno la coda in attesa che le centraliniste possano smistarle, ecc. Il problema delle chiamate telefoniche attraverso un centralino non automatizzato fu appunto il primo caso studiato che diede origine alla t. delle c. Primo studioso che si dedicò a questo compito fu A.K. Erlang della compagnia telefonica di Copenhagen a partire dal 1908. Nella sua formulazione più recente, la t. delle c. è un tipico studio di processi stocastici, cioè di quei processi che studiano l'evoluzione di sistemi non deterministici, ovvero di quei sistemi la cui evoluzione futura non si può ricavare dalla storia passata ma solo prevedere in termini probabilistici con l'aiuto della statistica. Per fare ciò, la t. delle c. deve ricorrere ad una formulazione matematica di un modello del sistema. Ciò non è possibile senza ricorrere a complessi algoritmi matematici per la cui comprensione occorrono solide basi statistiche; in questa voce la t. delle c. sarà pertanto trattata solo in generale, senza introdurre nessun calcolo. Il lettore interessato all'argomento è rimandato alla copiosa letteratura ormai esistente, quasi tutta in lingua inglese. Fra le opere in italiano citiamo la Teoria delle code Di Avondo-Bodino e Brambilla (1959) e gli Elementi introduttivi alla teoria delle code di A. Tosalli (1968). I presupposti necessari per la creazione di una coda sono l'esistenza di clienti, cioè di persone o cose che richiedono un determinato servizio, un centro o stazione di servizio, nel quale quel certo servizio è effettuato da un certo numero di persone o macchine, un processo di accesso al servizio e una disciplina della fila di attesa. Quest'ultima in molti casi è la semplice regola "primo arrivato primo servito"; in altri casi si hanno delle regole di priorità per cui un certo cliente può passare davanti ad un altro e ottenere prima di lui il servizio: ad es. un malato gravissimo in un ospedale, un aereo in avaria o a corto di carburante sulla pista di atterraggio, una macchina più importante di quelle che attendono di essere riparate, ecc. La t. delle c. si basa sul presupposto che tutti quelli che giungono ad una determinata stazione di servizio per ottenere il servizio lo possono ottenere immediatamente se la stazione è libera, mentre dovranno attendere il loro turno (formando un fila di attesa) se la stazione sta già servendo un cliente. Il sistema esaminato si compone quindi dei clienti in attesa, della stazione di servizio e del processo di accesso al servizio; una volta che un cliente è soddisfatto se ne va, e quindi esce dal sistema. Vi sono però dei casi in cui il cliente soddisfatto si pone in coda alla fila in quanto ha di nuovo bisogno del servizio: è ad es. il caso dei diversi utenti di un calcolatore elettronico (in time sharing): dopo che il calcolatore ha svolto un programma di un certo utente passa a svolgere quelli di altri; affinché quell'utente possa svolgere il secondo dei suoi programmi deve di nuovo seguire le regole di accesso, e quindi porsi in coda. Diversa è ad es. la situazione in un negozio: una volta che un cliente giunge alla stazione di servizio (il banco di vendita) esso viene completamente soddisfatto, quale che sia il numero di operazioni (acquisti) che deve fare. Un altro caso ancora è quello in cui i clienti sono serviti a gruppi; anche il cliente isolato che arrivi alla stazione di servizio vuota deve attendere finché vi è un certo gruppo di altri clienti prima di avere il servizio; questo caso è comune nel trasporto delle merci (si attende di averne una quantità sufficiente per caricare completamente un autotreno, un carro ferroviario, una nave, ecc.) ma può presentarsi anche in altri casi (ad es. una guida che accompagna i turisti a visitare un monumento attende che ve ne sia un certo numero prima di iniziare il giro e la sua spiegazione). Naturalmente questi diversi problemi richiedono un'impostazione diversa. Gli elementi che caratterizzano una fila di attesa sono i seguenti tre: a) Tempo di attesa (medio) e di servizio di un cliente; b) Numero di clienti in attesa, ossia lunghezza istantanea della coda (misurabile in termini di unità); c) Rapporto fra il tempo di attesa e il tempo di servizio. Il caso più semplice è quello in cui i clienti arrivano alla stazione di servizio con un ordine determinato (ad es. uno ogni dieci minuti) e che tutti richiedano tempi di servizio uguali: posto in questi termini il problema è estremamente semplice, ed è risolubile con un semplice algoritmo, onde non rientra nemmeno nella t. delle c. Sono invece interessanti i problemi in cui i clienti arrivano a caso, cioè statisticamente (distribuiti nel tempo secondo una legge statistica da individuare caso per caso); il tempo di servizio può essere costante per tutti i clienti o può essere anch'esso variabile e distribuito con un'altra legge statistica (uguale o diversa da quella di arrivo). Naturalmente i problemi più interessanti sono quelli che si profilano in termini economici, più o meno direttamente. Si prenda un esempio: un'azienda meccanica possiede un grande numero di macchine utensili che periodicamente si arrestano (ad intervalli statistici) per guasti e un'officina di manutenzione che ha il compito di rimettere in efficienza le macchine guaste. Naturalmente è possibile prevedere un'officina di dimensioni tali che anche se tutte le macchine si guastassero contemporaneamente esse sarebbero riparate tutte prontamente. Ciò evidentemente non è economico, in quanto un simile evento è improbabile, e si avrebbe un'officina che lavorerebbe praticamente sempre al di sotto delle sue possibilità. Nello stesso modo si potrebbe pensare di prevedere un'officina in grado di riparare solo una macchina alla volta: in questo caso si può verificare la situazione che una o più macchine si guastino mentre l'officina è occupata a ripararne una avariatasi in precedenza, e quindi si forma una coda di attesa. Se la potenzialità dell'officina è troppo bassa si può avere addirittura il caso che la lunghezza della coda tende all'infinito, cioè che il numero di macchine guaste in attesa di riparazione cresce a dismisura fino a raggiungere il numero totale delle macchine, bloccando completamente la produzione. Senza giungere a questi casi estremi, è chiaro che sia una coda mediamente troppo lunga sia un'officina che lavori molto al di sotto delle sue possibilità rappresentano due situazioni di perdita per l'azienda: si deve quindi progettare un'officina avente una potenzialità opportuna, in modo che la somma delle perdite per i tempi in cui l'officina non lavora e per le macchine che non lavorano sia minima. Molto spesso si ha il caso in cui il servizio è fornito da una persona (o azienda) diversa dalle persone o (aziende) che ne sono clienti. Naturalmente chi fornisce il servizio tende allora ad effettuarlo con la minima attrezzatura possibile, mentre i clienti desiderano avere dei tempi di attese quanto più piccoli possibili; le due esigenze sono evidentemente contrastanti. A prima vista parrebbe che se un certo servizio impegna la stazione ad es. per 2 minuti mentre i clienti giungono con la media di 30 all'ora (cioè mediamente proprio uno ogni 2 minuti) la stazione sia sufficiente a smaltire tutti i clienti senza che il loro tempo di attesa salga molto. La t. delle c. dimostra che ciò è falso: in una siffatta situazione la lunghezza della coda tende ad infinito e ugualmente all'infinito tende il tempo di attesa (medio). Questo fatto si può spiegare in parte intuitivamente senza ricorrere alla matematica. Infatti nella situazione detta vi saranno dei tempi morti, cioè dei tempi in cui la stazione non effettua nessun servizio per mancanza di clienti: questi tempi sono persi irrimediabilmente, e quindi non potranno essere soddisfatti tutti i clienti che arrivano in un certo periodo di tempo successivo e che saranno in quantità maggiore della media, dato che vi è stato prima un periodo di tempo in cui non è giunto nessun cliente. In questi casi la matematica dimostra che un piccolo aumento delle unità di servizio (cioè l'adozione di un numero un po' maggiore di persone o macchine che effettuano il servizio) ovvero una breve riduzione della durata del servizio rende molto minore sia il tempo di attesa medio sia il numero di clienti che devono attendere. Un'altra variabile può intervenire in certi casi. Se il servizio non è indispensabile o se esso può essere sostituito in qualche modo da un altro servizio, un cliente che giunge in una stazione dove vi sia una lunga coda può rinunciare al servizio (in vista del lungo tempo di attesa che gli si prospetta): naturalmente chi gestisce il servizio subirà una perdita dovuta al mancato guadagno per la perdita di un cliente. È questo il caso banale di chi si serve di un taxi perché stanco di attendere l'autobus ovvero di chi rinuncia all'acquisto di un modello di automobile (o si orienta su un altro) per il lungo tempo di consegna. A volte l'esigenza di non perdere clienti (anche in vista del fatto che i clienti attuali lo saranno di nuovo probabilmente in futuro) può consigliare un sovradimensionamento della stazione di servizio, fino a ridurre a pochissimo il tempo di attesa e ad una percentuale molto bassa il numero di clienti che non ottengono immediatamente il servizio. Uno dei campi in cui la t. delle c. trova una feconda applicazione è la gestione delle scorte. Il caso più generale è che la richiesta delle merci ad una certa azienda che si occupa della loro vendita sia variabile nel tempo, secondo una legge statistica che si suppone determinabile. L'azienda, per mantenere le merci a magazzino, subisce delle perdite quali i frutti del capitale investito nell'acquisto, il costo di affitto del magazzino, ecc.; vi sono poi delle perdite eventuali dovute al deterioramento della merce (particolarmente importante nel caso di derrate alimentari) o al fatto che, trascorso un certo periodo (ignoto), la merce può diventare invendibile (ad es. un elettrodomestico dopo che è stato prodotto un modello nuovo molto perfezionato). Tutti questi costi vanno a diminuire il guadagno che l'azienda ha dal ricavo della vendita delle merci. Sarebbe quindi consigliabile tenere a magazzino una quantità minima di merci. In questo caso però vi è la possibilità che le scorte non bastino a soddisfare la domanda nel tempo che intercorre fra una nuova ordinazione di merce e il suo arrivo a magazzino. Si avrebbe allora una perdita dovuta al mancato guadagno per i clienti che l'azienda non ha potuto accontentare. Mediante la t. delle c. si può - caso per caso - trovare quale deve essere la quantità a magazzino di una certa merce affinché il guadagno dell'azienda sia massimo e quando devono essere fatte le nuove ordinazioni, e di quale entità devono essere (tenuto conto evidentemente che anche l'ordinazione ha un suo costo intrinseco, indipendente dalla quantità di merce ordinata). Un'altra applicazione, molto recente, della t. delle c. è la regolazione semaforica a mezzo calcolatore elettronico, adottata in certe città per rendere minimo il tempo che un automobilista deve impiegare per spostarsi da un punto all'altro della città. Un nuovo capitolo della t. delle c. nel quale si indirizzavano diversi studi è quello della presenza contemporanea di diverse code e di una o più stazioni. Un caso particolare è quello di diverse code poste in luoghi diversi, servite ciclicamente da una sola stazione. Si può vedere subito che anche se gli arrivi di clienti alle diverse code è indipendente, la lunghezza di una coda è influenzata da quella delle altre. Questo problema, detto polling problem, è facilmente illustrabile con un esempio. Si abbia un tram (stazione di servizio mobile) che percorre un percorso circolare sul quale si trovano un certo numero di fermate dove si formano le code di viaggiatori in attesa. Giunto ad una fermata, il tram si trattiene fin che non ha caricato tutti i passeggeri ivi in attesa. È evidente che la presenza ad una fermata di una lunga coda fa sì che il tram vi si trattenga molto più a lungo. Nel frattempo però le altre code non sono rimaste invariate, perché si sono allungate in quanto vi giungono continuamente nuovi passeggeri in attesa del tram. Di conseguenza la lunghezza di una coda si ripercuote su quella di tutte le altre e quindi, in definitiva, sul tempo totale che il tram impiega a percorrere tutto il suo giro, ovvero sulla sua velocità media. Immaginiamo che su questa linea il tram considerato sia l'unico. Quando esso torna alla stazione dove vi era la lunga coda dato che esso avrà impiegato un tempo più lungo a percorrere il suo giro, la coda si sarà riformata e così tutte le altre; anzi, saranno mediamente più lunghe delle precedenti in quanto esso passa in ritardo rispetto alla sua normale tabella di marcia. Il fenomeno quindi tende ad aggravarsi da solo e la situazione si normalizza solo quando l'afflusso dei viaggiatori alle varie fermate diventa sensibilmente inferiore a quello medio. All'instaurarsi di simili disfunzioni si può provvedere solo immettendo sulla linea un secondo tram (o aumentando il numero di convogli in funzione se ve n'è già più d'uno), cosa che è normale nelle ore di punta in tutte le città. Il problema dei trasporti tranviari nelle ore di punta è anche aggravato dal rallentamento che subiscono i convogli a causa del maggior traffico automobilistico, del quale però si può tener conto anche in una formulazione matematica basata sulla t. delle c. Si è già citato il caso del time sharing dei calcolatori elettronici: diversi utenti utilizzano tutti un solo calcolatore elettronico al quale sono collegati mediante organi periferici detti terminali. Il problema che si pone è come distribuire il tempo fra i vari utenti. Il metodo più semplice sarebbe quello di far sì che il calcolatore svolga tutti i problemi di un utente e poi passi a quello successivo e così via, ricominciando poi dal primo. La situazione è analoga a quella del tram sul percorso circolare: un problema troppo lungo intaserebbe per così dire il traffico, con grave disagio degli altri utenti. Si ricorre allora alla limitazione del tempo: dopo che il calcolatore ha svolto per un certo tempo (ad es. 5 secondi) il problema di un utente senza terminarlo, lo sospende e passa all'utente successivo. Vi sono però certi utenti che hanno un bisogno immediato del servizio del calcolatore. Se questo ad es. controlla un laminatoio (dal quale esce qualche decina di metri di laminato al secondo) deve essere pronto ad intervenire (nel giro di decimi o centesimi di secondo) non appena il laminato non risponde più alle norme. Certe società di calcolatori hanno quindi modificato il sistema del servizio ciclico ai vari utenti con l'adozione di un codice di precedenze: gli utenti sono divisi ad es. in 10 classi, numerate 0,1 ...9. L'utente di classe 0 ha la precedenza assoluta, i problemi che sono in corso di esecuzione, vengono sospesi per svolgere i suoi. I problemi degli altri utenti sono svolti ciclicamente come sopra, a pari precedenza. Il calcolatore esamina tutti i terminali e svolge i problemi di precedenza 1, poi fa di nuovo il giro per svolgere quelli di precedenza 2 e così via. In tal modo però un utente ad es. della classe 7 non verrebbe mai servito se quelli delle classi precedenti impegnano continuamente il calcolatore. Si ricorre allora al cambio di classe: ogni volta che il calcolatore esamina un terminale sul quale gli è proposto un problema ma non lo svolge perché ne ha di una classe più bassa, quel problema cambia di classe; ad es. se è di un utente di classe 7 viene considerato di classe 6 e così via. È evidente che in questo modo tutti i problemi saranno svolti in un tempo abbastanza breve. Naturalmente queste regole di attesa alle code complicano ulteriormente l'unità di controllo del calcolatore. In questo campo sono tuttavia in corso molte ricerche.