第三节 生产批量计划问题的模型与相关算法

生产批量计划问题的早期研究一般是以库存问题的形式出现的。1913年，Harris 发表了著名的经济订货量（Economic Order Quantity, EOQ）公式，可以认为是这方面的最早文献。1958年，Wagner和 Whitin提出了动态批量计划问题的动态规划算法（简称 WW算法），但其局限于讨论单级批量计划问题。1968年，Schussel首次讨论了线型生产系统的批量计划问题。同时MRP系统在生产企业中被广泛接受，极大地促进了多级批量计划问题的研究。

一、批量计划问题模型的几类主要特征

批量计划问题的复杂性是由批量模型的特征决定的。模型的特征影响了问题的分类、建模与批量决策的复杂性。

1．计划期

计划期就是主生产计划的时间区段。

2．层级数量

生产系统可以是单级的或多级的。

3．产成品数量

生产系统的产成品数量是影响生产计划问题建模和复杂性的另一个特征。

4．能力或资源约束

生产系统中的资源或能力包括人力、设备、机器及预算等。

5．需求

需求类型是问题模型的输入。

由于批量计划问题的范围非常广，本书主要介绍具有确定需求的动态批量计划问题的模型与求解算法，并按层级原则来对四类问题进行阐述：①无资源约束单层级多产品生产批量计划问题；②有资源约束单层级多产品生产批量计划问题；③无资源约束多级单产品生产批量计划问题；④有资源约束多级单产品生产批量计划问题。

二、无资源约束单层级多产品生产批量计划问题的模型与算法

无资源约束单层级多产品生产批量计划（Single-Level Unconstrained Lot-sizing）问题的研究是有资源约束生产批量计划问题研究的基础，模型研究已经比较成熟，在生产实践（如 MRP）中被广泛采用。一般只需考虑单产品问题及模型，因为多产品问题可以看成多个独立的单产品问题。

（一）无资源约束单层级单产品生产批量计划问题的模型

1．假设条件

（1）计划期有限，长度为T；

（2）需求（dt, t=1,2, …, T）在每个时段事先已知，并且在时段的开始被满足；

（3）生产一个单位物料所需要的费用不随生产数量的多少而改变；

（4）提前期事先已知并设为常数（在不失一般性的情况下，设为0）；

（5）不允许缺货；

（6）每一生产批量的装配费用是常数；

（7）初始和期末的库存量为0。

2．参数定义

St——第t时段的装配费用；

Yt——二进制变量，表示如果产品在第t时段进行生产则值为1，否则值为0；

Ct——第t时段的单位产品的生产成本；

Xt——第t时段的产品生产数量；

ht——第t时段的单位产品的库存费用；

It——第t时段末的库存量；

dR——第R时段的需求量；

Mt——第t时段的需求总量，且Mt=。

3．模型

目标函数式（1-1）表示总费用包括生产准备费用、生产费用及库存费用；约束式（1-2）表示物流守恒方程；约束式（1-3）表示每个时段生产某物料之前必须经过生产准备；约束式（1-4）表示二进制决策变量，1表示生产，0表示不生产；约束式（1-5）表示生产量和库存量不能为负数。

（二）无资源约束单层级单产品生产批量计划问题的相关算法

从历史的角度讲，Harris在1913年提出的EOQ是最早提出的算法， EOQ平衡了装配费用与库存费用。在 EOQ模型中，需求是静态的和已知的，计划期是无限的。

1958年，Wagner和 Whitin提出的动态规划算法是最优算法，依据的是如下基本性质（简称 WW性质）:“存在满足条件It-1 Xt=0的最优解。”Silver等在1973年和1984年分别提出了基于最小单位时段费用的启发式方法（Silver-Meal, SM）及“前瞻后顾”的修正 SM启发式方法（Modified SM, MSM）; Groff在1979年提出基于边际费用分析的启发式（MCA）方法（又称GR）; Freeland等在1981年提出了基于增量费用分析的启发式（ICA）方法（又称FC）; Gaither在1981年提出了“前瞻后顾”的ICA方法；Boe等在1983年提出了基于增量费用分析的 PPA启发式方法（IPPA）;Coleman等在1990年提出了一种基于 IPPA 的迭代方法（TOPS）；在1992年和1993年由Wagelmans等人以及Aggarwal和Park，先后提出计算复杂度为O（nlogn）的算法；Federgruen和 Tzur在1991年提出了一个交错前向算法求解具有普遍性的动态批量模型，该算法的计算复杂度也为O（nlogn）；唐立新在1995年采用GA算法求解了单级无资源约束生产批量计划问题。

