Catene di Markov a tempo continuo e applicazioni ai sistemi client/server

Obiettivo di questa tesi è quello di presentare dei modelli probabilistici, in particolare le catene di Markov a tempo continuo, al fine di modellizzare i sistemi di coda di tipo client/server. La teoria delle code rappresenta uno strumento importante per analizzare i sistemi di servizio, caratterizzati da un server al quale giungono degli utenti in modo aleatorio che chiedono di usufruirne. Qualora il servizio risultasse occupato, c'è la possibilità di formazione di code di attesa prima di poterne beneficiare, per poi abbandonare il sistema. Tali modelli trovano innumerevoli applicazioni, dalla ricerca operativa all'ingegneria industriale. Alcuni esempi sono i flussi di traffico (veicoli, aerei, persone, comunicazione), programmazione (pazienti in ospedale, programmi su computer) e la progettazione di strutture (banche, uffici postali, parchi divertimento). I primi studi risalgono al 1909, quando il matematico e ingegnere telefonico Agner Krarup Erlang pubblicò "The Theory of Probabilities and Telephone Conversations". In lavori successivi osservò che il sistema telefonico era caratterizzato da ingressi Poissoniani, tempi di servizio esponenziali e con server multipli, oppure ingressi Poissoniani, tempi di servizio costanti e un unico server. La teoria a riguardo è abbastanza sviluppata e si possono trovare innumerevoli testi di riferimento; in questo caso abbiamo deciso di seguire principalmente la trattazione del libro di Ross (2006). Per arrivare a trattare tali sistemi, introdurremo preliminarmente i risultati di base nell'ambito delle catene di Markov su spazi discreti e passeremo poi al caso più generale di catene di Markov a tempo continuo e quindi arriveremo ai sistemi di code. In dettaglio, nel capitolo 1 definiremo le catene di Markov, ovvero processi stocastici la cui distribuzione futura dipende solo dallo stato presente ed è indipendente da quello passato; parleremo di matrice di transizione e classificheremo i possibili stati della catena. Infine analizzeremo le distribuzioni stazionarie, che saranno fondamentali per descrivere i sistemi di code. Nel capitolo 2 affronteremo la generalizzazione al caso di catene di Markov a tempo continuo, l'oggetto di base sarà il processo di Poisson, che possiamo pensare come una sequenza di arrivi indipendenti con tempi di interarrivo esponenziali. In particolare dimostreremo alcune proprietà rilevanti dei processi di Poisson. Tra le catene di Markov a tempo continuo ci focalizzeremo sui processi di nascita e morte per poi analizzare probabilità di transizione e limite. Nel capitolo 3 vedremo alcuni modelli di code; fondamentale nella nostra analisi sarà la formula di Little, che ci permetterà di calcolare alcune quantità medie, come il numero medio di clienti nel sistema o il tempo di attesa in coda, a seconda delle varie ipotesi. Inizialmente introdurremo le code M/M/1 con tempi di arrivo e tempi di servizio esponenziali con un unico server, per poi trattare il caso di code M/M/c con c server. Infine ci porremo in un contesto più generale indebolendo l'ipotesi di Markovianità, in particolare ci concentreremo sulle code M/G/1 con tempi di servizio generici. Tale modello sarà utile per poter affrontare il problema di code con priorità, in cui i clienti che accedono al servizio saranno di diversi tipi, i quali ne determineranno la priorità di servizio.