背景介绍

生产计划是工厂进行生产制造最为重要的决策内容之一。通过利用混合整数规划模型（MIP）对该问题进行建模与求解，得到生产排程解决方案，能够在一定时间内提供高质量的决策支持。在上一篇博客中，我们讨论了生产计划问题的一般场景和衍生场景；在本篇博客中，我们将对常用的问题解决方法进行讨论。

常用方法

解决方案框架

当前一般的并行机问题求解通常分为可行解阶段（Feasibility phase）和寻优阶段（Improvement phase），即先找到该问题的初始解，然后在此基础上继续探索，如果找到了更好的可行解，则替换初始可行解，不断更新，直到达到收敛标准，如：获得最优解，获得符合GAP值要求的可行解，当前最优解不再更新，达到时间限制等。

常见的解决方法

解决并行机问题的方法主要涉及基于数学规划的方法、拉格朗日启发式算法、分解和聚合启发式、元启发式算法、基于问题的贪心启发式算法等。这些方法分别作用于简化与优化、求解方法、求解框架几个过程。

基于数学规划的方法（Mathematical Programming Heuristics）通常通用性更强，在模型修改或拓展方面也更为灵活。此类方法包括分支定界法（Branc-and-Bound，获得最优解）、Dantzig-Wolfe 和列生成（Dantzig-Wolfe and Column Generation）、固定优化启发式（Fix-and-Optimize）等框架，涉及元整启发式（Rounding Heuristics）、线性规划启发式（LP heuristics）、固定松弛启发式（Fix-and-Relax）等求解方法。为了使模型更易求解或者获得更优质的解，还可以使用模型重构（Reformulation）简化问题或将问题转化为一类更容易求解的问题，使用有效不等式使得约束更紧，从而得到质量更高的可行解。基于拉格朗日的方法（Lagrangian Heuristics），使用拉格朗日松弛（Lagrangian Relaxation）一些复杂约束并在目标函数上对约束冲突进行惩罚，通过不断更新的拉格朗日乘子和可行解作为桥梁进行迭代求解。该方法能够获得比线性规划启发式更优质的下界，从而可能得到更优的可行解。
分解或聚合启发式（Decomposition and Aggregation Heuristics）。并行机问题涉及生产资源、产品、时间等多个维度，问题复杂，变量众多，求解困难。但是，其较为清晰的结构使得这一类问题可以通过分解或聚合的方法将原问题分解为子问题或对变量进行合并求解，之后再进行后处理，以降低问题的求解难度，即分解或聚合启发式（Decomposition and Aggregation Heuristics）
元启发式（Metaheuristics）也是一类较为通用的方法。与数学规划类问题的区别在于，数学规划类问题以模型为基础，在相同形式的问题上拓展性更强，而元启发式算法适用于更通用的场景，但定制性更强，能够灵活地利用专家知识对启发式的策略进行修正，使得模型更好更快地找到最优解。包括局部搜索启发式（Local Search Heuristics）、变邻域搜索启发式（Variable Neighborhood Search）、模拟退火启发式（Simulated Annealing Heuristics）等。为了提高启发式求解的效率，也常加入禁忌搜索启发式（Tabu Search Heuristics）以防止高频重复搜索。
基于问题的贪婪启发式（Greedy Heuristics）。如利用并行机问题多期的特点，采用贪婪算法依期数增加对每一期进行指派与计算。

文献举例

下面是几种有代表性的方法列举。

解决方案举例

固定优化启发式

固定优化启发式方法一般分别采用固定松弛法和固定优化法寻找问题的初始可行解和更优解。

固定松弛法的主要思路是，根据期数对原问题的换型变量进行分组，每一轮利用混合整数规划（MIP）求解器只求解其中一组变量而固定或松弛其它换型变量，从而简化问题，加快求解时间。固定变量，即将部分变量固定为之前轮次的求解结果；松弛变量，即将变量的可行域松弛为连续闭区间。第一轮只有求解变量和松弛变量。之后加入固定变量。最后一轮没有松弛变量。每一轮固定的变量有所重合，通过提升期数之间的交互来提升求解结果，获得更好的可行解。

固定优化法将问题分解为若干个子问题，对于每个子问题，在当前最优解的基础上，利用MIP求解器对一部分变量进行再优化（Re-optimize），以寻找更好的可行解。其分解依据主要有产品、资源、进程几个维度。其中，资源包括机器、期、原材料等。进程主要针对考虑每期排产先后次序的问题，在本场景中不考虑。依产品分解由于涉及的变动范围更小，也称为局部搜索；以期数涉及变动范围大，以跳出局部最优来探索更多的空间，也成为变领域搜索。分解后的子问题的求解次序不同，往往也会影响求解的效率或效果。如随机选择，根据机器最小灵活性（Randomized Least Flexible Machine，RLFM）[4]，根据变量相关性[3]等。

