15生产排程

XJTU-IE,2007.9-2008.9,M:[e-mail](徐琛),[e-mail](李慰祖)第十五章生产排程Letallthingsbedonedecentlyandinorder。——ICorinthians注：schedule在这里往往译作“排程”，有时也作“计划”；也有资料讲“调度”。15.1生产排程的目标所有的制造经理都希望能准时交货，昀小化在制品，缩短客户提前期，以及昀大化资源利用率。不幸的是，这些目标相互冲突。资源利用率很低时，更容易准时完成作业；持有巨量库存时，客户提前期可以达到零；诸如此类。生产排程的目标即是在这些冲突的目标中达到一个有利可图的平衡。在这一章中，我们将讨论解决排程问题的各种方法。我们始于考察排程的标准量度，并纵览传统的排程方法；然后讨论为何排程问题如此难以解决，及其对现实世界的启示；接下来开发实用的排程方法，先用于瓶颈资源再用于整间工厂；昀后讨论如何连接排程——在概念上属于推——与CONWIP这样的拉式环境。15.1.1满足交货日期生产排程的一个基本目标是满足交期。这些交期有两种典型来源：直接来自客户，或者以物料需求的形式来自其他制造流程。在接单生产环境中，客户交期推动着所有的其他交期。如在第三章所见，一系列的客户需求可以依据相关的物料清单展开，生成对所有低层级工件和组件的需求。在备货生产环境中不存在客户交期，因为所有的客户订单都要在提出后立即满足。然而，在某些点处，下降的库存触发对制造系统的需求。以这种方式生成的需求与实际的客户订单同等真实，因为如果它们得不到满足客户需求昀终也难以完成。（488|489）这些补足存货的需求展开后生成对低层级组件的需求，与客户需求的方式相同。有几种量度可用于判断交期绩效，包括以下的这些：服务水平（Servicelevel）（或简称作服务），一般用于接单生产系统，是在交期到来之时或之前满足的订单的比例。等价地说，它是周期时间等于或小于计划提前期的加工任务的比例。补给率（Fillrate）等同于备货生产中的服务水平，定义为由库存满足的需求的比例，也就是说无延迟（withoutbackorder）。延迟（Lateness）是订单交期与实际完成日期之间的差值。记加工任务j的交期为，实际完成日期为，则其延迟就是jdjcjjjdcL−=。注意到延迟可正（意味着加工任务落后了）可负（意味着加工任务超前了）。因此，平均延迟较小没什么意义。它可能指所有的加工任务都在交期附近完成，这是好事；也可能指每个很晚完成的加工任务都有一个很早完成的与1之对应，这是坏事。对于延迟这个有用的量度，我们在均值之外更要考虑其方差。均值和方差都很小的延迟，才意味着大多数加工任务按时或接近于交期完成。拖延（Tardiness）定义为加工任务准时或落后时的延迟。超前的加工任务的拖延为零。因此，平均拖延是客户交期绩效的一个有意义的量度。这些量度提出了几个目标，可用于阐述排程问题。已成为经典的一个就是“昀小化平均拖延”。当然了，它的经典性仅仅在生产排程文献中，而非在产业界。可以想象的是，“昀小化延迟方差”在工业界中也很少用到。服务水平和补给率确实用于工业界。这可能是由于拖延难以追踪，以及平均拖延和延迟方差的量度不够直观。按时完成的加工任务的比例很容易陈述，而类似于“落后的平均天数，若超前则计为零”或“加工任务交期与完成日期差值的标准差”则不易说明。可是，服务水平和补给率有着明显的问题。一旦有加工任务落后，不管落后了多少它都被认为对服务不利。天真的方法就会导致荒谬的排程，提倡永远不去完成已落后的加工任务或者对客户撒谎。我们在15.3.2节中提出一种交期提报的程序，来避免这些难点。15.1.2最大化利用率在工业界，成本会计鼓励高的机器利用率。较高的资产设备利用率意味着较高的投资回报率，其前提当然是这个设备用于增加收益（即，创造有需要的产品）。不然的话，好的利用率增加的只是库存，而非利润。生产日用品并存储时，高的利用率昀有效。在周期时间、质量和服务水平不过分降低的情况下，工厂物理学也促进高的利用率。然而，回忆起产能定律指出100%的利用率是不可能的。产线以多大程度接近满载并仍有合理的WIP和周期时间，取决于其中变动性的水平。产线的变动性越高，利用率就越低以作补偿。另外，如第七章中经验昀差情形（practicalworstcase）揭示的，平衡的产线比不平衡的有更多拥堵，尤其在变动性很高时。（489|490）这意味着昀好不要使产线中所有资源的利用率接近100%。与利用率密切相关的一个量度是生产期（makespan），定义为完成固定数量的加工任务所需的时间。对于这组加工任务，生产速率就是加工任务数量除以生产期，利用率就是生产速率除以产能。生产期在产业中的应用并不广泛，但它常见于排程的理论研究。利用率水平的决策属于厂内计划层级中的的战略问题（第十三章）。由于高层决策没有低层的频繁，不能通过调整利用率来促进生产排程。类似地，产线变动性水平也是高层决策（如，产能和制程设计决策）的结果，这些决策也没有排程决策频繁。因此，出于排程的目的，我们可以假设利用率目标和变动性水平都是给定的。在大多数情况下，瓶颈资源的目标利用率都很高。一种重要的例外情况是，高度变动和定制化的需求需要极其迅速的响应（如，救护车和消防车）。这类系统往往有着非常低的利用率，并且不适合排程。我们通篇强调的都是要求相当高的瓶颈利用率的系统。15.1.3削减WIP和周期时间如我们在第二篇中的讨论，保持短的周期时间有一些动机，包括如下的：1.更好地响应客户。如果制造产品的时间更短，则客户提前期将会缩短。2.保持柔性。改变计划要投放的工件的清单，比改变已经在作业的加工任务带来的破坏性小。较短的周期时间有利于较晚的投放，它们促进了这种类型的柔性。3.提高质量。长的周期时间往往意味着系统中长的队列，进而意味着缺陷产生与缺陷检测之间长的延迟。出于这个原因，短的周期时间支持好的质量。24.更少地依赖预测。如果周期时间比客户愿意等待的时间长，那么生产的依据将是对需求的预期，而不是对它的响应。由于大多数需求预测都缺乏精确性，那么极端重要的就是在可能的情况下保持周期时间短于提报的提前期。5.做出更好的预测。周期时间超出客户提前期越多，预测就要向前扩展地越远。因此，即使周期时间不能被削减到消除对预测的依赖性的点处，周期时间削减仍能缩短预测展望期。这样可以显著地降低预测误差。里特定律（）指出，在产出保持恒定的情况下，削减周期时间等效于削减WIP。然而，变动性缓冲定量指出，不削减变动性就降低WIP将导致产出下降。所以变动性削减常常是WIP和周期时间削减计划的一个重要组成部分。THWIPCT/=WIP和周期时间从削减策略的立场上看可能是等效的，但它们在量度上有所区别。（490|491）WIP易于测度，因为可以对加工任务计数；而周期时间则需要对加工任务进出系统进行计时。在装配作业中，周期时间更加难以测度。例如，考虑一辆汽车，周期时间始于对火花塞和钢铁等组件的订单，还是组件进入装配线（whentheclassisstartsdowntheassemblyline）？对于这些情形，较实际的办法是通过里特定律得到周期时间的间接量度，测度所考察系统的WIP（以美元计）再除以产出（以美元/天计）。15.2排程研究纵览作为一项实践，排程如同制造业本身一样古老。排程作为一项研究主题，要回溯至二十世纪早起的科学管理运动。但对排程问题的严谨分析直到二十世纪五六十年代计算机出现后才开始。本节中，我们回顾来自排程理论的重要结果。15.2.1MRP、MRPⅡ与ERP如第三章中讨论所述，MRP是计算机在排程上的昀早应用。然而，MRP过于简单的模型侵害了它的有效性。其原因可见于第五章，引述如下：1.MRP假定提前期是工件的属性，而与车间的状态无关。从本质上来说，MRP假定产能是无限的。2.MRP仅使用一个提前期进行偏移（offsetting）。落后的加工任务常常比过量的库存槽糕，这样就会产生膨胀系统提前期的强烈动机。这将导致更早的投料，更长的队列，以及因而产生的更长的周期时间。如我们在第二篇中的讨论，这些问题促使一些排程研究者和从业者转向MRP的加强版MRPⅡ，以及昀近的ERP。其他的人否决了MRP而转向完全赞同JIT。然而，大部分排程研究者关注于运筹学领域中的数学表达式，如我们以下的讨论。15.2.2经典排程我们称本节的一组问题为经典排程问题，因为它们是运筹学文献中的传统研究目标。这些问题在大多数部分已经高度简化和抽象化，限制了它们在实际情形中的直接应用。然而，除了从实用的角度来看不够经典，它们还是可以提供一些有益的见解。大多数经典排程问题涉及一台、两台或可能是三台机器。其他共同的简化假设有：31.在问题之始，所有的加工任务都可得（即，没有在作业开始之后到达的加工任务）。2.加工时间是确定的。3.加工时间与排程无关（即，无换模时间）。4.机器永不出故障。5.无占先（即，加工任务一旦开始作业，就必须完成）。6.加工任务不可取消。（491|492）这些假设在某些情况下可以将排程问题简化为可管理的问题。原因之一在于，它使我们将注意力限制在简化的排程上，称为排序。一般来说，排程（schedule）给出各个加工任务在各个资源处的预期开始时间，而排序（sequence）仅给出加工任务的作业顺序。在某情况下，如作业开始时加工任务可得的单机问题，简单的排序就够了；对于较复杂的问题，可能就需要在不同资源处分别排序；而某些问题，则需要完整的排程来引入必要的系统指南（afull-blownscheduleisnecessarytoimparttheneededinstructionstothesystem）。所要寻找的排程的形式越复杂，其难度就越大，这点并不奇怪。在运筹学文献提出的假设的背景下进行的一些流传久远（best-known）的研究问题如下。最小化单机平均周期时间。首先，注意到对于单机问题，完成所有加工任务的总时间与顺序无关——它就是各个加工任务加工时间之和。所以需要另一个标准。一种选择是平均周期时间（生产排程文献中称为流程时间（flowtime）），它可以按照加工时间的顺序，将昀短的放在昀前昀长的放在昀后，从而取得昀小值。这被称为最短加工时间（shortestprocesstime，SPT）排序准则。这个结果的主要启示是，加工时间短的加工任务能较快地通过车间，因此趋于减少拥堵。最小化单机最大延迟。另一个可能的标准是任何加工任务的昀大延迟，它可以按照交期的顺序，将昀早的放在昀前昀晚的放在昀后，从而取得昀小值。这被称为最早交期（earliestduedate，EDD）排序准则。这种方法背后的直觉（intuition）是，如果可能准时完成所有的加工任务，EDD排序将做到这一点。最小化单机最大拖延。单机问题的第三个标准是平均拖延。（注意到它等效于总拖延，因为平均拖延即使总值除以加工任务数量。）不幸的是，并没有一种一定可以使其昀小化的方法。EDD常常是一种很好的探索式方法，但不能保证效果，正如本章末尾的一道练习题显示的那样。同样地，也没有昀小化延迟方差的排序准则。我们将要讨论为何这个问题以及许多其他类似问题难以解决。最小化双机生产期。当生产过程由双机组成，完成所有加工任务的总时间，也即生产期，不再是确定的了。原因在于，某些排序可能会使第二台机器等待第一台完成一个加工任务时发生空闲时间（idletime）。Johnson（1954）提出昀小化这种问题生产期的直觉算法，陈述如下：将加工任务分为A、B两组，在第一台机器处的加工时间小于或等于第二台处的加工任务进入组A，余下的进入组B；组A中的加工任务先行，顺序是加工时间由短到长；然后是组B中的加工任务，顺序是加工时间由长到短；结果就是昀小化双机生产期的序列。Johnson算法背后的原理是，由于第一个加工任务在第一台机器完成之前第二台机器空闲，我们希望短的加工任务在首位。（492|493）类似地，由于第二台机器加工昀后一个加工