Appunti del corso Sistemi di servizio e simulazione Massimo Roma

01 mar 2018

Esame

Compito scritto, durata 3 ore. Parte di teoria e parte di esercizi. Due quesiti corporici (dimostrazione o teorema fondamentale), il secondo descrittivo (di minore valore), di solito il primo vale 8 il secondo 3-4. 3 esercizi scritti, punteggio variabile. Il totale fa 32. La lode si ottiene con 31-32, 30.5 è 30, ma negli altri casi si arrotonda per eccesso.

Per superare la prova bisogna fare almeno la metà dei punti di teoria, e ovviamente superare come somma il 18.

Possibilità di preappello.

In cosa consiste il corso

Corso diviso in due parti:

• Molto analitica, teoria delle code. Questa ci prenderà poco più di metà corso. Dimostrazioni... vedremo la parte basilare.
• Studiare la simulazione. Useremo i pacchetti software simulatori. I due simulatori usati dal professore sono Arena e Simio.

Di cosa ci occupiamo

Sistemi di servizio: teoria delle code

Un sistema è caratterizzato da parti che interagiscono tra di loro al fine di raggiungere uno scopo. Nel nostro caso un sistema di servizio è caratterizzato da arrivo di utenti che richiedono un servizio, questo è erogato da dei server. L’arrivo dei clienti è casuale, i tempi con cui i server erogano i servizi sono casuali, quindi è inevitabile la formazione di una coda.

Un sistema di servizio è anche un aeroporto (servente è la pista), ci possono essere ritardi, bisogna gestire al meglio questo sistema. Sistemi di trasmissione di dati, ci sono dei buffer (code), questi sistemi vengono anche denominati sistemi a coda. Sistemi complicati perché c’è di mezzo l’aleatorietà. Si tratta di modelli stocastici.

Parte analitica: analisi 1, serie numeriche. Servono concetti di calcolo delle probabilità per via dei fenomeni aleatori.

Un modello di traffico

Grafo, ogni nodo è una fermata, però è un fenomeno aleatorio, non deterministico.

Alla fine delle dispense c’è un capitolo che non fa parte del programma di esame ma serve per dare una ripassata ai concetti di base che servono per l’esame.

Simulazione - ad eventi discreti

Differisce dai sistemi dove esiste il tempo, per noi il tempo è scandito in maniera discreta, faremo scattare il tempo all’accadimento di un evento.

La necessità di utilizzare problemi quantitativi è ben consolidata. La ricerca operativa è quella disciplina che cerca di fornire un sistema di supporto alle decisioni: fornire al decisore (colui che deve selezionare la strategia) un ventaglio di soluzioni basate su un approccio scientifico non solo su un’intuizione euristica. Tutto ciò si fa attraverso la costruzione di un modello.

Se ho un problema reale lo posso studiare attraverso una sperimentazione diretta oppure attraverso un modello.

La sperimentazione diretta nella maggior parte dei casi non è fattibile, allora si usa il modello.

Un modello è una struttura appositamente costruita per rappresentare una situazione. Posso avere modelli fisici o matematici.

Un modello fisico è un modello reale, concreto, in scala.

Noi ci occupiamo di modelli matematici (ottimizzazione, grafi, problemi). La soluzione logica del problema si può determinare secondo due approcci:

• Soluzione analitica o numerica. Cioè posso determinare una forma chiusa della soluzione del problema.

Risolvere questo potrebbe essere molto complicato perché per dimensioni grandi non è praticabile.

Posso usare degli algoritmi (tipo il simplesso).

Ci sono casi in cui la soluzione esatta numerica non si riesce a calcolare, ci si accontenta di una buona approssimazione avendo stimato un gap, per problemi molto difficili si usano le euristiche. Ci sono problemi che non possono essere trattati neanche in questo modo.

Qui entra in ballo la simulazione. Per poter adottare questo strumento dobbiamo avere a monte un modello adeguato di simulazione. La costruzione di un modello non è una procedura sistematica, ci sono delle linee di guida ma si possono creare diversi modelli.

Quando costruiamo un modello abbiamo sempre l’esigenza di validarlo, ciò significa che la soluzione che otteniamo in qualsiasi forma o modo dobbiamo calarla nella realtà e vedere se ha un significato fisico.

Esempio

Moto rettilineo uniforme s=vt.

Particolarmente semplice, possiamo farne anche una trattazione analitica. È un modello valido? Se devo modellare un qualcosa che ha un andamento simile allora sì, ma se devo modellare ad esempio il traffico di Roma non è un modello valido. Fase di verifica e validazione, devo essere sicuro che il modello riproduca il fenomeno in esame.

