PaperlayerView exact revision on arXiv

Source-linked AI summary

Supply Chain Analytics: A Data-Driven Approach

Elioth Sanabria

arXiv:2609.10563v1math.OCcs.LGstat.ML

TL;DR

Estimating future demand is a supply-chain task for which historical observations may be limited. The text models demand probabilistically, presents data-driven strategies for balancing operational trade-offs, and concludes that the Bullwhip effect is an inherent network property even with perfect information and instantaneous ordering.

  • Problem

    Estimating future demand is a common supply-chain task, but historical observations may be limited.

    Source: §1.1 · p. 5, §1.4 · p. 13

  • Method

    The text models demand as a nonnegative random variable to represent uncertainty in demand estimation.

    Source: §1.2 · p. 5

  • Results

    The Bullwhip effect is an unavoidable, inherent topological property of supply-chain networks, even with perfect information and instantaneous ordering.

    Source: §6.2.2 · p. 77

  • Takeaways & Limitations

    Facility- and store-level decisions involve inherent trade-offs that the text presents strategies to balance optimally using data.

    Source: §2.1 · p. 21

    The inherent combinatorial nature of the problem is identified as an ultimate bottleneck.

    Source: §5.3.1 · p. 66

Abstract

from arXiv · show

Modern supply chain networks increasingly rely on real-time data to navigate structural uncertainties, market volatility, and operational disruptions. This manuscript bridges the gap between statistical data-driven learning and robust decision-making frameworks in logistics and operations management. We present a comprehensive, mathematically rigorous treatment of supply chain analytics, moving from empirical demand forecasting to optimal inventory and network control under uncertainty. Key topics explored include sample minimization, dynamic programming recursions for time-varying inventory replenishment, network fulfillment frameworks, and advanced distributionally robust optimization (DRO) via transport theory to hedge against rare events. By integrating predictive statistical models with prescriptive control algorithms, such as column generation for vehicle routing and non-homogeneous queueing regimes, this text provides the foundational tools necessary for designing resilient, data-driven automated systems. It serves as both a theoretical blueprint and an algorithmic guide for researchers and practitioners operating at the intersection of machine learning, mathematical optimization, and applied probability.

Demand Estimation and Forecasting … 1.3 Demand Evolution over Time

This section develops probabilistic and forecasting tools for modeling future demand as an unknown quantity, describing and bounding risk, and using side information to predict it. It covers time-varying processes, seasonality, flexible forecasting functions, and finite-sample estimation of unknown demand distributions.

1.1 Introduction

  • Future demand is unknowable before realization, so the notes model it as a random variable for forecasting.The demand quantity is treated as a nonnegative count with outcomes described by a probability mass function.Source: §1.1 · p. 5

1.2 The Demand as a Random Variable

  • Demand is modeled as a nonnegative count with a probability mass function; its cumulative mass function gives probabilities up to a threshold.The cumulative mass function can also express interval probabilities by subtracting its values at the interval endpoints.Source: §1.2 · pp. 5–6

1.2.1 Useful Probability Calculations

  • The probability that demand exceeds 5 million is at most 1/402 = 0.06%; mean demand μD and standard deviation σD provide useful information without knowing the full outcome distribution.The probability that demand exceeds 2 million is less than 1/100 = 1%.Source: §1.2.1 · p. 7

1.2.2 Side Information

  • The best predictor of demand given side information X = x is the conditional expected demand, E[D | X = x].Demand may depend on variables such as economic conditions, interest rates, competitors’ prices, other products’ demand, and weather.Source: §1.2.2 · pp. 7–8
  • With hot days occurring 5% of the time, demand of 5 MW otherwise and 15 MW on hot days gives expected demand of 5.5 MW.Source: §1.2.2 · pp. 8–9

1.3 Demand Evolution over Time

  • Model demand as Dt because pooling observations across time can mislead when demand changes over time.Source: §1.3 · pp. 9–10
  • For the base demand process, expected demand converges to α/(1−β) only when |β| < 1; if |β| > 1, demand explodes over time.Source: §1.3 · p. 11
  • Simulations show mean-reverting demand around α/(1−β) for β = 0.7, non-stationary drift for β = 1, and steep growth for β = 1.15.Source: Figure 1.2 · p. 11, §1.3 · p. 11

1.3.1 Modeling Seasonality and Time-varying Factors

  • Seasonality and other time-varying factors can be represented by indicators or covariates ht in the model Dt+1 = Aht + βDt + Vt.Source: §1.3.1 · p. 12

1.3.2 Other Modeling Specifications

  • Forecasting can fit a function of current and past demand and related variables to predict future demand, with the conditional expectation as the squared-error optimum.Source: §1.3.2 · pp. 12–13
  • The demand distribution is generally unknown, so estimation must use a finite sample, and a model must capture the conditional expectation's shape.Source: §1.3.2 · p. 13

