MDP Models Optimize Lot Sizing with Stochastic Demand Timing

The research addresses a challenging problem in supply chain management: multi-item capacitated lot sizing, where the quantities of demand are known, but their exact arrival times are uncertain. This scenario, common in real-world production and inventory planning, requires making production and allocation decisions while accounting for capacity constraints and the stochastic nature of demand timing. The authors formulate this stochastic problem as a discrete-time Markov decision process (DTMDP), meticulously defining the state space, feasible actions, transition kernel, and cost function. A key finding from comparing stochastic instances with their deterministic counterparts (where demand arrivals are fixed to their most likely periods) is that stochastic timing significantly increases computational complexity, leading to more states, transitions, and higher memory and solution time requirements. To overcome these computational hurdles, a genetic algorithm (GA) is introduced. This GA searches for optimal state-feedback policies and evaluates them precisely using the DTMDP transition model. Computational experiments on 330 benchmark instances show that the GA consistently achieves solutions very close to the exact stochastic solutions, with an average optimality gap of approximately 3.44%. For particularly difficult instances, the GA maintains an optimality gap below 5% and offers a substantial speedup, making it a practical approach for complex, real-world lot-sizing problems.