Search

This paper concentrates on robust deadlock control problems for an automated manufacturing system with uncontrollable, unobservable events and resource failures, which is modeled by a subclass of Petri nets. A recovery subnet is added to the holder of each unreliable resource to model resource failure and recovery. In order to prevent a strict minimal siphon in a Petri net model from being emptied, an extended constraint set is constructed based on the complementary set of a strict minimal siphon to obtain a robust liveness constraint. Due to the uncontrollability and unobservability of the transitions, an automated manufacturing system cannot enforce inadmissible robust liveness constraints. It is necessary to decide the admissibility of robust liveness constraints and transform the inadmissible constraints into admissible ones. To this end, a monitor is designed for each admissible robust liveness constraint such that it can be enforced. Finally, an iterative algorithm is developed to perform the above steps and a robust liveness controlled system is obtained. The feasibility of the control strategy is demonstrated by examples. [ABSTRACT FROM AUTHOR]

Automated Manufacturing Systems (AMS) consisting of many cooperating devices incorporated into multiple cooperating production lines, sharing common resources, represent industrial Multi-Agent Systems (MAS). Deadlocks may occur during operation of such MAS. It is necessary to deal with deadlocks (more precisely said, to prevent them) to ensure the correct behavior of AMS. For this purpose, among other methods, methods based on Petri nets (PN) are used too. Because AMS are very often described by PN models, two PN-based methods will be presented here, namely based on (i) PN place invariants (P-invariants); and (ii) PN siphons and traps. Intended final results of usage these methods is finding a supervisor allowing a deadlock-free activity of the global MAS. While the former method yields results in analytical terms, latter one need computation of siphons and traps. [ABSTRACT FROM AUTHOR]

In this paper we show that the dynamics of a class of kinetic compartmental models with bounded capacities, monotone reaction rates and a strongly connected interconnection structure is persistent. The result is based on the chemical reaction network (CRN) and the corresponding Petri net representation of the system. For the persistence analysis, it is shown that all siphons in the Petri net of the studied model class can be characterized efficiently. Additionally, the existence and stability of equilibria are also analyzed building on the persistence and the theory of general compartmental systems. The obtained results can be applied in the analysis of general kinetic models based on the simple exclusion principle. [ABSTRACT FROM AUTHOR]

In an automated manufacturing system (AMS), resources are, in general, subject to unpredictable failures, which invalidate many existing deadlock control strategies. In this article, we propose an adaptive deadlock control policy for an AMS with multiple types of unreliable resources. The considered AMS is modeled with a system of simple sequential processes with resources. First, based on an elementary siphon control method, monitors are added for elementary siphons and some particular dependent siphons to ensure the liveness of a system if there are no resource failures. By considering the fact that an unreliable resource may fail in a system, recovery subnets are added to describe the resource failures and recoveries. Since a monitor added for a siphon may not be able to guarantee that the corresponding siphon is always marked if the failure of a resource in the siphon occurs, the concept of switch controllers is presented so as to make the siphon always remarked if it is emptied by resource failures. It is verified that the adaptive controller proposed in this article can guarantee the liveness of the controlled system no matter whether unreliable resources break down or not. More importantly, if there is no resource failure, the system can maintain predefined production without degrading planned system performance. Finally, examples are presented to illustrate the validity of the proposed method. [ABSTRACT FROM AUTHOR]

A fundamental advantage of Petri net models is the possibility to automatically compute useful system invariants from the syntax of the net. Classical techniques used for this are place invariants, P-components, siphons or traps. Recently, Bozga et al. have presented a novel technique for the parameterized verification of safety properties of systems with a ring or array architecture. They show that the statement "for every instance of the parameterized Petri net, all markings satisfying the linear invariants associated to all the P-components, siphons and traps of the instance are safe" can be encoded in WS1S and checked using tools like MONA. However, while the technique certifies that this infinite set of linear invariants extracted from P-components, siphons or traps are strong enough to prove safety, it does not return an explanation of this fact understandable by humans. We present a CEGAR loop that constructs a finite set of parameterized P-components, siphons or traps, whose infinitely many instances are strong enough to prove safety. For this we design parameterization procedures for different architectures. [ABSTRACT FROM AUTHOR]

