Teoria delle code: differenze tra le versioni

Versione delle 16:41, 25 mag 2013

Versione delle 03:48, 22 giu 2013

Riga 1:

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 risalirerisalgono al [[1909]] quando l'ingegnere [[Danimarca|danese]] [[Agner Krarup Erlang]] pubblicò un articolo intitolato ''The theory of probability and telephone conversations'' relativo alle attese nelle chiamate telefoniche.

== Notazione di Kendall ==

Nel [[1953]], [[David George Kendall]] introdusse la notazione '''A/B/C''', successivamente estesa come '''1/2/3/4/5/6''' al fine di fornire una descrizione compatta e immediata del modello del sistema a code:

# Un codice che descrive la distribuzione di probabilità dei tempi di arrivo dei ''jobs'' nel sistema; i codici usati sono:

#* '''M''' per "di Markov", implicante una [[variabile casuale esponenziale negativa|distribuzione esponenziale negativa]] unilatera per i tempi di servizio o tra gli arrivi: ciò implica l'[[mancanza di memoria|assenza di memoria]] di questi ultimi;

#* '''D''' per [[variabile casuale degenere|distribuzione "degenere"]] o "deterministica" dei tempi di servizio;

#* '''E<math>_{k}</math>''' per una [[variabile casuale Erlanghiana|distribuzione di Erlang]] con k come parametro di forma;

#* '''G''' per una distribuzione "Generale".

# Un codice simile che rappresenta la distribuzione di probabilità dei tempi di servizio dei ''jobs'', usando gli stessi simboli.

# Il numero di canali di servizio, detti anche ''serventi'', o ''server'' (ad esempio gli sportelli aperti alla posta).

# Le dimensioni massime del sistema, che corrisponde alla somma tra i ''jobs'' in coda e i ''jobs'' attualmente nei canali di servizio; quando questoil massimo viene raggiunto ulteriori arrivi vengono rifiutati. Se non indicata la dimensione si intende infinita.

# 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. Se non indicata la dimensione si intende infinita.

# L'ordine dicon priorità nelil quale sono serviti i ''jobs'' nella coda (se nonper indicatodefault è FIFO):

#* 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);

#* PRI (esiste un sistema di selezione degli utenti a priorità (un classico esempio è l'ospedaleil pronto soccorso, con i codici bianco, verde e rosso).

I modelli più studiati sono i sistemi M/M/s/K, con s e k che possono assumere diversi valori (il modello più semplice è l'[[Coda M/M/1|M/M/1]], con un unico servente e a capacità illimitata): questo perché la distribuzione esponenziale degli intertempi di arrivo e di servizio permette di studiare i sistemi a coda come dei [[processo di nascita e morte|processi di nascita e morte]].

==Sistemi a coda e Teoria del traffico==

Riga 30:

Applicando tale principio ad ogni stato si ottiene un sistema di S equazioni in S incognite (le probabilità di stato) tante quante gli stati S; le equazioni non sono tutte indipendenti tra loro, quindi la soluzione del sistema è impossibile (determinante nullo) a meno di sostituire un'equazione con la somma delle probabilità degli stati pari ad uno.

Un particolare tipo di Catene di Markov sono le Catene di Markov di Nascita e Morte dove sono ammesse transizioni solo tra strati 'adiacenti' e per i quali è identificabile una linea di taglio di flusso.

Un sistema a coda è detto Markoviano se è modellizzabile tramite una Catena di Markov di Nascita e Morte con processo di arrivo e di servizio di tipo [[esponenziale]] negativo di parametri rispettivamente λ (nascita) e υ (morte) e valori attesi rispettivamentecorrispondentemente pari a 1/λ e 1/υ.

In un sistema a S Serventi diventa invece fondamentale un parametro prestazionale noto comedetto Probabilità di Blocco, il qualeche dipende dal numero S di Serventi e dal Traffico Offerto Ao in ingresso. Tale parametro si calcola facendo riferimento alla [[formula di Erlang B]] i cui valori, per S e Ao fissati, sono espressi in forma tabulata. Altrettanto di interesse è la probabilità di attesa in coda espressa in funzione del numero di serventi e del traffico offerto attraverso la [[formula di Erlang C]].

In una [[rete di telecomunicazione]] i sistemi a coda e i relativi problemi di gestione del traffico sono presenti all'interno dello stack protocollare dei sistemi di elaborazione, trasmissione e ricezione del flusso informativo ovvero i terminali [[host]] e i sottosistemi interni di commutazione ([[router]]) e più in generale in tutti gli [[apparato di rete|apparati di rete]] che presentano del traffico in ingresso.