Il modello matematico che useremo sarà un modello di simulazione, ci occuperemo di questa fase.

Modello di simulazione

È uno strumento che mi permette di replicare il funzionamento di un sistema di tipo stocastico, che ha dentro delle problematiche legate alla stocasticità. La differenza fondamentale di questi modelli, rispetto alla programmazione lineare, è la funzione che ha il computer nella soluzione. Nella simulazione il computer rappresenta il modello.

Legame funzionale tra variabili e realtà nel caso dei PL, qui invece il legame è di tipo logico funzionale. La corrispondenza non è più variabili quantità, ma variabile funzionamento. Abbiamo l’oggetto, in senso informatico, che rappresenta la situazione in corrispondenza con gli elementi reali. Questo ci permette di riprodurre il funzionamento del sistema che esiste, ma ci permette anche di realizzare un modello per realtà che non esistono, sono in fase di progettazione, permette quindi di capire come funzionerà questo sistema secondo quello che ho stabilito.

Aspetto duplice:

• Riproduce l’evoluzione di una realtà già esistente.
• Funzionamento di una realtà che ancora non esiste.

Differenza tra modello di ottimizzazione e uno di simulazione

Ottimizzazione: sistema WHAT BEST.

Cerchiamo massimo o minimo di una funzione nell’insieme ammissibile.

Simulazione: analisi di scenario, sistema WHAT IF, non trova la soluzione ottima ma dice cosa succede al sistema se vario i parametri.

L’analisi di scenario esamina un numero finito di alternative e sceglie la migliore tra queste, non la migliore in assoluto. Per assurdo per trovare la soluzione ottima dovremmo esaminare un numero infinito di soluzioni.

02 mar 2018

Richiami di calcolo delle probabilità

Densità di probabilità discreta.

Leggi congiunte di variabili aleatorie.

Distribuzioni condizionate.

Somma di variabili aleatorie indipendenti.

Momento di ordine r. Sono misure di dispersione, serviranno nella simulazione.

Distribuzioni discrete

Geometrica (successo al primo tentativo).

Binomiale. Numero di successi in prove ripetute.

Poisson. Arrivi casuali al sistema.

Distribuzioni continue

Uniforme in [a,b].

Esponenziale.

Normale.

Di Erlang. Per k=1 abbiamo la curva in blu. Per k che tende all’infinito abbiamo le altre curve. Quindi al variare di k abbiamo una famiglia di distribuzioni. Ad Erlang sono attribuite diverse formule.

In generale possiamo fare successioni di numeri e di variabili aleatorie, la difficoltà sta nel definire le convergenze.

Prendiamo una successione di variabili aleatorie, esistono tanti modi di definire la convergenza.

Convergenza con probabilità 1.

Legge forte dei grandi numeri.

Supponiamo di avere una successione di variabili aleatorie indipendenti identicamente distribuite (IID).

Teorema del limite centrale.

Questo è un altro modo di convergere, convergenza in distribuzione.

Queste cose non si trovano sulle dispense.

08 mar 2018

Introduzione alla teoria delle code

Un sistema a coda è un sistema in cui si prevedono arrivi casuali di utenti che richiedono un servizio erogato da uno o più serventi. Arrivo casuale, tempo di servizio casuale, l’erogazione del servizio è un tempo casuale, si creano file di attesa.

L’utente non è necessariamente una persona, può essere anche un semilavorato che viaggia nell’impianto, un aereo che aspetta che si liberi la pista, i pacchetti di dati sulla rete internet.

Progettare e gestire un sistema a coda

Guadagno dall’erogazione del servizio, quindi più servizi erogo più guadagno. L’utente che arriva vorrebbe non fare la fila, ci sono dei tempi di attesa che hanno dei costi, ci sono delle statistiche americane che hanno stimato quanto un americano medio perde in un anno delle sue ore lavorative, numeri molto alti.

Per soddisfare l’utente che arriva dovrei aumentare il numero dei serventi, altrimenti potrebbe accadere che l’utente arriva, vede una fila troppo lunga e non entra, il non entrare è una perdita di guadagno. Vorrei quindi evitare che la gente rinunci al servizio, potrei aumentare la rapidità del servizio, scelte dimensionali del sistema di servizio, questo però aumenta i costi, potrei a quel punto avere tanti serventi che non lavorano nei momenti in cui non c’è fila.