Deadlock control of automated manufacturing systems has been widely investigated in recent decades. According to classical Coffman theory, resource circular wait (RW) is viewed as a necessary condition for deadlocks to occur. However, the fact is not as simple as so. Counterexamples are presented to show that RWs do not necessarily appear together with deadlocks. Event circular waits (EWs) are proposed as an alternative to represent a fundamental necessary condition of deadlocks. First, we present the formal definitions of EWs in a type of Petri nets, i.e., weighted augmented marked graphs (WAMGs), and show that EWs are more general and essential than RWs in describing the cause of deadlocks. Second, we show a new classification of siphons, i.e., types I, II, III, and IV, and illustrate the relationship between undermarked siphons and EWs in the WAMGs. Third, we show that EWs are more efficient than RWs for deadlock avoidance since deadlocks can be avoided earlier at a specified marking by using EWs rather than RWs. Several examples are given to clarify the theory throughout this paper.

In supervisory control of Petri nets (PNs), the place-invariant ($P$ -invariant) control principle is the most typical and principal method to deal with the siphon control problem. Although it has a relatively narrow application, this principle is widely acknowledged due to its simplicity and efficiency. In this article, we first propose the extended $P$ -invariant control principle in order to extend the application of $P$ -invariants and provide a general methodology for the control of siphons. Second, three types of $P$ -invariants, from the special to the general, are developed to implicitly or explicitly invariant control the siphons. In the most general case, the virtual $P$ -invariants are constructed in the PNs. Third, the extended principle is further applied to the supervisor simplification. In the paradigm of the extended principle, it presents the redundancy from a structural perspective in contrast to several typical methods, and shows the significant importance of structural analysis in PNs, especially the important role of $P$ -invariants. As a consequence, the extended $P$ -invariant control principle can be considered as the fundamental principle of siphon control as well as its supervisor simplification. [ABSTRACT FROM AUTHOR]

Multidimensional torus interconnect finds wide application in modern exascale computing. For models design in high-performance computing, grid and cloud computing, and also systems biology, two basic ways of specifying spatial structures with Petri nets are considered – an infinite Petri net specified by a parametric expression (PE) and a reenterable coloured Petri net (CPN). The paper studies a composition of hypertorus grid models in the form of a PE and a reenterable CPN, their mutual transformations, and unfolding into a place/transition net; the parameters are the number of dimensions and the size of grid. A grid is composed via connection of neighbouring cells by dedicated transitions modelling channels. Reenterable model peculiarities are explained on step-by-step simulation examples. The rules of mutual transformations of Petri net spatial specifications are specified. Comparative investigation of two mentioned forms of spatial specifications is implemented, including analysis techniques and tools. CPNs are convenient for the state space analysis. The main advantage of PEs is the ability to obtain linear invariants and other structural constructs of Petri nets, for instance, siphons and traps, in parametric form that allows us to draw conclusions on Petri net properties for any values of parameters. [ABSTRACT FROM AUTHOR]

Solving the deadlocks avoidance problem in Resource Allocation Systems (RAS) in Discrete-Event Systems (DES) is a rife problem, especially in Flexible Manufacturing Systems (FMS), alias Automated Manufacturing Systems (AMS). Petri Nets (PN) are an effectual tool often used at this procedure. In principle, there are two basic approaches how to deal with deadlocks in RAS based on PN. They are listed and illustrated here. First of the approaches is realized by means of the supervisor based on P-invariants of PN, while the second one is realized by means of the supervisor based on PN siphons. While the first approach needs to know the reachability graph/tree (RG/RT) expressing the causality of the development of the PN model of RAS, in order to find (after its thorough analysis) the deadlocks, the second approach needs the thorough analysis of the PN model structure by means of finding siphons and traps. Next, both approaches will be applied on the same PN model of RAS and the effectiveness of the achievement of their results will be compared and evaluated. Several simple illustrative examples will be introduced. For the in-depth analysis of the problem of deadlock avoiding, next Part 2 of this paper is prepared, where the newest research will be introduced and illustrated on more complicated examples. If necessary (because of the limited length of particular papers), also the third part - Part 3, will be prepared. [ABSTRACT FROM AUTHOR]