三、有资源约束单层级生产批量计划问题的模型与相关算法

有资源（能力）约束单层级生产批量计划问题（Single Level Constrained Lot-sizing Problem, SLCP问题）可以看作通常所说的整体生产计划问题（Aggregate Production Problem, APP）。有资源约束单层级多产品批量计划问题是典型的大批次问题，在一个时段多种不同的产品可以在一台机器上同时进行生产。在进行生产时，计划期是有限的，需求是动态的且不允许缺货。

（一）有资源约束单层级生产批量计划问题的模型

1．参数定义

T——计划期的长度；

N——产品总数量；

Xit——在第t时段物料i的生产数量；

Iit——第t时段末物料i的库存量；

Yit——二进制变量，表示如果物料i在第t时段进行生产则值为1，否则值为0；

Rt——在第t时段的可用资源约束；

dit——在第t时段物料i的需求数量；

Cit——在第t时段一个单位物料i的生产费用；

Sit——在第t时段物料i的装配费用；

Mit=——在第t时段物料i的生产量的上限；

ait——在第t时段物料i的生产准备占用的资源量；

bit——在第t时段物料i的资源消耗量；

hit——在第t时段末物料i的库存保管费用。

2．模型

目标函数式（1-6）表示总费用包括生产准备费用、生产费用及库存费用；约束式（1-7）表示物流守恒方程；约束式（1-8）表示资源能力约束；约束式（1-9）表示只有在生产数量大于0时才能进行生产调整；约束式（1-10）表示二进制决策变量，1表示生产，0表示不生产；约束式（1-11）表示生产量和库存量不能为负数。

（二）有资源约束单层级生产批量计划问题的相关算法

在只考虑单产品的特殊情况下，SLCP问题存在多项式时间的最优算法，且这种最优算法一般都采用动态规划方法求解。单产品 SLCP问题已被Florian等人以及 Bitran和Yanasse 证明是 NP 难问题。Chen 和Thizy已经证明多产品 SLCP问题是强 NP难问题。1973年，Love将此方法推广到库存有限的问题。1978年，Lambrecht和 Vander Eechen又将此方法应用到生产能力随时间变化的问题。Maes等人证明在多项式时间内找到考虑生产准备时间的SLCP问题的可行解是不现实的。

根据文献来看，SLCP问题的求解方法可以分为三种类型：①精确算法；②基于常识的启发式算法或专用启发式算法；③基于数学规划的启发式算法。

1．精确算法

由于SLCP问题是NP难问题，大部分的算法都是启发式算法。鉴于SLCP问题是一个混合整数规划问题，可以采用分支定界法求最优解。解法通常有两种：①1984年由 Barany等人提出的割平面法；②1987年由Eppen和Martin提出的变量重定义法。最近，Belvaux和Wolsey在2000年提出了bc-prod软件，该软件允许对实际生产中的批量计划问题进行建模和求解。此外，针对单产品的 SLCP 问题，最近 Fatemi Ghomi 和Hashemin把问题重新进行模型变换得到最短路问题，并且证明在某些条件具备的情况下可以求得SLCP问题的最优解。

2．基于常识的启发式算法或专用启发式算法

基于常识的启发式算法很多，算法的执行过程一般分为三个步骤：①合并批量；②可行化处理；③进行算法改进。

根据Maes和 Wassenhove的描述，基于常识的启发式算法可以分为以下两类。

（1）基于period的启发式算法

在这一类的启发式算法中，Eisenhut的启发式算法是这方面的最早工作。其他的启发式算法由Maes和Wassenhove（1986）, Gunther （1987）, Trigeiro、Selen和 Heuts（1989），以及 Kirca和 Kokten（1994）等人分别在1986年、1987年、1989年和1994年相继提出。Maes 和Wassenhove开发了一种时段到时段的启发式算法来确定当前时段必须进行生产的产品。

