Received 4 June 2015; accepted 11 July 2015; published 14 July 2015

ABSTRACT

For responsiveness, in the Petri nets theory framework deadlock prevention policies based elementary siphons control are often utilized to deal with deadlocks caused by the sharing of resources in flexible manufacturing system (FMS) which is developing the theory of efficient strict minimal siphons of an S³PR. Analyzer of Petri net models and their P-invariant analysis, and deadlock control are presented as tools for modelling, efficiency structure analysis, control, and investigation of the FMSs when different policies can be implemented for the deadlock prevention. We are to show an effective deadlock prevention policy of a special class of Petri nets namely elementary siphons. As well, both structural analysis and reachability graph analysis and simulation are used for analysis and control of Petri nets. This work is successfully applied Petri nets to deadlock analysis using the concept of elementary siphons, for design of supervisors of some supervisory control problems of FMS and simulation of Petri net tool with MATLAB.

Keywords:

Deadlock Prevention, Siphon, Petri Net, FMSs, PN-Toolbox V. 2.3, S³PR

1. Introduction

A flexible manufacturing system (FMS) is proposed to produce a set of different types of products of varying batch size. It contains a set of computer-controlled machines and transportation systems. Various types of raw components enter it and are processed concurrently. Hence, part resources among various competing jobs have to be carefully controlled and coordinated. For this purpose, a powerful tool for modelling which is called Petri net (PNs) can be used. Petri net is a modelling tool applicable to numerous of FMS.

Petri nets are a favorite tool for depicting and studying information processing systems that are concurrent, asynchronous, synchronous, distributed systems, and reconfiguration structure system. When Petri nets are use of modelling of a real system, a powerful feature of Petri nets is their ability to represent good behavior properties of the system, such as liveness, boundedness, deadlock-free-ness, and reversibility. In FMSs, liveness ensures that deadlocks do not occur. Boundedness guarantees that the number of raw components, buffer spaces and resources is bounded. Reversibility enables the system to return to its initial state, thereby guaranteeing repetitive production. The competition for resources in an FMS may cause it to be deadlocked. In general, a deadlock occurs when the raw components are blocked, while waiting for shared resources held by other production processes.

Abdul-Hussin (2015) [1] studies the synchronization competitive processes to deal with deadlocks caused by the sharing of resources in FMS which is developing the theory for efficient strict minimal siphons for S³PR. An FMS example is used to illustrate the application of the proposed method, and competitive processes are provided in an S³PR to show its superior efficiency. The monitors are used to prevent the presence of unmarked siphons that are the direct causes of deadlocks in such a Petri net. The mathematical computations siphon and trap of Petri net are leading to liveness-enforcing Petri net supervisors with behavior that is more permissive. Petri nets are a modelling and simulation formalism for describing concurrency and synchronization in distributed of FMS.

Abdul-Hussin (2015) [2] presents an approach toward constructing a class structural analysis of Petri nets, where elementary siphon is a main utility used in the development of a deadlock control policy of flexible manufacturing systems (FMSs) that have been exploited successfully for the design of supervisors of some supervisory control problems. Deadlock-free operation of FMSs is significant objectives of siphons in the Petri net. A monitor is added to the plant model such that the siphon is P-invariant-controlled for each elementary siphon, where an integer programming technique is used to guarantee that no emptiable control-induced siphon is generated. The modelling, control and simulation are important topics for both design and operation of FMS. The author [2] has experimental approach based-siphon which is able to resolve the problem of deadlock occurred to Petri nets that are representative of an FMS.

A system of simple sequential processes with resources (S³PR) by Ezpeleta et al. [3] is a powerful Petri net model to describe and analyze the behavior of FMS, and has been adopted widely by many researchers to handle deadlock problems with FMS [1] [3] [4] . Ezpeleta et al. [3] develop a design method of monitor-based liveness Petri net supervisors for FMS, which is usually considered to be a classical contribution that utilizes structural analysis techniques of Petri nets to prevent deadlocks in FMS. The deadlock prevention method can be achieved by adding a control place and related arcs to each strict minimal siphon (SMS), thus the SMS can never be emptied, which guarantees the liveness of the controlled system. There is proposed the relationship between strict minimal siphons and liveness of an S³PR is established. Elementary siphons are first proposed by Li et al. [5] - [7] which are a subclass of SMSs. Apparently, the number is smaller the set of all SMSs. They use the method to control only elementary siphons and prove what the controlled system is live under some conditions.