Uzam and Zhou (Uzam, M. and Zhou, M., 2006. An improved iterative synthesis method for liveness enforcing supervisors of flexible manufacturing systems. International Journal of Production Research, 44 (10), 1987-2030) were able to obtain a near optimal controlled model for the net S3PR with 21,562 good states. Chao's deadlock recovery scheme (Chao, D.Y., 2010. Technical Note - Reaching more states for control of FMS. International Journal of Production Research, 48 (4), 1217-1220) improves by reaching more states (21,585). However, this paper identifies a problem and proposes a solution. [ABSTRACT FROM AUTHOR]

Uzam and Zhou (Uzam, M. and Zhou, M., 2006. An improved iterative synthesis approach for liveness enforcing supervisors of flexible manufacturing systems. International Journal of Production Research, 44 (10), 1987-2030) synthesised a near optimal controlled model for a well-known S3PR with 21,562 good states, 19 states short of the optimal one (21,581). It is non-trivial and interesting to synthesise an optimal controlled model as we will present it in this paper. [ABSTRACT FROM AUTHOR]

A deadlock avoidance supervisory controller for Discrete Event (DE) Systems is implemented. The DE controller uses a novel rule-based matrix dispatching formulation (US patent received). This matrix formulation makes it easy to write down the DE controller from standard manufacturing tools such as the bill of materials or the assembly tree. It is shown that the DE controller's matrix form equations plus the Petri Net (PN) marking transition equation provide a complete dynamical description of DE systems. We provide circular wait analysis (CW) for deadlock-free dispatching rules for Multipart Re-entrant Flow line (MRF) regular systems, and provide a regularity test for these systems in PN and matrix notations. We analyse the so-called critical siphons, and certain critical subsystems to develop a DE controller that guaranties deadlock-free dispatching by limiting the work-in-progress in the critical subsystems associated with each CW. This least-restrictive dispatching policy avoids deadlock. The deadlock-free dispatching rules are implemented by the DE controller on a three-robot, two-machine re-entrant flow line, the Intelligent Material Handling cell at the Automation and Robotics Research Institute of UTA. Technical information given includes the development of the deadlock-free controller in LabVIEW. [ABSTRACT FROM AUTHOR]

In this paper we develop concepts to configure deadlock prevention supervisors for Petri Nets (PNs) with an example in Flexible Manufacturing System (FMS). We focus on a subclass of Petri Nets: Systems of Simple Sequential Processes with Resources, S3PR, which allows multiple resource acquisitions and flexible routing. Sequential events have a significant impact on PNs in the dynamics of FMS, presented here as siphons control model. Several trials are required to determine the set of elementary siphons to provide the required effect on the final supervisor in the structurally complex system. Siphons play an important part in Petri Nets applications in representation analysis to resolve deadlock problems in FMS. The control dynamics of FMS are developed based on the structural analysis used in siphons to configure and control supervisors of the system. [ABSTRACT FROM AUTHOR]

Emptiable minimal siphons (EMSs) play a key role in the development of many deadlock control policies for resource allocation systems modeled with Petri nets. Recent research results show that siphon-based deadlock prevention methods can avoid complete siphon enumeration by using mixed-integer programming (MIP). This brief proposes a novel MIP approach, called MIP $'$ for short, to compute EMSs for deadlock control in a class of Petri nets, i.e., a system of simple sequential processes with resources (S3PR). Compared with classical MIP, since MIP $'$ utilizes the structural characteristics of S3PR nets to compute EMSs and more constraints are included in it, its solution space is drastically narrowed. As a result, the number of iterations to solve the MIP $'$ problem is significantly reduced, and the computational efficiency is considerably improved. Comparisons are provided on several S3PR nets to show its superior efficiency. [ABSTRACT FROM AUTHOR]

