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

Supply chain decisions must balance inherent trade-offs while accounting for demand uncertainty and volatility propagation. The paper develops data-driven strategies for these decisions and shows that the Bullwhip effect is an unavoidable topological property of supply chain networks.

  • Problem

    Supply chain decisions involve inherent trade-offs, while demand must be modeled as uncertain and nonnegative.

  • Method

    The paper uses data-driven strategies to balance supply chain trade-offs and models demand as a random variable.

  • Results

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

  • Takeaways & Limitations

    Supply chain network decisions should account for volatility propagation as an inherent network property.

  • Takeaways & Limitations

    The paper identifies the inherent combinatorial nature of supply chain decisions as an ultimate bottleneck.

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

The section develops demand forecasting from probabilistic foundations to time-dependent stochastic models, showing how side information, distributional bounds, and temporal structure improve demand estimation. It concludes that forecasting can target conditional expectations using flexible functions, while finite samples and unknown distributions limit estimation.

  • 1.1 Introduction: Demand is modeled as an unknowable future random variable, while realized demand is observed only after it occurs.The framework uses random variables to represent future demand and probability models to quantify possible outcomes.
  • 1.2 The Demand as a Random Variable: For nonnegative count demand, probability mass and cumulative mass functions support event probabilities, while mean and variance summarize typical levels and dispersion.The cumulative mass function gives P(D ≤ i), and interval probabilities can be computed from differences of cumulative values.
  • 1.2.1 Useful Probability Calculations: With only mean demand µD = 1 million units, Markov’s inequality bounds the probability of demand reaching 5 million at 20%, implying at least 80% probability below that threshold.The bound is loose because the actual exceedance probability could be exactly 0.
  • 1.2.1 Useful Probability Calculations: Knowing mean µD = 1 million and standard deviation σD = 100,000 units, Chebyshev’s inequality bounds demand outside 800,000–1,200,000 units at 25% and above 5 million at 0.06%.The same information also bounds demand exceeding 2 million at less than 1%.
  • 1.2.2 Side Information: Side information such as economic conditions, prices, related products, and weather improves estimation by conditioning demand on an observed variable X.Under squared-error loss, the best predictor given X = x is the conditional expectation of demand given X = x.
  • 1.2.2 Side Information: For the hydroelectric example, rare hot days with P(X = 1) = 5% and conditional demands of 5Mw and 15Mw produce average demand µD = 5.5Mw.The calculation uses E[D] = E[E[D|X]].
  • 1.3 Demand Evolution over Time: Time-dependent demand is represented as Dt because averaging without temporal information can mislead; the base model combines an intercept, lagged demand, and random variation.The time unit should match the decision context, and historical observations provide realized demand data for estimation.

1.4 Demand Estimation in Practice

Demand estimation is framed as approximating the conditional expectation from limited historical observations when the true demand distribution and relevant variables are unknown. The section develops reliability guarantees for i.i.d. sampling, shows why nonstationarity can invalidate naive averages, and proposes fitting and evaluating demand models out of sample.

  • Practical estimation challenge: The best possible demand prediction is the conditional expectation given information from relevant variables, but practice often provides limited observations and unknown or unobservable drivers.
  • Statistical guarantees: Under i.i.d. sampling with finite mean and variance, the Law of Large Numbers guarantees that the sample average converges to the true average demand, while the Central Limit Theorem quantifies its randomness.
  • Sample-size estimation: 34.5 years of observations are needed for the sample-average demand to be within 10% of the true mean with 95% confidence when σD = 30% of µD.The calculation uses the Central Limit Theorem under the stated demand-variability assumption.
  • Nonstationary demand: For a demand process with drift, the sample mean diverges as µD(t) → ∞, so differencing produces a stationary normal process with mean c and variance σ2.
  • Demand-model fitting: The practical modeling strategy proposes a functional form, calibrates its parameters by optimization, and evaluates it out of sample as an approximation to conditional expectation.Approximation quality depends on both the adequacy of the functional form and the historical sample size.

Inventory Management Models · 2.1 Introduction · 2.2 The Newsvendor Model