Huang et al. (2001) [8] propose a strict minimal siphon extraction algorithm such that the complete siphon enumeration is successfully avoided. A shortcoming of their method is that the maximal unmarked siphons need to be computed beforehand, thus the computational efficiency of their method still needs to be improved. Huang et al. (2006) [9] have proposed a deadlock prevention algorithm for S³PR modelled manufacturing systems. The algorithm is an iterative approach based on mixed integer programming (MIP) method [8] . At all iteration, the MIP technique is used to find an unmarked maximal siphon. Next, an unmarked minimal siphon is obtained from the maximal siphon.

Organization. Section 2 provides the preliminaries to be used in this paper. The deadlock control policy is proposed, where is introduced the class (S³PR) of Petri nets models, and the concept of elementary siphons in Section 3. Section 4 presents an FMS example to illustrate the applications of the proposed policy. Section 5 concludes papered.

2. Preliminaries [1] [3]

Definition 1. A Petri net is a 4-tuple Y = (P, T, E, W), where P, and T are finite nonempty, and disjoint sets. P is a set of places, and T is a set of transitions with P È T ≠ Æ, and P Ç T = Æ. E Í (P ´ T) È (T ´ P) is called a flow relation or the set of directed arcs. The net has represented by arcs with arrows from places to transitions or from transitions to places. W: E ® Z⁺ is a mapping that assigns a weight to any arc, where. Y = (P, T, E, W) is ordinary, denoted as Y = (P, T, E, W), (When Weights W, of the arcs (W) = l, the net Y is called ordinary Petri net). The Weights W: (P ´ T) È (T ´ P) ® Z⁺ is a mapping that assigns a weight to an arc: W(x, y) > 0 if (x, y) Î E, and W(x, y) = 0 otherwise, where x, y Î P È T and Z⁺ denote the set of non-negative integers.

Definition 2. In the absence of self-loops, an equivalent information is given by the incidence matrix. The computation of the incidence matrix C is subtracting C⁻ from C⁺ that is: C = (C⁺ − C⁻) or . A Petri net Y = (P, T, E, W) can be alternatively represented by its flow matrix or incidence C = (C_ij) which is defined by: and. In addition, we can write, is the change in matrix C, where incidence matrix [C] of net Y is a |P| × |T| integer matrix and.

Definition 3. The preset of a node is defined as. While the post-set of a node is defined as. This notation can be extended to a set of nodes as: given, and. A marking is a mapping M: P ® Z⁺, where Z⁺ È

{0}. M(p) denotes the number of tokens in place p. The preset (postset) of a set is defined as the union of the presets (postsets) of its elements. The pre- and post-sets of a transition t Î T are defined respectively as:

, and. The pre- and post-sets of a place p Î P are defined respectively as: and.

