Liveness characteristic analysis of a class of Petri nets

Abstract

Petri nets are an effective tool for analyzing and modeling the dynamic behavior of flexible manufacturing systems. Finite capacity systems of simple sequential processes with resources are an important subclass of Petri nets, for which this article gives a liveness characteristic analysis. First, an effective algorithm for deciding the liveness of finite capacity systems of simple sequential processes with resources is developed by analyzing the relation between the structural properties of resource subnets and the strict minimal siphons. Then, a liveness condition of finite capacity systems of simple sequential processes with resources is accordingly established. Based on the proposed liveness condition, an algorithm for configuring an initial marking for a finite capacity systems of simple sequential processes with resources is given, and therefore, a live finite capacity systems of simple sequential processes with resources net with a configured initial marking can be obtained, which avoids the siphon enumerations and the addition of any control actions. It is shown that the computational complexity of both the developed liveness deciding and the initial marking configuration algorithms is polynomial. Examples are finally provided to illustrate the mentioned results.

Introduction

A flexible manufacturing system (FMS) is a computer-controlled production equipment that consists of a set of workstations and can process different types of parts according to specified sequences of operations. Due to the competition for the limited shared resources such as machines, buffers, and robots, deadlocks often arise in an FMS and lead to a series of catastrophic results. In order to effectively operate an FMS to meet its production targets and avoid deadlocks, it is necessary to dynamically configure the shared resources to satisfy the changes of product specifications. Consequently, many investigations focus on deadlock control in FMSs.^1–5

Due to their appealing formal and graphical representation, Petri nets (PNs) are extensively adopted for modeling, analysis, scheduling,^6–9 and supervisory control^10–12 and hence adopted for handling the deadlock problems in FMSs. A seminal work in Zhou and Dicesare ¹³ contributes a PN model synthesis method for FMSs, where the places in a PN that are modeling of an FMS are first classified to A-, B-, and C-places. Then, on the basis of place classification, Zhou et al. discover the relation between the markings of B- and C-places, at which the PN is live. Consequently, motivated by the work in Zhou and Dicesare, ¹³ many studies on the liveness conditions in terms of initial markings are conducted by DiCesare, Jeng, and Zhou.^14,15 These research works can be summarized as the combination of modeling and control to enforce the liveness of a PN model.

A variety of PN-based approaches are adopted for the deadlock control of FMSs. Generally, there are two main methods: reachability graph (RG) analysis and structural analysis. The RG analysis method takes into account the complete reachable state space of a net model and plays an important role in PN theory since it can be used to solve many other problems such as deadlock control,^11,16–19 controllability analysis,^20,21 and opacity analysis.^22,23 Recently, Chen et al. ²⁴ develop a method to design an optimal PN controller with a special PN structure called data inhibitor, which can lead to a structurally minimal controller on the premise that such a controller exists. Nevertheless, the approaches in Chen et al. ²⁴ cannot deal with a large-scale systems with a large initial marking due to the state explosion problem. ²⁵ The works in Zhao ⁴ provide a deadlock control policy based on the divide-and-conquer strategy. However, the method in Zhao ⁴ has a high computational complexity since it needs to handle a large number of subsystems.

Most of the existing structure-based liveness characteristic analysis approaches are based on siphons, an important structural object of PNs, to achieve the purpose of deadlock control and thus avoid the problem of state explosion. A class of PNs, called system of simple sequential processes with resources (S³ PR) defined by Ezpeleta et al., ²⁶ has attracted the attention of many scholars. It can be adopted for modeling a class of FMSs, in which different types of products can be manufactured concurrently, and each step in a manufacturing process requires only one resource, that is, a machine or a robot. Liveness of an S³ PR is ensured by designing controllers for strict minimal siphons (SMSs) such that they cannot be emptied forever in the controlled system. However, the method presented in Ezpeleta et al. ²⁶ requires too many control places and arcs, and thus leads to a complex controlled system. In order to overcome such defects, Li and Zhou ²⁷ propose a deadlock prevention method by defining the concept of elementary siphons, where by controlling elementary SMSs only, all the SMSs are controlled, resulting in simple monitors and hence a simple controlled system. Then, Hou et al.^28–31 propose the concept of augmented siphons for extending the elementary siphon’s application to a class of generalized PNs. Consequently, on the basis of elementary siphons, many further research have been conducted by Li and Zhou.^32–34

Due to the siphon-based analysis methods, liveness-enforcing supervisors derived from adding control places for siphons are designed by Chao ³⁵ based on siphon controllability conditions of an systems of simple sequential processes with general resources requirement (S³ PGR²). Liu et al. ³⁶ further relax the conditions in Chao ³⁵ to propose a necessary liveness condition for a generalized systems of simple sequential processes with resources (GS³ PR) based on max″-controllability. However, these liveness conditions based on controllability of siphons are realized by solving a mixed integer programming (MIP),^32,37,38 which is a NP-hard problem.

The existing liveness characteristic analysis methods ensure the liveness of a controlled system by designing controllers for siphons in a PN. Nevertheless, as is known, the complexity of computing siphons grows exponentially with respect to the net size.^27,39–41 Different from the existing siphon-based liveness enforcement methods, Liu et al.^36,42 develop policies for resource configuration for a class of extended S³ PR named weighted systems of simple sequential processes with resources (WS³ PR) from a structural standpoint. The resource configuration method in Liu et al. ³⁶ explores the relationship between the initial marking of the resource places and their related arc weights and hence needs to find out all the weighted simple directed circuits (WSDCs) whose number is exponential with the net size. This work deals with finite capacity systems of simple sequential processes with resources (FC-S³ PR) that is a subclass of S³ PR. Compared with S³ PR, an FC-S³ PR is able to specify the capacity of the operation places, and thus model resource allocation concisely. On the basis of the structural analysis of an FC-S³ PR, a liveness deciding condition is proposed, and then an initial marking configuration algorithm to ensure the liveness of an FC-S³ PR is developed. The main contributions contained in this article are stated as follows:

1. An algorithm for deciding the liveness of an FC-S³ PR is explored by utilizing the corresponding relation between perfect resource subnets (PRSs) and their related SMSs in an FC-S³ PR. It is proved that the developed algorithm is of polynomial complexity;

