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

Léa Bayati; Mohamed Dahmoune; Melek Rodoplu

Source-linked AI summary

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

Léa Bayati, Mohamed Dahmoune, Melek Rodoplu

arXiv:2609.00004v1Jul 5, 2026cs.AIcs.NEmath.OC

TL;DR

The paper addresses multi-item capacitated lot sizing with deterministic demand quantities but stochastic arrival timing, where demand-level allocation must adapt to observed arrivals. It formulates the problem as a DTMDP and evaluates a GA over feasible state-feedback policies, finding that the GA remains close to exact solutions while addressing larger instances constrained by exact-solver resources.

Problem
The paper studies how to model and solve capacitated lot sizing when demand quantities are fixed but their realization periods are uncertain and demands compete for capacity.
Method
The paper formulates a finite-horizon DTMDP and uses a GA that searches feasible state-feedback policies evaluated exactly under the DTMDP transition model.
Results
On difficult instances, the GA remains below the 5% optimality-gap threshold, while stochastic timing makes exact resolution substantially more computationally demanding than deterministic timing.
Takeaways & Limitations
The GA becomes increasingly useful as instance size and exact computational effort increase, while exact DTMDP resolution remains appropriate for small instances.
Takeaways & Limitations
Exact resolution cannot be completed for instances with more than 7 demands on the available 15 GB machine, preventing direct optimality-gap computation there.

Abstract

from arXiv · show

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 substantially increases the number of states, the number of transitions, solution time, and memory pressure. A genetic algorithm (GA) is then proposed for the stochastic-timing problem. The GA searches over feasible state-feedback policies and evaluates each policy exactly under the DTMDP transition model. Computational experiments on 330 benchmark instances show that the GA remains close to the exact stochastic solution whenever the latter is available, with an average optimality gap of about $3.44\%$. On the difficult benchmark instances, comprising 90 test cases, the GA remains below the $5\%$ optimality-gap threshold and achieves an average optimization speedup of $6.89 \pm 1.41$ at the $95\%$ confidence level. For instances that cannot be solved exactly on the available hardware, an empirical Bellman-time regression is used to estimate the missing exact resolution time and extrapolate the expected GA speedup.

1. Introduction

The paper extends capacitated lot sizing to stochastic demand timing by modeling demand-level adaptive decisions in a finite-horizon DTMDP, then uses a GA to search feasible state-feedback policies. It also compares stochastic timing with deterministic counterparts to isolate the resulting computational burden.

Motivation: Stochastic demand timing keeps quantities fixed while making each demand’s realization period probabilistic within a specified window.Each demand occurs once according to a discrete distribution and must be satisfied by the end of its window.
Problem setting: The multi-item capacitated model includes setup times, production and setup costs, holding costs, backlog costs, and limited production capacity.
Modeling challenge: Demand-level production and allocation decisions capture competition among simultaneous demands and their effects on backlog, feasibility, and inventory evolution.Aggregate product-level formulations cannot represent how allocating scarce units across demand objects changes future costs and deadline feasibility.
Methodological contributions: The paper formulates the problem as a finite-horizon DTMDP whose decisions adapt as demand arrivals are progressively observed.
Methodological contributions: The GA searches over feasible state-feedback policies and evaluates each candidate exactly under the DTMDP transition model.
Computational study: Deterministic counterparts replace each arrival distribution with its most likely arrival period to quantify the added difficulty of stochastic timing.

Demands as objects with stochastic timing.

Each demand is represented as a known quantity with an uncertain realization period, modeled by a timing distribution over a feasible window and constrained by its deadline.

Production allocated to demand i is prohibited after its deadline u_i, so the demand must be fully satisfied no later than that period.
Demand i has a deterministic quantity and a random arrival period within its feasible window [s_i, u_i].
A fixed arrival period is represented by a singleton window and a Dirac histogram, unifying deterministic and stochastic timing.

Why per-demand allocation is needed (simultaneous arrivals).

Per-demand allocation is needed because simultaneous demands for the same product may compete for insufficient inventory and production capacity, with allocation choices changing future costs.

When same-product demands arrive simultaneously, available inventory and current production may be insufficient to satisfy all demands.
Allocating scarce units across demand objects determines which demand is backlogged and for how long, thereby changing total cost.

Data parameters vs. company parameters.

Demand-timing inputs are specified per demand, whereas machine and cost parameters are company-specific and can be derived from operational records and policy targets.

Demand-timing information includes each demand’s quantity, timing window, and arrival probabilities.
Machine parameters are company-specific and can be defined from routing sheets and standard processing times.
Holding and backlog cost rates can reflect inventory carrying factors, service-level targets, or contract penalties.

4. Discrete-time MDP formulation

