mathematics//probability//queueing theory
Queueing theory is the branch of probability that models waiting lines, items that arrive at random and servers that take time to serve them, and it is used to size what a system shares: the chargers of a robot fleet, the slots of a CAN bus, the processor of a flight controller, the buffers of a network, the repair crew of a plant. Its models are named in **Kendall notation**, A/S/c: the arrival process, the service-time distribution and the number of servers, with M standing for memoryless (independent random arrivals, exponential service times) and D for deterministic.
Queueing theory is the branch of probability that models waiting lines, items that arrive at random and servers that take time to serve them, and it is used to size what a system shares: the chargers of a robot fleet, the slots of a CAN bus, the processor of a flight controller, the buffers of a network, the repair crew of a plant. Its models are named in Kendall notation, A/S/c: the arrival process, the service-time distribution and the number of servers, with M standing for memoryless (independent random arrivals, exponential service times) and D for deterministic.
The number that governs everything is the utilization ρ=λ/(cμ)\rho=\lambda/(c\mu)ρ=λ/(cμ), the arrival rate over the total service rate, which is the fraction of time the servers are busy. Above one the line grows without limit. Below one it stays finite, but its mean wait grows as 1/(1−ρ)1/(1-\rho)1/(1−ρ), slowly at first and then violently as ρ\rhoρ approaches one, and that curve is why engineers keep slack where an accountant sees idle capacity.
Waiting is caused by variability as much as by load.
A server fed at perfectly regular intervals with jobs of fixed length never builds a queue below full load; randomness does. For one server with random arrivals the mean wait is proportional to (1+Cs2)/2(1+C_s^2)/2(1+Cs2)/2 (the Pollaczek-Khinchine formula, with CsC_sCs the coefficient of variation of the service time), so making every service the same length halves the wait of exponential service at any load.
The first thing to compute is usually Little's law, L=λWL=\lambda WL=λW: the count, the rate and the time of any stable system are tied together, so two easy measurements give the third, with no assumption about distributions.
The simplest model with a closed form is the M/M/1 queue, one server and memoryless arrivals and service; its table of waits against utilization is the argument to show anyone who wants to run a shared resource at 95 %.
The same ρ\rhoρ appears under other names. The utilization U=∑iCi/TiU=\sum_iC_i/T_iU=∑iCi/Ti of a processor in real-time scheduling and the bus load ∑iLi/(R Ti)\sum_iL_i/(R,T_i)∑iLi/(RTi) of a CAN bus (message bits over period and bus rate) are demand over capacity, and near one any burst becomes delay.
In large systems the waits are rarely well behaved. A jammed aisle slows the robots in it, which keeps them there longer and lets more in, so past a point adding robots lowers throughput (complex system), and the distribution of waits grows heavy tails that the mean hides.