动态调度的研究现状概述

可以看出， 虽然关于生产调度问题的研究成果非常多， 但有相当一部分研究是基于这样一种共同的假设： 所有的参数都是确定的， 而且在这种确定性调度的研究领域内， 普遍认为调度一旦下达到车间， 就会被按部就班的执行。 但这种假设并不现实， 在实际生产过程中， 存在大量的不确定因素， 比如原料供应、 产品需求及加工时间， 等等， 使得由各种确定性模型和方法得到的优化调度性能指标降低甚至不再可行。 因此， 在处理生产调度问题的时候， 生产过程中存在的不确定因素是必须要考虑的， 大部分数据都是模糊的， 难以用精确的数学模型进行描述， 对静态调度方法的研究比较多， 而对动态调度因素发生时应该采取何种策略以及采取的时间点方面研究很少， 大部分研究都是做了很多前提假设， 对不确定状态强制规定满足某个函数曲线分布， 数据都有准确的数值， 而这与实际生产不相符， 只能停留在实验室进行理论研究。

市场的动态需求导致了订单的不确定， 投料计划相应动态变化和每天的投料时间、 次数不确定， 从而工件的到达时间也就不能确定； 应用于加工的设备非常复杂， 容易发生不确定的故障事件， 维修时间也是不能确定； 封装测试加工过程伴有复杂的物理化学过程， 造成每道工序的结束加工时间难以确定， 同一个工件在不同的设备上加工时间都会有差异， 工序之间存在紧密的偶合性， 加工的步骤很长， 产品种类繁多， 加工顺序不完全相同， 存在返工现象，不同的操作人员也会对加工周期造成影响。 因此， 封装测试生产线比经典的车间作业加工要复杂很多。 生产调度是生产管理的核心内容和关键技术， 其任务是在企业车间有限的资源约束下， 确定工件在相关设备上的加工顺序和加工时间， 以保证所选定的生产目标最优。 同时， 生产调度过程也是动态过程， 在动态随机制造环境中，管理者不仅要产生高质量的调度， 而且要以节省费用的方式对调度中不可预测的事件迅速做出反应， 修改调度。 为了最小化一些扰动对系统性能的影响， 启动重调度是必需的。 重调度就是参考现有的静态调度， 并同时根据生产线的实时状态进行的动态调度， 它是广义的动态调度。 这里有许多类型的扰动能干扰计划， 包括机器损坏、 加工时间延迟和紧急订单等。 Bean 认为重调度是响应这些扰动的动态方法。 在实际制造系统中， 重调度是在系统状态的基础上对下一期作出周期计划活动。 Wu 研究用有效性和稳定性作为标准的单机重调度启发式算法。 Shafaei 提出动态和随机环境的调度规则的鲁棒性。 他们得出的结论是： 随着不确定性水平的增加， 经常性重调度在提高调度鲁棒性方面变得更加有效。

调度主要处理由外部商业环境和内部生产条件引起的不确定性问题， 国内外已有许多学者对其加以研究， 早期的如在开发生产调度专家系统时提出再生方法， 对柔性制造系统(flexible manufacturing system， FMS)中的动态调度问题进行了研究。 按照Olumolade 和Norrie 在1996 年的定义， 重调度是当既定生产调度方案在其执行过程中被干扰， 在既定调度方案的基础上生成新的调度方案， 以适应当前状态的过程。 根据各种重调度因素， 在决定何时产生重调度时， 常见的有周期性、 事件驱动型和混合型3 种重调度策略。 周期性重调度策略以恒定的时间间隔有规律地启动重调度，不考虑事件的触发， 特别适用于没有实时监视车间状态的在线数据环境。 但在实际应用中， 如何决定最合适重调度周期是一项困难且重要的工作。 事件驱动型重调度策略由扰动事件触发重调度， 能够即时响应动态制造系统中的扰动事件， 修改静态系统中的调度计划。 然而， 完全的事件响应可能会导致过度繁重的计算需求， 难以满足系统实时性要求。 混合型重调度策略将上述两种策略相结合，在周期性重调度的基准上， 当有特殊(或主要)的事件发生时会再次启动重调度， 希望能够在有效跟踪系统变化的同时控制计算量，但目前文献上所见到的混合重调度策略只是周期性策略和事件驱动策略的简单结合， 且考虑的事件也主要以设备故障为主。 Wu 等研究了机器故障情况下兼顾稳定性的单机重调度算法， 此时调度问题是一个兼顾效率指标和稳定性指标的双目标优化问题， 分别采用了成对交换算法和遗传算法。 对单次故障的仿真结果表明： 在牺牲一点效率指标的情况下极大改善了调度的稳定性， 分析了Job-Shop环境中干扰如何延迟工件的问题， 采取策略是生成一个鲁棒预调度， 采用右移重调度处理干扰并设计了调度鲁棒性的代理评价指标， 最后采用遗传算法寻找以期望延迟和期望的最大完成时间为目标的鲁棒预调度。 Byeon 等首先在空间上对问题进行分解， 采用分支定界方法构建部分最优调度， 随着时间的推移逐步添加剩余调度， 增加了处理干扰的灵活性。 仿真结果表明在多数情况下， 调度的鲁棒性优于分派规则， 但是当加工时间的多样性程度增大时， 分派规则的性能较好。 Wu 等设计了一个半在线的方法对Job-Shop 问题生成鲁棒调度， 实质是一种先预处理后调度的方法， 将离线方法的全局视角和在线调度的自适应性结合起来。 首先， 将所有的工序分解为多个独立的子集， 通过分支定界方法求出当前调度决策时刻关键的子集， 在不考虑其他子集的情况下采用分支定界方法确定这个关键子集的最优调度， 其余的采用分派规则动态性。 实验结果表明， 这种半在线算法在加工时间的一定扰动范围内都优于离线调度方法和在线调度方法。 对加工时间不确定的调度问题， 一般认为加工时间是随机变化的， 但是， 像上述加进人类主观因素的估计， 理解为模糊变量更接近于实际， 并且运用模糊模型可以方便地计算模糊变量叠加的联合隶属函数， 而随机变量叠加的联合随机函数， 只有随机变量服从均匀分布时容易计算得到， 其他分布时几乎无法计算。 随着模糊数学的发展， 基于这种规划的思想被运用到调度领域， 形成非确定性调度的一个重要分支——模糊调度。