Scheduling of multicluster tools has received much attention due to its complexity of interaction among cluster tools. A cluster tool comprises several modules such as processing modules, a transfer module with a single or dual-armed handling robot, and loadlock modules. A multicluster tool comprises two, three, or more cluster tools that are interconnected with each other. In this paper, we propose a deadlock prevention policy for noncyclic scheduling of dual-armed multicluster tools. The proposed deadlock prevention policy is effective for generating an efficient schedule for two or three-connected multicluster tools with a single or a dual-path flow. This is proven by analyzing the strict minimal siphon of the Petri net model. The performance of the proposed method is compared with that of a maximal permissible deadlock prevention policy. The results demonstrate that the proposed method is computationally efficient for larger state spaces and more suitable than conventional deadlock prevention policies for generating effective schedules for noncyclic scheduling of multicluster tools. Note to Practitioners—Scheduling of multicluster tools has recently attracted attention in the growing semiconductor manufacturing industry. Most conventional studies on multicluster tools focus on cyclic scheduling to minimize cycle time with swap strategy. The challenge addressed by this paper is to derive a deadlock-free schedule for multicluster tools with noncyclic operations. We propose a simple deadlock prevention policy that can be applied to large-scale timed Petri net (PN) model of general multicluster tools without enumeration of siphon computations or solution of mixed integer programming. A timed PN model is developed for noncyclic operations of dual-armed multicluster tools with a dual ath. The computational results show that the approximately 10% of the total throughput of the proposed method is better than those of the conventional methods. It enables more efficient operations for noncyclic scheduling under transient periods including cleaning operations. [ABSTRACT FROM AUTHOR]

Boolean network modeling of gene regulation but also of post-transcriptomic systems has proven over the years that it can bring powerful analyses and corresponding insight to the many cases where precise biological data is not sufficiently available to build a detailed quantitative model. Besides simulation, the analysis of such models is mostly based on attractor computation, since those correspond roughly to observable biological phenotypes. The recent use of trap spaces made a real breakthrough in that field allowing to consider medium-sized models that used to be out of reach. However, with the continuing increase in model size and complexity of Boolean update functions, the state-of-the-art computation of minimal trap spaces based on prime implicants shows its limits due to the difficulty of the prime-implicant computation. In this article we explore and prove for the first time a connection between trap spaces of a general Boolean network and siphons of its Petri net encoding. Besides important theoretical applications in studying properties of trap spaces, the connection enables us to propose an alternative approach to compute minimal trap spaces, and hence complex attractors, of a general Boolean network. It replaces the need for prime implicants by a completely different technique, namely the enumeration of maximal siphons in the Petri net encoding of the original model. We then demonstrate its efficiency and compare it to the state-of-the-art methods on a large collection of real-world and randomly generated models. [ABSTRACT FROM AUTHOR]

In this paper, we address the problems of enumerating siphons and minimal siphons in ordinary Petri nets (PNs) by resorting to the semi-tensor product (STP) of matrices. First, a matrix equation, called the siphon equation (SE), is established by using STP. Second, an algorithm is proposed to calculate all siphons in ordinary PNs. An example is presented to illustrate the theoretical results and show that the proposed method is more effective than other existing methods in calculating all siphons of PNs. Third, an efficient recursion algorithm is also proposed, which can be applied to computing all minimal siphons for any ordinary PNs. Last, some results on the computational complexity of the proposed algorithms, in this paper, are provided, as well as experimental results. [ABSTRACT FROM PUBLISHER]

Petri Nets are a family of formalisms that allow to effectively model manufacturing systems. The experimental approach method is provided to ensure formally in elementary siphons to distinguish deadlock conditions for a class in terms of generalized Petri nets, namely S4PR. A siphon is a kind of special structural objects of a Petri net and plays an important role in synthesizing a live Petri net controller of flexible manufacturing systems FMS. An FMS corresponds to a class of concurrent systems called Resource Allocation Systems (RASs). The application of Petri Nets (PNs) in RASs is an active research field devoted to defining and exploits different subclasses of Petri Nets allowing modeling the widest set of RAS. A monitor is added for a derived minimal siphon such that it is max-controlled if it is elementary with respect to the siphons that have been derived. Simulation PN to the structural analysis and reachability graph analysis are employed to synthesize and control of FMS. An example is used to illustrate this method. [ABSTRACT FROM AUTHOR]

