随机需求到达时间下的多产品产能规划：离散时间MDP建模与遗传算法求解

近日，一项发表于arXiv的研究聚焦于有限周期内的多产品产能规划问题。该问题的特殊性在于：需求数量是确定的，但需求到达的时间点具有随机性。每个需求仅在其已知时间窗口内发生一次，且必须在截止期限前得到满足。

研究团队构建了离散时间马尔可夫决策过程模型，该模型在需求层面制定生产和分配决策，能够准确刻画产能竞争、需求特定积压以及分配依赖的库存动态。为评估随机时间带来的计算影响，研究人员首先将每个随机实例与确定性对应实例进行比较——后者用最可能到达时间替代随机分布。结果显示，随机时间显著增加了状态数量、转移次数、求解时间和内存压力。

针对这一挑战，研究提出采用遗传算法求解随机时间问题。该算法在可行的状态反馈策略空间中进行搜索，并基于DTMDP转移模型精确评估每个策略。在330个基准实例上的计算实验表明，遗传算法在可获得精确解的情况下接近最优解，平均最优性差距约为3.44%。在包含90个测试案例的困难基准集上，算法仍保持在5%的最优性差距阈值以内，并在95%置信水平下实现了平均6.89±1.41倍的优化加速。对于无法在现有硬件上精确求解的实例，研究采用经验贝尔曼时间回归来估计缺失的精确求解时间，并外推遗传算法的预期加速效果。