The section frames inventory management as balancing costly over-allocation against congestion and lost sales, then develops the Newsvendor model and data-driven guarantees for empirical demand distributions. It derives optimal provisioning from price, cost, demand uncertainty, and sample size, including confidence bounds for inventory and profit.

  • 2.1 Introduction: Inventory decisions balance costly excess resources against congestion and lost sales when fixed capacity, materials, or labor must serve random demand.The section presents data-driven strategies for optimizing this trade-off.
  • 2.2 The Newsvendor Model: The Newsvendor model chooses production or inventory quantity q at time 0 to maximize expected profit from meeting random demand D_T at horizon T.Revenue is p min(q, D_T), variable cost is qc, and fixed costs do not affect the quantity decision.
  • 2.2 The Newsvendor Model: The optimal Newsvendor quantity is the demand quantile associated with the critical ratio (p − c)/p, with concavity ensuring the critical point uniquely maximizes profit.The critical ratio represents the probability of meeting all demand in the model’s visual formulation.
  • 2.2 The Newsvendor Model: When demand is approximated as normal, optimal inventory equals predicted demand plus a standard-deviation buffer determined by the inverse normal cdf and the price–cost ratio.For p = 3c, the buffer is approximately 43% of σ above predicted demand.
  • 2.2 The Newsvendor Model: In the avocado example, raising lifetime profit per customer ℓ to $2,000 increases the optimal quantity to q∗≈81.72 avocados.The extended expected-profit formulation includes purchase, preparation, disposal, and lost-customer costs.

2.3 Inventory Replenishment - The (s, S) rule

This section formulates the (s, S) inventory policy as a stochastic process, derives its long-term cost, and extends optimization from i.i.d. demand to time-varying demand through dynamic programming.

  • The (s, S) rule: The (s, S) rule replenishes inventory instantaneously to S whenever end-of-period stock falls below s; otherwise, demand reduces inventory from its current level.Replenishment intervals are random and depend on demand; inventory can fall below zero but never exceeds S.
  • The (s, S) rule: With i.i.d. demand, the inventory process is a Markov Chain whose transition probabilities determine a limiting distribution and the long-term cost of the (s, S) rule.The stationary distribution is computed numerically by solving πP = π, with the state space bounded below using the maximum possible demand M.
  • The (s, S) rule: The model incorporates fixed replenishment cost K, per-unit ordering cost c, holding cost c_h, and lost-sales loss of net revenue p̃ when inventory is negative.These components are summarized by a state-dependent cost function c(i).
  • Finding optimal (s, S) policies: For i.i.d. demand, enumerating feasible (s, S) pairs and solving πP(s, S) = π provides an easy-to-implement optimization routine, although it is not the most efficient algorithm.The procedure evaluates the stationary distribution and cost for each candidate pair before returning the policy with minimum cost.
  • Time-varying demand: For time-varying demand, dynamic programming defines optimal expected cost recursively over inventory states and actions, adjusting s_t and S_t during peak periods to minimize expected cost over horizon T.The approach works backward from the terminal period because inventory trajectories are history-dependent and non-time-homogeneous.

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

