15 M/M/n Queue

Published

June 18, 2025

The M/M/n queue is a discrete stochastic process that models a queue with n servers. There are three parameters:

\(n\): the number of servers
\(\lambda\): the arrival rate of customers
\(\mu\): the service rate of each server

The “M” in M/M/n stands for “memoryless” or Markovian. The M/M/n queue models the following process: - customers arrive at the queue according to a Poisson process with rate \(\lambda\). - Each customer is served by one of the n servers, and the service times are exponentially distributed with rate \(\mu\). - If all servers are busy, the customer waits in line until a server becomes available.

We are interested in testing the performance of the queue as function of the three parameters. There are various performance measures we can compute, including: - The average number of customers in the waiting line - The average time a customer spends waiting in line - The usage of the servers - The probability that a customer has to wait in line

There are two approaches we can take to simulate an M/M/n queue

Process driven
Event driven

VM = window.VM
vmTheme = Generators.observe(notify => VM.plotting.onThemeChange(notify))
chartColors = VM.plotting.colors(vmTheme)

mmnQueuePlot = VM.plotting.persistentPlot({height: "340px"})

// Discrete-event simulation of an M/M/n queue until maxCustomers have
// departed. Events are kept in a list sorted by time (a heap would be
// faster; a thousand customers don't need one). Returns each customer's
// arrival, service-start and departure times and the queue length after
// every event.
function mmnSimulate({arrivalRate, serviceRate, servers, maxCustomers, seed}) {
  const rng = VM.sampling.seededRandom(seed)
  const interArrival = VM.sampling.exponentialRandom(rng, arrivalRate)
  const serviceTime = VM.sampling.exponentialRandom(rng, serviceRate)
  const events = []
  function schedule(time, type, id) {
    let k = events.length
    while (k > 0 && events[k - 1].time > time) k--
    events.splice(k, 0, {time, type, id})
  }
  const arrival = [], start = [], departure = []
  const waiting = []
  const log = {times: [], lengths: []}
  let busy = 0
  let departed = 0
  let nextId = 1
  schedule(interArrival(), "arrival", 0)
  while (events.length > 0 && departed < maxCustomers) {
    const event = events.shift()
    const clock = event.time
    log.times.push(clock)
    log.lengths.push(waiting.length)
    if (event.type === "arrival") {
      arrival[event.id] = clock
      if (busy < servers) {
        busy++
        start[event.id] = clock
        schedule(clock + serviceTime(), "departure", event.id)
      } else {
        waiting.push(event.id)
      }
      if (nextId < maxCustomers) {
        schedule(clock + interArrival(), "arrival", nextId)
        nextId++
      }
    } else {
      departure[event.id] = clock
      departed++
      busy--
      if (waiting.length > 0) {
        const next = waiting.shift()
        busy++
        start[next] = clock
        schedule(clock + serviceTime(), "departure", next)
      }
    }
  }
  return {arrivalRate, serviceRate, servers, arrival, start, departure, log}
}

{
  const sim = mmnSim
  const waits = [], sojourns = []
  for (let id = 0; id < sim.departure.length; id++) {
    if (sim.departure[id] === undefined) continue
    waits.push(sim.start[id] - sim.arrival[id])
    sojourns.push(sim.departure[id] - sim.arrival[id])
  }
  const utilization = Math.min(1, sim.arrivalRate / (sim.servers * sim.serviceRate))
  return VM.ui.statRow([
    {label: "Customers simulated", value: String(waits.length)},
    {label: "Average wait time", value: VM.distributions.sampleStats(waits).mean.toFixed(4)},
    {label: "Average sojourn time", value: VM.distributions.sampleStats(sojourns).mean.toFixed(4)},
    {label: "Server utilization (theoretical)", value: utilization.toFixed(4)}
  ])
}

mmnQueuePlot([{x: mmnSim.log.times, y: mmnSim.log.lengths, type: "scatter", mode: "lines", line: {shape: "hv", color: chartColors.fn, width: 1.5}}], {
  title: {text: "Queue length over time"}, margin: {t: 40}, showlegend: false,
  xaxis: {title: "Simulation time"}, yaxis: {title: "Queue length"}
})