Kirca和Kokten开发了一个产品到产品的启发式算法。计算结果表明Kirca和Kokten 的算法比 Lambrecht与Vanderveken、Dixon 与Silver、Maes与 Wassenhove以及Cattrysse等人开发的算法更有效。

（2）改进启发式算法

这些启发式算法的执行过程通常包括三个步骤：第一步是在不考虑能力约束的前提下生成初始解；第二步是根据能力条件以最小的费用增量将产品的生产数量由一个时段移动到另一个时段；第三步是在保证可行性的情况下，尽量使费用降到最低。Dogramaci等人提出了一个四步算法。Karni和Roll的算法是一个改进启发式算法。该算法以单产品无资源约束 WW动态规划算法的解作为初始解。它由五个子算法构成，执行过程分三个步骤。在第一个步骤中，产生一个基于 WW算法的初始下界解；在第二个步骤中，算法采用向左和向右移动的方式，通过可变比例组合相邻时段的制造数量来消除不可行性并改进当前解；通过改变当前最好解的结构，算法在第三步骤中可以进一步改进最好解。

Gunther的启发式算法以 Lot-for-Lot策略的解为初始解，考虑三种因素：①作为批量规则的边际费用系数；②能够确保可行性的能力约束；③作为能力平衡有限性索引的费用系数。Selen和 Heuts提出了一个修改的Gunther启发式算法。Trigeiro开发了针对带装配时间的 SLCP问题的启发式算法，该算法是基于SM的批量启发式算法。Trigeiro采用一个反馈机制来确保能力可行性。算法的初始解是 Lot-for-Lot启发式的解，随后算法根据预先安排好的移动策略来尽量改进当前解。

由于改进启发式算法需要检验大量的移动策略和问题的可行性，且与时段到时段启发式算法相比需要更多的计算时间，因此这类启发式算法具有一定的缺陷。

3．基于数学规划的启发式算法

这类算法的好处之一是能够为最优解提供一个下界，因此，算法为解的质量提供了一个评价准则。由于这类算法的执行过程不容易被研究者编程实现，因此在对实际问题进行求解时需要更复杂的计算过程。

（1）松弛启发式算法

这类启发式算法是基于能力约束松弛的方法。这类算法非常流行，已经被许多学者编程实现了。通过松弛能力约束，SLCP问题被分解为N个无资源约束单产品问题，随后这些无资源约束单产品问题可以用 WW算法进行求解。

Thizy和 Wassenhove采用拉格朗日松弛算法松弛能力约束，将问题分解为N个无资源约束子问题。被松弛后，问题的解（对偶解）是原问题的一个下界。通过固定由对偶解给出的装配变量，问题转化成运输问题，运输问题的求解结果是原问题的上界。由此，拉格朗日乘子可以采用Held等人提出的次梯度优化过程进行更新。求解过程不断进行，直到下界等于上界或已经达到预先设定的迭代次数。

Trigeiro的算法基本上与 Thizy和 Wassenhove的算法相同，不同点在于 Trigeiro的算法根据原问题的对偶解，采用消除过程来构建可行调度。在消除过程中，采用前向和后向方式。在每次迭代中，先采用前向过程，之后采用后向过程产生可行调度。然后，采用拉格朗日费用准则来确定要移动的产品和移动数量。Billington等人、Trigeiro等人及 Diaby等人的方法都采用了Thizy和 Wassenhove的算法思想。

Bitran和Matsuo给出了松弛算法的错误界。他们指出：随着产品数量的增加，松弛问题与原问题之间的相对差可以忽略不计。Millar 和Yang对允许延期交货（Backordering）的有资源约束多产品问题采用基于网络的模型进行描述并提出了两种求解算法。他们实现了拉格朗日分解和拉格朗日松弛技术。这两种算法不但可以保证找到可行解，而且能够对解的质量进行评价。

尽管与其他技术相比，松弛技术更加灵活，不过值得一提的是，对于更复杂的生产计划模型（如多级问题或具有复杂产品结构的问题），松弛技术不一定适用。

