Stochastic Models in Operations Research

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.

Why Deterministic Models Fall Short

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:

- What fraction of time will the queue exceed 20 patients?

- How many servers do we need so 95% of customers wait less than 5 minutes?

- What inventory level ensures we never stock out with 99% probability?

Probability Fundamentals in OR

Stochastic OR relies on a standard toolkit of probability distributions and stochastic processes:

Key Distributions

- **Exponential distribution:** Memoryless distribution for service times and inter-arrival times; enables tractable queuing analysis

- **Poisson distribution:** Models the count of random events in a fixed period; Poisson arrivals are the standard assumption in queuing theory

- **Normal distribution:** Demand and forecast errors; central to inventory safety stock calculations

- **Lognormal distribution:** Asset returns, certain failure time models

- **Erlang distribution:** Sum of k exponential distributions; models service times more realistically than exponential

The Poisson Process

A Poisson process with rate λ has:

- Arrivals in any interval of length t distributed as Poisson(λt)

- Inter-arrival times distributed as Exponential(λ)

- Memoryless property: the time to next arrival is independent of how long since the last

Poisson processes arise naturally when many independent events occur, each with small probability — customer arrivals, equipment failures, incoming calls, insurance claims.

Queuing Theory

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.

Kendall's Notation

Queues are described by A/B/c/K/N notation:

- **A:** Arrival process (M = Poisson/memoryless, D = deterministic, G = general)

- **B:** Service time distribution (M, D, G as above)

- **c:** Number of servers

- **K:** System capacity (default: ∞)

- **N:** Population size (default: ∞)

The M/M/1 Queue

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.

The M/M/c Queue

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.

M/G/1 Queue

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.

Queuing Networks

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.

Markov Chains and Decision Processes

Markov Chains

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.

Markov Decision Processes (MDPs)

An MDP extends Markov chains to sequential decision problems:

- **States** S: the possible situations

- **Actions** A(s): decisions available in state s

- **Transition probabilities** P(s'|s,a): how actions stochastically move between states

- **Rewards** r(s,a): immediate payoff from taking action a in state s

- **Discount factor** γ ∈ [0,1): weight on future vs. immediate rewards

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:

- Inventory control with stochastic demand

- Equipment replacement under uncertain degradation

- Revenue management with stochastic arrivals (see [Revenue Management with OR](RevenueManagementWithOR))

- Call center routing policies

Monte Carlo Simulation

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.

The Method

1. Build a model of the system (event-driven or time-step-driven)

2. Specify probability distributions for all random inputs

3. Generate thousands of random scenarios from those distributions

4. Observe outputs (cost, throughput, queue length, profit) in each scenario

5. Use the distribution of outputs to estimate mean, variance, percentiles

When to Use Simulation

- Analytical models are intractable (non-Poisson arrivals, complex routing)

- The system involves dependencies that break product-form assumptions

- Need to model warm-up, transients, and non-stationary behavior

- Validating analytical results

- Communication: simulation runs are intuitive to non-specialists

Discrete-Event Simulation

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

**Stochastic programming** formulates optimization problems where some parameters are random, and decisions are made in stages as uncertainty resolves.

Two-Stage Stochastic Programming

The paradigmatic structure:

1. **First stage:** Make decisions x *before* uncertainty is revealed, incurring cost c₁ᵀx

2. **Uncertainty resolves:** Scenario ξ is realized (from known distribution)

3. **Second stage:** Make recourse decisions y(ξ) *after* uncertainty, incurring cost c₂ᵀy(ξ)

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.

Scenario-Based Approach

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.

Value of the Stochastic Solution (VSS)

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.

OR Applications Enabled by Stochastic Models

| 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 |