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

Forum topic · 小凯 · 2026-09-03

Summary

This arXiv paper (2509.00003) by Léa Bayati, Mohamed Dahmoune, and Melek Rodoplu studies a finite-horizon multi-item capacitated lot-sizing problem where demand quantities are deterministic but demand-arrival periods are stochastic. Each demand occurs once within a known time window and must be met 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, and formulates the stochastic problem as a discrete-time Markov decision process (DTMDP) with full state space, feasible actions, transition kernel, and one-period cost. Comparisons with deterministic counterparts show that stochastic timing substantially increases state counts, transitions, solve time, and memory pressure. A genetic algorithm (GA) searches over feasible state-feedback policies and evaluates each exactly under the DTMDP transitions. Experiments on 330 benchmark instances show GA achieves an average optimality gap of about 3.44% versus exact solutions, stays below a 5% gap on hard cases, and delivers a 6.89±1.41x speedup at 95% confidence.

This post introduces the arXiv paper 2509.00003, *Discrete-Time MDP Modeling for Multi-Item Capacitated Lot Sizing with Stochastic Demand Arrival*, by Léa Bayati, Mohamed Dahmoune, and Melek Rodoplu.

Problem and Model

The 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.

Production and allocation decisions are made at the demand level, enabling representation of 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.

Computational Impact of Stochastic Timing

To isolate the computational effect of stochastic timing, each stochastic instance is 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.

Genetic Algorithm Approach

The authors propose a genetic algorithm (GA) that searches over the space of feasible state-feedback policies and evaluates each policy exactly under the DTMDP transition model.

Experimental Results

Across 330 benchmark instances, GA consistently approaches exact solutions where available, with an average optimality gap of about 3.44%.
On hard benchmark cases (90 test cases), GA stays below a 5% optimality gap threshold and achieves an average speedup of 6.89±1.41x at 95% confidence.
For instances intractable on the available hardware, empirical Bellman-time regression is used to estimate missing exact solve times and infer GA's expected speedup.

*Auto-collected on 2026-09-03.*