Sage Journals: Discover world-class research

Abstract

This article proposes an iterative deadlock resolution method for flexible manufacturing systems modeled with G-systems. To design a non-blocking controlled system with maximally permissive behavior in a G-system (GS), a reachability graph-based analysis technology is utilized. Since the reachability graph of a large-scale GS easily becomes unmanageable, an optimal non-blocking supervisor becomes a challenging problem in a GS. To facilitate this problem, the Divide-and-Conquer approach is a good choice for complex G-systems. First, an uncontrolled GS resolves into a number of associated subnets. Then, every subnet suffering from deadlocks is utilized to design the liveness-enforcing supervisor for the original GS. Thus, additional monitors can be obtained if the liveness of all subnets is achieved. Subsequently, a partially controlled GS is derived by including all monitors within the GS, and its liveness can be ensured by designing a new set of monitors. Consequently, a non-blocking GS is derived. The major advantage of the proposed method is that a non-blocking supervisor with near-optimal behavioral permissiveness can be obtained in general. Finally, a typical GS example popularly studied in the literature is applied to demonstrate the validity and the availability of the method in this article.

Keywords

Petri net deadlock prevention divide-and-conquer reachability graph

Introduction

The survivability of a manufacturing system to a large extent depends on its capability to swiftly respond to the variable market requirements, leading to the emergence and development of flexible manufacturing systems (FMSs) that can produce multiple product types with a small batch. An FMS is a conglomeration of computer numerically controlled machine tools, buffers, fixtures, robots, automated guided vehicles (AGV), and other material-handling devices. It usually exhibits a high degree of resource sharing in order to increase flexibility such that market changes can be responded quickly. Deadlocks are a constant threat to the continuous run of an FMS. They always block a system which even leads to catastrophic results in highly automated manufacturing systems. In order to optimize dynamic performance of a system, it is thereof necessary to explore an effective and computationally efficient mechanism such that deadlocks can never occur. Over the last two decades, a great deal of researches has focused on solving deadlock problems in FMS, leading to significant results in theory and successful industrial applications.^1–7

Above all, Petri nets have been proven to be very useful in dealing with deadlock problems due to their natural ability on describing and analyzing the behavioral properties of an FMS. Generally, Petri net-based deadlock resolution methods can be classified into three strategies. They are deadlock detection and recovery,^8,9 deadlock avoidance,^10,11 and deadlock prevention.^12–18 Deadlock detection and recovery is an optimistic strategy that grants a resource to a request as long as the resource is available. A deadlock detection algorithm is used to detect the occurrence of deadlocks. Once a deadlock is detected, a recovery mechanism is initialized by aborting one or more processes involved in the deadlock and the resources held by the aborted processes are relinquished. In the deadlock avoidance approach, at each system state, an online control policy is used to determine the correct system evolution among the feasible ones. Some aggressive deadlock avoidance policies do not eliminate all deadlock states. As for the deadlock prevention method, an off-line computational mechanism is usually established before the control implementation of a net system. Specially, the deadlock prevention approach always prevents a system from reaching deadlocks by adding external monitors. Deadlock prevention is considered to be one of the most effective methods in deadlock control.^19–25

The analysis techniques of Petri nets used to deal with deadlocks in FMSs can be usually classified into two categories: structural objects and reachability graph (RG). Falling into the former category, a number of deadlock control policies can be developed based on the special structural objects of a Petri net model (PNM), that is, siphons, which are well recognized to be tied with deadlocks in either ordinary or generalized Petri nets.^26–34 The deadlock control policies can be achieved by adding monitors to the original PNM. Generally, there are three very important criteria in evaluating the performance of a liveness-enforcing supervisor (LES) for a system to be controlled: behavioral permissiveness, structural complexity, and computational complexity. Many researchers have developed a great number of siphon-based deadlock control policies in order to achieve LESs with maximal permissiveness, simple supervisory structure, and low computational complexity. Especially, behavioral permissiveness plays the most important role in evaluating the performance of an LES. A maximally permissive, that is, optimal, supervisor always means all legal markings are kept in the controlled system. In this case, the utilization of system resources has the minimal limitation. However, supervisors obtained using siphon-based control methods in generalized Petri nets are not optimal, or even overly restrictive and conservative, from the behavioral permissiveness standpoint.^35–37

As for the latter, the utilization of this technique can always lead to an optimal or a near-optimal supervisor with high behavioral permissiveness.^38–41 A representative work on the design of optimal Petri net supervisors is the theory of regions.⁴² The work by Uzam⁴³ proposes an approach to design optimal Petri net supervisors using the theory of regions. It establishes a connection between transition systems and Petri nets through net synthesis. The idea behind the theory of regions is that a state-based model, a model describing which states a process can be in and which transitions are possible between these states, can be transformed into a Petri net, a compact representation of the state space, explicitly showing causality, concurrency, and conflicts between transitions. Its appearance is followed by a large amount of research aiming to develop optimal deadlock prevention policies.^44–46 Shortly after the work in Uzam,⁴³ using popular and plain linear algebra, Ghaffari et al.⁴⁴ explore the condition on the existence of an optimal monitor-based liveness-enforcing Petri net supervisor and develop a methodology to synthesize such a supervisor. However, it bears much computational cost. In such an approach, one first needs to generate the RG given a plant PNM. Then, the set of marking/transition separation instances (MTSI) is calculated. Finally, for each instance, a monitor is computed by solving a linear programming problem in which the number of constraints is approximately equal to that of nodes in the RG. Another RG-based deadlock prevention method was proposed by Uzam and Zhou,⁴⁶ which does not require complex computations for obtaining the monitors. The method proposed in Uzam and Zhou⁴⁶ is an iterative deadlock prevention approach. Deadlocks can be eliminated effectively by preventing the firing of transitions enabled at a first-met bad marking (FBM)’s father marking such that the FBM is unreachable. In general, the work in Uzam and Zhou⁴⁶ presents a simple and effective method. However, the size of the RG was the only problem for applying such an approach to very large-scale Petri nets since it suffers from the problem that the computation of RG is necessary at each iteration step. Due to the notorious state explosion, the scalability issue always impedes the acceptance of current methods despite their theoretical appeal.

To develop a computationally efficient method of the LES for a large-scale FMS, the RG-based deadlock control methods must be further improved. One of the most interesting directions is to segment a global system into some subsystems, and the additional monitors can be first computed for the subsystems and then merged into the set of monitors included in the global system. To achieve this, the work in Uzam et al.⁴⁷ presents a Divide-and-Conquer (D-C) strategy in designing the LES from subsystems for a large-scale system. Motivated by the seminal work in Uzam et al.,⁴⁷ this article intends to extend the D-C strategy to the synthesis of an optimal non-blocking supervisor for a more general Petri nets, called G-systems (GS). To obtain the non-blocking supervisor for a complex GS, the G-system GS is divided into some smaller subnets. The set of monitors is computed only for those connected subnets with deadlocks such that the liveness of all related subnets can be ensured. By computing the RG of each subnet suffering from deadlocks, a dead-zone (DZ) and a live-zone (LZ) can be derived by splitting its RG. All reachable states in DZ are removed with respect to the simplified place invariant (PI)-based control method.⁴⁵ Note that the set of additional monitors is computed in an iterative way, that is, the earlier calculations of monitors may be contained within the latter subnets. Therefore, the DZ of the latter subnet is more smaller than its original subnet. The iterative process will terminate till all subnets are live. After that, we get a partially controlled G-system (PCGS) and sequentially compute monitors for the PCGS. In the end, a non-blocking G-system is obtained. The proposed method makes it possible to design non-blocking supervisor for a complex G-system when the RG of the PNM is big.

The remainder of the article is organized as follows. Section “Motivation of deadlock prevention policy for G-systems” outlines the motivation of the proposed deadlock prevention method for G-systems. Section “An iterative D-C synthesis approach for deadlock prevention in G-systems” develops an iterative deadlock prevention policy for G-systems and also provides a G-system example with two job processes to illustrate the applicability of the proposed policy. In section “A case study,” a typical case study from the literature is provided to show the validity and universality of the proposed method, and comparison study among different control methods and some discussion are made accordingly. The final section “Conclusion” concludes the article.

Motivation of deadlock prevention policy for G-systems

Some preliminaries related to Petri nets definitions used throughout this article can be referred to Li and Zhou.⁴⁸ Without loss of generality, we consider the most general classes of Petri nets as an example in this work, called G-systems, which are the most general processing-oriented class of generalized Petri net in the literature. A G-system can well model an FMS with process flexibility, assembly and disassembly operations, assignment flexibility, and permutation flexibility, whose corresponding definitions are depicted as Zhao and Hou.⁴⁹

As is well known, for most general classes of Petri nets, G-systems, a variety of deadlock prevention policies are developed based on structural analysis, that is, siphon control. However, the siphon-based control policies for G-systems are of exponential complexity due to a complete or partial siphon enumeration.^50,51 Furthermore, the behavioral permissiveness problem is referred to as the fact that permissive behavior is overly restricted by the siphon-based control policies, that is to say, the supervisor excludes some safe (admissible) states. This is so since the output arcs of a monitor are led to the source transitions of the net model, which limits the number of workpieces being released into and processed by the system. Consequently, the approaches derived from siphon control are in general not optimal, or even overly restrictive and conservative, from the behavioral permissiveness standpoint.

In order to design maximally permissive supervisors for generalized Petri nets, RG analysis is a reliable, accurate, and effective (surely not efficient) method of a Petri net, although it is computationally expensive. Based on the theory of regions, Uzam and Zhou develop an iterative deadlock prevention approach.⁴⁶ It is assumed that there is a monitor solution to the deadlock prevention for a plant net model. The RG is divided into two parts: LZ and deadlock zone. A LZ is in fact the maximal strongly connected component that contains the initial marking. A deadlock zone contains markings from which the initial marking is unreachable. An FBM is defined in the deadlock zone. It does not satisfy live control requirements and its father node is in the LZ. Then, deadlocks can be eliminated by preventing the firing of the transitions enabled at an FBM’s father marking such that the FBM is unreachable. It is shown that the transition firing control can be converted into a generalized mutual exclusion constraint (GMEC) problem that can be implemented by a monitor whose computation is highly efficient. However, the approach in Uzam and Zhou⁴⁶ suffers from the state explosion problem when enumerating all reachable states in a sizable net model. Moreover, at each iteration step, one needs to compute the RG once. In order to circumvent this problem, it is necessary to seek a strategy that optimizes computational complexity, structural complexity, and behavioral permissiveness.