2. A liveness condition of an FC-S³ PR is established on the basis of the proposed liveness deciding algorithm, which avoids computing siphons as well as establishing controllability conditions;

3. Based on the established liveness condition, an initial marking configuration algorithm is presented to compute an initial marking for an FC-S³ PR, at which the configured net is live without changing the structure of the net model.

The remainder of this article is organized as follows. Section “Preliminary” briefly reviews the notations of PNs. The liveness deciding algorithm and liveness condition are established by analyzing the relation between the PRSs and SMSs in section “Liveness characteristic analysis.” Section “Configure initial marking for an FC-S³ PR” presents an initial marking configuration algorithm to compute an initial marking for an FC-S³ PR. The illustrative examples on FC-S³ PR are provided to demonstrate the results in sections “Liveness characteristic analysis” and “Configure initial marking for an FC-S³ PR.” Section “Computational complexity analysis” analyzes the computational complexity of the developed algorithm. Section “Discussion and comparison” gives a discussion and comparison on the proposed method. Finally, section “Conclusion” concludes this study.

Preliminary

Basics of PNs

An ordinary PN ⁴³ is a three-tuple $N=(P,T,F)$ where P and T are finite, nonempty, and disjoint sets. P and T denote a set of places and transitions, respectively. The set $F\subseteq (P\times T)\cup (T\times P)$ is said to be a flow relation of N. Given a net $N=(P,T,F)$ and a node $x\in P\cup T$ , $x^{•}=\{y\in P\cup T|(x,y)\in F\}$ and ${}^{•}x=\{y\in P\cup T|(y,x)\in F\}$ are called the postset and preset of x, respectively. The incidence matrix of N is denoted by $[N]$ : $P\times T\to \{-1,0,1\}$ indexed by P and T such that $[N](p,t)=-1$ if $p\in {}^{•}t\backslash t^{•}$ ; $[N](p,t)=1$ if $p\in t^{•}{\backslash }^{•}t$ ; otherwise $[N](p,t)=0$ .

A marking or a state M of a PN N is a mapping from P to $\mathbb{N}$ . The multi-set $\sum _{p\in P}M(p)p$ is often used to denote M, where $M(p)$ denotes the number of tokens in p at M. For instance, $M=[3,5,8,0{]}^T$ is denoted by $M=3p_1+5p_2+8p_3$ . A place p is said to be marked at M if $M(p)>0$ . A subset p is said to be marked at M if at least one place in $P_S$ is marked at M. $M(P_S)$ indicates the sum of tokens of all places in $P_S$ , that is, $M(P_S)=\sum _{p\in P_S}M(p)$ . A PN N with an initial marking $M_0$ is called a marked net or net system for short, denoted as $(N,M_0)$ .

A nonempty set $S\subseteq P$ is a siphon if ${}^{•}S\subseteq S^{•}$ and S is a trap if $S^{•}{\subseteq }^{•}S$ . A siphon (trap) is said to be marked if at least one place in it has token(s). A siphon is said to be minimal if there is no siphon contained in it as a proper subset. A minimal siphon is strict if it contains no marked trap, that is, SMS.