In this paper a divide-and-conquer-method for the synthesis of liveness enforcing supervisors (LES) for flexible manufacturing systems (FMS) is proposed. Given the Petri net model (PNM) of an FMS prone to deadlocks, it aims to synthesize a live controlled Petri net system. For complex systems, the use of reachability graph (RG) based deadlock prevention methods is a challenging problem, as the RG of a PNM easily becomes unmanageable. To obtain the LESs from a large PNM is usually intractable. In this paper, to ease this problem the PNM of a system is divided into small connected subnets. Each connected subnet prone to deadlocks is then used to compute the LES for the original PNM. Starting from the simplest subnet prone to deadlocks to make the subnet live, monitors (control places) are computed. The RG of each subnet is considered and split into a dead-zone (DZ) and a live-zone. All states in the DZ are prevented from being reached by means of a well-established invariant-based control method. Next, the computation of monitors is followed for bigger subnets. Previously computed monitors are included within the bigger subnets based on a criterion. This process keeps the DZ of the bigger subnets smaller compared with the original uncontrolled subnets. When all subnets are live we obtain a set of monitors that are included within the PNM to obtain a partially controlled PNM (pCPNM). A new set of monitors is also computed for the pCPNM. Finally, a live controlled Petri net system is obtained. The proposed method is generally applicable, easy to use, effective and straightforward although its off-line computation is of exponential complexity in theory. Its use for FMS control guarantees deadlock-free operation and high performance in terms of resource utilization and system throughput. Two FMS deadlock problems from the literature are used to illustrate the applicability and the effectiveness of the proposed method. [ABSTRACT FROM AUTHOR]

Prevention and avoidance of deadlocks in sensor networks that use the wormhole routing algorithm is an active research domain. There are diverse control policies that will address this problem being our approach a new method. In this paper we present a virtual control policy for the new specialized Petri net subclass called Binary Ordered Resources Petri Net (BORPN). Essentially, it is an ordinary class constructed from various state machines that share unitary resources in a complex form, which allows branching and joining of processes. The reduced structure of this new class gives advantages that allow analysis of the entire system’s behavior, which is a prohibitive task for large systems because of the complexity and routing algorithms. [ABSTRACT FROM AUTHOR]

Monitors are added to problematic siphons to avoid deadlocks. Li and Zhou (2004, 2006a,b, 2008a,b,c) add monitors to elementary siphons only while controlling the rest-dependent siphons to save on costs. After failing a marking linear inequality (MLI) test, Li and Zhou perform a linear integer programming (LIP) test (NP-hard). We proposed a new MLI test earlier to avoid the LIP and extended it to systems of simple sequential processes with general resource requirements (S3PGR2) for strongly dependent siphons (SDSs). The control policy for weakly dependent siphons (WDSs) is rather conservative due to some negative terms in the MLI. This paper shows that WDS and SDS have the same controllability (i.e. MLI). As a result, the control for WDS need no longer be that conservative. We also develop an optimization (by redundancy elimination) of the computation required for the LIP test to ensure deadlock prevention of systems of simple sequential processes with resources (S3PR). A favourable result for this policy is that any n-dependent (n . 2) WDS (similar to SDS) needs no monitor and hence the complexity for synthesizing a controller becomes polynomial. Application to a slight variant of a well-known benchmark is illustrated. [ABSTRACT FROM AUTHOR]

The system of simple sequential processes with resources (S3PR) is a class of Petri nets that can model a typical class of resource allocation systems. This paper proposes a method to calculate the number of reachable states of an S3PR. First of all, an upper bound of reachable states of an S3PR can be obtained by combinatorics. The number of unreachable states may be counted in the upper bound because of the existence of shared resources. Hence, the next step is to subtract the number of unreachable states from the upper bound. Here, siphons with two resources derived from resource circuits are used to obtain the number of the unreachable states. The resulting number after subtracting the number of unreachable states from the upper bound is what we are looking for. Finally, example calculations and analyses are conducted to verify the effectiveness of the method. © 2016 Institute of Electrical Engineers of Japan. Published by John Wiley & Sons, Inc. [ABSTRACT FROM AUTHOR]

Traditional region-based liveness-enforcing supervisors focus on (1) maximal permissiveness of not losing legal states, (2) structural simplicity of minimal number of monitors, and (3) fast computation. Lately, a number of similar approaches can achieve minimal configuration using efficient linear programming. However, it is unclear as to the relationship between the minimal configuration and the net structure. It is important to explore the structures involved for the fewest monitors required. Once the lower bound is achieved, further iteration to merge (or reduce the number of) monitors is not necessary. The minimal strongly connected resource subnet (i.e., all places are resources) that contains the set of resource places in a basic siphon is an elementary circuit. Earlier, we showed that the number of monitors required for liveness-enforcing and maximal permissiveness equals that of basic siphons for a subclass of Petri nets modelling manufacturing, called α systems. This paper extends this to systems more powerful than the α one so that the number of monitors in a minimal configuration remains to be lower bounded by that of basic siphons. This paper develops the theory behind and shows examples. [ABSTRACT FROM AUTHOR]

