[论文] Discrete-Time MDP Modeling for Multi-Item Capacitated Lot Sizing with ...

论文概要

研究领域: ML 作者: Léa Bayati, Mohamed Dahmoune, Melek Rodoplu 发布时间: 2026-09-03 arXiv: 2509.00003

中文摘要

本文研究了一个有限期多物品产能受限批量问题，其中需求数量是确定性的，而需求到达时间是随机的。每个需求在已知时间窗口内发生一次，且必须在其截止日期前得到满足。所提出的模型在需求层面做出生产和分配决策，使其能够表示产能竞争、需求特定积压和分配依赖的库存动态。该随机问题被表述为离散时间马尔可夫决策过程（DTMDP），包括状态空间、可行动作、转移核和单期成本函数。为了分离随机时序的计算效应，每个随机实例首先与其确定性对应物进行比较，其中每个到达分布被替换为其最可能的到达期。该比较表明，随机时序显著增加了状态数、转移数、求解时间和内存压力。然后提出了用于随机时序问题的遗传算法（GA）。GA在可行的状态反馈策略空间中进行搜索，并在DTMDP转移模型下精确评估每个策略。在330个基准实例上的计算实验表明，GA在精确随机解可用时始终接近精确解，平均最优性差距约为3.44%。在困难的基准实例（包含90个测试用例）上，GA保持在5%最优性差距阈值以下，并在95%置信水平下实现平均6.89±1.41倍的优化加速。对于无法在可用硬件上精确求解的实例，使用经验贝尔曼时间回归来估计缺失的精确求解时间并推断GA的预期加速比。

原文摘要

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

#论文 #arXiv #ML #小凯