Sage Journals: Discover world-class research

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.

Keywords

Flexible manufacturing system Petri net liveness characteristic analysis

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:

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;

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;

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 \ t^{•}$ ; $[N] (p, t) = 1$ if $p \in t^{•} \^{•} t$ ; otherwise $[N] (p, t) = 0$ .

A marking or a state M of a PN N is a mapping from P to $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 = 3 p_{1} + 5 p_{2} + 8 p_{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'$ , denoted by $M [t 〉 M'$ with $M' (p) = M (p) + N (p, t)$ . $M^{″}$ is said to be reachable from M if there exists a sequence of transitions $δ = t_{1} t_{2} \dots t_{j}$ , $j \in N$ such that $M [δ 〉 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 = ◯_{i = 1}^{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:²⁶

$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;

$P_{A}^{i} \neq \emptyset$ ; $P_{R}^{i} \neq \emptyset$ ; $p_{0}^{i} \notin P_{A}^{i}$ ; $(P_{A}^{i} \cup {p_{0}^{i}}) \cap P_{R}^{i} = \emptyset$ ;

$\forall p \in P_{A}^{i}$ , $\forall t \in^{•} p$ , $\forall t' \in p^{•}$ , $\exists r_{p} \in P_{R}^{i}$ , ${}^{•}t \cap P_{R}^{i} = t'^{•} \cap P_{R}^{i} = {r_{p}}$ ;

$\forall r \in P_{R}^{i}$ ; ${}^{••}r \cap P_{A}^{i} = r^{• •} \cap P_{A}^{i} \neq \emptyset$ ; ${}^{•}r \cap r^{•} = \emptyset$ ;

${}^{••}(p_{0}^{i}) \cap P_{R}^{i} = (p_{0}^{i})^{• •} \cap P_{R}^{i} = \emptyset$ ;

$N_{i}'$ is a strongly connected state machine, where $N_{i}' = (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}$ ;

Every circuit of $N_{i}'$ contains place $p_{0}^{i}$ ;

Any two $N_{i}$ ’s are composable when they share a set of common resource places;

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;

For $p \in P_{A}$ , $(^{• •} p) \cap P_{R} = {r_{p}}$ where place $r_{p}$ is called the resource utilized by p; and

An initial marking $M_{0}$ is called an acceptable one if (a) $p \in P_{0}$ , $M_{0} (p) \geq 1$ ; (b) $p \in P_{A}$ , $M_{0} (p) = 0$ ; and (c) $p \in P_{R}$ , $M_{0} (p) \geq 1$ .

Definition 2

Let $\hat{N} = ◯_{i = 1}^{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 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}}$ , $\hat{c} (p_{2}) = \hat{c} (p_{3}) = \hat{c} (p_{4}) = \hat{c} (p_{5}) = \hat{c} (p_{6}) = \hat{c} (p_{7}) = \hat{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' \in^{•} P_{S} \ {P_{S}}^{•}$ such that ${}^{A}t \cap^{A} t' \neq \emptyset$ . Let $T_{S}^{λ}$ 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} \ {P_{S}}^{•}$ such that ${{}^{A}t}_{3} \cap^{A} t_{4} = {p_{3}} \neq \emptyset$ .

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}^{•}} \ T_{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)$ .

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} \ 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_{SA} \cup S_{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} \ P_{S}^{•})$ . $[S_{S}] = (\cup_{r \in S_{SR}} H (r)) \ 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_{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 = ◯_{i = 1}^{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 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) \leq \hat{c} (p)$ holds, we hence have $\sum_{p \in H (r)} M (p) \leq \sum_{p \in H (r)} \hat{c} (p)$ . Therefore, $\forall M \in R (\hat{N}, M_{0})$ ; we have $M (r) \geq 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 $\hat{C} : P_{A} \to ℕ$ denotes the capacity function. Given an RS $N_{S} = (P_{S}, T_{S}, F_{S})$ in $\hat{N}$ , we let $S_{S} = S_{SA} \cup S_{SR}$ be an SMS derived from $S_{SR} \subseteq P_{S}$ and $r \in S_{SR}$ . Let $P_{S}^{0} = {p_{0}^{i} \in P^{0} |^{• •} r \cap P_{A}^{i} \neq \emptyset}$ 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_{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) \leq M_{0} (p_{0}^{i})$ holds. Since $\forall M \in R (\hat{N}, M_{0})$ , $\forall p \in P_{A}^{i}$ , $M (p) \leq min {M_{0} (p_{0}^{i}), \hat{c} (p)}$ , we hence have $\sum_{p \in [S_{S}]} M (p) = \sum_{p \in [S_{S}] \cup P_{A}^{i}} M (p) \leq \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)}$ . Trivially, we have $\sum_{p \in S_{S}} M (p) \geq \sum_{p \in S_{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_{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_{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} = 3 p_{0}^{1} + 3 p_{0}^{2} + 3 r_{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}) \leq 1 < M_{0} (p_{0}^{1})$ holds. Hence, $M_{0} (r_{1}) = 3 > \min {\sum_{p \in P_{1}^{0}} M_{0} (p) = M_{0} (p_{0}^{1}), \sum_{p \in^{• •} r_{1} \cap P_{A}^{1}} \hat{c} (p) = \hat{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 $Ξ$ can be computed by Tarjan’s DFS by Step 2. Second, for each strongly connected RS, for example, $N_{S}$ in $Θ$ , 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}^{λ} \neq \emptyset$ , then there exist λ-transitions that need to be deleted in $N_{S}$ , and thus, a new RS $N_{S}'$ can be obtained. By Steps (7)–(9), a set of new strongly connected RSs $Ω$ can be obtained by applying Tarjan’s DFS to $N_{S}'$ . If $T_{S}^{λ} = \emptyset$ , 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}'$ can be obtained. By Steps (11)–(14), a set of new strongly connected RSs $Λ$ can be obtained by executing Tarjan’s DFS to $N_{S}'$ . Finally, when $Ξ = \emptyset$ , all the PRSs in $\hat{N}$ are deleted, Algorithm 1 returns $ζ = Yes$ .

Algorithm 1. Liveness deciding algorithm for an FC-S³ PR.
Input: An FC-S³ PR $(\hat{N}, M_{0})$ Output: $ζ$ , a variable related to liveness for an FC-S³ PR. 1) Compute the RS $N_{R}$ derived from $P_{R}$ ; 2) $Ξ : = Tarjan' s DFS (N_{R})$ ; 3) while { $Ξ \neq \emptyset$ } do 4) $ζ : = No;$ 5) for each $N_{S} \in Θ$ do 6) $Ξ : = Ξ \ {N_{S}}$ ; 7) if ${T_{S}^{λ} \neq \emptyset}$ then 8) $N_{S}^{'} : = N_{S} \ T_{S}^{λ}$ ; 9) $Ω : = Tarjan' s DFS (N_{S}^{'})$ ; 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}^{'} : = N_{S} \ {r}$ ; 13) $Λ : = Tarjan' s DFS (N_{S}^{'})$ ; 14) end if 15) end if 16) $Ξ : = Ξ \ {N_{S}}$ ; 17) end for 18) $Ξ : = Ξ \cup Ω \cup Λ \ {N_{S}}$ ; 19) end while 20) if { $Ξ = = \emptyset$ } then 21) $ζ : = Yes$ ; 22) end if 23) Output: $ζ$ ;

Algorithm 1. Liveness deciding algorithm for an FC-S³ PR.

Input: An FC-S³ PR

(\hat{N}, M_{0})

Output:

ζ

, a variable related to liveness for an FC-S³ PR.
1) Compute the RS

N_{R}

derived from

P_{R}

;
2)

Ξ : = Tarjan' s DFS (N_{R})

;
3) while {

Ξ \neq \emptyset

} do
4)