1.4 Demand Estimation in Practice

This section examines practical demand forecasting when historical data are limited and demand distributions are unknown or shifting, covering sample-based estimation and data-driven model fitting. It also discusses shorter estimation windows, out-of-sample backtesting, and forecast errors as tools for adapting and evaluating forecasts, while noting the limits of longer-horizon prediction.

1.4 Demand Estimation in Practice

  • With i.i.d. demand samples, the sample average converges to the true mean, while the Central Limit Theorem characterizes the randomness of the estimate.The Law of Large Numbers provides the convergence guarantee when samples have finite mean and variance.Source: §1.4 · p. 14
  • When demand’s standard deviation is 30% of its mean, at least 34.5 years of observations are needed for the sample average to estimate average demand within 10% at 95% confidence.Source: §1.4 · pp. 14–15
  • For a demand process whose mean grows without bound, differencing yields a process with normally distributed increments rather than a diverging sample mean.The example uses D_t+1 = D_t + c + σZ, for which the sample mean increases indefinitely; the differences have mean c and variance σ^2.Source: §1.4 · pp. 15–16

1.4.1 Data-driven Demand Estimation

  • Data-driven estimation proposes a functional form, calibrates its parameters, and evaluates its performance out of sample.The fitted function is intended to capture demand within a defined family of forms.Source: §1.4.1 · p. 16
  • The fitted predictor approximates demand’s conditional expectation, and its quality depends on both the functional form and the amount of historical data.The estimate is based on observed demand and prior demand information.Source: §1.4.1 · p. 16
  • Overly rich demand models can fit finite observations yet predict poorly when samples miss the conditional distribution’s geometry or demand shifts over time.The sample optimization can appear to have zero error even when future performance is arbitrarily poor.Source: §1.4.1 · p. 17
  • When distribution changes occur with small probability p and E(τ) = 1/p, using k < E(τ) recent observations is likely to reflect the current demand distribution.The passage gives probability (1 −p)^k ≈1 and notes that decaying observation weights are another approach.Source: §1.4.1 · p. 17
  • After a structural shock, the stale forecast fails to account for the change, while the updated model recalibrates and captures the new demand trajectory.Figure 1.4 shows both models tracking the same pre-shock parameters before diverging after the shock.Source: Figure 1.4 · p. 18, §1.4.1 · p. 18
  • Out-of-sample backtesting averages prediction errors to compare models and can be repeated across training-window sizes to select k.The mean absolute error is one stated comparison measure, and error measurements are made outside the model’s training data.Source: §1.4.1 · p. 18
  • The mean and variance of forecast errors can approximate prediction error and support confidence intervals for demand.The passage describes representing forecast error using its mean plus its standard deviation times a standard normal variable.Source: §1.4.1 · p. 19
  • Longer prediction horizons generally increase errors, error estimates are themselves random, and the approach implicitly assumes a stationary distribution that is not guaranteed.The passage cautions that prediction uncertainty cannot be eliminated and that real-world stationarity is not assured.Source: §1.4.1 · p. 19

Inventory Management Models · 2.1 Introduction · 2.2 The Newsvendor Model

This section examines inventory decisions through the Newsvendor model, balancing overprovisioning costs against congestion and lost sales while estimating demand uncertainty from empirical data. It develops sample-based profit bounds and convergence results, confidence intervals for optimal order quantities, and a pilot continuation test.

2.1 Introduction

  • Allocating too many fixed resources is costly and inefficient, while allocating too few causes congestion and lost sales; the chapter seeks data-driven strategies to balance these outcomes.Source: §2.1 · p. 21

2.2 The Newsvendor Model

  • The Newsvendor model chooses an order quantity for random horizon demand to maximize expected profit; its optimal quantity is predicted mean demand plus a buffer determined by the critical ratio.The critical point is optimal because the profit function is concave; the critical ratio is (p − c)/p.Source: §2.2 · pp. 21–23
  • When lifetime profit per customer ℓ is $2,000, the optimal avocado quantity rises to q*≈81.72.Source: §2.2 · p. 24

2.2.1 Empirical Distributions

  • Because true demand distributions are rarely known, the DKW bound gives a deviation probability below 2e^-2nλ^2, which decays with sample size and supports confidence intervals for the empirical CDF.Source: §2.2.1 · p. 24
  • A symmetric confidence interval γ ± ϵ for the CDF maps to a non-symmetric quantity interval [qL, qU] because the inverse CDF is nonlinear.The bound is not symmetric or centered at the empirical inverse CDF.Source: §2.2.1 · p. 25, Figure 2.2 · p. 25
  • p qhat/(2√n) bounds profit noise as sample size grows, independently of the demand distribution, enabling inference about true model performance.In the i.i.d. plain-vanilla Newsvendor, sample profit converges to true average profit.Source: §2.2.1 · p. 26
  • 1.96 p qhat/(2√n) gives a 95% interval around sample profit in the plain-vanilla Newsvendor model.The bound applies to i.i.d. demand; the passage says the technique extends to i.i.d. Newsvendor variations.Source: §2.2.1 · p. 26
  • The probability is P(Z < −1.56) = Φ(−1.56) = 5.9%, so under a 95% confidence one-sided test the pilot should continue because the probability is above 5%.Source: §2.2.1 · p. 26