The section shifts supply-chain analysis from matching demand over time to satisfying demand across physical space, where transportation delays and network structure matter. It develops graph-based warehouse-location models that balance cost, capacity, demand uncertainty, and risk while preserving computational tractability.

  • 3.1 Introduction: Network fulfilment models address spatial demand by moving goods between producers and customers while accounting for non-trivial transportation delays.The section also introduces algorithms and heuristics for common supply-chain problems in space.
  • 3.2 Warehouse consolidation and positioning: Warehouse-location problems represent physical space as graphs whose vertices denote locations and edges denote connections between them.Graph abstraction enables tractable algorithms but sacrifices some accuracy and resolution; routes can be represented explicitly or averaged on a single edge.
  • 3.2 Warehouse consolidation and positioning: The spatial model assigns each vertex random demand D_i and each edge random travel time T_ij, yielding a static, i.i.d. daily-demand formulation.These random quantities capture uncertainty in both customer requirements and vehicle travel times.
  • 3.2.1 Single Location Warehouse: Single-warehouse placement enumerates candidate locations and selects the minimum expected total cost, combining warehouse overhead with transport costs to demand nodes.The model can incorporate variance from demand and travel-time uncertainty when expected cost alone is insufficient.
  • 3.2.1 Single Location Warehouse: Risk-aware warehouse placement optimizes E(X)+λVar(X), making the risk-aversion parameter λ an explicit control over cost variability.The formulation penalizes variance caused by both random demand and random transportation times, and λ requires practical calibration.
  • 3.2.2 Multiple Location Warehouses: Multiple warehouses can reduce delivery costs, exploit economies of scale, or distribute logistical burden, but selecting among M locations creates 2^M possible subsets.The model therefore uses Mixed Integer Programming with binary location variables and flow variables linking selected warehouses to demand targets.
  • 3.2.2 Multiple Location Warehouses: The multi-location formulation enforces warehouse capacities and demand-service constraints, with chance constraints and MIQP or MISOCP extensions incorporating uncertainty and risk.The risk-aware formulation assumes travel times and demands are independent from each other and varies the objective through λ.
  • 3.2.2 Multiple Location Warehouses: The efficient frontier illustrates the trade-off between expected operational cost and cost variance, with λ = 0 representing risk neutrality and larger λ indicating increasing risk aversion.The plotted curve shows how location decisions change as the decision-maker places greater weight on reducing risk.

3.3 Distributionally Robust Warehouse Location Optimization

Finite-sample demand uncertainty can substantially alter warehouse-location solutions and cause sample-based optimization to underestimate true expected cost. Distributionally robust optimization addresses this by optimizing over distributions within a distance δ of the empirical distribution, allocating resources to plausible but unobserved demand.

  • Finite-sample sensitivity: Small changes in demand observations, expected values, and variances can compound across locations, making the sample-based warehouse solution substantially different from the true optimum.The section motivates robustness by highlighting sensitivity to limited or time-varying observations.
  • Finite-sample sensitivity: With 95% probability, Hoeffding’s inequality bounds the true expected cost around the sample estimate, showing that sample-based solutions likely underestimate cost and require at least quadratic growth in n as N increases.The bound treats delivery cost as a bounded function of the demand vector and exposes uncertainty driven by the number of geographical locations.
  • Distributionally robust formulation: DRO models the unknown true distribution P as lying within a distance-δ neighborhood of the empirical distribution P_n, with δ chosen according to risk aversion and confidence in the data.A larger δ reflects less trust in finite-sample estimates, whereas a smaller δ reflects greater confidence in the empirical distribution.
  • Fulfillment under distributional uncertainty: Unlike the empirical approach, DRO spreads probability mass to plausible demand gaps and forces positive allocations q_ij > 0 for unobserved but potentially critical regions.The empirical model can assign q_ij = 0 to regions absent from the sample, whereas DRO accounts for those regions through a broader distributional neighborhood.
  • Modeling assumptions: The proposed DRO treatment focuses on duality theory and optimal transport while varying demand uncertainty and assuming delivery costs c_ij are known and fixed.Historical demand is represented by the sample matrix D_n formed from n observed demand vectors.

Scheduling Models · 4.1 Introduction · 4.2 A set covering problem

The scheduling framework models fulfillment as a time-space matching problem, beginning with deterministic set covering and extending it to uncertain resource coverage. It captures combinatorial assignment challenges and converts probabilistic scheduling constraints into tractable conic programs.

  • 4.1 Introduction: Scheduling is treated as a time-space matching problem, beginning with spatial or discrete-time coverage before jointly modeling time and space.The framework addresses ordering decisions whose poor optimization can cause congestion, lost sales, and wasted resources.
  • 4.2 A set covering problem: Set covering represents demand across locations or time periods using available resources, but its combinatorial structure generally makes optimal solutions hard to find.Examples include assigning trucks to deliveries and workers to production tasks.
  • 4.2 A set covering problem: The basic formulation uses demand vector D, schedule matrix A, and feasible assignment vector x to choose schedules that cover structural space-time demand.A has dimensions N ×J, with aij = 1 when schedule j covers task i; x may be binary, such as X = {0, 1}J.
  • 4.2 A set covering problem: The same formulation can minimize worker count or schedule cost, with equal or hourly-proportional costs yielding the same optimum as minimizing |x|.Replacing the objective with |x| supports finding the minimum workforce that covers expected demand.
  • 4.2.1 Data Uncertainty: Data uncertainty is modeled by treating each coverage row ai as a multivariate normal variable, incorporating both resource-allocation and demand risk into probabilistic constraints.The framework covers productivity variation across shift hours and low-probability machine failures.
  • 4.2.1 Data Uncertainty: Because the resulting variance term xΣ_ix⊺ is nonlinear, the uncertain scheduling model is reformulated as a Second-order Cone Program and solved with a MISOCP solver when f(x) is affine.Cholesky decomposition supports the conic reformulation, whose feasible set is represented by the Lorentz cone.