ζ : = No;

5) for each

N_{S} \in Θ

do
6)

Ξ : = Ξ \ {N_{S}}

;
7) if

{T_{S}^{λ} \neq \emptyset}

then
8)

N_{S}^{'} : = N_{S} \ T_{S}^{λ}

;
9)

Ω : = Tarjan' s DFS (N_{S}^{'})

;
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}^{'} : = N_{S} \ {r}

;
13)

Λ : = Tarjan' s DFS (N_{S}^{'})

;
14) end if
15) end if
16)

Ξ : = Ξ \ {N_{S}}

;
17) end for
18)

Ξ : = Ξ \cup Ω \cup Λ \ {N_{S}}

;
19) end while
20) if {

Ξ = = \emptyset

} then
21)

ζ : = Yes

;
22) end if
23) Output:

ζ

;

Remark 1

By executing Algorithm 1, a result $ζ$ 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-S³ PR.
Input: An FC-S³ 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) $Θ : = Tarjan' sDFS (N_{R})$ ; 4) while { $Θ \neq \emptyset$ } do 5) for each $N_{S} \in Θ$ do 6) if { $N_{S}$ is a PRS} then 7) Let r be a resource place in $N_{S}$ ; 8) $M_{0} (r) : =$ min ${\sum_{p \in P_{S}^{0}} M_{0} (p), \sum_{p \in^{• •} r \cap P_{A}^{i}} \hat{c} (p)} + 1$ ; 9) $N_{S}^{'} : = N_{S} \ {r}$ ; 10) $Λ : = Tarjan' sDFS (N_{S}^{'})$ ; 11) end if 12) $Θ : = Θ \ {N_{S}}$ ; 13. end for 14) $Θ : = Θ \cup Λ$ ; 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}$ ;