2.3 Inventory Replenishment - The (s, S) rule

This section models and evaluates inventory replenishment under an (s, S) policy, using a Markov chain for i.i.d. demand and dynamic programming to optimize ordering under time-varying demand. It also describes an oxygen-concentrator example that uses humidity forecasts and conditional demand probabilities to account for inventory, shortage-fulfillment, and replenishment costs.

2.3 Inventory Replenishment - The (s, S) rule

  • Under the (s, S) rule, inventory at or below s triggers an instantaneous order restoring S; demand then reduces stock, and replenishment intervals vary with demand.The replenishment interval depends on the demand distribution.Source: §2.3 · p. 27
  • With i.i.d. demand, inventory is a Markov chain whose states may be negative; its long-run policy cost uses the limiting distribution, computed numerically from πP = π.The policy caps inventory at S by construction.Source: §2.3 · pp. 27–28
  • The replenishment cost model includes a fixed order cost, per-unit purchase cost, inventory holding cost, and lost net revenue when negative inventory represents unmet demand.Source: §2.3 · pp. 27–28

2.3.1 Finding the (s, S) values in the i.i.d. case

  • The straightforward i.i.d.-case optimizer enumerates candidate 0 ≤ s < S pairs, solves each policy’s stationary distribution, and compares costs; it is easy to implement but not most efficient.The procedure is presented as a computational routine for finding optimal policy parameters.Source: §2.3.1 · pp. 28, 30

2.3.2 The time-varying demand optimal inventory

  • For time-varying demand over horizon T, dynamic programming defines each action as a replenishment level j ≥ i and solves the one-step cost recursion backward from T.Demand distributions change from period to period, so inventory transitions are not time-homogeneous.Source: §2.3.2 · pp. 30–31
  • During peak periods, the dynamic-programming policy adjusts optimal s_t and S_t levels to minimize expected costs over horizon T.Source: §2.3.2 · p. 32
  • The oxygen-concentrator cost function represents holding costs, higher-cost external fulfillment when demand exceeds stock, and truck replenishment with fixed and unit costs and capacity limits.The example assumes overnight lead time and truck capacity L.Source: §2.3.2 · p. 32
  • When inventory is negative, unmet demand is not back-ordered but fulfilled at the higher external cost.Source: §2.3.2 · p. 32
  • The method incorporates humidity forecasts by modeling demand conditional on humidity and computing dynamic-programming expectations with conditional rather than unconditional probabilities.Source: §2.3.2 · pp. 32–33

Network Fulfilment Models · 3.1 Introduction · 3.2 Warehouse consolidation and positioning

This section develops warehouse fulfillment models that extend supply-chain analysis from matching demand over time to positioning and serving it across space under transportation delays and travel-time uncertainty. It covers graph-based, single- and multiple-location formulations that account for expected cost, cost variance, capacity, and risk trade-offs.

3.1 Introduction

  • The introduction frames supply-chain problems as transporting goods between producers and customers, with spatial matching adding time delays, and previews common problems and solution algorithms.Source: §3.1 · p. 35

3.2 Warehouse consolidation and positioning

  • Representing physical space as a graph enables tractable algorithms but sacrifices accuracy; adding route-specific nodes and edges or averaging travel times on an edge trades fidelity against tractability.Optimization algorithms generally scale with graph size.Source: §3.2 · p. 36
  • The warehouse-location model assigns each vertex a random demand, treated as static with i.i.d. daily realizations, and each edge a random vehicle travel time.Source: §3.2 · p. 37

3.2.1 Single Location Warehouse

  • The single-warehouse model enumerates candidate locations and selects the one minimizing expected total cost: warehouse overhead plus transportation costs to all demand nodes.The model treats location costs as random variables and uses expected value as a first approximation.Source: §3.2.1 · pp. 37–38
  • Expected-cost selection alone makes risk a conscious modeling choice, because a location with lower expected cost may have greater demand or travel-cost variation.The modeler may consider other distribution moments, such as variance, and should acknowledge the decision-maker’s risk aversion.Source: §3.2.1 · p. 37
  • The single-warehouse objective E(X)+λVar(X) is a principled risk adjustment, and λ can be calibrated using stakeholders’ certainty equivalents.A certainty equivalent is the amount a decision maker would pay or receive to be indifferent between a lottery and a certain payoff.Source: §3.2.1 · p. 39
  • In the single-warehouse model, λ > 0 penalizes cost variance caused by variability in both demand and transportation times.Source: §3.2.1 · p. 39