In an ordinary PN, a transition $t\in T$ is said to be enabled at M if $\forall p{\in }^{•}t$ , $M(p)>0$ . This fact can be denoted as $M[t〉$ . The firing of an enabled transition t can result in a marking $M\prime$ , denoted by $M[t〉M\prime$ with $M\prime (p)=M(p)+N(p,t)$ . $M^{″}$ is said to be reachable from M if there exists a sequence of transitions $\delta =t_1{t}_2\dots t_j$ , $j\in \mathbb{N}$ such that $M[\delta 〉M^{″}$ holds. $R(N,M_0)$ denotes the set of all reachable markings of a PN N from $M_0$ .

FC-S³ PR

Definition 1

A system of simple sequential processes with resources (S³ PR) $N=\underset{i=1}{\overset{q}{◯}}{N}_i=(P_A\cup P^0\cup P_R,T,F)$ is defined as the union of a set of nets $N_i=(P_A^i\cup \{p_0^i\}\cup P_R^i,T^i,F^i)$ sharing common places, where the following statements are true: ²⁶

1. $p_0^i$ is called the process idle place of $N_i$ . Elements in $P_A^i$ and $P_R^i$ are called operation and resource places, respectively;

2. $P_A^i\ne \varnothing$ ; $P_R^i\ne \varnothing$ ; $p_0^i\notin P_A^i$ ; $(P_A^i\cup \{p_0^i\})\cap P_R^i=\varnothing$ ;

3. $\forall p\in P_A^i$ , $\forall t{\in }^{•}p$ , $\forall t\prime \in p^{•}$ , $\exists r_p\in P_R^i$ , ${}^{•}t\cap P_R^i=t{\prime }^{•}\cap P_R^i=\{r_p\}$ ;

4. $\forall r\in P_R^i$ ; ${}^{\mathrm{••}}r\cap P_A^i=r^{••}\cap P_A^i\ne \varnothing$ ; ${}^{•}r\cap r^{•}=\varnothing$ ;

5. ${}^{\mathrm{••}}(p_0^i)\cap P_R^i=(p_0^i{)}^{••}\cap P_R^i=\varnothing$ ;

6. $N_i\prime$ is a strongly connected state machine, where $N_i\prime =(P_A^i\cup \{p_0^i\}\cup T^i\cup F^i)$ is the resulting net after the places in $P_R^i$ and their related arcs are removed from $N_i$ ;

7. Every circuit of $N_i\prime$ contains place $p_0^i$ ;

8. Any two $N_i$ ’s are composable when they share a set of common resource places;

9. For $r\in P_R$ , $H(r)={(}^{••}r)\cap P_A$ is the set of operation places that utilizes resource r and is called the holders of r;

10. For $p\in P_A$ , ${(}^{••}p)\cap P_R=\{r_p\}$ where place $r_p$ is called the resource utilized by p; and

11. An initial marking $M_0$ is called an acceptable one if (a) $p\in P_0$ , $M_0(p)\ge 1$ ; (b) $p\in P_A$ , $M_0(p)=0$ ; and (c) $p\in P_R$ , $M_0(p)\ge 1$ .

Definition 2

Let $\hat{N}=\underset{i=1}{\overset{q}{◯}}{\hat{N}}_i=(P_A\cup P^0\cup P_R,T,F,\hat{C})$ be a finite capacity S³ PR, simply presented as FC-S³ PR, where $\hat{C}:P_A\to \mathbb{N}$ denotes the limited capacity function of the set of operation places in $\hat{N}$ .

From a conceptual standpoint, an FC-S³ PR net has the same structural property as that of an S³ PR and the capacity function is the only difference between them. Note that the capacity function $\hat{C}$ can represent distinct practical meanings on the basis of different considerations, for example, cost or number, in the real systems. In a practical manufacturing system, the processing capacity of a machine is limited. Therefore, the capacity is defined to reflect the maximum number of workpieces that the machine processes at the same time. In a PN model, the capacity of each operation place implies the maximum number of tokens that operation place can hold at any time. It is clear that the upper bound of a maximal capacity for each operation place depends on the initial marking of its related idle places. A simple example of an FC-S³ PR net $\hat{N}$ is depicted in Figure 1(a), where $P_A^1=\{p_2-p_5\}$ , $P_A^2=\{p_6-p_8\}$ , $P_R=\{r_1,r_2,r_3,r_4\}$ , $T^1=\{t_1-t_6\}$ , $T^2=\{t_7-t_{10}\}$ , $\widehat{c}(p_2)=\widehat{c}(p_3)=\widehat{c}(p_4)=\widehat{c}(p_5)=\widehat{c}(p_6)=\widehat{c}(p_7)=\widehat{c}(p_8)=1$ . For instance, $\hat{c}(p_2)=1$ indicates that the maximal number of resources that operation place $p_2$ can possess is one at any marking.

Figure 1.

(a–d) An FC-S³ PR $\hat{N}$ and its three RSs.

Definition 3

Let $(\hat{N},M_0)=(P^0\cup P_A\cup P_R,T,F,\hat{C},M_0)$ be an FC-S³ PR with $P_S\subseteq P_R$ . $(N_S,M_{S_0})=(P_S,T_S,F_S,M_{S_0})$ is called a resource subnet (RS) derived from $P_S$ if (a) $T_S{=}^{•}{P}_S\cap P_S^{•}$ ; (b) $F_S=F\cap [(P_S\times T_S)\cup (T_S\times P_S)]$ ; and (c) $\forall p\in P_S$ , $M_{S_0}(p)=M_0(p)$ .

Let $\hat{N}=(P^0\cup P_A\cup P_R,T,F,\hat{C})$ be an FC-S³ PR and $t\in T$ be a transition. Then, in the following statement, let ${}^{A}t$ (resp., $t^A$ ) denote the input (resp., output) operation place of t, and ${}^{R}t$ (resp., $t^R$ ) denote the input (resp., output) resource place of t. Note that the notation can be extended to sets. For example, $t_3$ is a transition in Figure 1(a), and then we have ${{}^{A}t}_3=\{p_3\}$ , $t_3^A=\{p_4\}$ , ${{}^{R}t}_3=\{r_3\}$ , and $t_3^R=\{r_2\}$ .

Definition 4

Given an RS $N_S=(P_S,T_S,F_S)$ , a transition $t{\in }^{•}{P}_S\cap {P_S}^{•}$ is called a λ-transition if $\exists t\prime {\in }^{•}{P}_S\backslash {P_S}^{•}$ such that ${}^{A}t{\cap }^{A}t\prime \ne \varnothing$ . Let $T_S^{\lambda }$ denote the set of all λ-transitions in $N_S$ .

Consider an RS $N_S$ depicted in Figure 1(c) with $P_S=\{r_1,r_2,r_3\}$ . According to Definition 4, we can find that $t_3$ is a λ-transition in $N_S$ since $\exists t_4{\in }^{•}{P}_S\backslash {P_S}^{•}$ such that ${{}^{A}t}_3{\cap }^A{t}_4=\{p_3\}\ne \varnothing$ .

Definition 5

Let $(\hat{N},M_0)=(P^0\cup P_A\cup P_R,T,F,M_0,\hat{C})$ be an FC-S³ PR with $P_S\subseteq P_R$ . $(N_S,M_{S_0})=(P_S,T_S,F_S,M_{S_0})$ is called a characteristic RS derived from $P_S$ if (a) $T_S={\{}^{•}{P}_S\cap P_S^{•}\}\backslash T_S^{\lambda }$ ; (b) $F_S=F\cap [(P_S\times T_S)\cup (T_S\times P_S)]$ ; and (c) $\forall p\in P_S$ , $M_{S_0}(p)=M_0(p)$ .

Theorem 1

Let $N_S=(P_S,T_S,F_S)$ be a characteristic RS in an FC-S³ PR. $S_S=P_S{\cup }^A{(}^{•}{P}_S\backslash P_S^{•})$ is an SMS iff the characteristic RS $N_S$ derived from $P_S$ is strongly connected.

The proof of Theorem 1 can refer to the proofs of the results in Liu et al. ⁴⁴ For simplicity, in what follows, a strongly connected characteristic RS is denoted as a perfect RS (PRS).

Let $S_S=S_{\mathrm{SA}}\cup S_{\mathrm{SR}}$ be an SMS derived from its related PRS and only made up of operation and resource places. Let $\hat{N}=(P,T,F,\hat{C})$ be an FC-S³ PR net with $P_S\subseteq P_R$ and $N_S=(P_S,T_S,F_S)$ be an RS in N. Then, according to Theorem 1, $S_S$ is an SMS if $S_S=P_S{\cup }^A{(}^{•}{P}_S\backslash P_S^{•})$ . $[S_S]=({\cup }_{r\in S_{\mathrm{SR}}}H(r))\backslash S_S$ is said to be the complementary set of $S_S$ , which denotes a set of operation places that utilizes the resources in $S_S$ , that is to say, the places in $[S_S]$ compete for resources with those in $S_{\mathrm{SA}}$ . When all the resources in $S_S$ are occupied by the places in $[S_S]$ , $S_S$ is emptied forever. Inversely, if the maximal number of tokens in $[S_S]$ at any marking is not greater than the initial marking of $S_S$ , $S_S$ can never be emptied.

Liveness characteristic analysis

Liveness deciding condition

The motivation of the liveness characteristic analysis for an FC-S³ PR is presented and illustrated by an example in this section. A novel liveness deciding algorithm is then developed based on the structural analysis of an FC-S³ PR.

Property 1

Given an S³ PR N with $N=\underset{i=1}{\overset{q}{◯}}{N}_i=(P_A\cup P^0\cup P_R,T,F)$ , where $N_i=(P_A^i\cup \{p_0^i\}\cup P_R^i,T^i,F^i)$ ; let S denote an SMS in N. ²⁶ Then, $\forall M\in R(N,M_0)$ and $\forall i\in \{1,2,\dots ,q\}$ , $\sum _{p\in P_A^i\cup \{p_0^i\}}M(p)=M_0(p_0^i)$ and $\sum _{p\in S\cup [S]}M(p)=\sum _{p\in S}{M}_0(p)$ .

Obviously, this property still holds for an FC-S³ PR net since it has the same net structure as that of an S³ PR. Based on this, we can obtain the following results.

Theorem 2

Let $(\hat{N},M_0)$ be an FC-S³ PR net, where $\hat{C}:P_A\to \mathbb{N}$ denotes the capacity function. Then, the SMS $S=S_A\cup S_R$ can never be emptied in $\hat{N}$ if $\forall r\in S_R$ , $M_0(r)>\sum _{p\in H(r)}\hat{c}(p)$ holds.

Proof

It follows immediately from the fact that $\forall r\in S_R$ , $\forall M\in R(\hat{N},M_0)$ , $M(r)=M_0(r)-\sum _{p\in H(r)}M(p)$ holds. Since $\forall p\in H(r)\cap P_A$ , $\forall M\in R(\hat{N},M_0)$ , $M(p)\le \hat{c}(p)$ holds, we hence have $\sum _{p\in H(r)}M(p)\le \sum _{p\in H(r)}\hat{c}(p)$ . Therefore, $\forall M\in R(\hat{N},M_0)$ ; we have $M(r)\ge M_0(r)-\sum _{p\in H(r)}\hat{c}(p)$ . If $\forall r\in S_R$ , $\forall M\in R(\hat{N},M_0)$ , $M_0(r)>\sum _{p\in H(r)}\hat{c}(p)$ holds, then $M(r)>0$ can be obtained and hence $M(S)>0$ holds. Consequently, the SMS $S=S_A\cup S_R$ can never be emptied in $\hat{N}$ .

Theorem 3

Let $(\hat{N},M_0)$ be an FC-S³ PR net, where $\widehat{C}:P_A\to \mathbb{N}$ denotes the capacity function. Given an RS $N_S=(P_S,T_S,F_S)$ in $\hat{N}$ , we let $S_S=S_{\mathrm{SA}}\cup S_{\mathrm{SR}}$ be an SMS derived from $S_{\mathrm{SR}}\subseteq P_S$ and $r\in S_{\mathrm{SR}}$ . Let $P_S^0=\{p_0^i\in P^0{|}^{••}r\cap P_A^i\ne \varnothing \}$ with $i\in \{1,2,\dots ,q\}$ be a set of process idle places related to r. If $M_0(r)>min\{\sum _{p\in P_S^0}{M}_0(p),\sum _{p{\in }^{••}r\cap P_A^i}\hat{c}(p)\}$ , then $S_S$ can never be emptied in $\hat{N}$ since $\forall M\in R(\hat{N},M_0)$ , $M(S_S)>0$ holds.

Proof

According to Property 1, $\forall M\in R(\hat{N},M_0)$ , $\sum _{p\in P_A^i\cup \{p_0^i\}}M(p)=M_0(p_0^i)$ , $(i\in \{1,2,\dots ,q\})$ and $\sum _{p\in S_S\cup [S_S]}M(p)=M_0(S_S)=M_0(S_{\mathrm{SR}})$ . It is clear that $\forall M\in R(\hat{N},M_0)$ , $\forall p\in P_A^i\cup \{p_0^i\}$ , $M(p)\le M_0(p_0^i)$ holds. Since $\forall M\in R(\hat{N},M_0)$ , $\forall p\in P_A^i$ , $M(p)\le min\{M_0(p_0^i),\hat{c}(p)\}$ , we hence have ${\displaystyle \sum _{p\in [S_S]}M}(p)={\displaystyle \sum _{p\in [S_S]\cup P_A^i}}M(p)\le \min \{{\displaystyle \sum _{p\in [S_S]\cup P_A^i}{M}_0}(p_0^i),{\displaystyle \sum _{p\in [S_S]\cup P_A^i}\widehat{c}}(p)\}$ . Trivially, we have $\sum _{p\in S_S}M(p)\ge \sum _{p\in S_{\mathrm{SR}}}{M}_0(p)-min\{\sum _{p\in [S_S]\cup P_A^i}{M}_0(p_0^i),\sum _{p\in [S_S]\cup P_A^i}\hat{c}(p)\}$ . If $\exists r\in S_{\mathrm{SR}}$ such that $M_0(r)>min\{\sum _{p\in P_S^0}{M}_0(p),\sum _{p{\in }^{••}r\cap P_A^i}\hat{c}(p)\}$ , then $\sum _{p\in S_S}M(p)=M(S_S)>0$ holds since $\sum _{p\in S_{\mathrm{SR}}}{M}_0(p)>min\{\sum _{p\in [S_S]\cup P_A^i}{M}_0(p_0^i),\sum _{p\in [S_S]\cup P_A^i}\hat{c}(p)\}$ . That is to say, the SMS $S_S$ can never be emptied in $\hat{N}$ since $M(S)>0$ . Therefore, the conclusion holds.

Consider an FC-S³ PR net $\hat{N}$ depicted in Figure 1(a), where $P_A=\{p_2-p_8\}$ , $\hat{C}:P_A\to \{1\}$ , and $M_0=3p_0^1+3p_0^2+3r_1+r_2+r_3+r_4$ . Figure 1(b) shows the RS $N_R$ of $\hat{N}$ . Then, a strongly connected RS $N_S$ of $N_R$ shown in Figure 1(c) can be obtained. Obviously, $t_3$ is a λ-transition in $N_S$ according to Definition 4. That is to say, the RS $N_S$ depicted in Figure 1(c) is not a PRS. By deleting $t_3$ in Figure 1(c), a new RS $N_{S_1}$ that is strongly connected can be obtained, as shown in Figure 1(d). It is clear that there is no λ-transition in $N_{S_1}$ , that is, the RS $N_{S_1}$ shown in Figure 1(d) is a PRS, which can derive a corresponding SMS according to Theorem 1. By Property 1, $\hat{c}(p_2)=1$ implies the maximal marking of $p_2$ can hold, that is, $\forall M\in R(\hat{N},M_0)$ , $M(p_2)\le 1<M_0(p_0^1)$ holds. Hence, $M_0(r_1)=3>\min \{{\displaystyle \sum _{p\in P_1^0}{M}_0}(p)=M_0(p_0^1),{\displaystyle \sum _{p{\in }^{••}{r}_1\cap P_A^1}\widehat{c}}(p)=\widehat{c}(p_2)\}=1$ holds. Obviously, the SMS derived by $\{r_1,r_2\}$ in $\hat{N}$ cannot be emptied forever since the resources in $r_1$ cannot be completely occupied. After deleting $r_1$ , no any other RS can be obtained. As a consequence, we can claim that the FC-S³ PR net given in Figure 1(a) is live at $M_0$ .

Based on the analysis of the above example, it makes sense to perform a liveness characteristic analysis for an FC-S³ PR. Instead of siphon-controlled methods, we develop a novel liveness deciding algorithm for an FC-S³ PR that needs to compute all the PRSs by applying Tarjan’s depth first search (DFS) ⁴⁵ approach. A liveness condition of an FC-S³ PR can be explored based on the following developed liveness deciding algorithm.

By executing Algorithm 1, the liveness of an FC-S³ PR $(\hat{N},M_0)$ can be decided. First, an RS $N_R$ can be derived from $P_R$ by Step 1. A set of strongly connected RSs denoted as $\Xi$ can be computed by Tarjan’s DFS by Step 2. Second, for each strongly connected RS, for example, $N_S$ in $\Theta$ , it is necessary to decide whether it is a PRS or not. Given an RS $N_S$ , if there exist λ-transitions by Definition 4, we need to delete λ-transitions and utilize the λ-transitions to decide whether the new RS is a PRS or not. Now, if $T_S^{\lambda }\ne \varnothing$ , then there exist λ-transitions that need to be deleted in $N_S$ , and thus, a new RS $N_S\prime$ can be obtained. By Steps (7)–(9), a set of new strongly connected RSs $\Omega$ can be obtained by applying Tarjan’s DFS to $N_S\prime$ . If $T_S^{\lambda }=\varnothing$ , then it implies that $N_S$ is a PRS. For a resource place r in $N_S$ , if $M_0(r)>min\{\sum _{p\in P_S^0}{M}_0(p),\sum _{p{\in }^{••}r\cap P_A^i}\hat{c}(p)\}$ holds, we delete r in $N_S$ , and a new RS $N_S\prime$ can be obtained. By Steps (11)–(14), a set of new strongly connected RSs $\Lambda$ can be obtained by executing Tarjan’s DFS to $N_S\prime$ . Finally, when $\Xi =\varnothing$ , all the PRSs in $\hat{N}$ are deleted, Algorithm 1 returns $\zeta =\mathrm{Yes}$ .

Algorithm 1. Liveness deciding algorithm for an FC-S3 PR.

Input: An FC-S3 PR $(\hat{N},M_0)$ Output: $\zeta$ , a variable related to liveness for an FC-S3 PR. 1) Compute the RS $N_R$ derived from $P_R$ ; 2)  $\Xi :=\mathrm{Tarjan}\prime s\mathrm{DFS}(N_R)$ ; 3) while { $\Xi \ne \varnothing$ } do 4)   $\zeta :=\mathrm{No};$ 5)  for each $N_S\in \Theta$ do 6)    $\Xi :=\Xi \backslash \{N_S\}$ ; 7)   if $\{T_S^{\lambda }\ne \varnothing \}$ then 8)     $N_S^{\prime }:=N_S\backslash T_S^{\lambda }$ ; 9)     $\Omega :=\mathrm{Tarjan}\prime s\mathrm{DFS}(N_S^{\prime })$ ; 10)   else 11)    if { $\exists r\in P_S$ such that $M_0(r)>min\{\sum _{p\in P_S^0}{M}_0(p),\sum _{p{\in }^{••}r\cap P_A^i}\hat{c}(p)\}$ holds} then 12)      $N_S^{\prime }:=N_S\backslash \{r\}$ ; 13)      $\Lambda :=\mathrm{Tarjan}\prime s\mathrm{DFS}(N_S^{\prime })$ ; 14)    end if 15)   end if 16)   $\Xi :=\Xi \backslash \{N_S\}$ ; 17)  end for 18)  $\Xi :=\Xi \cup \Omega \cup \Lambda \backslash \{N_S\}$ ; 19) end while 20) if { $\Xi ==\varnothing$ } then 21)   $\zeta :=\mathrm{Yes}$ ; 22) end if 23) Output: $\zeta$ ;