Definition 4. The pair (Y, M₀) is called a marked Petri net or a net system. The set of markings reachable from M in Y is denoted as R(Y, M). A net (Y, M) is bounded if and only if (iff) $k Î Y, "M Î R(Y, M₀), "p Î P, M(p) ≤ k holds. A transition t Î T is enabled under M, denoted by M[tñ, iff "p Î ∙t, M(p) ≥ 1. A transition t Î T is live under M₀ iff "M Î R(Y, M₀), $M Î R(Y, M₀), M'[tñ holds. (Y, M₀) is deadlock-free iff "M Î R(Y, M₀), ∃t Î T, M[tñ holds. (Y, M₀) is live iff "t Î T, t is live under M₀.

Definition 5. A transition t is said to be live if for any M Î R(Y, M₀), there exists a sequence of transitions that is fired to lead next marking M' that enables at transition t. A PN is said to be live if all the transitions are live. A PN contains a deadlock if there is a marking M Î R(Y, M₀), at which no transition is enabled. Such a marking is called a dead marking. Deadlock situations are because of in appropriate resource allocation policies or exhaustive use of some or all resources. Liveness of a PN means that for each marking M Î R(Y, M₀) reachable from the M₀, it is finally possible to fire t, "t Î T through some firing sequence. A net (Y, M₀) is said to be reversible, if "M Î R(Y, M₀), M₀ Î R(Y, M). Therefore, in a reversible net it is always possible to go back to initial marking M₀. A marking M' is said to be a home state, if for each marking M Î R(Y, M₀), M' is reachable from M. Reversibility is a special case of the home state property. If the home state M' = M₀, then the net is reversible.

Definition 6. A sequence of transitions is a firing sequence of (Y, M₀) if and only if (iff) there exists a sequence of markings such that is: M₀[t₁ñM₁[t₂ñM₂, ××× , [t_nñM_n. Moreover, marking M_n is said to be reachable from M₀ by firing σ, and this is denoted by M₀[σñM_n. The firing sequence is a marking such that: ("i, 1 £ i £ n), and (M_i[t_iñM_i+1), We can also write its by [M₁[sñM_n+1]. The set of all markings reachable from M₀ is denoted by reachability set R(M₀). The function s': T ® Z⁺ is the firing count vector of the firable sequence s, i.e. s¢[t] represents the number of occurrences of t Î T in s. If M₀[sñM', then we can write in vector form M¢ = M₀ + C × s¢, which is referred to as the linear state equation of the net. A marking M₀ is said to be potentially reachable iff $X ≥ 0 such that: M¢ = M₀ + C × s ≥ 0, where s is a firing sequence, a vector which is i-th denotes the number of occurrences of in s. For M₀[σñM_n, we have, which is called the state equation of net Y, where s, called the firing count vector, is a vector which is i-th entry denotes the number of occurrences of t_i in s.

Definition 7. A P-vector is a column vector I: P  →  Z indexed by P, where Z is the set of integers. I is a P-invariant (place invariant) if and only if I  ≠ 0 and I^T × [Y] = 0^T holds. P-invariant I is said to be a P-semiflow

if every element of I is non-negative. is called the support of I. If I is a P-invariant of

(Y, M₀) then "M Î R(Y, M₀): I^T × M  =  I^T× M₀. In an ordinary net, siphon S is controlled by P-invariant I under

M₀ if and only if (I^T × M₀ > 0) and. Such a siphon is called invariant-controlled siphons.

Definition 8. Let S A non-empty sub-set of places. S Í P is a siphon (trap) iff ∙S Í S∙ (resp. Q∙ Í ∙Q). A siphon is said to be minimal iff there is no siphon contained in S it as a proper subset. A minimal siphon that does not contain the support of any P-invariant is called a strict minimal siphon (SMS). A siphon S is controlled iff it can never be emptied. It is said to be invariant-controlled by P-invariant I if I^T × M > 0 and ||I||⁺ Í S.

Definition 9. A PN is live under M₀ iff "t Î T, t is live under M₀. A transition t Î T is live under M₀ iff "M Î R(Y, M₀), $M' Î R(Y, M₀), t is friable under M'. A transition t Î T is dead under M₀ if M ÎR(Y, M₀), where t is friable. A marking M Î R(Y, M₀) is a (total) deadlock iff "t Î T, t is dead.

Definition 10.(Conservative). A Petri Net PN with initial marking M₀ is strictly conservative, if for all markings M, elements of the Reachability set R(M₀), the number of tokens remains constant, i.e. A marked Petri net

Y = (Y, M₀), is said to be conservative iff : "M Î R(M₀). If a marked Petri net is conservative, then the sum of all tokens will remain a constant in all reachable markings:.

A P-invariant characterizes a token conservation rule for a set of places, over which the weighted sum of tokens is constant independently from any firing, i.e., for a p-invariant x and any markings M_i, M_j Î Yⁿ, which are reachable from M₀ by the firing of transitions, it holds. X^T × M = X^T × M₀.

Definition 11. The Pre- and Post-incidence matrix of net Y can be represented as (n ´ m) matrix, Pre-and Post with elements Pre(p_i, t_j), and Post(p_i, t_j), respectively. The linear algebraic analysis method uses the description of a Petri net by its so called incidence matrix C = (C_ij) which is defined by:

is the change in number of tokens in p_i after firing t_j once, for and. Moreover, the incidence matrix C of the net is defined as C = Post-Pre. The incidence

matrix of a net is a matrix with |P| rows and |T| columns defined as pre (P × T) ® {−1, 0, 1} such that pre(p, t) is (+1) if (t, p) Î E, (−1) if (p, t) Î E, and 0 otherwise. The state changes of a PN occur when a transition t is fire. These changes can be representing in an algebraic form using the state equation given by: M₁ = M₀ + post(p, t) − pre(p, t).

Example 1. An example of a Petri net is shown in Figure 1. Places are circles and transitions by rectangles or bars. This is the convention, which has been adopted for ordinary Petri nets when the weight of arcs equals to one. To design a controller to avoid deadlock, it is necessary to find the strict minimal siphons as: S₁ = {p₁, p₃, p₄}, and S₂ = {p₁, p₂, p₄}. The strict minimal trap as Q₁ = {p₁, p₄, p₅}, and Q₂ = {p₁, p₃, p₄}. Siphons are very important in the analysis and control of deadlocks in a Petri net. Any Petri Net can be representation as an incidence matrix. The Petri net of Figure 1 has the following incidence matrices shown in Figure 2.

An important practical, applied definition (6) (linear state equation) is a Petri net a transition t of an ordinary. Petri net is enabled if and only if each of its input places contains at least one token. In this example represented in Figure 1, the initial marking M₀ = [1, 0, 1, 0, 1]^T and the following transitions can be fired starting from M₀.

Applied definition (6), the state equation is: M¢ = M₀ + C × s_ti , and taking the column vector of firing transition from the incidence matrix on Figure 2. The marking evolve M₁ = [0, 1, 1, 1, 1]^T, after the firing of t₁. Such that M₁ = M₀ + C × s_t1 = M₀ [1, 0, 1, 0, 1]^T + column t₁ from matrix Figure 2, [-1, 1, 0, 1, 0]^T = M₁ = [0, 1, 1, 1, 1]^T = M₁. For each of these new marking is representing a node of the reachability tree and used the next state at firing transition. In the sequel, the next marking can be found by adding last marking to the column of transition shown in Figure 2, where transition t₁ is enabled. The new marking M₂ = M₁ + C × s_t2 = [0, 1, 1, 1, 1]^T + [0, -1, -1, 1, 0]^T = [0, 0, 0, 2, 1] = M₂. The next firing transition is t₃, M₃ = M₁ + C × s_t3 = [0, 1, 1, 1, 1]^T + [1, 0, 0, -1, -1]^T = [1, 1, 1, 0, 0] = M₃. The deadlock is occurring at transition t₄, the marking M₉ = [0, 0, 2, 0, 3] as shown in Figure 3, in the red colored. The remainder of the mathematical computation of the net in Figure 1, can be analytically in the reachability tree of a Petri net is shown in Figure 3, where are used Petri net tool for MATLAB, (Toolbox PN-Tool 2.3) [10] .

Additional place V₁, called control place in order to controlled siphon of the net. The simulation and structure analyses of this example are provided to illustrate the feasibility and effectiveness of siphon controlled by adding a monitor that can be enforced on the net dynamics by the addition of a “control” or “monitor” place to the original net structure.

We have predicted a deadlock with a look-ahead Petri net controller. The connections of control places V₁is in the red colored in Figure 4. The resulting controlled Petri net is shown in Figure 5. It can be verified that deadlock does not occur in this Petri net. In the Figure 1, the minimal siphon whose emptiness leads to the deadlock of the net shown in Figure 3. To control the net prevented from being unmarked, a place V₁ is added with ×V₁ = {t₃} and V₁× = {t₄}, as shown in Figure 4, in order to the control is a Petri net in Figure 1. The effecting controlled place in Petri net is shown in Figure 5. It can be verified that deadlock does not occur in this Petri net.

3. Deadlock Prevent Policy

Deadlock prevention policy is dealing with a special class of Petri nets, which is a subclass of ordinary and conservative Petri nets called S³PR. In this a section, we introduced some definitions have been needed for our application for a deadlock prevention policy that can keep the system in deadlock-free for a class of Petri nets, which is called S³PR nets.

3.1. The Class of the S³PR Nets

The class of Petri nets investigated in this research is an S³PR that is first proposed in Ezpeleta et al. [3] . The presentation of its formal definitions is needed for our application. The following results are mainly from [3] [4] .

Definition 12. A simple sequential process (S²P) is a Petri net Y = (P_A È {p⁰}, T, E), where the following statements are true:

1) P_A ¹ Æ is called a set of operation places;

2) p⁰ Ï P_A is called the process idle place;

3) A net Y is a strongly connected state machine; and

4) Every circuit of Y contains place p⁰.

Definition 13. Let Y_i = (P_A È P⁰ È P_R, T, E) be an S³PR. An initial marking M₀ is called an acceptable one if: 1) "p Î P⁰, M₀(p) ≥ 1; 2) "p Î P_A, M₀(p) = 0; and 3) "p Î P_R, M₀(p) ≥ 1.

