Asymptotic Optimality of Constant-Order Policies for Lost Sales Inventory Models with Large Lead Times

David A. Goldberg, Dmitriy A. Katz-Rogozhnikov, Yingdong Lu, Mayank Sharma, Mark S. Squillante

Abstract

Lost sales inventory models with large lead times, which arise in many practical settings, are notoriously difficult to optimize due to the curse of dimensionality. In this paper we show that when lead times are large, a very simple constant-order policy, first studied by Reiman (2004), performs nearly optimally. The main insight of our work is that when the lead time is very large, such a significant amount of randomness is injected into the system between when an order for more inventory is placed and when that order is received, that "being smart" algorithmically provides almost no benefit. Our main proof technique combines a novel coupling for suprema of random walks with arguments from queueing theory.

Introduction

In the world of supply chain management, inventory models are generally categorized into two types: backorder models and lost sales models. In backorder models, unfilled demand is eventually satisfied when new stock arrives. These models are well-understood, and simple "order-up-to" policies are often optimal.

In contrast, lost sales models—where unfilled demand is simply gone forever—are a mathematical nightmare. The difficulty arises from the lead time ($L$), the delay between placing an order and receiving it. In a lost sales environment, the optimal decision at any given moment depends on the status of every single order currently in the pipeline. This creates a "curse of dimensionality": as the lead time increases, the state space an algorithm must track grows exponentially. For instance, a lead time of just four or five periods can render standard dynamic programming computationally infeasible. This paper investigates whether a radically simpler approach can suffice when delays are significant.

The Constant-Order Policy

Rather than attempting to solve the complex state-dependent optimization problem, the authors analyze a "constant-order" policy. This is an open-loop strategy where the manager orders a fixed amount $r$ every single period, regardless of current inventory levels or pipeline status.

While this approach seems counter-intuitive—ignoring real-time data is usually considered poor management—the authors prove that as lead times grow, this simplicity becomes an asset.

Methodology and Theoretical Framework

The research employs a sophisticated blend of queueing theory and probability theory to establish the performance of constant-order policies.

1. The GI/D/1 Queue Analogy

A key observation in the paper is that if a manager orders a constant amount $r$ every period, the inventory level behaves mathematically like the waiting time in a standard GI/D/1 queueing system. This allows the authors to leverage decades of established queueing theory to analyze expected costs.

2. Randomness Injection

The core philosophical insight of the paper is the "Randomness Injection" effect. When the lead time $L$ is very large, a massive amount of stochastic demand occurs between the time an order is placed and the time it arrives. This accumulated randomness effectively "washes out" the benefits of making precise, state-dependent decisions. In essence, the future becomes so unpredictable that the specific state of the system at the time of ordering provides almost no actionable information.

3. Mathematical Proofs

To formalize this, the authors utilize:

  • Novel Coupling: A technique for comparing the suprema of random walks to show that the difference between the optimal policy and the constant-order policy shrinks relative to the total cost.
  • Stein’s Method: A version of the Central Limit Theorem used to bound costs when the order quantity is very close to the average demand, ensuring the system remains stable.
  • Stability Gap: The authors demonstrate that the optimal constant order amount $z$ must be strictly less than the average demand to prevent the inventory "queue" from drifting toward infinity.

Key Results

The paper’s primary contribution is the proof of Asymptotic Optimality:

  • Theorem 1: For any $\epsilon > 0$, there exists a lead time $L$ such that the best constant-order policy incurs an expected cost at most $(1 + \epsilon)$ times the cost of the true optimal policy.
  • Convergence: As $L \to \infty$, the ratio of the constant-order policy cost to the optimal policy cost converges to 1.

Furthermore, the paper provides explicit formulas for calculating how large $L$ must be to achieve a specific performance threshold. While these theoretical bounds are conservative, they provide a rigorous foundation for why simple heuristics have been observed to perform well in practical simulations even with relatively small lead times ($L=4$ or $5$).

Implications and Limitations

This research suggests that for systems with significant delays—such as international shipping or complex manufacturing—complex algorithmic optimization may be unnecessary. A consistent, simple ordering rule can achieve near-optimal results.

However, some limitations remain:

  • Small Lead Times: For very short lead times (e.g., $L=1$ or $2$), constant-order policies are not optimal, and traditional dynamic programming is still required.
  • Demand Assumptions: The current proof assumes independent and identically distributed (i.i.d.) demand. Future research is needed to see if these results hold for correlated demand or non-stationary environments.
  • Hybrid Approaches: The findings point toward the potential for hybrid algorithms that use complex optimization for short-term delays and transition to simple, constant-order rules as lead times increase.

By proving that simplicity is asymptotically optimal, this paper provides a powerful theoretical justification for streamlined inventory management in the face of the curse of dimensionality.

Summary updated

Abstract

Lost sales inventory models with large lead times, which arise in many practical settings, are notoriously difficult to optimize due to the curse of dimensionality. In this paper we show that when lead times are large, a very simple constant-order policy, first studied by Reiman (\cite{Reiman04}), performs nearly optimally. The main insight of our work is that when the lead time is very large, such a significant amount of randomness is injected into the system between when an order for more inventory is placed and when that order is received, that "being smart" algorithmically provides almost no benefit. Our main proof technique combines a novel coupling for suprema of random walks with arguments from queueing theory.
BibTeX
@article{goldberg2016asymptotic,
  author = {David A. Goldberg and Dmitriy A. Katz-Rogozhnikov and Yingdong Lu and Mayank Sharma and Mark S. Squillante},
  title = {{Asymptotic Optimality of Constant-Order Policies for Lost Sales Inventory Models with Large Lead Times}},
  journal = {Math. Oper. Res.},
  year = {2016},
  doi = {10.1287/moor.2015.0760},
}
Figure