4.3 Production Scheduling · 4.4 A knapsack problem

Production scheduling with known demand is reduced to a shortest-path problem whose optimal path identifies production periods, while the knapsack problem is solved through forward-recursion dynamic programming when greedy selection or direct mixed-integer optimization is inadequate. The knapsack recursion accommodates general benefits under non-decreasing capacity consumption with O(CN|X|) operations.

  • 4.3 Production Scheduling: Known-demand production scheduling defines deterministic interval costs c(s, t) that include production and holding costs while satisfying demand exactly.The cost specification may vary, provided all costs are deterministic and computable.
  • 4.3 Production Scheduling: The production recursion computes minimum future cost backward from c(T + 1) = 0, yielding a graph with nodes for periods and edges weighted by c(s, t).The formulation relies on the renewal structure after production decisions covering an interval are completed.
  • 4.3 Production Scheduling: The optimal production plan is a shortest path from nodes 0 to T, with visited nodes identifying periods when production runs occur.Edge weights represent setup, variable production, and holding costs over the corresponding periods.
  • 4.4 A knapsack problem: The knapsack problem maximizes object benefits under a capacity constraint, covering applications such as selecting jobs within limited time or investments within a budget.Each object has benefit f_i(x_i), consumes nonnegative capacity c_i(x_i), and uses a quantity or indicator x_i ∈ X.
  • 4.4 A knapsack problem: Greedy sorting by f_i(x_i)/c_i(x_i) need not produce an optimal assortment, and direct mixed-integer optimization is not applicable when f_i(x_i) is non-linear.Non-linear benefits can include threshold penalties that temporarily reduce total net profit when allocation crosses a threshold.
  • 4.4 A knapsack problem: Forward-recursion dynamic programming defines F_j(k) as the optimal benefit using the first j objects and capacity k, then relates it to predecessor states.The recurrence compares object j's benefit with the optimal benefit from the first j − 1 objects at residual capacity k − c_j(x_j).
  • 4.4 A knapsack problem: Under non-decreasing capacity c_i, the knapsack recursion fills F_j(k) forward with O(CN|X|) operations.The resulting state space uses stages for sequential decisions and rows for remaining subproblem capacity; each cell evaluates the best transition from the preceding stage.

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

The chapter formulates vehicle routing as simultaneous time–space supply-demand matching, emphasizing computational difficulty and tractable heuristics. It develops the TSP formulation, resolves subtours iteratively, and extends routing to stochastic, risk-aware travel costs.

  • 5.1 Introduction: Vehicle routing combines time and space allocation to match supply and demand, but these combinatorial problems are hard to solve optimally.The chapter therefore studies heuristics that produce feasible solutions in computationally tractable time while minimizing travel time and fulfilling demand.
  • 5.2 The Traveling Salesman Problem: The TSP finds a minimum-cost tour through all locations, using edge-selection variables and constraints that enforce one incoming and outgoing edge per node.The formulation represents locations as graph vertices, assigns travel costs c_i,j, and minimizes total tour cost.
  • 5.2 The Traveling Salesman Problem: The basic assignment constraints can produce disconnected subtours, so valid TSP solutions require additional constraints linking each subtour to nodes outside it.Figure 5.2 depicts two disconnected subtours satisfying the row- and column-sum constraints.
  • 5.2 The Traveling Salesman Problem: Because all subtour constraints are exponentially numerous, practical solvers add violated constraints lazily during optimization, while sequential re-solving converges relatively quickly.The Dantzig-Fulkerson-Johnson formulation adds constraints for every possible subtour, whereas modern solvers add them as they emerge.
  • 5.2 The Traveling Salesman Problem: Adding subtour-connectivity constraints transforms disconnected assignments into an optimal tour visiting all nodes, illustrated by the resulting single connected cycle.The required constraint is v_sX(1 − v_s)^⊺ ≥ 1; Figure 5.3 shows the connected-cycle solution.
  • 5.2.1 Incorporating Randomness and Risk Awareness: Stochastic routing models treat transportation time as a random cost and incorporate variance to hedge against unusually long travel times.This is motivated by strict delivery windows and risk-sensitive applications where a lower expected time may still have high variance.
  • 5.2.1 Incorporating Randomness and Risk Awareness: A mean-variance extension penalizes route-cost variance through covariance terms, while retaining subtour constraints that can be added dynamically.The variance term is expressed as xCov(c)x^⊺ for the flattened route vector x.