3.2. Elementary Siphon in Petri Nets

The concepts elementary and dependent siphons are original work by Li et al. [5] - [7] . They are developed the Petri nets theory of computation and powerful mathematics. We have introduced the concept of elementary and dependent siphons as well as used in this paper.

Definition 14. Let S Í p is a subset of places of Petri net Y = (P, T, E, W). P-vector l_S is called the characteristic P-Vector of S if and only if "p Î S, l_S(p) =1; otherwise l_S(p) = 0.

Definition 15. Let h_S is characteristic T-Vector of S if and only if h_S^T = l_S^T = [Y].

Definition 16. Let S Í P is a subset of places of Petri net Y. h_S is characteristic T-Vector of S if and only if h_S = l_S^T∙[C], where C is incidence matrix of Y.

Definition 17. Let Y = (P, T, E, W) is a net with |P| = m, |T| = n, and K siphons S₁ - S_k,. Let l_S (h_S) is the characteristic P(T)-vector of siphon S_i, i Î Y_k. We define [l]_k´m = [l_S1|l_S2|×××|l_Sk]^T, and [h]_k´n = [l]_k´m ´ [Y]_m´n = [h_S1|h_S2|×××|h_Sk]^T. Where [l]([h]) is called the characteristic P(T)-vector matrix of the siphons in net Y.

