第二十七章生产与服务运作管理中的优化问题 本章主要介绍生产和服务运作管理方面的一些优化问题。实际上，生产和服务运作 管理的内容也是非常丰富的，几乎包含了企业管理的所有方面，本章中只是介绍几个实 例而已。 §1有瓶颈设备的多级生产计划问题 在制造企业的中期或短期生产计划管理中，常常要考虑如下的生产计划优化问题 在给定的外部需求和生产能力等限制条件下，按照一定的生产目标（通常是生产总费用 最小)编制未来若干个生产周期的最优生产计划，这种问题在文献上一般称为批量问题 (lotsizing problems)。所谓某一产品的生产批量(lotsize),就是每通过一次生产准备生 产该产品时的生产数量，它同时决定了库存水平。由于实际生产环境的复杂性，如需求 的动态性 费用的非线 生产工艺过程利 络结构的复 生 产能力的限 制，以及车间层生产排序的复杂性等，批量问题是 一个非常复杂 非常困难的问题 ○我们通过下面的具体实例来说明这种多级生产计划问趣的优化模型。这里“多级” 的意思是需要考虑产品是通过多个生产阶段（工艺过程）生产出来的。 例1某工厂的主要任务是通过组装生产产品A,用于满足外部市场需求。产品A 的构成与组装过程见图1，即D,E,F,G是从外部采购的零件，先将零件D,E组装成 部件B,零件F,G组装成部件C,然后将部件B,C组装成产品A出售。图中弧上的 数字表示的是组装时部件（或产品）中包含的零件（或部件）的数量（可以称为消耗系 数)，例如DB弧上数字“9”表示组装1个部件B需要用到9个零件D:BA弧上的 数字“5”表示组装1件产品A需要用到5个部件B:依此类推。 一瓶颈设备加工 15 @ 图1产品构成与组装过程图 假设该工厂每次生产计划的计划期为6周（即每次制定未来6周的生产计划），只 有最终产品A有外部需求，目前收到的订单的需求件数按周的分布如表1第2行所示。 部件B,C是在该工厂最关键的设备（可以称为瓶颈设备）上组装出来的，瓶颈设备的 386
-386- 第二十七章 生产与服务运作管理中的优化问题 本章主要介绍生产和服务运作管理方面的一些优化问题。实际上，生产和服务运作 管理的内容也是非常丰富的，几乎包含了企业管理的所有方面，本章中只是介绍几个实 例而已。 §1 有瓶颈设备的多级生产计划问题 1.1 问题实例 在制造企业的中期或短期生产计划管理中，常常要考虑如下的生产计划优化问题： 在给定的外部需求和生产能力等限制条件下，按照一定的生产目标（通常是生产总费用 最小）编制未来若干个生产周期的最优生产计划，这种问题在文献上一般称为批量问题 （lotsizing problems）。所谓某一产品的生产批量（lotsize），就是每通过一次生产准备生 产该产品时的生产数量，它同时决定了库存水平。由于实际生产环境的复杂性，如需求 的动态性，生产费用的非线性，生产工艺过程和产品网络结构的复杂性，生产能力的限 制，以及车间层生产排序的复杂性等，批量问题是一个非常复杂、非常困难的问题。 我们通过下面的具体实例来说明这种多级生产计划问题的优化模型。这里“多级” 的意思是需要考虑产品是通过多个生产阶段（工艺过程）生产出来的。 例 1 某工厂的主要任务是通过组装生产产品 A ，用于满足外部市场需求。产品 A 的构成与组装过程见图 1，即 D, E, F,G 是从外部采购的零件，先将零件 D, E 组装成 部件 B ，零件 F,G 组装成部件C ，然后将部件 B,C 组装成产品 A 出售。图中弧上的 数字表示的是组装时部件（或产品）中包含的零件（或部件）的数量（可以称为消耗系 数），例如 DB弧上数字“9”表示组装 1 个部件 B 需要用到 9 个零件 D ； BA 弧上的 数字“5”表示组装 1 件产品 A 需要用到 5 个部件 B ；依此类推。 图 1 产品构成与组装过程图 假设该工厂每次生产计划的计划期为 6 周（即每次制定未来 6 周的生产计划），只 有最终产品 A 有外部需求，目前收到的订单的需求件数按周的分布如表 1 第 2 行所示。 部件 B,C 是在该工厂最关键的设备（可以称为瓶颈设备）上组装出来的，瓶颈设备的
生产能力非常紧张，具体可供能力如表1第3行所示（第2周设备检修，不能使用）。B,C 的能力消耗系数分别为5和8，即生产1件B需要占用5个单位的能力，生产1件C需 要占用8个单位的能力 表1生产计划的原始数据 用次 3 6 A的外部需求 40 0 100 10 瓶颈能力 1000 5000 5000 1000 零件编号 A B D E F G 生产准%费用400 00 1000 300 200 400100 单件库存费用 12 0.6 1.0 0.04 0.03 0.04 0.04 对于每种零部件或产品，如果工厂在某一周订购或者生产该零部件或产品，工厂 需要一个与订购或生产数量无关的固定成本（称为生产准备费用）：如果某一周结束时 该零部件或产品有库存存在，则工厂必须付出一定的库存费用（与库存数量成正比）。 这些数据在表1第5、6行给出。 按照工厂的信誉要求，目前接收的所有订单到期必须全部交货， 不能有缺货：此 外，不妨简单地假设目前该企业没有任何零部件或产品库存，也不希望第6周结束后留 下任何零部件或产品库存。最后，假设不考虑生产提前期，即假设当周采购的零件马上 就可用于组装，组装出来的部件也可以马上用于当周组装成品A。 在上述假设和所给数据下，如何制定未来6周的生产计划。 12建立模型 (1)问题分析 这个实例考虑的是在有限的计划期内，给定产品结构、生产能力和相关费用及零 部件或成品（以下统称为生产项目）在离散的时间段上（这里是周，也可以是天、月等） 的外部需求之后，确定每一生产项目在每一时间段上的生产量（即批量），使总费用最 小。由于每一生产项目在每一时间段上生产时必须经过生产准备(stup),所以通常 讨论中总费用至少应考虑生产准 费用和库存费用。其实，细心的读者 定会问： 是香 需要考虑生产的直接成本（如原材料成本、人力成本、电力成本等）？这是因为本例 假设了不能有缺货发生，且计划初期和末期的库存都是0，因此在这个6周的计划期内 A的总产量一定正好等于A的总需求，所以可以认为相应的直接生产成本是一个常数， 因此就不予考虑了。贝要理解了我们下面魂立代化模型的过程和思想，对于放松这些假 定条件以后的情形， 也是很容易类似地建立优化模型的 (2)符号说明 为了建立这类问题的一般模型，我们定义如下数学符号： N:生产项目总数（本例中N=7): T:计划期长度（本例中T=6): K:瓶颈资源种类数（本例中K=1)为 -387
-387- 生产能力非常紧张，具体可供能力如表 1 第 3 行所示（第 2 周设备检修，不能使用）。B,C 的能力消耗系数分别为 5 和 8，即生产 1 件 B 需要占用 5 个单位的能力，生产 1 件C 需 要占用 8 个单位的能力。 表 1 生产计划的原始数据 周次 1 2 3 4 5 6 A 的外部需求 40 0 100 0 90 10 瓶颈能力 10000 0 5000 5000 1000 1000 零件编号 A B C D E F G 生产准备费用 400 500 1000 300 200 400 100 单件库存费用 12 0.6 1.0 0.04 0.03 0.04 0.04 对于每种零部件或产品，如果工厂在某一周订购或者生产该零部件或产品，工厂 需要一个与订购或生产数量无关的固定成本（称为生产准备费用）；如果某一周结束时 该零部件或产品有库存存在，则工厂必须付出一定的库存费用（与库存数量成正比）。 这些数据在表 1 第 5 、6 行给出。 按照工厂的信誉要求，目前接收的所有订单到期必须全部交货，不能有缺货；此 外，不妨简单地假设目前该企业没有任何零部件或产品库存，也不希望第 6 周结束后留 下任何零部件或产品库存。最后，假设不考虑生产提前期，即假设当周采购的零件马上 就可用于组装，组装出来的部件也可以马上用于当周组装成品 A 。 在上述假设和所给数据下，如何制定未来 6 周的生产计划。 1.2 建立模型 （1）问题分析 这个实例考虑的是在有限的计划期内，给定产品结构、生产能力和相关费用及零 部件或成品（以下统称为生产项目）在离散的时间段上（这里是周，也可以是天、月等） 的外部需求之后，确定每一生产项目在每一时间段上的生产量（即批量），使总费用最 小。由于每一生产项目在每一时间段上生产时必须经过生产准备（setup），所以通常的 讨论中总费用至少应考虑生产准备费用和库存费用。其实，细心的读者一定会问：是否 需要考虑生产的直接成本（如原材料成本、人力成本、电力成本等）？这是因为本例中 假设了不能有缺货发生，且计划初期和末期的库存都是 0，因此在这个 6 周的计划期内 A 的总产量一定正好等于 A 的总需求，所以可以认为相应的直接生产成本是一个常数， 因此就不予考虑了。只要理解了我们下面建立优化模型的过程和思想，对于放松这些假 定条件以后的情形，也是很容易类似地建立优化模型的。 （2）符号说明 为了建立这类问题的一般模型，我们定义如下数学符号： N ：生产项目总数（本例中 N = 7）； T ：计划期长度（本例中T = 6 ）； K ：瓶颈资源种类数（本例中 K =1）；
M:一个充分大的正数，在模型中起到使模型线性化的作用： d:项目1在1时段的外部需求（本例中只有产品A有外部需求）： X:项目1在1时段的生产批量： 1,:项目1在1时段的库存量： y:项目i在1时段是否生产的标志(0：不生产，1：生产)： S():产品结构中项目i的直接后继项目集合 :产品结构中项目了对项目i的消耗系数： S:项目1在1时段生产时的生产准备费用： h,:项目1在1时段的单件库存费用： C:资源k在1时段的能力上限； a:项目i在1时段生产时，生产单个项目占用资源k的能力： 在上述数学符号中，只有X,I,Y为决策变量，其余均为已知的计划参数。 其实，真正的生产计划只是要求确定X就可以了，因为知道X,以后1，Y,也就 自然确定了。另外，在我们的具体例子中参数s,h,au其实只与项目i有关，而 不随时段1变化，我们这里加上下标1只是为了使模型能够更一般化。 (3)目标函数 这个问题的目标是使生产准备费用和库存费用的总和最小。因此，目标函数应该 是每个项目在每个阶段上的生产准备费用和库存费用的总和，即 22,+A,n (1) (4)约束条件 这个问题中的约束有如下儿类：每个项目的物流应该守恒、资源能力限制应该满 足、每时段生产某项目前必须经过生产准备和非负约束（对y,是0-1约束）。 所谓物流守恒，是指对每个时段、每个项目（图中一个节点）而言，该项目在上
-388- M ：一个充分大的正数，在模型中起到使模型线性化的作用； di,t ：项目i 在t 时段的外部需求（本例中只有产品 A 有外部需求）； Xi,t ：项目i 在t 时段的生产批量； i t I , ：项目i 在t 时段的库存量； Yi,t ：项目i 在t 时段是否生产的标志（0：不生产，1：生产）； S(i) ：产品结构中项目i 的直接后继项目集合； i j r, ：产品结构中项目 j 对项目i 的消耗系数； i t s , ：项目i 在t 时段生产时的生产准备费用； hi,t ：项目i 在t 时段的单件库存费用； Ck ,t ：资源 k 在t 时段的能力上限； ak ,i,t ：项目i 在t 时段生产时，生产单个项目占用资源 k 的能力； 在上述数学符号中，只有 Xi,t ， i t I , ，Yi,t 为决策变量，其余均为已知的计划参数。 其实，真正的生产计划只是要求确定 Xi,t 就可以了，因为知道 Xi,t 以后 i t I , ，Yi,t 也就 自然确定了。另外，在我们的具体例子中参数 i t s , ，hi,t ，ak ,i,t 其实只与项目i 有关，而 不随时段t 变化，我们这里加上下标t 只是为了使模型能够更一般化。 （3）目标函数 这个问题的目标是使生产准备费用和库存费用的总和最小。因此，目标函数应该 是每个项目在每个阶段上的生产准备费用和库存费用的总和，即 ∑∑= = + N i T t i t i t i t i t s Y h I 1 1 , , , , ( ) （1） （4）约束条件 这个问题中的约束有如下几类：每个项目的物流应该守恒、资源能力限制应该满 足、每时段生产某项目前必须经过生产准备和非负约束（对Yi,t 是0 −1约束）。 所谓物流守恒，是指对每个时段、每个项目（图中一个节点）而言，该项目在上
一个时段的库存量加上当前时段的生产量，减去该项目当前时段用于满足外部需求的量 和用于组装其它项目（直接后继项目）的量，应当等于当前时段的库存量。具体可以写 成如下表达式（假设1。=0）： 1+X-1u=d,+∑Xn i=1,2,.,N,t=12,.,T (2) 资源能力限制比较容易理解，即 含uCw.k=l2nk.1=2T (3) 每时段生产某项目前必须经过生产准备，也就是说当X,=0时Y,=0:X,>0 时y,=1。这本来是一个非线性约束，但是通过引入参数M(很大的正数，表示每个 项目每个时段的最大产量)可以化成线性约束，即 0sXu≤MY,ye{01,i=12.,N,1=1,2,.,T (4) 另外有 120,1=1,2,.,N,1=l,2.,T, (5) 总结上面的讨论，这个问题的优化模型就是在约束(2)、(4)下使目标函数(1) 达到最小，这可以认为是一个混合整数规划模型（因为产量一般较大，可以把X和/ 看成连续变量（实数）求解，而只有Y,为0-1变量) 13求解模型 本例中生产项目总数N=7(分别用1~7表示项目A,B,C,D,E,F,G),计划期 长度T=6(周)，瓶颈资源种类数K=1。只有A有外部需求，所以d,中只有d可 以取非零需求，即表1中的第2行的数据，其它d,全部为零。参数5，h,只与项目 1有关，而不随时段1变化，所以可以略去下标1，其数值就是表1中的最后两行数据 由于只有一种资源，参数C,可以略去下标k,其数值就是表1中的第3行的数据：而 a只与项目i有关，而不随时段1变化，所以可以同时略去下标k和1，即a=5, -389
-389- 一个时段的库存量加上当前时段的生产量，减去该项目当前时段用于满足外部需求的量 和用于组装其它项目（直接后继项目）的量，应当等于当前时段的库存量。具体可以写 成如下表达式（假设 Ii,0 = 0 ）： j t j S i Ii t Xi t Ii t di t rij X , ( ) , 1 , , , ∑∈ − + − = + i = 1,2,L,N ，t = 1,2,L,T （2） 资源能力限制比较容易理解，即 i t k t N i ak i t X , C , 1 ∑ , , ≤ = ，k = 1,2,L,K ，t = 1,2,L,T （3） 每时段生产某项目前必须经过生产准备，也就是说当 Xi,t = 0 时Yi,t = 0；Xi,t > 0 时Yi,t = 1。这本来是一个非线性约束，但是通过引入参数 M （很大的正数，表示每个 项目每个时段的最大产量）可以化成线性约束，即 0 ≤ Xi,t ≤ MYi,t ， {0,1} Yi,t ∈ ，i = 1,2,L, N ，t = 1,2,L,T （4） 另外有 Ii,t ≥ 0 ，i = 1,2,L,N ，t = 1,2,L,T ， （5） 总结上面的讨论，这个问题的优化模型就是在约束（2）~（4）下使目标函数（1） 达到最小。这可以认为是一个混合整数规划模型（因为产量一般较大，可以把 Xi,t 和 i t I , 看成连续变量（实数）求解，而只有Yi,t 为0 −1变量）。 1.3 求解模型 本例中生产项目总数 N = 7（分别用 1～7 表示项目 A, B,C, D, E, F,G ），计划期 长度T = 6 （周），瓶颈资源种类数 K =1。只有 A 有外部需求，所以 di,t 中只有 d1,t 可 以取非零需求，即表 1 中的第 2 行的数据，其它 di,t 全部为零。参数 i t s , ，hi,t 只与项目 i 有关，而不随时段t 变化，所以可以略去下标t ，其数值就是表 1 中的最后两行数据。 由于只有一种资源，参数Ck ,t 可以略去下标 k ，其数值就是表 1 中的第 3 行的数据；而 ak ,i,t 只与项目i 有关，而不随时段t 变化，所以可以同时略去下标 k 和t ，即 5 a2 =
a,=8(其它a,为0)。从图1中容易得到项目i的直接后继项目集合S(①和消耗系数 对本例，A的外部总需求为240，所以任何项目的产量不会超过 240×7×15=25000(从图1可以知道，这里7×15已经是每件产品A对任意一个项 目的最大的消耗系数了)，所以取M-25000就已经足够了， MODEL: TITL瓶颈设备的多级生产计划 SETS: !PART=项目集合，Setup=生产准备费，Ho1d=单件库存成本 A=对瓶预资源的消耗系数： PART/A B C D E F G/:Setup,Hold,A; !TME-计划期集合，Capacity-瓶颈设备的能力 TIME/1.6/:Capacity !SES=项目结构关系，Rq=项目之间的消耗系数 USES (PART,PART):Reg; !PXT=项目与时间的派生集合，De西and=外部需求， x=产量（批量），Y=0/1变量，V=库存： PXT (PART,TIME)Demand,X,Y,Inv; ENDSETS !目标函数： [OBJ]Min=@sum(PXT(i,t):setup(i)*Y(i,t)+hold(i)*Inv(i,t)); ！物流平衡方程： CFOR(PXT(i,七)I七#NE# 1:[Bal]Inv(i,t-1)+X(i,t)-Inv(i,t)=Demand(i,t)+@SUM(USES(,j):Req 1,j)*x(,t)1) @FOR(PXT(i,t)It #eg# 1:[Ba0]x(i,t)-Inv(i,t)=Demand (i,t)+@SUM(USES (i,j):Reg(i,j)*x(j,t) 能力约束 @FOR(TIME (t):[Cap]@SUM(PART(i):A(i)*x(i,t))<Capacity(t)); !其他约束 M=25000; @FOR(PXT(i,t):x(i,t)<=M*Y(i,t)); @FOR(PXT:@BIN(Y)); DATA: Demand=0;Req =0 Capac1ty=1000005000500010001000 390-
-390- a3 = 8 （其它 ai 为 0）。从图 1 中容易得到项目i 的直接后继项目集合 S(i) 和消耗系数 i j r, 。 对本例， A 的外部总需求为 240 ，所以任何项目的产量不会超过 240× 7 ×15 = 25000 （从图 1 可以知道，这里7 ×15已经是每件产品 A 对任意一个项 目的最大的消耗系数了），所以取 M = 25000 就已经足够了。 MODEL: TITLE 瓶颈设备的多级生产计划; SETS: ! PART=项目集合,Setup=生产准备费，Hold=单件库存成本， A=对瓶颈资源的消耗系数; PART/A B C D E F G/:Setup,Hold,A; ! TIME=计划期集合，Capacity=瓶颈设备的能力; TIME/1.6/:Capacity; ! USES=项目结构关系，Req=项目之间的消耗系数; USES(PART,PART):Req; ! PXT=项目与时间的派生集合，Demand=外部需求, X=产量（批量）, Y=0/1变量，INV=库存; PXT(PART,TIME):Demand,X,Y,Inv; ENDSETS ! 目标函数; [OBJ]Min=@sum(PXT(i,t):setup(i)*Y(i,t)+hold(i)*Inv(i,t)); ! 物流平衡方程; @FOR(PXT(i,t)|t #NE# 1:[Bal]Inv(i,t-1)+X(i,t)-Inv(i,t)=Demand(i,t)+@SUM(USES(i,j):Req( i,j)*X(j,t))); @FOR(PXT(i,t)|t #eq# 1:[Ba0]X(i,t)-Inv(i,t)=Demand(i,t)+@SUM(USES(i,j):Req(i,j)*X(j,t) )); ! 能力约束; @FOR(TIME(t):[Cap]@SUM(PART(i):A(i)*X(i,t))<Capacity(t)); ! 其他约束; M = 25000; @FOR(PXT(i,t):X(i,t)<=M*Y(i,t)); @FOR(PXT:@BIN(Y)); DATA: Demand=0;Req =0; Capacity=10000 0 5000 5000 1000 1000;