Lo studio che faremo ci permetterà di rispondere ai quesiti tipici:

• Se configuro il sistema di servizio in un certo modo qual è il tempo medio che l’utente che arriva dovrà aspettare?
• Qual è la probabilità che l’utente in arrivo non debba fare la fila?
• Qual è il numero migliore di serventi che devo mettere affinché l’attesa media sia minore di 5 minuti?

Si fanno delle misure di prestazione del sistema, cioè delle grandezze che ci danno informazioni molto importanti per quanto riguarda il funzionamento del sistema stesso.

Campi di applicazione

Alcuni esempi:

• Traffico auto su una rete stradale, di deterministico c’è poco, è un problema di flusso (sistemi di trasporto).
• Trasmissione email (sistemi di comunicazione).
• Tubature.
• Passaggio clienti auto al casello autostradale.

Tutte situazioni in cui ci sono delle stocasticità.

Calcolo parallelo, sincronismo ecc.

• Servizi commerciali (supermercato, uffici pubblici...) servizi sociali (ospedalieri ecc).
• Sistemi di produzione, sistemi di manutenzione.

Componenti fondamentali di un sistema di servizi

• Si chiama popolazione l’insieme di tutti i potenziali clienti (utenti) che noi assumeremo sempre essere indistinguibili tra di loro (l’utente è un’identità). Potenzialmente possiamo considerarla infinita. È importante vedere se la popolazione è finita o infinita, la trattazione è più difficile nel momento in cui la popolazione è finita, questo perché se la popolazione è finita il numero di utenti che stanno nel sistema influenza il numero degli utenti fuori dal sistema. Se si può ipotizzare la popolazione infinita la trattazione è più semplice.
• Serventi, in particolare il numero, di solito lo indichiamo con “s”. Potrebbero lavorare sia in serie che in parallelo, l’ipotesi che faremo nella maggior parte dei casi sarà che operano in parallelo.
• Schema di arrivo: devo specificare in che modo gli utenti arrivano al sistema, fornendo quindi i tempi di interarrivo. t_i è il tempo di interarrivo tra l’(i-1)-esimo e l’i-esimo cliente. Variabili aleatorie di cui è nota la distribuzione di probabilità. Se fosse deterministica dovrei dare un numero preciso dei tempi di interarrivo.
• Schema di servizio: riguarda la specificazione del tempo che il servente o i serventi impiegano ad erogare il servizio. Variabili aleatorie anche in questo caso. Anche di queste dobbiamo supporre nota la distribuzione di probabilità.

Assunzione: nel caso in cui ci sono più serventi, in parallelo, si supporrà sempre che operano con lo stesso schema di servizio.

• Capacità del sistema. Nella realtà può accadere che lo spazio fisico (buffer) dove ci sono i clienti in coda sia limitato, sistema a capacità limitata: nel momento in cui il sistema ha raggiunto la capacità massima il cliente che arriva deve rinunciare al servizio. L’eventuale rinuncia in inglese solitamente viene chiamata fenomeno di BALKING.

Quando parlo di capacità parlo della capacità del sistema non solo della coda, quindi devo considerare come massimo numero di clienti in coda la capacità del sistema meno il numero dei serventi.

Capacità del sistema = clienti in coda + clienti serviti.

• Disciplina della coda. La più comune è FIRST IN FIRST OUT, chiamata anche FCFS (first come first served). LIFO last in first out, anche qui potrebbe essere LCFS. SIRO service in random order, ho l’operatore che ha uno scatolone di oggetti che deve mettere nella macchina, c’è una coda di oggetti nello scatolone, l’utente li prende in ordine casuale. Ci sono situazioni in cui la scelta è basata sul criterio di priorità (esempio al pronto soccorso) PRI (priority).

Invece di avere una sola coda potrei avere diverse file, quando l’utente arriva può scegliere dove andare a fare la fila.

Per ogni utente che entra nel sistema potrò quantificare il suo tempo di attesa in coda.

Variabili

• Per ogni utente che entra nel sistema potrò quantificare il suo tempo di attesa in coda.
• Tempo di permanenza nel sistema dell’i-esimo utente.

Notazione di Kendall

Assumeremo che: notazione di Kendall.

È una stringa di lettere e numeri separate dallo / A/B/s/c/p/Z.

• A identifica lo schema di arrivo: distribuzione.
• B identifica lo schema di servizio: distribuzione.

A e B possono avere le seguenti distribuzioni:

• M markoviana (esponenziale).
• D discreta.
• E_k Erlang di parametro k.
• G distribuzione generale.
• s è il numero dei serventi: numero.
• c è la capacità: numero, supporremo che sia infinita.
• p è la popolazione: di solito infinita.
• Z è la disciplina della coda: FIFO LIFO SIRO PRI FCFS LCFS.

Posso scrivere anche solo questo, sottintendo le cose scritte sopra.

Grandezze

Quanto sto utilizzando quel servente.

Se fosse più grande di 1 vorrebbe dire che il sistema non riesce a supportare il numero di clienti.

Se ho capacità finita il sistema si autoregola, quindi non importa il valore del ρ, così anche nel caso di popolazione finita. In tutti gli altri casi dovremo imporre che il ρ sia minore di 1. Il ρ prossimo a 1 indica che il servente sta lavorando molto.

n(t) è una variabile aleatoria. Se faccio variare t varierà n(t), quindi in realtà non ho solo una variabile aleatoria ma ho una famiglia di variabili aleatorie che dipendono dal tempo t.

Le famiglie di VA si chiamano processi stocastici.

Esempio n.1

Copisteria con 4 serventi.

Il tempo che occorre a scrivere una pagina è distribuito esponenzialmente con una media di 5 minuti.

Arrivi clienti esponenziali di media 1 ogni 30 min.

Singola coda.

Lavori eseguiti nell’ordine in cui arrivano.

Se non ci metto nient’altro va bene.

La copisteria non accetta più lavori quando ne ha già 20 nel sistema.

Chi paga un prezzo più alto ha priorità.

Esempio n.2

Catena di montaggio dalla quale esce un pezzo ogni 10 minuti, ognuno di questi poi deve essere collaudato, tempo medio collaudo distribuito esponenzialmente con media 18 minuti, è effettuato indipendentemente da due collaudatori.

L’ingresso nel sistema è l’uscita dal montaggio che prendono a caso un pezzo di quelli nel buffer di attesa e lo lavorano.

9 mar 2018

Un sistema di coda è definito da tutti gli elementi prima detti, dal punto di vista del funzionamento bisogna invece calcolare il processo degli arrivi e quello delle uscite. N(t) è una variabile aleatoria che indica il numero degli utenti all’interno del sistema al tempo t. Si chiama anche stato del sistema al tempo t.

Possiamo definire il numero di utenti in coda presenti (nq(t)). Se consideriamo al variare di t (tempo) quella diventa una famiglia di variabili aleatorie. Questa famiglia si chiama processo stocastico a tempo continuo (continuo perché l’indice di questo processo è un parametro continuo).

Ora dobbiamo stimare delle misure di prestazione del sistema. Si tratta di quelle grandezze di cui dobbiamo tenere conto se vogliamo andare a valutare come funziona il sistema e come possiamo andarlo a modificare. Dire che un sistema ha raggiunto la stazionarietà vuol dire che esistono dei limiti finiti. Esiste per questi sistemi un istante temporale per cui dopo di quello i sistemi si trovano ad essere invarianti.

Misure di prestazione

Andremo ad esaminare tali misure in condizioni stazionarie. Quali sono le grandezze di interesse? Sono essenzialmente 4:

• N che indica il numero medio di utenti nel sistema.
• N^q che indica il numero medio di utenti in coda.
• T che indica il tempo medio di permanenza nel sistema.
• T^q che indica il tempo di permanenza nella coda.

La cosa importante è dare un’esatta definizione di tali quantità. Occorre dire cosa si intende matematicamente con tali simboli. Quello che stiamo per fare è dare una definizione di queste 4 quantità mediante la p_k(t) che è la probabilità che nel sistema vi siano k utenti.

Il raggiungimento dello stato di stazionarietà vuol dire che esiste il limite finito di p, con t che tende all’infinito. Non tutti i sistemi arrivano a tale stato, noi assumeremo sempre che questa ipotesi sia verificata nei nostri studi.

Come definiamo N e T?

Immagino di disporre di due funzioni a(t), che indica il numero totale di utenti arrivati al sistema al tempo t, e b(t) che indica il numero totale di utenti serviti e quindi usciti dal sistema al tempo t. Facciamo un diagramma cartesiano di questa situazione con singolo servente e disciplina di coda FIFO.

Ergodicità: tale proprietà comporta l’uguaglianza:

La prima uguaglianza vale perché per i sistemi a coda che andiamo a verificare vale l’ergodicità.

Il fatto che i limiti esistano è dato dalla stazionarietà.

Legge di Little

Legame importantissimo tra λ, N e T. È valida per qualunque sistema.