Definition 18. Let a linearly independent maximal set of Matrix [h]. Then, is called a set of elementary siphons in net Y.

Definition 19. Let S Ï P_E be a siphon in net Y. Then S is called a strongly dependent siphon if holds, where.

Theorem 1. Let Y_ES be the number of elementary siphons in Y = (P, T, E, W). Then we have Y_ES < min{|P|, |T|}. This result indicates that the smaller of a place and transition counts bound the number of elementary siphons in a net.

Theorem 2. Let S be a siphon if net Y = (P, T, E, W) and h_S be its characteristic T-vector. We can conclude that {t Î T|h_S(t) > 0}, {t Î T|h_S(t) = 0}, and {t Î T|h_S(t) < 0} are a sets of transitions that is firings will increase, maintain, and decrease the number of tokens marked in S respectively.

4. Application of Petri Net Modelling in FMSs

Let us assume the small FMS have shown in Figure 6. The system consists of two robots, R1 and R2, each of

which can hold one part at a time, and three machines, M1, M2, and M3. The machine M1 can process only one part at a time, while M2 and M3 can process two parts at a time. Parts enter into the FMS through input/output buffers I1/O1 and I2/O2. In the situation, we consider that there are two part types J1 - J2, can be produced in this system. The production routing of J1 is: I1 ® R1 ® M1 ® O1 or I1 ® R1 ® M2 ® R2 ® M3 ® O1. The production routing of J2 is I2 ® M3 ® R2 ® M2 ® O2.

The S³PR Petri net with 15 places and 11 transitions depicted in Figure 7, which has been considered in the literature (see [3] [6] [8] ). We are choice of different approach to structure and initial markings in order to find out different sets of siphons, and have experienced, and application to show the efficient methods the concept of, elementary and dependent siphons in an S³PR can be controlled net.

The Petri net model of the FMS is shown in Figure 7, in which places p₃, p₄, p₉, p₁₀, p₁₁, denote R1, M1, M2, R2, and M3, respectively. Places p₁ and p₁₅ are idle places, and p₂, p₅, p₆, p₇, p₈, are operation places for production Line_1. Places p₁₂, p₁₃, and p₁₄ are operation places for production Line_2. The Petri net shown in Figure 7 is represented an S³PR by this place specification.

