Simulazione di Code con Algoritmo M/M/c

Questo post presenta QueueForge, uno strumento interattivo e didattico per la simulazione di code basato sul modello M/M/c della teoria delle code. L'applicazione, costruita con React, TypeScript e Vite, consente di esplorare in modo visuale e in tempo reale il comportamento di un sistema di code multi-server, tipicamente utilizzato per modellare scenari reali come call center, sportelli bancari e help desk.

QueueForge combina tre aspetti fondamentali:

  • Modello teorico M/M/c - implementazione delle formule matematiche della teoria delle code, inclusa la formula di Erlang C
  • Simulazione a eventi discreti - motore di simulazione che genera dati empirici confrontabili con le previsioni teoriche
  • Visualizzazione in tempo reale - grafici e metriche aggiornate istantaneamente al variare dei parametri

L'applicazione è disponibile e accessibile liberamente all'indirizzo: https://computationalmindset.com/apps/QueueForge

Fondamenti della Teoria delle Code

La teoria delle code (in inglese queueing theory) è una branca della matematica applicata che studia i fenomeni di attesa. Nata nel 1909 dal lavoro dell'ingegnere danese Agner Krarup Erlang nell'ambito della telefonia, questa teoria fornisce strumenti matematici per analizzare e ottimizzare sistemi in cui entità (clienti, pacchetti, richieste) arrivano, attendono e vengono servite.

Un sistema di code è caratterizzato da tre componenti fondamentali:

  • Processo di arrivo: descrive come i clienti arrivano nel sistema (ad esempio, secondo un processo di Poisson)
  • Processo di servizio: descrive la durata del servizio (ad esempio, con distribuzione esponenziale)
  • Infrastruttura di servizio: numero di server, capacità della coda, disciplina di servizio (FIFO, LIFO, priorità)

La notazione di Kendall classifica i sistemi di code con la forma A/B/c/K/N/D, dove:

  • A: distribuzione dei tempi di inter-arrivo (M = Markoviana/esponenziale, D = deterministica, G = generica)
  • B: distribuzione dei tempi di servizio
  • c: numero di server
  • K: capacità massima del sistema (omessa se infinita)
  • N: dimensione della popolazione (omessa se infinita)
  • D: disciplina di servizio (omessa se FIFO)

Nella forma abbreviata, un sistema M/M/c indica:

  • M (primo): arrivi secondo un processo di Poisson (tempi di inter-arrivo esponenziali)
  • M (secondo): tempi di servizio con distribuzione esponenziale
  • c: numero di server identici e paralleli
con capacità infinita della coda, popolazione infinita e disciplina FIFO.

Il Modello M/M/c

Il modello M/M/c è il modello fondamentale della teoria delle code per sistemi multi-server. I parametri principali sono:

  • Tasso di arrivo $\lambda$ (lambda): numero medio di clienti che arrivano per unità di tempo
  • Tasso di servizio $\mu$ (mu): numero medio di clienti che un singolo server può servire per unità di tempo
  • Numero di server $c$: server identici e paralleli disponibili

Utilizzazione del sistema

L'utilizzazione $\rho$ rappresenta la frazione di tempo in cui i server sono occupati: $$\rho = \frac{\lambda}{c \cdot \mu}$$ Il sistema è stabile (cioè la coda non cresce indefinitamente) se e solo se $\rho < 1$, ossia quando la capacità complessiva di servizio $c \cdot \mu$ è superiore al tasso di arrivo $\lambda$. Se $\rho \geq 1$, la coda cresce senza limiti nel tempo.

Formula di Erlang C

La formula di Erlang C calcola la probabilità che un cliente debba attendere in coda (probabilità di ritardo). Definendo il carico offerto $a = \lambda / \mu$, la formula è: $$C(c, a) = \frac{\displaystyle \frac{a^c}{c!} \cdot \frac{c}{c - a}}{\displaystyle \sum_{k=0}^{c-1} \frac{a^k}{k!} + \frac{a^c}{c!} \cdot \frac{c}{c - a}}$$ Questa formula è alla base del calcolo di tutte le metriche prestazionali del sistema M/M/c.

Metriche prestazionali

A partire dalla formula di Erlang C si derivano le metriche fondamentali del sistema:

Lunghezza media della coda $L_q$ (numero medio di clienti in attesa, esclusi quelli in servizio): $$L_q = C(c, a) \cdot \frac{\rho}{1 - \rho}$$

Numero medio di clienti nel sistema $L$ (in attesa + in servizio): $$L = L_q + \frac{\lambda}{\mu}$$

Tempo medio di attesa in coda $W_q$ (derivato dalla Legge di Little): $$W_q = \frac{L_q}{\lambda}$$

Tempo medio nel sistema $W$ (attesa + servizio): $$W = \frac{L}{\lambda}$$

La Legge di Little

La Legge di Little è un teorema fondamentale che vale per qualunque sistema di code stabile, indipendentemente dalla distribuzione degli arrivi o dei servizi: $$L = \lambda \cdot W$$ e analogamente per la coda: $$L_q = \lambda \cdot W_q$$ Questa relazione è utilizzata sia nel calcolo teorico sia nella validazione della simulazione.

Esempio numerico: coda M/M/1

Come caso particolare del modello M/M/c con $c = 1$, consideriamo un sistema con $\lambda = 6$ clienti/min e $\mu = 10$ clienti/min:

  • Utilizzazione: $\rho = 6 / (1 \times 10) = 0{,}6$ (60%)
  • Lunghezza media della coda: $L_q = 0{,}9$ clienti
  • Tempo medio di attesa: $W_q = 0{,}15$ min = 9 secondi