（2）基于分支定界的启发式算法

分支定界算法可以作为求解整数规划问题的通用方法。不过，采用这种方法求解，具有很大规模的 SLCP问题是非常耗时的。因此，这个方法通常不被作为求大规模问题最优解的算法。前面提到的松弛启发式可以作为分支定界算法的下界算法。

Gelders等人提出了一个基于拉格朗日能力约束松弛分支定界算法和一个次梯度优化算法。Diaby等人开发了几个新的求解算法，这些算法能够求解经典的 SLCP问题以及带装配时间、有限常规时间和有限加班时间的SLCP问题。Hindi在他的启发式算法中集成了分支定界方法。Armentano等人将考虑生产准备时间的有资源约束单层级多产品问题表示为一个最小费用网络流问题。Chung等人将动态规划和分支定界算法相结合来求解单产品有资源约束问题。

（3）集划分与列生成启发式算法

Cattrysse等人提出了求解 SLCP问题的3个集划分启发式算法和1个列生成启发式算法。Trigeiro等人指出：由于在批量被分割时装配费用及装配时间仅仅被考虑了一次，因此集划分方法忽略了部分成本。

（4）其他方法

在其他的研究文献中，提出了一些混合算法或方法，这些方法在某些方面与前面提到过的方法有所不同。Hindi把 SLCP问题转化为最短路问题，之后采用列生成启发式算法求解最短路问题的线性规划松弛问题。松弛问题的解是一个可行解，通过重新优化可变成本等方式对当前解进行改进，改进后的解用作禁忌搜索（Tabu Search, TS）算法的初始解。Hindi等人采用嵌入了消除启发式和局部搜索算法的次梯度拉格朗日松弛算法对带有装配时间的多产品 SLCP问题进行了求解。算法首先找到一个好的可行解（上界），之后对可行解进行了改进。Lozano等人采用主对偶方法求解了 SLCP 问题的线性规划松弛问题。他们的计算实验显示，尽管主对偶算法需要更多的计算时间，其效果还是好于次梯度算法的。唐立新在1999年提出了求解 SLCP问题的基于能力消除法的拉格朗日算法。在问题的求解过程中，首先对能力约束进行松弛，然后采用动态规划算法对N个独立的无资源约束子问题进行求解，对产生的不可行解采用顺时段能力调整法和逆时段能力调整法进行调整。熊红云在2001年采用多级退火遗传算法求解了多产品、单级、单资源约束的静态批量计划问题；采用0—1矩阵的编码方式对问题进行编码，将能力约束作为罚函数加到目标函数中，然后求解无资源约束的批量计划问题模型。杨红红在2001年采用遗传算法，以生产数量为编码，出现不可行解后，需要对库存平衡和能力约束两方面进行调整。

目前，在求解SLCP问题时，我们可以采用 CPLEX软件和 XPRESS-MP软件。Belvaux与 Wolsey提出的 bc-prod软件为 SLCP问题的求解提供了一个完整的开发平台。在该平台下，我们可以输入模型、添加分割以及应用XPRESS-MP对SLCP问题进行求解。

四、多资源约束单层级生产批量计划问题的模型与相关算法

（一）多资源约束单层级生产批量计划问题的模型

多资源约束单层级问题的模型与单资源约束单层级问题模型大致相同，只是在资源约束的表达上将Rt变为Rkt（k=1,2, …, K, K表示资源数目）。模型如下：

（二）多资源约束单层级生产批量计划问题的相关算法

关于多资源约束单层级问题的求解算法方面的文献很少，从已发表的文献上看，唐立新等人提出了基于线性规划分解的遗传算法。他们首先将问题改写成线性规划模型，然后采用线性规划软件包进行求解，对求解结果采用遗传算法再进行寻优。许志兴等人提出了基于退火惩罚的混合遗传算法；马慧民等人提出了粒子群优化算法，采用罚函数法将约束吸收到目标函数中，采用0—1编码的方式求解问题。

五、无资源约束多层级生产批量计划问题的模型与相关算法