The D-C approach is a significant design paradigm in computer science to develop computationally efficient algorithms. When considering the RG-based deadlock resolution methods for a complex FMS, it is a really good option for improving the computational efficiency. Based on this mind, the work in Uzam and Zhou⁴⁶ first introduces the D-C approach, which divides a PNM into smaller subsystems and then carries out the monitors computation for the subsystems. Finally, the set of all monitors is added to the complex system. Then, Li et al.⁵² propose a D-C method to prevent deadlocks for a class of ordinary Petri nets, called S³PR. Using the structural object of Petri nets, that is, resource circuits, a PNM is split into three strategies, which are idle subnet, autonomous subnet, and connected subnets. An LES, called a toparch, is designed for each connected subnet. If a particular separation condition holds in a PNM, the computational overhead of toparches is significantly reduced. This research shows that the resulting net by composing the toparches derived for the connected subnets can serve as an LES for the whole plant model. It has been claimed in Li et al.⁵² that D-C-based deadlock control method is computationally superior compared with some global-conquer deadlock control policies such as Uzam and Zhou⁴⁶ and Ezpeleta et al.⁵³

To inherit and reserve the advantages of RG analysis in a complex FMS, this work proposes a deadlock prevention method for G-system by utilizing the D-C strategy. To obtain the non-blocking supervisor for a structurally complicated G-system GS, the global system model is first split into a few of smaller connected subnets. Based on the place-invariant (PI) control methods, monitors (control places) are added for every deadlocked subnet. In order to obtain as many as reachable states, the RG analysis is used to generate the state space of all subnets, which can be divided into good markings, dangerous markings, bad markings (BMs), and deadlock markings. The two former belongs to the LZ, and the two latter are included in the DZ. All states in the DZ must be excluded from the state space in terms of the simplified PI-based control method proposed by Uzam and Zhou.⁴⁵ Starting with the simplest subnet, monitors are computed to make the subnet live. Note that the computation of additional monitors and related arcs is a gradual process started with smaller subnets. The further calculation of the bigger subnets contains all monitors in previous iterations. Obviously, the DZ of the bigger subsystem by running the iterative process is smaller than that of in the original subsystem. When the computational iterations of all subsystems are completed, a set of monitors and a PCGS are obtained. After that, we add a number of new monitors for the PCGS to enforce its liveness. Consequently, a non-blocking controlled G-system, called CGS, is derived. The following section presents an iterative algorithm of deadlock control method for G-systems in detail.

An iterative D-C synthesis approach for deadlock prevention in G-systems

As the results stated previously, when an uncontrolled G-system is considered, the RG analysis technique is very useful in designing an optimal non-blocking supervisor. Obviously, the set of legal markings of the RG represents the optimal permissive behavior of the controlled system. Therefore, to obtain an optimal supervisor, an effective deadlock control policy should be established by excluding the DZ from the RG, while reserving all legal markings within LZ. To achieve this purpose, the theory of regions has been used for a PNM with respect to its RG. However, the computation of RG in a very complex net system cannot be carried out using the global-conquer methods as in Zhao and colleagues.^51,54 In order to improve the computational efficiency of the supervisor, this section develops a D-C-based deadlock control algorithm for G-systems. At first, the definition of non-blockingness in a G-system is depicted as follows:

Definition 1

A G-system GS is well-formed if there exists an initial marking $M_{S_{0}}$ such that $\forall M \in R (N_{S}, M_{S_{0}})$ , $M_{S_{F}} \in R (N_{S}, M)$ , where $M_{S_{0}}$ and $M_{S_{F}}$ denote the initial marking and the final marking of $N_{S}$ , respectively.

Definition 2