Remark 1

By executing Algorithm 1, a result $\zeta$ can be returned, which provides a theory basis for establishing the following liveness condition of an FC-S³ PR net. In addition, Algorithm 2 needs to compute all the PRSs by applying Tarjan’s DFS approach, while the SMS enumerations are avoided. Therefore, the developed liveness deciding algorithm for an FC-S³ PR net is superior to other existing siphon-based works in terms of computational complexity.

Algorithm 2. Initial marking configuration of an FC-S3 PR.

Input: An FC-S3 PR $\hat{N}$ with $M_0^I$ . Output: $M_0$ , a configured initial marking of $\hat{N}$ . 1)  $M_0:=M_0^I$ ; 2) Compute the RS $N_R$ generated from $P_R$ ; 3)  $\Theta :=\mathrm{Tarjan}\prime \mathrm{sDFS}(N_R)$ ; 4) while { $\Theta \ne \varnothing$ } do 5)  for each $N_S\in \Theta$ do 6)   if { $N_S$ is a PRS} then 7)   Let r be a resource place in $N_S$ ; 8)    $M_0(r):=$ min $\{{\displaystyle \sum _{p\in P_S^0}{M}_0}(p),{\displaystyle \sum _{p{\in }^{••}r\cap P_A^i}\widehat{c}}(p)\}+1$ ; 9)    $N_S^{\prime }:=N_S\backslash \{r\}$ ; 10)    $\Lambda :=\mathrm{Tarjan}\prime \mathrm{sDFS}(N_S^{\prime })$ ; 11)   end if 12)   $\Theta :=\Theta \backslash \left\{N_S\right\}$ ; 13. end for 14)   $\Theta :=\Theta \cup \Lambda$ ; 15) end while 16) for each $r\in P_R$ do 17)  if { $M_0(r)==0$ } then 18)    $M_0(r):=1$ ; 19)    $M_0:=M_0+M_0(r)r$ ; 20)  end if 21) end for 22) Output: $M_0$ ;

