Modules of Petri nets and new Petri net structure: Arcs with a weighted function set

Abstract

This article addresses expressiveness problems for Petri nets and their useful extension for modeling and control of a system that can be modeled with Petri nets. We construct some Petri net modules, namely, an enabling module, an inhibitor module and a Modulo-N counter, which are useful for system operations. We also present the simplifications for the enabling and inhibitor modules. Then, we propose two new types of arcs, namely, enabling and inhibitor arcs, with a weighted function set. The arcs with the weighted function set from places to transitions are the marked arcs. A function set is employed to denote the weight of an arc according to the system requirements. They are very useful to solve the resource reallocation problem in a resource allocation system, where resource sharing contributes to the occurrences of deadlocks. Finally, two examples are used to show the advantages of the presented new types of arcs.

Introduction

Petri nets ¹ can be served as a graphical and mathematical modeling tool for many contemporary technological systems such as flexible manufacturing systems, urban traffic systems, and concurrent programming systems. They have found extensive applications to the modeling, analysis, control,^2–10 scheduling,^11–13 performance evaluation, ¹⁴ fault identification and diagnosis,^15–17 and verification of various properties^7,18 of discrete event systems.^9,19 Since they were proposed by CA Petri in 1962, many researchers and engineers from different fields have been working on Petri nets and their applications to real-world systems. ²⁰ According to the properties of a graphical tool, we can use Petri nets to make flowcharts, networks, and block diagrams. Furthermore, the token variation of a net can be used to simulate the dynamic behavior of a system. We also use Petri nets to govern the behavior of systems by setting up state equations, algebraic equations, and other mathematical approaches due to its properties of a mathematic tool. A mathematical approach is applicable to almost every system, no matter it is complicated or simple. Due to the inherent properties, more and more researchers from academic and industry communities are beginning to pay attention to Petri nets with their variations.

For discrete event systems, deadlocks^21–28 have been an important problem to solve, especially in the resource sharing systems which have the shared resources.^29–33 They also include computer systems, flexible manufacturing systems, communication systems, and so on, showing the importance of Petri nets in the problem of deadlocks. Petri nets have been extensively used to solve the problem of deadlocks and forbidden state problem of discrete event systems^34–38 due to their powerful ability in modeling and controlling systems. The reachability graph of a Petri net model has an important effect on analyzing a Petri net model.^39,40 It is used directly to represent the behavior and the evolution of a system.

Although Petri nets have been used to describe a large number of systems since 1962, they still have limitations in the simplicity compared with the classical models ⁴¹ when they are used to describe complex systems. Some extensions to the basic Petri net structure is developed to overcome this problem by introducing extended concepts, such as enabling arcs and inhibitor arcs to control a transition enabling.

In this article, in order to solve the resource reallocation problem, we first propose two novel Petri net structures, called an enabling arc with a weighted function set and an inhibitor arc with a weighted function set, respectively. In particular, an enabling arc with a weighted function set is an enabling arc from a place $p$ to a transition $t$ with a weighted function set labeled on the arc. Transition $t$ is enabled by $p$ at a marking $M$ if $M(p)$ is equal to any value of the weighted function in the function set. If $t$ is enabled and fires, it cannot change the number of tokens in $p$ . Moreover, an inhibitor arc with a weighted function set is an inhibitor arc from a place $p$ to a transition $t$ with a weighted function set labeled on the arc. Transition $t$ is enabled by $p$ at a marking $M$ if $M(p)$ is not equal to any value of the weighted function in the function set. Based on these two novel arcs, we present some examples to show their applications and advantages.

Other parts of this article are organized as follows. In section “Literature review,” we provide an overview of the related literature on several Petri net structures and compare the main features of the two proposed new net structures with them. In section “Preliminaries,” we summarize the basic definitions of Petri nets and the extended Petri nets. Section “Enabling and inhibitor modules” constructs the enabling module, inhibitor module, and a Modulo-N counter. Section “The weighted function of arcs” introduces an enabling arc with a weighted function set and an inhibitor arc with a weighted function set, and proves some important results about the relations among the two new types of arcs and several kinds of arcs in the literature. Section “Example” gives two examples and uses the new types of arcs proposed in this article to solve the problem of conflict. Finally, we conclude this article in section “Conclusion.”

Literature review

An inhibitor arc^42,43 from a place to a transition is a special arc. If there are tokens in a place, the special arc is to block the firing of the transition.^44–47 We can use it to test the presence of tokens in a place, and it is widely used in supervisory control problem. In Gelen and Uzam, ⁴⁸ weighted inhibitor arcs are considered in addition to inhibitor arcs. The former can be used for testing whether the number of tokens in a place is less than a certain threshold number. ⁴⁹

