Petri网化简理论在资源不可靠制造系统优化控制中的应用

Deadlock control remains being a key problem in automated manufacturing systems (AMSs). It aims to avoid the deadlock states so that the system can run smoothly. It is of particular significance in practice to research deadlock control in AMSs with unreliable resources. Petri net is the most effective formal tool that is widely used for solving system deadlock problems. In many systems, to handle the optimal deadlock control is a NP-hard problem. While the Petri net models of quite a few complex systems are too large because there is redundant information from the control viewpoint. This project focuses on the application of Petri net reduction for the deadlock optimization control in AMSs with unreliable resources. Specifically, we will resolve the following issues: 1) to explore the internal connection between resource failures and system deadlocks; 2) to set up the foundation of the reduction method; 3) to design algorithms to recognize the redundant information; 4) to design algorithms to reduce the Petri net models of AMSs; 5) to test and to evaluate the reduction method, and to extend the practical application fields of the method. In summary, we will establish a novel methodology of Petri nets reduction. After we process the Petri net models of AMSs with the method, much computational time would be saved in the control implementation. The reduction is a promising technology to reduce some deadlock control problems to be practically solvable while maintaining the other control performances.

死锁控制是自动制造系统（简称AMS）中的一个关键问题，其目标是保证系统的正常运行。带有不可靠资源的AMS的死锁控制研究则特别具有实用价值。Petri网是解决系统死锁问题最有效、使用最广泛的形式化工具。在许多系统中，死锁的最优控制是NP难问题。同时，从优化控制的角度看，大量的复杂系统中存在冗余信息，导致Petri网模型的规模太大。本项目研究Petri网化简理论在资源不可靠AMS的死锁优化控制中的应用。主要研究内容包括：1) 探寻资源故障与系统死锁的内在关联；2) 建立化简方法的理论基础；3) 设计系统冗余信息的识别算法；4) 设计AMS的Petri网模型化简算法；5) 测试、评价化简方法，并扩展其应用领域。我们将建立一套化简Petri网的新理论体系。对AMS的Petri网模型做预处理，能够减少后继实现控制所需的计算量，有望将一些问题缩小到实际可计算的规模，并且保持其它控制性能不变。

Petri网是解决系统死锁问题最有效、使用最广泛的形式化工具之一。在许多系统中，死锁的最优控制是NP难问题。带有不可靠资源的自动制造系统（automated manufacturing systems,简称AMSs）的死锁控制，其目标是保证系统的正常运行。因而本项目研究特别具有实用价值。从优化控制的角度看，大量的复杂系统中存在冗余信息，导致Petri网模型的规模太大。本项目研究Petri网化简理论在资源不可靠AMSs的死锁优化控制中的应用。我们建立了一套化简Petri网的新理论体系。对AMSs的Petri网模型做预处理，能够减少后继实现控制所需的计算量，结果将一些问题缩小到实际可计算的规模，并且保持其它控制性能不变。除了项目摘要中所列出的内容，本项目还研究了一类柔性装配系统（flexible assembly systems，简称FASs）的多项式时间复杂度的监督控制方法。该系统属于制造系统的大范畴。从离散事件系统监督控制的视角看，FASs是一类资源分配系统。因而在系统运行中需要解决死锁控制的问题，从而保证系统平稳运行。本项目探索FASs的死锁避免策略的设计，相对于已有研究工作中讨论的FASs，我们研究的FASs的范围更广。具体来说，每个处理步骤都可以占用多种类型的多个资源，并且每个资源均能够被任何两个操作共享。本项目为这类FASs开发了一种基于Petri网的银行家算法式的死锁避免策略。整个策略由三个可执行的算法组成，同时其计算时间是系统模型规模的多项式复杂度的。项目研究结果有助于促进制造系统自动化理论的深入发展。