3.2.2 Multiple Location Warehouses

  • With M candidate sites, enumerating the 2^M possible subsets grows exponentially, making brute-force enumeration generally unsuitable beyond small instances.Source: §3.2.2 · p. 40
  • The expected-cost multi-warehouse MIP uses binary site choices, assignment flows, warehouse-capacity and demand-service constraints, and can be solved with off-the-shelf MIP solvers.Source: §3.2.2 · pp. 41–42
  • The risk-aware multi-warehouse formulation is an MIQP that combines a demand chance constraint with a variance penalty for travel-time cost fluctuations.Source: §3.2.2 · p. 42
  • The multiple-warehouse formulation uses variance rather than standard deviation and can be solved as an MIQP or MISOCP, assuming travel times and demands are independent.The formulation is also described as solvable with an MIQP solver.Source: §3.2.2 · pp. 42–43
  • The efficient frontier shows the trade-off between expected operational costs and cost variance; its green marker is risk-neutral (λ = 0), while the red marker indicates increasing risk aversion.The frontier considers different values of λ.Source: Figure 3.4 · p. 43, §3.2.2 · p. 43

3.3 Distributionally Robust Warehouse Location Optimization

This section addresses the unreliability of warehouse decisions under finite-sample uncertainty by using distributionally robust optimization to account for plausible demand distributions beyond the observed sample. It develops a tractable mixed-integer reformulation using Hoeffding bounds, Wasserstein-1 distance, and duality, with bounded shadow prices limiting sensitivity to demand uncertainty.

3.3 Distributionally Robust Warehouse Location Optimization

  • Errors in estimated demands and variances can compound, making the warehouse solution from sample observations substantially different from the true optimum.Source: §3.3 · p. 43
  • A 95% confidence bound from Hoeffding’s inequality shows sample-based optimization may underestimate true expected cost, and mitigating uncertainty from N locations requires at least quadratic growth in sample size.The bound is for the variable cost component when facility operating costs are known.Source: §3.3 · p. 45

3.3.1 A reformulation using duality and optimal transport

  • DRO optimizes over distributions within distance δ of the empirical distribution, with a larger radius expressing less trust in finite-sample estimates.The radius is chosen according to the decision-maker’s risk aversion.Source: §3.3.1 · pp. 45–46
  • Unlike the empirical approach, DRO can allocate resources to unobserved but plausible demand by spreading probability mass into gaps in the sample.Source: §3.3.1 · p. 46
  • The reformulation uses duality and optimal transport while treating delivery costs as known and fixed and allowing demand to vary.Source: §3.3.1 · p. 46
  • Using Wasserstein-1 distance, duality rewrites the worst-case expected warehouse cost in terms of the empirical demand distribution and the risk parameter λ.The resulting expression combines λδ with sample-wise worst-case terms, which are then incorporated into the warehouse objective.Source: §3.3.1 · p. 47
  • The reformulation is almost a mixed-integer program; auxiliary variables zij = ηixj and big-M constraints handle its remaining bilinear terms.The text specifies upper and lower big-M bounds for zij, with a sufficiently large M.Source: §3.3.1 · p. 48
  • The robust optimizer discounts demand shadow prices to [−λ, λ], capping the system’s sensitivity to demand uncertainty.The reformulation imposes −λ ≤ ηN ≤ λ.Source: §3.3.1 · p. 48

Scheduling Models · 4.1 Introduction · 4.2 A set covering problem

Scheduling is treated as an order-sensitive time-space matching problem, where poor fulfillment order can cause congestion, lost sales, and wasted resources. The section formulates scheduling as set covering and extends the framework to uncertain resource coverage.

4.1 Introduction

  • Poorly optimized fulfillment order can cause congestion, lost sales, and wasted resources; scheduling is framed as time-space matching, starting with space or discrete time before random time.The text reserves simultaneous treatment of space and random time for future chapters.Source: §4.1 · p. 49

4.2 A set covering problem

  • Many scheduling problems are combinatorial set-covering problems: choose resources or schedules to cover demand at minimum cost, with optimal solutions generally hard to find.Demand may extend over time or space; examples include assigning trucks to deliveries and workers to production tasks.Source: §4.2 · pp. 49–50
  • The model defines a demand vector of dimension N, J available schedules, and an N × J matrix A with a_ij = 1 when schedule j covers task i; x is a feasible-assignment decision vector.Source: §4.2 · p. 50
  • In the warehouse scheduling example, H workers are allocated among 24 possible consecutive 8-hour shifts, one starting each hour; a 24-by-24 matrix records which shifts cover each hour.Each worker processes b packages per hour.Source: §4.2 · p. 50
  • For the shift problem, minimizing the number of workers is an alternative objective, with constraints requiring expected demand to be covered at every hour.The objective is changed to |x|, the total worker count.Source: §4.2 · p. 51
  • With equal schedule costs or costs proportional to hours at the same rate, the cost-minimizing assignment matches the solution to the minimum-worker formulation.Source: §4.2 · p. 51

