Appunti di Sistemi di servizio e simulazione, parte sistemi di servizio, prof. Massimo Roma, La Sapienza, ingegneria gestionale

Introduzione

Un sistema è definibile come una collezione di entità che agiscono ed interagiscono per il raggiungimento di uno scopo. Tale sistema in questione può essere analizzato e studiato mediante un modello, che ne rappresenti le caratteristiche. I modelli matematici (analitici) rappresentano la realtà attraverso variabili e relazioni logico-matematiche. Questi non sono gli unici modelli utilizzabili; in situazioni complesse, infatti, tali modelli non forniscono una rappresentazione adeguata, per questo si adottano modelli di simulazione, che è in grado di replicare il funzionamento del sistema reale in esame. In un modello di simulazione vi è una corrispondenza funzionale tra gli elementi della realtà e l’oggetto che ne svolge la funzione.

Inoltre, la simulazione:

• Permette di analizzare e studiare modelli stocastici, cioè modelli in cui le grandezze sono influenzate da fenomeni di natura aleatoria.
• Permette di effettuare la validazione di un modello matematico in alternativa alla sperimentazione diretta.

In un modello di ottimizzazione cerchiamo la soluzione di un modello matematico, che coinciderà con il min/max di una funzione obiettivo. In tale caso si dice che stiamo utilizzando un approccio di tipo what-best, cioè tra tutte le soluzioni possibili stiamo cercando quella ottima; il modello di simulazione, invece, ha un approccio diverso, di tipo what-if, ed è in grado quindi di mostrare cosa succede quando variano alcune decisioni. La simulazione per ciò, non trova una soluzione.

Capitolo 1: Teoria delle code

Una struttura con arrivo casuale di clienti (clients) che richiedono lo svolgimento di un servizio, erogato da dei server, in un tempo casuale (tempo di servizio), viene chiamata sistema di servizio; tale sistema risulta caratterizzato da parti che interagiscono tra di loro per il raggiungimento di uno scopo. A causa dei tempi casuali, si genererà automaticamente una coda. La teoria delle code studia i fenomeni di attesa che si possono verificare, appunto, quando si richiede un servizio. Un esempio classico e semplice è quello del supermercato, con la fila alla cassa, oppure anche l’attesa alle poste per ricevere un servizio.

Si sa inoltre che il tempo necessario per espletare un servizio da parte del servente non è nullo. Quando tutti i serventi sono occupati a servire dei clienti, i successivi clienti che entrano sono costretti ad aspettare un certo tempo in coda. Il servente può essere singolo oppure ce ne può essere anche più di uno: la scelta del numero di serventi è volta a minimizzare i costi e a massimizzare il profitto, evitando di far generare lunghe code di attesa. Quello di cui si occupa la teoria delle code è valutare alcune grandezze sulle quali basarsi per dimensionare il sistema di servizio. Per ricavare tali grandezze in modo da analizzare le prestazioni del sistema è indispensabile l’uso della simulazione.

Componenti di un sistema di servizio

Un sistema di servizio è composto da un insieme di serventi (non vuoto) e da un insieme di aree di attesa. Esso accoglie i clienti in attesa di poter ricevere un servizio. L’utente non è necessariamente una persona. Vediamo le altre componenti caratteristiche di un sistema di servizio:

