Teoria delle code

studio matematico delle linee di attesa e di processi correlati

La teoria delle code è lo studio matematico delle linee di attesa (o code) e di vari processi correlati, quali il processo di arrivo in coda, l'attesa (essenzialmente un processo di immagazzinamento) e il processo di servizio. Può essere applicata ad un'ampia varietà di problemi reali, soprattutto nel campo dei trasporti, delle telecomunicazioni, della fornitura di servizi pubblici (ad es. in sanità) e delle operations aziendali.

Usualmente, la teoria delle code è considerata una branca della ricerca operativa. Le sue origini vengono fatte risalire al 1909 quando l'ingegnere danese Agner Krarup Erlang pubblicò un articolo intitolato The theory of probability and telephone conversations relativo alle attese nelle chiamate telefoniche.

Nel 1953, David George 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).

Collegamenti esterni