4.2.1 Data Uncertainty

  • To model uncertain resource coverage, the framework treats each row of A as a multivariate normal random variable and estimates its mean and covariance from samples.With demand modeled as an independent random variable, the coverage requirement becomes probabilistic, accounting for imperfect resource allocation.Source: §4.2.1 · p. 52
  • The resulting nonlinear probabilistic constraint is made tractable using second-order cone programming, allowing a MISOCP solver when the objective is affine.The quadratic variance term xΣ_i x⊺ motivates the SOCP reformulation.Source: §4.2.1 · p. 52

4.3 Production Scheduling · 4.4 A knapsack problem

For deterministic production scheduling, the sections model production decisions through interval costs and a shortest-path formulation. They also define the knapsack problem and present forward dynamic programming as a solution approach when greedy selection or direct mixed-integer optimization is inadequate.

4.3 Production Scheduling

  • For known demands over T periods, c(s,t) represents deterministic production and holding costs that satisfy demand exactly over the inclusive interval.The cost specification may vary, provided these costs are deterministic and computable.Source: §4.3 · p. 53
  • The production cost recursion is solved backward from c(T + 1) = 0, yielding the shortest path from node 0 to node T.The graph has nodes 0 through T and edges weighted by c(s,t).Source: §4.3 · pp. 53–54
  • The optimal production schedule is a shortest path whose visited nodes identify periods when production runs should occur.Figure 4.3 illustrates the network for T = 4, with edge weights representing setup, variable production, and holding costs.Source: §4.3 · p. 54, Figure 4.3 · p. 54

4.4 A knapsack problem

  • Greedy selection by the benefit-to-capacity ratio f_i(x_i)/c_i(x_i) may fail to find an optimal assortment.The problem is described as combinatorial and can represent choices such as jobs within limited time or investments under a budget.Source: §4.4 · pp. 54–55
  • The knapsack problem maximizes the benefit of selected object quantities or indicators subject to a total capacity limit.Each object i has benefit f_i(x_i) and consumes capacity c_i(x_i) ≥ 0.Source: §4.4 · pp. 54–55
  • A mixed-integer program can solve the knapsack problem directly, but this approach does not apply when the benefit function is nonlinear.The illustrated nonlinear profit has a step-down penalty when allocation crosses x_i = 3, after which marginal returns resume growth.Source: §4.4 · p. 55, Figure 4.4 · p. 55
  • Forward dynamic programming computes F_j(k) from the benefit of object j and the best value for the previous j − 1 objects at residual capacity, in O(CN|X|) operations when c_i is non-decreasing.The full-capacity solution is F_N(C).Source: §4.4 · p. 56
  • The forward-recursion state space uses decision stages as columns and remaining capacity as rows, with each cell evaluating the maximum over stage transitions.Figure 4.5 schematically shows this matrix representation.Source: Figure 4.5 · p. 57, §4.4 · p. 57

Vehicle Routing Problems · 5.1 Introduction · 5.2 The Traveling Salesman Problem

This section develops vehicle-routing approaches for allocating movement across time and space, using tractable heuristics to find feasible solutions and the traveling salesman problem to minimize tour travel cost. It also addresses TSP randomness and risk through the variance of aggregate random costs and on-the-fly addition of random subtour constraints.

5.1 Introduction

  • Vehicle routing jointly allocates time and space to match supply with demand, while heuristics seek feasible solutions in computationally tractable time.The chapter combines optimization in both domains and notes that exact optimization is very hard.Source: §5.1 · p. 59

5.2 The Traveling Salesman Problem

  • The TSP minimizes the travel cost of a tour through locations, with binary edge variables and one incoming and outgoing edge required at each node.The graph represents locations as vertices and travel costs as edge costs; the degree constraints alone may still permit disconnected subtours.Source: §5.2 · pp. 60–61
  • Adding subtour-elimination constraints produces an optimal valid tour, while modern solvers can add these constraints lazily as subtours emerge.The Dantzig-Fulkerson-Johnson formulation includes constraints for all possible subtours, an exponentially large set rarely implemented directly.Source: §5.2 · p. 62, Figure 5.3 · p. 62
  • When automatic constraint addition is unavailable, the procedure repeatedly solves the problem and adds constraints for invalid tours, and the text says it converges relatively quickly.Solvers can incorporate new constraints while retaining branch-and-bound-tree information.Source: §5.2 · p. 62

