1.2　制造系统生产调度问题研究现状

1.2.1　制造系统生产调度问题的复杂性

针对市场需求面向多品种、小批量定制的发展模式，产品的结构表现出更多的BOM、工序种类繁多及其生产加工要求多车间、多机床及多AGV协调生产等特性，合理而有效的调度将是制造系统实现高效生产的关键技术之一。调度优化针对若干可以分解的任务，在满足一定的约束条件下，安排其组成部分所占用的生产资源以确定所有任务的某一项或者某几项性能指标达到最优。1954年，美国学者Johnson在他发表的文章中首次阐述了流水车间（Flow Shop）调度问题，从此，生产调度问题的研究开始受到运筹学、应用数学和工程技术等领域的专家学者的重视，并且取得了一系列的丰富理论成果。

生产调度问题一般采用α/β/γ三元组的方法对其进行描述，其中，α用于描述机器环境类型，β用于描述约束和限制要求，γ用于描述某一项或者某几项性能指标最优要求。

生产调度作为制造系统研究对象之一，它是企业生产管理系统的关键。一个良好的生产调度方案，能够在不增加其他成本的基础上，提升车间的生产效率，提高企业的竞争力。在实际的企业生产中，生产调度问题往往非常复杂，该类问题通常具有如下固有特性。

（1）调度目标的多元化。车间调度问题的研究，大多数是以完工时间最短为调度目标函数。在企业的实际生产调度中，为了均衡客户需求和自身经济效益，企业决策者往往不会仅考虑单一的优化目标，最短完工时间、最小拖延时间、成本最低、能耗最低、机器最大负荷、总负荷等都是车间调度的优化目标。在每次实际生产调度中，往往不止考虑一个目标。

（2）调度条件的约束化。车间调度方案的确定，往往需要考虑各种约束条件，包括任务本身的约束条件，如每道加工工序要满足基准先行、先面后孔、先粗后精等约束要求。另外，车间调度资源的约束、任务对加工机器的约束、AGV的约束，以及其他一些约束都是在建立目标函数时需要考虑的。

（3）调度对象的柔性化。在传统的车间调度中，每个工件的加工路径都是唯一的，即每个任务的加工工序固定，并且每道工序加工的机器也是固定的。而在实际的生产中，柔性生产调度往往更切合实际。柔性生产调度包括加工工艺的柔性、加工机器的柔性、加工方法的柔性。其中，加工工艺的柔性是指工件的加工路径不唯一，每条工艺路线上的工序也不相同；加工机器的柔性是指工件的加工工序可以由不同的机器完成，加工时间和资源消耗也不同；加工方法的柔性是指同一个加工特征可以用不同的加工方法实现。因为柔性生产调度既要对工序顺序进行调度，又要为每个工件选择合适的工艺（或为每道工序选择适当的加工机器），所以比一般的车间调度更复杂。

（4）调度环境的动态化。多数的生产调度方案都是假定调度环境是静态的，即从加工开始到加工结束，所有的资源都是固定不变的。而在实际生产中，往往会出现突发情况，比如，机器发生故障，订单发生变化，有紧急工件插入，等等。这时，原有的调度方案就不再适用，为了保证企业的利益，就需要及时调整调度方案。动态调度能够根据加工条件的变化适时地调整调度方案，更符合企业的生产实际。动态调度一般是先对调度任务进行静态调度，然后再根据生产实际中出现的突发情况，对尚未完成的任务进行重调度。

（5）调度计算的复杂化。生产调度问题在大部分文献中已经被证明是一个NP-Complete问题，该问题的复杂性在于随着问题规模的增加，可行解的数量快速递增，计算的强度呈指数级增大。

1.2.2　现代制造系统生产调度面临的需求

生产调度问题除了1.2.1节所述的一些固有特性，随着智能制造系统的发展，制造系统的生产组织模式发生了巨大的变化，生产调度问题也面临着新的挑战。由于生产车间是制造系统的重要组成部分和基本单元，是实施客户需求的真实场所，是工厂生产和管理的基本单位，是企业从事生产经营活动的基础，因此，其优良的调度方法和运作过程直接体现出制造系统的性能。如图1.2所示，从业务层次来看，生产车间是接纳上层物料、信息和状态反馈的聚集点，是工厂层的组成单元。

在现代工厂车间里有不同柔性和自动化程度的生产设备，如数控（Numerical Control，NC）机床、计算机数控（Computer Numerical Control，CNC）机床和加工中心等，这些加工设备使生产车间成为具有高度柔性的生产系统。然而，可靠性和柔性程度高的生产制造系统不仅依赖于柔性的设备和组件，在组织生产、配置任务和资料的过程中采用良好的生产管理方式和优秀的调度技术也具有非常重要的作用。合适的调度技术和优化方法是制造车间高效运行的保证。因此，研究高可靠性和高柔性的生产调度技术已经成为现代智能制造系统领域的关键性问题之一。同时，现代智能制造系统处在一个动态的运行环境中，许多不可预知的动态事件频繁发生，如紧急订单、订单取消、设备故障或工艺路线变化等。为了快速地适应这些动态变化，智能制造系统对调度技术实时性和响应性的需求更加迫切。

分布性、自治性和协商性是现代智能制造系统具有的显著特点，而这种特性也是调度技术的发展趋势。调度技术利用分布的智能单元根据其自身知识实现局部优化，然后通过单元间的协商达到全局优化。这种调度技术完全可以适应各种制造系统中随机出现的动态事件，并满足多目标的优化（如成本、时间、资源利用率等）。传统的调度技术一般采用离线的方式进行调度计算，具有离线性的特点；而新的调度技术除了必须具备分布性、自治性和协商性的特点，还必须具备实时性、智能性和事件驱动性的特点。