A G-system $(N_{S}, M_{S_{0}}, M_{S_{F}})$ is non-blocking if $\forall M \in R (N_{S}, M_{S_{0}})$ , there exists a sequence of transitions $σ$ such that $M [σ 〉 M_{S_{F}}$ holds.⁴⁹

Remark 1

Note that the concepts of liveness and non-blockingness are totally different. Given a Petri net $(N, M_{0})$ , it is deadlock-free if $\forall M \in R (N, M_{0})$ , $\exists t \in T$ such that $M [t 〉$ holds. $(N, M_{0})$ is live if $\forall t \in T$ , t is live at $M_{0}$ . This definition is widely used in the deadlock control and analysis area of Petri nets. Note that a live Petri net guarantees deadlock-freedom no matter what firing sequence is chosen but the converse in not true. Therefore, deadlock resolution methods mainly aim to obtain an LES for a PNM prone to deadlocks. As for the concept of non-blockingness, it is originally defined based on the theory of automata and formal language. Actually, in the frame of Petri nets, there is no standard definition of non-blockingness of deadlock control in the existing literatures. In the article, Definition 2 first gives its formal definition for the most general class of Petri nets, called G-systems. Note that the non-blockingness is an important property of a controlled G-system, which indicates that the system can always reach a final marking from any reachable state. In particular, the net structure of a G-system GS is different with that of other generalized Petri nets classes. Since a G-task GT is circuit-free, that is, it is inadmissible to have loops in a G-task. As a result, a G-system GS is not strongly connected. To analyze the liveness of the given G-system, its corresponding augmented G-system GS* is then defined by adding transition $t^{*}$ , which leads to a strongly connected G-system. Thus, it can be concluded that a controlled G-system is non-blocking if $\forall M \in R (N_{S}, M_{S_{0}})$ , the controlled system can always reach the final marking $M_{S_{F}}$ , which indicates that all resources are released and all job parts are completed and stored in sink places. By considering the definition of an augmented net, if a well-formed G-system $(N_{S}, M_{S_{0}}, M_{S_{F}})$ is non-blocking, its augmented G-system is live since every G-task $(N_{j}, M_{0_{j}}, M_{F_{j}})$ in GS is augmented by adding $t_{j}^{*}$ such that $N_{j}^{*}$ with $o_{j}^{•} =^{•} i_{j} = {t_{j}^{*}}$ and $W (o_{j}, t_{j}^{*}) = W (t_{j}^{*}, i_{j}) = n$ is strongly connected.⁴⁹ In a word, the liveness of an augmented G-system is equivalent to the non-blockingness of its original well-formed G-system GS.

As is well known, three kinds of places are defined in a G-system, which are resource places, operation places, and source/sink places. The first one represents all system resources of a G-system. Generally, a number of tokens are placed in resource places initially, which describes the number of available capacity. Operation places represent an action to produce a part in a processing sequence by a resource such as machines, robots, and so on. Note that there are no tokens initially in those places. The tokens in each source place describe the maximal number of concurrent job parts that can possibly take place in a processing route. In a cyclic model, the function of a sink place is the same as the source place and vice versa. Therefore, to simplify the structural analysis of the G-system net model, a sink place and a source place in a cyclic process are usually merged into an idle place.

Example 1

The net shown in Figure 1(a) is a G-system, where source places and sink places are $i_{1} = p_{8}$ , $o_{1} = p_{9}$ , $i_{2} = p_{13}$ , and $o_{2} = p_{14}$ . The net contains two job processes $P_{A 1} = {p_{1} - p_{7}}$ and $P_{A 2} = {p_{10} - p_{12}}$ . The corresponding augmented net system is obtained by adding transitions $t_{1}^{*}$ and $t_{2}^{*}$ with ${}^{•}{i_{1}} = {o_{1}}^{•} = {t_{1}^{*}}$ , ${}^{•}{i_{2}} = {o_{2}}^{•} = {t_{2}^{*}}$ . By merging the sink places and source places of the two processes, we have two idle places $P_{0} = {p_{8}, p_{13}}$ . Furthermore, we have $M_{0} (p_{8}) = 8$ and $M_{0} (p_{13}) = 8$ . Figure 1(b) is the corresponding simplified G-system with three shared resource (SR) places $P_{R} = {p_{15}, p_{16}, p_{17}}$ , which results in three resource P-invariants: $I_{p 15} = 2 p_{1} + p_{12} + p_{15}$ , $I_{p_{16}} = p_{2} + p_{6} + p_{11} + p_{16}$ , and $I_{p_{17}} = p_{3} + p_{4} + p_{7} + p_{10} + p_{17}$ . Note that $M_{0} (p_{15}) = M_{0} (p_{16}) = 2$ (resp. $M_{0} (p_{17}) = 3$ ) hold, which represent that $p_{15}$ and $p_{16}$ (resp. $p_{17}$ ) can process two parts (resp. three parts) simultaneously. The RG analysis of the net system is carried out by INA.⁵⁵ It can be verified that the net is pure, bounded, and prone to deadlock. Moreover, there are 1090 reachable states in RG, where LZ contains 1057 good states (GSs), and DZ includes 33 bad states. To achieve the optimal solution of the controlled system, the proposed policy should design a non-blocking G-system with 1057 legal markings.

Figure 1.

(a) A G-system net $(N, M_{0})$ with source/sink places and (b) the G-system net with simplified idle places.

When considering a large-scale G-system net model, the G-system is first divided into some smaller connected subnets such that the following RG computation can be simplified. Specially, each connected subnet consists of SR places with their corresponding input and output transitions and related connected arcs. In addition, operation places with their input and output arcs presented among those transitions of SR places should be included in the connected subnet. Subsequently, the formal definition of connected subnet $S N_{i}$ is listed in detail.

Definition 3

Let $P_{R} = \cup_{i = 1}^{m} P_{R}^{i}$ be the set of SR places in a PNM $N = (P_{A} \cup P_{R} \cup P_{0}, T, F, W)$ . If $P^{i} = P_{R}^{i} \cup {p \in P_{A} | p \in ∥ I_{r} ∥, r \in P_{R}^{i}}$ and $T^{i} = \cup_{p \in P^{i}} (^{•} p \cup p^{•})$ , where $i = {1, 2, \dots, m}$ , then the net generated by $X = P^{i} \cup T^{i}$ is called a connected subnet denoted by $S N_{i}$ , where $S N_{i} = (P^{i}, T^{i}, F_{X}, W_{X})$ .

In theory, the number of possible connected subnets equals to $2^{m} - 1$ , where m is the number of SR places. Next, we should check whether the idle places must be included in the subnets or not. Property 1 shows the condition that all subnets may exclude the idle places in a G-system.

Property 1

Let $P_{0} = {p_{i}^{0}}$ be the set of idle places in a G-system $(N_{S}, M_{S_{0}}, M_{S_{F}})$ , and $p_{A_{1}}, p_{A_{2}}, \dots, p_{A_{n}}$ be a set of operation places related with the idle place $p_{i}^{0}$ . Idle place $p_{i}^{0}$ is said to be structurally unnecessary in the construction of connected subnets if the initial marking of the source place $p_{i}^{0}$ is greater than or equal to the sum of token capacities of all operation places related with $p_{i}^{0}$ , that is, $M_{0} (p_{i}^{0}) ⩾ M_{C} (p_{A_{1}}) + M_{C} (p_{A_{2}}) + \dots + M_{C} (p_{A_{n}})$ , where $M_{C}$ denotes the maximal number of tokens in an operation place.

Example 2

First of all, let us check the necessity of the idle places $p_{8}$ and $p_{13}$ in the construction of subnets. We have $M_{0} (p_{8}) = 8$ , $M_{C} (p_{1}) = 2$ , $M_{C} (p_{2}) + M_{C} (p_{6}) = 2$ , $M_{C} (p_{3}) + M_{C} (p_{4}) + M_{C} (p_{7}) = 3$ , then $M_{0} (p_{8}) > M_{C} (p_{1}) + M_{C} (p_{2}) + M_{C} (p_{6}) + M_{C} (p_{3}) + M_{C} (p_{4}) + M_{C} (p_{7})$ . Similarly, we have $M_{0} (p_{13}) = 8$ , $M_{C} (p_{10}) = 3$ , $M_{C} (p_{11}) = 2$ , $M_{C} (p_{12}) = 2$ , then $M_{0} (p_{13}) > M_{C} (p_{10}) + M_{C} (p_{11}) + M_{C} (p_{12})$ . Therefore, it can be concluded that $p_{8}$ and $p_{13}$ are unnecessary in the construction of connected subnets.

When all connected subnets are derived from Definition 3 for an uncontrolled G-system, the RG analysis is used to compute the set of subnets suffering with deadlocks. Meanwhile, the LZ and DZ of those subnets are obtained. In order to implement the liveness of those connected subnets, all states in DZ should be removed according to the PI-based control method.⁴⁵ Specially, the purpose of the control policy is to prevent all BMs of the subset from being reached. Each BM related to operation places can be described as a PI in the G-system, the sum of tokens in PI has to be at most one less than their current value within the BM such that the BM is unreachable. Generally, each PI can be achieved by adding a control place and its connected arcs. Based on the RG of those connected subnets, monitors are computed to make all connected subnets live.

Subsequently, the controller computation method is presented based on PI control method, where the control specification on an uncontrolled G-system can be formulated by the following form

l^{T} M ⩽ b

(1)

where M means a marking vector while l and b are integer constants. To achieve it, a monitor V should be imposed on the net system according to the following equations

M_{0} (V) = b - l_{p}^{T} M_{0} (P_{A})

(2)

[N_{V}] = - l_{p}^{T} [N_{p}]

(3)

where $M_{0} (V)$ is the initial marking of the monitor V, $M_{0}$ is the initial marking of the PNM, and $l_{p}$ is an integer constant representing the invariant-related operation places. Actually, it is known that at initial marking of the PNM, the operation places have no tokens. Therefore, equation (2) can be modified as $M_{0} (V) = b$ . In equation (3), $N_{V}$ is the monitor row matrix representing the connection of monitor to the transitions, and $[N_{p}]$ is the incidence matrix of the PI-related net.

Notation 1

Let $[S N_{k}]_{op}$ be the set of operation places within the connected subnet $S N_{k}$ . Let $[PI]_{mop}$ be the set of marked operation places in a PI, which represents a bad state within a DZ.

Consequently, in order not to reach a BM $M_{B}$ , the PI is defined as $\sum_{p \in {[PI]}_{mop}} M (p) ⩽ \sum_{p \in P_{A}} M (p) - 1$ , where M denotes any reachable marking in GS. Next, the D-C iterative algorithm in designing a non-blocking supervisor for a G-system is summarized as follows.

Remark 2

The first step of Algorithm 1 is to divide a whole net model into a number of connected subnets due to Definition 3. Note that the number of connected subnets is closely related to the sets of SRs and resource circuits. For those connected subnets including more than one resource, there must exist the resource circuit simultaneously. That is to say, those unconnected resources cannot derive connected subnets. Therefore, the numbers of SR places and resource circuits in a PNM are the decisive factor of connected subnets in the actual computation. Although there are $2^{m} - 1$ possible connected subnets in theory, the fewer connected subnets may be obtained since the number of resource circuits is generally less than that of resource places. Second, all subnets suffering from deadlocks should be derived, and their corresponding RGs are also computed. After that, all BMs in the DZ must be forbidden using PI-based control method. Note that the concept of the minimal covered sets of FBMs is utilized such that the computation cost for each PI can be reduced, which leads to the fewer additional monitors. When all iterations are finished, the redundant verification of additional monitors is carried out. Subsequently, the non-blocking controlled G-system can be derived with all necessary monitors.

Algorithm 1.

Non-blocking Supervisor Design for a G-system Using D-C Synthesis Method.

Input: a G-system $GS = (N_{S}, M_{S_{0}}, M_{F_{0}})$ , where $N_{S} = (P_{0} \cup P_{A} \cup P_{R}, T, F \cup F_{R}, W \cup W_{R})$

Output: a non-blocking controlled system $CGC = (N^{c}, M_{0}^{c}, M_{F}^{c})$

1: begin;

2: Obtain the set of subnets $S N_{ij}$ by dividing the given G-system GS, where $i = {1, \dots, m}$ is the index value related to the shared resources in a connected subnet, and m is the number of system resources. Note that $j = {1, \dots, n}$ is the index value of the current ith connected subnet, and n is the number of current ith connected subnets.

3: $S N_{L} : = \emptyset$ ; $S N_{D} : = \emptyset$ . ( $S N_{L}$ is defined as the set of connected live subnets, while $S N_{D}$ is defined as the set of subnets suffering from deadlocks).

4: for ( $i = 1$ ; $i ⩽ m$ ; $i + +$ ) do

5: for ( $j = 1$ ; $j ⩽ n$ ; $j + +$ ) do

6: Extract the connected subnet $S N_{ij}$ from the given G-system, and compute the $R G_{ij}$ of connected subnet $S N_{ij}$ ;

7: if The net $S N_{ij}$ is live then

8: $S N_{L} : = S N_{L} \cup S N_{ij}$ .

9: else

10: $S N_{D} : = S N_{D} \cup S N_{ij}$ .

11: end if

12: end for

13: end for

14: Rename the set of connected subnets with deadlocks as $S N_{D} = {S N_{1}, S N_{2}, \dots, S N_{K}}$ and their corresponding $RG = {R G_{1}, R G_{2}, \dots, R G_{K}}$ , and compute $[S N_{k}]_{op}$ , where $k = {1, \dots, K}$ .

15: $C_{k} : = \emptyset$ ; $C : = \emptyset$ . ( $C_{k}$ and C are defined as the set of additional monitors for subnet $S N_{k}$ and GS, respectively.)

16: for ( $k = 1$ ; $k ⩽ K$ ; $k + +$ )do

17: if ( $C_{k} \neq \emptyset$ & $[PI]_{mop} \subseteq [S N_{k}]_{op}$ ) then

18: Add all previously computed monitors within $S N_{k}$ that satisfies $[PI]_{mop} \subseteq [S N_{k}]_{op}$ , and derive the partially controlled $S N_{k}$ , namely $PCS N_{k}$ , and then compute the $R G_{k}$ of $PCS N_{k}$ .

19: if The net $PCS N_{k}$ is not live then

20: Define the $L Z_{k}$ and the $D Z_{k}$ of the $R G_{k}$

21: end if

22: else

23: Make use of the $R G_{k}$ together with its $L Z_{k}$ and $D Z_{k}$ computed in Step 14.

24: end if

25: Find the minimal covered set $M_{B}^{*} = {M_{B_{1}}, M_{B_{2}}, \dots, M_{B_{l}}}$ of all bad markings $M_{B}$ within the $D Z_{k}$ based on the method in Chen et al.³⁸

26: for ( $i = 1$ ; $i ⩽ l$ ; $i + +$ ) do

27: Define a $P I_{i}$ for each $M_{B_{i}}$ ;

28: Add the monitor $V_{i}$ for each $P I_{i}$ using the simplified PI-based method proposed in Uzam and Zhou.⁴⁵

29: $C_{k} : = C_{k} \cup V_{i}$ .

30: end for

31: Derive the live subnet $CS N_{k}$ with all additional monitors for $S N_{k}$ , within $PCS N_{k}$ (resp. $S N_{k}$ ); $C : = C \cup C_{k}$ .

32: end for

33: Obtain the partially controlled GS with the set of monitors C, denoted as PCGS,

34: Compute the RG of the PCGS.

35: if PCGS is not live then

36: Define the LZ and the DZ of the PCGS.

37: Find the minimal covered set $M_{B}^{*} = {M_{B_{1}}, M_{B_{2}}, \dots, M_{B_{q}}}$ of all bad markings $M_{B}$ within the DZ.

38: for ( $j = 1$ ; $j ⩽ q$ ; $j + +$ ) do

39: Define a $P I_{j}$ for each $M_{B_{j}}$ .

40: Design the monitor $V_{j}$ for each $P I_{j}$ using the PI-based method in Uzam and Zhou.⁴⁵

41: $C : = C \cup V_{j}$ .

42: end for

43: Carry out the redundancy identification of monitors C by utilizing the method in Uzam et al.⁵⁶

44: Obtain the non-blocking controlled GS, denoted as CGS, by including all necessary monitors C.

45: end if

46: Output the non-blocking controlled system $CGS = (N^{c}, M_{0}^{c}, M_{F}^{c})$ , where $N^{c} = (P_{0} \cup P_{A} \cup P_{R} \cup C, T, F \cup F_{R} \cup F_{C}, W \cup W_{R} \cup W_{C})$ .

47: end.

Example 3

Now let us utilize Algorithm 1 to design a non-blocking supervisor for the uncontrolled net shown in Figure 1(b).

Step 1: The G-system shown in Figure 1(b) is divided into connected subnets based on its SRs. Since there are three ( $m = 3$ ) SR places, we could get $2^{m} - 1 = 7$ possible connected subnets in theory. Actually, we can have fewer connected subnets. For this G-system, five connected subnets are derived. Specifically, there are three connected subnets with one SR as shown in Figure 2, which are named as $S N_{11}$ , $S N_{12}$ , and $S N_{13}$ , respectively. Furthermore, two connected subnets with two SRs can also be computed as shown in Figure 3, which are named as $S N_{21}$ and $S N_{22}$ , respectively.

Step 2: By analyzing the liveness of each connected subnets $S N_{ij}$ , the sets of live connected subnets $S N_{L}$ and connected subnets prone to deadlocks $S N_{D}$ are obtained, where $S N_{L} = {S N_{11}, S N_{12}, S N_{13}}$ and $S N_{D} = {S N_{21}, S N_{22}}$ . Note that $S N_{21}$ and $S N_{22}$ are renamed as $S N_{1}$ and $S N_{2}$ , respectively. The RG of $S N_{1}$ consists of 34 reachable states, with $M_{B_{1}}$ constituting the DZ₁ and 33 GSs representing the LZ₁. By computing RG₁ of $S N_{1}$ , there are 34 reachable states in RG₁, where LZ₁ contains 33 GSs, and DZ₁ consists of 1 bad state. Similarly, the RG₂ of $S N_{2}$ consists of 340 reachable states, with 337 GSs representing the LZ₂ and 3 bad states constituting the DZ₂. The set of operation places exist in the connected subnet $S N_{1}$ and $S N_{2}$ are shown in Table 1.

Step 3: Next, additional monitors are designed for each connected subnet in $S N_{D}$ based on PI control method.

For $S N_{1}$ , a BM $M_{B_{1}}$ is obtained with $M_{B_{1}} = p_{1} + p_{11}$ , and we have $M_{B_{1}} (p_{1}) = 1$ , $M_{B_{1}} (p_{11}) = 2$ , and $[PI]_{mop} = {p_{1}, p_{11}}$ . In order not to reach $M_{B_{1}}$ , a P-invariant $P I_{1}$ is established as $P I_{1} = M (p_{1}) + M (p_{11}) ⩽ 2$ . Consequently, the monitor $V_{1}$ is designed to implement $P I_{1}$ , where we have ${}^{•}{V_{1}} = {t_{2}, t_{6}, t_{11}}$ , $V_{1}^{•} = {t_{1}, t_{10}}$ , and $M_{0}^{c} (V_{1}) = 2$ . Thus, the partially controlled system $PCS N_{1}$ of the subnet $S N_{1}$ is obtained with the monitor $V_{1}$ . It can be verified that $PCS N_{1}$ is live with 33 GSs. It indicates that the net $PCS N_{1}$ provides the maximally permissive behavior for the subnet $S N_{1}$ .

For $S N_{2}$ , there are three bad states constituting the DZ₂. The minimal covered set of all BMs is obtained as $M_{B}^{*} = {M_{B_{2}}} = p_{2} + p_{6} + p_{10}$ . In order not to reach $M_{B_{2}}$ , $P I_{2}$ is computed as follows: $P I_{2} = M (p_{2}) + M (p_{6}) + M (p_{10}) ⩽ 4$ . To enforce $P I_{2}$ , a monitor $V_{2}$ is then computed with ${}^{•}{V_{2}} = {t_{3}, t_{7}, t_{10}}$ , $V_{2}^{•} = {t_{2}, t_{6}, t_{9}}$ , and $M_{0}^{c} (V_{2}) = 4$ . Similarly, the controlled $S N_{2}$ with the additional monitor $V_{2}$ , denoted as $PCS N_{2}$ , has 337 GSs. It can be concluded that the net $PCS N_{2}$ is also a live subnet with optimal behavior.

The PCGS with monitors $V_{1}$ and $V_{2}$ mentioned above is then obtained. The RG of the PCGS contains 1059 reachable states, where DZ includes 2 bad states and LZ consists of 1057 GSs. After that, the minimal covered set of all BMs is then derived as $M_{B}^{*} = {M_{B_{3}}, M_{B_{4}}}$ , and we have $M_{B_{3}} = p_{1} + p_{2} + p_{10} + p_{11}$ and $M_{B_{4}} = p_{1} + p_{6} + p_{10} + p_{11}$ . Therefore, two P-invariants are established as $P I_{3} = M (p_{1}) + M (p_{2}) + M (p_{10}) + M (p_{11}) ⩽ 5$ and $P I_{4} = M (p_{1}) + M (p_{6}) + M (p_{10}) + M (p_{11}) ⩽ 5$ such that $M_{B_{3}}$ and $M_{B_{4}}$ cannot be reached, respectively. Hence, two monitors $V_{3}$ and $V_{4}$ are computed as follows: ${}^{•}{V_{3}} = {t_{3}, t_{6}, t_{11}}$ , $V_{3}^{•} = {t_{1}, t_{9}}$ , $M_{0}^{c} (V_{3}) = 5$ ; ${}^{•}{V_{4}} = {t_{2}, t_{7}, t_{11}}$ , $V_{4}^{•} = {t_{1}, t_{9}}$ , and $M_{0}^{c} (V_{4}) = 5$ .

Step 4: Finally, the controlled G-system with additional monitors $V_{3}$ and $V_{4}$ for PCGS is then derived, which is denoted as CGS. It can be verified that the net CGS is non-blocking, and the final supervisor shown in Table 2 has 1057 GSs. In addition, the non-blocking control procedure of the G-system GS is briefly depicted in Table 3. The results show that the non-blocking controlled system CGS has maximally behavioral permissiveness.

Figure 2.

Three connected subnets with one shared resource of the system in Figure 1(b): (a) SN₁₁. (b) SN₁₂, and (c) SN₁₃.

Figure 3.

Two connected subnets with two shared resources of the system in Figure 1(b): (a) SN₂₁(SN₁) and (b) SN₂₂(SN₂).

Table 1.

Set of operation places existing in the connected subnets $S N_{1}$ and $S N_{2}$ .

Subnet	$p_{1}$	$p_{2}$	$p_{3}$	$p_{4}$	$p_{5}$	$p_{6}$	$p_{7}$	$p_{10}$	$p_{11}$	$p_{12}$
$S N_{1}$	1	1	0	0	1	1	0	0	1	1
$S N_{2}$	0	1	1	1	0	1	1	1	1	0

Table 2.

Monitors added for the G-system in Figure 1(b) by the proposed method.

$V_{i}$	${}^{•}{V_{i}}$	$V_{i}^{•}$	$M_{0} (V_{i})$
$V_{1}$	$t_{2}$ , $t_{6}$ , $t_{11}$	$t_{1}$ , $t_{10}$	2
$V_{2}$	$t_{3}$ , $t_{7}$ , $t_{10}$	$t_{2}$ , $t_{6}$ , $t_{9}$	4
$V_{3}$	$t_{3}$ , $t_{6}$ , $t_{11}$	$t_{1}$ , $t_{9}$	5
$V_{4}$	$t_{2}$ , $t_{7}$ , $t_{11}$	$t_{1}$ , $t_{9}$	5

Table 3.

Non-blocking design procedure for the G-system in Figure 1(b).

Nets	Included monitor $C_{i}$	Computed monitor $C_{i}$	Reachable states
$S N_{1}$	–	$V_{1}$	33
$S N_{2}$	–	$V_{2}$	337
PCPNM	$V_{1}$ , $V_{2}$	$V_{3}$ , $V_{4}$	1057
G-system model	$V_{1} - V_{4}$	–	1057

The non-blocking supervisor obtained by the proposed method is near-optimal. In this article, “optimal supervisor” is used as a synonym for “maximally permissive supervisor.” A maximally permissive supervisor always implies high coefficient utilization of SRs. In general, the reachable states in LZ of a PNM can be viewed as a “quality metric.” Therefore, the highest quality can be provided in terms of the optimal control policies. In this sense, the proposed method is a good choice for designing an optimal supervisor. Since G-systems are the most general net models in the literature, a G-system is referred to as a PNM of an FMS in this article. For a bound G-system, the RG analysis of G-systems can be carried out by INA⁵⁵ that can provide both LZ and DZ. The DZ is regarded as the collection of all BMs for each connected subnet. According to Algorithm 1, if all BMs in RG are forbidden, implying that the controlled system is live since it cannot enter DZ anymore.

Theorem 1

Algorithm 1 can always terminate in a finite number of steps for a bounded G-system, and its termination gives a non-blocking supervisor and a controlled system $(N^{c}, M_{0}^{c}, M_{F}^{c})$ .

Proof

As is well known, a BM was main incentive of deadlock in an uncontrolled net system. If all BMs are eliminated and no new bad states are generated in the resulting controlled system $(N^{c}, M_{0}^{c}, M_{F}^{c})$ , the LES can be finally derived. Consequently, the non-blocking controlled system is then obtained according to the relationship between liveness and non-blockingness. When given an uncontrolled G-system, an uncontrolled connected subnets and uncontrolled GS can be derived due to Algorithm 1, in order to ensure all BMs being eliminated in those nets, we design PIs to them, that is, monitors are added such that all live connected subnets and controlled GS are derived. Note that all PIs are marked with the number of tokens less than the sum of tokens in all marked operation places at the selected BM. In other words, it is impossible to reach BMs and other equal markings at the BM under those PI conditions. Furthermore, there exist no new BMs in the RG due to these PI constraints. After all BMs are eliminated for a bounded G-system, Algorithm 1 will terminate. According to aforementioned results, all BMs are eliminated and no new BMs are generated. Consequently, we can conclude that the supervised system has no deadlock state, implying that the liveness of controlled system $(N^{c}, M_{0}^{c}, M_{F}^{c})$ is ensured. Furthermore, from Definition 2, we conclude that the resulting controlled system $(N^{c}, M_{0}^{c}, M_{F}^{c})$ is non-blocking.

Remark 3

The RG analysis is an effective approach that can derive a maximally permissive supervisor for a PNM by adding monitors if such a supervisor exists. When there exists an optimal solution in a Petri net, a BM is optimally controlled if none of the good markings in the RG is removed. Unfortunately, since the coefficient of each PI equals 1, some legal markings may be forbidden when the related monitor is added to forbid the selected BM.³⁸ In this case, the maximally permissive supervisor cannot be obtained. Therefore, the proposed method cannot lead to the controlled system with maximally permissive behavior in a G-system. That is to say, the computed monitors may not allow some GSs to be reached when disabling the bad ones in an uncontrolled G-system. However, it is appealing to design a “near-optimal” supervisor, implying that the most number of legal markings are kept after adding monitors. In the practical applications, a lot of examples have been verified, overwhelming majority of which can obtain a high performance by the proposed method. Due to the limited space, we could not present all examples here. In this article, two experimental G-systems show that the supervisors are a near-optimal with high behavioral permissive. Meanwhile, the computational cost is reduced greatly by comparing with some RG-based global-conquer methods.

Theorem 2

Given a G-system $GS = (N_{S}, M_{S_{0}}, M_{F_{0}})$ , where $N_{S} = (P_{0} \cup P_{A} \cup P_{R}, T, F \cup F_{R}, W \cup W_{R})$ , Algorithm 1 for the computation of its controlled system $CGS = (N^{c}, M_{0}^{c}, M_{F}^{c})$ , where $N^{c} = (P_{0} \cup P_{A} \cup P_{R} \cup C, T, F \cup F_{R} \cup F_{C}, W \cup W_{R} \cup W_{C})$ , is of exponential time complexity.

Proof

In theory, the number of reachable states in RG is exponential with the size of PNM. Since the RG generation of a given G-system GS is necessary at each iteration step in Algorithm 1, the computational complexity of Algorithm 1 is exponential.

Remark 4

Although the computational complexity of the proposed method is exponential, it is faster than the traditional global-conquer approaches to compute a RG and has been used widely in deadlock prevention policies.

A case study

In this section, a typical case study is presented to demonstrate the effectiveness and availability of the proposed method in an FMS. First, a G-system example is considered to illustrate the design steps in detail. Then, the performance comparison of non-blocking supervisors is made among different deadlock control polices in Li and Zhao³⁷ and Zhao and Hou,⁴⁹ and some discussion is also given subsequently.

A G-system example

Now a benchmark example is used to illustrate deadlock control polices presented in this article. An FMS as shown in Figure 4 consists of two robots R1 and R2, each of which can hold three parts every time, and four machines M1–M4, each of which can process two or three parts at the same time. Parts enter the system through three loading buffers I1–I3, and leave the system through three unloading buffers O1–O3. Three part types J1–J3 are produced.

R1 handles part movements from I1 to M1, M1 to M2, M2 to M1, and M1 to O1.

R2 handles part movements from M2 to M3, M3 to O1, I2 to M3, M3 to M2, I3 to M4, and M4 to O3.

M1 performs operations on J1 and J2.

M2 performs operations on J1 and J2.

M3 performs operations on J1 and J2.

M4 performs operations on J2 and J3.

Figure 4.

An FMS layout.

Figure 5(a) shows the net model of the FMS that may use a multi-set of resources at a work processing step. The net system is a G-system that contains three processes $J_{1}$ , $J_{2}$ , and $J_{3}$ with $J_{1} = {p_{1} - p_{7}}$ , $J_{2} = {p_{12} - p_{16}}$ , and $J_{3} = {p_{8} - p_{10}}$ . There are three source places $i_{1} (p_{18})$ , $i_{2} (p_{17})$ , and $i_{3} (p_{11})$ , three sink places $o_{1} (p_{19})$ , $o_{2} (p_{21})$ , and $o_{3} (p_{20})$ , where $M_{0} (p_{11}) = 4$ , $M_{0} (p_{17}) = 9$ , and $M_{0} (p_{18}) = 10$ . The number of tokens in source places represents the number of concurrent activities that can take place for parts types J1–J3. There are six resource places $P_{R} = {p_{22} - p_{27}}$ with $M_{0} (p_{22}) = 2$ , $M_{0} (p_{23}) = 2$ , $M_{0} (p_{24}) = 2$ , $M_{0} (p_{25}) = 3$ , $M_{0} (p_{26}) = 3$ , and $M_{0} (p_{27}) = 3$ . Places $p_{23}$ , $p_{24}$ , $p_{25}$ , $p_{27}$ , $p_{22}$ , and $p_{26}$ denote M1, M2, M3, M4, R1, and R2, respectively. The augmented net is strongly connected after adding three transitions $t_{1}^{*}$ , $t_{2}^{*}$ , and $t_{3}^{*}$ , respectively. The uncontrolled G-system in Figure 5(a) is not live. The RG of the uncontrolled system can be computed by INA, which shows “Memory Exhausted.” To simplify the structural analysis of the net model in Figure 5(a), the sink place and the source place in the same process can be merged into an idle place. The G-system net with simplified idle places is shown in Figure 5(b).

Figure 5.

(a) A G-system net $(N, M_{0})$ and (b) the G-system net $(N, M_{0})$ with simplified idle places.

Now let us utilize Algorithm 1 to design an optimal or a near-optimal non-blocking supervisor for the G-system shown in Figure 5(b). The RG of the uncontrolled G-system model has 68,531 states, whose DZ contains 2131 bad states, and LZ includes 66,400 GSs.

First, there are six ( $n = 6$ ) SR places. This means that when we divide this PNM into subnets based on SRs, in theory, we could get $2^{n} - 1 = 2^{6} - 1 = 63$ possible connected subnets, but it turns out that we have fewer connected subnets. There are 35 connected subnets obtained from this net model shown in Tables 4 –8. As shown in Table 4, there are six connected subnets with only one SR: $S N_{11}$ , $S N_{12}$ , $S N_{13}$ , $S N_{14}$ , $S N_{15}$ , and $S N_{16}$ . As shown in Table 5, there are eight connected subnets with two SRs: $S N_{21}, S N_{22}, \dots, S N_{28}$ . As shown in Table 6, there are eight connected subnets with three SRs: $S N_{31}, S N_{32}, \dots, S N_{38}$ . As shown in Table 7, there are eight connected subnets with four SRs: $S N_{41}, S N_{42}, \dots, S N_{48}$ . Moreover, there are five connected subnets with five SRs shown in Table 8, namely $S N_{51}, S N_{52}, \dots, S N_{55}$ , respectively.

Table 4.

Connected subnets with one shared resource for the net system in Figure 5(b).

Subnet	Places set	Transitions set	Live or not
$S N_{11}$	$p_{1}$ , $p_{5}$ , $p_{16}$ , $p_{22}$	$t_{1}$ , $t_{2}$ , $t_{6}$ , $t_{17}$ , $t_{18}$	Live
$S N_{12}$	$p_{1}$ , $p_{5}$ , $p_{15}$ , $p_{23}$	$t_{1}$ , $t_{2}$ , $t_{6}$ , $t_{16}$ , $t_{17}$	Live
$S N_{13}$	$p_{2}$ , $p_{6}$ , $p_{14}$ , $p_{24}$	$t_{2}$ , $t_{3}$ , $t_{6}$ , $t_{7}$ , $t_{15}$ , $t_{16}$	Live
$S N_{14}$	$p_{4}$ , $p_{12}$ , $p_{13}$ , $p_{25}$	$t_{4}$ , $t_{5}$ , $t_{8}$ , $t_{13}$ , $t_{14}$ , $t_{15}$	Live
$S N_{15}$	$p_{3}$ , $p_{7}$ , $p_{8}$ , $p_{10}$ , $p_{13}$ , $p_{26}$	$t_{3}$ , $t_{4}$ , $t_{7}$ , $t_{8}$ , $t_{9} - t_{12}$ , $t_{14}$ , $t_{15}$	Live
$S N_{16}$	$p_{4}$ , $p_{8}$ , $p_{9}$ , $p_{27}$	$t_{4}$ , $t_{5}$ , $t_{8} - t_{11}$	Live

Table 5.

Connected subnets with two shared resources for the net system in Figure 5(b).

Subnet	Places set	Transitions set	Live or not
$S N_{21}$	$p_{1}$ , $p_{5}$ , $p_{15}$ , $p_{16}$ , $p_{22}$ , $p_{23}$	$t_{1}$ , $t_{2}$ , $t_{6}$ , $t_{16} - t_{18}$	Live
$S N_{22}$	$p_{1}$ , $p_{2}$ , $p_{5}$ , $p_{6}$ , $p_{14}$ , $p_{16}$ , $p_{22}$ , $p_{24}$	$t_{1} - t_{3}$ , $t_{6}$ , $t_{7}$ , $t_{15} - t_{18}$	Live
$S N_{23}$	$p_{1}$ , $p_{2}$ , $p_{5}$ , $p_{6}$ , $p_{14}$ , $p_{15}$ , $p_{23}$ , $p_{24}$	$t_{1}$ , $t_{2}$ , $t_{3}$ , $t_{6}$ , $t_{7}$ , $t_{15}$ , $t_{16}$ , $t_{17}$	Not live
$S N_{24}$	$p_{2}$ , $p_{4}$ , $p_{6}$ , $p_{12} - p_{14}$ , $p_{24}$ , $p_{25}$	$t_{2} - t_{8}$ , $t_{13} - t_{16}$	Live
$S N_{25}$	$p_{2}$ , $p_{3}$ , $p_{6} - p_{8}$ , $p_{10}$ , $p_{13}$ , $p_{14}$ , $p_{24}$ , $p_{26}$	$t_{2} - t_{4}$ , $t_{6} - t_{8}$ , $t_{9} - t_{12}$ , $t_{14} - t_{16}$	Not live
$S N_{26}$	$p_{3}$ , $p_{4}$ , $p_{7}$ , $p_{8}$ , $p_{10}$ , $p_{12}$ , $p_{13}$ , $p_{25}$ , $p_{26}$	$t_{3} - t_{5}$ , $t_{7} - t_{12}$ , $t_{13} - t_{15}$	Not live
$S N_{27}$	$p_{4}$ , $p_{8}$ , $p_{9}$ , $p_{12}$ , $p_{13}$ , $p_{25}$ , $p_{27}$	$t_{4}$ , $t_{5}$ , $t_{8} - t_{11}$ , $t_{13} - t_{15}$	Live
$S N_{28}$	$p_{3}$ , $p_{4}$ , $p_{7} - p_{10}$ , $p_{13}$ , $p_{26}$ , $p_{27}$	$t_{3} - t_{5}$ , $t_{7} - t_{12}$ , $t_{14}$ , $t_{15}$	Live

Table 6.

Connected subnets with three shared resources for the net system in Figure 5(b).

Subnet	Places set	Transitions set	Live or not
$S N_{31}$	$p_{1}$ , $p_{2}$ , $p_{5}$ , $p_{6}$ , $p_{14} - p_{16}$ , $p_{22} - p_{24}$	$t_{1} - t_{3}$ , $t_{6}$ , $t_{7}$ , $t_{15} - t_{18}$	Not live
$S N_{32}$	$p_{1}$ , $p_{2}$ , $p_{4} - p_{6}$ , $p_{12} - p_{14}$ , $p_{16}$ , $p_{22}$ , $p_{24}$ , $p_{25}$	$t_{1} - t_{8}$ , $t_{13} - t_{16}$ , $t_{17}$ , $t_{18}$	Live
$S N_{33}$	$p_{1} - p_{3}$ , $p_{5} - p_{8}$ , $p_{10}$ , $p_{13}$ , $p_{14}$ , $p_{16}$ , $p_{22}$ , $p_{24}$ , $p_{26}$	$t_{1} - t_{4}$ , $t_{6} - t_{12}$ , $t_{14} - t_{18}$	Not live
$S N_{34}$	$p_{1}$ , $p_{2}$ , $p_{4} - p_{6}$ , $p_{12} - p_{15}$ , $p_{23} - p_{25}$	$t_{1} - t_{8}$ , $t_{13} - t_{17}$	Not live
$S N_{35}$	$p_{1} - p_{3}$ , $p_{5} - p_{8}$ , $p_{10}$ , $p_{13} - p_{15}$ , $p_{23}$ , $p_{24}$ , $p_{26}$	$t_{1} - t_{4}$ , $t_{6} - t_{12}$ , $t_{14} - t_{17}$	Not live
$S N_{36}$	$p_{2} - p_{4}$ , $p_{6} - p_{8}$ , $p_{10}$ , $p_{12} - p_{14}$ , $p_{24} - p_{26}$	$t_{2} - t_{16}$	Not live
$S N_{37}$	$p_{2}$ , $p_{4}$ , $p_{6}$ , $p_{8}$ , $p_{9}$ , $p_{12} - p_{14}$ , $p_{24}$ , $p_{25}$ , $p_{27}$	$t_{2} - t_{11}$ , $t_{13} - t_{16}$	Live
$S N_{38}$	$p_{3}$ , $p_{4}$ , $p_{7} - p_{10}$ , $p_{12}$ , $p_{13}$ , $p_{25} - p_{27}$	$t_{3} - t_{5}$ , $t_{7} - t_{15}$	Not live

Table 7.

Connected subnets with four shared resources for the net system in Figure 5(b).

Subnet	Places set	Transitions set	Live or not
$S N_{41}$	$p_{1}$ , $p_{2}$ , $p_{4} - p_{6}$ , $p_{12} - p_{16}$ , $p_{22} - p_{25}$	$t_{1} - t_{8}$ , $t_{13} - t_{18}$	Not live
$S N_{42}$	$p_{1} - p_{3}$ , $p_{5} - p_{8}$ , $p_{10}$ , $p_{13} - p_{16}$ , $p_{22} - p_{24}$ , $p_{26}$	$t_{1} - t_{4}$ , $t_{6} - t_{12}$ , $t_{14} - t_{18}$	Not live
$S N_{43}$	$p_{1} - p_{8}$ , $p_{10}$ , $p_{12} - p_{14}$ , $p_{16}$ , $p_{22}$ , $p_{24} - p_{26}$	$t_{1} - t_{18}$	Not live
$S N_{44}$	$p_{1}$ , $p_{2}$ , $p_{4} - p_{6}$ , $p_{8}$ , $p_{9}$ , $p_{12} - p_{14}$ , $p_{16}$ , $p_{22}$ , $p_{24}$ , $p_{25}$ , $p_{27}$	$t_{1} - t_{11}$ , $t_{13} - t_{18}$	Live
$S N_{45}$	$p_{1} - p_{8}$ , $p_{10}$ , $p_{12} - p_{15}$ , $p_{23} - p_{26}$	$t_{1} - t_{17}$	Not live
$S N_{46}$	$p_{1}$ , $p_{2}$ , $p_{4} - p_{6}$ , $p_{8}$ , $p_{9}$ , $p_{12} - p_{15}$ , $p_{23} - p_{25}$ , $p_{27}$	$t_{1} - t_{11}$ , $t_{13} - t_{17}$	Not live
$S N_{47}$	$p_{1} - p_{10}$ , $p_{13} - p_{15}$ , $p_{23}$ , $p_{24}$ , $p_{26}$ , $p_{27}$	$t_{1} - t_{12}$ , $t_{14} - t_{17}$	Not live
$S N_{48}$	$p_{2} - p_{4}$ , $p_{6} - p_{10}$ , $p_{12} - p_{14}$ , $p_{24} - p_{27}$	$t_{2} - t_{16}$	Not live

Table 8.

Connected subnets with five shared resources for the net system in Figure 5(b).

Subnet	Places set	Transitions set	Live or not
$S N_{51}$	$p_{1} - p_{8}$ , $p_{10}$ , $p_{12} - p_{16}$ , $p_{22} - p_{26}$	$t_{1} - t_{18}$	Not live
$S N_{52}$	$p_{1}$ , $p_{2}$ , $p_{4} - p_{6}$ , $p_{8}$ , $p_{9}$ , $p_{12} - p_{16}$ , $p_{22} - p_{25}$ , $p_{27}$	$t_{1} - t_{11}$ , $t_{13} - t_{18}$	Not live
$S N_{53}$	$p_{1} - p_{10}$ , $p_{13} - p_{16}$ , $p_{22} - p_{24}$ , $p_{26}$ , $p_{27}$	$t_{1} - t_{12}$ , $t_{14} - t_{18}$	Not live
$S N_{54}$	$p_{1} - p_{10}$ , $p_{12} - p_{14}$ , $p_{16}$ , $p_{22}$ , $p_{24} - p_{27}$	$t_{1} - t_{18}$	Not live
$S N_{55}$	$p_{1} - p_{10}$ , $p_{12} - p_{15}$ , $p_{23} - p_{27}$	$t_{1} - t_{17}$	Not live

From above results, we obtain 35 connected subnets from this net model. After computing RG_ij of above 35 connected subnets $S N_{ij}$ , we have: $S N_{L} = {S N_{11}, S N_{12}, S N_{13}, S N_{14}, S N_{15}, S N_{16}, S N_{21}, S N_{22}, S N_{24}, S N_{27}, S N_{28}, S N_{32}, S N_{37}, S N_{44}}$ , and there are 21 connected subnets are not live, that is, $S N_{D} = {S N_{23}, S N_{25}, S N_{26}, S N_{31}, S N_{33}, S N_{34}, S N_{35}, S N_{36}, S N_{38}, S N_{41}, S N_{42}, S N_{43}, S N_{45}, S N_{46}, S N_{47}, S N_{48}, S N_{51}, S N_{52}, S N_{53}, S N_{54}, S N_{55}}$ . Note that those connected subnets in $S N_{D}$ which are renamed as $S N_{1}, S N_{2}, \dots, S N_{21}$ , respectively. By analyzing the reachable states set of those subnets in $S N_{D}$ , the number of states in the RG, DZ, and LZ of $S N_{D}$ are shown in Table 9. The set of SR places exist within the connected subnets $S N_{1}, S N_{2}, \dots, S N_{21}$ are all shown in Table 10.

Table 9.

Reachability graph analysis of the subnets in $S N_{D}$ .

States	$S N_{1}$	$S N_{2}$	$S N_{3}$	$S N_{4}$	$S N_{5}$	$S N_{6}$	$S N_{7}$	$S N_{8}$	$S N_{9}$	$S N_{10}$	$S N_{11}$
States in RG	57	556	456	128	3336	1140	3160	4511	559	2560	7072
States in DZ	1	3	4	1	18	20	69	81	8	20	84
States in LZ	56	553	452	127	3318	1120	3091	4238	551	2540	6988
States	$S N_{12}$	$S N_{13}$	$S N_{14}$	$S N_{15}$	$S N_{16}$	$S N_{17}$	$S N_{18}$	$S N_{19}$	$S N_{20}$	$S N_{21}$
States in RG	27,066	25,596	2964	13,100	5466	57,172	6656	29,152	32,796	30,862
States in DZ	486	858	52	294	153	1303	52	384	918	1286
States in LZ	26,580	24,738	2912	12,806	4985	55,869	6604	28,768	31,878	29,576

Table 10.

Set of shared resources constituting the subnets prone to deadlocks.

Subnets	$p_{22}$	$p_{23}$	$p_{24}$	$p_{25}$	$p_{26}$	$p_{27}$	Subnets	$p_{22}$	$p_{23}$	$p_{24}$	$p_{25}$	$p_{26}$	$p_{27}$
$S N_{1}$	0	1	1	0	0	0	$S N_{2}$	0	0	1	0	1	0
$S N_{3}$	0	0	0	1	1	0	$S N_{4}$	1	1	1	0	0	0
$S N_{5}$	1	0	1	0	1	0	$S N_{6}$	0	1	1	1	0	0
$S N_{7}$	0	1	1	0	1	0	$S N_{8}$	0	0	1	1	1	0
$S N_{9}$	0	0	0	1	1	1	$S N_{10}$	1	1	1	1	0	0
$S N_{11}$	1	1	1	0	1	0	$S N_{12}$	1	0	1	1	1	0
$S N_{13}$	0	1	1	1	1	0	$S N_{14}$	0	1	1	1	0	1
$S N_{15}$	0	1	1	0	1	1	$S N_{16}$	0	0	1	1	1	1
$S N_{17}$	1	1	1	1	1	0	$S N_{18}$	1	1	1	1	0	1
$S N_{19}$	1	1	1	0	1	1	$S N_{20}$	1	0	1	1	1	1
$S N_{21}$	0	1	1	1	1	1

For clarity, all BMs in DZ and PIs are derived for all connected subnets $S N_{1} - S N_{21}$ by utilizing the simplified PI control method in Uzam and Zhou,⁴⁵ which are presented in Table 11. Moreover, the redundancy test of all computed monitors is carried out by utilizing the method in Uzam et al.⁵⁶ It can be verified that $V_{1}, V_{2}, \dots, V_{11}$ are all necessary. Consequently, the controlled G-system is obtained by including computed necessary monitors $V_{1}, V_{2}, \dots, V_{11}$ within the G-system as shown in Table 12. It can be concluded that the controlled G-system with $V_{1}, V_{2}, \dots, V_{11}$ is non-blocking and has 62,682 GSs. This means that the permissiveness of the controlled model is $62, 682 / 66, 400 = 94.40 %$ . Table 13 briefly shows the non-blockingness enforcing procedure applied for the G-system model.

Table 11.

Place invariants computed for all bad markings of the G-system in Figure 5(b).

$M_{B_{i}}$	$P I_{i}$
$M (p_{1}) = 2$ , $M (p_{14}) = 2$	$M (p_{1}) + M (p_{14}) ⩽ 3$
$M (p_{2}) = 1$ , $M (p_{6}) = 1$ , $M (p_{13}) = 3$	$M (p_{2}) + M (p_{6}) + M (p_{13}) ⩽ 4$
$M (p_{3}) = 2$ , $M (p_{7}) = 1$ , $M (p_{12}) = 3$	$M (p_{3}) + M (p_{7}) + M (p_{12}) ⩽ 5$
$M (p_{1}) = 2$ , $M (p_{2}) = 1$ , $M (p_{13}) = 3$ , $M (p_{14}) = 1$	$M (p_{1}) + M (p_{2}) + M (p_{13}) + M (p_{14}) ⩽ 6$
$M (p_{1}) = 2$ , $M (p_{6}) = 1$ , $M (p_{13}) = 3$ , $M (p_{14}) = 1$	$M (p_{1}) + M (p_{6}) + M (p_{13}) + M (p_{14}) ⩽ 6$
$M (p_{2}) = 1$ , $M (p_{3}) = 1$ , $M (p_{6}) = 1$ , $M (p_{12}) = 1$ , $M (p_{13}) = 2$	$M (p_{2}) + M (p_{3}) + M (p_{6}) + M (p_{12}) + M (p_{13}) ⩽ 5$
$M (p_{2}) = 1$ , $M (p_{6}) = 1$ , $M (p_{7}) = 1$ , $M (p_{12}) = 1$ , $M (p_{13}) = 2$	$M (p_{2}) + M (p_{6}) + M (p_{7}) + M (p_{12}) + M (p_{13}) ⩽ 5$
$M (p_{1}) = 2$ , $M (p_{2}) = M (p_{3}) = M (p_{12}) = 1$ , $M (p_{13}) = 2$ , $M (p_{14}) = 1$	$M (p_{1}) + M (p_{2}) + M (p_{3}) + M (p_{12}) + M (p_{13}) + M (p_{14}) ⩽ 7$
$M (p_{1}) = 2$ , $M (p_{6}) = M (p_{7}) = M (p_{12}) = 1$ , $M (p_{13}) = 2$ , $M (p_{14}) = 1$	$M (p_{1}) + M (p_{6}) + M (p_{7}) + M (p_{12}) + M (p_{13}) + M (p_{14}) ⩽ 7$
$M (p_{1}) = 2$ , $M (p_{3}) = M (p_{6}) = M (p_{12}) = 1$ , $M (p_{13}) = 2$ , $M (p_{14}) = 1$	$M (p_{1}) + M (p_{3}) + M (p_{6}) + M (p_{12}) + M (p_{13}) + M (p_{14}) ⩽ 7$
$M (p_{1}) = 2$ , $M (p_{2}) = M (p_{7}) = M (p_{12}) = 1$ , $M (p_{13}) = 2$ , $M (p_{14}) = 1$	$M (p_{1}) + M (p_{2}) + M (p_{7}) + M (p_{12}) + M (p_{13}) + M (p_{14}) ⩽ 7$

Table 12.

Monitors for the net system in Figure 5(b) by the proposed method.

$V_{i}$	${}^{•}{V_{i}}$	$V_{i}^{•}$	$M_{0}^{c} (V_{i})$
$V_{1}$	$t_{2}$ , $t_{6}$ , $t_{16}$	$t_{1}$ , $t_{15}$	3
$V_{2}$	$t_{3}$ , $t_{7}$ , $t_{15}$	$t_{2}$ , $t_{6}$ , $t_{14}$	4
$V_{3}$	$t_{4}$ , $t_{8}$ , $t_{14}$	$t_{3}$ , $t_{7}$ , $t_{13}$	5
$V_{4}$	$t_{3}$ , $t_{6}$ , $t_{16}$	$t_{1}$ , $t_{14}$	6
$V_{5}$	$t_{2}$ , $t_{7}$ , $t_{16}$	$t_{1}$ , $t_{14}$	6
$V_{6}$	$t_{4}$ , $t_{7}$ , $t_{15}$	$t_{2}$ , $t_{6}$ , $t_{13}$	5
$V_{7}$	$t_{3}$ , $t_{8}$ , $t_{15}$	$t_{2}$ , $t_{6}$ , $t_{13}$	5
$V_{8}$	$t_{4}$ , $t_{6}$ , $t_{16}$	$t_{1}$ , $t_{13}$	7
$V_{9}$	$t_{2}$ , $t_{8}$ , $t_{16}$	$t_{1}$ , $t_{13}$	7
$V_{10}$	$t_{2}$ , $t_{4}$ , $t_{7}$ , $t_{16}$	$t_{1}$ , $t_{3}$ , $t_{13}$	7
$V_{11}$	$t_{3}$ , $t_{6}$ , $t_{8}$ , $t_{16}$	$t_{1}$ , $t_{7}$ , $t_{13}$	7

Table 13.

Divide-and-conquer-based non-blockingness enforcing procedure for G-system in Figure 5(b).

Nets	Included monitor $V_{i}$	Computed monitor $V_{i}$	Reachable states	Unreachable states
$S N_{1}$	–	$V_{1}$	56	0
$S N_{2}$	–	$V_{2}$	553	0
$S N_{3}$	–	$V_{3}$	452	0
$S N_{4}$	$V_{1}$	–	127	0
$S N_{5}$	$V_{2}$	–	3318	0
$S N_{6}$	$V_{1}$	–	1120	0
$S N_{7}$	$V_{1}$ , $V_{2}$	$V_{4}$ , $V_{5}$	3091	0
$S N_{8}$	$V_{2}$ , $V_{3}$	$V_{6}$ , $V_{7}$	4238	192
$S N_{9}$	$V_{3}$	–	551	0
$S N_{10}$	$V_{1}$	–	2540	0
$S N_{11}$	$V_{1}$ , $V_{2}$ , $V_{4}$ , $V_{5}$	–	6988	0
$S N_{12}$	$V_{2}$ , $V_{3}$ , $V_{6}$ , $V_{7}$	–	25,428	1152
$S N_{13}$	$V_{1} - V_{7}$	$V_{8} - V_{11}$	23,638	1100
$S N_{14}$	$V_{1}$	–	2912	0
$S N_{15}$	$V_{1}$ , $V_{2}$ , $V_{4}$ , $V_{5}$	–	12,806	0
$S N_{16}$	$V_{2}$ , $V_{3}$ , $V_{6}$ , $V_{7}$	–	4985	0
$S N_{17}$	$V_{1} - V_{11}$	–	53,681	2188
$S N_{18}$	$V_{1}$	–	6604	0
$S N_{19}$	$V_{1}$ , $V_{2}$ , $V_{4}$ , $V_{5}$	–	28,768	0
$S N_{20}$	$V_{2}$ , $V_{3}$ , $V_{6}$ , $V_{7}$	–	29,910	1968
$S N_{21}$	$V_{1} - V_{11}$	–	27,706	1870
G-system model	$V_{1} - V_{11}$	–	62,682	3718

Comparison and discussion

Many researchers develop deadlock prevention algorithms that can obtain LESs with maximally permissive behavior, simple supervisory structure, and low computational complexity. Especially, a maximally permissive supervisor can always lead to high utilization of system resources. In general, most existing deadlock prevention polices for G-systems in the literature are not maximally permissive.^37,49,54 However, the proposed method provides an optimal or a near-optimal deadlock prevent policy for designing a non-blocking supervisor for a G-system. Next, we review and compare the proposed method with that in Zhao and Li⁵⁴ and Zhao and Hou⁴⁹ through a typical case study proposed in this section.

To reduce the structural complexity of the controlled system, elementary siphons theory is a good choice for designing LESs with simple structure. The approach in Zhao and Li⁵⁴ can lead to structurally simple liveness-enforcing monitor-based supervisors using elementary siphons. Take the plant net model shown in Figure 5(b) as an example. The net has 68,531 reachable states, 66,400 of which are legal. Based on the method in Zhao and Li,⁵⁴ the net has 13 minimal siphons, 5 of those are elementary siphons, and the others are dependent. As a result, the elementary siphon-based supervisor of the example has five monitors only for elementary siphons, namely $V_{S_{1}}, V_{S_{2}}, \dots, V_{S_{5}}$ , as shown in Table 14. Meanwhile, the corresponding controlled system has 11,903 reachable states. It shows that the supervisor obtained by the algorithm in Zhao and Li⁵⁴ can provide 18% (11,903/66,400) of the optimal behavior. Furthermore, computational complexity of supervisor design remains to be exponential with respect to the net size since the computation of a set of elementary siphons depends on the complete siphon enumeration.

Table 14.

Monitors added for the net system in Figure 5(b) due to the policy in Zhao and Li.⁵⁴

$V_{S_{i}}$	${}^{•}{V_{s_{i}}}$	$V_{S_{i}}^{•}$	$M_{0 V} (V_{S_{i}})$
$V_{S_{1}}$	$t_{4}$ , $t_{8}$ , $t_{14}$	$t_{1}$ , $t_{13}$	5
$V_{S_{2}}$	$t_{4}$ , $t_{8}$ , $2 t_{11}$	$t_{1}$ , $2 t_{9}$	5
$V_{S_{3}}$	$2 t_{2}$ , $2 t_{6}$ , $t_{17}$	$2 t_{1}$ , $t_{13}$	5
$V_{S_{4}}$	$t_{2}$ , $t_{6}$ , $t_{16}$	$t_{1}$ , $t_{13}$	3
$V_{S_{5}}$	$t_{3}$ , $t_{7}$ , $t_{15}$	$t_{1}$ , $t_{13}$	1

Due to the inherent complexity of Petri nets, any deadlock prevention policy that depends on the complete siphon enumeration is definitely exponential with respect to the size of its plant net model. In order to tackle the computational complexity problem, a mixed integer programming (MIP)-based deadlock detection method finds its further applications. The study in Zhao and Hou⁴⁹ proposes a two-stage iterative deadlock prevention policy for G-systems using MIP-based deadlock detection technique. Similarly, for the model shown in Figure 5(b), five monitors are computed due to the method in Zhao and Hou,⁴⁹ namely $V_{S_{1}}, V_{S_{2}}, \dots, V_{S_{4}}$ and $V_{S}^{*}$ , as shown in Table 15. It can be verified that the controlled system has 62,771 reachable states. It means that the corresponding supervisor obtained by the method of Zhao and Hou⁴⁹ can provide 94.5% (62,771/66,400) of the optimal permissive behavior. Note that the permissive behavior of the supervisor depends on the control-induced siphons control stage. That is to say, selecting different siphons in the second stage to control may lead to the supervisors with different permissive behavior. Furthermore, the deadlock control methods that are based on either complete or partial siphon enumeration are computationally expensive in large-scale systems.

Table 15.

Monitors added for the net system in Figure 5(b) due to the policy in Zhao and Hou.⁴⁹

$V_{S}$	${}^{•}{V_{s_{i}}}$	$V_{S_{i}}^{•}$	$M_{0 V} (V_{S_{i}})$
$V_{S_{1}}$	$t_{4}$ , $t_{8}$ , $t_{14}$	$t_{3}$ , $t_{7}$ , $t_{13}$	5
$V_{S_{2}}$	$t_{4}$ , $t_{8}$ , $2 t_{15}$	$t_{2}$ , $t_{6}$ , $t_{13}$ , $t_{14}$	7
$V_{S_{3}}$	$t_{2}$ , $t_{6}$ , $t_{16}$	$t_{1}$ , $t_{15}$	3
$V_{S_{4}}$	$t_{4}$ , $t_{8}$ , $t_{15}$ , $t_{16}$	$t_{1}$ , $t_{13}$ , $t_{14}$	9
$V_{S}^{*}$	$t_{4}$ , $t_{8}$ , $2 t_{14}$ , $t_{16}$	$t_{1}$ , $3 t_{13}$	11

As stated previously, behavioral permissiveness is one of the most important criteria in evaluating a supervisor. Determining how to design a maximally permissive Petri net supervisor has been an interesting yet significant problem. Note that RG is a reliable, accurate, and effective analysis method. However, the method usually suffers from expensive overhead since the complete state enumeration of a Petri net is exponential with its size and initial marking. Aiming at solving the deadlock problems for complex FMS, by further improving the RG-based control policies, the D-C strategy is a significant application on designing a non-blocking supervisor for G-system. Likewise, taking the net model shown in Figure 5(b) as an example. There are 11 monitors designed by the proposed method, namely $V_{1} - V_{11}$ as shown in Table 12. As mentioned above, the controlled system has 62,682 reachable states. It means that the corresponding supervisor obtained by the proposed method can provide 94.4% (62,682/66,400) of the optimal permissive behavior. Note that all monitors in Table 12 have ordinary arcs, while the other two sets of monitors in Tables 14 and 15 have both ordinary arcs and weighted arcs. It indicates that the permissive behavior of the controlled system suffers from the less restriction in some extent due to the proposed method. It is clear to see that the proposed method can provide a near-optimal solution in general. Moreover, the proposed method is well suitable for large-scale systems.

Conclusion

The deadlock prevention approaches in the literature are usually developed by either structural analysis or RG analysis. The former utilizes structural objects such as siphons, P-invariants, and resource circuits. Generally, the major weakness of existing deadlock prevention polices based on structural analysis is the behavioral permissiveness. Specially, an optimal or a near-optimal supervisor cannot be obtained in a generalized net since siphon control is conservative in general. By contrast, the theory of regions is a technique that can find an optimal LES in general cases when it exists. However, its computation is notoriously expensive since the complete state enumeration is necessary. Therefore, the bottleneck of the RG-based method limits its broad application for structural complex systems.

The proposed deadlock prevention policy aims to felicitously trade off behavioral optimality for computational tractability. To achieve this, a D-C iterative algorithm is explored for the most general classes of Petri nets, called G-systems. First, a given G-system is parted into some connected subnets, and then partial controllers for those subnets prone to deadlocks are designed based on the RG analysis. Obviously, the RG computation of the subnet becomes much easier compared with the global G-system. Finally, a non-blocking supervisor is designed after all subnet and its partially controlled system are live. The applicability and the effectiveness of the proposed method to realistic systems have been shown by considering two blocked G-systems from the literature. Experiment results indicate that the method proposed in this article can always lead to a near-optimal non-blocking supervisor. Moreover, the computational cost of the proposed method is lower, which is applicable to big FMS prone to deadlocks.

Footnotes

Academic Editor: ZhiWu Li

Declaration of conflicting interests

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

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This work was supported in part by the Natural Science Foundation of China under Grant Nos 61563045, 61403296, and 61104110, in part by the research grant of the Scientific and Technological Research Council of Turkey under the project number TüBiTAK-112M229, and in part by the Fundamental Research Funds for Central Universities under Grant Nos XJS1404, JB140407.

References

Chen

Barkaoui

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

Wang

Zhou

MC.

Design of optimal monitor-based supervisors for a class of Petri nets with uncontrollable transitions. IEEE T Syst Man Cy: Syst 2013; 43: 1248–1255.

Wang

Yang

Deadlock prevention policy for a class of Petri nets based on complementary places and elementary siphons. J Intell Manuf 2015; 26: 321–330.

Wang

You

Zhou

. Characterization of admissible marking sets in Petri nets with uncontrollable transitions. IEEE T Automat Contr. Epub ahead of print 18 September 2015. DOI: 10.1109/TAC.2015.2480233.

Zhou

ZW.

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

Giua

Decentralized supervision of Petri nets with a coordinator. IEEE T Syst Man Cy: Syst 2015; 45: 955–966.

Zhang

Khalgui

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

Fanti

Maione

Turchiano

Deadlock detection and recovery in flexible production systems with multiple capacity resources. In: Proceedings of the 8th Mediterranean electrotechnical conference, Bari, 13–16 May 1996, pp.237–241. New York: IEEE.

Kumaran

Chang

Cho

. A structured approach to deadlock detection, avoidance and resolution in flexible manufacturing systems. Int J Prod Res 1994; 32: 2361–2379.

10.

Hsien

Chang

SC.

Dispatching-driven deadlock avoidance controller synthesis for flexible manufacturing systems. IEEE T Robot Autom 1994; 10: 196–209.

11.

Xing

Zhou

Liu

. Optimal Petri-net-based polynomial-complexity deadlock-avoidance polices for automated manufacturing systems. IEEE T Syst Man Cy A 2009; 39: 188–199.

12.

Barkaoui

Chaoui

Zouari

. Supervisory control of discrete event systems based on structure theory of Petri nets. In: Proceedings of IEEE international conference on systems, man, cybernetics, computational cybernetics and simulation, Orlando, FL, 12–15 October 1997, vol. 4, pp.3750–3755. New York: IEEE.

13.

Chao

DY.

MIP iteration-reductions for deadlock prevention of flexible manufacturing systems. Int J Adv Manuf Tech 2009; 41: 343–346.

14.

Chen

Zhou

MC.

Optimal supervisory control of flexible manufacturing systems by Petri nets: a set classification approach. IEEE T Autom Sci Eng 2014; 11: 549–563.

15.

Chen

Barkaoui

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

16.

Hou

Zhao

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

17.

Shpitalni

Smart deadlock prevention policy for flexible manufacturing systems using Petri nets. IET Control Theory A 2009; 3: 362–374.

18.

Zouari

Barkaoui

. Parameterized supervisor synthesis for a modular class of discrete event systems. In: Proceedings of IEEE international conference on systems, man, and cybernetics, Washington, DC, 5–8 October 2003, pp.1874–1879. New York: IEEE.

19.

Hou

Al-Ahmari

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

20.

ZW.

Efficient deadlock prevention policy in automated manufacturing systems using exhausted resources. Int J Adv Manuf Tech 2009; 40: 566–571.

21.

Iordache

Antsaklis

PJ.

Synthesis of supervisors enforcing general linear vector constraints in Petri nets. IEEE T Automat Contr 2003; 48: 2036–2039.

22.

Zhou

Jeng

MD.

A maximally permissive deadlock prevention policy for FMS based on Petri net siphon control and the theory of regions. IEEE T Autom Sci Eng 2008; 5: 182–188.

23.

Liu

Jiang

Zhou

MC.

Two simple deadlock prevention policies for S³PR based on key-resource/operation-place pairs. IEEE T Autom Sci Eng 2010; 7: 945–957.

24.

Giua

Design of optimal Petri net controllers for disjunctive generalized mutual exclusion constraints. IEEE T Automat Contr 2015; 60: 1774–1785.

25.

Park

Structural analysis and control of resource allocation systems using Petri nets. Atlanta, GA: Georgia Institute of Technology, 2000.

26.

Chao

DY.

Incremental approach to computation of elementary siphons for arbitrary S³PR. IET Control Theory A 2008; 2: 168–179.

27.

Jeng

Xie

XL.

Deadlock detection and prevention of automated manufacturing systems using Petri nets and siphons. In: Zhou

Fanti

(eds) Deadlock resolution in computer-integrated systems. New York: Marcel Dekker Co., pp.233–281, 2005.

28.

Zhou

MC.

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

29.

Piroddi

Cordone

Fumagalli

Combined siphon and marking generation for deadlock prevention in Petri nets. IEEE T Syst Man Cy A 2009; 39: 650–661.

30.

Tricas

Ezpeleta

Computing minimal siphons in Petri net models of resource allocation systems: a parallel solution. IEEE T Syst Man Cy A 2006; 36: 532–539.

31.

Wang

Zhou

. A method to compute strict minimal siphons in S³PR based on loop resource subsets. IEEE T Syst Man Cy A 2012; 42: 226–237.

32.

Wang

Zhou

MC.

Controllability conditions of resultant siphons in a class of Petri nets. IEEE T Syst Man Cy A 2012; 42: 1206–1215.

33.

Wang

. An algorithm to find the minimal initial markings of resource places ensuring liveness of finite-capacity S³PR. Int J Prod Res 2012; 50: 1528–1538.

34.

Wang

YP.

Design of a liveness-enforcing supervisor for S³PR based on complementary places. ACM T Embed Comput S 2013; 12: 1–18.

35.

Hou

Zhao

Liu

Deadlock control for a class of generalized Petri nets based on proper resource allocation. Asian J Control 2016; 18: 206–223.

36.

Huang

YS.

Deadlock prevention for flexible manufacturing systems in sequence resource allocation systems. J Inf Sci Eng 2007; 23: 215–231.

37.

Zhao

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

38.

Chen

Khalgui

. Design of a maximally permissive liveness-enforcing Petri net supervisor for flexible manufacturing systems. IEEE T Autom Sci Eng 2011; 8: 374–393.

39.

Chen

ZW.

Design of a maximally permissive liveness-enforcing supervisor with a compressed supervisory structure for flexible manufacturing systems. Automatica 2011; 47: 1028–1034.

40.

Chen

Zhou

MC.

Behaviorally optimal and structurally simple liveness-enforcing supervisors of flexible manufacturing systems. IEEE T Syst Man Cy A 2012; 42: 615–629.

41.

Chen

Barkaoui

Maximally permissive Petri net supervisors for flexible manufacturing systems with uncontrollable and unobservable transitions. Asian J Control 2014; 16: 1646–1658.

42.

Badouel

Darondeau

Theory of regions. In: Reisig

Rozenberg

(eds) Lectures on Petri nets I: basic models (LNCS), vol. 1491. London: Springer, 1998, pp.529–586.

43.

Uzam

An optimal deadlock prevention policy for flexible manufacturing systems using Petri net models with resources and the theory of regions. Int J Adv Manuf Tech 2002; 19: 192–208.

44.

Ghaffari

Nidhal

Xie

XL.

Design of a live and maximally permissive Petri net controller using the theory of regions. IEEE T Robot Autom 2003; 19: 137–142.

45.

Uzam

Zhou

MC.

An improved iterative synthesis method for liveness enforcing supervisors of flexible manufacturing systems. Int J Prod Res 2006; 44: 1987–2030.

46.

Uzam

Zhou

MC.

An iterative synthesis approach to Petri net based deadlock prevention policy for flexible manufacturing systems. IEEE T Syst Man Cy A 2007; 37: 362–371.

47.

Uzam

Gelen

. A divide-and-conquer-method for the synthesis of liveness enforcing supervisors for flexible manufacturing systems. J Intell Manuf. Epub ahead of print 12 July 2014. DOI: 10.1007/s10845-014-0938-z.

48.

Zhou

MC.

Deadlock resolution in automated manufacturing systems: a novel Petri net approach. London: Springer, 2009.

49.

Zhao

Hou

YF.

An iterative method for synthesizing non-blocking supervisors for a class of generalized Petri nets using mathematical programming. Discrete Event Dyn S 2013; 23: 3–26.

50.

Zhao

Hou

Liu

Liveness-enforcing supervisors synthesis for a class of generalised Petri nets based on two-stage deadlock control and mathematical programming. Int J Control 2010; 83: 2053–2066.

51.

Zhao

HS.

Suboptimal liveness-enforcing supervisor design for a class of generalised Petri nets using partial siphon enumeration and mathematical programming. Int J Syst Sci 2010; 41: 1013–1026.

52.

Zhu

Zhou

MC.

A divide-and-conquer strategy to deadlock prevention in flexible manufacturing systems. IEEE T Syst Man Cy C 2009; 39: 156–169.

53.

Ezpeleta

Colom

Martinez

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

54.

Zhao

ZW.

On deadlock control for a class of generalised Petri net models of flexible manufacturing systems. Int J Prod Res 2009; 47: 6085–6107.

55.

INA. Integrated Net Analyzer, a software tool for analysis of Petri nets, version 2.2, 31 July 2003, http://www.informatik.hu-berlin.de/~starke/ina.html

56.

Uzam

Zhou

MC.

Identification and elimination of redundant control places in Petri net based liveness enforcing supervisors of FMS. Int J Adv Manuf Tech 2007; 35: 150–168.

Near-optimal supervisory control of flexible manufacturing systems using divide-and-conquer iterative method

Abstract

Keywords

Introduction

Motivation of deadlock prevention policy for G-systems

An iterative D-C synthesis approach for deadlock prevention in G-systems

Definition 1

Definition 2

Remark 1

Example 1

Definition 3

Property 1

Example 2

Notation 1

Remark 2

Example 3

Theorem 1

Proof

Remark 3

Theorem 2

Proof

Remark 4

A case study

A G-system example

Comparison and discussion

Conclusion

Footnotes

Declaration of conflicting interests

Funding

References