Petri nets are a simple formalism for modeling concurrent computation. They are also an interesting tool for modeling and analysing biochemical reaction systems, bridging the gap between purely qualitative and quantitative models. Biological networks can indeed be complex, large, and with many unknown kinetic parameters, which makes the development of quantitative models difficult. In this paper, we focus on the Petri net representation of biochemical reactions and on two structural properties of Petri nets, siphons and traps, that bring us information about the persistence of some molecular species, independently of the kinetics. We first study the theoretical time complexity of minimal siphon decision problems in general Petri nets, and present three new complexity results: first, we show that the existence of a siphon of a given cardinality is NP-complete; second, we prove that deciding the Siphon-Trap property is co-NP-complete; third, we prove that deciding the existence of a minimal siphon containing a given set of places, deciding the existence of a siphon of a given cardinality and deciding the Siphon-Trap property can be done in linear time in Petri nets of bounded tree-width. Then, we present a Boolean model of siphons and traps, and two method for enumerating all minimal siphons and traps of a Petri net, by using a SAT solver and a Constraint Logic Program (CLP) respectively. On a benchmark of 345 Petri nets of hundreds of places and transitions, extracted from biological models from the BioModels repository, as well as on a benchmark composed of 80 Petri nets from the Petriweb database of industrial processes, we show that both the SAT and CLP methods are overall faster by one or two orders of magnitude compared to the state-of-the-art algorithm from the Petri net community, and are in fact able to solve all the enumeration problems of our practical benchmarks. We investigate why these programs perform so well in practice, and provide some elements of explanation related to our theoretical complexity results. [ABSTRACT FROM AUTHOR]

We propose a new deadlock prevention policy for an important class of resource allocation systems (RASs) that appear in the modeling of flexible manufacturing systems (FMSs). The model of this class in terms of generalized Petri nets is, namely, S4PR. On the basis of recent structural analysis results related to the elementary siphons in generalized Petri nets on one hand and an efficient deadlock avoidance policy proposed for the class of conjunctive/disjunctive (C/D) RASs on the other hand, we show how one can generate monitors to be added to a net system such that all its strict minimal siphons are max′-controlled and no insufficiently marked siphon is generated. Thereby, a new, simple, and more permissive liveness-enforcing supervisor synthesis method for S4PR is established. [ABSTRACT FROM AUTHOR]

In automated manufacturing systems (AMSs), deadlocks problems can arise due to limited shared resources. Petri nets are an effective tool to prevent deadlocks in AMSs. In this paper, a simulation based on existing deadlock prevention policies and different Petri net models are considered to explore whether a permissive liveness-enforcing Petri net supervisor can provide better time performance. The work of simulation is implemented as follows. (1) Assign the time to the controlled Petri net models, which leads to timed Petri nets. (2) Build the Petri net model using MATLAB software. (3) Run and simulate the model, and simulation results are analyzed to determine which existing policies are suitable for different systems. Siphons and iterative methods are used for deadlocks prevention. Finally, the computational results show that the selected deadlock policies may not imply high resource utilization and plant productivity, which have been shown theoretically in previous publications. However, for all selected AMSs, the iterative methods always lead to structurally and computationally complex liveness-enforcing net supervisors compared to the siphons methods. Moreover, they can provide better behavioral permissiveness than siphons methods for small systems. For large systems, a strict minimal siphon method leads to better behavioral permissiveness than the other methods. [ABSTRACT FROM AUTHOR]

Existing policies for deadlock control are mainly based on siphons due to their ability to indicate deadlocks, and can be used as a powerful tool to deal with deadlock situations in flexible manufacturing systems. In order to avoid deadlocks, researchers often add monitors to control siphons. This may result in redundant monitors, unnecessary cost, and restriction of the behavior permissiveness. For example, for a system of sequential systems with shared resources (S4R), the existing deadlock control policies based on max, max′ or max′′-controlled siphons tend to overly restrict the behavior of a controlled system. To ensure maximal permissive behavior of controlled systems, a new concept of siphon controllability named W-control is defined and then a sufficient and necessary condition under which a WS3PR is live if all its siphons are W-controlled. Examples are given to demonstrate them. [ABSTRACT FROM AUTHOR]

