Grid theory shows when dynamic lot sizing can be solved quickly
Grid Theory and Polynomiality in Dynamic Lot-Sizing
Discrete MathematicsData Structures and Algorithms
Summary
Dynamic lot-sizing involves planning how much of a product to make over time while meeting limits on production amounts. The authors introduce a framework called Grid Theory that identifies patterns in these production limits that let the problem be solved efficiently. They show that when these limits have a certain additive structure, the problem can be broken down into simpler parts, enabling fast algorithms. This advances understanding of which lot-sizing problems are easy or hard to solve.
What this means in practice
- •For manufacturing planners: Design scheduling algorithms for production with changing capacity and order size limits that run efficiently due to identified additive structures.
- •For supply chain software developers: Build optimization tools that handle complex production constraints like periodic or polynomial capacities with guaranteed fast runtimes.
A theory result. No direct application yet.
Authors
El-Mehdi Mehiri, Nabil Absi, Elodie Suzanne
Abstract
Why are some dynamic lot-sizing problems polynomial? We address this question by introducing Grid Theory, a structural framework based on cumulative production and the additive structure of production bounds. For a general single-item dynamic lot-sizing model with lower and upper production bounds, there exists an optimal extreme solution in which, within each regeneration interval, all but at most one production quantity lie on a boundary value. This induces additive grids, and the Main Grid Theorem establishes that an optimal cumulative production trajectory can be restricted to these discrete sets. Although the resulting grids may be exponentially large, we introduce the notion of additive dimension to capture production-bound profiles whose boundary sums admit a low-dimensional representation. We show that bounded additive dimension yields a polynomially constructible grid envelope and a polynomial time grid-based dynamic programming algorithm. The framework extends to separable concave costs and establishes polynomial solvability of several families, including constant capacities, minimum order quantities, a fixed number of capacity levels, fixed-degree polynomial capacities, periodic capacities, and piecewise polynomial capacities. In particular, polynomiality may hold even when the number of distinct capacity values grows with the planning horizon. Grid Theory thus identifies additive structure, rather than the number of distinct resource values, as a sufficient mechanism for polynomial solvability.