目前， 关于模糊调度问题的研究， 主要集中在模糊数的操作问题上， 包括模糊数的求和、 取大以及模糊数之间的比较等方面的研究。 针对调度问题中的模糊加工时间的研究已经取得了一定的进展。 如Mitsuru Kuroda 和Feng-Zhelin 等用三角模糊数对Job-Shop：Scheduling 模糊加工时间等问题进行了分析； Zhang Peihong 等用三角模糊数对双机Flow-Shop 中的时间参数进行了分析； Moar A.Hgryaeb 采用三角模糊数来处理Job-Shop 中的多目标优化问题；Pual M.Satnfiedl 等用通用L_R 模糊数和梯形模糊数来解决单机调度中的模糊加工时间问题； Feng Zhelin 等用(λ， 1)区间值模糊数来表征模糊作业车间调度中的模糊加工时间， Jing Shingya 等用(λ，p)三角区间值模糊数和有符号距离来处理Flow-Shop 中的加工时间问题， Juite Wang 用六角梯形来表征项目调度中的模糊时间间隔问题。 针对具有较强不确定性的调度环境， 希望预调度在不确定参数的所有可能实现情况下都具有较好的性能， 尽量避免最坏性能。 在该研究领域中共有三种鲁棒指标： 绝对鲁棒指标、 偏差鲁棒指标和相对鲁棒指标。 文献分别研究了单机和两机Flow-Shop 在加工时间不确定情况下的鲁棒调度问题， 根据问题的特性提出了利于求解的相应优势准则， 在此基础上设计了保证鲁棒性的分支定界方法和近似启发式方法， 实验结果表明了这些方法的有效性， 提高了在各种加工时间情况下调度的鲁棒性。

对于动态调度环境， Vieira 研究了事件驱动规则。 用这个规则我们可以清楚看到用在动态调度的时间比其他的策略要多， 并且它需要一个快速和可靠的电子数据去迅速获得新的事件。 混合重调度规则周期性地发生重调度， 它也在主要事件发生时重调度系统， 主要事件通常是机器损坏， 但是也有突然作业到达、 作业取消或作业优先性改变。 Church 讨论了一个混合规则， 这个规则在每个时期开始和有重大的破坏发生时修改调度， 即当有突发事件时立即进行调度， 其他时间每隔一个固定周期进行再调度。 研究表明， 这种调度策略要优于前两种策略。 Vieira 同时也研究了一个混合重调度规则， 当机器损坏和一个修复完成时引发重调度。 Montagnon 提出了通过仿真来规划车间重调度方案。 与确定性调度不同， 随机调度从概率的角度出发， 假定工件特征可以由一个确定性的概率分布来描述， 而实际的值只有在调度执行之后才可以得到。 由于随机调度的性能依赖于不确定参数的实际值， 所以该模型一般以期望的调度性能为指标。 随机调度模型在实际应用时存在一些困难： (1)难以得到不确定参数准确的概率分布； (2)假设各参数是独立分布的， 但有些情况下这个假设不成立。 决策者在多数情况下不愿冒险， 特别是存在较大范围扰动且无法确定具体干扰源的情况下， 尽量避免某些数据实现下的最坏性能。 鲁棒调度方法以最坏性能作为优化目标， 保证调度在各种可能数据实现情况下具有一定的鲁棒性， 对存在较大范围扰动的调度环境是一种很有效的决策方法。