Theorem 4

Let $(\hat{N},M_0)$ be an FC-S³ PR net. $\hat{N}$ is live at $M_0$ if Algorithm 1 returns $\zeta =\mathrm{Yes}$ .

Proof

After executing Algorithm 1 for an FC-S³ PR $(\hat{N},M_0)$ , a result $\zeta =\mathrm{Yes}$ can be obtained, which implies that all the PRSs in $\hat{N}$ are deleted. Let $N_{S_1}$ and $S_1$ be a PRS and its corresponding SMS in $\hat{N}$ . Let $r_1$ be a resource place in $S_1$ . If the marking of $r_1$ satisfies $M_0(r_1)>min\{\sum _{p\in P_{S1}^0}{M}_0(p),\sum _{p{\in }^{••}{r}_1\cap P_A^i}\hat{c}(p)\}$ , then the SMS $S_1$ derived by the corresponding PRS that contains $r_1$ cannot be emptied according to Theorem 3. Next, $r_1$ is deleted and a new PRS $N_{S_2}$ can be analyzed. Let $S_2$ be an SMS related to $N_{S_2}$ and $r_2$ be a resource place in $S_2$ . If $M_0(r_2)>min\{\sum _{p\in P_{S2}^0}{M}_0(p),\sum _{p{\in }^{••}{r}_2\cap P_A^i}\hat{c}(p)\}$ , then $S_2$ derived by the corresponding PRS $N_{S_2}$ that contains $r_1$ cannot be emptied according to Theorem 3. Similarly, repeat the above procedures until all the PRSs are deleted, that is, Algorithm 1 returns $\zeta =\mathrm{Yes}$ . It implies that each PRS’s corresponding SMS cannot be emptied since there always exists a resource place in its related SMS that cannot be completely occupied. As a conclusion, we can claim that the net is live if Algorithm 1 returns $\zeta =\mathrm{Yes}$ .