5.3 The Vehicle Routing Problem

The vehicle routing formulation extends the single-salesman problem to K depot-based routes while addressing disconnected customer islands through subtour elimination. Operational constraints such as vehicle capacities and delivery time windows motivate iterative feasibility enforcement rather than one oversized formulation.

  • Multi-vehicle formulation: The VRP adds depot node 0 and exactly K departures and returns while each customer is visited once, extending the single-resource routing formulation.The resulting network has N + 1 nodes, with the depot serving as the common origin and destination for all vehicles.
  • Modeling operational constraints: A single formulation combining capacities, time windows, and other constraints often has a weak linear-programming relaxation and tends to fail beyond small instances.The alternative starts with a lean formulation and adds constraints until feasibility and optimality are reached, although the required iterations are uncertain and combinatorial complexity remains the bottleneck.
  • Capacity constraints: Capacity violations occur when a vehicle’s assigned demand exceeds capacity; subset cuts enforce enough outgoing vehicles to cover cumulative demand, using lazy feasibility constraints.For node subset s_k, the minimum required vehicles is m(s_k)=⌈Σ_i∈s_k E[D_i]/C⌉, and CapacityUnfeasibility checks violating customer subsets.
  • Time-window constraints: Time-window constraints are difficult because route variables abstract away arrival times, and naive violations produce slow, weak cuts that mainly reorder tours.Deliveries such as perishables may require specified time slots, while the cited procedure ultimately ensures an optimal solution.

Chain Effects · 6.1 Introduction · 6.2 Basic Model

The chapter quantifies how demand risk, volatility, and lead times propagate through supply-chain networks. Its basic model combines Newsvendor hedging with network flow constraints and shows that capacity limits and topology amplify stockout and bullwhip risks.

  • 6.1 Introduction: The chapter studies quantitatively how risk propagates and bubbles up through supply-chain networks, including the effects of demand randomness and lead times.It formalizes these effects using stochastic network theory.
  • 6.2 Basic Model: The basic model formulates maximum product flow as a linear program using node capacities, external demand, routing proportions, and Newsvendor risk buffers.Under normally distributed demand, each node’s buffer depends on its demand standard deviation and critical-ratio factor z_i = Φ^-1(ρ_i).
  • 6.2 Basic Model: Some nodes are capacity-capped and therefore produce below the quantity needed to optimally hedge their Newsvendor risk, creating a non-negligible stockout chance.The remaining nodes produce the maximum quantity permitted by external demand and network structure.
  • 6.2.1 The bullwhip effect and other sensitivities: Demand increases and network structure jointly drive the Bullwhip effect, which also propagates external-demand variance toward more internal supply-chain nodes.Sensitivity analysis captures changes in both demand and volatility through network multipliers.
  • 6.2.1 The bullwhip effect and other sensitivities: The network multiplier matrix (I_H − P_H)^−1 represents how production requirements and risk feedback across nodes, with entries giving multipliers between nodes.For substochastic matrices, repeated feedback terms converge; deeper nodes can therefore experience amplified effects as shocks propagate through the network.
  • 6.2.2 Volatility Propagation: Variance propagation has a second multiplier, M_σ = (I − (P ⊙ P))^-1, which further amplifies shocks to external-demand standard deviations.The resulting shock is also proportional to the current standard deviation, accentuating volatility effects further.
  • 6.2.2 Volatility Propagation: Even with perfect information and instantaneous fulfillment, hedging against risk makes the Bullwhip effect unavoidable as an inherent topological property of supply-chain networks.The model attributes amplification to network structure rather than solely to poor information, coordination, forecasting, or lead times.
  • 6.2.2 Volatility Propagation: In a two-node rare-earth example, a 1-ton increase in demand volatility raises producer output by 1.645 tons under safety level z_1 = z_2 = 1.645.The producer must produce substantially above the seller’s quantity to remain optimally hedged against demand fluctuations.

