1.3 复杂制造系统的生产计划与调度
生产计划与调度是制造企业组织和管理车间级生产活动的关键核心，旨在通过合理规划生产任务并调配有限生产资源，在保证生产有序进行的同时，尽可能提高企业综合效益，在制造信息系统中处于承上启下的核心地位。从学术研究的角度看，生产计划与调度问题可以归结为组合优化问题，即从问题的所有可行解中求出最优解，属于一类具有非确定多项式难题（Non-deterministic Polynomial Hard，NP-hard或NPH）特性的典型复杂问题。从应用的角度看，生产计划与调度是企业生产经营活动的主要依据，并直接影响着生产的性能和效益。
1.3.1 生产计划与调度概念
生产计划与调度问题因其复杂性，在实际分析求解时，往往会根据研究的侧重或关注的因素不同，对其加以合理分解而形成若干子问题。
从时间性上考察，一般将实际运行前完成的优化决策称为计划（Planning），将随着生产过程的运行同时进行的优化决策称为调度（Scheduling）。生产计划又可根据时间粒度分为中期生产计划和短期生产计划（长期生产计划因归入上层企业级的决策而不属于本书讨论的范畴）。中期生产计划对应于车间级的生产计划，是根据上层计划下达的销售预测和销售订单，在考虑车间生产能力、生产负荷、产品交货要求、车间实时状态等多方面因素的情况下，给出的车间任务（主要包括产品生产任务和设备的配备安排）下达，计划周期稍长，一般以周为单位。短期生产计划也可称作车间作业计划，是根据中期生产计划下达的生产任务，在满足工艺和资源等相关约束条件下，通过确定各工序任务（作业）的加工设备和在相应设备上的加工顺序/加工开始时间等，使生产性能尽可能趋优。短期生产计划是在生产运行开始前完成的工序级的分配和序列执行方案，计划周期稍短，一般以天或班次为单位。
从空间性上考察，又可以分为投料控制、工件调度、设备维护调度等。投料控制决定产品原料投入生产系统进行生产的投放时间、数量和品种，旨在控制生产系统的在制品（Work in Process，WIP）水平，同时提高单位时间内生产线的产出。设备维护调度决定各个设备分别何时开始进入维护保养状态，以及维护的类型和时间等，通过对计划停机时间和非计划停机时间的折中优化，保证安全高效的设备运行。工件调度对每个进入系统的工件的每道加工工序进行详细安排，又可再进一步划分为工件派工（Dispatching）和工件排序（Sequencing），前者决定工件的某道加工工序由哪台或哪类设备进行加工；后者决定共同竞争加工资源的多个工件的先后加工顺序。
从资源特殊性上考察，还有诸如瓶颈设备调度、批加工设备调度、特殊集成设备调度等局部问题。瓶颈设备泛指制造系统中限制了整体“最大”能力的少数能力“最小”的关键性设备（组），因其决定着生产系统的生产节奏，往往被作为重点调度优化的对象。批加工设备是一类可以同时加工多个产品的设备，因其产能具有不确定性，其调度的求解也需要特殊对待。另外，对于特定的复杂制造系统，还有一些专门的集成设备，比如半导体制造系统中把多组晶圆加工模块和搬运系统有效组织为一体的集束型设备（Cluster Tool），虽然能够提高生产率、充分利用作业空间，但同时也带来了精确建模与分析的困难，从而通常作为一类特殊复杂问题而被深入研究。
上述生产计划与调度子问题虽然各有特点、各不相同，但都具有在约束条件下追求目标优化的共性模式，只不过每个子问题存在的环境条件、约束方式、优化目标不尽相同罢了。另外，在实际系统中，这些子问题也往往都是同时交叉存在的，因此分解后的有效集成也是达成生产计划与调度问题求解的关键。
对于本书讨论的复杂制造系统，因其具有规模大、多重入流程、约束复杂、不确定性强等特点，其生产计划与调度问题不仅有一般计划与调度问题普遍具有的NP-难特性，而且还需要面对由于复杂制造本身多重入、混合加工方式等特殊复杂性，相关的研究也一直备受关注。
1.3.2 中期生产计划问题与方法
中期生产计划需要为计划时段内的车间生产任务和车间资源安排做出合理规划，计划时段一般以周或天为单位。狭义的中期生产计划仅涉及车间生产任务的安排，也就是要确定计划时段内投入车间安排生产的产品类型、数量及相应的开始生产及计划完工时间，不涉及详细的设备机时及工件的加工工序。车间生产任务的安排其实是一个负荷与能力的匹配问题，所谓的车间生产能力，涉及可用于安排生产的设备、工具、工装、人员等多方面的资源。就设备而言，虽然其监测统计、维护保养、故障维修等管理活动一般由专门的设备管理系统负责，但其中决定生产能力并与正常生产直接相关的设备工作时间和非工作时间（包括维修保养时间）的规划，也可列入中期生产计划的范畴，本书采用这一观点，将中期生产计划扩展为投料控制（车间生产任务的投入安排）和设备维护调度（车间设备资源的安排）两部分。
早在1988年就有学者［11，12］从加工周期（Cycle Time）、成本（Cost）、库存（Inventory）和成品率（Yield）等角度论证了投料控制对复杂的可重入制造系统性能指标提升的重要性。解决投料控制的方法经历了从开环投料策略到闭环投料策略的发展过程。开环投料策略不考虑生产线的状态，按事先计划好的固定策略安排投料计划，且投料时间点也不会随着生产线状态的不同而改变。此类投料控制方法包括：统一投料法、固定时间间隔投料法、随机分布泊松流投料法、指数分布投料法等［13］。闭环投料策略通过监控生产线上的某一指标，根据实际生产线状态来对投料进行调整控制。此类投料控制方法包括：固定在制品数投料法（Constant WIP，CONWIP）［14，15］、避免饥饿投料法（Starvation Avoidance，SA）［16］、固定工作负荷投料法（Constant Load，CONLOAD）［17］等。
中期生产计划中考虑的设备维护调度主要指预防性维护，即在设备正常工作阶段，为减少和避免设备意外故障的发生，保证设备的安全可靠生产，对设备的维护时机（即预防性维护周期）提前做出的合理规划。主要的方法有基于役龄的维护计划、基于周期的维护计划、基于健康状况的维护计划。
基于役龄的维护方式是在设备累计运行时间达到预定的役龄（役龄为固定值）时安排维修；基于周期的维护方式通过统计数据或经验定期安排设备维修，根据决定周期的因素不同，又分为按加工时间的周期性维护（平均故障间隔时间，Mean Time between Failure，MTBF）、按加工数量的周期性维护（Unit Based Maintenance，UBM）计划；基于健康状况的维护计划是依据反映设备健康状况的信息来安排维护任务，比如基于性能参数的维护（Condition Based Maintenance，CBM）、基于设备故障预测与健康管理（Prognostics and Health Management，PHM）的维护计划。
在中期生产计划阶段形成的车间生产任务和设备维护任务下达到短期生产计划阶段后，都需要通过占用相应设备的时间来完成，这种生产/维护任务到设备时间在作业层面的合理优化就构成了短期生产计划阶段要重点解决的问题。
1.3.3 短期生产计划生产调度问题与方法
短期生产计划是依据中期生产计划下达的任务和当前车间制造资源状态，通过生产任务转换、作业排程等操作，制定一定生产周期内的车间作业计划。因其为实际生产开始前完成的优化作业执行方案，所以是一种“计划”，故称为短期生产计划；又因为决策的是车间作业计划中的各工作任务到各类制造资源的优化指派，所以也是一种“调度”，可以称其为生产作业调度，或生产调度。复杂制造系统的调度问题可以描述为在资源受限与能力约束条件下，针对一项可分解的生产任务，通过确定工件加工顺序和生产资源的分配等，获得生产任务执行效率或成本的优化。具体而言，调度是对一定时间范围内的工件集合，按照工艺流程要求的加工步骤（工序，Step）分解后，安排分解后的各工序在设备上的加工顺序，形成调度方案（Schedule），即确定所有工序由某台设备在某个确定的时间段内完成。生产资源安排的时间精度具体到小时、分钟甚至秒，具备明显的次序要求。
作为一项具有较长历史的研究命题，自20世纪50年代以来，关于生产调度的大量理论和应用研究使这一领域的模型和方法体系逐渐形成并完善。
在模型方面，早期针对多重入制造系统的调度模型主要是以排队论为基础的Kelly模型、Brawnian模型、连续流模型、马尔可夫模型等，但因其对实际系统过强的人为假设，以及无法克服系统复杂度带来的维数灾难，因此基本不具备实用性。另一类以离散事件动态系统理论为基础的调度模型，如Petri模型、离散事件仿真模型等，虽然能够较好地描述复杂制造系统动态、并发等特性，但因缺乏准确、及时的模型参数和对复杂生产系统不确定因素的快速反应等，而无法真正得到精度和应变力都满足实际要求的模型；近年来，随着信息技术的发展，特别是制造业信息化的普及，新的基于数据的生产调度建模方法被提出并日益得到重视。基于数据的调度建模涉及两方面含义：一方面是基于制造信息系统积累的大量离线和在线数据，运用数据挖掘等技术手段，建立生产调度过程的模型；另一方面是基于工业制造数据的生产调度模型的参数预测和在线调整，以增加模型的精度。
在方法方面也出现了运筹学方法（随机整数规划、动态规划等）、启发式方法（各类启发式调度规则）和智能方法（神经网络、遗传算法、蚁群算法等）等主要流派。传统运筹学方法在理论上能求得问题的全局最优解，但计算量偏大，对于实际问题规模的求解速度往往难以达到实用的要求，因此通常只能用来解决规模较小或大幅简化了的问题，缺乏实用性。启发式方法虽然不存在计算成本过大的问题，但易于陷入局部最优及无法保证最优等问题也限制了其通用性。近十多年来，相关研究更注重于引入智能化方法，通过模拟某种自然现象、物理规律或生物行为来探索更为高效可行的运算机理。更有学者进一步尝试将智能方法加以混合运用，以提高方法的性能和效率。
1.3.4 动态调度问题与方法
生产调度（Production Scheduling）是对工件在相关设备上的加工顺序和加工时间实施安排，以保证所选定的生产目标趋优。生产调度按照类型可以分为静态调度（Static Scheduling）和动态调度（Dynamic Scheduling）。静态调度是在作业及设备等生产环境确定已知且不考虑意外扰动变化的情况下，对加工任务进行的组合优化决策；动态调度需要依据动态变化的实时生产环境，逐步生成调度方案并指导实际的生产过程。通常的动态调度方法大致分为三类：反应式调度（Reactive Scheduling）、预测-反应式调度（Predictive-reactive Scheduling）和主动式调度（Proactive Scheduling）［18］。
反应式调度并不会事先形成全局的优化调度方案，而是伴随着实际生产过程的执行，根据生产系统的实时状态及加工任务信息，实时进行局部决策，为空闲的设备确定加工任务，这种动态调度也称为实时调度（Real-time Scheduling）。最常见的实时调度方法就是运用某种调度规则（Dispatching Rule）从等待空闲设备加工的众多加工任务中，选择优先级最高的一个加工，优先级的计算依据是当前加工任务和相关设备的实时状态与属性。经过众多学者的长期研究，已有非常多的调度规则被提出并加以实际应用。基于调度规则的实时调度方法具有快速、直观、易实施等优点，但其局部优化的本质也导致其具有难以达成全局和长远的调度优化效果等局限性。
预测-反应式调度是一个调度/重调度的过程。调度阶段在假定生产系统状态和加工任务均确定的情况下，形成优化的调度方案（原始调度方案）；重调度阶段在已形成的原始调度方案基础上，响应实际动态环境下生产系统状态和加工任务执行的变化情况，对原始调度方案加以调整，产生新的也是最终的调度方案。因为前一阶段调度过程实际上相当于短期生产计划，所以后一阶段的重调度就是这一类动态调度的关注重点，或者就直接称其为重调度（Rescheduling）问题。
主动式调度是指在进行调度决策时，提前将可能出现的不确定因素考虑在内，从而构建一种对动态生产环境具有一定鲁棒性的预防式调度方案，所以这种动态调度方法也称为鲁棒调度。在主动式调度研究中，目前被广泛加以考虑的是加工时间相关的不确定性。例如，Pereira［19］针对单机调度问题，将其中不确定的工序加工时间在固定闭区间上取值，基于场景规划方法，提出了以加权完工时间为性能指标的鲁棒调度方法。Drwal等［20］基于并行机调度中工序加工时间只有其间隔边界已知的认识，提出了以总完工时间为评价指标的最小、最大后悔值调度方法。除了加工时间的不确定，也有学者通过对随机机器故障［21］和急件到达［22］等生产系统不确定性的预测，开展主动式鲁棒调度方法的研究。
综观过去几十年的学术研究和实践探索，关于生产计划与调度的研究和应用已取得了大量成果，从概念理论到方法体系，再到系统工具都有丰厚的积累。但是，大部分工作都是将生产计划和车间调度分离开来，作为两个独立的领域，分别针对其各自的子问题加以分析和求解。例如，生产计划领域的投料控制、维护调度，生产调度领域的作业排程、实时调度、组批调度、瓶颈设备调度等。然而这些子问题之间又是密切相关的，为了达到彼此协同、优化整合的效果，需要将其纳入一个系统框架下加以分析和研究，以探索真正适合实际的复杂制造系统管理需要的解决方案，这也正是本书撰写的初衷。