Deterministic OR models assume all parameters — demand, costs, travel times, capacities — are known with certainty. In practice, uncertainty is pervasive: customer arrivals are random, demand fluctuates, machines fail, delivery times vary. Stochastic OR extends the deterministic toolkit to handle randomness explicitly, producing plans that are robust to uncertainty rather than optimized for a single scenario that may never occur.
Consider a hospital emergency department. A deterministic model might assume 10 patients per hour and staff for exactly that load. But arrivals are random — sometimes 5 per hour, sometimes 18. A staff level that's "optimal" for 10/hour deterministic may produce catastrophic queues during surges or expensive idle time during lulls.
Stochastic models answer the right questions:
Stochastic OR relies on a standard toolkit of probability distributions and stochastic processes:
A Poisson process with rate λ has:
Poisson processes arise naturally when many independent events occur, each with small probability — customer arrivals, equipment failures, incoming calls, insurance claims.
Queuing theory analyzes systems where customers (broadly defined: people, packets, jobs, vehicles) arrive, wait for service, are served, and depart. The field was founded by Danish engineer A.K. Erlang in 1909 to analyze telephone exchange traffic.
Queues are described by A/B/c/K/N notation:
The simplest non-trivial queue: Poisson arrivals (rate λ), exponential service times (mean 1/μ), one server, infinite capacity.
Traffic intensity: ρ = λ/μ. Stability requires ρ < 1 (arrivals slower than service on average).
Equilibrium performance measures:
| Measure | Formula | Interpretation |
|---|---|---|
| P(n customers in system) | (1-ρ)ρⁿ | Geometric distribution |
| Expected customers L | ρ/(1-ρ) | Average queue length |
| Expected wait W | 1/(μ-λ) | Average time in system |
| Expected wait in queue Wq | ρ/(μ-λ) | Average time waiting |
Little's Law: L = λW (the most important equation in queuing theory). The average number in system equals the arrival rate times the average time in system. This holds for any stable queue under very mild conditions — no distributional assumptions needed.
With c servers, the system is stable when ρ = λ/(cμ) < 1. The Erlang C formula gives the probability that a customer must wait (all servers busy). This formula underlies call center staffing: given arrival rate and target wait time, compute the minimum number of agents needed.
When service times have a general distribution (not necessarily exponential) with mean 1/μ and variance σ², the Pollaczek-Khinchine (P-K) formula gives the mean number waiting:
Lq = ρ²(1 + Cₛ²) / (2(1-ρ))
where Cₛ = σμ is the coefficient of variation of service times. The M/M/1 formula is the special case Cₛ = 1.
Key insight: Higher variability in service times increases queue length quadratically. Reducing service time variability (through standardization, automation) can dramatically reduce queues even without adding capacity.
Real systems are networks of queues: a customer passes through multiple service stations. A hospital visit involves triage, registration, physician assessment, lab tests, prescription. A manufacturing job moves through multiple work centers.
Jackson networks (1957): A network of M/M/c queues where each queue can be analyzed independently in isolation, with the arrival rate at each station computed from the network's routing probabilities. This product-form solution makes analysis tractable for large networks.
A Markov chain is a stochastic process where the next state depends only on the current state, not the history. This Markov property (memorylessness) makes computation tractable.
Discrete-time Markov chains (DTMC): State evolves at discrete time steps. Characterized by a transition probability matrix P where Pᵢⱼ = P(next state = j | current state = i).
Continuous-time Markov chains (CTMC): State evolves in continuous time. Characterized by a rate matrix Q where Qᵢⱼ (i≠j) gives the rate of transition from i to j.
Queues are CTMCs: the M/M/1 queue is a birth-death chain with birth rate λ and death rate μ.
Steady-state distribution: For ergodic chains, the long-run fraction of time in each state satisfies πP = π (DTMC) or πQ = 0 (CTMC). This is what queuing performance formulas compute.
An MDP extends Markov chains to sequential decision problems:
The goal is a policy π: S → A that maximizes expected discounted total reward.
Value iteration and policy iteration are the standard algorithms. They converge to the optimal policy for finite MDPs.
MDP applications in OR include:
When a system is too complex for analytical tractability, simulation becomes the tool of choice. Monte Carlo simulation generates many random realizations of the system, observing outcomes to estimate performance measures.
In discrete-event simulation (DES), the simulation advances from event to event (arrival, service completion) rather than in fixed time steps. Events are maintained in a priority queue sorted by time. This is computationally efficient for systems where events are sparse relative to the time horizon.
Major DES platforms: AnyLogic, Arena, Simul8, SimPy (Python), JaamSim.
Stochastic programming formulates optimization problems where some parameters are random, and decisions are made in stages as uncertainty resolves.
The paradigmatic structure:
The objective minimizes expected total cost: c₁ᵀx + E_ξ(Q(x,ξ)), where Q(x,ξ) is the second-stage cost given first-stage decisions x and realized scenario ξ.
Example: A power company decides how much generation capacity to build (first stage, before knowing demand) and how much power to buy on the spot market or shed load (second stage, after demand is known). The objective minimizes expected total cost over many demand scenarios.
For discrete scenario distributions, stochastic programs are solved by enumerating scenarios and solving the resulting large deterministic LP. With many scenarios, Benders decomposition decomposes them into a master problem and scenario subproblems, making large instances tractable.
The VSS measures how much is gained by solving the stochastic program vs. ignoring uncertainty and optimizing for the expected scenario. High VSS problems strongly reward stochastic approaches.
| Application | Model Type | Key Insight |
|---|---|---|
| Call center staffing | M/M/c queuing | Erlang C gives minimum agents for service target |
| Hospital capacity planning | Queuing networks | Model patient flow through care stages |
| Inventory safety stock | Stochastic demand | Safety stock = z × σ_demand × √lead_time |
| Revenue management | MDP | Optimal booking policies under random demand |
| Financial portfolio risk | Stochastic LP | CVaR constraints handle tail risk |
| Power grid planning | Two-stage SP | Capacity decisions before demand uncertainty resolves |
| Supply chain design | Stochastic IP | Robust network against demand and disruption uncertainty |