• Popolazione: i suoi componenti risultano indistinguibili tra di loro e la sua caratteristica principale è la dimensione. Considerata una popolazione di utenti, la loro dimensione è il numero totale dei distinti potenziali clienti che richiedono un servizio. Essa può essere finita o infinita; per semplicità tratteremo il caso di popolazione infinita.
• Numero di serventi (s): ci può essere uno o più serventi; qualora ve ne siano più di uno è necessario distinguere se questi lavorano in parallelo oppure in serie.
• Schema di arrivo: descrive il modo secondo il quale i clienti si presentano a richiedere il servizio. Esso è definito come intervallo di tempo tra due arrivi successivi di clienti nel sistema (tempo di interarrivo). Lo indicheremo come t_i, pari quindi al tempo che intercorre tra l’arrivo del i-esimo cliente e il (i-1)-esimo cliente. Di tali intertempi si supponga nota la distribuzione di probabilità. Due aspetti, meno comuni, che si possono presentare sono l’arrivo di un gruppo di utenti e la rinuncia di un cliente (balking).
• Schema di servizio: descrive il modo in cui ciascun servente eroga il servizio. Viene specificato un tempo di servizio, che indica il tempo necessario a servire un cliente. Esso potrà essere deterministico, ma di solito si assumerà come una variabile aleatoria, indicata con t_s. Di tali tempi si assumerà nota la distribuzione di probabilità. Nel caso di più serventi un’assunzione che faremo è che essi operano con il medesimo schema di servizio (stessa distribuzione per il sistema di servizio).
• Capacità del sistema: è il valore massimo che può assumere la variabile associata al numero di utenti presenti nel sistema. Indica il numero massimo di utenti che possono essere contemporaneamente nel sistema (tenendo conto sia degli utenti in coda sia di quelli che stanno ricevendo un servizio da un server). Nella realtà lo spazio fisico dove sostano gli utenti è limitato; quando si raggiunge la massima capacità chiunque arriva dopo si trova a dover rinunciare al servizio. Tale fenomeno prende il nome di balking. Quando si parla di capacità si intende la capacità complessiva del sistema, ovvero la somma degli utenti in coda e quelli che sono serviti.
• Disciplina della coda: indica il modo e l’ordine con cui gli utenti vengono serviti. Le discipline più utilizzate sono:
  • FIFO (First In First Out): i clienti vengono serviti nell’ordine in cui arrivano. È la disciplina di coda più utilizzata.
  • LIFO (Last In First Out): si serve come primo cliente l’ultimo arrivato nel sistema. Essa è conosciuta anche come LCFS.
  • SIRO (Service In Random Order): si servono gli utenti in modo casuale.
  • PRI: consente di classificare gli utenti in base a classi di priorità, servendo per primi quelli appartenenti alla classe più alta. Un esempio di tale caso è il pronto soccorso.

Indichiamo con t_iq la variabile aleatoria che rappresenta il tempo passato dall’i-esimo utente nella coda prima di iniziare ad usufruire del servizio. All’interno di un sistema di coda avviene la seguente situazione: clienti che richiedono un servizio vengono generati nel tempo dalla popolazione, entrano nel sistema e raggiungono la coda; in un certo momento da tale coda viene selezionato un cliente secondo la disciplina della coda. Il servizio richiesto viene effettuato da un servente e successivamente a ciò il cliente lascia il sistema. Possiamo quindi indicare con t_iw il tempo passato complessivamente dall’i-esimo cliente nel sistema. Tale tempo sarà il seguente: t_iw = t_iq + t_is.

Nel trattare la teoria delle code assumeremo sempre verificate due situazioni:

1. I tempi di interarrivo sono indipendenti ed identicamente distribuiti.
2. I tempi di servizio sono indipendenti ed identicamente distribuiti.

Un’altra assunzione che facciamo per tutta la trattazione è che il cliente che arriva all’interno del sistema sceglie su quale fila piazzarsi senza mai cambiarla in seguito. Si utilizza una notazione, detta notazione di Kendall, per indicare sinteticamente le caratteristiche principali di un sistema di servizio. Tale notazione prevede delle sigle o simboli, separati da /. Ad esempio A/B/s/c/p/Z, dove:

• A indica lo schema di arrivo (distribuzione di probabilità dei tempi di interarrivo).
• B lo schema di servizio (distribuzione di probabilità dei tempi di servizio).
• s il numero dei serventi.
• c la capacità del sistema.
• p la dimensione della popolazione.
• Z la disciplina della coda.

Le ultime tre componenti possono anche non essere specificate, e in tale caso si assumerà che esse abbiano i seguenti valori di default: in mancanza della componente c si assume che la capacità del sistema sia infinita; se non è specificata la componente p si assume che la popolazione sia infinita e se non è presente la componente Z si assume che la disciplina della coda sia FIFO.

Inoltre, le componenti c, s e p sono numeri interi non negativi. Per quanto riguarda gli schemi di arrivo o di servizio, si assumerà molto spesso che essi siano distribuiti in modo esponenziale, oppure che seguano una distribuzione costante e la distribuzione di Erlang di ordine k. Avremo per notazione che:

• M indica la distribuzione esponenziale.
• D indica la distribuzione costante (o tempi deterministici).
• E_k indica la distribuzione di Erlang di ordine k.
• G indica una distribuzione generica.