Algorithm 2. Initial marking configuration of an FC-S³ PR.

Input: An FC-S³ 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)

Θ : = Tarjan' sDFS (N_{R})

;
4) while {

Θ \neq \emptyset

} do
5) for each

N_{S} \in Θ

do
6) if {

N_{S}

is a PRS} then
7) Let r be a resource place in

N_{S}

;
8)

M_{0} (r) : =

min

{\sum_{p \in P_{S}^{0}} M_{0} (p), \sum_{p \in^{• •} r \cap P_{A}^{i}} \hat{c} (p)} + 1

;
9)

N_{S}^{'} : = N_{S} \ {r}

;
10)

Λ : = Tarjan' sDFS (N_{S}^{'})

;
11) end if
12)

Θ : = Θ \ {N_{S}}

;
13. end for
14)

Θ : = Θ \cup Λ

;
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 $ζ = Yes$ .

Proof

After executing Algorithm 1 for an FC-S³ PR $(\hat{N}, M_{0})$ , a result $ζ = 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_{S 1}^{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_{S 2}^{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 $ζ = 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 $ζ = 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:

An RS $N_{R}$ of N can be generated by $P_{R}$ , as shown in Figure 2(b).

After executing Tarjan’s DFS to $N_{R}$ , a strongly connected RS $N_{S}$ can be returned, as shown in Figure 3(a).

Obviously, $T_{S}^{λ} = {t_{12}} \neq \emptyset$ according to Definition 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.

(a) For the strongly connected RS $N_{S_{1}}$ , it is clear that $T_{S_{1}}^{λ} = {t_{3}} \neq \emptyset$ . After deleting $t_{3}$ , no any new strongly connected RS can be found by utilizing Tarjan’s DFS.

(b)For the strongly connected RS $N_{S_{2}}$ , we have $T_{S_{2}}^{λ} = \emptyset$ . 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 $ζ = 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).

$ζ = 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}^{λ} = \emptyset$ 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}^{λ} = \emptyset$ , 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}^{λ} = \emptyset$ 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}^{λ} = \emptyset$ 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, $ζ = 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}$	$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} = ◯_{i = 1}^{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 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 $Θ$ . Second, we compute the markings of the resource places for each PRS in $Θ$ . If $Θ = \emptyset$ , 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} \neq \emptyset}$ , 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} \neq \emptyset}$ , 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}}^{λ} = \emptyset$ . For the PRS $N_{R}$ , we configure an initial marking for $p_{18}$ , that is, $M_{0} (p_{18}) = \min {\sum_{p \in P_{S}^{0}} M_{0} (p) = M_{0} (p_{1}) + M_{0} (p_{8}) = 16, \sum_{p \in^{• •} p_{18} \cap P_{A}^{i}} \hat{c} (p) = \hat{c} (p_{11}) + \hat{c} (p_{5}) + 2 \hat{c} (p_{2}) = 8} + 1 = 9$ . After allocating one token for each of the rest resource places, Algorithm 2 returns $M_{0} = 8 p_{1} + 8 p_{8} + p_{14} + p_{15} + p_{16} + p_{17} + 9 p_{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.

Footnotes

Handling Editor: Yangmin Li

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This work was supported in part by the National Natural Science Foundation of China under grant no. 61472295 and the Doctoral Scientific Research Foundation of SUST under grant nos 2016BJ-15 and 2017BJ-39.

ORCID iD

Miao Liu

References

Liu

Hanisch

M-H

et al . Deadlock prevention based on structure reuse of Petri net supervisors for flexible manufacturing systems. IEEE T Syst Man Cy A 2012; 42: 178–191.

Zhou

. Deadlock control of automated manufacturing systems based on Petri nets—a literature review. IEEE T Syst Man Cy C 2012; 42: 437–462.

Xing

Han

Zhou

et al . Deadlock-free genetic scheduling algorithm for automated manufacturing systems based on deadlock control policy. IEEE T Syst Man Cy B 2012; 42: 603–615.

Zhao

. An integrated control method for designing non-blocking supervisors using Petri nets. Adv Mech Eng 2017; 9: 1–17.

Zhao

Uzam

. A suboptimal deadlock control policy for designing non-blocking supervisors in flexible manufacturing systems. Inform Sci 2017; 388–389: 135–153.

Giua

. Cycle time optimization of deterministic timed weighted marked graphs by transformation. IEEE T Contr Syst T 2017; 25: 1318–1330.

Giua

. Optimization of deterministic timed weighted marked graphs. IEEE T Autom Sci Eng 2017; 14: 1084–1095.

Zhou

. Short-term scheduling of crude-oil operations: Petri net-based control-theoretic approach. IEEE Robot Autom Mag 2015; 22: 64–76.

Zhou

Bai

et al . Short-term scheduling of crude oil operations in refinery with high fusion point oil and two transportation pipelines. Enterp Inform Syst 2016; 10: 581–610.

10.

Wang

Khemaissia

Khalgui

et al . Dynamic low-power reconfiguration of real-time systems with periodic and probabilistic tasks. IEEE T Autom Sci Eng 2015; 12: 258–271.

11.

Wang

Wonham

. Dynamic multiple-period reconfiguration of real-time scheduling based on timed DES supervisory control. IEEE T Ind Inform 2016; 12: 101–111.

12.

Zhang

Khalgui

et al . Reconfigurable coordination of distributed discrete event control systems. IEEE T Contr Syst T 2015; 23: 323–330.

13.

Zhou

Dicesare

. Parallel and sequential exclusions for Petri net modeling for manufacturing systems. IEEE T Robotic Autom 1991; 7: 515–527.

14.

Jeng

Dicesare

. A review of synthesis techniques for Petri nets with applications to automated manufacturing systems. IEEE T Syst Man Cyb 1993; 23: 301–312.

15.

Jeng

. A Petri net synthesis theory for modeling flexible manufacturing systems. IEEE T Syst Man Cy B 1997; 27: 169–183.

16.

Chen

Barkaoui

. New Petri net structure and its application to optimal supervisory control: interval inhibitor arcs. IEEE T Syst Man Cy: S 2014; 44: 1384–1400.

17.

Chen

Barkaoui

et al . On the enforcement of a class of nonlinear constraints on Petri nets. Automatica 2015; 55: 116–124.

18.

Chen

Al-Ahmari

et al . Deadlock recovery for flexible manufacturing systems modeled with Petri nets. Inform Sci 2017; 381: 290–303.

19.

Uzam

Gelen

et al . A divide-and-conquer-method for the synthesis of liveness enforcing supervisors for flexible manufacturing systems. J Intell Manuf 2016; 27: 1111–1129.

20.

Tong

et al . Basis marking representation of Petri net reachability spaces and its application to the reachability problem. IEEE T Automat Contr 2017; 62: 1078–1093.

21.

Giua

. Characterization of admissible marking sets in Petri nets with conflicts and synchronizations. IEEE T Automat Contr 2017; 62: 1329–1341.

22.

Tong

Giua

. On the equivalence of observation structures for Petri net generators. IEEE T Automat Contr 2016; 61: 2448–2462.

23.

Tong

Seatzu

et al . Verification of state-based opacity using Petri nets. IEEE T Automat Contr 2017; 62: 2823–2837.

24.

Chen

Barkaoui

et al . Compact supervisory control of discrete event systems by Petri nets with data inhibitor arcs. IEEE T Syst Man Cy: S 2017; 47: 364–379.

25.

Ciardo

. Reachability set generation for Petri nets: can brute force be smart? In: Proceedings of the 25th international conference applications and theory of Petri nets and concurrency, LNCS, Bologna, 21–25 June 2004, pp.17–34. New York: Springer.

26.

Ezpeleta

Colom

Martinez

. A Petri net based deadlock prevention policy for flexible manufacturing systems. IEEE T Robotic Autom 1995; 11: 173–184.

27.

Zhou

. Elementary siphons of Petri nets and their application to deadlock prevention in flexible manufacturing systems. IEEE T Syst Man Cy A 2004; 34: 38–51.

28.

Hou

Zhao

et al . Extended elementary siphon-based deadlock prevention policy for a class of generalized Petri nets. Int J Comp Integ M 2014; 27: 85–102.

29.

Hou

Al-Ahmari

. Extended elementary siphons and their application to liveness-enforcement of generalized Petri nets. Asian J Control 2014; 16: 1789–1810.

30.

Hou

Zhao

et al . Extraction of elementary siphons in a class of generalized Petri nets using graph theory. Eng Comput 2014; 31: 331–352.

31.

Hou

Barkaoui

. Deadlock analysis and control based on Petri nets: a siphon approach review. Adv Mech Eng 2017; 9: 1–30.

32.

Zhou

. Two-stage method for synthesizing liveness-enforcing supervisors for flexible manufacturing systems using Petri nets. IEEE T Ind Inform 2006; 2: 313–325.

33.

Zhou

. On siphon computation and deadlock control for a class of Petri nets. IEEE T Syst Man Cy A38: 667–679.

34.

Zhao

. On controllability of dependent siphons for deadlock prevention in generalized Petri nets. IEEE T Syst Man Cy A 2008; 38: 369–384.

35.

Chao

. Max′-controlled siphon for liveness of S³ PGR². IET Contr Theory Appl 2007; 1: 933–936.

36.

Liu

Zhou

. Liveness of an extended SPR. Automatica 2010; 46: 1008–1018.

37.

Chu

Xie

. Deadlock analysis of Petri nets using siphons and mathematical programming. IEEE T Robotic Autom 1997; 13: 793–804.

38.

Huang

Jeng

Xie

et al . Deadlock prevention policy based on Petri nets and siphons. Int J Prod Res 2001; 39: 283–305.

39.

Wang

Jia

et al . An effective algorithm to find elementary siphons in a class of Petri nets. IEEE T Syst Man Cy A 2009; 39: 912–923.

40.

Wang

Zhou

et al . A method to compute strict minimal siphons in a class of Petri nets based on loop resource subsets. IEEE T Syst Man Cy A 2012; 42: 226–237.

41.

Wang

You

Zhou

. A necessary and sufficient condition for a resource subset to generate a strict minimal siphon in SPR. IEEE T Automat Contr 2017; 62: 4173–4179.

42.

Liu

Zhou

. A parameterized liveness and ratio-enforcing supervisor for a class of generalized Petri nets. Automatica 2013; 49: 3167–3179.

43.

Murata

. Petri nets: properties, analysis and applications. Proc IEEE 1989; 77: 541–580.

44.

Liu

Wang

. Sufficient conditions for loop resource subsets to derive strict minimal siphons in class of Petri nets. Electron Lett 2014; 50: 25–27.

45.

Tarjan

. Depth first search and linear graph algorithms. SIAM J Comput 1972; 1: 146–160.

46.

Starke

. INA: integrated net analyzer, https://www2.informatik.hu-berlin.de/~starke/ina.html

Liveness characteristic analysis of a class of Petri nets

Abstract

Keywords

Introduction

Preliminary

Basics of PNs

FC-S3 PR

Definition 1

Definition 2

Definition 3

Definition 4

Definition 5

Theorem 1

Liveness characteristic analysis

Liveness deciding condition

Property 1

Theorem 2

Proof

Theorem 3

Proof

Remark 1

Theorem 4

Proof

Illustrative examples

Example 1

Example 2

Configure initial marking for an FC-S3 PR

Remark 2

Theorem 5

Proof

Example 3

Computational complexity analysis

Discussion and comparison

Conclusion

Footnotes

Declaration of conflicting interests

Funding

ORCID iD

References

FC-S³ PR

Configure initial marking for an FC-S³ PR