Illustrative examples

In this section, two examples on FC-S³ PR nets are used to demonstrate the application of the proposed liveness deciding method. The detailed execution steps of the second example are not listed to save space.

Example 1

Let us consider the FC-S³ PR $(\hat{N},M_0)$ depicted in Figure 2(a) as the first example to illustrate the application of Algorithm 1, where $\hat{C}:P_A\to \{1\}$ . The detailed steps are executed as follows:

1. An RS $N_R$ of N can be generated by $P_R$ , as shown in Figure 2(b).

2. After executing Tarjan’s DFS to $N_R$ , a strongly connected RS $N_S$ can be returned, as shown in Figure 3(a).

3. Obviously, $T_S^{\lambda }=\{t_{12}\}\ne \varnothing$ according to Definition 4.

4. After deleting $t_{12}$ in $N_S$ , we apply Tarjan’s DFS to it. Then, two new strongly connected RSs $N_{S_1}$ and $N_{S_2}$ can be obtained as shown in Figure 3(b) and (c), respectively.

5. (b)For the strongly connected RS $N_{S_2}$ , we have $T_{S_2}^{\lambda }=\varnothing$ . That is to say, $N_{S_2}$ is a PRS. Then, we find that $\exists R_2\in N_{S_2}$ such that $M_0(R_2)>min\{\sum _{p\in P_{S_2}^0}{M}_0(p)=M_0(p_1)=5,\sum _{p{\in }^{••}{R}_2\cap P_A^i}\hat{c}(p)=\hat{c}(p_5)=1\}$ holds. After deleting $R_2$ , no any new strongly connected RS can be found by invoking Tarjan’s DFS.

Algorithm 1 returns $\zeta =\mathrm{Yes}$ .

Figure 2.

(a) An FC-S³ PR $(\hat{N},M_0)$ net and (b) its RS $N_R$ .

Figure 3.

(a–c) Three strongly connected RSs of the net in Figure 2(a).

$\zeta =\mathrm{Yes}$ is returned by executing Algorithm 1, which implies that the FC-S³ PR net $(\hat{N},M_0)$ depicted in Figure 2(a) is live at $M_0$ according to Theorem 4.

Example 2