目前， 对车间任务的调度绝大多数是基于精确的信息。 以往调度研究主要集中在理想的调度环境， 一般都是以确定性的数学模型为基础， 与实际的车间调度环境存在很大差别。 在实际的制造车间中， 往往存在着很多动态不确定因素， 如加工时间变动、 机器故障或者交货期变更等， 实际生产线上加工信息具有模糊性。 所谓模糊信息、 模糊状态以及模糊行为分别是指信息空间、 状态空间及行动空间上的模糊集合。 如何在生成预调度方案时充分考虑到不确定因素的影响， 已经成为解决实际调度问题的关键。 不确定因素可以分为部分未知和完全未知两类， 对于第一类情况， 在建立预调度优化模型时， 就应考虑这些因素的影响， 可以有效提高调度的鲁棒性和稳定性； 而对于第二类情况， 采用反应式的动态重调度是适应环境变化的最好解决方式。 在动态不确定环境下的调度问题， 其计算复杂度远远超过了静态调度问题的难度， 使得以往的研究方法难以直接应用， 对问题的求解提出了更高的要求。 通常的研究文献都只是针对单机、 平行机或者设备与加工不复杂的车间进行研究。 由于封装测试企业是复杂的大规模加工生产， 因此对车间作业研究的复杂程度就成指数增加， 对任务进行分解也就成了最适宜的优化研究方法。 怎样对生产线进行任务调度合理分解， 是解决大规模生产线决策优劣的关键策略。

分解方法是将一个复杂的大规模调度问题分解为相对简单的小规模调度子问题求解后， 按一定方式将局部解整合为原来大规模问题的解。 分解方法可以归结为两种主要的类型， 基于时间的分解和基于空间的分解。 滚动调度策略就属于一种时间分解方法， 基于空间的分解包括基于工件或工序的分解和基于机器或加工中心的分解。 拉格朗日分解方法是一种比较典型的实体分解方法， 它的分解实体是工件或者工序， 另外一种是基于机器的移动瓶颈分解方法。Ovacik 等的研究表明， 滚动时域方法把一个全局大规模优化问题分解为一系列相关联的小规模优化子问题， 计算复杂性大大降低， 而且子问题部分利用了全局信息， 调度质量比分派规则有显著提高，当关键资源的竞争非常激烈时效果更加明显。 方剑等采用基于时间窗口和基于工件窗口的滚动优化方法对具有柔性加工路径的Job-Shop 动态调度问题进行了研究， 降低了问题的计算规模， 同时对加工环境的变化比静态调度具有更好的适应能力， 并且在合理的计算时间内得到具有良好性能的调度。 王冰针对大规模静态调度问题提出了一种基于初始调度的两阶段滚动调度策略， 对一类性能指标可分的单机调度模型采用终端约束优化子问题， 在局部优化子问题中考虑了全局目标， 从而保证了全局调度性能不断改善。 因此， 对于复杂多变的现代制造， 更需要从动态的角度来深入研究车间作业的调度， 才能具有实际的指导意义。

对于环境、 任务都是事先去确定的静态调度， 由于缺乏对生产过程中各种变化因素的应变能力， 往往在实际的应用中受到限制。与此相对应的动态调度， 通常指的是在调度环境与任务存在不可预测扰动情况下所进行的调度， 能够针对实际情况规划出更加具有可操作性的决策方案。 广义的动态调度的实现方式有两种： 一是事前不存在静态调度方案， 直接按照生产线上的工件和设备的状况以及信息， 使用某种算法， 制定出工件的加工方案， 即为实时调度或者叫作狭义的动态调度； 二是在已有静态调度方案的基础上， 根据生产线现场的实际情况， 及时对静态调度方案进行调整， 给出新的调度方案， 此种方案称为重调度， 它是动态调度的主要形式。

