|
[[File:Teoria_de_colas.svg|thumb|Schema di un sistema a coda, con clienti, serventi, code di attesa e flussi di traffico in ingresso e uscita]]
La '''teoria delle code''' è lo studio [[matematica|matematico]] delle linee di attesa (o [[Coda (informatica)|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 [[Sistema sanitario|sanità]]) e delle [[operations|operazioni]] aziendali[[azienda]]li. Usualmente considerata una branca della [[ricerca operativa]], le sue origini risalgono 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.
==Descrizione==
Usualmente, la teoria delle code è considerata una branca della [[ricerca operativa]]. Le sue origini vengono fatte risalire 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 === ▼
[[File:Exponential_pdf.svg|thumb|[[Distribuzione esponenziale|Distribuzione esponenziale negativa]]]]
[[File:Degenerate_distribution_PMF.png|thumb|[[Distribuzione degenere]]]]
[[File:Gamma_distribution_pdf.svg|thumb|[[variabile casuale Erlanghiana|Distribuzione di Erlang]]]]
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 più usati sono: ▼▲== Notazione di Kendall ==
#* '''"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; ▼▲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:
#* '''"D '''" per [[variabile casuale degenere|distribuzione "degenere"]] o "deterministica" dei tempi di servizio; ▼#* '''"E<math> _{k}_k</math> '''" per una [[ variabile casuale Erlanghiana|distribuzione di Erlang]] con <math>k </math> come parametro di forma; ▼#* '''"G '''" per una distribuzione " Generalegenerale". ▼# Un codice simile che rappresenta la distribuzione di probabilità dei tempi di servizio dei ''jobs'', usando gli stessi simboli precedenti. ▼# 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<math>S</ math>/<math>K </math>, con s<math>S</math> e k<math>K</math> 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]]. ▼▲# 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 questo massimo viene raggiunto ulteriori arrivi vengono rifiutati. Se non indicata 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 si intende infinita.
▲# L'ordine di priorità nel quale sono serviti i ''jobs'' nella coda (se non indicato è 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'ospedale con i codici bianco, verde e rosso).
== = Sistemi a coda e Teoriateoria del traffico === ▼▲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]].
{{vedi anche|Traffico (telecomunicazioni)}}
[[File:FIFO-LIFO.svg|thumb|Confronto tra tecnica FIFO e LIFO.]]
[[File:Mminfinity-statespace.svg|thumb|upright=1.0|[[Catene di Markov]] per sistemi a coda con stati, transizione di stati e relative probabilità, usata per la modellazione dei sistemi a coda]]
I sistemi a coda sono modellizzabili tramite [[processo markoviano|catene di Markov]] a tempo continuo ossia con [[sistema dinamico|sistemi dinamici]] caratterizzati da <math>N</math> stati, probabilità di stato <math>P(N_i)</math> e [[probabilità di transizione]] da uno stato a un altro uguale al prodotto tra la frequenza di transizione <math>f</math> e l'intervallo di tempo <math>dt,</math> dipendente solo dallo stato presente del sistema e non da quelli precedenti (sistema senza memoria). Lo stato rappresenta la situazione in cui si trova il sistema rispetto a variabili prese come riferimento (in linea di massima non univoche) e l'evoluzione del sistema è mappata con una sequenza di salti fra gli stati stessi. Note le frequenze di transizione, ossia la probabilità di transizione di stato, è possibile derivare le probabilità di stato <math>P(S_i)</math> risolvendo la catena di Markov; dalla conoscenza di queste probabilità si possono poi derivare i parametri prestazionali di interesse quali il traffico smaltito, la probabilità di rifiuto, il tempo di coda, ecc…
Definendo il flusso proveniente dallo stato <math>i </math>-esimo verso lo stato <math>k </math>-esimo come il prodotto <math>P( SkS_k) *qk\cdot q_k, i</math> tra la probabilità di stato in <math>k </math> e la frequenza di transizione verso lo stato <math>k, </math> per il calcolo della probabilità di stato si utilizza la condizione espressa dalla [[legge di conservazione ]] dei flussi la quale afferma che la somma dei flussi entranti è uguale alla somma dei flussi uscenti da uno stato . Applicando tale principio ad ogni stato si ottiene un sistema di <math>S</math> equazioni in <math>S</math> incognite (le probabilità di stato) tante quante gli stati <math>S;</math> 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. ▼▲==Sistemi a coda e Teoria del traffico==
I Sistemi a Coda sono modellizzabili tramite [[processo markoviano|catene di Markov]] tempo continue ovvero con [[sistema dinamico|sistemi dinamici]] caratterizzati da N Stati, Probabilità di Stato pari a P(Ni) e Probabilità di Transizione da uno stato ad un altro pari al prodotto tra la Frequenza di Transizione f e l’intervallo di tempo dt, dipendente solo dallo stato presente del sistema e non da quelli precedenti (sistema senza memoria).
Lo stato rappresenta la situazione in cui si trova il sistema rispetto a variabili prese come riferimento (in linea di massima non univoche) e l’evoluzione del sistema è mappata con una sequenza di salti fra gli stati stessi.
Note le frequenze di transizione, ovvero la probabilità di transizione di stato, è possibile derivare le probabilità di stato P(Si) risolvendo la catena di Markov; dalla conoscenza di queste probabilità si possono poi derivare i parametri prestazionali di interesse quali il traffico smaltito, la probabilità di rifiuto, il tempo di coda, ecc…
▲Definendo il flusso proveniente dallo stato i-esimo verso lo stato k-esimo come il prodotto P(Sk)*qk, i tra la probabilità di stato in k e la frequenza di transizione verso lo stato k, per il calcolo della probabilità di stato si utilizza la condizione espressa dalla legge di conservazione dei flussi la quale afferma che la somma dei flussi entranti è uguale alla somma dei flussi uscenti da uno stato.
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 Catenecatene di Markov sono le Catenecatene di Markov di Nascitanascita e Mortemorte 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 è modellabile tramite una catena di Markov di nascita e morte con processo di arrivo e di servizio di tipo [[esponenziale]] negativo di parametri λ (nascita) e υ (morte) e valori attesi corrispondentemente pari a 1/λ e 1/υ.
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 λ e υ e valori attesi rispettivamente pari a 1/λ e 1/υ.
In un sistema acon <math>S</math> Serventiserventi diventa invece fondamentale un parametro prestazionale notodetto come Probabilitàprobabilità di Blocco ilblocco, qualeche dipende dal numero <math>S</math> di Serventiserventi e dal Trafficotraffico Offertoofferto Ao<math>A</math> in ingresso. Tale parametro si calcola facendo riferimento alla [[formula di Erlang B]] i cui valori, per <math>S</math> e Ao<math>A</math> 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 ossia 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.
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.
== Voci correlate ==
* [[Traffico (telecomunicazioni)]]
* [[Coda M/M/1]]
* [[Coda (informatica)|Coda]]
== Altri progetti ==
{{interprogetto|preposizione=sulla}}
== Collegamenti esterni ==
* {{Collegamenti esterni}}
* http://web2.uwindsor.ca/math/hlynka/queue.html
* [{{cita web|http://jmt.sourceforge.net |Java Modelling Tools - Una suite GPL per la risoluzione di modelli a reti di code e per studi di performance]}}
{{Controllo di autorità}}
{{portale|ingegneria|matematica|telematica}}
[[Categoria:Teorie delle telecomunicazioni]]
[[Categoria:Teorie di rete]]
[[Categoria:ComplessitàTeoria della complessità computazionale]]
[[Categoria:Computazioni]]
[[Categoria:Ricerca operativa]]
[[Categoria:Processi stocastici]]
| 