多层级生产批量计划（Multilevel Lot-sizing, MLLS）问题是依据产品数据结构、项目（物料）提前期数据、最终项目的外部需求（独立需求）信息以及中间项目的关联需求信息，在给定的计划时间范围上，确定全部项目在不同时间段上的生产数量，使得总费用之和最小。MLLS问题比单层级批量计划问题要复杂得多，因为单层级批量计划问题是以产品为单位，产品之间的需求是相互独立的。而多层级批量计划问题是以零部件为单位，在同一产品结构中的零部件之间是相互关联的，即项目之间存在相关需求。由于多层级批量计划问题具有一定难度，实际运行的MRP系统一般都采用无限能力符合方法来确定生产计划，并依次产生能力需求计划，而这种无限能力负荷法确定的生产批量计划问题即为多级无资源（能力）约束生产批量计划问题。

MLLS问题的计划安排与产品结构的组成及类型有关。产品结构主要可以分为三种不同的类型：①线型结构（Serial Structure）; ②装配树状结构（Assembly Structure）; ③一般网络结构（General Structure）。图1-3给出了三种不同的产品结构。

图1-3中每个节点对应一种物料，节点i和节点j 之间的边（i, j）表示如果要生产物料j需要用到物料i。

（一）无资源约束多层级生产批量计划问题的模型

离散制造业中无资源约束MLLS问题中，假设提前期为零，并且不允许缺货。总成本由生产准备费用和库存费用组成且成本参数不随时间变化。

1．参数定义

T——计划期的长度；

Xit——在第t时段物料i的生产数量；

Iit——在第t时段末物料i的库存量；

Yit——二进制变量，表示如果物料i在第t时段进行生产则值为1，否则值为0；

dit——在第t时段物料i的需求数量；

Cij——生产一个单位物料j所需要的物料i的数量；

Mit=——在第t时段物料i的生产量的上限；

hit——在第t时段末物料i的库存保管费用；

N——物料总数量；

Γ（i）——物料i的直接后继的集合；

Γ-1（i）——物料i的直接前趋的集合。

2．模型

目标函数式（1-18）表示总费用包括生产准备费用及库存费用；约束式（1-19）表示物流守恒方程；约束式（1-20）表示需求公式，如果物料i是最终项目，则需求为外部需求，否则需求由当前物料i的所有后继物料的生产量决定；约束式（1-21）表示只有在生产数量大于0时才能进行生产调整；约束式（1-22）表示二进制决策变量，1表示生产，0表示不生产；约束式（1-23）表示生产量和库存量不能为负数。

（二）无资源约束多层级生产批量计划问题的相关算法

无资源约束多层级的批量计划问题中，中间项目除独立需求（即外部需求）外，还有相关需求（即内部需求），因此求解方法与产品结构的复杂程度关系密切。

1．动态规划最优算法

1968年，Schussel[13]首次提出单产品定常需求串联生产系统的批量模型，并基于“前趋的生产批量是其后继的生产批量的整数倍”的原则，采用动态规划方法求解。1981年，Lambrecht等对串联生产系统的批量计划问题进行了较全面的综述。

2．分支定界最优算法

1984年，Afentakis等对装配系统采用 Lagrange松弛确定下界，然后采用分支定界算法求最优解。1986年，该方法被推广到一般生产系统。1986年，Rosling 对装配系统采用设备布置问题（Facility Location Problem, FLP）建模，基于线性规划松弛确定下界，然后分支定界求最优解。

3．基于费用修正的启发式算法

1981年，Graves提出了一种称为“Multi-pass”的启发式算法，从某种单层级能力无限的批量计划问题的求解算法（WW算法）出发，在各个层级之间通过修正费用参数，进行迭代求解。1982年，Blankburn和 Millen直接根据项目之间的相互关系对费用参数进行修正。

4．平行启发式算法

通常的启发式算法一般是逐级（Level by Level）确定生产批量，1987年，Afentakis提出了一种称为“平行启发式”的算法，该算法按逐个时段（Period by Period）确定生产批量。

5．亚启发式算法