Consider the FC-S³ PR $(\hat{N},M_0)$ depicted in Figure 4 as the second example to illustrate the application of Algorithm 1, where $\hat{C}:P_A\to \{2\}$ . In order to save space, Table 1 instead of the detailed steps is listed as follows: (a) By Definition 3, the RS $N_1$ of N can be generated by $\{R_1-R_7\}$ . Obviously, $T_1^{\lambda }=\varnothing$ and $M_0(R_1)=5>min\{\sum _{p\in P_1^0}{M}_0(p)=M_0(p_5)=12,\sum _{p{\in }^{••}{R}_1\cap P_A^i}\hat{c}(p)=2\hat{c}(p_6)=4\}$ holds. We delete $R_1$ in $N_1$ and apply Tarjan’s DFS to it. (b) A new strongly connected RS $N_2$ that contains $\{R_2,R_3,R_5-R_7\}$ can be obtained. It is clear that $T_2^{\lambda }=\varnothing$ , that is, $N_2$ is a PRS, and $M_0(R_2)=3>min\{\sum _{p\in P_2^0}{M}_0(p)=M_0(p_5)=12,\sum _{p{\in }^{••}{R}_2\cap P_A^i}\hat{c}(p)=\hat{c}(p_{11})=2\}$ holds. We hence delete $R_2$ in $N_2$ and apply Tarjan’s DFS to it. (c) Then, a new strongly connected RS $N_3$ that contains $\{R_3,R_5-R_7\}$ can be found. Since $T_3^{\lambda }=\varnothing$ and $M_0(R_3)=7>min\{\sum _{p\in P_3^0}{M}_0(p)=M_0(p_1)+M_0(p_5)=17,\sum _{p{\in }^{••}{R}_3\cap P_A^i}\hat{c}(p)=\hat{c}(p_2)+\hat{c}(p_8)+\hat{c}(p_{12})=6\}$ holds, we hence delete $R_3$ in $N_3$ and apply Tarjan’s DFS to it. (d) Then, a new strongly connected RS $N_4$ that contains $\{R_6-R_7\}$ can be returned. Obviously, $T_4^{\lambda }=\varnothing$ and $M_0(R_6)=3>min\{\sum _{p\in P_4^0}{M}_0(p)=M_0(p_5)=12,\sum _{p{\in }^{••}{R}_6\cap P_A^i}\hat{c}(p)=\hat{c}(p_{13})=2\}$ holds. After deleting $R_6$ in $N_4$ , no any other strongly connected RS can be found by Tarjan’s DFS. That is to say, by executing Algorithm 1, $\zeta =\mathrm{Yes}$ is returned. According to Theorem 4, we can claim that the FC-S³ PR net $(\hat{N},M_0)$ depicted in Figure 4 is live at $M_0$ .

Figure 4.

An FC-S³ PR net $(\hat{N},M_0)$ .

Table 1.

Execution processes of Example 2.

$N_i\supseteq P_S$	$\mathrm{Choose}R$	$A=\sum _{p{\in }^{••}R\cap P_A^i}\hat{c}(p)$	$B=\sum M_0(p_0^i)$	$M_0(R)>min\{B,A\}$
(a) $N_1\supseteq \{R_1-R_7\}$	$R_1$	$2\hat{c}(p_6)$	$M_0(p_5)$	Yes
(b) $N_2\supseteq \{R_2,R_3,R_5-R_7\}$	$R_2$	$\hat{c}(p_{11})$	$M_0(p_5)$	Yes
(c) $N_3\supseteq \{R_3,R_5-R_7\}$	$R_3$	$\hat{c}(p_2)+\hat{c}(p_8)+\hat{c}(p_{12})$	$M_0(p_1)+M_0(p_5)$	Yes
(d) $N_4\supseteq \{R_6-R_7\}$	$R_6$	$\hat{c}(p_{13})$	$M_0(p_5)$	Yes

Configure initial marking for an FC-S³ PR

In this section, we deal with the problem of initial marking configuration for an FC-S³ PR and explore the following algorithm by utilizing the developed liveness condition. In order to make the following exposition clear, let $\hat{N}=\underset{i=1}{\overset{q}{◯}}{\hat{N}}_i=(P_A\cup P^0\cup P_R,T,F,\hat{C})$ denote an FC-S³ PR with $\hat{C}:P_A\to \mathbb{N}$ implies the limited capacity function of the set of operation places in $\hat{N}$ , and $M_0^I=\sum _{i\in \{1,\dots ,q\}}{M}_0(p_0^i)p_0^i$ denote the initial marking of only the process idle places at $M_0$ .

By executing Algorithm 2 for an FC-S³ PR net $\hat{N}$ with $M_0^I$ , a configured initial marking $M_0$ can be obtained. The detailed execution procedures of Algorithm 2 are stated as follows. First, an RS $N_R$ can be generated from $P_R$ . We apply Tarjan’s DFS for $N_R$ and obtain a set of strongly connected RSs $\Theta$ . Second, we compute the markings of the resource places for each PRS in $\Theta$ . If $\Theta =\varnothing$ , it implies that the markings of all the PRSs in $N_R$ are configured. In these execution steps, there necessarily exists a part of resource places with $M_0(r)=0$ , $r\in P_R$ . We hence assign marking $M_0(r)=1$ for each of them to satisfy the condition of an acceptable initial marking by Definition 1. By executing Algorithm 2, a configured initial marking $M_0$ of $\hat{N}$ can be ultimately found.

Remark 2

Given an FC-S³ PR net $\hat{N}$ with an initial marking $M_0^I$ , which implies that only the process idle places are initially marked, a configuration marking $M_0$ of $\hat{N}$ can be obtained by Algorithm 2. Obviously, without changing the net structure of a given FC-S³ PR net $\hat{N}$ , we can ensure the liveness of $\hat{N}$ at marking $M_0$ even if $M_0^I$ changes. Then, we can avoid the enumeration of SMSs and implementation of external control actions to make the net live.

Theorem 5

Let $\hat{N}$ be an FC-S³ PR net with an initial marking $M_0^I$ . $M_0$ is the configured initial marking returned by Algorithm 2. Then, $\hat{N}$ is live at $M_0$ .

Proof

Let $S_1$ be an SMS and $r_1$ be a resource place in $S_1$ . If the configuration marking of $r_1$ is allocated with $M_0(r_1)=min\{\sum _{p\in P_1^0}{M}_0(p),\sum _{p{\in }^{••}{r}_1\cap P_A^i}\hat{c}(p)\}+1$ , where $P_1^0=\{p_0^i\in P^0{|}^{•}{r}_1\cap T_1\cap T^i\ne \varnothing \}$ , then $S_1$ generated by the corresponding PRS that contains the resource place $r_1$ cannot be emptied according to Theorem 3. Delete $r_1$ and a resource place $r_2$ can be analyzed. If $M_0(r_2)=min\{\sum _{p\in P_2^0}{M}_0(p),\sum _{p{\in }^{••}{r}_2\cap P_A^i}\hat{c}(p)\}+1$ with $P_2^0=\{p_0^i\in P^0{|}^{•}{r}_2\cap T_2\cap T^i\ne \varnothing \}$ , then we can find that the SMS $S_2$ generated by the PRS that contains $r_2$ cannot be emptied. Analogously, repeat the above procedures, the resource places in each PRS can be configured by Algorithm 2. Note that after executing Algorithm 2, the places in each PRS of an FC-S³ PR are configured. That is to say, each PRS’s corresponding SMS cannot be emptied at the configured initial marking since the configured resource places in their related SMSs cannot be completely occupied. As a result, we can claim that the net $\hat{N}$ is live at $M_0$ .