Una volta assegnate le distribuzioni, risultano definiti anche i parametri che ora vedremo nel dettaglio. Si indica con λ la frequenza media degli arrivi; con μ indichiamo e definiamo la velocità di servizio o tasso di servizio. Se ci sono più serventi assumeremo che questi operano in parallelo con lo stesso μ. Si definisce poi un’altra grandezza che si indica con ρ: λ/(s*μ). Essa è il rapporto e si chiama fattore di utilizzazione dei serventi. Con tale grandezza si rappresenta la frazione di tempo in cui i serventi sono occupati: tale rapporto è la frazione della capacità di servizio che ha il sistema (vedi denominatore) che è utilizzata in media dai clienti che arrivano (λ).

È un rapporto tra una grandezza al numeratore che rappresenta gli arrivi: quindi al crescere di λ mi aspetto che il sistema sia più congestionato, con un denominatore che rappresenta il numero di serventi per la velocità di servizio (μ). Naturalmente λ, che abbiamo detto essere la frequenza, sarà dato da 1/il valore atteso dei tempi di arrivo. Stessa cosa vale per μ. Per specificare in maniera completa un sistema a coda è necessario fornire la notazione di Kendall che lo rappresenta ed i parametri λ e μ. Occorre quindi fornire le caratteristiche fisiche e le logiche di funzionamento del sistema di servizio in esame, insieme alla definizione dei due processi fondamentali che lo caratterizzano: il processo degli arrivi e il processo dei servizi.

Le ultime due quantità da definire sono n(t), con cui indicheremo il numero degli utenti nel sistema all’istante t, invece con n_q(t) indichiamo il numero di utenti in coda all’istante t. Avremo a che fare non solo con variabili aleatorie, ma anche con processi stocastici: in tali processi è presente una dipendenza da un parametro.

Abbiamo definito tutti i parametri che permettono di definire un sistema a coda; se vogliamo però vedere un sistema a coda dal punto di vista del funzionamento ci occorre anche calcolare i processi degli arrivi e quelli dei servizi. N(t) è una variabile aleatoria che mi indica il numero degli utenti all’interno del sistema al tempo t. Tale variabile aleatoria prende anche il nome di stato del sistema (a coda) al tempo t. Definiamo inoltre il numero di utenti in coda all’istante t come n_q(t) e lo chiamiamo lunghezza della coda. Tale parametro dipenderà sia da s sia da n(t): varrà zero se il numero di utenti all’interno del sistema all’istante t è minore del numero dei serventi; sarà invece pari a n(t)-s se il numero dei clienti all’interno del sistema è maggiore del numero dei serventi.

Lo stato del sistema e la lunghezza della coda risultano essere processi stocastici a tempo continuo. Le famiglie di variabili aleatorie dei tempi di permanenza nel sistema e nella coda sono processi stocastici a tempo discreto. Analizziamo e denotiamo quelle che sono le misure di prestazione di un sistema di servizio. Tali misure sono interessanti da valutare quando il sistema ha raggiunto una situazione di regime, ovvero quando il sistema è stato in funzione per un tempo sufficientemente grande, in quanto in tale caso il sistema non risentirà fortemente dello stato iniziale. Un sistema che ha cominciato a funzionare da poco si dice che è in condizioni transitorie. Un sistema che diviene indipendente dallo stato iniziale si dice che ha raggiunto condizioni stazionarie o di equilibrio (steady-state). Un sistema con ρ ≥ 1 non raggiungerà mai tale condizione, in quanto sarà destinato a crescere nel tempo indefinitivamente.

Le grandezze di interesse per effettuare l’analisi di un sistema in condizioni di stazionarietà sono:

• N: numero medio degli utenti nel sistema.
• N_q: numero medio degli utenti in coda.
• T: tempo medio di permanenza nel sistema.
• T_q: tempo medio di permanenza in coda.

Con interessa inoltre, dare una definizione di ciascuna delle quantità. Vediamo una interpretazione grafica di quanto definito fino ad ora. Consideriamo un intervallo prefissato [0,t] e consideriamo a(t) e b(t) rispettivamente il numero totale degli utenti arrivati nel sistema e il numero totale degli utenti serviti e quindi usciti dal sistema al tempo t. Vediamo un grafico che tiene conto di un sistema con un singolo servente e con disciplina di coda FIFO. La maggior parte dei sistemi a coda di interesse sono ergodici. La proprietà in questione è quella per cui le medie statistiche convergono quasi ovunque alle medie temporali.