In the case that the legal state space is non-convex, in order to deal with the problem of deadlock control, Chen and Li ⁵⁰ propose a net structure called interval inhibitor arcs. In that work, an interval inhibitor arc is an arc from a place $p$ to a transition $t$ labeled by an integer interval $[a,b]$ . Transition $t$ is disabled by the interval inhibitor arc at a marking $M$ if $a\le M(p)\le b$ . Based on such kind of arcs, they propose two techniques to obtain optimal supervisors by solving integer linear programming problems. However, by only using interval inhibitor arcs, we cannot guarantee that an optimal supervisor always exists for any bounded Petri net. Thus, a more general net structure called data inhibitor arcs is proposed in Chen et al. ⁵¹ to design an optimal supervisor for any bounded Petri net. In particular, a data inhibitor arc is an arc from a place $p$ to a transition $t$ , on which a set of non-negative integers $\{a_1,a_2,\dots ,a_k\}$ is labeled. If $M(p)\notin \{a_1,a_2,\dots ,a_k\}$ , then $t$ is enabled by $p$ at a marking $M$ . If $t$ is enabled and fires, it does not change the number of tokens in $p$ .

An enabling arc ⁵² from a place to a transition is also a special arc. If there are tokens in a place, the special arc is to enable and fire the transition. ⁴⁴ Also, we can use it to test the presence of tokens in a place. In Gelen and Uzam, ⁴⁸ weighted enabling arcs are considered in addition to enabling arcs. The former can be used for testing whether the number of tokens in a place is larger than or equal to a certain threshold number. ⁴⁹ Moreover, the enabling arcs and/or the weighted enabling arcs are widely used in the fields of forbidden state problem^42,53 and deadlock control. ⁴⁸

In this article, we first propose some sub-nets of Petri nets using weighted enabling arcs or weighted inhibitor arcs. In particular, when the sub-net contains the net structure such that there are both weighted enabling arc and weighted inhibitor arc from a place to a transition, we show that this net structure has the same enabling condition as the enabling arcs labeled by an integer interval or an integer set. That is to say, the net structure with weighted enabling arc and weighted inhibitor arc can be simplified. Based on this result, we propose an enabling module and an inhibitor module, and provide their related simplifications accordingly. Then, in order to solve the resource reallocation problem, two new types of arcs are proposed, called an enabling arc with a weighted function set and an inhibitor arc with a weighted function set. To the best of our knowledge, it is the first time to add the weighted function set to an enabling arc and an inhibitor arc. The two new types of arcs are the extension of the enabling and the inhibitor arcs. Compared with the weighted inhibitor arcs and interval inhibitor arcs, an inhibitor arc with a weighted function set is a more general structure, and it has a more powerful modeling and control ability. Compared with data inhibitor arcs, an inhibitor arc with a weighted function set has an equivalent disabling condition with a simpler and compact representation. Analogically, an enabling arc with a weighted function set also has the advantages compared with the enabling arcs and weighted enabling arcs. However, both of the two types of arcs proposed in this article are not in the sense of the Petri nets, that is, the resulting combined net is not a Petri net anymore and the traditional net analysis cannot be done on it. Moreover, given an arbitrary control requirement, it may be not easy to find a suitable weighted function set labeled on the enabling and/or inhibitor arcs to meet this requirement. From the illustrated examples, we can see that they are very useful to solve the resource reallocation problem. In summary, this article makes the following contributions:

1. Enabling module and inhibitor module with some input places are proposed. Their graphical representations are provided. Moreover, we provide the simplifications of these two kinds of modules.

2. We construct a Modulo-N counter which has an important effect on real-time control system.

3. The arcs with the weighted function set based on the proposed modules are proposed. Their definitions and graphical representations are provided. We propose the enabling and firing rules of the transitions in a net with them. Two examples are used to demonstrate the effect of the two new types of arcs for solving the resource reallocation problem.

Preliminaries

Petri nets

In general, a Petri net ¹ is a 4-tuple $\mathrm{PN}=(P,T,F,W)$ . Among them, $P$ denotes all the places, and $T$ denotes all the transitions, and they are disjoint but not empty. $F\subseteq (P\times T)\cup (T\times P)$ is called a flow relation of the net, represented by arcs with arrows from places to transitions or from transitions to places. $W:(P\times T)\cup (T\times P)\to \mathbb{N}$ is a mapping that assigns a weight to an arc: $W(x,y)>0$ if $(x,y)\in F$ , and $W(x,y)=0$ otherwise, where $x,y\in P\cup T$ and $\mathbb{N}$ denote the set of non-negative integers. ${}^{•}x=\{y\in P\cup T|(y,x)\in F\}$ is called the preset of $x$ and $x^{•}=\{y\in P\cup T|(x,y)\in F\}$ is called the post-set of $x$ . A marking is denoted by $M$ . In a Petri net, a marking is equivalent to a mapping $M:P\to \mathbb{N}$ . The pair $(\mathrm{PN},M_0)$ is called a net system with the initial marking $M_0$ . A net is pure (self-loop free) if $\nexists x,y\in P\cup T$ , $(x,y)\in F\wedge (y,x)\in F$ . Its incidence matrix $[C]$ is a $|P|\times |T|$ integer matrix with $[C](p,t)=W(t,p)-W(p,t)$ . In a Petri net, if the weight of any arc is not greater than one, it is said to be ordinary. In all states, if the tokens are always no greater than a certain number $k$ in a place $p$ , we call the place $p$ k-bounded. Thus, we can say that a net is k-bounded if all the places are k-bounded.