Example 3

Let us consider the FC-S³ PR $(\hat{N},M_0)$ depicted in Figure 5(a) as an example to illustrate the application of Algorithm 2, where $\hat{C}:P_A\to \{2\}$ . An RS $N_R$ of N can be generated by $P_R$ , as shown in Figure 5(b). Obviously, the RS $N_R$ in Figure 5(b) is a PRS since $T_{N_R}^{\lambda }=\varnothing$ . For the PRS $N_R$ , we configure an initial marking for $p_{18}$ , that is, $M_0(p_{18})=\min \{{\displaystyle \sum _{p\in P_S^0}}{M}_0(p)=M_0(p_1)+M_0(p_8)=16,{\displaystyle \sum _{p{\in }^{••}{p}_{18}\cap P_A^i}\widehat{c}}(p)=\widehat{c}(p_{11})+\widehat{c}(p_5)+2\widehat{c}(p_2)=8\}+1=9$ . After allocating one token for each of the rest resource places, Algorithm 2 returns $M_0=8p_1+8p_8+p_{14}+p_{15}+p_{16}+p_{17}+9p_{18}+p_{19}$ . That is to say, by executing Algorithm 2, a configured initial marking $M_0$ of $\hat{N}$ depicted in Figure 5(a) is returned. According to Theorem 5, the FC-S³ PR net $\hat{N}$ depicted in Figure 5(a) is live at the configured initial marking $M_0$ .

Figure 5.

(a) An FC-S³ PR net $\hat{N}$ and (b) its RS $N_R$ .

Computational complexity analysis

In this section, the computational complexity of the proposed method is analyzed. Let $n=|P|+|T|$ denote the size of an FC-S³ PR $(\hat{N},M_0)$ , where P is the set of places and $T{=}^{•}P\cap P^{•}$ in $\hat{N}$ . In the execution process of Algorithm 1, there are two basic operation processes need to be considered: (a) Find new strongly connected RSs by Tarjan’ DFS after deleting λ-transitions in each strongly connected RS. It is well known that the complexity of Tarjan’ DFS is linear with respect to the net size. ⁴⁵ That is to say, the complexity of Tarjan’ DFS is O(n) at most. Obviously, Tarjan’ DFS is invoked no more than $|T|$ times in the worst case, that is, the computation cost of this part is O(n²). (b) Delete λ-transitions for each strongly connected RS; obviously, the execution times is less than $|T|<n$ ; therefore, its computation cost can be ignored. Consequently, we can find that the overall computational complexity of the developed Algorithm 1 is O(n²). As a result, we draw the conclusion that the developed liveness deciding approach explored in this article is of polynomial complexity.

By the same analysis for the computation procedures as those of Algorithm 1, it is clear that the main computation cost of Algorithm 2 depends on finding new strongly connected RS by Tarjan’s DFS after deleting the configured resource place in each PRS. As stated above, the complexity of Tarjan’s DFS is O(n) at most. Obviously, Tarjan’s DFS is invoked no more than n times at the worst case. Therefore, the computational complexity of the proposed initial marking configuration method by Algorithm 2 is O(n²).

Discussion and comparison

The developed liveness deciding method for an FC-S³ PR in Algorithm 1, from a structural standpoint, avoids the enumeration of SMSs. The existing liveness checking methods via Integrated Net Analyzer (INA) are of exponential computational complexity. ⁴⁶ Some existing approaches by employing the siphon controllability conditions to decide the liveness are based on solving MIP problems, which leads to the fact that many markings computed by solving an MIP problem cannot be actually reached given PN models. It is clear that Algorithm 1 does not need SMS enumeration, while needs to compute all the PRSs by applying Tarjan’s DFS. The complexity of finding PRSs by Tarjan’s DFS is O(n), where n is the size of a given net model. In addition, as stated in section “Computational complexity analysis,” Algorithm 1 that can decide the liveness of an FC-S³ PR net is of polynomial complexity, which is superior to other existing ones in terms of computational complexity.

To our knowledge, different from the existing siphon-based liveness enforcement methods, Liu et al. ³⁶ develop policies for resource configuration for a class of extended S³ PR named WS³ PR. The resource configuration method in Liu et al. ³⁶ needs to find out all the WSDCs whose quantity is $2^m-m-1$ in the worst case, with m being the number of resource places in a net. Obviously, the number of WSDCs is exponential with the net size in the worst case. Thus, the resource configuration method presented in Algorithm 2 is much more efficient than the method in Liu et al. ³⁶ in terms of computational complexity. However, the configured initial marking in our work that can ensure the liveness of an FC-S³ PR net may lead to the resources cannot be fully utilized. That is to say, the proposed method has such a shortcoming, that is, it cannot compute a minimal initial marking for the resource places. Hence, we will then work on this issue in the future.

Conclusion

This article gives a liveness characteristic analysis including dealing with liveness deciding and initial marking configuration for a class of PNs. By analyzing the structural properties of PRSs, a liveness condition is explored for deciding liveness of an FC-S³ PR. On the basis of the developed liveness condition, an algorithm for computing a configured initial marking for each resource place in an FC-S³ PR is provided, which avoids the enumeration of siphons and the implement of any external control actions to ensure the liveness of the net. Without changing the net structure of an FC-S³ PR with an initial marking of the process idle places, a configured initial marking can be returned efficiently by Algorithm 2 in response to the changes of the marking of the process idle places. However, the proposed initial marking configuration approach does not consider the configuration priority as well as the cost of resources. Our future work includes specifying the cost of resources and exploring the configuration priority.