5.2.1 Incorporating Randomness and Risk Awareness

  • Random travel-time costs can make routes with lower expected times risky because of high variance, motivating mean-variance methods for risk-aware routing.The motivation includes avoiding potentially unacceptable long trips and meeting strict delivery windows.Source: §5.2.1 · p. 63
  • The formulation proceeds from the variance of a sum of random variables.Source: §5.2.1 · p. 63
  • The variance term is represented as xCov(c)x⊺, where x is the flattened decision vector and c is the corresponding cost vector.The text introduces this as the variance expression for a sum of random variables.Source: §5.2.1 · p. 63
  • Random subtour constraints can be added on the fly, as in Algorithm 3.Source: §5.2.1 · p. 64

5.3 The Vehicle Routing Problem

This section extends vehicle routing to multiple depot-based vehicles, describing constraint-based approaches to disconnected customer groups and capacity violations and the difficulty of incorporating time windows directly into route formulations. It then formulates time-window routing as selecting feasible tours that cover every location and uses column generation, with dual prices and dynamic programming, to generate and prune tours without enumerating the full route set.

5.3 The Vehicle Routing Problem

  • The VRP extends the single-salesman model to K routes departing from and returning to a depot, while visiting each customer once.Source: §5.3 · p. 64
  • Customer-only islands can satisfy the basic formulation without connecting to the depot; iterative subtour constraints eliminate them, using IsolatedCycles instead of DisjointCycles.Source: §5.3 · pp. 64–65

5.3.1 On Capacities and Similar Issues

  • The text contrasts monolithic “masochist” models, whose weak LP relaxations often fail beyond small instances, with lean “sadist” models that add constraints iteratively, though convergence iterations are uncertain.Source: §5.3.1 · pp. 65–66
  • For a customer subset whose expected demand exceeds capacity, lazy capacity constraints require at least ceil(sum_i∈sk E[Di]/C) vehicles to serve it until feasibility is reached.Source: §5.3.1 · pp. 66–67

5.3.2 Time-window constraints: Column generation

  • Time windows are difficult to encode because the route variables do not directly track time; adding constraints for violations mainly reorders tours and yields weak cuts.Source: §5.3.2 · p. 67
  • Selecting feasible tours that visit each location exactly once yields an optimal solution to the time-window routing problem.The formulation’s tour universe contains only routes that arrive within each location’s time window.Source: §5.3.2 · pp. 67–68
  • Because the feasible tour set is difficult to know in advance and has exponentially many columns, the method generates routes iteratively.It seeks feasible, lower-cost routes to add to the optimization problem.Source: §5.3.2 · p. 68
  • Dual shadow prices define route reduced costs: negative-reduced-cost routes are candidates for addition, and their absence certifies optimality within the considered routes.The linear relaxation’s coverage-constraint dual variables provide the prices used to evaluate candidate routes.Source: §5.3.2 · p. 68
  • A dynamic program generates candidate routes by minimizing reduced cost over node and arrival time, enforcing delivery windows and pruning routes that revisit a node less effectively.The recursion prunes non-improving tours; when windows are not tight, cycles may still arise and can be prevented by checking recent node visits.Source: §5.3.2 · pp. 68–69
  • The generated columns can be combined with capacity variation to obtain capacitated routing formulations.Source: §5.3.2 · p. 69

Chain Effects · 6.1 Introduction · 6.2 Basic Model

This section models risk propagation and bullwhip effects in supply-chain networks using capacity-constrained flows and network multipliers to characterize production limits and amplification. It explains how risk hedging can make bullwhip inherent even with perfect information and instantaneous fulfillment.

6.1 Introduction

  • The chapter quantifies risk propagation through supply-chain networks, including added propagation from lead times, using Stochastic Networks theory.Source: §6.1 · p. 71

6.2 Basic Model

  • Network capacity limits can leave some nodes unhedged against demand risk, creating a stockout risk even at the maximum feasible product flow.The basic model formulates maximum flow as a linear program with capacity constraints.Source: §6.2 · pp. 72–73

6.2.1 The bullwhip effect and other sensitivities

  • The bullwhip effect reflects not only demand increases but also network structure and external-demand variance, with the network multiplier matrix representing propagation through feedback loops.The analysis uses sensitivities of the solution to demand and volatility.Source: §6.2.1 · p. 74
  • Demand shocks travel along network paths, and their effects can be amplified at deeper nodes compared with directly affected nodes.The text describes the network multiplier as encoding effects across successive steps.Source: §6.2.1 · pp. 75–76

6.2.2 Volatility Propagation

  • A shock to external-demand standard deviation is amplified by both the network multiplier and a further variance multiplier, with sensitivity also proportional to current standard deviation.Source: §6.2.2 · pp. 76–77
  • Even with perfect information, coordination, and instantaneous order fulfillment, hedging against risk makes the Bullwhip effect an unavoidable topological property of supply-chain networks.Source: §6.2.2 · p. 77
  • Even in the two-node example, the producer must produce well above the seller node’s quantity to hedge optimally against demand fluctuations.Source: §6.2.2 · p. 77
  • In the two-node rare-earth example, increasing demand volatility by 1 ton increases producer production by 1.645 tons.Source: §6.2.2 · p. 78