Kuik和Salomon在1990年提出了求解无资源约束MLLS问题的模拟退火（Simulated Annealing, SA）算法。Dellaert等人在2000年采用遗传算法对具有一般网络结构的批量计划问题进行了求解。Dellaert等人在2003年提出了求解一般网络结构批量计划问题的基于随机装配费用系数的WW算法。Tang在2004年采用模拟退火算法对线型结构批量计划问题进行了求解。Jeunet和Jonard采用单点随机搜索算法求解了一般网络结构的批量计划问题。Pitakaso 等人采用基于随机装配费用系数WW算法的蚁群（Ant Colony Optimization, ACO）算法对一般网络结构的批量计划问题进行了求解。蚁群算法首先规划了各个项目的调度顺序，之后采用 WW算法进行问题求解。

六、有资源约束多层级生产批量计划问题的模型与相关算法

在考虑MLLS问题的批量计划时，当以关键资源为约束时，确定生产批量计划的问题就是有资源约束多层级生产批量计划问题[2]。有资源约束多层级生产批量计划问题更接近于实际生产计划，是研究的重点和难点。

（一）有资源约束多层级生产批量计划问题的模型

此问题的数学模型与无资源约束多层级 MLLS问题的模型相似，只是在约束部分增加了一个资源约束条件，模型如下：

（二）有资源约束多层级生产批量计划问题的相关算法

1．基于网络分析的动态规划最优算法和启发式算法

1978年，Lambrech和 VanderEechen研究了线型系统的能力受限的批量计划问题，基于凹费用网络分析构造了动态规划最优算法。1980年， Steinberg和Napier将一般网络系统的批量计划问题转化为一个广义约束网络的最小费用问题，从而可用网络算法求最优解，但是上述两种算法的时间效率都很低。1984年，Zahorik等分析了装配系统批量计划问题的混合整数规划（Mixed Integer Programming, MIP）模型的特点，将只有三个时段的批量计划问题转化为网络问题，然后以此为基础对多个时段依次采用只有三个时段的最优启发式算法求解问题。

2．基于Lagrange松弛的分支定界启发式算法

1986年，Billington等对装配系统的单瓶颈情形采用 Lagrange松弛确定下界，然后采用启发式分支定界方法求解，这与有资源约束单层级的批量计划问题的Lagrange松弛方法类似，只是具体过程更复杂些。

3．基于单层级或能力无限批量计划问题的启发式算法

1984年，Bahl和Ritzman对产品结构中间级上的生产项目，采用求解单层级能力无限批量计划问题的直接批量算法作为启发式算法。Blackburn和Millen将他们在1982年的求解多层级能力无限批量计划问题的费用修正启发式算法推广到能力受限问题中，提出了多种相关启发式算法。1991年，Roll和 Karni将他们用于求解单层级能力受限批量计划问题的移动启发式算法推广到带整体约束的多层级批量计划问题中。

4．基于线性规划松弛的启发式算法

1991年，Maes等讨论了多层级能力受限的批量计划问题及其可行性问题的计算复杂性，并将其 MIP数学模型形式上等价变换为广义设备布置问题的数学模型。求解时分成两步：①线性规划松弛（即将Yit∈{0,1}松弛为Yit∈[0,1]）求解；②若解中有些Yit不为整数，则将这些Yit的解进行舍入（0或1），并将其值固定，回到①。

5．亚启发式算法

采用亚启发式算法求解有资源约束的批量计划问题时，通常会结合三种约束处理方法：①罚函数法；②能力调整法；③拉格朗日松弛法。Kuik等人在1993年提出了模拟退火和禁忌搜索算法求解有资源约束的批量计划问题；唐立新等人在1997年采用基于线性规划分解算法的遗传算法求解了多资源约束批量计划问题；Barbarosoglu和 Ozdamar在2000年提出了求解多资源约束批量计划问题的模拟退火算法。Ozdamar 和Barbarosoglu在2000年采用基于Largrange松弛的模拟退火算法求解了带装配时间的多资源约束的批量计划问题；Xie和Dong在2002年提出了启发式遗传算法；Berretta和Rodrigues 在2004年提出了元算法；Pitakaso等人在2006年提出了基于滑动时间窗的蚁群算法。

表1-2根据不同批量计划问题的特点，给出了一个文献总结。