Teoria delle code

La teoria delle code è lo studio matematico delle linee di attesa (o code) e di vari processi correlati, come l'arrivo alla fine di una coda, l'attesa (essenzialmente un processo di immagazzinamento) e l'essere servito all'inizio della coda. Può essere applicata nei trasporti e nelle telecomunicazioni; occasionalmente è collegata alla Ride theory.

La prima pubblicazione sulla teoria delle code è del 1909 dell'ingegnere danese Agner Krarup Erlang.

Nel 1953, David G. Kendall introdusse la notazione A/B/C, successivamente estesa come 1/2/3/(4/5/6) nella quale i numeri sono sostituiti con quanto segue.

1. Un codice che descrive il processo di arrivo; i codici usati sono:
   • M per "di Markov", implicante una distribuzione esponenziale negativa unilatera per i tempi di servizio o tra gli arrivi: ciò implica l'assenza di memoria di questi ultimi;
   • D per distribuzione "degenere" o "deterministica" dei tempi di servizio;
   • Ek per una distribuzione di Erlang con k come parametro di forma;
   • G per una distribuzione "Generale".
2. Un codice simile che rappresenta il processo di servizio, usando gli stessi simboli.
3. Il numero di canali di servizio.
4. Le dimensioni massime del sistema: il massimo numero di clienti permessi nel sistema compresi coloro che vengono serviti attualmente; quando questo massimo viene raggiunto ulteriori arrivi vengono rifiutati.
5. Le dimensioni della fonte di arrivi: le dimensioni della popolazione da cui possono arrivare i clienti; questo limita il ritmo di arrivi, tanti più jobs sono presenti nella coda tanti meno ne sono disponibili per entrare nel sistema.
6. L'ordine di priorità nel quale sono serviti i jobs nella coda:
   • First Come First Served (FCFS) (o First In First Out - FIFO) (il primo che arriva viene servito per primo);
   • Last Come First Served (LCFS) (o Last In First Out - LIFO) (l'ultimo che arriva viene servito per primo);
   • Service In Random Order (SIRO) (servizio in ordine casuale).

Curiosità

Nella puntata di "Chi vuol essere milionario?" andata in onda lunedì 17 marzo 2008 fu chiesto, in una domanda da 15 mila euro,a che cosa riguardasse la teorie delle code. C'è da considerare che la Teoria delle Code è uno dei campi più importanti in Informatica e modellizza le strutture per la gestione di processi concorrenti e la soluzione delle relative problematiche.

Collegamenti esterni

• http://www2.uwindsor.ca/~hlynka/queue.html
• Java Modelling Tools - Una suite GPL per la risoluzione di modelli a reti di code e per studi di performance