Siphons are a kind of special structural objects in a Petri net, and plays a key role in synthesizing a live Petri net controller for flexible manufacturing systems. In order to obtain a small size Petri net controller, this paper introduces the concept of a controllable siphon basis. It then proves that a live Petri net controller can be established by adding a control place and related arcs to each strict minimal siphon (SMS) in a controllable siphon basis. The initial markings of control places are determined by an integer linear program. The number of control places in the obtained controllers is the same as the number of SMSs in the controllable siphon basis, while the latter is no more than that of the activity places in a Petri net model. An algorithm for constructing a controllable siphon basis is proposed, and a new deadlock prevention policy based on it is established. A few examples are provided to demonstrate the proposed concepts and policy and used to compare them with the state-of-the-art methods. [ABSTRACT FROM PUBLISHER]

Unmarked siphons in a Petri net modelling concurrent systems such as those in cloud computing induce deadlocks. The number of siphons grows exponentially with the size of a net. This problem can be relieved by computing compound (or strongly dependent) siphons based on basic siphons. A basic (resp. compound) siphon can be synthesized from an elementary (resp. compound called alternating) resource circuit. It however cannot be extended to cases where two elementary circuits intersect at a directed path rather than a single place (i.e., corresponding to a weakly dependent siphon). This paper develops a uniform formula not only for both cases but also valid for the complementary set of siphon and characteristic vectors. We further propose to generalize it to a compound siphon consisting of $$n$$ basic siphons. This helps simplify the computation and the computer implementation to shorten the program size. Also, the formula is easier to be memorized without consulting the references due to the same underlying physics. [ABSTRACT FROM AUTHOR]

Li and Zhou propose simpler Petri net controllers based on the concept of elementary siphons (generally much smaller than the set of all strict minimum siphons (SMSs) in large Petri nets) to minimise the addition of control places. SMSs can be divided into two groups: elementary and dependant; characteristicT-vectors of the latter are linear combinations of that of the former. AT-vector η is associated with each siphonSsuch that η(i) is the number of tokens gained in or lost fromSby firing transitiontionce. A dependent siphonS0strongly depends on elementary siphonsS1,S2, … ,Skif η0=a1η1+a2η2+ ⋅⋅⋅ +akηkwith allai(i= 1, 2, 3, … ,k) positive.S0is a weakly dependent siphon if someaiis negative. TheT-vectors (resp. number) for elementary siphons are mutually independent (linear to the size of the net). In an earlier paper, we show that there exists a third siphonS3such thatηβ=η1+η2-η3. This equation (called η relationship) plays an important role for optimal control of weakly dependent siphons. However, it assumes that all aboveSspan between exactly two processes. For a well-known benchmark, however, most dependent siphons span more than two processes. This paper improves by removing this restriction and shows thatηβ=η1+η2-η3holds as long asS1∩S2is another emptiable siphon. [ABSTRACT FROM AUTHOR]

This paper deals with the problems of computational and structural complexity in designing maximally permissive liveness-enforcing supervisors for a class of Petri nets called Systems of Simple Sequential Processes with Resources ( S3PR) without ξ-resources. The supervisor consists of two parts: the first part proposes an algorithm to extract a desired emptied strict minimal siphon ( SMS) from a given emptied siphon based on loop resource subsets. This is faster than the existing ones. The second part proposes a siphon-based deadlock prevention policy, which can obtain a maximally permissive liveness-enforcing supervisor with reduced structural complexity and no weighted monitors, owing to the contribution of the first part, which can compute a desired SMS such that one with the smallest number of resource places is selected first for control. Several flexible manufacturing systems are used to show the proposed method and its superior performance over the previous ones. [ABSTRACT FROM AUTHOR]

