Parallelized decomposition approaches for capacitated lot-sizing problems: application to the problem with constraints on ending inventories
本文提出一种新的并行化松弛-固定启发式算法，不依赖传统时间顺序，用于求解带期末库存约束、准备时间和销售损失的多产品批量问题，并设计了拉格朗日松弛启发式及多项式动态规划算法。
This paper introduces an original parallelisation framework to design a new relax-and-fix heuristic, using strategies that do not rely on the classical chronological order, for capacitated lot-sizing problems. These decomposition approaches, never considered in the literature, are applied to solve a multi-item lot-sizing problem with constraints on ending inventories, setup times and lost sales. Another decomposition approach, a Lagrangian relaxation heuristic, is also proposed and parallelised. Moreover, to solve the relaxed problem in the Lagrangian relaxation heuristic, a polynomial dynamic programming algorithm is derived for an uncapacitated version of the single-item lot-sizing problem with ending inventory constraints. Computational experiments are conducted to analyze the efficiency of the different approaches, in particular of the new relax-and-fix strategies, and compare them to a linear programming standard solver.