Paper Overview
Field: ML Authors: Léa Bayati, Mohamed Dahmoune, Melek Rodoplu Published: 2026-09-03 arXiv: 2509.00003
Summary
This paper studies a finite-horizon multi-item capacitated lot-sizing problem in which demand quantities are deterministic, while demand-arrival periods are stochastic. Each demand occurs once within a known time window and must be satisfied no later than its deadline.
The proposed model makes production and allocation decisions at the demand level, allowing it to represent capacity competition, demand-specific backlog, and allocation-dependent inventory dynamics.
Methodology
- The stochastic problem is formulated as a discrete-time Markov decision process (DTMDP), including the state space, feasible actions, transition kernel, and one-period cost function.
- To isolate the computational effect of stochastic timing, each stochastic instance is first compared with a deterministic counterpart in which each arrival distribution is replaced by its most likely arrival period.
- This comparison shows that stochastic timing significantly increases the number of states, transitions, solve time, and memory pressure.
- A genetic algorithm (GA) is proposed for the stochastic-timing problem. The GA searches within the space of feasible state-feedback policies and evaluates each policy exactly under the DTMDP transition model.
- On 330 benchmark instances, the GA consistently stays close to the exact stochastic solution when available, with an average optimality gap of about 3.44%.
- On the hard benchmark subset (90 test cases), the GA remains below the 5% optimality-gap threshold and achieves an average speedup of 6.89±1.41x at a 95% confidence level.
- For instances that cannot be solved exactly on the available hardware, empirical Bellman-time regression is used to estimate the missing exact solve times and infer the GA's expected speedup.