The stochastic lot-sizing problem with quantity discounts

Wen Jiao, Ju-Liang Zhang, Hong YanComput. Oper. Res 2017 · DOI

TL;DR

This paper tackles the complex challenge of determining optimal order quantities in a dynamic inventory system where demand is uncertain and suppliers offer all-unit quantity discounts. The authors develop a novel polynomial-time algorithm that efficiently solves this problem, offering significant improvements for businesses managing inventory under these common, yet challenging, conditions.

What Problem Does This Paper Address?

Businesses often face the dilemma of how much to order at a given time to minimize costs, especially when demand is unpredictable and suppliers incentivize larger orders through price breaks. The "economic lot-sizing problem" (ELS) is a classic operations research problem that aims to find the optimal production or purchase plan over a planning horizon to satisfy all demands at minimal cost. However, traditional ELS models often assume deterministic demand and no price variations.

This paper specifically addresses the stochastic economic lot-sizing problem (SELS) with all-unit quantity discounts. This means:

  • Stochastic Demand: Demand in each period is not fixed but follows a probability distribution.
  • Finite Periods: The planning horizon is limited to a specific number of periods.
  • All-Unit Quantity Discounts: If an order quantity exceeds a certain threshold, the price per unit for all units in that order is reduced. This is a common pricing strategy in many industries.
  • Fixed Ordering Cost: There's a cost associated with placing an order, regardless of its size.
  • Holding Cost: Storing excess inventory incurs a cost.
  • Zero Lead Time: Orders are delivered immediately upon placement.

The core challenge is to balance the cost savings from quantity discounts against the increased holding costs of larger inventory, all while accounting for uncertain future demand. Existing research has tackled aspects of this problem, but integrating both stochasticity and all-unit quantity discounts into an efficient solution has remained a significant hurdle.

Methods

The authors leverage a scenario tree to model the stochastic nature of demand and costs over time. This is a standard technique in stochastic optimization, where each node in the tree represents a possible state (demand and cost realization) at a specific point in time. The problem is then solved using dynamic programming, working backward from the end of the planning horizon.

Key methodological contributions include:

  • Characterizing Optimal Policy Properties: The paper proves that an optimal ordering policy exists where, if an order is placed, it's either for a specific discount quantity or to meet demand up to a certain future point. This simplifies the decision space.
  • Developing a Polynomial-Time Algorithm: Based on the identified policy properties, they design an algorithm that computes the optimal solution efficiently. The algorithm's complexity is O(n³) for a single discount level and O(n log²(m+1)+2) for m discount levels, where 'n' is the number of nodes in the scenario tree. This is a significant improvement over potentially exponential-time brute-force approaches.
  • Handling Backlogging and Multiple Discount Levels: The framework is extended to scenarios where unmet demand can be backlogged (incurring a penalty cost) and where multiple discount tiers exist.

Datasets

Not discussed in the paper. The paper focuses on developing a theoretical model and algorithm, with numerical experiments conducted on randomly generated instances.

Key Insights and Ideas

  • The "Sweet Spot" of Ordering: The paper demonstrates that optimal ordering decisions in this complex environment tend to fall into specific, predictable patterns: either ordering exactly at a discount threshold or ordering to meet a specific future demand point. This significantly prunes the search space for optimal solutions.
  • The Power of Scenario Trees: Using scenario trees effectively captures the uncertainty of future demand, allowing for a more realistic and robust inventory management strategy than deterministic models.
  • Algorithmic Efficiency is Key: The development of a polynomial-time algorithm is crucial. Without it, solving this problem for even moderately sized planning horizons and scenario trees would be computationally intractable.
  • Discount Structure Matters: The specific structure of all-unit discounts, while common, introduces unique complexities that require tailored algorithmic approaches compared to simpler pricing models.

Key Results

  • Optimal Policy Characterization: The paper proves the existence of a simple optimal policy structure for the stochastic lot-sizing problem with all-unit quantity discounts.
  • Efficient Algorithm: A polynomial-time dynamic programming algorithm is developed.
  • For a single discount level, the complexity is O(n³).
  • For 'm' discount levels with backlogging, the complexity is O(n log²(m+1)+2).
  • Numerical Validation: Experiments on randomly generated instances show that the algorithm is efficient. The number of nodes in the scenario tree ('n') has the most significant impact on runtime, followed by the number of periods ('T') and then the branching factor ('β'). The number of discount levels ('m') has the least impact, which is a notable finding.

Limitations and Future Work

The authors acknowledge several simplifying assumptions made in this study:

  • All-Unit Quantity Discounts: The model specifically addresses all-unit discounts, not incremental discounts.
  • Single Product: The model is for a single product.
  • No Capacity Limit: The model assumes unlimited production or ordering capacity.
  • Zero Lead Time: Orders are assumed to be delivered instantaneously.

Future work suggested by the authors includes:

  • Incremental Discounts: Extending the model to handle incremental quantity discounts.
  • Ordering Capacity: Incorporating capacity constraints into the model.
  • Multiple Products: Developing solutions for multi-product inventory systems.
  • Time Windows: Considering demand with specific time windows.
  • Non-Zero Lead Times: Addressing scenarios where there is a delay between placing an order and receiving it.

Summary updated

BibTeX
@article{jiao2017stochastic,
  author = {Wen Jiao and Ju-Liang Zhang and Hong Yan},
  title = {{The stochastic lot-sizing problem with quantity discounts}},
  journal = {Comput. Oper. Res.},
  year = {2017},
  doi = {10.1016/j.cor.2016.11.014},
}
Figure