该方法在实现上有较多变种。如：向原问题的资源类约束中添加松弛变量（Slack Variable）并在目标函数中添加相应的惩罚项，使得修改后的问题一定可行；通过最小化目标函数使得求解结果逐渐向原问题的可行解收敛；这种方法替代了可行解阶段，使得求解框架更为简单[2]。为了提升求解速度，还可以在局部搜索的过程中限定改变变量的个数[3]。为了提升解决方案的多样性，拓展求解空间，可以加入随机变换来改变某些变量的取值[3]。

滚动优化方法（Rolling Horizon）

滚动优化方法主要针对资源约束少，约束间交互简单的问题，如机器同质且没有其它资源约束的问题。
它将期数分为若干个相互连续且无重合的区间，并根据期数顺序将原问题分解为若干个子问题，修改或添加约束后求解。每个子问题只涉及该期数区间对应的变量，考虑扣除了已经求解的子问题所消化的需求。由于求解时各期没有实时交互，为了保证后期的可行性，需要添加约束，以保证遗留的需求不超过后期可实现的最大需求[5]。
利用上述方法找到可行解，之后可以利用固定优化方法寻求更优解。

Dantzig-Wolfe 和列生成

这类方法主要针对换型变量非常多且约束矩阵稀疏的问题，求解结果中只有某些换型变量被考虑且变量间关联约束较少的问题。如果考虑所有换型变量同时求解，巨大的变量数会使得求解非常困难；而通过一步一步添加对目标函数有益的变量的方法能够极大地提升找到解决方案的效率。

（伪代码引用自Fiorotto, Diego Jacinto, Silvio Alexandre de Araujo, and Raf Jans. "Hybrid methods for lot sizing on parallel machines." Computers & Operations Research 63 (2015): 136-148.）

例如，利用Dantzig-Wolfe分解，引入变量表示多种计划子方案（这里指是否在某期某机器上生产某产品），写出主问题（Restricted Master Problem，RMP），并将其分解成若干个子问题，求解子问题来判断如果将该子问题对应的变量加入原问题是否能得到更好的目标函数，即如果考虑采用该子计划是否能够降低生产成本。在添加随机初始变量之后，求解主问题得到其对偶变量并通过求解子问题获得主问题各变量的Reduced Cost，根据Reduced Cost取值决定是否添加相应变量到主问题；循环迭代直至找到问题的最优解[6]。也有方案根据期数进行了Dantzig-Wolfe分解和列生成求解[7]。
对于这种方法而言，如果约束相互的关联过于复杂，可能会使得求解不易收敛，从而影响求解效果。

参考文献

[1]    Maes, Johan, John O. McClain, and Luk N. Van Wassenhove. "Multilevel capacitated lotsizing complexity and LP-based heuristics." European Journal of Operational Research 53.2 (1991): 131-148. 
[2]    Helber, Stefan, and Florian Sahling. "A fix-and-optimize approach for the multi-level capacitated lot sizing problem." International Journal of Production Economics 123.2 (2010): 247-256.
[3]    Chen, Haoxun. "Fix-and-optimize and variable neighborhood search approaches for multi-level capacitated lot sizing problems." Omega 56 (2015): 25-36.
[4]    Xiao, Jing, et al. "MIP-based fix-and-optimise algorithms for the parallel machine capacitated lot-sizing and scheduling problem." International Journal of Production Research 51.16 (2013): 5011-5028.
[5]    Beraldi, Patrizia, et al. "Rolling-horizon and fix-and-relax heuristics for the parallel machine lot-sizing and scheduling problem with sequence-dependent set-up costs." Computers & Operations Research 35.11 (2008): 3644-3656.
[6]    Cunha, Jesus O., Hugo H. Kramer, and Rafael A. Melo. "Effective matheuristics for the multi-item capacitated lot-sizing problem with remanufacturing." Computers & Operations Research 104 (2019): 149-158.
[7]    Fragkos, Ioannis, Zeger Degraeve, and Bert De Reyck. "A horizon decomposition approach for the capacitated lot-sizing problem with setup times." INFORMS Journal on Computing 28.3 (2016): 465-482.
[8]    Toledo, Franklina Maria Bragion, and Vinicius Amaral Armentano. "A Lagrangian-based heuristic for the capacitated lot-sizing problem in parallel machines." European Journal of Operational Research 175.2 (2006): 1070-1083.
[9]    Xiao, Jing, et al. "A hybrid Lagrangian-simulated annealing-based heuristic for the parallel-machine capacitated lot-sizing and scheduling problem with sequence-dependent setup times." Computers & Operations Research 63 (2015): 72-82.
[10]    Fiorotto, Diego Jacinto, Silvio Alexandre de Araujo, and Raf Jans. "Hybrid methods for lot sizing on parallel machines." Computers & Operations Research 63 (2015): 136-148.
[11]    Silva, Cristovao, Nathalie Klement, and Olivier Gibaru. "A generic decision support tool for lot-sizing and scheduling problems with setup and due dates." Closing the Gap Between Practice and Research in Industrial Engineering. Springer, Cham, 2018. 131-138.