基于Petri网的制造系统建模、调度和控制方法研究

利用模型进行科学技术的研究已有悠久的历史，从最早的原样模型，到后来抽象意义的相似及数学模型，建模技术在不断地发展。制造系统建模就是运用适当的建模方法将制造系统抽象地表达出来，通过研究系统的结构和特性，对制造系统进行分析、综合及优化。[49]模型可以支持对系统的分析和综合、新系统的设计与现有系统的重构、系统控制与调度以及系统仿真。

制造系统是具有并行、异步、事件驱动、死锁和冲突等明显特征的离散事件动态系统（Discrete event dynamic system，简称DEDS）。[50]由于系统大多属于离散事件动态系统而不服从物理学定律或广义物理学定律的约束，因此不能像连续变量动态系统（Continous variable dynamic system，简称CVDS）那样采用传统的微分方程或差分方程建立数学解析模型。

图示概念模型利用所规定的图形符号和自然语言描述，并建立系统的功能模型，即刻画系统中的功能活动及其相互关系，其中最常用且效果较好的是IDEF建模方法。[51]IDEF方法已被广泛地应用于制造系统中计算机应用系统的分析和设计领域。其特点是：①通过简单的图形符号和自然语言来清楚、全面地描述系统；②采用严格的自顶向下、逐层分解的结构化方法来建立系统功能模型；③明确系统功能和系统实现之间的差别，即“做什么”和“如何做”的差别；④通过严格的人员分工、评审、文档管理等程序来控制所建模型的完整性和准确性。[52]IDEF模型的优点是对制造系统的信息流进行详尽的建模，充分表达了信息在系统中的流程；其缺点是无法通过该模型对制造系统这类典型的DEDS进行定量的系统性能分析。

1.制造系统的DEDS建模方法

针对DEDS国内外已有多种图示-解析混合建模方法，具有代表性的有：形式语言与自动机、极大-加法代数、算术与布尔函数法、排队论、马尔可夫链、摄动分析及Petri网。[53-56]

●形式语言与自动机 形式语言与自动机理论的基本出发点是：每一个DEDS都是具有与其关联的事件集E，事件集可看作是一个语言的“字母表”（Alphabet），事件序列则是该语言的“字”（Word），自动机则是根据一定的规则通过组合字母来产生一种语言的“装置”（Device）。在这种架构下，建立的DEDS模型就是能够说某种语言的装置（自动机）。这一方法的重要应用是DEDS的监控。DEDS监控的基本问题是对于DEDS施加闭环控制，强制地获得某些期望的系统性能。在自动机模型中，为事件集E设置时钟结构用以描述事件发生所经历的时间，从而引入时间自动机。若时间为随机的，即时钟结构是个概率分布函数集合，从而引入随机时间自动机。[57]

●极大-加法代数 引入该方法的目的是建立DEDS的时间化线性模型，该模型与连续状态变量系统的线性离散事件模型状态空间方程相对应。极大-加法代数主要引入了两种基本运算：“加”与“乘”。极大-加法代数法已用于制造过程的分析和优化。[58]

●算术与布尔函数法 算术与布尔函数法的目的是为DEDS建立离散系统的状态函数和输出方程形式的方程和函数，但所有的变量均为布尔量（0或1）。与极大-加法代数法不同，算术与布尔函数法仍然采用一般的代数运算。该方法已用于多种工件离散物流传输系统的建模与控制中。

●排队论 排队论的研究对象是排队系统和排队网络。在建立排队模型时，必须定义三类参数：①顾客到达与服务的随机过程概率分布类型和参数；②模型的结构参数，如队列的存储容量、服务员个数等；③操作规则，如接纳到达的顾客的条件及对于某类顾客特惠等。通常排队队列模型表示为：A/B/m/QD/K/P。此处：A为顾客达到间隔时间概率分布；B为服务时间概率分布；m为服务员个数；QD为描述队列规则，其中有以下几种规则：先到后享受服务（FCFS）、后到先享受服务（LCFS）、享受服务的顺序为随机的（SIRO）和一般排队规则（GD）；K为队列存储容量，当容量为无穷时，省略；P为顾客抽样的群体大小，当无穷大，省略。排队论对于有资源竞争的随机DEDS分析作出了重要贡献。[59]

●马尔可夫链 马尔可夫特征是指某事件轨迹的某点上事件发生所产生的下一状态值仅与当前状态有关，而与过去的状态轨迹无关。当随机时间自动机具有泊松时钟结构时，可以产生退化的马尔可夫链。在给定所有状态转移的概率以及初始状态下的概率分布，可以确定状态在任意时刻的概率。马尔可夫链在制造系统建模与分析中得到了广泛地应用。

●摄动分析 摄动分析提供了一种视为随机DEDS的定量性能分析的方法，它通过观察DEDS的单一样本轨迹计算其性能指标相对于某些系统参数的灵敏度来进行分析。[60]

●Petri网 一个基本DEDS的Petri网模型的结构元素包括：用图表示的库所（Place）、用长方形或粗实线表示的变迁（Transition）以及带箭头的弧（Arc）。库所描述DEDS的可能状态，变迁代表DEDS可能的事件。通过弧建立局部状态与事件之间的联系，等价于自动机中的状态转移函数，表示使事件能够发生的局部状态或事件发生所引起的局部状态变化。Petri网具有并发、形式化等特点，是描述DEDS最有效的一个手段。[61，62]