6.3 Dynamic Model

The section extends the supply-chain model to track the timing and magnitude of Bullwhip and other shocks, while showing that its long-run equilibrium matches the static model. It describes inventory evolution through shortfall reflection and, with capacity limits, sequential changes in hedged and unhedged nodes.

6.3 Dynamic Model

  • To capture shock timing, the model enforces nonnegative inventory with a Skorokhod correction Y(t), which tracks shortfalls and their propagation across nodes.The correction increases when inventory reaches zero and remains unchanged when inventory is positive.Source: §6.3 · p. 78
  • At equilibrium, the unconstrained dynamic model gives λ = α(I − P)^−1 and converges to q*, matching the static production quantity.This equilibrium result is derived for the case where production capacities are large enough to allow any production level.Source: §6.3 · p. 79
  • With physical capacity limits, nodes are partitioned into hedged H and unhedged U sets; rising demand can shrink H, and flows are refined for those sets.When λ ∧ C = λ, the earlier flow equation still holds.Source: §6.3 · p. 79

6.3.1 Sequential dynamics

  • Between set changes, inventory evolves linearly from the initial state until time τ, when a hedged node cannot meet its production obligations and the system is simulated again.A hedged node with θ_j < 0 eventually reaches its production limit, even at maximum capacity.Source: §6.3.1 · pp. 79–80

Queueing Models · 7.1 Introduction · 7.2 A network view of a queueing system

This section develops queueing models that use networks and probability to analyze how operational order and configuration affect throughput. It introduces CTMCs for queue states, transitions, and equilibrium, then derives revenue and waiting-time relationships and extends the analysis to connected queues through flow symmetry and joint equilibrium distributions.

7.1 Introduction

  • Task order and system configuration affect production or warehouse throughput, making faster and more resilient system design strategically important.The chapter applies network and probabilistic theory to describe common queueing problems.Source: §7.1 · p. 81

7.2 A network view of a queueing system

  • A CTMC models queue size with transition probabilities between states and time-homogeneous state durations; memorylessness yields geometric discrete or exponential continuous sojourn times.The transition-rate matrix has q_ii = -μ_i and q_ij = p_ijμ_i, and the transition matrix is P(t) = e^(Qt).Source: §7.2 · pp. 81–82
  • The equilibrium distribution for a system with transitions p_ij and exponential state durations can be found by solving πQ = 0.For small Δt, P(Δt) ≈ I + QΔt, which leads to the equilibrium condition.Source: §7.2 · pp. 83–84
  • The strait example models ships as a queue with five inspection stations, two-hour average service per ship per station, and fee-dependent arrivals of e^-5p ships per hour.It frames questions about hourly revenue and ship time in the system under per-time or per-ship charging.Source: §7.2 · p. 84
  • Solving πQ = 0 gives the equilibrium distribution, from which expected revenue is calculated as p[0π0 + 1π1 + 2π2 + · · · ].The text identifies pE(N) as the system’s earnings rate.Source: §7.2 · p. 85
  • Little’s law states E(N) = E(a)E(W), allowing the average waiting time to be inferred from the arrival rate and average number in the system.The section also presents the equivalent revenue identity pE(N) = E(a)pE(W).Source: §7.2 · pp. 85–86
  • When arrivals remain below the maximum service rate, departures match arrivals, and the output process behaves like the input, enabling queues to be studied individually.The input is described as Poisson, with exponentially distributed interarrival times.Source: §7.2 · pp. 86–87
  • For queues in tandem or with fixed-probability routing, the joint equilibrium distribution factors into the product of each queue’s equilibrium distributions.The passage describes Poisson arrivals and gives π(N1, · · · , Nℓ) = π1(N1) × · · · × πℓ(Nℓ).Source: §7.2 · p. 87

7.3 Time-varying arrivals

This section examines how systems respond to time-varying arrivals modeled with piecewise-constant rates, analyzing both infinite- and finite-server systems. For finite-server systems, it describes how expected queue size shifts between linear and exponential regimes as load changes relative to capacity, illustrated by the World Cup ticket example.

7.3 Time-varying arrivals

  • Piecewise-constant arrival rates approximate a time-varying system within each interval, but rate changes can make the approximation inaccurate when processing is slow and work carries over.For example, daytime congestion may persist into the night shift; the approximation works better when processing is fast and the system is usually empty.Source: §7.3 · pp. 87–88

7.3.1 Time-varying arrivals with infinite servers

  • With infinite servers, a recursion combines surviving jobs from earlier periods with new arrivals, allowing expected system load to be estimated from N(0) and used to plan staffing.The recursion averages contributions across arrival periods and converges to Little’s Law as expected processing time approaches zero.Source: §7.3.1 · p. 90