生产调度过程是动态过程， 在动态随机制造环境中， 管理者不仅要产生高质量的调度， 而且要以节省费用的方式对调度中不可预测的事件迅速做出反应和修改调度。 为了最小化一些扰动对系统性能的影响， 重调度是必需的。 这里有许多类型的扰动能干扰计划，包括机器损坏、 加工时间延迟和紧急订单等。 重调度是响应这些扰动的动态方法。 在实际制造系统中， 重调度是在系统状态的基础上对下一段时期作周期计划活动。 许多生产调度问题的研究应用了3种分类模型。 模型用3 个参数α、 β 和λ 表示调度问题， 这里α 代表调度环境， β 代表调度作业的一些区别性特征， λ 描述目标函数。 这个模型用于精确描述一个广泛的车间模型中， 如单机、 并行机器和作业车间调度问题， 研究者也应用它描述许多其他静态调度问题。 然而， 重调度研究范围非常广， 没有标准的分类模型。 重调度不仅作为产生和更新生产调度的一个技术集合， 而且作为在许多环境下影响制造系统性能的控制策略。 这里的重调度框架包括重调度环境、 重调度策略、 重调度规则和重调度方法。 重调度环境识别需要调度的作业集； 重调度策略描述产生生产调度的时机问题， 重调度规则指出什么时候应该产生重调度； 重调度方法描述怎样产生和更新调度。

在动态、 随机的制造过程中， 只要使用离线调度(即静态调度)， 重调度就是实际上不可避免的。 重调度的存在主要有两个方面的原因： 一是由于生产环境的变化。 对于竞争日益激烈的制造业， 客户的需求是在不断地变化， 如紧急订单、 工件取消。 同时，制造企业的上层领导对于某些指标重视程度的改变也需要进行重调度； 二是由于生产过程的变化。 在初始调度方案生成的过程中， 通常认为加工时间、 车间状态等的调度是已知的， 并且在相当一段时间内是有效的。 但是， 在实际情况中， 这些参数受到不确定因素的影响， 在调度过程中可能会发生明显的变化。 相应地， 以前的调度方案可能变得不适合， 甚至不可行。 在这种情况下， 初始调度必须重新考虑， 进行修改。 环境的变化通常有两种方式： 一种是积极的， 即环境向好的方向发展， 如实际的加工时间比计划的时间短，原来的调度尽管可以执行下去， 但是在这种情况下显得不够有效，重调度根据环境的变化而生成使生产性能更好的新调度方案， 充分利用系统资源； 另一种是消极的， 即环境变差了， 如机器故障、 加工时间的延迟、 质量问题等， 初始调度变得不可行， 甚至无法执行下去， 这时重新生成调度是必需的， 通过重调度可以找到这种环境下的合适的调度。

目前， 国内外的动态调度研究主要集中于单台机器、 并行机器、 流水车间(Flow-Shop)和经典类型作业车间(Job-Shop)的动态调度方法和对动态制造系统性能的影响。 对于车间动态重调度的研究， 文献针对调度环境的不确定情况， 设计了一种先预处理后调度的半在线方法， 将全局前瞻性和在线调度的自适应性结合起来。 首先在初始时刻根据全局目标对工件进行一种优先权分配， 而不是一个详细调度， 然后在执行过程逐步实现完全调度， 这样可以保证调度具有良好的鲁棒性和前瞻性。 Policella 等旨在生成一个部分调度来保持暂时的灵活性， 以使调度在不可预测的环境下保持一定程度的鲁棒性。 首先计算资源利用有界来识别潜在的资源冲突， 然后通过时间窗口的推进来逐步消除冲突而得到可行的部分调度方案。McKay 和Wiers 讨论了调度理论和实践之间的关系， 提出了三个准则解释实际的生产调度过程： (1)对部分问题生成部分解； (2)对干扰作出反应并进行调整； (3)对环境变化很敏感。 大规模动态Job-Shop 调度问题对在线重调度的计算效率要求很高， 希望能快速处理各种干扰事件。 在这种情况下， 为了能在很短时间内生成新调度， 重调度时刻可以只调度一部分工序， 剩余的工序在下一次重调度时刻再进行详细调度。 如何在当前规模较大的工序集中选出重调度工序集是影响重调度算法性能和计算效率的关键因素， 在以往的研究中， 常常采用简单的规则确定哪些工序进入当前重调度工序集， 忽视了选入的工序对全局性能指标的影响。

动态调度的时机决策以及调度方法仍然是当前车间调度问题的主要热点与研究方向。 而模糊逻辑已成功应用于很多不确定环境的研究。 模糊逻辑是一种新型的分类方法， 它模仿人类的智慧， 引入隶属度的概念， 描述介于真与假之间的过渡过程。 在模糊逻辑中，事件不以集合的极限值分类， 而是一个元素赋予一个介于0 和1 之间的实数， 描述其属于一个集合的强度， 是一种很好反映决策者主观意愿的工具。 由于半导体封装测试系统中存在着高度的不确定性， 因此， 模糊逻辑很自然地成为其解决调度问题的主要工具之一。 所以， 本书进一步的工作就是将模糊逻辑应用于车间调度。