Single-item lot sizing problem under budgeted lead-time uncertainty
2026-06-15 • Data Structures and Algorithms
Data Structures and Algorithms
AI summaryⓘ
The authors study a problem where a company needs to decide how much of a product to make over time, knowing that delivery times can vary unpredictably within certain limits. They assume production orders cannot be split, and earlier orders must arrive before later ones. To handle uncertainty in delivery times, the authors use a method called the R* criterion, which helps create a range of production plans from optimistic to pessimistic scenarios. They also develop algorithms and mathematical models to find optimal plans efficiently, and show through tests that their approach offers more flexible planning options compared to traditional methods.
lot sizingbackorderinglead time uncertaintyrobust optimizationR* criterionbudgeted uncertaintyproduction planningmixed integer programmingorder crossovercomputational complexity
Authors
Romain Guillaume, Adam Kasperski, Szymon Wrobel, Pawel Zielinski
Abstract
In this paper, a single-item lot sizing problem with backordering is discussed. The time horizon is divided into planning periods, characterized by fixed and variable production costs, and future delivery periods with specified demands, where inventory holding and backordering costs may occur. For each planning period, a common nominal lead time is given. The true lead times can deviate to some extent from the nominal one, and their exact values are unknown at the planning step. We assume that lead times take only integer values and splitting production orders is not allowed. Furthermore, order crossovers are prohibited; thus, an order placed earlier cannot arrive after one placed later. A budgeted uncertainty set of possible lead-time scenarios is defined, where a budget allows us to control the amount of uncertainty of lead times. It is shown how to construct a family of production plans varying from the most optimistic (a best lead-time scenario occurs) to the most pessimistic (a worst lead-time scenario occurs). In order to compute these plans the R* criterion is applied which generalizes the conservative robust min-max criterion, commonly used in robust optimization. The computational complexity of the problem is investigated. Polynomial, pseudopolynomial time algorithms, and mixed integer programming formulations are proposed to solve the general problem and its special cases. The results of computational tests are provided that demonstrate that using the R* criterion can significantly enlarge the set of candidate production plans.