基于Petri网的可重组制造系统的调度方法研究

有效的调度方法和优化技术是实现先进制造和提高生产效益的基础和关键。[83]所谓调度优化算法，就是一种搜索过程或规则，它是基于某种思想和机制，通过一定的途径或者规则得到满足用户要求的问题的解。[84]

1.现有的调度优化方法

目前，在调度领域大致有如下一些优化方法。

●运筹学方法

运筹学方法是将生产调度问题简化为数学规划模型，采用基于枚举思想的分支定界法或动态规划算法进行解决调度最优化或近优化问题，属于精确方法。文献[85]提出了不同的分支定界法，其不同点主要在于分析规则、定界机制和上界的产生这三方面存在差异。这类方法虽然从理论上能求得最优解，但由于其计算复杂性的原因，因而不能获得真正的使用。

●基于规则的方法

对生产加工任务进行调度最传统的方法是使用调度规则，因其调度规则简单、易于实现、计算复杂度低等原因，能够用于动态实时调度系统中，多年来一直受到学者们的广泛研究，并不断涌现出新的调度规则。文献[86]中总结了113条规则，将它们按形式分为了三类：简单规则、复合规则和启发式规则，并针对一个实际的FMS，分析了这些规则对系统性能（如作业的平均等待时间、设备的平均利用率、作业总加工时间等）的影响。

启发式规则虽然直观、简单、易于实现，但并不存在一个全局最优的调度规则，它们的有效性依赖于对特殊性能需求的标准及生产条件。它是局部优化方法，难以得到全局优化结果，并且不能对得到的结果进行次优性的定量评估。

●基于DEDS的解析模型调度方法

由于制造系统是一类典型的离散事件动态系统，因此，可以用研究离散事件动态系统的解析模型和方法去探讨车间调度问题，诸如排队论、极大/极小代数模型、Petri网等。[53]调度中的排队论方法是一种随机优化方法，它将每个设备看成一个服务台，将每个作业作为一个客户，作业的各种复杂的可变特性及复杂的路径，可通过将其加工时间及到达时间假设为一个随机分布来进行描述。[87]基于Petri网的调度算法能处理制造系统并发、冲突和随机性。[88]

由于制造系统中存在不确定因素，建立解析模型存在一定的困难。

●基于排序的方法

该方法是先有可行性加工顺序，然后才确定每个操作的开工时间，并对这个顺序进行优化，它虽然属于近似算法，但有可能达到最优的调度方案。它主要是邻近搜索法，它在生产调度领域得到了相当广泛的应用，在探索解空间时，仅对选定的成本函数值的变化做出响应，因而通用性强。这类方法包括局部探索（Local search，简称LS）[89]、模拟退火法（Simulated annealing，简称SA）、[90]遗传算法（Genetic algorithms，简称GA）[91]和神经网络优化。[92]

邻近搜索虽然可能得到最优的调度方案，但也存在各自的不足，一般采取混合算法来弥补单一方法的不足。

●基于智能的调度方法

在20世纪80年代，以卡耐基梅隆大学的Fox M为代表的学者们开展基于约束传播（Intelligent scheduling and information system，简称ISIS）的研究为标志，人工智能才真正开始应用于调度问题。文献[93]中探讨了一种基于知识推理的专家系统模型，以实现作业排序问题的求解，并给出了采用三种不同知识表示方式和分段推理的排序知识处理方法。该部分主要包括智能调度专家系统、基于智能搜索的方法及基于多代理技术的合作求解的方法等。(www.xing528.com)

2.基于Petri网与排序的混合调度方法

调度问题包括了针对具体问题的建模及其相应的调度算法。混合调度方法可以扬长避短地吸取各种调度算法的长处并限制短处，其中基于DEDS的解析建模方法和基于排序的方法的糅合，因其建模精确、计算时间短得到了广泛地研究和应用。

Petri网作为描述DEDS最常用的建模工具，在制造系统建模方面有着广泛的应用[94]。建立在Petri网基础上的混合调度算法主要分为两类。

●基于Petri网可达图的启发式搜索算法

Shih和Sekiguchi[95]在利用Petri网仿真FMS功能的过程中，利用局部调度解决冲突。Lee和DiCesare[96]用人工智能的算法给出了一个解决生产调度问题的框架。Sun和Cheng[97]对Lee的方法进行了改进，提出了有限扩展的A*算法。薛雷等[98]针对FMS利用增强确定时间Petri网和类A*算法进行了多目标优化。

●基于Petri网的遗传算法

Muth[99]最早使用遗传算法对一个10×10的Job shop问题进行了优化。Shun-Yu Lin[100]等使用着色时间Petri网和遗传算法对一个Wafer probe center进行了建模和调度。Yung-Yi Chung等[101]使用TPPN和GA算法对一个FMS系统进行了建模和调度。An-Chih CHuang等[102]使用QCPN（Queueing colored Petri net）和GA对Wafer制造进行了建模和调度。Xu Gang[103]使用了Petri网和GA算法解决了FMS系统死锁问题。郝东[104]利用Petri网的激发序列作为染色体编码解决了一个FMS中的Job shop问题。

上述调度方案主要解决了小规模FMS或Job shop问题。第一类方法的启发式算法针对复杂应用问题需要制定复杂的启发规则，复杂系统的Petri网可达图存在状态爆炸问题，导致算法效率的低下。第二类方法的GA调度算法中未充分利用Petri网优势来降低算法的复杂度，并且调度方法不能适应RMS生产调度的需求（包括调度算法必须和系统自身的结构脱离、利用不同构件的增减和整合适应生产以及不同构形下的多目标优化等）。

3.可重组制造系统调度方法

可重组制造系统调度方法是系统实施过程中的一个重要技术，该技术适时调整因设备故障、生产能力变化因素而引进的系统重组。

Chen-Hung Wu[105]考虑了一个两阶段的随机排队制造系统中，可重组资源的最优分配问题，证明了在不考虑可重组资源的安装费用和时间的情况下，一个最优的单调策略的存在性。Ahmed M.Deif[106]在系统层面上研究了可重组制造系统的生产能力优化调度问题，采用GA算法得到可重组制造系统何时重组和重组时生产能力改变多少的一个最优方案。Yasuhiro[107]采用粒子群算法研究了可重组制造系统的车间布局和传输机器人（Transport robot）的优化分配问题。Mustapha Nourelfath[108]研究了两类可重组制造系统的优化问题，一类是在一定的资源限制下，找出配置方案来最大化系统的生产能力；第二类是找出达到某一生产能力的最小资源成本。Mingyuan Chen[109]研究了在动态生产环境下，最小化重组费用的问题，提出了一个整数规划模型来最小化机器的加工处理花费和可重组花费，然后将这一整数规划问题分解为难度降低的子问题，并分别采用动态规划的方法来对其进行求解。

4.有待研究的问题

RMS针对产品或产量的变化对现有制造系统的资源进行重组，最大限度利用原有资源对系统构件进行快速重组、替代、整合及升级，使制造系统适应同一产品族或不同族多品种、变批量的产品生产。在满足系统并发、共享和加工路径的可选择性等特点之外，RMS的生产调度提出了不同于FMS和DML的新课题，如系统构件模块化设计并可快速重构、根据生产任务进行组元重组、重视系统的成本经济性等。

RMS的生产调度问题是在一定约束条件下，既要解决生产批量及相应加工排序问题，还要解决资源如何重构问题，以获得高的设备利用率、短的生产周期以及高的顾客满意度。