Optimal enforcement of liveness to flexible manufacturing systems modeled with Petri nets via transition-based controllers

Abstract

This article reports a transition-based control technique to prevent deadlocks for flexible manufacturing systems that can be modeled with a generalized class of Petri nets. The proposed method utilizes the structural properties of the Petri net model to avoid the computation of its reachability graph which in general leads to the state explosion problem. Three algorithms are developed. The first and second algorithms aim to compute first-met and n-met uncontrolled transitions, respectively, in an iterative manner until all the n-met uncontrolled transitions are found in the plant net model. The third algorithm is used to design n-transition controllers iteratively. The iteration terminates when all the transitions in the set of uncontrolled transitions are processed. The addition of the n-transition controllers to the plant net model is to make the n-met uncontrolled transitions controlled. The transition controllers are capable of enforcing liveness to the plant net model with all its reachable markings being retained in the controlled system, which ensures the full utilization of resources and provides the high productivity of a flexible manufacturing system.

Introduction

Economic diversification of a country usually depends on its emerging technological development and application. Manufacturing, as an essential source of society development and civilization, is a pillar industry in many developed and developing countries. A flexible manufacturing system (FMS) aims to provide a special consideration to diversify the products in a medium or small batch to increase the competition ability in the world market. An FMS usually consists of two main parts: a physical system that is composed of manufacturing resources (such as machine tools, robots, and transportation systems) shared by several jobs and a management system or decision-making system responsible for the control of the physical system to achieve the goal of productivity. ¹ Due to the request of high throughput of such a system, deadlocks can occur because of resource sharing, which may degrade the performance of an FMS. ² Deadlocks in some highly automated production processes such as semiconductor manufacturing or safety-critical systems may even lead to serious economic loss. ³

With the increasingly improved automation level in contemporary production processes, deadlocks are important issue to be considered in the design and control stage of an FMS, since their occurrences can halt the whole system from operation.^4–6 Coffman et al. ⁷ formulates four necessary conditions for the deadlock occurrence in a resource allocation system. They are popularly known as Coffman conditions,^5,8 that is, (1) mutual exclusion: a resource can only be used by one process at a time; (2) hold and wait: processes that use some resources may need another new resource; (3) non-preemption: it is infeasible to remove a resource that is held by a particular process, but a process can only release a resource by an explicit action of that process; and (4) circular wait: when two or more processes form a circular chain where each process waits for a resource that the next process in the chain holds. To prevent the occurrence of deadlocks, at least one of the four conditions should be broken. Several tools have been developed to deal with deadlocks in FMSs.^8,9

Petri nets, automata, and graph theory are the three main methodologies to deal with the modeling, scheduling,^10–12 and control problem^13,14 of discrete event systems. A supervisor is usually designed to prevent the occurrence of deadlocks in an FMS.^15,16 Recent decades have seen that Petri nets increasingly become essential to the study on deadlocks in an FMS as well as other supervisory control issues,^17–20 since they can appropriately describe both structural and behavioral properties of an FMS, such as conflicts, concurrency, casual dependency, liveness, and boundedness.^21,22 Generally there are four strategies to handle deadlocks in automated manufacturing systems:^23–26 (1) deadlock ignoring, (2) deadlock detection and recovery, (3) deadlock avoidance, and (4) deadlock prevention.

The performance of a deadlock prevention policy can be evaluated based on the following three criteria:^2,27–29 (1) behavioral permissiveness, (2) structural complexity, and (3) computational complexity. A maximally permissive supervisor usually leads to sufficient utilization of resources in a system.^8,27 A supervisor with the minimal number of control places can decrease both hardware and software costs in the stage of control verification, validation, and implementation.^27,30,31 A deadlock control policy with low computational complexity means that it can be applied to large-sized real-world systems.^8,32

There are mainly two Petri nets–based analysis techniques used to cope with deadlocks:^8,32,33 (1) structural analysis and (2) reachability graph (RG) analysis. In structural analysis, Petri net components, such as siphons, place and transition invariants, and resource transition circuits, are extensively used, as there are particular corresponding relationships between behavioral properties of a Petri net and its structural components. A deadlock prevention strategy derived from siphon control is usually suboptimal, since it is difficult to ensure every permissive state to be included in the controlled system.^34,35 To prevent a siphon from being insufficiently marked, a control place can be usually used to disable the related transitions in a plant at some particular markings.^5,36–40 In general, the number of siphons grows exponentially with the structural size of a net.

The RG analysis enables one to check certain properties of FMSs, such as liveness, boundedness, synchronization, concurrency, and safeness.^38,41–43 However, the RG analysis usually requires a complete or partial enumeration of reachable states. Therefore, it suffers from the state explosion problem. The theory of regions is developed in Ghaffari et al. ^41,44,45 and is thought of as one of the most powerful methods of deadlock prevention for deriving a maximally permissive supervisor for FMSs. However, it is computationally expensive since too many inequality constraints have to be considered in the linear programming problems, ⁴¹ in addition to the generation of a complete state space. The work by Uzam et al.^38,42 divides the RG of a Petri net model into two components: a live zone (LZ) and a deadlock zone (DZ). The former contains legal markings, and the latter contains illegal markings. The partition of the RG is used to find the first-met bad markings (FBMs) in the DZ such that once all FBMs are prohibited, all illegal markings in the DZ are not reachable. The deadlock prevention method by Uzam et al.^38,42 is an iterative procedure in which at each iteration step, an FBM is controlled by designing a control place. The iterations are repeated until all FBMs of a Petri net model are forbidden. However, this method does not guarantee maximally permissive behavior of the controlled system. It is then improved by the study in Chen et al. ⁴⁶

Within the context of a supervisory structure using Petri net paradigm, the structures of a supervisor are mostly designed via control places in the existing literature. Only a few works can be found for obtaining a supervisory structure via transition controller in the literature. The disadvantage of using control places in the design of a supervisory structure is that they cut off some of the reachable states of the plant model, leading to non-optimal utilization of shared resources. In contrast, the advantage of using transition controllers in the design of a supervisory structure is that it retains all the reachable states of the plant model while achieving liveness of the plant model. It results in the full utilization of the shared resources of the plant model.

The work of Huang et al. ⁴⁷ develops the first method to design a supervisory structure via transitions controller. In the developed method, they use the RG analysis to analyze the presence of deadlock states in plant net models. The method aims to manipulate all the deadlock markings to be included in a controlled system by adding control transitions to a plant net. It provides more permissive behaviors than the traditional methods of adding control places. However, its computation is expensive as it requires an iterative computation of the RG of the plant net.

The studies by Chao et al.^48,49 develop methods to construct supervisory structures using a mixed transition controller and control places of plant net models. In both the methods, Chao employs the use of structural analysis via siphon techniques. The first method can recover the system from a state at which there exist unmarked siphons. It adopts control places and control arcs similar to the traditional approaches for deadlock prevention. However, it preserves all the reachable markings of the original uncontrolled Petri net models. The second method deals with deadlocks by coloring some arcs and adding a control transition and control places to an uncontrolled Petri net model. It can recover all markings in the RG. However, in both the methods, the liveness of a plant net is in general not guaranteed in theory. Moreover, the methods do not embrace the transition controller only, since they are combined with the computation of the siphons which grows exponentially with the size of the Petri net model.

The study by Huang et al. ⁵⁰ focuses on the deadlock problem for FMSs modeled with a class of Petri nets, called systems of simple sequential processes with resources (S³PR), in a static deadlock recovery way. The developed policy first uses a RG-based technique to compute the deadlock markings that are classified group by group. For each group, a control transition is added to the plant net. The livelock markings are controlled by adding control transitions by iterative computation of RG of the plant net model. The method suffers from the computational complexity as it requires iterative computation of RGs and the supervisory structure that contains many control arcs connected from the plant to the transition controllers, which increases the costs of the implementation for the supervisory structure. Recently, Zhang and Uzam ⁵¹ develop a novel deadlock control policy to design control transitions based on the RG analysis and add the control transitions to the plant net which can recover all deadlock and livelock markings to legal ones. A set covering technique is developed to derive the minimal set of control transitions. However, the method uses a RG analysis which also suffers from the computational complexity.

To overcome the computational complexity of the existing methods in the literature, we propose a new approach to design an optimal enforcement of liveness to FMSs modeled with Petri nets via transition-based controllers. In this method, we employ the structural analysis via computing uncontrolled transitions of the plant net model to avoid the computations of RG which in general can lead to state space explosion. In this article, we enforce liveness for an M-net Petri net model (generalized class of Petri nets). It provides a novel, yet minimal supervisory structure of Petri nets. A transition controller is used to enforce liveness to a plant net with its all markings being reachable, precisely as in the original uncontrolled plant net. The main contributions of the proposed method are summarized as follows:

1. It uses structural analysis to derive all the n-met uncontrolled transitions from a plant net to avoid the computation of all reachable markings.

2. We proposed a new method of designing transition controllers.

3. For each uncontrolled transition, a transition controller is designed to enforce liveness of a plant net with its all markings being reachable, as in the uncontrolled plant net.

4. Case studies show that the proposed method can derive a structurally simple supervisor.

The proposed method is an iterative procedure. At each iteration step, a transition controller is added to a plant net till there is no n-met uncontrolled transition. The method can be applied to a large class of Petri nets modeling FMSs. Some typical examples from the literature are used to illustrate the significance of the proposed method.

The remainder of this article is organized as follows. Basics of Petri nets and their notations used in this article are presented in section “Preliminaries.” Section “Transition-based deadlock control” deals with transition controllers. In section “Deadlock prevention policy using transition controller and its correctness,” we report a deadlock prevention policy using transition controllers. Experimental examples are provided in section “Experimental Examples.” Finally, section “Discussion” provides a discussion of the proposed method, while section “Conclusion” concludes this article.

Preliminaries