Esempio numerico: coda M/M/2

Per un call center con 2 operatori ($c = 2$), $\lambda = 10$ clienti/min e $\mu = 8$ clienti/min per server:

  • Utilizzazione: $\rho = 10 / (2 \times 8) = 0{,}625$ (62,5%)
  • Probabilità di attesa (Erlang C): $C(2, 1{,}25) \approx 0{,}481$
  • Lunghezza media della coda: $L_q \approx 0{,}8$ clienti

La Simulazione a Eventi Discreti

Oltre al calcolo teorico, QueueForge implementa un motore di simulazione a eventi discreti (discrete event simulation) che genera dati empirici confrontabili con le previsioni del modello matematico.

La simulazione opera per passi temporali discreti e ad ogni passo esegue le seguenti operazioni:

  1. Generazione degli arrivi: si verifica se un nuovo cliente arriva nel passo corrente, usando un processo di Bernoulli con probabilità $p_{\text{arrivo}} = \lambda \cdot \Delta t$ (approssimazione del processo di Poisson per piccoli $\Delta t$)
  2. Completamento dei servizi: per ciascun server occupato, si verifica se il servizio viene completato con probabilità $p_{\text{servizio}} = \mu \cdot \Delta t$ (approssimazione del processo esponenziale)
  3. Gestione della coda: i clienti in attesa vengono assegnati ai server disponibili secondo la disciplina FIFO
  4. Raccolta delle statistiche: si aggiornano le metriche cumulative (lunghezza media della coda, tempo medio di attesa, ecc.)

Questo approccio consente di osservare come i valori empirici convergano verso le previsioni teoriche all'aumentare del tempo di simulazione. Per simulazioni sufficientemente lunghe (oltre 5000 secondi), i risultati empirici tendono a convergere entro il 5-10% dei valori teorici.

Interfaccia Utente e Interazione

QueueForge fornisce un'interfaccia intuitiva e professionale con diverse funzionalità chiave:

  • Slider interattivi: regolazione in tempo reale del tasso di arrivo ($\lambda$), tasso di servizio ($\mu$), numero di server ($c$) e velocità di simulazione
  • Grafico in tempo reale: visualizzazione canvas dell'andamento della lunghezza della coda nel tempo
  • Metriche del sistema: lunghezza corrente della coda, utilizzazione, medie teoriche ed empiriche a confronto
  • Tooltip educativi: passando il mouse sui parametri si ottiene una spiegazione del loro significato
  • Controlli di simulazione: pulsanti Play, Pausa e Reset per controllare il flusso della simulazione

L'interazione principale consiste nel modificare i parametri del sistema e osservare immediatamente l'effetto sia sulle metriche teoriche (calcolate analiticamente) sia sulla simulazione in corso, costruendo così un'intuizione profonda sul comportamento dei sistemi di code.

Implementazione Tecnica

QueueForge è costruito utilizzando tecnologie web moderne e segue una architettura a separazione netta delle responsabilità:

  • React 18: framework UI basato su componenti per costruire la struttura dell'applicazione
  • TypeScript: con strict mode abilitato per la sicurezza dei tipi e la manutenibilità del codice
  • Vite: strumento di build moderno per uno sviluppo veloce e build di produzione ottimizzate
  • SCSS: CSS con variabili e moduli per uno stile strutturato
  • Canvas API: rendering personalizzato dei grafici per prestazioni ottimali

L'architettura del progetto è organizzata in quattro livelli distinti:

  1. Livello Models (models/): funzioni matematiche pure che implementano le formule della teoria delle code M/M/c (Erlang C, Legge di Little, ecc.)
  2. Livello Simulation (simulation/): motore di simulazione a eventi discreti che genera dati empirici
  3. Livello Visualization (visualization/): rendering basato su Canvas ottimizzato per aggiornamenti in tempo reale
  4. Livello UI (components/, App.tsx): componenti React che orchestrano l'interazione con l'utente

La suite di test garantisce una copertura del codice superiore al 70%, verificando l'accuratezza delle formule M/M/c, la conformità alla Legge di Little, la convergenza della simulazione e il corretto rilevamento dell'instabilità del sistema.

Prova QueueForge

Prova QueueForge direttamente nel tuo browser:

Avvia QueueForge

L'applicazione non richiede installazione e funziona su qualsiasi browser web moderno. Per la migliore esperienza, utilizza una versione recente di Chrome, Firefox, Safari o Edge.

Sviluppo e Contributi

QueueForge è stato sviluppato con Claude Code seguendo l'approccio BMAD (Breakthrough Method of Agile AI-driven Development), come parte di un'esplorazione nello sviluppo software assistito da AI per strumenti educativi.

Il progetto segue le pratiche standard di sviluppo TypeScript e JavaScript moderno:

Clonare il repository: 

git clone https://github.com/ettoremessina/QueueForge.git
cd QueueForge

Installare le dipendenze: 

npm install

Avviare il server di sviluppo: 

npm run dev
Questo avvia un server di sviluppo locale con hot module replacement per un'iterazione rapida.

Build per la produzione: 

npm run build
L'output ottimizzato viene generato nella cartella dist/ e può essere distribuito su qualsiasi servizio di hosting statico.

Eseguire i test: 

npm test

Codice Sorgente e Licenza

Il codice sorgente completo è disponibile su GitHub a questo indirizzo: QueueForge.

Questo materiale è distribuito su licenza MIT; sentiti libero di usare, condividere, "forkare" e adattare tale materiale come credi.
Sentiti anche libero di pubblicare pull-request e bug-report su questo repository di GitHub oppure di contattarmi sui miei canali social disponibili nell'angolo in alto a destra di questa pagina.