Sistemi a coda

Un sistema a coda è una struttura caratterizzata dall'arrivo casuale di utenti (clienti) che richiedono un servizio.

I sistemi a coda sono un sottoinsieme dei sistemi di flusso.

Come funziona un sistema a coda

Uno dei principali soggetti in un sistema a coda è il cliente (o utente).

L'insieme dei clienti è detta popolazione che può essere finita o infinita.

Nota. Un cliente può essere una persona ma anche una qualsiasi altra entità. Ad esempio una persona all'ufficio postale, un pacchetto dati nella rete internet, un aereo sulla pista di un aeroporto, ecc.

In un sistema a coda il cliente

1. entra nel sistema
2. attende il suo turno
3. ottiene il servizio
4. esce dal sistema

Il servizio è erogato da un'unità detta server (servente) in un determinato tempo non nullo.

In un sistema a coda può esserci uno o più serventi.

• Sistema a singolo servente
  Nel sistema è presente un unico server
• Sistema multiservente
  Nel sistema ci sono più server

Nota. Nel caso multiservente, se non indicato diversamente, si suppone che i serventi operino in parallelo e hanno lo stesso schema di servizio. Pertanto, i tempi di servizio sono identici per ogni servizio (indipendenti identicamente distribuiti).

L'erogazione del servizio avviene un cliente alla volta.

Pertanto, è possibile che si crei una lista di attesa dei clienti ossia una coda.

Nota. In un sistema a coda le liste di attesa possono essere anche più di una.

Schema di arrivo e schema di servizio

In un sistema a coda devono essere noti lo schema di arrivo e lo schema di servizio.

• Schema di arrivo
  Lo schema di arrivo è composto dai tempi di interrarivo t^a.

  Nota.Il tempo di interarrivo è il tempo che intercorre tra l'arrivo del cliente (i-1)-esimo e il cliente i-esimo $$ t^a_i $$ Si tratta di una variabile aleatoria con a una distribuzione di probabilità. Se non è specificato diversamente si suppone che la distribuzione di probabilità dei tempi di interarrivo sia identica per ogni cliente (tempi indipendenti identicamente distribuiti).

• Schema di servizio
  Lo schema di servizio è composto dai tempi di servizio t^s.

  Nota. Il tempo di servizio è il tempo necessario per servire il cliente i-esimo è $$ t^s_i $$ Si tratta di una variabile aleatoria con a una distribuzione di probabilità.

Il tempo di interarrivo e di servizio è associato a ogni cliente nel sistema a coda.

Quindi, non c'è un solo tempo di interrarivo e un tempo di servizio.

La capacità del sistema

La capacità del sistema a coda è il numero massimo di utenti che possono trovarsi contemporaneamente nel sistema a coda.

Nella capacità massima vanno considerati sia gli utenti in coda, sia quelli presso un servente che stanno beneficiando del servizio.

Esempio. Un ufficio postale ha 5 sportelli (serventi) e una capacità massima di 20 utenti. Vuol dire che nel sistema ci possono essere contemporaneamente al massimo 17 utenti in coda e 3 utenti allo sportello. La capacità del sistema è 20.

Quando non è specificato, il sistema a coda si intende senza una capacità massima finita.

Le regole della coda

Le regole della coda determinano il criterio di scelta dell'utente successivo quando si libera un servente.

Esistono quattro principali criteri

• FIFO (First Input First Output)
  Il primo che si mette in coda prima, è il primo a uscire.
  

  Nota. Nella teoria delle code questo criterio è anche noto come FCFS (First Come First Served)

• LIFO (Last Input First Output)
  L'ultimo che si mette in coda, è il primo a uscire.
  

  Nota. Nella teoria delle code questo criterio è anche noto come LCFS (Last Come First Served)

• SIRO (Serve In Random Order)
  L'utente successivo viene scelto casualmente tra quelli in coda
• PRI (Priority)
  Viene scelto l'utente con priorità più alta tra quelli in coda.
  

  Esempio. Un esempio tipico è la coda in un pronto soccorso. Agli utenti viene assegnato un codice rosso, giallo, verde. Dove il codice rosso indica una priorità più alta (caso più grave). Il verde è la priorità più bassa. Il giallo è una priorità intermedia.

Oltre a questi esistono anche altri criteri più complessi per disciplinare l'uscita dalla coda.

Le variabili aleatorie del sistema

Le principali variabili aleatorie del sistema a coda sono

• Tempo passato dal cliente i-esimo in coda
  E' il tempo passato in coda dal cliente i-esimo $$ t_i^q $$
• Tempo di servizio
  E' il tempo passato dal cliente i-esimo presso un servente per ottenere il servizio richiesto. $$ t_i^s $$
• Tempo di permanenza nel sistema
  E' il tempo passato dal cliente i-esimo nel sistema. E' il tempo che intercorre tra l'istante in cui entra all'istante in cui esce dal sistema. $$ t_i^w = t_i^q + t_i^s $$

I parametri del sistema

Alcuni parametri fondamentali nella configurazione del sistema.

• Frequenza media degli arrivi
  La frequenza media degli arrivi dei clienti nel sistema è il numero medio di arrivo dei clienti in un'unità di tempo (es. 50 utenti in un'ora). In genere si misura con la lettera greca lambda minuscola. $$ \lambda = \frac{1}{E(t_i^a)} $$
• Tasso di servizio
  Il tasso di servizio è il numero medio che beneficiano del servizio in un'unità di tempo (es. 40 utenti in un'ora). In genere si misura con la lettera greca mu minuscola. $$ \mu = \frac{1}{E(t^s_i)} $$
• Fattore di utilizzazione dei serventi
  Il fattore di utilizzazione dei serventi indica l'impiego dei serventi $$ \rho= \frac{\lambda}{s \mu} $$ Dove s è il numero dei serventi. Se è molto alto, il sistema non gestisce bene gli interarrivo e la coda tende a crescere nel corso del tempo.

E così via.