Figure 7 shows the Petri net model of FMS. Places p₂ and p₅ represent the operation of R1, and M1, respectively, for the production sequence of the part type_P₁. Similarly, places p₂, p₆, p₇ and p₈ represent the operation of R1, M2, R2 and M3 respectively, for the production sequence of the part type P₁. The production sequence of the part type_P₂, places p₁₂, p₁₃ and p₁₄ represent the operation of M3, R2 and M2 respectively. The number of tokens in Figure 7, M₀ is an acceptable initial marking if M₀(p₁) = 3, M₀(p₁₅) = 5, M₀(p₉) = M₀(p₁₁) = 2, M₀(p₃) = M₀(p₄) = M₀(p₁₀) = 1, and others are zero.

For the Petri net of Figure 7 is an S³PR. The elements of this net are defined as: Figure 7. , for the process idle places P⁰ = {p₁, p₁₅}, the resource places: P_R = {p₃, p₄, p₉, p₁₀, p₁₁}, holders of resource H(p₃) = (p₂), H(p₉) = {p₆, p₁₄}, H(p₁₀) = {p₇, p₁₃}, and H(p₁₁) ={p₈, p₁₂}.The initial marking of Figure 7, corresponds to the situation when all the resources are idle. The analysis of the behavioral properties of the PN model used Petri net tool with MATLAB [10] starts with consulting its coverability tree key. The reachability graph has 285 states with initial marking, and the deadlock marking is occurring at:

We can be found out the strict minimal siphons. In the Petri net shown in Figure 7, has 10 minimal siphons:

, , ,

, , ,

, , ,.

The set of siphons from S₄ - S₁₀ is both a siphon and a trap. We have choice strict minimal siphons S₁, S₂, and

S₃ that do not contain any trap. The strict minimal siphons are as:

, ,.

We have three the strict minimal:

, , and.

The computation of S₁ and S₂ is leading to determinate the third control place S₃ from the account accumulation of S₁ and S₂ is the linearly independent vectors can be constructed in [η] shown as follows.

, , and.

The T-vector matrix can be strutted in [η] shown as follows:

Therefore, the siphons that correspond to the first and second rows are elementary siphons. Next, we can compute the dependent siphons as: h_S3 = h_S1+ h_S2 . Thus, S₁ = {p₈, p₁₀, p₁₁, p₁₃}, and S₂ = {p₇, p₉, p₁₀, p₁₄}, are elementary siphons and S₃ = {p₈, p₉, p₁₀, p₁₁, p₁₄}, is a strict dependent siphon. The elementary siphons are Π_E = (S₁, S₂), and the dependent siphons Π_D = (S₃), and S₃ is a strongly dependent siphon.

We are representing here a structural analysis method including the following verification on the specification of the elementary siphon of the algorithm found in [6] - [8] , and S₁ and S₂ are elementary siphons in the net for the deadlock control purpose. Therefore, we are connected control place VS₁ to the transition, where: ∙VS₁ = {t₆, t₉}, VS₁∙ = {t₅, t₈}, and ∙VS₂ = {t₄, t₅, t₁₀}, VS₂∙ = {t₁, t₃, t₈}. We can be adding two controls place in the original net. While the third control place is not necessary to add because the simulation of Petri net in Figure 8, do not affected results. The resulting control policy is overly restrictive only, and reachability graph has reduced to 15 states as show in Figure 9.

This is successfully resulted when comparison purposes with the other researcher such as: Ezpeleta et al. [3] computes three control places and has only 28 reachable marking. The method in [6] classifies S₁ and S₂ as elementary siphons and S₃ as strictly dependent. Then, only two controls places are necessary, which actually coincide with the first two control places added by the previous method. In addition, this work has only 28 markings be reachable in the controlled net. The method of Huang et al. (2001) [8] proposed to require three control places, one of which connected with weighted arcs that the controlled net is not ordinary: The controlled net has only 44 reachable markings. In our experiment, we can add two-controlled net has only (15) reachable markings show in Figure 9, without needing third control places, because, the result is not affected to the net (i.e. some results).

The additional controlled places net of Figure 8, is live and obtain to marking M₁₄, and has 15 reachable states marking, so that the Petri net is deadlock-free actually liveness. Siphons are generating even though the monitors are added. An experiment is carried on encouragement one to discover the technicality to make a siphon powerful to control by adding control places (monitor). The result of the efficient structural analysis of Petri nets, because the PN-Toolbox with MATLAB [10] can show the PN shape of the simulation is accurate and correct results.

