Simulazione di Code con Algoritmo M/M/c/K

Questo post presenta l'estensione M/M/c/K del modello di code M/M/c, implementata in QueueForge. QueueForge supporta ora entrambi i modelli — M/M/c (capacità infinita) e M/M/c/K (capacità finita) — selezionabili tramite un menu a tendina nel pannello dei parametri. Se non hai ancora familiarità con la teoria delle code e il modello M/M/c, ti consigliamo di leggere prima il post introduttivo Simulazione di Code con Algoritmo M/M/c, che tratta la notazione di Kendall, gli arrivi di Poisson, la formula di Erlang C e la Legge di Little. Questo post si concentra esclusivamente sulla variante a capacità finita e su come cambia l'analisi matematica.

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

Da M/M/c a M/M/c/K: Capacità Finita del Sistema

Il modello M/M/c assume una sala d'attesa illimitata: qualunque numero di clienti può accodarsi mentre tutti i server sono occupati. In pratica, molti sistemi reali hanno un limite fisico o logico al numero totale di clienti consentiti contemporaneamente (coda + server combinati). Quando il sistema è pieno, i nuovi arrivi vengono rifiutati (persi o bloccati).

Nella notazione di Kendall A/B/c/K/N/D, il quarto campo K specifica la capacità massima del sistema (clienti in attesa più clienti in servizio). Un sistema M/M/c/K ha quindi:

M (primo): arrivi di Poisson con tasso $\lambda$
M (secondo): tempi di servizio esponenziali con tasso $\mu$ per server
c: numero di server identici e paralleli
K: capacità massima del sistema — deve soddisfare $K \geq c + 1$

Due conseguenze immediate distinguono M/M/c/K da M/M/c:

Sempre stabile: poiché la coda è limitata, il sistema è sempre in stato stazionario indipendentemente dal rapporto ρ. Anche con λ > cμ il sistema non va mai in overflow.
Probabilità di rifiuto: un cliente che arriva quando il sistema è alla capacità K viene respinto. Questa probabilità deve essere calcolata e incorporata in tutte le metriche prestazionali tramite un tasso di arrivo effettivo.

Il Modello Matematico M/M/c/K

Probabilità di stato

La probabilità stazionaria $P_n$ di avere $n$ clienti nel sistema è: $$P_n = \begin{cases} P_0 \cdot \dfrac{a^n}{n!} & 0 \le n \le c \\[6pt] P_0 \cdot \dfrac{a^c}{c!} \cdot \rho^{n-c} & c < n \le K \end{cases}$$ dove $a = \lambda / \mu$ è il carico offerto e $\rho = \lambda / (c \cdot \mu)$ è l'utilizzazione del server. La costante di normalizzazione $P_0$ (probabilità che il sistema sia vuoto) si ottiene imponendo $\sum_{n=0}^{K} P_n = 1$: $$P_0 = \frac{1}{\displaystyle\sum_{k=0}^{c-1} \frac{a^k}{k!} \;+\; \frac{a^c}{c!} \cdot \frac{1 - \rho^{K-c+1}}{1 - \rho}} \qquad (\rho \ne 1)$$ Quando $\rho = 1$ la somma geometrica degenera e il denominatore diventa: $$\sum_{k=0}^{c-1} \frac{a^k}{k!} + \frac{a^c}{c!} \cdot (K - c + 1)$$

Probabilità di rifiuto

La probabilità che il sistema sia pieno — e che un cliente in arrivo venga respinto — è $P_K$: $$P_K = \begin{cases} P_0 \cdot \dfrac{a^K}{K!} & K \le c \\[6pt] P_0 \cdot \dfrac{a^c}{c!} \cdot \rho^{K-c} & K > c \end{cases}$$ $P_K$ è talvolta chiamata probabilità di perdita o probabilità di blocco.

Tasso di arrivo effettivo

Poiché una frazione $P_K$ di tutti gli arrivi viene persa, il tasso di clienti che entrano effettivamente nel sistema è: $$\lambda_{\text{eff}} = \lambda \cdot (1 - P_K)$$ Tutte le metriche prestazionali devono essere calcolate con $\lambda_{\text{eff}}$ anziché con il $\lambda$ nominale, altrimenti la Legge di Little verrebbe violata.

Lunghezza media della coda

Il numero medio di clienti in attesa (esclusi quelli in servizio) è: $$L_q = \frac{a^c \cdot \rho \cdot P_0}{c!} \cdot \frac{1 - \rho^{K-c+1} - (K-c+1)\,\rho^{K-c}(1-\rho)}{(1-\rho)^2} \qquad (\rho \ne 1)$$ Quando $\rho = 1$: $$L_q = \frac{a^c \cdot P_0}{c!} \cdot \frac{(K-c)(K-c+1)}{2}$$

Metriche prestazionali derivate

Le rimanenti metriche si derivano da $L_q$ e $\lambda_{\text{eff}}$ applicando la Legge di Little:

Numero medio di clienti nel sistema $L$: $$L = L_q + \frac{\lambda_{\text{eff}}}{\mu}$$

Tempo medio di attesa in coda $W_q$: $$W_q = \frac{L_q}{\lambda_{\text{eff}}}$$

Tempo medio nel sistema $W$: $$W = \frac{L}{\lambda_{\text{eff}}}$$

Confronto con M/M/c

