Discrete-Time MDP Modeling for Multi-Item Capacitated Lot Sizing with Stochastic Demand Timing

Forum topic · 小凯 · 2026-09-03

Summary

This paper studies a finite-horizon multi-item capacitated lot-sizing problem in which demand quantities are deterministic but demand-arrival periods are stochastic. Each demand occurs once within a known time window and must be satisfied by its deadline. The model makes production and allocation decisions at the demand level, capturing capacity competition, demand-specific backlog, and allocation-dependent inventory dynamics. The stochastic problem is formulated as a discrete-time Markov decision process (DTMDP) with an explicit state space, feasible actions, transition kernel, and one-period cost function. Comparisons against deterministic counterparts (replacing each arrival distribution with its most likely arrival period) show that stochastic timing significantly increases state counts, transitions, solve times, and memory pressure. The authors propose a genetic algorithm (GA) that searches over feasible state-feedback policies and evaluates each exactly under the DTMDP transition model. Experiments on 330 benchmark instances show GA consistently near exact solutions, with an average optimality gap of about 3.44%. On 90 hard instances, GA stays within a 5% optimality gap and achieves a mean 6.89±1.41x speedup at 95% confidence. For instances unsolvable exactly on available hardware, empirical Bellman-time regression estimates missing exact solve times and infers GA's expected speedup. arXiv:2509.00003.

Overview

Research area: Machine Learning / Operations Research Authors: Léa Bayati, Mohamed Dahmoune, Melek Rodoplu Published: 2026-09-03 arXiv: 2509.00003

Abstract (translated)

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.

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 times, and memory pressure.

A genetic algorithm (GA) is then 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.

Key Results

Computational experiments on 330 benchmark instances show that GA is consistently close to exact stochastic solutions when available, with an average optimality gap of about 3.44%.
On hard benchmark instances (90 test cases), GA remains below a 5% optimality gap threshold and achieves a mean 6.89±1.41x optimization speedup at 95% confidence.
For instances that cannot be solved exactly on the available hardware, an empirical Bellman-time regression is used to estimate missing exact solve times and infer GA's expected speedup.

---

*Source: arXiv:2509.00003*