有瓶颈设备的多级生产计划问题课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,优化建模,5.2 有瓶颈设备的多级生产计划问题,5.2 有瓶颈设备的多级生产计划问题,1,5.2.1 问题实例,在给定的外部需求和生产能力等限制条件下，按照生产总费用最小编制未来若干个生产周期的最优生产计划，这种问题在文献上一般称为批量问题（Lotsizing Problems）。,我们通过下面的具体例子来说明这种多级生产计划问题的优化模型。这里“多级”的意思是需要考虑产品是通过多个生产阶段（工艺过程）生产出来的。,5.2.1 问题实例在给定的外部需求和生产能力等限制条件下,2,例5.2 某工厂的主要任务是通过组装生产产品A，用于满足外部市场需求。,A产品的产品构成与组装过程见图5-2：即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；,依此类推。,例5.2 某工厂的主要任务是通过组装生产产品A，用于满足外,3,瓶颈设备加工,A,B,C,D,E,F,G,5,7,9,11,13,15,图5-2 产品构成与组装过程图,瓶颈设备加工ABCDEFG579111315图5-2 产品构,4,表5-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,表5-1 生产计划的原始数据 周次123456A的外部需求4,5,假设该工厂每次生产计划的计划期为6周（即每次制定未来6周的生产计划），只有最终产品A有外部需求，目前收到的订单的需求件数按周的分布如表5-1第2行所示。部件B、C是在该工厂最关键的设备（可以称为瓶颈设备）上组装出来的，瓶颈设备的生产能力非常紧张，具体可供能力如表5-1第3行所示（第2周设备检修，不能使用）。B、C的能力消耗系数分别为5和8，即生产1件B需要占用5个单位的能力，即生产1件C需要占用8个单位的能力。,对于每种零部件或产品，如果工厂在某一周订购或者生产该零部件或产品，工厂需要付出一个与订购或生产数量无关的固定成本（称为生产准备费用）；如果某一周结束时该零部件或产品有库存存在，则工厂必须付出一定的库存费用（与库存数量成正比）。这些数据在表5-1第5、6行给出。,假设该工厂每次生产计划的计划期为6周（即每次制定未来6周的生,6,按照工厂的信誉要求，目前接收的所有订单到期必须全部交货，不能有缺货发生；此外，不妨简单地假设目前该企业没有任何零部件或产品库存，也不希望第6周结束后留下没有任何零部件或产品库存。最后，假设不考虑生产提前期，即假设当周采购的零件马上就可用于组装，组装出来的部件也可以马上用于当周组装成品A。,在上述假设和所给数据下，如何制定未来6周的生产计划？,按照工厂的信誉要求，目前接收的所有订单到期必须全部交货，不能,7,5.2.2 建立模型,问题分析 这个例子考虑的是在有限的计划期内,给定产品结构、生产能力和相关费用及零部件或成品（以下统称为生产项目）在离散的时间段上（这里是周，也可以是天、月等）的外部需求之后,确定每一生产项目在每一时间段上的生产量(即批量),使总费用最小.由于每一生产项目在每一时间段上生产时必须经过生产准备(Setup),所以通常的讨论中总费用至少应考虑生产准备费用和库存费用.,其实，细心的读者一定会问：是否需要考虑生产的直接成本（如原材料成本、人力成本、电力成本等）？,5.2.2 建立模型,8,符号说明,为了建立这类问题的一般模型，我们定义如下数学符号：,N-生产项目总数（本例中N=7）;,T-计划期长度（本例中T=6）;,K-瓶颈资源种类数（本例中K=1）;,M-一个充分大的正数，在模型中起到使模型线性化的作用;,符号说明,9,-项目,i,在,t,时段的外部需求,（本例中只有产品A有外部需求）;,-项目,i,在,t,时段的生产批量;,-项目,i,在,t,时段的库存量;,-项目,i,在,t,时段是否生产的标志,(0：不生产,1：生产);,-产品结构中项目,j,对项目,i,的消耗系数;,S,(,i,)-产品结构中项目,i,的直接后继项目集合;,-项目i在t时段的外部需求-项目i在t,10,-项目,i,在,t,时段生产时的生产准备费用;,-项目,i,在,t,时段的单件库存费用;,-资源,k,在,t,时段的能力上限;,-项目,i,在,t,时段生产时,生产单个产品占用资源,k,的能力;,(,x,)-这个函数当且仅当,x,0时取值1,否则取值0.,在上述数学符号中，只有,为决策变量,;,其余均为已知的计划参数。,-项目i在t时段生产时的生产准备费用;,11,有瓶颈设备的多级生产计划问题课件,12,目标函数,这个问题的目标是使生产准备费用和库存费用的总和最小。因此，目标函数应该是每个项目在每个时段上的生产准备费用和库存费用的总和，即,(28),约束条件,这个问题中的约束有这么几类：每个项目的物流应该守恒、资源能力限制应该满足、每时段生产某项目前必须经过生产准备和非负约束（对,Y,i,j,是0-1约束）。,目标函数 这个问题的目标是使生产准备费用和库存费用的总和最小,13,(29),资源能力限制比较容易理解，即,(30),所谓物流守恒（假设,I,i,0,=0）,(29)资源能力限制比较容易理解，即(30)所谓物流守恒（假,14,(31),每时段生产某项目前必须经过生产准备，也就是说当,X,it,=0时,Y,it,=0；,X,it,0时,Y,it,=1。这本来是一个非线性约束，但是通过引入参数,M,（很大的正数，表示每个项目每个时段的最大产量）可以化成线性约束，即：,总结:这个问题的优化模型就是在约束（29）（30）（31）下使目标函数（28）达到最小。,(31)每时段生产某项目前必须经过生产准备，也就是说当Xit,15,5.2.3 求解模型,本例生产项目总数,N,=7(A、B、C、D、E、F、G)，计划期长度,T,=6（周），瓶颈资源种类数,K,=1。只有A有外部需求，所以,d,i,t,中只有,d,1,t,可以取非零需求，即表5-1中的第2行的数据，其他全部为零。参数,s,i,t,、,h,i,t,只与项目,i,有关，而不随时段,t,变化，所以可以略去下标,t,，其数值就是表5-1中的最后两行数据。,由于只有一种资源，参数,C,k,t,可以略去下标,k,，其数值就是表5-1中的第3行的数据；而,a,k,I,t,只与项目,i,有关，而不随时段,t,变化，所以可以同时略去下标,k,和,t,，即,a,2,=5，,a,3,=8（其他,a,i,为0）。从图6-2中容易得到项目,i,的直接后继项目集合,S,(,i,)和消耗系数。,5.2.3 求解模型本例生产项目总数N=7(A、B、C、D,16,准备以下的数据文件（文本文件exam0502.LDT，可以看到其中也可以含有注释语句）：,!项目集合;,ABCDEFG,!计划期集合;,123456,!需求;,40010009010,0 0 0 0 0 0,0 0 0 0 0 0,0 0 0 0 0 0,0 0 0 0 0 0,0 0 0 0 0 0,0 0 0 0 0 0,准备以下的数据文件（文本文件exam0502.LDT，可以看,17,!能力;,1000005000500010001000,!生产准备费;,4005001000300200400100,!库存费;,120.61.00.040.030.040.04,!对能力的消耗系数；,0580000,!能力;,18,!项目间的消耗系数:req(i,j)表示j用到多少i;,0 0 0 0 0 0 0,5 0 0 0 0 0 0,7 0 0 0 0 0 0,0 9 0 0 0 0 0,0 11 0 0 0 0 0,0 0 13 0 0 0 0,0 0 15 0 0 0 0,!数据结束;,!项目间的消耗系数:req(i,j)表示j用到多少i;,19,对本例，A的外部总需求为240，所以任何项目的产量不会超过24071525000（从图6-2可以知道，这里715已经是每件产品A对任意一个项目的最大的消耗系数了），所以取M=25000就已经足够了。,本例中的具体模型可以如下输入LINGO软件：,MODEL:,TITLE 瓶颈设备的多级生产计划;,!从文本文件exam0502.LDT中读取数据;,对本例，A的外部总需求为240，所以任何项目的产量不会超过2,20,SETS:,!PART=项目集合,Setup=生产准备费，Hold=单件库存成本，,A=对瓶颈资源的消耗系数;,PART/FILE(exam0502.LDT)/:Setup,Hold,A;,!TIME=计划期集合，Capacity=瓶颈设备的能力;,TIME/FILE(exam0502.LDT)/:Capacity;,!USES=项目结构关系，Req=项目之间的消耗系数;,USES(PART,PART):Req;,!PXT=项目与时间的派生集合，Demand=外部需求,X=产量（批量）,Y=0/1变量，INV=库存;,PXT(PART,TIME):Demand,X,Y,Inv;,ENDSETS,SETS:,21,!目标函数;,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);,!目标函数;,22,!其他约束;,M=25000;,FOR(PXT(i,t):X(i,t)=M*Y(i,t);,FOR(PXT:BIN(Y);,DATA:,Demand=FILE(exam0502.LDT);,Capacity=FILE(exam0502.LDT);,Setup=FILE(exam0502.LDT);,Hold=FILE(exam0502.LDT);,A=FILE(exam0502.LDT);,Req=FILE(exam0502.LDT);,ENDDATA,END,注意：由于本例有42个0-1变量，LINGO演示版是无法求解的,!其他约束;注意：由于本例有42个0-1变量，LINGO演,23,表,5,-2,生产计划的最后结果,周次,1,2,3,4,5,6,A,的产量,40,100,100,B,的产量,200,1000,C,的产量,1055,625,D,的产量,1800,9000,E,的产量,2200,11000,F,的产量,13715,8125,G,的产量,15825,9375,LINDO求解:得到最优目标函数值为9245,结果如下：,表5-2 生产计划的最后结果 周次123456A的产量401,24,