Per $K \to \infty$ le formule M/M/c/K convergono ai risultati M/M/c: $P_K \to 0$, $\lambda_{\text{eff}} \to \lambda$ e la formula di $L_q$ si riduce all'espressione di Erlang C $C(c,a) \cdot \rho / (1-\rho)$. In un sistema a capacità finita la coda è sempre più corta (alcuni clienti vengono respinti prima di accodarsi), quindi $L_q^{(K)} \le L_q^{(\infty)}$ per qualsiasi $K$ e qualsiasi $\rho$.

Esempio numerico: coda M/M/1/5

Consideriamo un sistema a singolo server sovraccarico con $c = 1$, $K = 5$, $\lambda = 10$ arrivi/min e $\mu = 8$ clienti/min — una configurazione che sarebbe instabile come semplice M/M/1 ($\rho = 1{,}25 > 1$), ma è sempre stabile con M/M/1/5:

Utilizzazione del server: $\rho = 10 / (1 \times 8) = 1{,}25$ (sovraccaricato, eppure stabile grazie a $K$)
Probabilità di rifiuto: $P_5 \approx 0{,}271$ (circa il 27,1% degli arrivi viene respinto)
Tasso di arrivo effettivo: $\lambda_{\text{eff}} = 10 \times (1 - 0{,}271) \approx 7{,}29$ clienti/min
Lunghezza media della coda: $L_q \approx 2{,}22$ clienti
Tempo medio nel sistema: $W = L / \lambda_{\text{eff}} \approx 0{,}43$ min = 25,8 secondi

Aumentando $K$ si riduce la probabilità di rifiuto, si allunga la coda e il sistema si avvicina all'instabilità M/M/1 per $K \to \infty$.

Simulazione di M/M/c/K

Il motore di simulazione di QueueForge gestisce il caso a capacità finita estendendo la simulazione M/M/c a passi temporali con una sola regola aggiuntiva: quando viene generato un nuovo arrivo e il numero corrente di clienti nel sistema è uguale a $K$, il cliente viene rifiutato e il contatore dei rifiuti viene incrementato. Tutte le altre meccaniche (prove di Bernoulli per gli arrivi con $p = \lambda \cdot \Delta t$, prove di completamento del servizio con $p = \mu \cdot \Delta t$ per ciascun server occupato, gestione FIFO della coda) rimangono identiche alla simulazione M/M/c descritta in Simulazione di Code con Algoritmo M/M/c.

Questo consente alla simulazione di stimare direttamente il tasso empirico di rifiuto, che converge alla $P_K$ teorica all'aumentare del tempo di simulazione. Il tasso di rifiuto esposto dal motore di simulazione è: $$\hat{P}_K = \frac{\text{totale rifiutati}}{\text{totale arrivi}}$$

Interfaccia Utente e Interazione

QueueForge mette a disposizione un menu a tendina Modello di Coda in cima al pannello dei parametri per passare in qualsiasi momento tra M/M/c e M/M/c/K. Il modello M/M/c/K è apribile direttamente anche tramite il parametro URL ?model=mmck (ad es. .../QueueForge?model=mmck); cambiando il menu a tendina l'URL si aggiorna automaticamente, rendendo il link condivisibile.

Quando è selezionato M/M/c/K, appare uno slider aggiuntivo Capacità Massima (K) accanto ai parametri standard ($\lambda$, $\mu$, $c$, velocità di simulazione). Il pannello delle metriche mostra anche:

Probabilità di rifiuto: P_K teorica e tasso empirico di rifiuto a confronto
Tasso di arrivo effettivo: la vera portata di clienti che entra nel sistema

Implementazione Tecnica

Il modello M/M/c/K è implementato nella classe MMCKQueueingModel (src/models/MMCKQueueingModel.ts), un complemento alla classe MMCQueueingModel per il caso illimitato. Il motore di simulazione in QueueSimulation.ts accetta un parametro opzionale maxCapacity: quando fornito, attiva la modalità M/M/c/K in modo trasparente, senza modificare la struttura del ciclo di simulazione.

L'architettura complessiva rimane la stessa a quattro livelli:

Livello Models (models/): MMCKQueueingModel implementa $P_0$, $P_K$ (probabilità di blocco di Erlang B), $L_q$ e tutte le metriche derivate con le formule in forma chiusa indicate sopra
Livello Simulation (simulation/): QueueSimulation con maxCapacity per il tracciamento dei rifiuti
Livello Visualization (visualization/): grafico canvas invariato; il tasso di rifiuto è mostrato nel pannello metriche
Livello UI (components/, App.tsx): componenti React con uno slider K aggiuntivo

La suite di test in src/models/__tests__/MMCKQueueingModel.test.ts verifica valori noti per M/M/1/K e M/M/2/K, valida la probabilità di blocco di Erlang B rispetto a tabelle di riferimento pubblicate, controlla che $P_K \to 0$ per $K \to \infty$ e conferma che $\lambda_{\text{eff}} \le \lambda$ sia sempre verificato.

Prova QueueForge

Prova QueueForge con il modello M/M/c/K direttamente nel tuo browser:

Avvia QueueForge (M/M/c/K)

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

L'estensione M/M/c/K di QueueForge è stata sviluppata con Claude Code seguendo l'approccio BMAD (Breakthrough Method of Agile AI-driven Development), come parte di un'esplorazione continua 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.