Lot sizing solved faster for piecewise-concave production costs
Monge matrix searching for lot sizing with piecewise-concave production costs
Data Structures and Algorithms
Summary
Managing production and inventory over time can get complicated when costs don't behave simply. This paper studies how to efficiently plan production in scenarios where costs curve in complex ways and include backlogs. The authors develop exact algorithms that use special mathematical structures called Monge matrices to speed up calculations. Their approach works well in tests and covers many realistic cost scenarios.
What this means in practice
- •For production planners: Plan production quantities more efficiently under complex cost structures including backlogs and stock limits.
- •For supply chain software developers: Enhance lot sizing modules in inventory management software to handle nonlinear production and holding costs faster and exactly.$Commercial implications: The algorithms enable faster and more accurate inventory optimization features appealing to manufacturers and retailers.
Authors
Kleitos Papadopoulos
Abstract
We study single-item lot sizing with piecewise-concave production and holding--backlog costs over $T$ periods. Production has $m$ common positive finite breakpoints, and stock costs and domains have $K$ common finite boundary levels. For fixed $m,K$, we give an exact deterministic algorithm using $\OmK(T^{m+2}α(T+2))$ arithmetic operations and a Las Vegas algorithm using $\OmK(T^{m+2})$ expected operations, where $α$ is the inverse Ackermann function. The algorithms retain nonlinear concave cost pieces and cover backlogging, common-grid stock limits, and explicit terminal-stock policies. A structural decomposition at stock boundary levels yields breakpoint-only prefix and suffix tables. Batching transitions by a designated production period produces implicit matrices that are Monge double staircases on each production piece. Established matrix searches, merged state orders, and backward evaluation provide the bounds. A simpler rectangle/SMAWK variant requires $\OmK(T^{m+2}\log(T+2))$ operations. On 300 no-backlogging benchmark cases, its objectives agree exactly with the predecessor dynamic program and an inventory-state oracle. Geometric-mean paired time ratios are \GeoUncap\ for uncapacitated cases and \GeoCap\ for capacitated cases, with ratios above one favoring matrix searching. A 640-case base-model validation suite and a separate 624-case generalized-model suite pass. The timing study does not benchmark the generalized models or the stronger staircase routines. All bounds assume exact arithmetic, constant-time cost queries, and explicit closed-domain concavity conditions.