A Petri net is a four-tuple $N=(P,T,F,W)$ where $P$ and $T$ are finite and non-empty sets. $P$ is a set of places and $T$ is a set of transitions with $P\cap T=\varnothing$ . $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. Places are graphically represented by circles, while transitions are graphically represented by bars or square boxes. $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\times T)\cup (T\times P)$ and $\mathbb{N}$ is the set of non-negative integers. $N=(P,T,F,W)$ is said to be an ordinary net, denoted as $N=(P,T,F)$ , if $\forall f\in F$ , $W(f)=1$ . Let $x\in P\cup T$ be a node in $N=(P,T,F,W)$ . The preset of $x$ , denoted by ${}^{•}x$ , is defined as ${}^{•}x=\{y\in P\cup T|(y,x)\in F\}$ , and $x^{•}=\{y\in P\cup T|(x,y)\in F\}$ is called the postset of $x$ . A marking $M$ of a Petri net $N=(P,T,F,W)$ is a mapping $M:P\to \mathbb{N}$ , where $M$ is an n-dimensional vector, and $n=|P|$ is the number of places in the net. Let $t\in T$ be a transition in $N=(P,T,F,W)$ at a marking $M$ . Transition $t$ is said to be enabled if $\forall p{\in }^{•}t$ , $M(p)\ge W(p,t)$ . An enabled transition $t$ can fire, leading to a new marking $M\prime$ , denoted by $M[t〉M\prime$ , that is, $\forall p\in P$ , $M\prime (p)=M(p)-W(p,t)+W(t,p)$ . The set of all reachable markings of a Petri net $N$ from $M_0$ is denoted as $R(N,M_0)$ . A place $p\in P$ is said to be bounded if $\forall M\in R(N,M_0)$ , $\exists k\in \mathbb{N}$ , and $M(p)\le k$ . A net system is said to be k-bounded if any place is bounded. A place $p\in P$ is said to be safe if it is 1-bounded. A net is said to be safe if all of its places are safe. Let $t\in T$ be a transition in $(N,M_0)$ . Transition $t$ is said to be live if $\forall M\in R(N,M_0)$ , $\exists M\prime \in R(N,M_0)$ , such that $M\prime [t〉$ . $(N,M_0)$ is live if $\forall t\in T$ , $t$ is live at $M_0$ . $N$ is dead at $M_0$ if $\cancel{\exists }t\in T$ , $M_0[t〉$ holds. Let $\sigma$ be a transition sequence. $M[\sigma 〉M\prime$ denotes the fact that firing transition sequence $\sigma$ at marking $M$ reaches a (new) marking $M\prime$ . The Parikh vector of $\sigma$ , denoted by $\overrightarrow{\sigma }$ , is a column, represented by $\overrightarrow{\sigma }=[\#\sigma (t_1),\#\sigma (t_2),\dots ,\#\sigma (t_n){]}^T$ , where $n=|T|$ and $\#\sigma (t_i)$ denotes the number of occurrences of $t_i$ in $\sigma$ . A P-vector is a column vector $L:$ $P\to \mathbb{Z}$ , indexed by $P$ , where $\mathbb{Z}=\{\dots ,-2,-1,0,1,2,\dots \}$ . A P-vector $L$ is a place invariant if $L\ne 0$ and $L^T[N]=0^T$ . A T-vector is a column vector $H:T\to \mathbb{Z}$ indexed by $T$ . A T-vector $H$ is a transition invariant if $[N]H=0^T$ and $H\ne 0$ . The support of a place (transition) invariant $L(H)$ is denoted by $||L||=\{p|L(p)\ne 0\}(||H||=t|H(t)\ne 0)$ . A place invariant $L$ is said to be a P-semiflow if $L\ge 0$ .

Transition-based deadlock control

This section proposes an approach to derive a transition-based controller to enforce liveness to a plant net of an FMS. The proposed method utilizes the structural properties of the uncontrolled Petri net model (plant net) for designing transition controllers to avoid the full or partial computation of the RG. However, the proposed method utilizes the knowledge of a RG to develop some techniques that deal with deadlock problem in the plant net for FMSs.

Knowledge of RG analysis

To make a reader understand the research, this subsection reviews the basics of RG analysis. However, we do not compute an RG for finding transitions controllers. Let $G(N,M_0)$ be the RG of a plant net $(N,M_0)$ . It consists of a LZ and a DZ. Usually $\mathrm{LZ}$ and $\mathrm{DZ}$ are used to denote the sets of markings in LZ and DZ, respectively. Formally we have $\mathrm{LZ}=\{M|M\in R(N,M_0),\exists \sigma \in T^{*},M[\sigma 〉M_0\}$ and $\mathrm{DZ}=\{M|M\in R(N,M_0),\cancel{\exists }\sigma \in T^{*},M[\sigma 〉M_0\}$ .

Definition1

Let $(N,M_0)$ be a net system with $N=(P,T,F,W)$ . ²⁷ A marking $M\in \mathrm{DZ}$ is said to be an FBM in $G(N,M_0)$ if $M\prime [t〉M$ , where $M\prime \in \mathrm{LZ}$ , $t\in T$ . The set of FBMs is represented by ${\mathcal{M}}_{\mathrm{FBM}}=\{M\in \mathrm{DZ}|\exists M\prime \in \mathrm{LZ},t\in T$ , s.t. $M\prime [t〉M\}$ .

Figure 1(a) depicts a plant net, and Figure 1(b) visualizes its RG. From the RG, the set of FBMs is ${\mathcal{M}}_{\mathrm{FBM}}=\{M_{12},M_{18},M_{19},M_{20},M_{21},M_{24},M_{27},M_{28},M_{29},M_{30},M_{31},M_{32},M_{33}\}$ . The successive markings of FBMs form another set of markings called second-met bad markings (SBMs).

Figure 1.

(a) A plant net and (b) its RG of the plant net.

Definition 2

Let $(N,M_0)$ be a net system with $N=(P,T,F,W)$ . A marking is said to be an SBM if it is a successive marking of an FBM. Let ${\mathcal{M}}_{\mathrm{SBM}}$ be the set of SBMs. Formally, we have ${\mathcal{M}}_{\mathrm{SBM}}=\{M\in \mathrm{DZ}|\exists M\prime \in {\mathcal{M}}_{\mathrm{FBM}},t\in T$ , s.t. $M\prime [t〉M\}$ . Accordingly, the set of n-met bad markings, denoted by ${\mathcal{M}}_{\mathrm{nBM}}$ , can be defined as ${\mathcal{M}}_{\mathrm{nBM}}=\{M\in \mathrm{DZ}|\exists M\prime \in {\mathcal{M}}_{(n-1)\mathrm{BM}},t\in T$ , s.t. $M\prime [t〉M\}$ , where $n\in \mathbb{N}$ .

The markings $M_{22},M_{25}$ , and $M_{26}$ shown in Figure 1(b) are SBMs of the plant net shown in Figure 1(a), that is, ${\mathcal{M}}_{\mathrm{SBM}}=\{M_{22},M_{25},M_{26}\}$ . While the marking $M_{23}$ is third-met bad marking, as it is a successor marking of a SBM. In general, the markings in the DZ can be classified into $n$ different levels of bad markings with $n\in \{1,2,\dots \}$ . In a bounded Petri net, $n$ is finite and depends the structure and initial marking of the Petri net.

Transition controller

As stated earlier, the proposed method utilizes structural properties a Petri net model to enforce liveness by adding transition-based controllers. A transition controller consists of a set of external (additional) transitions, control arcs, and some parameters that exist in the plant net, to implement particular constraints with respect to markings. As seen in the following, transition controllers are separated from the plant net by sharing control information via control arcs.

The transition-based control technique is implemented by an iterative procedure, in which, at each iteration step, a set of uncontrolled transitions are computed together with controller constraints from the plant net. The iteration would terminate when there are no any uncontrolled transitions in the plant net. To make uncontrolled transitions controlled, for each set of uncontrolled transitions computed by an algorithm (Algorithms 1 and 2 in this article), transition controllers are designed using another algorithm (Algorithm 3 in this article) and are added to the plant net. Generally, there exist in a plant net uncontrollable and unobservable transitions. ⁵² A transition is said to be unobservable if its firing cannot be directly detected or measured. A transition is said to be uncontrollable if its firing cannot be inhibited by an external action. However, this article assumes that all transitions are both observable and controllable.

Algorithm 1 53 Computation of first-met uncontrolled transitions

Input: A Petri net $(N,M_0)$ with $N=(P^0\cup P_A\cup P_R,T,F)$ prone to deadlocks Output: Set of first-met uncontrolled transitions $({\mathrm{\Pi }}^{[1]})$ 1:  ${\mathrm{\Pi }}^{[1]}=\varnothing$ ; $l=1,2,\dots ,\omega$ $/*\omega$ is the number of concurrent process in the $\mathrm{net}*/$ 2: while $l\le \omega$ do 3: Identify $(p_l^0)$ and $P_{A_l}=\{p_i,p_{i+1},p_{i+2},\dots ,p_n\}$ 4:  ${\mathrm{\Pi }}^{*}=\varnothing$ 5:  Compute $(p_l^0{)}^{••}$ ; let $p_i$ be the activity place in $(p_l^0{)}^{••}$ ; choose a resource place $r$ such that $p_i\in ||I_r||$ , and compute $||{\chi }_i(A)||\cup ||{\chi }_i(r)||=||{\chi }_{(r,p_i)}||=\{r,p|r\in P_R,p\in P_A\}$ 6: for $(i=1,|P_{A_l}|,i++)$ do 7: if $||{\chi }_{(r,p_i)}||\ne ||I_r||$ then 8:  Choose an activity place $p_{i+1}$ from $p_i^{••}$ ; find a resource place $r$ such that $p_{i+1}\in ||I_r||$ ; compute $||{\chi }_{(r,p_{i+1})}||=\{r,p_{i+1}|r\in P_R,p_{i+1}\in P_A,p_{i+1}\in ||I_r||\}$ 9: else 10:  ${\mathrm{\Pi }}^{*}={\mathrm{\Pi }}^{*}{\cup }^{•}{p}_i$ 11: end 12: end 13:  $l=l+1,{\mathrm{\Pi }}^{[1]}={\mathrm{\Pi }}^{[1]}\cup {\mathrm{\Pi }}^{*}$ 14: end 15: Output the set of active uncontrolled transitions ${\mathrm{\Pi }}^{[1]}$ .

Algorithm 2 Computation of n-met uncontrolled transitions

Input: A Petri net $(N,M_0)$ with $N=(P^0\cup P_A\cup P_R,T,F)$ prone to deadlocks Output: A set $(\Omega )$ of uncontrolled transitions 1: find the set of first-met uncontrolled transitions ${\mathrm{\Pi }}^{[1]}$ by Algorithm 1 2: Compute the set of first-met activity places ${\Theta }^{[1]}$ by Definition 5 3: Compute the first-met shared resource places $r_l^{[1]}$ by Definition 8 4:  $n=1$ , $\Omega ={\mathrm{\Pi }}^{[1]}$ 5: if $(p_{l^{\prime }}^{[n]}{)}^{•}\subseteq (r_l^{[n]}{)}^{•}$ then /* $\exists l,l\prime \in \{1,2,\dots ,\omega \}$ , $l\ne l\prime$ */ 6: go to step 15 7: else 8:  $n=n+1$ 9: Compute n-met shared resource places using Definition 10 10: Compute n-met uncontrolled transitions ${\mathrm{\Pi }}^{[n]}$ from Definition 11 11: Compute n-met activity places $({\Theta }^{[n]})$ from Definition 12 12:  $\Omega =\Omega \cup {\mathrm{\Pi }}^{[n]}$ 13: end 14: go to step 5 15: Output the set of uncontrolled transitions $\Omega$ .

Algorithm 3 Design of transition controllers

Input: A Petri net $(N,M_0)$ with $N=(P^0\cup P_A\cup P_R,T,F)$ prone to deadlocks Output: A live Petri net system $(N^{\mathrm{Cn}},M_0^{\mathrm{Cn}})$  1:  Compute the set of uncontrolled transitions $\Omega$ by Algorithm 2  2:   $\mathcal{C}:=\varnothing$ , $n=1$ , /* $\mathcal{C}$ denotes the set of transition controllers */  3:  for $(i=1,i++,|\Omega |)$ do  4:  Design an i-order transition controller $C_l^{[i]}$  5:  if $n=1$ then  6:   $C_l^{[i]}=(\{p_l^{[1]},p_l^0,r_l^{[1]}\},\{t_{\mathrm{ci}}^{[1]}\},F_l^{[1]},W_l^{[1]})$ with  7:   $F_l^{[n]}=\{(p_l^{[1]},t_{\mathrm{ci}}^{[1]}),(t_{\mathrm{ci}}^{[1]},p_l^0),(t_{\mathrm{ci}}^{[1]},r_l^{[1]})\}$  8:   $W_l^{[n]}=W_l^{[1]}(p_l^{[1]},t_{\mathrm{ci}}^{[1]})=W_l^{[1]}(t_{\mathrm{ci}}^{[1]},P_l^{[0]})=W_l^{[1]}(t_{\mathrm{ci}}^{[1]},r_l^{[1]})=1$  9:  else 10:   $C_l^{[i]}=(\{p_l^{[1]},p_l^{[n]},r_l^{[1]},r_l^{[n]}\},\{t_{\mathrm{ci}}^{[n]}\},F_l^{[n]},W_l^{[n]})$ , with 11:   $F_l^{[n]}=\{(p_l^{[n]},t_{\mathrm{ci}}^{[n]}),(t_{\mathrm{ci}}^{[n]},p_l^{[1]}),(r_l^{[1]},t_{\mathrm{ci}}^{[n]}),(t_{\mathrm{ci}}^{[n]},r_l^{[n]})\}$ 12:   $W_l^{[n]}=W_l^{[n]}(t_{\mathrm{ci}}^{[n]},p_l^{[1]})=W_l^{[n]}(p_l^{[n]},t_{\mathrm{ci}}^{[n]})=W_l^{[n]}(r_l^{[1]},t_{\mathrm{ci}}^{[n]})=$ 13:   $W_l^{[n]}(t_{\mathrm{ci}}^{[n]},r_l^{[n]})=1$ 14:   $/*t_{\mathrm{ci}}^{[n]}$ denotes a control transition to be added to the plant $\mathrm{net}*/$ 15:  end 16:   $n=n+1$ 17:   $\mathcal{C}:=\mathcal{C}\cup \{C_l^{[i]}\}$ 18: end 19: Output $(N^{\mathrm{Cn}},M_0^{\mathrm{Cn}})$ .

Uncontrolled transitions are responsible to drive the markings to the DZ. The FBMs are derived by firing the first-met uncontrolled transitions; the SBMs are derived by firing the second-met uncontrolled transitions and accordingly the n-met bad markings are derived by firing the n-met uncontrolled transitions.

We consider a class of Petri nets, called M-nets, in this article. An M-net ⁴⁰ is a Petri net $(N,M_0)$ with $N=(P,T,F,W)$ which has a place partition with $P=P_0\cup P_A\cup P_R$ and a transition partition $T=T_1\cup T_2\cup \cdots \cup T_{\omega }$ , where $\forall i,j\in \{1,2,\dots ,\omega \}$ , $i\ne j$ , $T_i\cap T_j=\varnothing$ , $P_0$ is a set of process idle places, $P_A$ is a set of activity places, and $P_R$ is a set of resource places with $P_0$ , $P_A$ , and $P_R$ being mutually disjoint. Activity place set $P_A$ has a partition with $P_A=P_{A1}\cup P_{A2}\cup \cdots \cup P_{A\omega }$ , where $\forall i,j\in \{1,2,\dots ,\omega \}$ , $P_{\mathrm{Ai}}\cap P_{\mathrm{Aj}}=\varnothing$ , implying that a system is composed of $\omega$ concurrent processes. In an M-net, each resource place $r$ is associated with a minimal P-semiflow, denoted by $I_r$ whose support $||I_r||$ contains the resource place $r$ and some activity places that need the resource $r$ to participate. Simply speaking, an M-net is composed of a set of state machines that are connected by shared resources. Without loss of generality, we assume that each process idle place has only one output transition, that is, $\forall l\in \{1,2,\dots ,\omega \}$ , $|(p_l^0{)}^{•}|=|(p_l^0{)}^{••}|=1$ .

Definition 3

The first-met uncontrolled transition is a transition whose firing at a certain state leads a system to the DZ. Let $\mathrm{\Pi }$ denote the set of active uncontrolled transitions in a Petri net model.

Definition 4

Let $r$ be a resource place in $(N,M_0)$ and $||I_r||$ be the support of the minimal P-semiflow associated with $r$ in $(N,M_0)$ . An activity resource transition circuit (ARTC) associated with resource place $r$ is a simple circuit ${\chi }_r\equiv p\stackrel{t_i}{\to }r\stackrel{t_j}{\to }p$ , where $\exists l\in \{1,2,\dots ,\omega \}$ , $t_i,t_j\in T_l$ , $p\in P_A$ , and $r\in P_R$ . The support of an ARTC is defined as $||{\chi }_r||=\{r,p|r\in P_R,p\in P_A\}$ . In general, $||\chi ||\subseteq ||I||$ in $(N,M_0)$ .

Definition 5

Let $P_t^{[1]}\subseteq P_A$ be a set of activity places in the postset of a first-met uncontrolled transition $t\in {\mathrm{\Pi }}^{[1]}$ , that is, $P_t^{[1]}=t^{•}\cap P_A$ . A place in the postset of an uncontrolled transition is called a first-met activity place. The set of first-met activity places is hence denoted by ${\Theta }^{[1]}={\cup }_{t\in {\mathrm{\Pi }}^{[1]}}{t}^{•}\cap P_A={\cup }_{t\in {\mathrm{\Pi }}^{[1]}}{P}_t^{[1]}$

Let us consider the model in Figure 1(a). The set of first-met uncontrolled transitions is ${\mathrm{\Pi }}^{[1]}=\{t_1,t_{10}\}$ . The postset of $t_1$ is $\{p_2\}$ and that of $t_{10}$ is $\{p_{13}\}$ . The set of first-met activity places is ${\Theta }^{[1]}=\{p_2,p_{13}\}$ . The plant net consists of several resource places shared by different jobs among the concurrent processes. We classify the resources in a plant net model into unshared resources and shared resources, that is, $P_R=R^S\cup R^U$ , where $R^U$ denotes the set of unshared resources and $R^S$ denotes the set of resources with $R^U\cap R^S=\varnothing$ .

Corollary 1

Let $P_t^{[1]}\subseteq P_A$ be a set of activity places in the postset of a first-met uncontrolled transition $t$ in an M-net. Then, $|P_t^{[1]}|=1$ , that is, $P_t^{[1]}$ contains a unique activity place.

Proof 1

By considering the definition of a state machine, it is trivial since an M-net is composed of a set of state machines that share resources.

Definition 6

Let $r$ be a resource in an M-net $(N,M_0)$ with $N=(P_0\cup P_A\cup P_R,T,F,W)$ and $I_r$ be the minimal P-semiflow associated with $r$ , where $P_A={\cup }_{i=1}^l{P}_{\mathrm{Ai}}$ . Resource $r$ is said to be unshared if $\exists j\in \{1,2,\dots ,l\}$ , $(||I_r||\backslash \{r\})\subseteq P_{\mathrm{Aj}}$ .

Definition 7

Resource $r$ is said to be shared if $\exists p,p\prime \in (||I_r||\backslash \{r\})$ , $p\in P_{\mathrm{Ai}}$ , $p\prime \in P_{\mathrm{Aj}}$ , $i\ne j$ .

Definition 8

A resource place is said to be a first-met shared resource place, denoted by $r_l^{[1]}$ , if its postset contains a first-met uncontrolled transition, that is, $\exists t\in {\mathrm{\Pi }}^{[1]}$ $t\in r_l^{[1]•}$ .

Let us consider the plant net model of Figure 1(a), where there are two concurrent processes. The set of shared resource place $P_R=\{p_6,p_7,p_8,p_9\}$ with $R^S=\{p_6,p_7,p_8,p_9\}$ , and the set of unshared resource places is $R^U=\varnothing$ . The postset of $p_6$ is $\{t_1,t_7\}$ . Since $t_1$ is in the set of first-met uncontrolled transitions, $p_6$ is the first-met resource place, that is, $r_1^{[1]}=p_6$ . With no ambiguity, the first-met shared resource $p_6$ belongs to process I as the process contains the first-met uncontrolled transition. Similarly, the postset of resource place $p_9$ is $\{t_4,t_{10}\}$ with $t_{10}$ being a first-met uncontrolled transition. The resource place $p_9$ is a first-met shared resource place, denoted by $r_2^{[1]}=p_9$ . Without lost of generality, this first-met shared resource place belongs to process II as the process contains the first-met uncontrolled transition $t_{10}$ . Next, we define a transition controller.

Definition 9

A first-order transition controller $C_l^{[1]}$ for an M-net $(N,M_0)$ is defined as a four-tuple $C_l^{[1]}=(\{p_l^{[1]},p_l^0,r_l^{[1]}\},\{t_{\mathrm{ci}}^{[1]}\},F_l^{[1]},W_l^{[1]})$ where $p_l^{[1]}$ , $p_l^0$ , and $r_l^{[1]}$ are the first-met activity place, process idle place, and first-met shared resource place, respectively; $t_{\mathrm{ci}}^{[1]}$ is the first additional control transition; $F_l^{[1]}=\{(p_l^{[1]},t_{\mathrm{ci}}^{[1]}),(t_{\mathrm{ci}}^{[1]},P_l^{[0]}),(t_{\mathrm{ci}}^{[1]},r_l^{[1]})\}$ is called a flow relation from the plant to the first-order transition controller; and $W_l^{[1]}(p_l^{[1]},t_{\mathrm{ci}}^{[1]})$ , $W_l^{[1]}(t_{\mathrm{ci}}^{[1]},P_l^{[0]})$ , $W_l^{[1]}(t_{\mathrm{ci}}^{[1]},r_l^{[1]})\in \mathbb{N}$ are the weights of the concerned arcs between the transition and the plant net $(N,M_0)$ .

Corollary 2

The number of the first-order transition controllers is equal to that of concurrent processes in an M-net $(N,M_0)$ .

Proof 2

Each first-met uncontrolled transition corresponds to a first-order transition controller. Furthermore, each process has a process idle place and each process idle place corresponds to a first-met uncontrolled transition. Thus, the result is true.

Perhaps the first transition controllers are capable of transforming all FBMs markings to live markings. In a situation where a plant net contains SBMs, the plant net needs second-order transition controllers to re-enforce liveness. In general, for a plant net with n-met bad markings, to re-enforce liveness with all its markings in the RG, the plant net needs n-order transition controllers.

Given two shared resource places $r_l^{[1]}$ and $r_l^{[2]}$ , $r_l^{[1]}$ is said to wait for $r_l^{[2]}$ , denoted by $r_l^{[2]}\stackrel{t}{\to }{r}_l^{[1]}$ , if the availability of $r_l^{[2]}$ is an immediate condition to release $r_l^{[1]}$ by firing the transition $t$ . Equivalently, $\exists t\in T$ , $t{\in }^{•}(r_l^{[1]})\cap (r_l^{[2]}{)}^{•}$ . ³⁴

Definition 10

$r_l^{[n]}$ is called n-met shared resource place if it forms a circular path (resource transition circuit) with an (n–1)-met shared resource place, that is, $r_l^{[n]}\stackrel{t_x}{\to }{r}_l^{[n-1]}\stackrel{t_m}{\to }{r}_l^{[n]}$ , $\exists t_x,t_y\in T$ , $l\in \{1,2,\dots ,n\}$ , $t_x{\in }^{•}(r_l^{[n-1]})\cap (r_l^{[n]}{)}^{•}$ , and $t_y{\in }^{•}(r_l^{[n]})\cap (r_l^{[n-1]}{)}^{•}$ .

Definition 11

$t_l^{[n]}$ is said to be n-met uncontrolled transition if it satisfies one of the following statements: (1) $\exists r_l^{[n-1]},r_l^{[n]}\in R^S$ , $r_l^{[n]}\stackrel{t_l^{[n]}}{\to }{r}_l^{[n-1]}$ and (2) $\exists r_l^{[n-1]},r_l^{[n]}\in R^S$ , $\exists r_i^U\in R^U$ , $r_l^{[n]}\stackrel{t_l^{[n]}}{\to }{r}_i^U\stackrel{t_y}{\to }{r}_l^{[n-1]}$ , where $t_y\in T$ .

By the definition of an M-net, for any activity place $p$ , it satisfies $|p^{•}|={|}^{•}p|=1$ . That is to say, for a transition $t$ , its postset contains one activity place only.

Definition 12

The place in the postset of an n-met uncontrolled transition $t_l^{[n]}$ is called n-met activity place, denoted by $p_l^{[n]}$ . The set of n-met activity places is ${\Theta }^{[n]}=\{p|p\in (t_l^{[n]}{)}^{•}\cap P_A,l=1,2,\dots ,\omega \}$ .

In the plant net visualized in Figure 1(a), there are two circular paths (circuits) with first-met shared resource places: $p_7\stackrel{t_2}{\to }{p}_6\stackrel{t_7}{\to }{p}_7$ , that is, $p_7{t}_2{p}_6{t}_7{p}_7$ and $p_8\stackrel{t_9}{\to }{p}_9\stackrel{t_4}{\to }{p}_8$ , that is, $p_8{t}_9{p}_9{t}_4{p}_8$ . From Definition 10, $r_1^{[2]}=p_7$ and $r_2^{[2]}=p_8$ are second-met shared resource places. Using Definition 11, $p_7\stackrel{t_2}{\to }{p}_6$ satisfies Condition (1), and therefore, the second-met uncontrolled transition is $t_1^{[2]}=t_2$ . Similarly, $p_8\stackrel{t_9}{\to }{p}_9$ satisfies Condition (1) in Definition 11. Then $t_2^{[2]}=t_9$ is also a second-met uncontrolled transition in the plant net. Without loss of generality, we assume that the second-met resource place $p_7$ belongs to process I, as it identifies the second-met uncontrolled transition in process I. Similarly, we assume that the second-met shared resource place $p_8$ belongs to process II, as it identifies the second-met uncontrolled transition from process II. The postset of $t_2$ contains the second-met activity place $p_3=p_1^{[2]}$ , and the postset of $t_9$ contains the second-met activity place $p_{12}=p_2^{[2]}$ . The set of second-met activity places is ${\Theta }^{[2]}=\{p_3,p_{12}\}$ . Next, we accordingly define an n-order transition controller by first-order transition controllers.

Definition 13

Let $C_l^{[i]}$ be an n-order transition controller for a plant M-net $(N,M_0)$ . It is a four-tuple $C_l^{[i]}=(\{p_l^{[1]},p_l^{[n]},r_l^{[1]},r_l^{[n]}\},\{t_{\mathrm{ci}}^{[n]}\},F_l^{[n]},W_l^{[n]})$ where $p_l^{[1]}$ and $p_l^{[n]}$ are the first-met and n-met activity places, respectively, and $r_l^{[1]}$ and $r_l^{[n]}$ are the first-met and n-met shared resource places, respectively. $t_{\mathrm{ci}}^{[n]}$ is the nth additional control transition. $F_l^{[n]}=\{(t_{\mathrm{ci}}^{[n]},p_l^{[1]}),(p_l^{[n]},t_{\mathrm{ci}}^{[n]}),(r_l^{[1]},t_{\mathrm{ci}}^{[n]}),(t_{\mathrm{ci}}^{[n]},r_l^{[n]})\}$ is called a flow relation from the plant net to the transition controller, simply represented by directed arcs. $W_l^{[n]}(t_{\mathrm{ci}}^{[n]},p_l^{[1]})$ , $W_l^{[n]}(p_l^{[n]},t_{\mathrm{ci}}^{[n]})$ , $W_l^{[n]}(r_l^{[1]},t_{\mathrm{ci}}^{[n]}),W_l^{[n]}(t_{\mathrm{ci}}^{[n]},r_l^{[n]})\in \mathbb{N}$ are the weights of concerned arcs between the transition controller and the plant net.

Deadlock prevention policy using transition controller and its correctness

This section presents two iterative algorithms. The first is to compute all the n-met uncontrolled transitions in the plant net. The second is capable of designing transition controllers to re-enforce liveness of the plant net such that all the reachable markings in the original plant model are preserved.

Algorithm 2 uses the structural properties of a plant net to compute all the n-met uncontrolled transitions. The proposed algorithm is an iterative procedure. At each iteration step, a set of n-met uncontrolled transitions is computed. The iterations terminate at a particular condition when $(p_{l^{\prime }}^{[n]}{)}^{•}\subseteq (r_l^{[n]}{)}^{•}$ , where $r_l^{[n]}$ is the n-shared resource place obtained from the lth process and $p_{l\prime }^{[n]}$ is the n-activity place obtained from the l′-th process. Note that, $l\prime \in \{1,2,\dots ,\omega \}\backslash \{l\}$ .

In theory, if this condition $(p_{l\prime }^{[n]}{)}^{•}\subseteq (r_l^{[n]})$ is met, it implies that the rest of the transitions in lth process is properly covered with respect to the n-met shared resource places from the l′-th process. It means that there are no remaining transitions in the Petri net model with respect to the process under consideration that can be found in the DZ. Otherwise, there are still some transitions in the lth process that are not properly covered with respect to the n-met shared resource places from the l′-th process. This simply means that there are some remaining transitions in the Petri net model with respect to the process under consideration to be included in the DZ.

Suppose that we consider the plant net shown in Figure 1(a). Assume that process I can be referred as the lth process, while process II can be referred as the l′-th process. At the first iteration, that is, n = 1, the set of first-met uncontrolled transitions computed by Algorithm 1 is ${\mathrm{\Pi }}^{[1]}=\{t_1,t_{10}\}$ with $t_1^{[1]}=t_1$ and $t_2^{[1]}=t_{10}$ . The set of first-met activity places is ${\Theta }^{[1]}=\{p_2,p_{13}\}$ with $p_1^{[1]}=p_2$ and $p_2^{[1]}=p_{13}$ . The first-met shared resource place in the lth process is $r_1^{[1]}=p_6$ , while the first-met activity place in process $l\prime$ is $p_2^{[1]}=p_{13}$ . $(r_1^{[1]}{)}^{•}=\{t_1,t_2\}$ and $(p_2^{[1]}{)}^{•}=\{t_9\}$ , since $(p_2^{[1]}{)}^{•}\cancel{\subseteq }(r_1^{[1]}{)}^{•}$ signifies that there are some transitions in the l′-th process not properly covered by the n-met shared resource place from the lth process. Similarly, for process II, the first-met shared resource place from the l′-th process is $r_2^{[1]}=p_9,$ while the first-met activity place in the lth process is $p_2^{[1]}=p_2$ . $(r_2^{[1]}{)}^{•}=\{t_4,t_{10}\}$ and $(p_1^{[1]}{)}^{•}=\{t_2\}$ , since $(p_1^{[1]}{)}^{•}\cancel{\subseteq }(r_2^{[1]}{)}^{•}$ implying that there are some transitions in the lth process not properly covered by the n-met shared resource places from the l′-th process. We conclude that there exist remaining uncontrolled transitions in both the processes as the termination condition is not met.

We proceed to the second iteration by increasing $n$ , that is, $n=2$ . The set of second-met uncontrolled transitions is ${\mathrm{\Pi }}^{[2]}=\{t_2,t_9\}$ with $t_1^{[2]}=t_2$ and $t_2^{[2]}=t_9$ . The second-met shared resource place from $l$ process $r_1^{[2]}=p_7,$ while the second-met activity place in process $l\prime$ is $p_2^{[2]}=p_{12}$ . $(r_1^{[2]}{)}^{•}=\{t_2,t_8\}$ and $(p_2^{[2]}{)}^{•}=\{t_8\}$ , since $(p_2^{[2]}{)}^{•}\subseteq (r_1^{[2]}{)}^{•}$ satisfying the termination condition. It implies that the rest of the transitions in the l′-th process is properly covered by the first-met and second-met resource places from the lth process. The second-met shared resource place from the l′-th process $r_2^{[2]}=p_8,$ while the second-met activity place in process $l$ is $p_1^{[2]}=p_3$ . $(r_2^{[2]}{)}^{•}=\{t_3,t_9\}$ and $(p_1^{[2]}{)}^{•}=\{t_3\}$ , since $(p_1^{[2]}{)}^{•}\subseteq (r_2^{[2]}{)}^{•}$ satisfies the termination condition. It shows that the rest of the transitions in the lth process is properly covered by the first-met and second-met resource places from the l′-th process. This can be seen from Figure 1(b), and the transitions $(t_1,t_2,t_9,t_{10})$ are the only transitions in the DZ that are referred to as uncontrolled transitions.

Proposition 1

Algorithm 2 can compute all the n-met uncontrolled transitions in all the concurrent processes in an M-net.

Proof 3

Suppose that there exist uncontrolled transitions in any concurrent process of the plant net $(N,M_0)$ , then $(p_{l\prime }^{[n]}{)}^{•}\cap (r_l^{[n]}{)}^{•}=\varnothing$ , implying that the termination condition for Algorithm 2 does not meet. Since each concurrent process has finite transitions, after a few iteration steps, $(p_{l\prime }^{[n]}{)}^{•}\cap (r_l^{[n]}{)}^{•}\ne \varnothing$ is true with $(p_{l\prime }^{[n]}{)}^{•}\subseteq (r_l^{[n]}{)}^{•}$ . We conclude that all the uncontrolled transitions are computed from the plant net.

Theorem 1

Assume that a liveness-enforcing supervisor exists at some initial marking of $(N^n,M_0^{\mathrm{cn}})$ for an M-net. If $(p_{l\prime }^{[n]}{)}^{•}\subseteq (r_l^{[n]}{)}^{•}$ holds, then all transitions not in ${}^{•}(p_{l\prime }^{[n]})$ are properly covered by $r_l^{[n]}$ , where $p_{l\prime }^{[n]}$ is the n-met activity place from the l′-th process, and $r_l^{[n]}$ is the n-met resource place from the lth process.

Proof 4

Let $n$ be the finite number of iteration steps. We need to show that at $(n+1)$ steps, we have the shared resource $r_l^{[n+1]}=r_{l\prime }^{[n]}$ . Given the sets of transitions $T_l$ and $T_{l\prime }$ in $(N,M_0)$ . $T_l=T\backslash T_{l\prime }$ is the set of transition from the lth process. Similarly, $T_{l\prime }=T\backslash T_l$ is the set of transitions from the l′-th process. At $n=i$ (i.e. $i=1,2,\dots ,n$ ), $\exists t_i\in T_l$ , $t_i$ cannot be fired unless the place ${{}^{•}t}_i$ is marked, which cannot become marked unless the transitions in ${{}^{••}t}_i\cap (r_l^{[i]}{)}^{•}$ are fired. Let $p_l^{[i+1]}={t_i}^{•}\cap {(r_l^{[i+1]})}^{••}$ . The transitions in $(p_l^{[i+1]}{)}^{•}$ cannot fire unless the place in $(t_i{)}^{•}$ is marked, which cannot become marked unless the transitions in ${}^{•}pl[i+1]\cap (r_l^{[i+1]}{)}^{•}$ fire before. It continues in the same way until it reaches $r_l^{[n]}$ . Similarly, $\exists t_i\in T_{l^{\prime }}$ , $t_i$ cannot be fired unless the place in ${{}^{•}t}_i$ is marked, which cannot become marked unless the transition in ${{}^{••}t}_i\cap (r_{l\prime }^{[i]}{)}^{•}$ is fired. Let $p_{l^{\prime }}^{[i+1]}={t_i}^{•}\cap (r_{l\prime }^{[i+1]}{)}^{••}$ . The transition in $(p_{l\prime }^{[i+1]}{)}^{•}$ cannot fire unless the place in $(t_i{)}^{•}$ is marked, which cannot become marked unless the transition in ${{}^{•}p}_{l\prime }^{[i+1]}\cap (r_{l\prime }^{[i+1]}{)}^{•}$ fires before. It continues in the same way until it reaches $r_{l\prime }^{[n]}$ . In addition to ${{}^{•}p}_l^{[n]}\cap (r_l^{[n]}{)}^{•}$ , the rest of transitions in the lth process is properly covered by n-met shared resource places from the l′-th process. This process repeats at $n=n+1$ , and the transition in $(p_{l\prime }^{[n+1]}{)}^{•}$ can fire, since the place in $(t_n{)}^{•}$ is marked. At that instant, $p_l^{[n+1]}+p_{l\prime }^{[n]}+r_l^{[n+1]}$ forms a minimal P-invariant and $p_{l\prime }^{[n]}+p_l^{[n+1]}+r_{l\prime }^{[n]}$ forms a minimal P-invariant. Hence, $r_l^{[n+1]}=r_{l\prime }^{[n]}$ .

Algorithm 3 is an iterative procedure. At each iteration step, a transition controller is designed till all uncontrolled transitions are processed. When the derived n-order transition controllers are added to the uncontrolled plant net, a live plant net is obtained with all its markings as in the uncontrolled plant net.

Theorem 2

The transition controllers designed by Algorithm 3 can provide a guarantee for the liveness of a plant net.

Proof 5

By Proposition 1, for each computed uncontrolled transition of the uncontrolled plant net, a transition controller is designed using Algorithm 3. This makes each uncontrolled transition to be controlled. Finally, when all the transitions in the plant net are controlled, there is no any transition that can take the states in the plant net to n-met bad markings. Hence, the resulting plant net is live with all its states being preserved.

Theorem 3

Let $C_l^{[i]}=(\{p_l^{[1]},p_l^{[n]},r_l^{[1]},r_l^{[n]}\},\{t_{\mathrm{ci}}^{[n]}\},F_l^{[n]},W_l^{[n]})$ be the n-met transition controller of $(N^{\mathrm{cn}},M_0^{\mathrm{cn}})$ with $P$ being the set of places in $N$ . $R\prime (N^{\mathrm{cn}},M_0^{[\mathrm{cn}]})=\{M^{[\mathrm{cn}]|U}|M^{[\mathrm{cn}]}\in R(N^{\mathrm{cn}},M_0^{\mathrm{cn}})\}$ is the projection of $R(N^{\mathrm{cn}},M_0^{\mathrm{cn}})$ onto $R(N,M_0)$ , where $M^{[\mathrm{cn}]|U}$ is the projection of $M^{[\mathrm{cn}]}$ onto $M_0$ (i.e. $p\in P,M^{{[\mathrm{cn}]}_0}(p)=M_0(p)$ ), which is a ||P||-dimensional vector. Then, $R\prime (N^{\mathrm{cn}},M_0^{[\mathrm{cn}]})=R(N^{\mathrm{cn}},M_0^{\mathrm{cn}})$ implies that the controlled model reaches the same number of states as the uncontrolled model.

Proof 6

We prove by induction. First, it is obvious that $M_0^{[\mathrm{cn}]|U}=M_0^{[\mathrm{cn}]}$ . Let $t$ be an uncontrolled transition and $t_c$ be the first-met control transition. Assume that $t$ and $t_c$ are both enabled in $N$ and $N^{[\mathrm{cn}]}$ (i.e. $N^{[\mathrm{cn}]}$ is the Petri net with first-met controlled transitions included), respectively. Let $M_1$ and $M_1^{[\mathrm{cn}]}$ be markings such that $M_0[t〉M_1$ and $M_0^{[\mathrm{cn}]}[t_c〉M_1^{[\mathrm{cn}]}$ . Then, $M_1^{[\mathrm{cn}]|U}=M_1$ since they have the same set of identical marked places under $M_1$ and $M_1^{[\mathrm{cn}]}$ . Thus, the theorem holds at this case.

Assume that it also holds at $\parallel \sigma \parallel =k$ (i.e. $\sigma$ is the firing sequence of transitions). We need to show that it also holds for $\parallel \sigma \parallel =k+1$ . Let $M_0[\sigma 〉M_k$ and $M_0^{[\mathrm{cn}]}[{\sigma }^c〉M_k^{[\mathrm{cn}]}$ . By the assumption, $M_k^{[\mathrm{cn}]|U}=M_k$ , the same set of $t_{\mathrm{ci}}$ transitions will be enabled without disabling any transition by $C_l^{[i]}$ . Similarly, following the same arguments, we have $M_k[t〉M_{k+1}$ and $M_k^{[\mathrm{cn}]}[t_c〉M_{k+1}^{[\mathrm{cn}]}$ and the following similar argument $M_k^{[\mathrm{cn}]|U}=M_k$ and $M_{k+1}^{[\mathrm{cn}]|U}=M_{k+1}$ holds. Hence, it shows that $R\prime (N^{\mathrm{cn}},M_0^{[\mathrm{cn}]})=R(N^{\mathrm{cn}},M_0^{\mathrm{cn}})=R(N,M_0)$ implies the controlled model reaches the same number of states as the uncontrolled model.

To demonstrate Algorithm 3, let us consider the plant net shown in Figure 1(a). First, we compute the n-met uncontrolled transitions from the plant net. Second, for the first-met uncontrolled transitions, a first-order transition controller is designed as shown in Figure 2(a) (Table 1). We have $C_1^{[1]}=(\{p_2,p_1,p_6\},\{t_{c1}^{[1]}\},F_1^{[1]},W_1^{[1]})$ with $F_1^{[1]}=\{(p_2,t_{c1}^{[1]}),(t_{c1}^{[1]},p_1),(t_{c1}^{[1]},p_6)\}$ and $W_1^{[1]}(p_2,t_{c1}^{[1]})=W_1^{[1]}(t_{c1}^{[1]},p_1)=W_1^{[1]}(t_{c1}^{[1]},p_6)=1$ . Similarly, we have $C_2^{[1]}=(\{p_{13},p_{14},p_9\},t_{c2}^{[1]},F_2^{[1]},W_2^{[1]})$ with $F_2^{[1]}=\{(p_{13},t_{c2}^{[1]}),(t_{c2}^{[1]},p_{14}),(t_{c2}^{[1]},p_9)\}$ and $W_2^{[1]}(p_{13},t_{c2}^{[1]})=W_2^{[1]}(t_{c2}^{[1]},p_{14})=W_2^{[1]}(t_{c2}^{[1]},p_9)=1$ . Third, we compute the second-order transition controllers for the corresponding second-met uncontrolled transitions as $C_1^{[2]}=(\{p_2,p_3,p_6,p_7\},\{t_{c3}^{[2]}\},F_1^{[2]},W_1^{[2]})$ with $F_1^{[2]}=\{(t_{c3}^{[2]},p_2),(p_3,t_{c3}^{[2]}),(p_6,t_{c3}^{[2]}),(t_{c3}^{[2]},p_7)\}$ and $W_1^{[2]}(t_{c3}^{[2]},p_2)=W_1^{[2]}(p_3,t_{c3}^{[2]})=W_1^{[2]}(p_6,t_{c3}^{[2]})=W_1^{[2]}(t_{c3}^{[2]},p_7)=1$ . Similarly, we have $C_2^{[2]}=(\{p_{13},p_{14},p_9,p_8\},\{t_{c4}^{[2]}\},F_2^{[2]},W_2^{[2]})$ with $F_2^{[2]}=\{(t_{c4}^{[2]},p_{13}),(p_{12},t_{c4}^{[2]}),(p_9,t_{c4}^{[2]}),(t_{c4}^{[2]},p_8)\}$ and $W_2^{[2]}(t_{c4}^{[2]},p_{13})=W_2^{[2]}(p_{12},t_{c4}^{[2]})=W_2^{[2]}(p_9,t_{c4}^{[2]})=W_2^{[2]}(t_{c4}^{[2]},p_8)=1$ . After adding the second-order transition controllers to $(N^{C1},M_0^{C1})$ , the plant net $(N^{C2},M_0^{C2})$ is live with all its 48 markings. The plant net model $(N^{C2},M_0^{C2})$ contains all the transition controllers (Table 2) to re-enforce liveness as shown in Figure 2(b).

Figure 2.

(a) A plant net coupling with a first-order transition controller and (b) a plant net with final transition controllers.

Table 1.

Summary of transition controllers for a plant net shown in Figure 2(b).

S/N	Constraint	$C_l^{[n]}$	$t_{\mathrm{ci}}^{[n]}$	Pre	Post
1	$p_1+p_2+p_6$	$C_1^{[1]}$	$t_{c1}^{[1]}$	$p_2$	$p_1,p_6$
2	$p_9+p_{13}+p_{14}$	$C_2^{[1]}$	$t_{c2}^{[1]}$	$p_{13}$	$p_9,p_{14}$
3	$p_2+p_3+p_6+p_7$	$C_1^{[2]}$	$t_{c3}^{[2]}$	$p_3,p_6$	$p_2,p_7$
4	$p_8+p_9+p_{12}+p_{13}$	$C_2^{[2]}$	$t_{c4}^{[2]}$	$p_9,p_{12}$	$p_8,p_{13}$

Table 2.

Supervisory structure for a plant net shown in Figure 2(b).

No. control transition	No. control arcs	Total No. reachable states
4	14	48

Experimental examples

This section presents experimental results to expose the applicability of the proposed method that is not only confined to the examples or the class of Petri nets presented in this article, rather it is applicable to the existing M-nets manufacture-oriented Petri net models of FMSs in the literature. The examples considered in this article are almost benchmark examples extensively used in the literature to show the strength of the proposed method compared with other deadlock control policies.

Example 1

Let us consider an FMS shown in Figure 3. The FMS consists of three machines M1, M2, and M3, each of which can process two part at a time. It consist of three robots R1, R2, and R3 which can hold one part at a time. Parts enter the FMS through input/output buffers I1/O1 and I2/O2. Parts P1 and P2 are considered in the production sequence. Initially, it is assumed that there are no parts in the system.

Figure 3.

(a) An FMS layout and (b) its production sequences.

Its equivalent representation of FMS shown in Figure 3 is depicted in Figure 4 using Petri nets. The places in the Petri net model can be represented as $P=P^0\cup P_A\cup P_R$ , where $P^0=\{p_1,p_{14}\}$ , $P_R=\{p_{15},\dots ,p_{20}\}$ , and $P_A=\{p_2,\dots ,p_{13}\}$ . Places $p_2,p_3,p_4,p_5,p_6$ , and $p_7$ represent the operations of M1, R1, M2, R2, M3, and R3 for the production sequence of part P1, respectively. Similarly, for the production sequence part P2, places $p_8,p_9,p_{10},p_{11},p_{12}$ , and $p_{13}$ represent the operations of R3, M3, R2, M2, R1, and M1 respectively. Places $p_1$ and $p_{12}$ represent the I1/O1 and I2/O2 buffers, respectively. While places $p_{15},p_{16},p_{17},p_{18},p_{19}$ , and $p_{20}$ represent the shared resources of M1, R1, M2, R2, M3, and R3 respectively.

Figure 4.

(a) A plant net of FMS shown in Figure 3 and (b) a plant net with a first transition controller $(N^{C1},M_0^{C1})$ .

The set of first-met uncontrolled transitions is ${\mathrm{\Pi }}^{[1]}=\{t_1,t_8\}$ with $t_1^{[1]}=t_1$ and $t_2^{[1]}=t_8$ . The set of first-met activity places is ${\Theta }^{[1]}=\{p_2,p_8\}$ with $p_1^{[1]}=p_2$ and $p_2^{[1]}=p_8$ . The first-met shared resource places are $r_1^{[1]}=p_{15}$ and $r_2^{[1]}=p_{20}$ . The first-order transition controller is designed as shown in Figure 4(b). We have $C_1^{[1]}=(\{p_2,p_1,p_{15}\},\{t_{c1}^{[1]}\},F_1^{[1]},W_1^{[1]})$ with $F_1^{[1]}=\{(p_2,t_{c1}^{[1]}),(t_{c1}^{[1]},p_1),(t_{c1}^{[1]},p_{15})\}$ and $W_1^{[1]}(p_2,t_{c1}^{[1]})=W_1^{[1]}(t_{c1}^{[1]},p_1)=W_1^{[1]}(t_{c1}^{[1]},p_{15})=1$ . Similarly, we have $C_2^{[1]}=(\{p_8,p_{14},p_{20}\},t_{c2}^{[1]},F_2^{[1]},W_2^{[1]})$ with $F_2^{[1]}=\{(p_8,t_{c2}^{[1]}),(t_{c2}^{[1]},p_{14}),(t_{c2}^{[1]},p_{20})\}$ and $W_2^{[1]}(p_8,t_{c2}^{[1]})=W_2^{[1]}(t_{c2}^{[1]},p_{14})=W_2^{[1]}(t_{c2}^{[1]},p_{25})=1$ .

To check the termination condition in process I, we have $(r_2^{[1]}{)}^{•}=\{t_6,t_8\}$ and $(p_1^{[1]}{)}^{•}=\{t_2\}$ , and hence $(p_1^{[1]}{)}^{•}\cancel{\subseteq }(r_2^{[1]}{)}^{•}$ . Similarly, for process II, we have $(r_1^{[1]}{)}^{•}=\{t_1,t_{13}\}$ and $(p_2^{[1]}{)}^{•}=\{t_9\}$ , implying $(p_2^{[1]}{)}^{•}\cancel{\subseteq }(r_1^{[1]}{)}^{•}$ . Hence, we need to proceed to the second iteration.

The second-met shared resource places are $r_1^{[2]}=p_{16}$ and $r_2^{[2]}=p_{19}$ . The set of second-met uncontrolled transitions is ${\mathrm{\Pi }}^{[2]}=\{t_2,t_9\}$ with $t_1^{[2]}=t_2$ and $t_2^{[2]}=t_9$ . The set of the second-met activity places is ${\Theta }^{[2]}=\{p_3,p_9\}$ with $p_1^{[2]}=p_3$ and $p_2^{[2]}=p_9$ . The second-order transition controllers for the corresponding second-met uncontrolled transitions are $C_1^{[2]}$ and $C_2^{[2]}$ . $C_1^{[2]}=(\{p_2,p_3,p_{15},p_{16}\},\{t_{c3}^{[2]}\},F_1^{[2]},W_1^{[2]})$ with $F_1^{[2]}=\{(t_{c3}^{[2]},p_2),(p_3,t_{c3}^{[2]}),(p_{15},t_{c3}^{[2]}),(t_{c3}^{[2]},p_{16})\}$ and $W_1^{[2]}(t_{c3}^{[2]},p_2)=W_1^{[2]}(p_3,t_{c3}^{[2]})=W_1^{[2]}$ $(p_{15},t_{c3}^{[2]})=W_1^{[2]}(t_{c3}^{[2]},p_{16})=1$ . Similarly, we have $C_2^{[2]}=(\{p_8,p_9,p_{20},p_{19}\},\{t_{c4}^{[2]}\},F_2^{[2]},W_2^{[2]})$ with $F_2^{[2]}=\{(t_{c4}^{[2]},p_8),(p_9,t_{c4}^{[2]}),(p_{20},t_{c4}^{[2]}),(t_{c4}^{[2]},p_{19})\}$ and $W_2^{[2]}(t_{c4}^{[2]},p_8)=W_2^{[2]}(p_9,t_{c4}^{[2]})=W_2^{[2]}(p_{20},t_{c4}^{[2]})=W_2^{[2]}(t_{c4}^{[2]},p_{19})=1$ .

To check the termination condition in process I, we have $(r_2^{[2]}{)}^{•}=\{t_5,t_9\}$ and $(p_1^{[2]}{)}^{•}=\{t_3\}$ , which implies $(p_1^{[2]}{)}^{•}\cancel{\subseteq }(r_2^{[2]}{)}^{•}$ . It does not satisfy the termination condition. Similarly for process II, we have $(r_1^{[2]}{)}^{•}=\{t_2,t_{12}\}$ and $(p_2^{[2]}{)}^{•}=\{t_{10}\}$ and therefore $(p_2^{[2]}{)}^{•}\cancel{\subseteq }(r_1^{[2]}{)}^{•}$ , which does not satisfy the termination condition. Hence, we need to proceed to the third iteration.

The third-met shared resource places are $r_1^{[3]}=p_{17}$ and $r_2^{[3]}=p_{18}$ . The set of third-met uncontrolled transitions is ${\mathrm{\Pi }}^{[3]}=\{t_3,t_{10}\}$ with $t_1^{[3]}=t_3$ and $t_2^{[3]}=t_{10}$ . The set of the third-met activity places is ${\Theta }^{[3]}=\{p_3,p_{10}\}$ with $p_1^{[3]}=p_3$ and $p_2^{[3]}=p_{10}$ . The third-order transition controllers for the corresponding third-met uncontrolled transitions are $C_1^{[3]}$ and $C_2^{[3]}$ . $C_1^{[3]}$ $=(\{p_2,p_4,p_{15},p_{17}\},\{t_{c5}^{[3]}\},F_1^{[3]},W_1^{[3]})$ with $F_1^{[3]}=\{(t_{c5}^{[3]},p_2),(p_4,t_{c5}^{[3]}),(p_{15},t_{c5}^{[3]}),(t_{c5}^{[3]},p_{17})\}$ and $W_1^{[3]}(t_{c5}^{[3]},p_2)=W_1^{[3]}(p_4,t_{c5}^{[3]})=W_1^{[3]}(p_{15},t_{c5}^{[3]})=W_1^{[3]}(t_{c5}^{[3]},p_{17})=1$ . Similarly, we have $C_2^{[3]}=(\{p_8,p_{10},p_{20},p_{18}\},\{t_{c6}^{[3]}\},F_2^{[3]},W_2^{[3]})$ with $F_2^{[3]}=\{(t_{c6}^{[3]},p_8),(p_{10},t_{c6}^{[3]}),(p_{20},t_{c6}^{[3]}),(t_{c6}^{[3]},p_{18})\}$ and $W_2^{[3]}(t_{c6}^{[3]},p_8)=W_2^{[3]}(p_{10},t_{c6}^{[3]})=W_2^{[3]}(p_{20},t_{c6}^{[3]})=W_2^{[3]}(t_{c6}^{[3]},p_{18})=1$ .

To check the termination condition in process I, we have $(r_2^{[3]}{)}^{•}=\{t_4,t_{10}\}$ and $(p_1^{[3]}{)}^{•}=\{t_4\}$ , which implies $(p_1^{[2]}{)}^{•}\subset (r_2^{[2]}{)}^{•}$ . It satisfies the termination condition. Similarly for process II, we have $(r_1^{[3]}{)}^{•}=\{t_3,t_{11}\}$ and $(p_2^{[3]}{)}^{•}=\{t_{11}\}$ and therefore $(p_2^{[2]}{)}^{•}\subset (r_1^{[2]}{)}^{•}$ , which satisfies the termination condition. Hence, in both processes I and II, the iteration of computing n-met uncontrolled transition terminates.

After adding the third-order transition controllers to the $(N^{C2},M_0^{C2})$ , the plant net $(N^{C3},M_0^{C3})$ is live with all its 1134 markings. The plant net model with all transition controllers to re-enforce liveness is shown in Figure 5(b).

Figure 5.

(a) A plant net with a second transition controller $(N^{C2},M_0^{C2})$ and (b) a plant net with a third transition controller $(N^{C3},M_0^{C3})$ .

Table 3 presents the details of transition controllers to re-enforce liveness of the plant net. Table 4 provides comparison of the proposed method with some existing policies in the literature based on the numbers of control transitions, control arcs, and reachable states.

Table 3.

Summary of transition controllers for a plant net shown in Figure 5(b).

S/N	Constraint	$C_l^{[n]}$	$t_{\mathrm{ci}}^{[n]}$	Pre	Post
1	$p_1+p_2+p_{15}$	$C_1^{[1]}$	$t_{c1}^{[1]}$	$p_2$	$p_1,p_{15}$
2	$p_8+p_{14}+p_{20}$	$C_2^{[1]}$	$t_{c2}^{[1]}$	$p_8$	$p_{14},p_{20}$
3	$p_2+p_3+p_{15}+p_{16}$	$C_1^{[2]}$	$t_{c3}^{[2]}$	$p_3,p_{15}$	$p_2,p_{16}$
4	$p_8+p_9+p_{19}+p_{20}$	$C_2^{[2]}$	$t_{c4}^{[2]}$	$p_9,p_{20}$	$p_8,p_{19}$
5	$p_2+p_4+p_{15}+p_{17}$	$C_1^{[3]}$	$t_{c5}^{[3]}$	$p_4,p_{15}$	$p_2,p_{17}$
6	$p_8+p_{10}+p_{18}+p_{20}$	$C_2^{[3]}$	$t_{c6}^{[3]}$	$p_{10},p_{20}$	$p_8,p_{18}$

Table 4.

Performance comparison of deadlock control policies for the net in Figure 5(b).

Policy	No. of control transitions	No. of control places	No. of control arcs	Total no. of reachable states
Uzam and Zhou 42	−	23	94	396
Huang and Pan 54	−	23	94	396
Huang et al. 50	11	−	78	1318
Proposed method	6	−	22	1318

Example 2

An FMS shown in Figure 6 is from the study of Ezepeleta et al. ¹⁵ that consists of two robots R1 and R2, each of which can hold one part at a time, four machines M1–M4, each of which can process one part at a time, two loading buffers I1 and I2, and two unloading buffers O1 and O2. Two part types are considered in the system that has been studied by researchers.^{8,15,21,27,36,38,42,50,54}

Figure 6.

(a) An FMS layout and (b) its production sequences.

The plant net of this FMS is shown in Figure 7. It has 282 reachable states. The plant net has 19 places and 14 transitions. The places can be considered as the collection of $P_A=\{p_2,p_3,\dots ,p_7,p_9,\dots ,p_{13}\}$ , $P^0=\{p_1,p_8\}$ and $P_R=\{p_{14},p_{15},\dots ,p_{19}\}$ . The plant net has two concurrent processes $(l=2)$ . Note that three resources are shared by the two concurrent processes, and the other three resources are unshared. Then, we have $P_R=R^S\cup R^U$ with $R^S=\{p_{15},p_{18},p_{19}\}$ and $R^U=\{p_{14},p_{16},p_{17}\}$ .

Figure 7.

A plant net of FMS shown in Figure 6.

The set of first-met uncontrolled transitions is ${\mathrm{\Pi }}^{[1]}=\{t_1,t_9\}$ with $t_1^{[1]}=t_1$ and $t_2^{[1]}=t_9$ as both of them can be enabled at the initial marking. Their corresponding set of the first-met activity places is ${\Theta }^{[1]}=\{p_2,p_9\}$ with $p_{t_1}^{[1]}=\{p_2\}$ and $p_{t_9}^{[1]}=\{p_9\}$ . The first-met shared resource places are $r_1^{[1]}=p_{18}$ and $r_2^{[1]}=p_{19}$ . The first-order transition controller associated with the first-met activity place $p_2$ is $C_1^{[1]}=(\{p_2,p_1,p_{18}\},\{t_{c1}^{[1]}\},F_1^{[1]},W_1^{[1]})$ with $F_1^{[1]}=\{(p_2,t_{c1}^{[1]}),(t_{c1}^{[1]},p_1),(t_{c1}^{[1]},p_{18})\}$ and $W_1^{[1]}(p_2,t_{c1}^{[1]})=W_1^{[1]}(t_{c1}^{[1]},p_1)=W_1^{[1]}(t_{c1}^{[1]},p_{18})=1$ . The first-order transition controller associated with the first-met activity place $p_9$ is $C_2^{[1]}=(\{p_8,p_9,p_{19}\},\{t_{c2}^{[1]}\},F_2^{[1]},W_2^{[1]})$ with $F_2^{[1]}=\{(p_9,t_{c2}^{[1]}),(t_{c2}^{[1]},p_8),(t_{c2}^{[1]},p_{19})\}$ and $W_2^{[1]}(p_9,t_{c2}^{[1]})=W_2^{[1]}(t_{c2}^{[1]},p_8)=W_2^{[1]}(t_{c2}^{[1]},p_{19})=1$ . Both controllers $C_1^{[1]}$ and $C_2^{[1]}$ are shown in Figure 8(a).

Figure 8.

(a) A first transition controller with plant net and (b) final transition controllers with plant net.

In the second iteration, the first-met shared resource places are $r_1^{[2]}=p_{15}$ and $r_2^{[2]}=p_{18}$ , and the set of second-met uncontrolled transitions is ${\mathrm{\Pi }}^{[2]}=\{t_2,t_{11}\}$ with $t_1^{[2]}=t_2$ and $t_2^{[2]}=t_{11}$ . While the set of first-met activity places is ${\Theta }^{[2]}=\{p_3,p_{11}\}$ with $p_1^{[2]}=p_3$ and $p_1^{[2]}=p_{11}$ .

The second-order transition controller associated with $p_3$ is designed as $C_1^{[2]}=(\{p_2,p_3,p_{18},p_{15}\},\{t_{c3}^{[2]}\},F_1^{[2]},W_1^{[2]})$ with $F_1^{[2]}=\{(t_{c3}^{[2]},p_2),(p_3,t_{c3}^{[2]}),(p_{18},t_{c3}^{[2]}),(t_{c3}^{[2]},p_{15})\}$ and $W_1^{[2]}(t_{c3}^{[2]},p_2)=W_1^{[2]}(p_3,t_{c3}^{[2]})=W_1^{[2]}(p_{18},t_{c3}^{[2]})=W_1^{[2]}(t_{c3}^{[2]},p_{15})=1$ .

The second-order transition controller associated with $p_{11}$ is $C_2^{[2]}=(\{p_9,p_{11},p_{19},p_{18}\},\{t_{c4}^{[2]}\},F_2^{[2]},W_2^{[2]})$ with $F_2^{[2]}=\{(t_{c4}^{[2]},p_9),(p_{11},t_{c4}^{[2]}),(p_{19},t_{c4}^{[2]}),(t_{c4}^{[2]},p_{18})\}$ and $W_2^{[2]}(t_{c4}^{[2]},p_9)=W_2^{[2]}(p_{11},t_{c4}^{[2]})=W_2^{[2]}(p_{19},t_{c4}^{[2]})=W_2^{[2]}(t_{c4}^{[2]},p_{18})=1$ .

The iteration for computing the uncontrolled transitions terminates after second iterations, as $(r_2^{[2]}{)}^{•}=\{t_1,t_5,t_{11},t_{13}\}$ , $(p_1^{[2]}{)}^{•}=\{t_5\}$ , and $(p_1^{[2]}{)}^{•}\subset (r_2^{[2]}{)}^{•}$ , which shows that the iteration terminates in the first process. Similarly for the second process, $(r_1^{[2]}{)}^{•}=\{t_2,t_{12}\}$ ; $(p_2^{[2]}{)}^{•}=\{t_{12}\}$ and $(p_2^{[2]}{)}^{•}\subset (r_1^{[2]}{)}^{•}$ , which shows that the iteration terminates in the second process. Hence, in both processes, the iterations terminate. When the second transition controllers are added to the plant net $(N^{C1},M_0^{C1})$ , the plant net $(N^{C2},M_0^{C2})$ shown in Figure 8(b) is live with all 282 markings.

Table 5 presents the details of transition controllers to re-enforce liveness of the plant net. Table 6 provides comparison of the proposed method with some existing policies in the literature based on the numbers of control transitions, control arcs, and reachable states.

Table 5.

Summary of transition controllers for a plant net shown in Figure 8(b).

S/N	Constraint	$C_l^{[n]}$	$t_{\mathrm{ci}}^{[n]}$	Pre	Post
1	$p_1+p_2+p_{18}$	$C_1^{[1]}$	$t_{c1}^{[1]}$	$p_2$	$p_1,p_{18}$
2	$p_8+p_9+p_{19}$	$C_2^{[1]}$	$t_{c2}^{[1]}$	$p_9$	$p_8,p_{19}$
3	$p_2+p_3+p_{15}+p_{18}$	$C_1^{[2]}$	$t_{c3}^{[2]}$	$p_3,p_{18}$	$p_2,p_{15}$
4	$p_9+p_{11}+p_{18}+p_{19}$	$C_2^{[2]}$	$t_{c4}^{[2]}$	$p_{11},p_{19}$	$p_9,p_{18}$

Table 6.

Performance comparison of deadlock control policies for the net in Figure 8(b).

Policy	No. of control transitions	No. of control places	No. of control arcs	Total no. of reachable states
Uzam and Zhou 42	−	8	37	205
Pirrodi et al. 36	−	4	39	205
Huang et al. 50	7	−	69	282
Proposed method	4	−	14	282

Example 3

Consider a flexible manufacturing cell shown in Figure 9 from the study of Ezepeleta et al. ¹⁵ It consists of three robots R1–R3, each of which can hold a product at a time. The cell has four machines M1–M4, each of which can process two products at a time. There are three loading buffers I1–I3 and three unloading buffers O1–O3 to load and unload the FMS, respectively. There are three raw product types, namely, P1, P2, and P3, to be processed. For these raw product types, the production cycles are shown in Figure 9(b). According to the production cycles, a raw product P1 is taken from I1 by R1 and put either in M1 or M3. After being processed by M1 (resp. M3) it is then moved from M1 (resp. M3) to M2 (resp. M4) by R2. Finally, after being processed by M2 (resp. M4), it is moved from M2 (resp. M4) to O1 by R3. A raw product P2 is taken from I2 and put in M2 by R2. After being processed by M2, it is moved from M2 to O2 by R2. A raw product P3 is taken from I3 and put in M4 by R3. After being processed by M4 it is then moved from M4 to M3 by R2. Finally, after being processed by M3, it is moved from M3 to O3 by R1.

Figure 9.

(a) An FMS layout and (b) its production sequences.

Figure 10 shows the Petri net model of the system, in which $p_1$ , $p_5$ , and $p_{14}$ are process idle places; $p_2$ , $p_3$ , $p_6$ – $p_{13}$ , $p_{15}$ – $p_{19}$ are activity places; and $p_{20}-p_{26}$ are resource places. Initially, it is assumed that there are no parts in the system. In the model, there are 26 places and 20 transitions. Places $p_6$ , $p_7$ , $p_8$ , $p_9$ , and $p_{10}$ represent the operations of R1, M1, R2, M2, and R3, respectively, for the production sequence of part type P1. Similarly, places $p_6,p_{10},p_{11},p_{12},p_{13}$ represent the operations of R1, M3, R2, M4, and R3, respectively for the production sequence of part type P1. For production sequence of part type P2, places $p_2$ , $p_3$ , and $p_4$ represent the operations of R2, M2, and R2, respectively. For production sequence of part type P3, places $p_{15}-p_{19}$ represent the operations of R3, M4, R2, M3, and R1, respectively. The number of tokens in place $p_1$ is 3, that is, $M_0(p_1)=3$ , that in $p_5$ is 11, that is, $M_0(p_5)=11$ , and that in $p_{14}$ is 7, that is, $M_0(p_{14})=7$ . They represent the numbers of concurrent activities that can take place for part types P1–P3, respectively. Places $p_{23}-p_{26}$ denote the shared resources M1–M4, respectively. Places $p_{20}-p_{22}$ denote the shared resources R1–R4, respectively. Initially, the markings of places $p_{20}-p_{22}$ are all one as each robot can hold one part and those in $p_{23}-p_{26}$ are all two as each machine tool can process two parts at a time.

Figure 10.

A plant net of FMS shown in Figure 9.

The plant net depicted in Figure 10 has 26,750 reachable states. Its activity places can be partitioned to three concurrent processes. The resource places can be partitioned as $P_R=R^U\cup R^S$ with $R^U=\{p_{23}\}$ and $R^S=\{p_{20},p_{21},p_{22},p_{24},p_{25},p_{26}\}$ . The set of first-met uncontrolled transitions is ${\mathrm{\Pi }}^{[1]}=\{t_1,t_{11},t_{15}\}$ with $t_1^{[1]}=t_{11}$ , $t_2^{[1]}=t_1$ , and $t_3^{[1]}=t_{15}$ . The set of first-met activity places is ${\Theta }^{[1]}=\{p_2,p_6,p_{15}\}$ with $p_1^{[1]}=p_2$ , $p_2^{[1]}=p_6$ , and $p_3^{[1]}=p_{15}$ . The first-met shared resources are $r_1^{[1]}=p_{21}$ , $r_2^{[1]}=p_{20}$ , and $r_3^{[1]}=p_{22}$ . The first-order transition controller associated with $p_{21}$ is $C_1^{[1]}=(\{p_2,p_1,p_{21}\},\{t_{c1}^{[1]}\},F_1^{[1]},W_1^{[1]})$ with $F_1^{[1]}=\{(p_2,t_{c1}^{[1]}),(t_{c1}^{[1]},p_1),(t_{c1}^{[1]},p_{21})\}$ and $W_1^{[1]}(p_2,t_{c1}^{[1]})=W_1^{[1]}(t_{c1}^{[1]},p_1)=W_1^{[1]}(t_{c1}^{[1]},p_{21})=1$ . The first-order transition controller associated with $p_{20}$ is $C_2^{[1]}=(\{p_6,p_5,p_{20}\},t_{c2}^{[1]},F_2^{[1]},W_2^{[1]})$ with $F_2^{[1]}=\{(p_6,t_{c2}^{[1]}),(t_{c2}^{[1]},p_5),(t_{c2}^{[1]},p_{20})\}$ and $W_2^{[1]}(p_6,t_{c2}^{[1]})=W_2^{[1]}(t_{c2}^{[1]},p_5)=W_2^{[1]}(t_{c2}^{[1]},p_{20})=1$ . The first-order transition controller associated with $p_{22}$ is $C_3^{[1]}=(\{p_{15},p_{14},p_{22}\},\{t_{c3}^{[1]}\},F_3^{[l]},W_3^{[1]})$ with $F_3^{[1]}=\{(p_{15},t_{c3}^{[1]}),(t_{c3}^{[1]},p_{14}),(t_{c3}^{[1]},p_{22})\}$ and $W_3^{[1]}(p_{15},t_{c3}^{[1]})=W_3^{[1]}(t_{c3}^{[1]},p_{14})=W_3^{[1]}(t_{c3}^{[1]},p_{22})=1$ . The three first-order transition controllers are shown in Figure 11(a).

Figure 11.

(a) A first transition controller and (b) final transitions controllers with plant net.

At the second iteration step, the shared resource places are $r_1^{[2]}=p_{24}$ , $r_{21}^{[2]}=p_{25}$ , $r_{22}^{[2]}=p_{21}$ , and $r_3^{[2]}=p_{26}$ . The set of second-met uncontrolled transitions is ${\mathrm{\Pi }}^{[2]}=\{t_3,t_7,t_{12},t_{16}\}$ with $t_1^{[2]}=t_{12}$ , $t_{21}^{[2]}=t_3$ , $t_{22}^{[2]}=t_7$ , and $t_3^{[2]}=t_{16}$ . The set of second-met activity places is ${\Theta }^{[2]}=\{p_3,p_8,p_{11},p_{16}\}$ with $p_1^{[2]}=p_3$ , $p_{21}^{[2]}=p_8$ , $p_{22}^{[2]}=p_{11}$ , and $p_3^{[2]}=p_{16}$ . The second-order transition controller associated with $p_3$ is $C_1^{[2]}=(\{p_2,p_3,p_{21},p_{24}\},\{t_{c4}^{[2]}\},F_1^{[2]},W_1^{[2]})$ with $F_1^{[2]}=\{(t_{c4}^{[2]},p_2),(p_3,t_{c4}^{[2]}),(p_{21},t_{c4}^{[c2]}),(t_{c4}^{[2]},p_{24})\}$ and $W_1^{[2]}(t_{c4}^{[2]},p_2)=W_1^{[2]}(p_3,t_{c4}^{[2]})=W_1^{[2]}(p_{21},t_{c4}^{[2]})=W_1^{[2]}(t_{c4}^{[2]},p_{24})=1$ .

The second-order transition controller associated with $p_8$ is $C_2^{[2]}=(\{p_6,p_8,p_{20},p_{21}\},\{t_{c5}^{[2]}\},F_2^{[2]},W_2^{[2]})$ with $F_2^{[2]}=\{(t_{c5}^{[2]},p_6),(p_8,t_{c5}^{[2]}),(p_{20},t_{c5}^{[2]}),(t_{c5}^{[2]},p_{21})\}$ and $W_2^{[2]}(t_{c5}^{[2]},p_6)=W_2^{[2]}(p_8,t_{c5}^{[2]})=W_2^{[2]}(p_{20},t_{c5}^{[2]})=W_2^{[2]}(t_{c5}^{[2]},p_{21})=1$ .

The second-order transition controller associated with $p_{11}$ is $C_3^{[2]}=(\{p_6,p_{11},p_{20},p_{25}\},\{t_{c6}^{[2]}\},F_3^{[2]},W_3^{[2]})$ with $F_3^{[2]}=\{(t_{c6}^{[2]},p_6),(p_{11},t_{c6}^{[2]}),(p_{20},t_{c6}^{[2]}),(t_{c6}^{[2]},p_{25})\}$ and $W_3^{[2]}(t_{c6}^{[2]},p_6)=W_3^{[2]}(p_{11},t_{c6}^{[2]})=W_3^{[2]}(p_{20},t_{c6}^{[2]})=W_3^{[2]}(t_{c6}^{[2]},p_{25})=1$ .

The second-order transition controller is associated with $p_{16}$ is $C_4^{[2]}=(\{p_{15},p_{16},p_{22},p_{26}\},\{t_{c7}^{[2]}\},F_4^{[2]},W_4^{[2]})$ with $F_4^{[2]}=\{(t_{c7}^{[2]},p_{15}),(p_{16},t_{c7}^{[2]}),(p_{22},t_{c7}^{[2]}),(t_{c7}^{[2]},p_{26})\}$ and $W_4^{[2]}(t_{c7}^{[2]},p_{15})=W_4^{[2]}(p_{16},t_{c7}^{[2]})=W_4^{[2]}(p_{22},t_{c7}^{[2]})=W_4^{[2]}(t_{c7}^{[2]},p_{26})=1$ .

Before we proceed to next iteration, we need to check the termination condition in the processes. For process I, we have $(r_{21}^{[2]}{)}^{•}=\{t_3,t_8,t_{11},t_{13},t_{17}\}$ , $(p_1^{[2]}{)}^{•}=\{t_{13}\}$ , and $(p_1^{[2]}{)}^{•}\subset (r_{21}^{[2]}{)}^{•}$ . It shows that there is no uncontrolled transition and the iteration terminates for process I. For process II, we have $(r_1^{[2]}{)}^{•}=\{t_4,t_{12}\}$ , $(p_{21}^{[2]}{)}^{•}=\{t_4\}$ , and $(p_{21}^{[2]}{)}^{•}\subset (r_1^{[2]}{)}^{•}$ . Similarly, we have $(r_{21}^{[2]}{)}^{•}=\{t_3,t_8,t_{11},t_{13},t_{17}\}$ , $(p_{22}^{[2]}{)}^{•}=\{t_8\}$ , and $(p_{22}^{[2]}{)}^{•}\subset (r_{21}^{[2]}{)}^{•}$ . This means that the iteration terminates for process II. For process III, we have $(r_{21}^{[2]}{)}^{•}=\{t_3,t_8,t_{11},t_{13},t_{17}\}$ ; $(p_3^{[2]}{)}^{•}=\{t_{17}\}$ and $(p_3^{[2]}{)}^{•}\subset (r_{21}^{[2]}{)}^{•}$ . This implies that the iteration terminates for process III. The iteration terminates after the second iteration.

When the second-order controllers are added to the plant net, we obtain a net system $(N^{C2},M_0^{C2})$ shown in Figure 11(b) which is live with all its 26,750 reachable markings. Table 7 provides the final transition controllers together with its incidence relationships, while Table 8 provides the comparison of the results obtained by the proposed method with some of the existing results available in the literature.

Table 7.

Summary of transition controllers for a net in Figure 11(b).

S/N	Constraint	$C_l^{[n]}$	$t_{\mathrm{ci}}^{[n]}$	Pre	Post
1	$p_1+p_2+p_{21}$	$C_1^{[1]}$	$t_{c1}^{[1]}$	$p_2$	$p_1,p_{21}$
2	$p_5+p_6+p_{20}$	$C_2^{[1]}$	$t_{c2}^{[1]}$	$p_6$	$p_5,p_{20}$
3	$p_{14}+p_{15}+p_{22}$	$C_3^{[1]}$	$t_{c3}^{[1]}$	$p_{15}$	$p_{14},p_{22}$
4	$p_2+p_3+p_{21}+p_{24}$	$C_1^{[2]}$	$t_{c4}^{[2]}$	$p_3,p_{21}$	$p_2,p_{24}$
5	$p_6+p_8+p_{20}+p_{21}$	$C_2^{[2]}$	$t_{c5}^{[2]}$	$p_8,p_{20}$	$p_6,p_{21}$
6	$p_{15}+p_{16}+p_{22}+p_{26}$	$C_3^{[2]}$	$t_{c6}^{[2]}$	$p_{16},p_{22}$	$p_{15},p_{26}$
7	$p_6+p_{11}+p_{20}+p_{25}$	$C_4^{[2]}$	$t_{c7}^{[2]}$	$p_{11},p_{20}$	$p_6,p_{25}$

Table 8.

Performance comparison of deadlock control policies for a plant net shown in Figure 11(b).

Policy	No. of control transitions	No. of control places	No. of control arcs	Total no. of reachable states
Pirrodi et al. 36	−	13	83	21,581
Uzam and Zhou 55	−	17	101	21,562
Chao 48	−	7	79	26,750
Huang et al. 50	20	−	80	26,750
Proposed method	7	−	25	26,750

Discussion

The proposed method can be applied to the M-nets which are more general than almost all manufacture-oriented Petri net subclasses in the literature. Specifically, this method can be applied to system of simple sequential processes with resources (S³PR) Petri net, linear system of simple sequential process with resources (LS³PR) Petri net, simple sequential processes with weighted resources allocation (WS³PR) Petri net, systems of sequential systems with shared resources (S⁴R) Petri net, system of sequential systems with shared resources (S⁴PR) Petri net, extended from systems of simple sequential processes with resources (ES³PR) Petri net, S³PMR Petri net (a subclass of weighted Petri nets), and G-systems Petri net. In the proposed method, we have considered three different subclasses of Petri net as seen in the experimental examples. The Petri net model used to demonstrate the proposed method belongs to an LS³PR Petri net; the Petri net model used in Example 1 belongs to WS ³ PR Petri net, while both Examples 2 and 3 belong to S³PR Petri net. In the Petri nets considered, the proposed method works effectively in the enforcement of liveness to the Petri net model for FMSs.

Suppose that there are $\omega$ concurrent processes in $(N,M_0)$ with $N=(P_A\cup P^0\cup P_R,T,F)$ . Obviously, $\omega$ is less than the structural size of net $N$ . We have two nested loops in Algorithm 1 to search the first-met uncontrolled transitions in $(N,M_0)$ . The first while loop is executed $\omega$ times such that it can visit each process in $(N,M_0)$ , while in the worst case the for loop is executed $|P_A|$ times to find the first-met uncontrolled transitions (i.e. when $|I_r|=|P_A|$ , where $r\in P_R$ is a resource place). Note that $|P_A|<|P|$ . The overall computational complexity of Algorithm 1 (finding first-met uncontrolled transitions in $(N,M_0)$ ) is $\mathcal{O}(\omega |P|)$ . However, in general, the worst case is almost unlikely to occur, since the active uncontrolled transitions can be usually found at the first iteration. ⁵³

For Algorithm 2, we have only one go loop that would be executed $n$ times such that at each time it can visit each process in $(N,M_0).$ Hence, the computational complexity of Algorithm 2 at the worst case is $\mathcal{O}(n\omega )$ . Note that $n$ is the number of times of the iteration before it meets the termination condition. For Algorithm 3, it has only one for loop that can be executed $|\Omega |$ times, where $|\Omega |<|T|$ . Hence, its computational complexity is $\mathcal{O}(|\Omega |)$ . In summary, the proposed method in this article has polynomial time complexity.

Conclusion

This article proposes three algorithms. The first and second algorithms are used to compute first-met and n-met uncontrolled transitions for a class of Petri nets modeling FMSs, respectively, and the third algorithm is used to design a transition controller for each uncontrolled transition obtained by Algorithms 1 and 2. The purposes of the transition controllers are to make the uncontrolled transitions controlled and to ensure the final plant net is live with its all reachable markings being preserved, as contained in the uncontrolled plant net. The proposed method is efficient as it provides a minimal supervisory structure, compared with the existing methods available in the literature. In terms of computational overheads, the proposed method is much more efficient as it uses only structural properties of the plant net, avoiding a complete enumeration of reachable states, which usually leads to the state explosion problem.

The proposed method involves iterative procedures. At each iteration, there is a need to check the termination condition for the computation of uncontrolled transitions, which may limit the speed of the computation. The future work would focus on how to guarantee the absence of redundant control transitions in the supervisory structure.