Teoria delle code: differenze tra le versioni

Versione delle 09:58, 20 ago 2014

Versione attuale delle 15:08, 14 dic 2023

(34 versioni intermedie di 21 utenti non mostrate)

Riga 1:

[[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 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, soprattutto nel campo dei [[trasporti]], delle [[telecomunicazioni]], della fornitura di servizi (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 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.

=== 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 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 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;

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

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

#* '''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'''Un codice perche [[variabilerappresenta casualela degenere|distribuzione "degenere"]]di o "deterministica"probabilità dei tempi di servizio; dei ''jobs'', usando gli stessi simboli precedenti.

#* '''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 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 alla posta).

# Le dimensioni massime del sistema, che corrisponde alla somma tra i ''jobs'' in coda e i ''jobs'' nei canali di servizio; quando il 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 con il quale sono serviti i ''jobs'' nella coda (per default è 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 esempio è il 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 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 Teoriateoria del traffico ===

{{vedi anche|Traffico (telecomunicazioni)}}

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).

[[File:FIFO-LIFO.svg|thumb|Confronto tra tecnica FIFO e LIFO.]]

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.

[[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]]

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…

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 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.

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.

Un tipo di Catene di Markov sono le Catene 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 λ (nascita) e υ (morte) e valori attesi corrispondentemente pari a 1/λ e 1/υ.

Un tipo di catene di Markov sono le catene 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 è modellizzabilemodellabile tramite una Catenacatena di Markov di Nascitanascita e Mortemorte 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/υ.

In un sistema a S Serventi diventa fondamentale un parametro prestazionale detto Probabilità di Blocco, che 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 A 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 un sistema con <math>S</math> serventi diventa fondamentale un parametro prestazionale detto probabilità di blocco, che dipende dal numero <math>S</math> di serventi e dal traffico offerto <math>A</math> in ingresso. Tale parametro si calcola facendo riferimento alla [[formula di Erlang B]] i cui valori, per <math>S</math> e <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 ovveroossia 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 ==

* {{ThesaurusCollegamenti BNCFesterni}}

* 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]]