1.2.3　现代智能制造系统动态调度技术

为了解决制造系统在实际生产过程中存在的不确定性和随机性问题，研究现代智能制造系统在动态生产环境下的调度技术引起了不少机构、组织和学者的关注。进入20世纪之后，许多先进的调度优化技术不断被应用到动态生产调度中，其研究成果持续地得到充实和发展，归纳起来可以分为传统调度方法和非传统调度方法两种。传统调度方法一般是用离线的方式来解决调度问题，包括近似方法和精确方法，其中涉及的一些具体方法如图1.3所示。

离线的方法可以获得较好的优化结果，但是其缺陷也非常明显，即它很难适应实时调度。而非传统调度方法是相对离线调度方法而言的，它主要关注制造系统在生产调度实时变化条件下的应对机制及决策方案，并强调调度的连续性，因此，它更适应现代智能制造系统发展的需求。从计算形式上，可以将非传统调度方法分为集中式调度和分布式调度两类。集中式调度，顾名思义是所有任务通过一个中央调度器完成任务分配，所得到的调度结果往往是全局最优解。然而由于控制结构的限制，集中式调度很难适应动态变化的制造系统环境，在发生扰动时，制造系统的运行经常被中断，且计算复杂性很难被分解和降低。分布式调度强调自治与协调，它赋予各个智能单元决策能力和计算能力。各个智能单元在解决自身调度问题的前提下，通过智能单元间的协调调节解决更高层次的调度问题，因此，它具有其他方法所不具备的优点。

（1）利用分布式特性将调度问题离散化，简化调度问题规模。

（2）智能单元具有优化能力和计算能力，可通过并行计算提高系统运算效率。

（3）智能单元的调度算法灵活多变。

（4）智能单元可集成至实体，并连接物理资源实现实时调度。

（5）针对动态事件，调度系统具有适应性、响应性和扰动事件影响局部性等特点。

自治与协调是分布式调度方法的典型特征，其基本思想是把复杂制造系统的生产组织结构划分成相互独立的智能单元，将复杂的调度任务分散至各个智能单元上并行完成。与此同时，各个智能单元之间通过相互间协商完成各自的调度行为，从而实现制造系统调度目标的优化。在现代智能制造系统中，具有自治与协调特性的分布式制造系统以多智能体制造系统（MAMS）和Holon制造系统（HMS）最为典型，而且这种基于自治与协调的调度技术隶属于分布式智能调度算法的范畴，是MAMS和HMS生产计划领域的研究热点。

从目前的研究来看，对MAMS和HMS生产调度的研究主要集中在装配生产线、柔性制造系统（Flexible manufacturing systems，FMS）、Job Shop、物料处理系统等各个方面。比如，有学者提出了一种针对车间动态调度的多Agent构架。各个加工单元Agent动态地选择最具适应性的调度规则执行局部调度。当监控Agent认为既定的事件出现时，局部Agent根据优化后的阈值重新选择调度规则，然后Agent之间通过协商机制完成制造系统的动态调度。还有的学者提出了一种基于协商的多Agent调度系统解决动态事件的弹性作业调度问题。Agent之间采用基于信息素的方法进行协商通信，完成任务分配，也可以采用一种多Agent的AGV路径选择/调度方法，利用Agent之间的通信协商完成路径生成、枚举时间窗、中断搜索、调整等待时间和决策路径选择等，该方法在单/双向路径网络AGV“无冲突”和“最短路径选择”中都表现出了很好的效果。还有学者提出了一种针对动态调度的HMS构架，HMS架构由资源Holon、任务Holon、工艺规划Holon、生产计划Holon和工艺规划Holon组成。Holon之间采用合同网协议进行协商通信。在调度过程中，任务Holon和资源Holon之间通过招投标过程进行任务分配，同时，资源Holon受调度Holon和工艺规划Holon的约束控制。为了解决随机加工时间的柔性流水车间调度问题，提出了一种HMS方法，采用两种调度策略进行动态调度。当任务进入流水车间后，机床Holon根据其随机属性被聚集为两个Holon群。具有低随机性的Holon群采用遗传算法生成局部解；具有高随机性的Holon群成员之间利用基于合同网协商机制进行谈判获得可行的局部解。HMS通过两种算法的结合获得全局最优解。

1.2.4　现状总结

尽管制造系统中Agent（Holon）的自治与协商特性在调度中得到了较为广泛的应用，但是或多或少仍然存在缺陷或不足。与之前分析的MAMS类似，Agent（Holon）以分布式的形式存在，通过Agent（Holon）的自治以及Agent（Holon）之间的协商来完成生产调度。但是由于Agent（Holon）间具有平等地位，只能根据局部信息做出调度决策，使调度结果达不到最优；并且，整个系统没有一个集中的调度控制器，在调度过程中不可避免地会产生冲突和死锁。虽然该问题可以通过多次协商解决，但也带来了系统通信量大的负担，尤其在解决大型复杂调度问题时，多次协商带来的问题将会被放大。另外，若缺乏优秀的调节策略和方法，调度的结果不但达不到预期结果，并且还有恶化的可能。因此，对现代智能制造系统调度领域的研究还存在以下一些需改进之处。

（1）构建更合理的智能制造系统体系构架。

（2）寻找一种更好的协商（通信）机制。

（3）探索更合理和更优化的调度策略和优化方法，为智能单元的协商过程服务。