随机需求时间让批量生产难解？新算法提速6.89倍，最优性差距仅3.44%！
Discrete-Time MDP Modeling for Multi-Item Capacitated Lot Sizing with Stochastic Demand Timing
📖 AI 总结
本文研究了一个有限时域内多物品、有产能限制的批量生产问题，其中需求量是确定的，但需求到达时间具有随机性，每个需求在已知时间窗口内发生一次，且必须在截止日期前满足。作者将这一问题建模为离散时间马尔可夫决策过程（DTMDP），在需求层面做出生产和分配决策，以刻画产能竞争、需求特定积压及依赖分配的库存动态。为隔离随机时间的影响，研究将随机实例与用最可能到达期替代的确定性版本对比，发现随机性显著增加了状态数、转移数、求解时间和内存压力。为此，作者提出一种遗传算法（GA），在可行状态反馈策略空间搜索，并在DTMDP模型下精确评估策略。在330个基准实例上，GA的平均最优性差距约为3.44%；在90个困难实例中，差距保持在5%以内，并实现了平均6.89倍的求解加速。对于无法精确求解的实例，作者用经验Bellman时间回归估计缺失的精确求解时间，以推算GA的预期加速比。
🔑 关键词速览
| Discrete-Time Markov Decision Process (DTMDP) | 离散时间马尔可夫决策过程，一种在离散时间点上进行决策的随机动态规划模型，用于处理状态转移具有马尔可夫性质的序贯决策问题。 |
| Multi-Item Capacitated Lot Sizing | 多物品有容量限制的批量生产问题，指在有限生产能力下，决定多种产品各期生产批量以最小化总成本的优化问题。 |
| Stochastic Demand Timing | 随机需求时间，指需求到达的时期不确定，而需求量本身是确定的，增加了决策的随机性。 |
| Genetic Algorithm (GA) | 遗传算法，一种基于自然选择和遗传机制的启发式优化算法，通过选择、交叉和变异操作迭代搜索最优解。 |
| State-Feedback Policy | 状态反馈策略，指决策规则根据当前系统状态来确定行动，是动态规划中常用的策略形式。 |
📱 每天一份 AI 前沿日报
关注公众号，每天 09:00 推送 · 不错过任何重磅