7.3.2 Time-varying arrivals with finite servers

  • With k finite servers, systems starting at N(0) ≤ k decrease exponentially toward Little’s Law, while those starting above capacity change linearly at net rate r1 − kµ.If r1 > kµ, the queue grows; if r1 ≤ kµ, it decreases until the arrival rate changes or the system reaches k jobs.Source: §7.3.2 · pp. 90–91
  • When expected jobs exceed k, the system evolves linearly; at or below k, it follows an exponential regime, and changing arrival rates can switch between them.In the exponential regime, fewer than k servers are operating, so it is slower than the linear regime under the same arrival rate.Source: §7.3.2 · p. 91
  • With k = 3,000, the system enters the exponential regime around 9:10am, then enters the linear regime around 10:20am and grows at 2 thousand customers per hour.A separate equilibrium is approximately 3,333 customers, below k = 5,000.Source: §7.3.2 · p. 92
  • With k = 5,000, the system absorbs both demand periods below capacity, while k = 3,000 crosses capacity after 10am into unsustainable linear growth (Figure 7.4).The figure contrasts the two configurations’ transient behavior over three hours.Source: §7.3.2 · p. 93, Figure 7.4 · p. 93

Optimization of Queueing Systems · 8.1 Introduction · 8.2 Linear Allocation

Queueing-system resources must be allocated in line with business goals such as meeting demand within a prescribed time or sustaining service levels. The section develops a tractable linear-allocation approximation for staffing and operating costs, with extensions for approximation error and risk.

8.1 Introduction

  • Queueing resources such as staff, online capacity, or manufacturing stations should be matched to business goals, including timely demand fulfillment and sustained service levels.The introduction frames resource choice as an optimization problem tied to the system’s operating objective.Source: §8.1 · p. 95

8.2 Linear Allocation

  • The scheduling model links resource allocations to processing capacity, requiring demand stability and average waiting times below a specified maximum.The objective can represent payroll or a more elaborate cost measure.Source: §8.2 · p. 96
  • A car-wash operator can minimize payroll and operating costs while ensuring service capacity covers demand.The example models payroll as cx⊺ and imposes the queue-stability condition µAx⊺≥E(A).Source: §8.2 · p. 96
  • The car-wash model estimates expected customers in the system across staffing configurations and uses selection variables to linearize variable operating costs as a MIP.The estimate uses arrival rates and the approximated service rate for each period.Source: §8.2 · pp. 96–97
  • The formulation is tractable in one pass without repeated simulations, but its queueing approximation requires careful calibration.A single mega-server at rate kµ differs from k servers at rate µ when fewer than k jobs are present.Source: §8.2 · p. 97
  • Scaling a mega-server rate by η_k<1 can compensate for the speedup by reflecting that some original servers are idle when fewer than k jobs are present.One suggested η_k is the probability that all servers are active in the original M/M/k queue.Source: §8.2 · p. 97

8.2.1 Mean-variance optimization

  • A risk-aware extension adds a weighted variance of the number in the system to the objective, using known variance expressions such as the M/M/1 approximation.The multiplier λ controls the variance penalty.Source: §8.2.1 · pp. 97–98

8.3 Accuracy and non-exponential service times

The section uses time-discretized dynamic programming for server allocation with a waiting-time chance constraint, then presents QPLEX for estimating transitions with non-exponential service times. Non-exponential times make control harder because elapsed or remaining service must be tracked.

8.3 Accuracy and non-exponential service times

  • LLM providers face server-allocation problems for thousands of simultaneous requests and hundreds of thousands of concurrent requests needing reasonable time in system.Source: §8.3 · p. 98
  • The server-allocation procedure discretizes time and server-count actions, then applies a dynamic-programming recursion using transition f(N,k,rt) and expected arrival rate rt.The actions are k = 0, 1, . . . , K and the time-step size is Δt.Source: §8.3 · p. 99
  • For N > k, the model accounts for the N −k queued customers served at rate kµ before a customer's own service at rate µ, and prunes (N,k) pairs violating P(W > s) ≤ α.The waiting-time constraint is incorporated by pruning paths that violate it.Source: §8.3 · p. 99

8.3.1 Non-exponential service times

  • Non-exponential service times make control problems intractable because they are not memoryless, requiring elapsed or remaining service times to be tracked.The reliability function generally fails the time-homogeneity relation R(s)R(t) = R(s + t).Source: §8.3.1 · p. 100
  • QPLEX estimates remaining-service-time distribution νt and approximates next-step system-count and remaining-service distributions through conditioning.For example, expected departures are Ntνt(L = ∆t|Nt).Source: §8.3.1 · p. 100

Related papers

Loading 2609.10563v1…