As a significant structural object, siphons are extensively employed to implement a large number of deadlock prevention and liveness-enforcing methods for flexible manufacturing systems modeled by Petri nets. By linear combinations, a set of elementary siphons is chosen from all strict minimal ones to be controlled and thus the structural complexity of a supervisor is greatly reduced. The concept of elementary siphons is originally proposed for ordinary Petri nets. When applied to generalized Petri nets, their selection and controllability require an additional study. In this work, the concept of augmented siphons is proposed to extend the application of the elementary ones to a class of generalized Petri nets, GLS3 PR. Based on graph theory, a siphon extraction algorithm is developed to obtain all strict minimal siphons, from which augmented elementary ones are computed. In addition, the controllability conditions of dependent siphons are developed. Through fully investigating the net structure, especially weight information, the set of augmented elementary siphons is more compact and well suits for generalized Petri net models under consideration. Some examples are used to illustrate the proposed method. [ABSTRACT FROM AUTHOR]

Prevention and avoidance of deadlocks in sensor networks that use the wormhole routing algorithm is an active research domain. There are diverse control policies that will address this problem being our approach a new method. In this paper we present a virtual control policy for the new specialized Petri net subclass called Binary Ordered Resources Petri Net (BORPN). Essentially, it is an ordinary class constructed from various state machines that share unitary resources in a complex form, which allows branching and joining of processes. The reduced structure of this new class gives advantages that allow analysis of the entire system’s behavior, which is a prohibitive task for large systems because of the complexity and routing algorithms.

In Yan et al. (J Inf Sci Eng 25(1): 167-183, ), a deadlock prevention policy is proposed for a subclass of Petri nets, SPMR, that can well model a large class of flexible manufacturing systems (FMS) where deadlocks are caused by unmarked siphons in their Petri net models. To validate the effectiveness and efficiency of the proposed approach, two examples were demonstrated in Yan et al. (J Inf Sci Eng 25(1): 167-183, ). This paper shows that there is a problem with one of the control places computed for one of the examples. In Yan et al. (J Inf Sci Eng 25(1): 167-183, ), for another example, two different deadlock prevention supervisors were proposed. It is also shown in this paper that, for these two supervisors, it is possible to obtain two subsets of control places. Thus, the structures of the two supervisors are further simplified with the same permissive system behaviours. [ABSTRACT FROM AUTHOR]

Purpose – Siphon-based deadlock control in a flexible manufacturing system (FMS) suffers from the problems of computational and structural complexity since the number of siphons grows exponentially with respect to the size of its Petri net model. In order to reduce structural complexity of a supervisor, a set of elementary siphons derived from all strict minimal siphons (SMS) is explicitly controlled. The purpose of this paper is through fully investigating the structure of a class of generalized Petri nets, WS3PR, to compute all SMS and a compact set of elementary siphons. Design/methodology/approach – Based on graph theory, the concepts of initial resource weighted digraphs and restricted subgraphs are proposed. Moreover, the concept of augmented siphons is proposed to extend the application of elementary siphons theory for WS3PR. Consequently, the set of elementary siphons obtained by the proposed method is more compact and well suits for WS3PR. Findings – In order to demonstrate the proposed method, an FMS example is presented. All SMS and elementary siphons can be derived from initial resource weighted digraphs. Compared with those obtained by the method in Li and Zhou, the presented method is more effective to design a structural simple liveness-enforcing supervisor for WS3PR. Originality/value – This work presents an effective method of computing SMS and elementary siphons for WS3PR. Monitors are added for the elementary siphons only, and the controllability of every dependent siphon is ensured by properly supervising its elementary ones. A same set of elementary siphons can be admitted by different WS3PR with isomorphic structures. [ABSTRACT FROM AUTHOR]

In automated manufacturing systems (AMSs), deadlock problems must be well solved. Many deadlock control policies, which are based on siphons or Resource-Transition Circuits (RTCs) of Petri net models of AMSs, have been proposed. To obtain a live Petri net controller of small size, this paper proposes for the first time the concept of transition covers in Petri net models. A transition cover is a set of Maximal Perfect RTCs (MPCs), and the transition set of its MPCs can cover the set of transitions of all MPCs. By adding a control place with the proper control variable to each MPC in an effective transition cover to make sure that it is not saturated, it is proved that deadlocks can be prevented, whereas the control variables can be obtained by linear integer programming. Since the number of MPCs in an effective transition cover is less than twice that of transition vertices, the obtained controller is of small size. The effectiveness of a transition cover is checked, and ineffective transition covers can be transformed into effective ones. Some examples are used to illustrate the proposed methods and show the advantage over the previous ones. [ABSTRACT FROM AUTHOR]