Da notare bene che tutte le uguaglianze valgono con probabilità pari ad uno. Esistono importanti relazioni che legano le quantità N, T, N_q, T_q, in un sistema in condizioni stazionarie. La prima importante relazione che trattiamo è il legame importantissimo che vi è tra N e T: tale legge si chiama legge di Little. La legge di Little appena vista è indipendente dalla distribuzione delle probabilità dei tempi di interarrivo e dei tempi di servizio; è inoltre indipendente dalla disciplina del servizio ed è valida per sistemi in condizioni stazionarie.

Ripetendo il discorso fatto per la dimostrazione del teorema di Little, questa volta considerando gli utenti che arrivano in coda e quelli che escono dalla coda, si ottiene la seguente espressione: N_q = λ*T_q. Occorre tenere conto che l’esistenza di fenomeni di rinuncia consta il fatto che la frequenza degli arrivi non coincide con quella degli utenti che effettivamente entrano nel sistema: per questo dovremmo distinguere tra chi entra e chi non entra all’interno del sistema. Per il teorema di Little occorrerà tenere conto del λ effettivo, ovvero occorre considerare solo gli utenti che effettivamente entrano nel sistema. Le relazioni ottenute fino ad adesso sono molto importanti; tramite esse sarà possibile determinare tutte le quantità una volta nota una di esse. Poiché p₀ è la probabilità che nel sistema non vi siano utenti e che quindi il servente sia inoperoso, il complemento ad 1 di p₀ rappresenta l’operosità del servente.

Capitolo 2

Vediamo ora la distribuzione esponenziale. Abbiamo appena visto come all’interno di un sistema siano fondamentali due processi stocastici che lo caratterizzano: il processo degli arrivi, caratterizzato dalla distribuzione di probabilità dei tempi di interarrivo e quello di servizio, caratterizzato invece dalla distribuzione di probabilità dei tempi di servizio. La distribuzione di probabilità che maggiormente viene presa in considerazione nella teoria delle code è la distribuzione esponenziale. Vedremo perché tale distribuzione è la più utilizzata, analizzando le sue fondamentali proprietà.

Questa proprietà di assenza di memoria può essere interpretata nella seguente maniera: se il tempo di durata di un’apparecchiatura è distribuito esponenzialmente allora un’apparecchiatura che è già in uso da un certo numero di ore è buona tanto quanto una nuova in termini di tempo totale di durata prima della sua rottura. La distribuzione esponenziale è l’unica distribuzione continua che gode di tale proprietà.

Occorre notare che se X rappresenta il tempo mancante fino ad un certo evento, Y rappresenta il tempo fino a che il primo evento accada. L’interpretazione di tale proprietà è molto importante: supponiamo di avere s serventi che lavorano in parallelo, ognuno dei quali ha tempi di servizio distribuiti esponenzialmente con lo stesso parametro μ. In questo caso sia r ≤ s il numero dei serventi che effettivamente stanno fornendo il servizio e X_i il tempo che rimane per il completamento del servizio da parte di ciascun servente. Si ha che X_i è distribuita esponenzialmente con parametro α = μ (velocità di servizio), e che Y rappresenta il tempo fino al prossimo completamento di un servizio. Il tasso di servizio quindi sarà dato da μ*il numero dei serventi effettivamente operanti in un determinato istante di tempo.

Questo tipo di scrittura ha una utilità quando l’o piccolo è assimilabile a zero e questo avviene quando Δt è molto piccolo. Quello che si ottiene sommando un certo numero k di variabili aleatorie iid è una nuova variabile aleatoria S_k che ha distribuzione di Erlang, di parametri α e k. Essa corrisponde ad una rappresentazione in cui un servizio non si esaurisce in una operazione semplice, ma in n volte la ripetizione di un servizio.

Il processo di Poisson

Cominciamo dall’introdurre un concetto importante. Un processo stocastico {X(t), t>0} è detto processo di conteggio (o counting process) se X(t) rappresenta il numero totale di eventi che accadono fino all’istante t.