6.3 Dynamic Model

The dynamic model captures the timing and magnitude of Bullwhip and other shocks through a Skorokhod formulation, while recovering the static equilibrium in the long term. Capacity limits create changing hedged and un-hedged node sets whose evolution is simulated piecewise linearly.

  • Dynamic Model: The model extends the network to a dynamic setting for analyzing the timing and magnitude of the Bullwhip effect and other shocks.
  • Dynamic Model: A Skorokhod construction enforces nonnegative inventories by adding boundary regulation, while the term Yj(t)pji tracks shortfall propagation between nodes.The process satisfies Z(t) = X(t) + Y(t)(I − P), with regulation active at zero inventory and inactive when inventory is positive.
  • Dynamic Model: In the long run, the dynamic model converges to the static production quantity, with limt→∞ λ(t) = q∗ and λ = α(I − P)^−1 when capacities are sufficient.The equilibrium condition is 0 = θ = C(I − P) − α, yielding C = λ and the effective production rates.
  • Dynamic Model: When nodes hit capacity limits, the network partitions into disjoint hedged and un-hedged sets that can change as demand increases.The system evolves linearly between set changes and restarts simulation when a node reaches a production limit or obligations can no longer be satisfied.

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

The chapter introduces queueing systems as probabilistic models of time-dependent operations and develops continuous-time Markov-chain tools for equilibrium analysis. It then applies these tools to throughput, revenue, waiting times, and interconnected queues.

  • 7.1 Introduction: Queueing models capture how task order, station configuration, and available workers affect throughput and resilience in production and warehouse operations.The chapter uses networks and probabilistic theory to describe common queueing problems.
  • 7.2 A network view of a queueing system: A queueing system tracks the number of jobs in a bounded system, represented as a stochastic process whose time-homogeneous distribution describes the proportion of time in each state.The state variable is N = 0, 1, 2, . . . and time-homogeneous systems support stationary-distribution analysis.
  • 7.2 A network view of a queueing system: Continuous Time Markov Chains model manufacturing processes using transition probabilities between states and time-homogeneous average sojourn times.The transition matrix P contains pij, the probability of moving from state i to state j.
  • 7.2 A network view of a queueing system: Time-homogeneity imposes the memoryless relation R(t)R(s) = R(t + s), yielding geometric waiting times in discrete time and exponential tails R(t) = e^−µt in continuous time.The same property makes the probability of leaving state i over a small interval approximately µi∆t.
  • 7.2 A network view of a queueing system: The generator matrix Q, with qii = −µi and qij = pijµi, gives the transition matrix P(t) = eQt and enables computation of the equilibrium distribution.Solving the equilibrium system yields the distribution for chains following pij and remaining in state i for exponential time Ti.
  • 7.2 A network view of a queueing system: In the five-station ship-inspection example, the birth-death model uses arrival rate e−5p and service rate min(i, 5)/2, with revenue pE(N) from its equilibrium distribution.The model defines states by the number of ships and solves πQ = 0 to obtain long-run revenue.
  • 7.2 A network view of a queueing system: Little’s law states E(N) = E(a)E(W), allowing expected waiting time to be inferred from the arrival rate and average number in the system.The derivation equates system revenue viewed through time-weighted occupancy and arriving ships’ turnaround times.

7.3 Time-varying arrivals

