mathematics//probability//queueing theory//M/M/1 queue

The M/M/1 queue is the simplest model of a waiting line, with random independent arrivals at rate \(\lambda\), a single server whose service times are exponential with mean \(1/\mu\), and service in order of arrival, and it is used to show how waiting depends on utilization before any detailed simulation is built. With utilization \(\rho=\lambda/\mu\) below one, the mean time spent waiting before service is

The M/M/1 queue is the simplest model of a waiting line, with random independent arrivals at rate λ\lambdaλ, a single server whose service times are exponential with mean 1/μ1/\mu1/μ, and service in order of arrival, and it is used to show how waiting depends on utilization before any detailed simulation is built. With utilization ρ=λ/μ\rho=\lambda/\muρ=λ/μ below one, the mean time spent waiting before service is

Wq=ρ1−ρ⋅1μ.W_q=\frac{\rho}{1-\rho}\cdot\frac{1}{\mu}.Wq​=1−ρρ​⋅μ1​.

The first factor counts waits in units of one service time. At 50 % utilization an arrival waits on average one service time; at 90 %, nine; at 99 %, ninety-nine. A shared charger whose charges take 30 minutes, busy 90 % of the time, keeps robots waiting four and a half hours on average before they even plug in, and the total time in the system is W=1/(μ−λ)W=1/(\mu-\lambda)W=1/(μ−λ).

Spare capacity is what keeps the waits finite.

Raising a shared resource from 80 % to 95 % utilization multiplies the mean wait by almost five (from 4 to 19 service times), so the last points of utilization are bought with latency, and a proposal to run a charger, a bus or a link near full because the capacity looks idle is a proposal to make everyone wait.

M stands for memoryless. Arrivals come independently (a Poisson process) and every service time is exponential, so the past says nothing about when the next arrival or completion comes. Real arrivals in bursts, at a shift change or after a mission ends, make waits longer than the model; services of nearly fixed length make them shorter, about half for a constant service time (queueing theory).

At λ≥μ\lambda\ge\muλ≥μ there is no steady state: the line grows without limit. A burst above the service rate leaves a backlog that drains only at μ−λ\mu-\lambdaμ−λ, so a server normally loaded at 95 % needs four times as long as a burst at 120 % lasted to clear the backlog it left.

Pooling helps. Two chargers fed from one shared line (M/M/2) keep shorter waits than two chargers each with its own line at the same total load, because no charger sits idle while a robot waits at the other.

The same curve, flat and then vertical, is the latency of a network link, a disk or a processor plotted against load, and Little's law turns its waits into the number of robots, packets or tasks piled up.