| A flexible manufacturing system (FMS) is an automated manufacturing system (AMS) that can efficiently produce medium or small batches of different products. An FMS is made up of computer numerical control machine tools and a material trans-mission system. Deadlocks must be considered and resolved in control system design of FMSs. In some cases, a local or global system halt caused by deadlocks can not only lead to the deterioration of productivity but also heavy economic losses and even fatal results. Therefore, it is vital to ensure the realization and operation of system control based on deadlock description, analysis, and control in an FMS. At present, deadlock resolution methods in AMSs modeled with Petri nets are mainly classified into three strategies: deadlock detection and recovery, deadlock avoidance, and deadlock prevention. Dead-lock detection and recovery is an online mechanism of detecting and recovering deadlock states. When a deadlock occurs, it is detected and then the system is put back to a deadlock-free state, by simply reallocating the shared resources. Deadlock avoidance is a resources allocation mechanism, behind which an online control policy is used to make a correct decision to proceed among the feasible evolutions that keep the system away from deadlock states. Deadlock prevention is usually achieved by using an off-line computational mechanism to control the request for resources to ensure that deadlocks never occur.Generally, deadlock prevention policies can be realized by adding monitors to a Petri net system to forbid deadlock states. There are three important criteria in evalu-ating the performance of a liveness-enforcing supervisor for a system to be controlled: behavioral permissiveness, structural complexity, and computational complexity. As a structural object of Petri nets, siphons are closely related to deadlocks, which is always true whether in ordinary Petri nets or generalized ones. Many researchers have developed a great number of siphon-based deadlock control policies in order to achieve liveness-enforcing supervisors with maximal permissiveness, simple supervisory structure, and low computational complexity. Therefore, siphons analysis is important for deadlock control. Due to the inherent complexity of siphons resolution, any deadlock preven-tion algorithm with a complete siphon enumeration must be of exponential complexity in theory. This thesis focuses on liveness-enforcing Petri net supervisors considering siphon-based structural analysis and an elementary siphons extraction method. The following research contributions are proposed in this thesis.1. Behavioral permissiveness is one of the most important criteria in evaluating the performance of a liveness-enforcing supervisor. For a class of ordinary Petri nets, S3PR, this work explores sufficient conditions with respect to an initial marking under which there exists a maximally permissive liveness-enforcing Petri net supervisor. Based on elementary siphons, an algorithm with polynomial complexity is proposed to decide the existence of a maximally permissive supervisor for S3PR. Its development is based on the computation of a set of elementary siphons and siphons composition operations, which has been shown to be of polynomial complexity with respect to the size of a plant net model. It can be concluded that, for any S3PR, there exist initial markings such that a maximally permissive liveness-enforcing supervisor can be always found. By combining the proposed sufficient conditions, an iterative algorithm is developed to design maximally permissive liveness-enforcing supervisors for S3PR. At each iteration, a siphon is derived by an MIP-based deadlock detection method and then controlled by adding a monitor. Several examples are used to demonstrate the proposed methods. This study can be considered as further applications of elementary siphons of Petri nets.2. Siphon-based deadlock control in an FMS suffers from the problems of computa-tional and structural complexity. Thus, the concept of elementary siphons is originally proposed in ordinary Petri nets to reduce structural complexity of a supervisor. Due to the complex requirement of multiple resource types by an operation, the selection of elementary siphons and their controllability still need improvements in generalized Petri nets. From this, the concept of augmented siphons is proposed to extend the applica-tion of the elementary ones to a class of generalized Petri nets, WS3PR. An augmented siphon is a multiset that reflects the weights information of resource places contained by its original siphon. Among augmented siphons, the elementary siphons are redefined, from which a set of elementary siphons that strongly connects the system structure can be found for WS3PR. Moreover, based on graph theory, initial resource weighted di-graphs are presented for WS3PR, and the concept of isomorphic structures of Petri nets is introduced. A same set of elementary siphons can be admitted by different WS3PR with isomorphic structures.3. A class of generalized Petri nets, GLS3PR, is proposed, which can well model FMSs and facilitate structure analysis. An efficient strict minimal siphons (SMSs) and elementary ones extraction method is developed for GLS3PR. Augmented siphons are proposed based on the structural analysis, and the elementary siphons are redefined. Based on graph theory, the concept of initial resource digraphs is first introduced to compute all SMSs in ordinary Petri nets. In this thesis, the initial resource weighted digraph for GLS3PR is presented. A restrictive induced subgraph can be obtained by in-ducing an initial resource weighted digraph under certain restrictions. Based on them, a method for computing all SMSs and their augmented versions is developed through fully investigating the structure of GLS3PR. According to the relationship between siphons and their restrictive induced subgraphs, the supremum of the number of augmented elementary siphons is found. Experimental results show that the set of elementary siphons obtained by the proposed method is more compact and well suits for the class of generalized Petri nets considered.4. In order to improve the structural complexity and behavioral permissiveness for a class of generalized Petri nets, S4PR, a novel deadlock prevention policy is pre-sented. The analysis of generalized Petri nets leads us to characterize deadlock situa-tions in terms of insufficiently marked siphons. The theory of elementary siphons guides our efforts toward the development of structurally simple liveness-enforcing supervisors. Therefore, insufficiently marked siphons can be classified into elementary and dependent ones. The controllability of a dependent siphon can be ensured by properly supervising its elementary ones. In order to find a compact and proper set of elementary siphons, the concept of augmented siphons is proposed for S4PR. Meanwhile, the concept of max’-controlled siphons is employed, which can relax the siphon controllability condition. By explicitly controlling elementary siphons via adding monitors, a live controlled sys-tem can be gained. In addition, the liveness-enforcing supervisor with more permissive behavior is obtained through the rearrangement of the output arcs of monitors. |
PDF Full Text Request