The section extends queueing analysis to time-varying arrivals by approximating rates as piecewise constant and deriving transient recursions for expected system inventory. It shows that capacity relative to arrival intensity determines whether queues drain, stabilize, or grow unsustainably.

  • Piecewise-constant approximation: Piecewise-constant arrival rates r0 and r1 approximate time-varying demand, with errors concentrated near rate changes and better accuracy when processing is fast.The approximation treats each interval as nearly homogeneous and is less reliable when slow processing leaves earlier jobs in the system.
  • Capacity regimes: When arrival rate r1 exceeds capacity kµ, the queue grows at rate (r1 − kµ)t; when r1 ≤ kµ, growth does not persist.The server cannot process jobs fast enough when r1 > kµ, whereas capacity can prevent continued accumulation when r1 ≤ kµ.
  • Capacity regimes: With k = 3000, the system transitions from linear draining to an 833-customer equilibrium, then enters unsustainable linear growth after the 10am surge.The alternating regimes arise when the surge crosses the capacity boundary.

Optimization of Queueing Systems · 8.1 Introduction · 8.2 Linear Allocation

The section frames queueing optimization as resource allocation governed by demand, service capacity, and business objectives. It develops a tractable linear allocation formulation, illustrates it with car-wash scheduling, and extends it to risk-aware mean-variance optimization.

  • 8.1 Introduction: Queueing optimization assigns resources such as staff, servers, or stations to meet demand and service-level targets while remaining economically justified.Applications include retail staffing, online server capacity, and manufacturing stations.
  • 8.2 Linear Allocation: A single-server approximation uses Little’s law to express expected waiting time through arrival rate and service rate, assuming stability requires E(a) < µ.The approximation is nearly linear in µ, enabling server rates to be linked to assigned resources x.
  • 8.2 Linear Allocation: The linear allocation model enforces demand below processing capacity and limits average waiting time to a prescribed maximum across service periods.The objective f(x) can represent payroll or a more elaborate operating measure.
  • 8.2 Linear Allocation: The car-wash example minimizes payroll and operating costs subject to satisfying demand, using µAx⊺ ≥ E(A) as the queue-stability constraint.Variable costs depend on the average number of customers in the system under each staffing configuration.
  • 8.2 Linear Allocation: Estimating queue occupancy over feasible values and selecting them with auxiliary variables yields a tractable MIP that avoids repeated simulation in a combinatorial staffing space.The formulation remains an approximation and requires linearizing the variable-cost component.
  • 8.2 Linear Allocation: Because one mega-server at rate kµ differs from k separate servers, the approximation slows the aggregate rate to kµη_k with η_k < 1 to reflect idle servers.A possible η_k is based on the probability that all servers are active in the original M/M/k queue.
  • 8.2.1 Mean-variance optimization: Risk-aware allocation adds λVark(N(t)) to the approximated queueing objective, using closed-form variance expressions such as the M/M/1 case.The multiplier λ controls the emphasis on variability.

8.3 Accuracy and non-exponential service times

The section extends queueing-based dynamic programming from exponential to non-exponential service times, where memorylessness fails and control becomes difficult. QPLEX estimates transition dynamics without full simulation or explosive state tracking, enabling the dynamic program to be reapplied.

  • Application scope: The framework targets high-volume computer services, including LLM providers allocating servers to keep hundreds of thousands of concurrent requests within reasonable system time.The optimization balances average operating cost against a low-probability service-time threshold.
  • Exponential service-time model: For exponential service times, the model uses a dynamic program over server counts and discretized time, with transitions driven by expected arrival rates and queueing dynamics.The loss function combines server cost c(k) and congestion cost γ(N), while the recursion iterates over k = 0, 1, …, K.
  • Service constraint: The service constraint P(W > s) ≤ α is enforced by pruning dynamic-programming paths whose queueing delay violates the threshold.When N > k, waiting time is derived from the N − k queued customers entering service at rate kµ, followed by the new customer’s service at rate µ.
  • Non-exponential service times: Non-exponential service times make control problems intractable because elapsed or remaining service times must be tracked when service is no longer memoryless.The reliability function generally lacks time-homogeneity, with R(s)R(t) ≠ R(s + t).
  • Non-exponential service times: QPLEX estimates remaining-service and system-size distributions, allowing dynamic programming for non-exponential service times without full simulation or explosive state spaces.It estimates the distribution ν_t of a randomly selected job’s remaining service time and the next-step system distribution p_t through conditioning.
Loading 2609.10563v1…