A transition $t$ is enabled at $M$ if $\forall p{\in }^{•}t$ , $M\ge W(p,t)$ , which is denoted as $M[t〉$ . When $t$ fires, it produces a new marking $M\prime$ , which is denoted as $M[t〉M\prime$ . We write $M[\sigma 〉$ to denote that the sequence of transitions $\sigma =t_1{t}_2\dots t_n$ is enabled at $M$ , and $M[\sigma 〉M\prime$ represents that the enabled sequence $\sigma$ may fire at $M$ yielding $M\prime$ . Moreover, we also denote $\overrightarrow{\sigma }:T\to {\mathbb{N}}^n$ the firing vector associated with a sequence $\sigma$ . Specifically, $y(t)=k$ if the transition $t$ is contained $k$ times in $\sigma$ . A marking $M$ is said to be reachable from $(\mathrm{PN},M_0)$ if there exists a firing vector $\sigma$ such that $M_0[\sigma 〉M$ that is computed by the state equation of the net as follows

$$M=M_0+[C]·\overrightarrow{\sigma }$$

(1)

Extended Petri nets

An extended Petri net $\mathrm{EPN}=(P,T,F,W,\mathrm{Ena},\mathrm{Inh})$ is a Petri net with weighted enabling arcs ⁴⁸ and weighted inhibitor arcs, ⁴⁸ where $\mathrm{Ena}:(P\times T)\to \mathbb{N}$ defines weighted enabling arcs from places to transitions and $\mathrm{Inh}:(P\times T)\to \mathbb{N}$ defines weighted inhibitor arcs from places to transitions. Normal (regular) arcs can connect places to transitions and vice visa, while the weighted enabling arcs and the weighted inhibitor arcs can connect only places to transitions. The enabling and firing rules of weighted enabling arcs and weighted inhibitor arcs are shown as follows.

Definition 1

Let $p$ be a place and $t$ be a transition with $\mathrm{Ena}(p,t)=a$ . Transition $t$ is enabled by $\mathrm{Ena}(p,t)$ at a marking $M$ if $M(p)\ge a$ ; otherwise, it is disabled. Once $t$ is enabled, the tokens in $p$ cannot be changed by its firing.

In Figure 1(a), for a transition $t$ , if there exist both a normal (regular) arc $W(p,t)=w$ and a weighted enabling arc $\mathrm{Ena}(p,t)=a$ , then $t$ is enabled when $M(p)\ge w$ and $M(p)\ge a$ . Once $t$ fires, it produces a new marking $M\prime$ with $M\prime (p)=M(p)-w$ . It is important to note that a weighted enabling arc is a generalization of an enabling arc. In particular, an enabling arc starting from a place $p$ to a transition $t$ can be regarded as a specific case of a weighted enabling arc with $\mathrm{Ena}(p,t)=1$ . Thus, the enabling and firing rules for the enabling arc are the same as a weighted enabling arc by only considering the weight as one.

Figure 1.

An extended Petri net model.

Definition 2

Let $p$ be a place and $t$ be a transition with $\mathrm{Inh}(p,t)=b$ . Transition $t$ is enabled by $\mathrm{Inh}(p,t)$ at a marking $M$ if $M(p)<b$ ; otherwise, it is disabled. Once $t$ is enabled, the tokens in $p$ cannot be changed by its firing.

In Figure 1(b), for a transition $t$ , if there exist both a normal (regular) arc $W(p,t)=w$ and a weighted inhibitor arc $\mathrm{Inh}(p,t)=b$ , then $t$ is enabled when $M(p)\ge w$ and $M(p)<b$ . Once $t$ fires, it produces a new marking $M\prime$ with $M\prime (p)=M(p)-w$ . It is important to note that a weighted inhibitor arc is a generalization of an inhibitor arc. In particular, an inhibitor arc starting from a place $p$ to a transition $t$ can be regarded as a specific case of a weighted inhibitor arc with $\mathrm{Inh}(p,t)=1$ . Thus, the enabling and firing rules for the inhibitor arc are the same as a weighted inhibitor arc by only considering the weight as one.

In Figure 1(c), for a transition $t$ , if there exist a normal (regular) arc $W(p,t)=w$ , a weighted enabling arc $\mathrm{Ena}(p,t)=a$ , and a weighted inhibitor arc $\mathrm{Inh}(p,t)=b$ , then $t$ is enabled when $M(p)\ge w$ , $M(p)\ge a$ , and $M(p)<b$ . Once $t$ fires, it produces a new marking $M\prime$ with $M\prime (p)=M(p)-w$ .

Enabling and inhibitor modules

In order to design and analyze the dynamic behavior of a system, we can apply the method of segment description. In a Petri net, we can make a segment for the collection of places and transitions, which is defined as a part of a sub-net called a module. Then, we can carry out this sub-net separately. ⁵⁴ These modules are useful for constructing Petri net models in system operations.

In this article, a module is a Petri net starting from some input places and ending at a transition connected with the inhibitor or enabling arc. The tokens of the input places can only be modified by external agents.

First, let us consider a net structure as shown in Figure 2(a) that consists of a weighted enabling arc and a weighted inhibitor arc. Suppose that $a$ and $b$ are non-negative integers. From Figure 2(a), the following fact is verified: if $a\le M(p)\le b$ holds, transition $t$ is enabled. In Figure 2(b), if $a\le M(p)\le b$ holds, transition $t$ is also enabled. Therefore, they are equivalent in the enabling condition of transition $t$ , which means that the net in Figure 2(b) is the simplified representation of that in Figure 2(a).

Figure 2.

Three equivalent net structures.

If $a=b$ at all markings, the net structure in Figure 2(a) can be further simplified, as shown in Figure 2(c), where transition $t$ is enabled if $M(p)\in \{a\}$ . That is to say, the net structure in Figure 2(a) can be represented by various enabling arcs including enabling arcs labeled by an integer interval or an integer set.

Modules with more than one input places

Based on the aforementioned results in this section, we can construct the enabling module and inhibitor module with more than one input places, without loss of generality, with two places as an example. Let us construct an enabling module with two input places $p_1$ and $p_2$ , and an output transition $t$ , as shown in Figure 3(a), where $a_1$ , $b_1$ , $a_2$ , and $b_2$ are non-negative integers, and $a_1\le b_1$ and $a_2\le b_2$ hold at all markings. We can change the tokens in $p_1$ and $p_2$ by an external agent.

Figure 3.

Enabling module with two input places.

Graphically simplified representation of Figure 3(a) is shown in Figure 3(b). We have:

1. t ₁ is enabled if a₁ ≤ M(p₁) ≤ b₁, and t₂ is enabled if a₂ ≤ M(p₂) ≤ b₂.

2. By firing t₁ (t₂), M(p₀) is equal to one.

3. t is enabled if the place p₀ is marked.

That is, if transition $t$ is enabled, then $a_1\le M(p_1)\le b_1$ or $a_2\le M(p_2)\le b_2$ holds. Furthermore, let $a_1=b_1$ and $a_2=b_2$ . If transition $t$ is enabled, then $M(p_1)=a_1$ or $M(p_2)=a_2$ . In this case, the enabling module can be simplified to the net structure as shown in Figure 3(c). Similarly, we can construct an inhibitor module, as shown in Figure 4(a).

Figure 4.

Inhibitor module with two input places.

Graphically simplified representation of Figure 4(a) is shown in Figure 4(b). We have:

1. t ₁ is enabled if a₁ ≤ M(p₁) ≤ b₁, and t₂ is enabled if a₂ ≤ M(p₂) ≤ b₂.

2. By firing t₁ (t₂), M(p₀) is equal to one.

3. t is disabled if M(p₀) is marked.

That is, if transition $t$ is disabled, then the tokens in the places $p_1$ and $p_2$ meet the condition $a_1\le M(p_1)\le b_1$ or $a_2\le M(p_2)\le b_2$ .

Furthermore, let $a_1=b_1$ and $a_2=b_2$ , if transition $t$ is disabled, then $M(p_1)=a_1$ or $M(p_2)=a_2$ . In this case, the inhibitor module can be simplified to the net structure as shown in Figure 4(c).

Modulo-N counter

Let us consider a Modulo-N counter as shown in Figure 5. The number of tokens in place $p$ is in the cycle from 0 to $N-1$ and it is called a Modulo-N counter.

Figure 5.

Modulo-N counter.

Modulo-N counter is an important part of a controller in real-time control systems. It is also similar to the “switch… case…” statement in C programming language.

In Figure 5, $N$ can be any integer greater than one according to the requirement of a system. At the initial marking, transition $t$ is enabled. After firing $t$ , place $p$ increases one token and the number of tokens in place $p_0$ remains unchanged. Furthermore, only if the number of tokens in place $p$ is less than the number $N-1$ , transition $t$ is always enabled. Once the number of tokens in place $p$ is equal to $N-1$ , $t$ is disabled by a weighted inhibitor arc between place $p$ and transition $t$ , and transition $t_0$ is enabled. By firing $t_0$ , place $p$ is emptied. In this case, the system returns to the initial state. That is to say, the number of tokens in place $p$ is in a cycle from 0 to $N-1$ .

The weighted function of arcs

Based on the above analysis of enabling and inhibitor modules, we have a deeper understanding of the weighted enabling and the weighted inhibitor arcs. Then, we propose two new types of arcs, namely, the enabling arcs with the set of weighted functions and the inhibitor arcs with the set of weighted functions. Now some definitions about these two kinds of arcs are given as follows.

Definition 3

An enabling arc with a set of weighted functions is an enabling arc from a place $p$ to a transition $t$ labeled by a function set $\{f_1(x),\dots ,f_k(x)\}$ , denoted as $\mathrm{Enaf}(p,t)=\{f_1(x),\dots ,f_k(x)\}$ , where $x$ can be any non-negative integer and, for each $x\in \mathbb{N}$ , $f_j(x)$ (for $j=1,2,\dots ,k$ ) is also a non-negative integer.

Figure 6 shows the graphic representation of an enabling arc with a weighted function set. Then, the enabling and firing rules of the enabling arc with the weighted function set shown in Figure 6 are defined as follows.

Figure 6.

An enabling arc with a weighted function set.

Definition 4

Let $p$ be a place and $t$ a transition with $\mathrm{Enaf}(p,t)=\{f_1(x),\dots ,f_k(x)\}$ . Transition $t$ is enabled if $M(p)\in \{f_1(x),\dots ,f_k(x)\}$ (for $x\in \mathbb{N}$ ); otherwise, it is disabled. Once $t$ is enabled and fires, its firing does not change the token count in $p$ .

In Figure 7, for a transition $t$ , if there exist both a normal (regular) arc $W(p,t)=w$ and an enabling arc with a weighted function set $\mathrm{Enaf}(p,t)=\{f_1(x),\dots ,f_k(x)\}(x\in \mathbb{N})$ , then $t$ is enabled when $M(p)\ge w$ and $M(p)\in \{f_1(x),\dots ,f_k(x)\}$ . Once $t$ fires, it produces a new marking $M\prime$ with $M\prime (p)=M(p)-w$ .

Figure 7.

$W(p,t)=w$ and $\mathrm{Enaf}(p,t)=\{f_1(x),\dots ,f_k(x)\}$ .

In general, there can be multiple elements in $\mathrm{Enaf}(p,t)$ . However, in some special case, some of the elements in $\mathrm{Enaf}(p,t)$ are redundant. And, we show it in the following remark.

Remark 1

Suppose that there is an enabling arc with a weighted function set $\mathrm{Enaf}(p,t)=\{f_1(x),\dots ,f_k(x)\}$ and a normal arc from a place $p$ to a transition $t$ with $W(p,t)=w$ . If $w=f_1(x)$ for a variable $x$ and $f_1(x)<f_2(x)\cdots <f_k(x)$ for any $x\in \mathbb{N}$ hold, then $f_2(x),\dots ,f_k(x)$ are redundant.

Proposition 1

An enabling arc with a weighted function set is more general such that it is a generalization of a weighted enabling arc.

Proof

Without loss of generality, let us consider a weighted enabling arc from a place $p$ to a transition $t$ labeled by a non-negative integer $a$ , which can enable transition $t$ at marking $M$ if $M(p)\ge a$ . There exists an enabling arc with a weighted function set $\mathrm{Enaf}(p,t)=\{x\}$ $(x\ge a)$ , which has the same enabling condition. However, let us consider an enabling arc with a weighted function set $\mathrm{Enaf}(p,t)=\{2x\}$ $(x\in \mathbb{N})$ , which can enable transition $t$ at marking $M$ if $M(p)\in \{2x\}$ . Based on the definition of the weighted enabling arcs, there exists no such arc that can have the same enabling condition. Thus, the conclusion holds.

Proposition 1 shows the relation between an enabling arc with a weighted function set and a weighted enabling arc. From Proposition 1, we can conclude that an enabling arc with a weighted function set has a more powerful modeling and control ability compared with a weighted enabling arc. The following example shows the advantage of the enabling arc with a weighted function set in a control problem.

Example 1

Let us consider an unbounded place $p$ and a transition $t$ , and the control requirement is that $M(p)$ should not disable transition $t$ for any marking $M(p)\in \{2,3,4,6,\dots ,2x,3x\}$ $(x\in {\mathbb{N}}^{+})$ . It is obvious that the weighted inhibitor arc cannot satisfy this control requirement. However, it is easy to be implemented by an enabling arc with a weighted function set $\mathrm{Enaf}(p,t)=\{2x,3x\}$ $(x\in {\mathbb{N}}^{+})$ .

Definition 5

An inhibitor arc with a set of weighted functions is an inhibitor arc from a place $p$ to a transition $t$ labeled by a function set $\{f_1(x),\dots ,f_k(x)\}$ , denoted as $\mathrm{Inhf}(p,t)=\{f_1(x),\dots ,f_k(x)\}$ , where $x$ can be any non-negative integer and for each $x\in \mathbb{N}$ , $f_j(x)$ (for $j=1,2,\dots ,k$ ) is also a non-negative integer.

Figure 8 shows the graphic representation of an inhibitor arc with a weighted function set. Then, the enabling and firing rules of the inhibitor arc with the weighted function set shown in Figure 8 are defined as follows.

Figure 8.

An inhibitor arc with a weighted function set.

Definition 6

Let $p$ be a place and $t$ a transition with $\mathrm{Inhf}(p,t)=\{f_1(x),\dots ,f_k(x)\}$ . Transition $t$ is disabled if $M(p)\in \{f_1(x),\dots ,f_k(x)\}$ (for $x\in \mathbb{N}$ ); otherwise, it is enabled. Once $t$ is enabled and fires, its firing does not change the token count in $p$ .

In Figure 9, for a transition $t$ , if there exist both a normal (regular) arc $W(p,t)=w$ and an inhibitor arc with a weighted function $\mathrm{Inhf}(p,t)=\{f_1(x),\dots ,f_k(x)\}(x\in \mathbb{N})$ , then $t$ is enabled when $M(p)\ge w$ and $M(p)\notin \{f_1(x),\dots ,f_k(x)\}$ . Once $t$ fires, it produces a new marking $M\prime$ with $M\prime (p)=M(p)-w$ .

Figure 9.

$W(p,t)=w$ and $\mathrm{Inhf}(p,t)=\{f_1(x),\dots ,f_k(x)\}$ .

Proposition 2

An inhibitor arc with a weighted function set is more general such that it is a generalization of a weighted inhibitor arc and an interval inhibitor arc.

Proof

We first prove that an inhibitor arc with a weighted function set is a generalization of a weighted inhibitor arc. Without loss of generality, let us consider a weighted inhibitor arc from a place $p$ to a transition $t$ labeled by a non-negative integer $b$ , which can disable transition $t$ at marking $M$ if $M(p)\ge b$ . There exists an inhibitor arc with a weighted function set $\mathrm{Inhf}(p,t)=\{x\}$ $(x\ge b)$ , which has the same disabling condition. However, let us consider an inhibitor arc with a weighted function set $\mathrm{Inhf}(p,t)=\{2x\}$ $(x\in \mathbb{N})$ , which can disable transition $t$ at marking $M$ if $M(p)\in \{2x\}$ . Based on the definition of the weighted inhibitor arcs, there exists no such arc that can have the same disabling condition.

Then, we prove that an inhibitor arc with a weighted function set is a generalization of an interval inhibitor arc. Without loss of generality, let us consider an interval inhibitor arc from a place $p$ to a transition $t$ labeled by an integer interval $[a,b]$ , which can disable transition $t$ at marking $M$ if $a\le M(p)\le b$ . There exists an inhibitor arc with a weighted function set $\mathrm{Inhf}(p,t)=\{x\}$ $(a\le x\le b)$ , which has the same disabling condition. However, let us consider an inhibitor arc with a weighted function set $\mathrm{Inhf}(p,t)=\{2x\}$ $(x\in \mathbb{N})$ , which can disable transition $t$ at marking $M$ if $M(p)\in \{2x\}$ . Based on the definition of the interval inhibitor arcs, there exists no such arc that can have the same disabling condition. Thus, the conclusion holds.

Proposition 3

An inhibitor arc with a weighted function set is equivalent to a data inhibitor arc.

Proof

Without loss of generality, let us consider a data inhibitor arc from a place $p$ to a transition $t$ labeled by a set of non-negative integers $\{a_1,a_2,\dots ,a_k\}$ , which can disable transition $t$ at marking $M$ if $M(p)\in \{a_1,a_2,\dots ,a_k\}$ . There exists an inhibitor arc with a weighted function set $\mathrm{Inhf}(p,t)=\{x\}$ $(x\in \{a_1,a_2,\dots ,a_k\})$ , which has the same disabling condition. However, let us consider an inhibitor arc with a weighted function set $\mathrm{Inhf}(p,t)=\{f_1(x),\dots ,f_k(x)\}$ $(x\in \mathbb{N})$ , which can disable transition $t$ at marking $M$ if $M(p)\in \{f_1(x),\dots ,f_k(x)\}$ . There exists a data inhibitor arc labeled by a set of non-negative integers $\{f_1(0),f_1(1),\dots ,f_1(x),\dots ,f_k(0),f_k(1),\dots ,f_k(x)\}$ , which has the same disabling condition. Thus, the conclusion holds.

Proposition 2 provides the relations among an inhibitor arc with a weighted function set, a weighted inhibitor arc, and an interval inhibitor arc. From Proposition 2, it is obvious that an inhibitor arc with a weighted function set has a more powerful modeling and control ability compared with a weighted inhibitor arc and an interval inhibitor arc. Proposition 3 indicates the relation between an inhibitor arc with a weighted function set and a data inhibitor arc. From Proposition 3 and its proof, an inhibitor arc with a weighted function set is equivalent to a data inhibitor arc, but it has a more simpler and compact representation compared with a data inhibitor arc in general.

Example 2

Let us consider an unbounded place $p$ and a transition $t$ , and the control requirement is that $M(p)$ should disable transition $t$ for any marking $M(p)\in \{2,3,4,6,\dots ,2x,3x\}$ $(x\in {\mathbb{N}}^{+})$ . It is obvious that a weighted inhibitor arc and an interval inhibitor arc cannot satisfy this control requirement. Moreover, we can use a data inhibitor arc $\mathbb{A}(p,t)=\{2,3,4,6,\dots ,2x,3x\}$ $(x\in {\mathbb{N}}^{+})$ to fulfill this control requirement. However, it is easy to be implemented by an inhibitor arc with a weighted function set $\mathrm{Inhf}(p,t)=\{2x,3x\}$ $(x\in {\mathbb{N}}^{+})$ , which has a more simpler and compact representation compared with the corresponding data inhibitor arc.

Now, a Petri net with the enabling and/or inhibitor arcs labeled by the sets of weighted functions is called an extended function Petri net, which is denoted as $\mathrm{EFPN}=(P,T,F,W,\mathrm{Enaf},\mathrm{Inhf})$ . As known, deadlocks have been an important problem to solve in discrete event systems that include computer-integrated systems, flexible manufacturing systems, communication systems, and so on. Petri nets are very useful to solve the deadlock problems due to their powerful ability in modeling and controlling systems. ⁵⁵ Many novel arcs such as interval inhibitor arcs and data inhibitor arcs have been proposed to strengthen the ability of Petri nets. What is more, they are very useful for us to solve the deadlock problems in discrete event systems. However, it is difficult to use the novel arcs to solve the deadlock problems directly. They need to add the control places. ⁵⁶ Based on these considerations, we propose the arcs with the set of weighted functions, which can be used to redistribution of resources to solve the problem of conflict in Petri nets. Two examples are used to demonstrate this idea in the next section.

Example

As known, deadlocks often occur in a resource allocation system owing to the existence of shared resources. It can make an impact on the running of a system. Petri nets have an important effect on modeling and controlling these computer-integrated systems.^4,57–60

Now, we take a system consisting of a producer, two consumers, and a buffer as an example, as shown in Figure 10. In this Petri net, the enabling arcs and the inhibitor arcs with the weighted function sets are used to solve the problem of conflict such that Consumers 1 and 2 have different choices under some conditions. In particular, Consumer 1 needs to hold the system when the number of tokens in the buffer (place $p_7$ ) is odd, while Consumer 2 needs to hold the system when the number of tokens in the buffer is even. In order to achieve the resource reallocation requirement of the system, an ordinary arc from place $p_7$ to transition $t_3$ is substituted by an inhibitor arc with a weighted function set $\{2x\}$ from $p_7$ to $t_3$ , where $x$ is a non-negative integer variable. Moreover, another ordinary arc from place $p_7$ to transition $t_5$ is also substituted by an enabling arc with a weighted function set $\{2x+2\}$ from $p_7$ to $t_5$ , where $x$ is a non-negative integer variable. It means that Consumers 1 and 2 can hold the system, respectively, with different number of tokens in $p_7$ using such kinds of inhibitor and enabling arcs proposed in this article, which effectively avoids the conflict between Consumers 1 and 2.

Figure 10.

An extended function Petri net model (two consumers).

Then, we make a concrete analysis. From the extended function Petri net model, we can see that transition $t_3$ is enabled if the number of tokens in $p_7$ is odd. Transition $t_5$ is enabled if the number of tokens in $p_7$ is even. From Figure 10, we can find that the sub-net consisting of $p_1$ , $p_2$ , $t_1$ , and $t_2$ is live, that is, there is no deadlock in the sub-net. Every time transition $t_2$ fires, the number of tokens in $p_7$ is increased by one.

When there is one token in place $p_7$ , we remark the present marking as $M_0$ , where $M_0=[\begin{array}{c}1010101\hfill \end{array}{]}^T$ . We can see that transitions $t_1$ and $t_3$ are enabled at $M_0$ . Then, if the transition sequence $t_1{t}_3$ fires, we can compute the destination marking $M_1$ using equation (1) as follows

$$\begin{array}{cc}\multicolumn{1}{c}{\overrightarrow{\sigma }}& ={\left[\begin{array}{cccccc}1\hfill & 0\hfill & 1\hfill & 0\hfill & 0\hfill & 0\hfill \end{array}\right]}^T\hfill \\ \multicolumn{1}{c}{\left[C\right]}& =\left[\begin{array}{cccccc}-1\hfill & 1\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill \\ \multicolumn{1}{c}{1}& -1\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill \\ \multicolumn{1}{c}{0}& 0\hfill & -1\hfill & 1\hfill & 0\hfill & 0\hfill \\ \multicolumn{1}{c}{0}& 0\hfill & 1\hfill & -1\hfill & 0\hfill & 0\hfill \\ \multicolumn{1}{c}{0}& 0\hfill & 0\hfill & 0\hfill & -1\hfill & 1\hfill \\ \multicolumn{1}{c}{0}& 0\hfill & 0\hfill & 0\hfill & 1\hfill & -1\hfill \\ \multicolumn{1}{c}{0}& 1\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill \end{array}\right]\hfill \\ \multicolumn{1}{c}{M_1}& =M_0+[C]·\overrightarrow{\sigma }={\left[0101101\right]}^T\hfill \end{array}$$

(1)

When there are two tokens in place $p_7$ , we remark the current marking as $M_2$ , where $M_2=[\begin{array}{c}1010102\hfill \end{array}{]}^T$ . Then, we can see that transitions $t_1$ and $t_5$ are enabled. Then, if the transition sequence $t_1{t}_5$ fires, we can compute the destination marking $M_3$ using equation (1) as follows

$$\begin{array}{c}\overrightarrow{\sigma }={\left[\begin{array}{cccccc}1\hfill & 0\hfill & 0\hfill & 0\hfill & 1\hfill & 0\hfill \end{array}\right]}^T\hfill \\ M_3=M_2+C·\overrightarrow{\sigma }={\left[\begin{array}{ccccccc}0\hfill & 1\hfill & 1\hfill & 0\hfill & 0\hfill & 1\hfill & 2\hfill \end{array}\right]}^T\hfill \end{array}$$

(1)

The above analysis fully shows that the weighted function of arcs can be used to solve the problem of resource reallocation. In Figure 10, we can see that the system has no conflict problem. In this net system, we use the arcs with weighted functions to solve the problem of conflict. The result shows that these two new types of arcs are very useful to analyze and solve the problem of conflict in the net system.

By this example, compared with the proposed new types of arcs, we now show that the weighted enabling arcs cannot achieve the control requirements of Consumers 1 and 2. Take Consumer 1 as an example. Since Consumer 1 needs to hold the system when the number of tokens in the buffer (place $p_7$ ) is odd, transition $t_3$ needs to be enabled when the number of tokens in $p_7$ is odd. According to Definition 1, a weighted enabling arc from place $p_7$ to transition $t_3$ can enable transition $t_3$ if the number of the tokens in $p_3$ is no less than the weight of the weighted enabling arc. However, it is obvious that the odd numbers are not consecutive. Thus, no weighted enabling arcs can guarantee to enable transition $t_3$ when the number of tokens in $p_7$ is odd. Similarly, the weighted inhibitor arcs neither achieve the control requirements of Consumers 1 and 2.

Moreover, we show that we cannot use interval inhibitor arcs ⁵⁰ to solve the resource reallocation problem for this example. In fact, according to the requirement of Consumer 1, it needs to hold the system when the number of tokens in the buffer is odd. Since the odd numbers are not consecutive, they cannot be represented by any integer interval. Based on the definition of the interval inhibitor arcs, it is obvious that we cannot use the finite number of interval inhibitor arcs to achieve the requirement of Consumer 1. Similarly, we can neither use any interval inhibitor arc to satisfy the requirement of Consumer 2.

Finally, we use data inhibitor arcs proposed in Chen et al. ⁵¹ to solve this resource reallocation problem. Based on the definition of data inhibitor arcs, if we want to use data inhibitor arcs to meet the requirement of Consumer 1 (disable $t_3$ when the number of tokens in $p_7$ is even), we need to use the set of all even numbers labeled on the inhibitor arc from $p_7$ to $t_3$ . According to the control requirement of Consumer 2 (disable $t_5$ when the number of tokens in $p_7$ is odd), we need to use the set of all odd numbers labeled on the inhibitor arc from $p_7$ to $t_5$ . Table 1 shows the performance comparison of different types of arcs for the net model in Figure 10. From Table 1, we can see that only data inhibitor arcs can satisfy the control requirements of the two consumers among several different types of arcs in the literature. However, since the form of the weight labeled on the inhibitor arcs is more complex and the data set contains too many variables, its representation is not compact compared with the enabling or inhibitor arcs with the weighted function set in general. Moreover, from the practical point of view, since the data set labeled on the inhibitor arcs is infinite for this example, it may cost more memory to store this information for the system. Thus, we can conclude that the data inhibitor arcs are not efficient to solve this resource reallocation problem compared with the proposed new types of arcs in this article.

Table 1.

Performance comparison of different types of arcs for the net model in Figure 10.

Type of arcs	Meet the control requirements?	Weight of arcs
Weighted enabling arcs 48	No	–
Weighted inhibitor arcs 48	No	–
Interval inhibitor arcs 50	No	–
Data inhibitor arcs 51	Yes	$\{0,2,4,\dots ,2x\}$ , $\{1,3,5,\dots ,2x+1\}$
Arcs with a weighted function set	Yes	$\{2x\}$ , $\{2x+2\}$

In order to further show the advantages of the proposed net structures, we present a Petri net model as shown in Figure 11 that represents a system consisting of a producer, $j$ consumers $(j>2)$ , and a buffer, which is a more general case of Figure 10. Due to the existence of shared resources among consumers, consumers can hold the system when there are tokens in $p_{2j+3}$ . In this case, conflict can occur in this system. When there are enough tokens in the buffer, they can be reasonably allocated to $j$ consumers by each enabling arc with a set of weighted functions. For this example, it is similar as the case we have discussed in Figure 10, the resource reallocation problem cannot be solved by weighted enabling arcs, weighted inhibitor arcs, and interval inhibitor arcs. Now, we use data inhibitor arcs to solve this resource reallocation problem. Without loss of generality, we consider Consumer $q(1\le q\le j)$ in the system. In order to meet the control requirement of this consumer, place $p_{2j+3}$ needs to enable transition $t_{2q+1}$ when the number of tokens in the place is equal to an element in the set $\{q,j+q,\dots ,\mathrm{jx}+q\}$ , where $x$ is an integer greater than one. Thus, the data set labeled on the inhibitor arc should be $\{1,\dots ,q-1,q+1,\dots ,j+q-1,\dots ,j\cdot (x-1)+q+1,\dots ,jx+q-1,jx+q+1,\dots \}$ , which is the complementary set of $\{q,j+q,\dots ,\mathrm{jx}+q\}$ . From this example, we can see that the proposed net structures in this article are more efficient and have more powerful control ability than the existing net structures in the related literature.

Figure 11.

An extended function Petri net model ( $j$ consumers).

However, we must point out that the set of functions labeled on the arcs is strongly related to the control requirements of the net system. Given an arbitrary control requirement, it is not obvious to find a suitable set of weighted functions and the corresponding domain of each function in the set to meet the control requirement. Moreover, in this article, we cannot guarantee that the number of arcs with a weighted function set has a polynomial bound with respect to the size of a net system for any control requirement.

Conclusion

To make Petri net with enabling and inhibitor arcs more powerful, the extended Petri net modules which include an enabling module, an inhibitor module, and a Modulo-N counter are constructed in this article. We propose three equivalent net structures, and simplify the enabling module and inhibitor module based on these net structures. The proposed modules can be used to design the forbidden state problem controller for discrete event systems.^53,61,62 Then, we introduce two new types of arcs, namely, enabling and inhibitor arcs with the set of weighted functions. Arcs with the set of weighted functions are special arcs since their weights are denoted by the set of functions. The new Petri net structures also make a Petri net more capable to model and control a system. They are very useful to solve the problem of resource reallocation in the systems. A future work is to extend the proposed net structures to deal with the resource reallocation problem when the control requirement is unknown by using the learing-based method. ⁶³