The paper formulates stochastic demand timing as a finite-horizon DTMDP following the standard (S, A, P, r) structure. Its step-by-step arrival process converts marginal timing probabilities into a period-by-period Markov model.

4. Discrete-time MDP formulation: The DTMDP follows the standard (S, A, P, r) structure for sequential decisions under stochastic demand arrivals.
4.1. Arrival process: step-by-step hazards: Marginal arrival probabilities cannot be applied directly at each period because prior arrival information is already known.
4.1. Arrival process: step-by-step hazards: Table 2 summarizes the DTMDP components used to represent the lot-sizing problem.
4.1. Arrival process: step-by-step hazards: Conditional arrival hazards convert each demand’s marginal arrival pmf into period-by-period transition probabilities.
4.1. Arrival process: step-by-step hazards: The resulting DTMC uses states (t, α), where t is the current period and α records whether the demand has arrived.

DTMC state encoding.

The model encodes arrival information, demand-level production allocations, and resource-dependent transitions in the DTMDP state and action structure. Costs capture setup, production, holding, and backlog consequences while deadline completion is enforced.

Arrival states: From an arrived state, the demand remains arrived; before arrival, the process either transitions to arrival or remains non-arrived according to its hazard.
Arrival states: The illustrative demand has window, hazards q1 = 0.15, q2 ≈ 0.294, and q3 = 1, preserving its marginal distribution.
State encoding: A state records the current period, each demand’s arrival flag, and cumulative production allocated to each demand.
State encoding: Inventory is derived without an explicit inventory state because production for an unarrived demand represents demand-dedicated pre-production.
Actions and transitions: Actions specify production quantities for each demand, subject to remaining demand quantities and feasibility constraints.
Actions and transitions: Transitions first update cumulative production deterministically, then update unarrived-demand flags stochastically using conditional arrival probabilities.
Costs and feasibility: The stage cost combines setup and production costs with holding costs for pre-arrival units and backlog costs for unmet arrived demand.
Costs and feasibility: Deadline feasibility requires each demand’s cumulative allocation to reach its quantity by its deadline, with production prohibited afterward.

5. Genetic algorithm heuristic

The GA searches over complete feasible state-feedback policies using the same DTMDP model as exact optimization. It evaluates policies deterministically by propagating state probabilities through the transition kernel.

5. Genetic algorithm heuristic: The GA addresses the growing explicit state–action representation by searching directly over feasible state-feedback policies.
Policy encoding: Each chromosome assigns one feasible action to every reachable DTMDP state, representing a complete non-stationary finite-horizon policy.
Policy encoding: Each state action specifies demand-level production quantities, from which product quantities and setup indicators are derived.
Fitness evaluation: Fitness is expected total reward, with rewards equal to negative costs, so maximizing fitness minimizes expected cost.
Fitness evaluation: The GA computes each policy’s expected value exactly by propagating state probability mass through the fixed DTMDP transition kernel.
Initialization: The initial population combines structured constructive policies, randomly generated feasible policies, and optionally projected relaxed policies.
Initialization: The urgency-based seed favors production for arrived, near-deadline, or currently likely-to-arrive demands, but affects initialization only.
Reproduction: Each generation forms N/2 parent pairs, and every pair produces four children using gene-uniform and time-block crossover.

Gene-uniform crossover.

The GA uses gene-uniform crossover for state-level exploration and time-block crossover to preserve temporal policy structure.

Gene-uniform crossover: Gene-uniform crossover independently selects each state gene from either parent with probability 0.5.
Gene-uniform crossover: Gene-uniform crossover explores by recombining parent policies at the state level.
Time-block crossover: Time-block crossover transfers genes before and after a uniformly sampled cut period between parents.

Time-block crossover.

The genetic algorithm mutates feasible child policies, evaluates offspring exactly under the DTMDP, and retains strong solutions while preserving diversity. It stops after a generation limit or detected convergence.

Mutation: Mutation replaces a random fraction of selected genes with feasible actions, so mutation never creates infeasible genes.Mutation is applied to a child with probability µ, and fraction ϕ controls the share of genes modified.
Selection: Offspring are evaluated using the exact DTMDP transition model before the next population is formed.The best children are retained, while randomly selected remaining children maintain population diversity.
Selection: The best chromosome found across generations is stored separately as the incumbent solution.
Termination: The algorithm stops after G generations or earlier when best global fitness fails to improve beyond ε for Gstall consecutive generations.

6. Computational complexity

The complexity analysis identifies the dominant growth factors of DTMDP construction, exact solution, and GA search in terms of model and algorithm parameters. It shows that stochastic branching and exhaustive action evaluation drive exact-method costs, whereas the GA evaluates fixed policies and adds separate population memory.