Petri网是一种结构化的描述工具，能充分描述DEDS局部与局部之间的关系。因此，能反映事件的先后、并行、同步与异步特征，反映系统的冲突、互斥、非确定及系统死锁；能直接从可视的Petri网模型动态产生监控控制编码，实现DEDS的实时控制；能用于仿真，实现对系统的分析与评估；Petri网能转化为其他DEDS模型（如马尔可夫链、自动机等）。由于上述优势，Petri网被广泛地应用到制造系统建模中，如单条流水线、柔性制造系统、智能制造系统等。

2.基于Petri网的制造系统建模技术

根据系统最终模型的不同构建过程，基于Petri网的制造系统建模方法共分三种：自底向上、自顶向下以及混合建模方法。自底向上的建模方法首先将制造系统分成若干子系统并分别表征它们，然后通过共享变迁或库所合成最终模型。相反，自顶向下的建模方法首先从宏观上整体表达系统，然后逐步细化其中的每个变迁或库所直至系统被充分描述清晰。[62]混合建模方法综合了对制造系统操作过程的自顶向下建模以及对制造资源的自底向上建模。[63]上述文献从建模方法上探讨了基于Petri网的制造系统建模技术，除此以外，Petri网自身的不断演化也给建模技术带来持续发展的动力。(www.xing528.com)

随着Petri网自身特性的扩展，相继出现了着色Petri网、面向对象Petri网、模糊Petri网、可变结构Petri网等，这些Petri网高级形式的出现能方便地结构化描述日益复杂的现代制造系统。[62，64]为支持结构变化制造系统建模，文献[65，66]针对变结构制造系统，提出了可变结构的时间Petri网。文献[67]采用RCN技术，研究了具有组装功能的离散制造系统的控制问题，并针对系统活性进行了分析。文献[68]针对FMS短的循环周期和最少在制品这两个变量，采用PN for short（UTPN）对柔性生产线进行建模和分析。上述方法通过Petri网的分析工具如可达图、T不变量、P不变量能对被描述的系统进行结构分析，如死锁、活性、有界等。

为了对DEDS系统的性能进行分析，Ramchandani[69]引入了确定性（Deterministic）时间特性，产生了时间Petri网（Timed Petri nets，简称TPN）。在TPN中系统固定时延与库所或变迁联系在一起，除了能分析系统结构外，还能分析系统的循环周期性能（如系统吞吐率、资源利用率等）。Zurawski R[70]利用TPN对制造单元（包括2台设备、2个机器人和2辆小车）进行了分析，计算了系统运行周期以及在制品数量。

实际上，制造过程的操作或活动所需的时间往往并非确定的，确定时间的Petri网对真实系统的模拟还不充分。随着随机Petri网（Stochastic Petri nets，简称SPN）[71]以及广义随机Petri网（Generalized stochastic Petri nets，简称GSPN）[72]的出现，提高了对真实系统的模拟程度，开启了带有随机特征的制造系统性能分析之门。GSPN因减轻了SPN状态空间爆炸的问题而得到广泛应用。GSPN假设制造过程符合指数分布或者为瞬时过程，通过构造同构马尔可夫链并计算其转移概率矩阵得到系统状态的稳定概率分布，据此可计算系统各项性能指标[73]。Robert Y[74]对自动生产线进行了建模，并进行了自动线的性能分析，证明了n台机器n-1个缓冲是活性的。Jin Young Choi[75]提出了一个基于GSPN的分析框架，对能力受限的柔性自动可重组生产线进行建模、分析和控制。

然而，真实的制造系统是个非常复杂过程，其中既包括了确定时间的变量，也包括了随机时间变量。由于扩展随机Petri网（Extended stochastic Petri nets，简称ESPN）[76]中可包含任意分布的随机变量，因此，它的出现进一步提高了对制造系统的建模及分析能力。目前，利用ESPN对制造系统进行建模还不多见。

3.可重组制造系统动态建模技术

可重组制造系统动态建模技术是可重组制造系统的一个重要支撑技术，通过建模可分析制造系统的加工能力、可变构件配置的合理性等。

Liberopoulos[77]建立了柔性制造系统的能力分析模型，分析对所有产品的加工能力，该柔性制造系统由不同的具有重组能力的加工设备组成，这些加工设备能够同时加工不同的产品，进行产品之间的快速切换。黄雪梅等[78]提出了构建面向可重构装配线的数字仿真验证平台，研究了仿真平台中的系统集成、制造实体建模等关键技术。Guixiu Qiao[79]提出了采用有色Petri网描述大规模定制制造系统的方法，支持大规模定制制造系统的动态和重组特性与操作。Eungjoo Lee[80]采用自底向上的资源控制网（Resource control nets，简称RCN）技术对制造系统进行建模，一个RCN子网包括一个资源库所和操作库所，系统通过这些子网的变迁组合形成系统模型，这些变迁联系方式的改变就意味这一系统物理模型的改变。

上述文献对可重组制造系统的不同侧面的建模及分析作出了初步的探讨。

4.有待研究的问题

可重组制造系统是一个典型的复杂生产过程，同其他的制造系统模型相比，其建模方法的特点为：

●可重组制造系统更注重通过自身构件的变化和重组来适应生产的变化，描述可重组制造系统的模型必须具有高度的重用性[81，82]，在制造系统发生变化时能够迅速、方便地反映这一变化。

●系统内部既有固定节拍的设备加工时间、工件运输时间又有随机产生的设备故障、构件重组等一系列影响因素，根据对象的快速变化相应地重构描述系统，建立系统模型。

●寻求一种满足包含任意分布Petri网模型的定量性能分析方法，而且要避免可达图状态空间爆炸问题。

因此，有必要研究适合可重组特性的随机Petri网建模技术及满足任意分布的制造系统分析方法。