算法大全第27章__生产与服务运作管理中的优化问题

《算法大全第27章__生产与服务运作管理中的优化问题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二十七章生产与服务运作管理中的优化问题本章主要介绍生产和服务运作管理方面的一些优化问题。实际上，生产和服务运作管理的内容也是非常丰富的，几乎包含了企业管理的所有方面，本章中只是介绍几个实例而已。§1有瓶颈设备的多级生产计划问题1.1问题实例在制造企业的中期或短期生产计划管理中，常常要考虑如下的生产计划优化问题：在给定的外部需求和生产能力等限制条件下，按照一定的生产目标（通常是生产总费用最小）编制未来若干个生产周期的最优生产计划，这种问题在文献上一般称为批量问题（lotsizingproblems）。所谓某一产品的生产批量（lotsize），就是每通过一次生产准备

2、生产该产品时的生产数量，它同时决定了库存水平。由于实际生产环境的复杂性，如需求的动态性，生产费用的非线性，生产工艺过程和产品网络结构的复杂性，生产能力的限制，以及车间层生产排序的复杂性等，批量问题是一个非常复杂、非常困难的问题。我们通过下面的具体实例来说明这种多级生产计划问题的优化模型。这里“多级”的意思是需要考虑产品是通过多个生产阶段（工艺过程）生产出来的。例1某工厂的主要任务是通过组装生产产品A，用于满足外部市场需求。产品A的构成与组装过程见图1，即D,E,F,G是从外部采购的零件，先将零件D,E组装成部件B，零件F,G组装成部件C，然后将部件B,C组装成产品

3、A出售。图中弧上的数字表示的是组装时部件（或产品）中包含的零件（或部件）的数量（可以称为消耗系数），例如DB弧上数字“9”表示组装1个部件B需要用到9个零件D；BA弧上的数字“5”表示组装1件产品A需要用到5个部件B；依此类推。图1产品构成与组装过程图假设该工厂每次生产计划的计划期为6周（即每次制定未来6周的生产计划），只有最终产品A有外部需求，目前收到的订单的需求件数按周的分布如表1第2行所示。部件B,C是在该工厂最关键的设备（可以称为瓶颈设备）上组装出来的，瓶颈设备的-386-生产能力非常紧张，具体可供能力如表1第3行所示（第2周设备检修，不能使用）。B,C的

4、能力消耗系数分别为5和8，即生产1件B需要占用5个单位的能力，生产1件C需要占用8个单位的能力。表1生产计划的原始数据周次123456A的外部需求40010009010瓶颈能力1000005000500010001000零件编号ABCDEFG生产准备费用4005001000300200400100单件库存费用120.61.00.040.030.040.04对于每种零部件或产品，如果工厂在某一周订购或者生产该零部件或产品，工厂需要一个与订购或生产数量无关的固定成本（称为生产准备费用）；如果某一周结束时该零部件或产品有库存存在，则工厂必须付出一定的库存费用（与库存数量

5、成正比）。这些数据在表1第5、6行给出。按照工厂的信誉要求，目前接收的所有订单到期必须全部交货，不能有缺货；此外，不妨简单地假设目前该企业没有任何零部件或产品库存，也不希望第6周结束后留下任何零部件或产品库存。最后，假设不考虑生产提前期，即假设当周采购的零件马上就可用于组装，组装出来的部件也可以马上用于当周组装成品A。在上述假设和所给数据下，如何制定未来6周的生产计划。1.2建立模型（1）问题分析这个实例考虑的是在有限的计划期内，给定产品结构、生产能力和相关费用及零部件或成品（以下统称为生产项目）在离散的时间段上（这里是周，也可以是天、月等）的外部需求之后，确定每

6、一生产项目在每一时间段上的生产量（即批量），使总费用最小。由于每一生产项目在每一时间段上生产时必须经过生产准备（setup），所以通常的讨论中总费用至少应考虑生产准备费用和库存费用。其实，细心的读者一定会问：是否需要考虑生产的直接成本（如原材料成本、人力成本、电力成本等）？这是因为本例中假设了不能有缺货发生，且计划初期和末期的库存都是0，因此在这个6周的计划期内A的总产量一定正好等于A的总需求，所以可以认为相应的直接生产成本是一个常数，因此就不予考虑了。只要理解了我们下面建立优化模型的过程和思想，对于放松这些假定条件以后的情形，也是很容易类似地建立优化模型的。（2

7、）符号说明为了建立这类问题的一般模型，我们定义如下数学符号：N：生产项目总数（本例中N=7）；T：计划期长度（本例中T=6）；K：瓶颈资源种类数（本例中K=1）；-387-M：一个充分大的正数，在模型中起到使模型线性化的作用；d：项目i在t时段的外部需求（本例中只有产品A有外部需求）；i,tX：项目i在t时段的生产批量；i,tI：项目i在t时段的库存量；i,tY：项目i在t时段是否生产的标志（0：不生产，1：生产）；i,tS(i)：产品结构中项目i的直接后继项目集合；r：产品结构中项目j对项目i的消耗系数；i,js：项目i在t时段生产时的生产准备费用；i,th：项

8、目i在t时