Complexity framework: The analysis uses planning horizon T, demands I, products K, maximum demand quantity Qmax, population size N, and generations G as its main growth parameters.The bounds are intended to identify dominant factors rather than provide tight worst-case estimates.
DTMDP state and action spaces: Before reachability pruning, the DTMDP state space combines 2I arrival-status vectors with cumulative production vectors bounded by Qmax.The notation uses Qmax^I instead of (Qmax + 1)^I because they are equivalent in Big-O notation for Qmax ≥ 1.
DTMDP state and action spaces: A worst-case action specifies one production quantity for each demand, while practical constraints reduce the action catalogue.Capacity, deadline, production-discretization, and explicit catalogue-size limits restrict feasible actions.
DTMDP construction: DTMDP construction enumerates stochastic arrival outcomes, with up to 2I outcomes in one period.Construction also scans actions for reachable states and checks demand-level and product-level feasibility.
Memory: Transition storage can dominate memory because each state-action pair may have up to 2I stochastic successors.In large instances, the transition model itself is usually the dominant memory component.
GA complexity: One chromosome evaluation propagates probabilities through the DTMDP, and a full GA run evaluates 2N children per generation over G generations.The GA’s additional memory stores population and offspring chromosomes, while preconstructed DTMDP transition memory remains separately required.
Exact method versus GA: Exact solution evaluates all admissible actions in every state, whereas the GA evaluates fixed policies with one prescribed action per reachable state.This action-factor difference explains the GA’s usefulness as state and action spaces grow, although it provides no optimality certificate.

7. Experimental study

Stochastic demand timing substantially enlarges DTMDP computational requirements, while the GA provides near-optimal feasible policies with increasing speed advantages on harder instances. Exact resolution becomes constrained by memory and computation as model size grows, motivating empirical time extrapolation for unsolved cases.

Stochastic-timing complexity: 6.62 times more states and 83.51 times more transition entries arise under stochastic timing than in deterministic counterparts.The mean stochastic state count is 4.44 × 10^3, and the largest transition model contains 8.59 × 10^7 non-zero entries.
Stochastic-timing complexity: 83.50% peak RAM usage leaves some stochastic instances unsolved because exact value and policy tables must accompany the transition model.Exact resolution is limited by both memory consumption and the size of the generated state, action, and transition structures.
GA solution quality and speed: 3.44%±0.39% average optimality gap keeps the GA below the study’s 5% threshold across solved instances, including 90 difficult cases.The difficult cases achieve an average optimization speedup of 6.89 ± 1.41 at the 95% confidence level.
Demand quantity: For small quantities, the exact method is faster; at Q = 1024, GA speedup reaches approximately 5.15 while the average gap is approximately 3.52%.Larger quantities expand cumulative production levels, feasible allocations, state space, and action catalogues.
Number of demands: For small demand sets, GA is slower; from I = 5 it becomes faster, reaching approximately 4 at I = 7, while the average gap is approximately 8.25%.Instances with more than 7 demands could not be solved exactly on the 15 GB machine because of memory limitations.
Unsolved-instance estimation: The Bellman-time regression uses ln(S2A) to predict ln(texact), with an approximately 5% mean absolute percentage error on retained large instances.The fitted relation is texact ≈ 2.8 × 10^-8S2A, and the log-scale fit has R2 approximately 0.999.

8. Discussion

The DTMDP captures stochastic demand timing precisely but incurs substantial computational cost, while the GA offers a practical compromise for larger instances without an optimality certificate.

The stochastic model’s average total-time ratio exceeds 100 relative to comparable deterministic counterparts.Deterministic counterparts replace each arrival distribution with its most likely period.
Exact DTMDP resolution is appropriate for small instances because it provides an optimality certificate and solves them quickly.
The exact method becomes limited by time and memory as the horizon, demand quantities, number of demands, and transition structure grow.
The GA evaluates policies exactly under the stochastic transition model and keeps the average gap close to the target accuracy level.

9. Conclusion

The paper formulates demand-level stochastic lot sizing as a DTMDP and uses a GA to search feasible state-feedback policies. The GA remains close to exact solutions and provides substantial speedups on difficult instances, while regression estimates missing exact baselines for unsolved cases.

9. Conclusion: The DTMDP models deterministic demand quantities, stochastic arrival periods, simultaneous arrivals, capacity competition, demand-specific backlog, and demand-dedicated pre-production.
9. Conclusion: Stochastic timing creates a much larger transition model and substantially increases the memory required for exact resolution.
9. Conclusion: The GA searches feasible state-feedback policies and evaluates each policy exactly under the DTMDP transition model.
9. Conclusion: 6.89 ± 1.41 average speedup at the 95% confidence level is achieved on difficult instances while satisfying the 5% optimality-gap limit.
9. Conclusion: Empirical exact-time regression estimates missing exact baselines and extrapolates likely GA speedups when exact resolution is unavailable.