Let us show the Petri net is modelled in Figure 8. According to definition 7, there are three minimal siphons, which can be emptied. There are S₁ = {p₈, p₁₀, p₁₁, p₁₃}, S₂ = {p₇, p₉, p₁₀, p₁₄}. For the purpose control place VS₁ is added such that I₁ = (0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1VS1) is a P−invariant of (Y₁, M₁). Therefore, I₁ × M₁ = 0 by definition 7, we can compute that [(Y₁](VS₁, t) = − t₅ + t₆ − t₈ + t₉. Similarly, I₂ = (0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1VS₂) is also a P−invariant of (Y₁, M₁). Hence (I₂ × M₁) = 0, and [Y₁](VS₂, t) = − t₁ − t₃ + t₄ + t₅ − t₈ + t₁₀, than reachability tree reachable to M₁₄ as shown in Figure 9.

For elementary siphons S₁ and S₂, three monitor VS₁ and VS₂ are added respectively to the net. We can apply definition 7, to find a P-invariant controlled of the Petri net depending of the incidence matrix existing in Figure 10, implementation manuals.

Petri net incidence matrix and P-invariant

Figure 10. The incidence matrix of Figure 8, and P-invariant.

For instance, Figure 8 has shown an S³PR net. S₁ = {p₈, p₁₀, p₁₁, p₁₃} is a siphon of the net. We can apply definition 7, to find a P-invariant of the net in Figure 10. This is: I₁ = (0, −1, −1, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, −1VS₁)^T = (−p₂ − p₃ + p₈ + p₁₀ + p₁₁ + p₁₃ − VS₁) is a P-invariant of (Y₁, M₁). Where, I^T × M₀ = M(p₈) + M(p₁₀) + M(p₁₁) + M(p₁₃) − M(p₂) − M(p₃) − M(VS₁) = 1 > 0. So that ||I₁||⁺ = {p₈, p₁₀, p₁₁, p₁₃} Í S. Thus, S₁ = {p₈, p₁₀, p₁₁, p₁₃} is an invariant-controlled siphon and it can never be emptiable. Similarly, for S₂ = {p₇, p₉, p₁₀, p₁₄} is a siphon of the net. Also, I₂ = (1, 0, 0, 0, 0, 1, 1, 0, 1, 1, −1, −1, 0, 1, 0, −1VS₁ − 1VS₂)^T = {p₁ + p₆ + p₇ + p₉ + p₁₀− p₁₁ − p₁₂ + p₁₄ − VS₁ − VS₂} is a P−invariant of (Y₁, M₁). Where, I^T × M₀ = {M(p₁) + M(p₆) + M(p₇) + M(p₉) + M(p₁₀) − M(p₁₁) − M(p₁₂) + M(p₁₄)− M(VS₁) − M(VS₂)} = 1 > 0. So that: ||I₂||⁺ = {p₇, p₉, p₁₀, p₁₄} Í S, is an invariant-controlled siphon and it can never be emptied.

In addition, there are five resources in this system of Figure 7, leading to five minimal P-invariants, we would like to mention as follow:

, where,

, where,

, where,

, ,

,.

This has been done with a Laptop computer, Intel(R) Core(TM) i5-3337U CPU@ 1.80GHz, with 4Gb of RAM, with Windows 7 Ultimate.

5. Conclusion

Petri net is possible to represent of FMS that can be simulation and analysis is supported by different visualization and interaction techniques to capture the properties such as strict minimal siphons, and behaviour of Petri nets quickly (e.g. interactive behavior, interactive exploration of invariants and the reachability graph). We are developing a guarantees tool for Petri net based to siphon, simulation and structural analysis dealing with the (FMS). Some control places and related arcs are added to minimal siphons such that no siphon can be emptied. A Petri net is efficient techniques to enumerate and reduce the reachability graph by adding monitors to all basic siphons and only those compound siphons. The reachability graph is reduced to explain the necessary evolutionary behavior of the PN regarding liveness and deadlocks. Based on Petri nets, a deadlock prevention policy is proposed to a special class of Petri nets called (S³PR).

Cite this paper

Mowafak HassanAbdul-Hussin, (2015) Elementary Siphons of Petri Nets and Deadlock Control in FMS. Journal of Computer and Communications,03,1-12. doi: 10.4236/jcc.2015.37001

References