<figure><img src="image_1.png" /></figure>

HAL
open science

Compute Optimization of Petri Net Controllers Using
the Algebraic Method

Sadok Rezig, Sadok Turki, Nidhal Rezg

<figure><img src="image_2.png" /></figure>

► To cite this version:

Sadok Rezig, Sadok Turki, Nidhal Rezg. Compute Optimization of Petri Net Controllers Using the Algebraic Method. Applied Sciences, 2019, 9 (13), pp.2633. 10.3390/app9132633. hal-02968023

HAL Id: hal-02968023

https://hal.univ-lorraine.fr/hal-02968023

Submitted on 15 Oct 2020

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_3.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Article

# Compute Optimization of Petri Net Controllers Using the Algebraic Method

Sadok Rezig\*ID, Sadok Turki and Nidhal Rezg

Laboratoire de Génie Informatique, de Production et de Maintenance, UFR MIM, Université de Lorraine,
57000 Metz, France

\* Correspondence: sadok.rezig@univ-lorraine.fr; Tel.: +33-372-748-045

Received: 14 May 2019; Accepted: 18 June 2019; Published: 28 June 2019

<figure><img src="image_4.png" /></figure>

check for
updates

**Featured Application:** This paper allowed us to implement Petri net controllers on PLCs (Programmable Logic Controller) of the Flexible Manufacturing System (FMS) in the university of UFR MIM in Metz-FRANCE. Our teamwork applied this control model to the FMS recently installed in our laboratory LGIPM using all the appropriate software (Siemens STEP7 and SCHNEIDER Unity Pro for control software, simulation, and modeling software: CPN Tools and finally supervision software: WINCC FLEXIBLE).

**Abstract:** This study attempted to calculate an optimal Petri net supervisor able to respect the control specifications imposed for a flexible manufacturing system. There are several theories around the control synthesis of discrete event systems. Unfortunately, these methods are very sensitive to the combinatorial explosion of states in the generated graph, especially when the complexity of the system increases. It is therefore necessary to move towards new ways based on formal methods allowing the synthesis of a supervisor. In this work, we propose an algebraic approach using the theory of regions. Our main contribution is to design a set of Petri net controllers based on the properties of Petri nets and not on reachability graph generation for bounded Petri nets. This will decrease significantly the production cost of the manufacturing system, since the computation burden of the supervisor is reduced. Our control policy was applied to a flexible manufacturing system implemented in our laboratory. Comparisons with previous studies using CPLEX software are provided in order to illustrate the effectiveness of our proposed method.

**Keywords:** discrete event systems; flexible manufacturing system; combinatorial explosion of states; theory of regions; bounded petri nets

## 1. Introduction

The control of automated systems has long been a matter of great interest to the scientific world. The tools for studying discrete event systems (DES) are numerous, but Petri nets (PNs) [1] are nowadays most used because of their various and interesting properties for complex systems, such as airplanes, nuclear power plants or oil refineries, etc. This kind of system with a high level of safety and precision requires formal control methods to ensure operation in conformance with the specifications. Given a manufacturing system, we are interested in imposing on it a function respecting a desired behavior. For less complex systems, the easiest way for the control is the direct design of a supervised model of the system. However, when the complexity of the system increases, this method becomes very laborious and cannot guarantee compliance with control specifications. It is therefore necessary to opt for a formal method allowing the synthesis of the controller.

The works of [2,3] forms the basis of the general theory of control by supervision. Although the formalism used by the authors allows the modeling of a large class of DES, it is not adapted to real
systems because of its high sensitivity regarding the combinatorial explosion of states. For this reason, many attempts have been made to solve this problem [4–8]. In fact, to model complex systems, the use of PNs seems more rigorous and beneficial, since this formalism is characterized by richer modeling structures. Nevertheless, the advantage of representation conciseness is counterbalanced by the low result optimality.

One of the most efficient methods that generate maximum permissive PN controllers is the theory of regions (TR) developed by Ghaffari et al. [9–12]. This theory gives an optimal control solution regardless of the process controllability level. The synthesis of the PN supervisor is based on the reachability graph (RG) and relies on the [2-3] approach to compute the controller. Its applicability is general for bounded PN models. Unfortunately, the TR suffers from a great technical obstacle; In fact, the steps of generating the RG and its analysis in order to find the existing cycles, the legal/forbidden states, weigh down heavily on the process of calculating PN controllers. Moreover, a possible combinatorial explosion of states in RG for complex systems increases significantly the computational burden. Since the calculation time of the control costs money according to the imposed constraints, the main contribution of this paper is to develop a control method which enables us to use the advantages of the PN properties and the TR while avoiding its technical obstacles, i.e., the generation and the analysis of the RG.

As a result, several studies have focused on RG analysis to synthesize near-optimal/optimal PN controllers [13–16]. Indeed, a reachability graph-based approach was developed to design an optimal PN controller with the fewest control places for flexible manufacturing systems. The graph was divided into a live zone and deadlock zone, with the states in the deadlock zone already deadlocked or leading to a deadlock and those in the live zone as legal ones. In addition, Chen et al. [17] proposed a vector-covering approach to decrease the number of states to consider in the synthesis process of the PN supervisor. These methods can reduce the number of PN monitors. However, they have a disadvantage; the computation load is extremely hard, principally for large models. In Zhao et al. [18], a new approach for control synthesis called divide-and-conquer strategy was developed to improve the computational efficiency of the PN supervisor developed by the traditional methods of Uzam and Zhou [19,20]. Unfortunately, too many subsystems must be disposed. Thus, if the considered model is big, the improvement of these methods will be impeded. In addition, many studies also focused on reducing the computational complexity of TR. Li and Zhao [21] developed a new approach which used a siphon method before using TR to design PN controllers. Furthermore, Huang and Pan [22] developed a new method for deadlock prevention based on the TR. This control policy sought to decrease the number of reachability conditions of the theory of regions in order to facilitate supervisor computation. The comparison of this work with the previous studies [19,23,24] shows that this approach is the most optimal, but the use of the TR is always based on the analysis of the graph. Yet, the approaches able to use the TR without generating the graph have not been investigated. This work sheds new light on the simplification of the TR for control synthesis for bounded PNs.

In our previous works [25–29], a new method called minimal cuts in RG was developed. Through this control policy, the computational cost of the PN supervisor was minimized by applying the TR on specific zones and not on the whole graph. Nevertheless, the RG-generation step and its analysis are inevitable. In this work, a new method is proposed to design PN controllers by avoiding generating the RG. Indeed, based on mathematical concepts and structural properties of PNs, the controller is designed. Consequently, the computing time of the monitor is reduced, and then one can control the system constraints in a timely manner. Thus, the security or the production will be directly affected.

The paper is formulated as follows. Section 2 presents the background of PN tools and the theory of regions for control synthesis. Section 3 depicts the concept of our new control policy. Section 4 presents the petri net of our flexible manufacturing system example, on which we will apply our method. In Section 5, the comparison results with previous works on supervisory control are provided [13,22,28,29]. Finally, conclusions and perspectives are drawn in Section 5.
## 2. Preliminaries

### 2.1. Petri Nets

A PN is a mathematical and graphical modeling tool for many systems, especially for DES. From an informal point of view, a PN is a directed graph with two types of nodes (place and transition) and has a dynamic behavior. The places and transitions are connected by oriented arcs. An arc connects either a place to a transition or a transition to a place but never connects a place to a place or a transition to a transition. Moreover, from a formal point of view, a PN is a bipartite graph: $PN = \langle P, T, Pre, Post \rangle$; P is a set of places. T is a set of controllable and uncontrollable transitions $T = T_c \cup T_u$ [1] (Murata, 1989); the transitions are partitioned into two disjoint subsets: the set of controllable transitions $T_c$, which can be disabled by the controller, while the set of uncontrollable transitions $T_u$ cannot. Pre: $P \times T \to \mathbb{N}$ represent a pre-incidence function that specifies weighted arcs from P to T. Post: $P \times T \to \mathbb{N}$ is the post-incidence function that specially weights arcs from T to P. ($\mathbb{N}$ is a set of nonnegative integers.) Let the set $p^{(t)}$ (respectively $(^t)p$) be the output transitions (respectively input transitions) of a place p. Indeed, a PN can be expressed by an indexed matrix C such that $C(p_i, t_j) = w(t_j, p_i)$ if $t_j \in (^t)p_i$ and $C(p_i, t_j) = -w(p_i, t_j)$ if $t_j \in p_i^{(t)}$, or else 0; where $w: F \to \mathbb{N}$ is a valuation function of arcs (the finite set of arcs $F \subseteq (P \times T) \cup (T \times P)$). Moreover, let $t^{(p)}$ (respectively $(^p)t$) be the set of output places (respectively input places) of a transition t. The reachability graph designed from the initial marking $M_0$ is denoted by $G(N, M_0)$. The generated markings in the RG are denoted by M. A transition t is enabled from a state $M \in M$ (denoted by $M[t >)$ if and only if $M \ge Pre(., t)$). An enabled transition t may fire-yield a new state $M'$ such that $M' = M + C(., t)$ this statement can be defined by $M[t > M'$. A new state $M'$ is reachable from a marking M if a firing sequence $\sigma = t_1t_2...t_n$ exists by firing $\sigma$, and any state $M'$ reachable from the initial state $M_0$ satisfies the following Petri net state equation: $M' = M_0 + C \cdot \vec{\sigma}$, where $\vec{\sigma}: T \to \mathbb{N}$ is a vector of nonnegative integers called the occurrence of $t_i$ in $\sigma$. A Petri net is said to be k-bounded if in each place $p_i \in P$, the number of tokens does not exceed k. A Petri net is reversible, if from any reachable marking $M'$, an enabled sequence $\sigma$ exists, transforming $M'$ into $M_0$. Finally, a Petri net is said to be live if every transition is live.

### 2.2. Theory of Regions

The theory of regions (TR) for control synthesis was developed by Ghaffari et al. [9–12] using PN tools for adding a control place $P_c$ to the initial PN model with initial marking $M_0(P_c)$ and its incidence vectors $C(P_c, .)$. This theory is reformulated by a linear system composed of three kinds of conditions; the reachability conditions, the marking/transition separation instance (MTSI) equations, and the basic cycle conditions. By resolving this linear system, one can compute a PN supervisor composed of a set of control places. Each control place $P_c$ must fulfill the reachability conditions, i.e.:

$$M_0(P_c) + C(P_c, .) \vec{\Gamma}_M \ge 0. \qquad (1)$$

$\vec{\Gamma}_M$: is the path between $M_0$ and M.

In addition, each PN monitor to add should solve at least one prohibited event $(M, t)$. The MTSI condition relative to the couple $(M, t)$ is:

$$M_0(P_c) + C(P_c, .) \vec{\Gamma}_M + C(P_c, t) < 0. \qquad (2)$$

Finally, $P_c$ must satisfy cycle equations:

$$\sum_{t \in T} C(P_c, t) \cdot \vec{\sigma}[t] = 0, \forall \sigma \in \Delta. \qquad (3)$$

$\vec{\sigma}[t]$ is the algebraic sum of occurrences of $t$ in $\sigma$. $\Delta$ is the set of existing cycles in RG.
Notably, many MTSI conditions may obtain the same solutions by resolving the linear system composed of Equations (1)–(3). As a result, the number of PN controllers will be much smaller than the set of MTSI conditions. The following example of Figure 1 is an application of the TR for control synthesis.

<figure><img src="image_5.png" /><figcaption>Figure 1. Application of the theory of regions in the (a) Petri net (PN) model, (b) reachability graph, and (c) controlled PN model.</figcaption></figure>

For this prohibited state problem, one can forbid the following event ($M_5 \xrightarrow{T_1} M_7$) (see Figure 1b) since $M_7$ is a blocking state. Based on the TR, there are:

Seven reachability conditions:

$$M_0(P_c) \geq 0,$$

$$M_1(P_c) = M_0(P_c) + C(P_c, T_1) \geq 0,$$

$$M_2(P_c) = M_0(P_c) + C(P_c, T_1) + C(P_c, T_2) \geq 0,$$

$$M_3(P_c) = M_0(P_c) + C(P_c, T_1) + C(P_c, T_2) + C(P_c, T_3) \geq 0,$$

$$M_4(P_c) = M_0(P_c) + 2C(P_c, T_1) + 2C(P_c, T_2) + C(P_c, T_3) \geq 0,$$

$$M_5(P_c) = M_0(P_c) + 2C(P_c, T_1) + 2C(P_c, T_2) \geq 0,$$

$$M_6(P_c) = M_0(P_c) + 2C(P_c, T_1) + C(P_c, T_2) \geq 0.$$

One cycle equation:

$$C(P_c, T_1) + C(P_c, T_2) + C(P_c, T_3) + C(P_c, T_4) = 0.$$

One MTSI condition:

$$M_7(P_c) = M_0(P_c) + 2C(P_c, T_1) + 2C(P_c, T_2) + C(P_c, T_1) < 0.$$

Therefore, the linear system contains nine equations. Its resolution leads to the controlled PN (see Figure 1c). The controller $P_c$ is characterized as follows:

$$M_0(P_c) = 2; C(P_c, .) = (-1, 0, 0, 1).$$
**3. Computationally Improved Optimal Control Policy**

In this section, we propose an efficient controller synthesis method based on a new interpretation of the theory of regions without generating the reachability graph.

**3.1. *Supervisory Control Problem***

The theory of regions is recognized as one of the powerful methods for the supervisory control problem. However, the analyzing steps of the RG to determine the linear system of the TR weigh down heavily on the calculation process of PN controllers. This may lead to a failure to respect the control constraints. Based on PN properties and mathematical concepts, one can obtain the linear system of TR without needing the RG. In this work, the non-generated RG will be appointed a virtual graph (VG).

**Definition 1.** [30] A GMEC (generalized mutual exclusion constraint) is a condition that limits a weighted sum of tokens contained in a subset of places P. A control specification expressed by a GMEC is represented by a couple $(\vec{w}, K)$, which defines a set of legal markings: $ML = \{M \in M | \vec{w}^t.M \le K\}$, where $\vec{w}$ is a weight vector of nonnegative integers and K is a positive integer. Markings which fail to comply with a GMEC will be denoted forbidden state MF.

**Definition 2.** [27] Let a net $N = (P, T, Pre, Post)$ be a Petri net with an incidence matrix $C$. $X_t$ is a nonnegative vector of $n$ integers, it is the solution of the equation: $C.X_t = 0$. $\sigma$ is the firing sequence for a legal marking $M$ with $\sigma = X_t$ (card($\sigma$) = $n$). The sequence $\sigma$ is called transition invariant (t-invariant): $C.[X_{t1} \ X_{t2} \ ... \ X_{tn}]^t = 0$ The resolution of this system generates the transition invariants that can identify the cycle Equation (3).

**Definition 3.** [29] A p-invariant of a given PN is a nonnegative vector $X$ of $n$ integers (card($P$) = $n$) verifying: $X.C = 0 \Rightarrow [X_1 \ X_2 \ ... \ X_n].C = 0$.

**Property 1.** An important property arises from Definition 3. Indeed, for any legal marking $M \in ML$, a p-invariant verifies: $X^t.M = X^t.M_0$, which means that the sum of places markings weighted by the vector $X$ is constant, i.e., $\sum_{i=1}^n X_i m_i = Ct$, $\forall Ct \ge 0$, where $m_i$ is the marking of $p_i$.

**Definition 4.** A primitive state $M_p$ is a vector presented with the following coordinates: $M_p^t = [p'_1 p'_2 ... p'_n]^t$, where $n$ is the number of places in the given PN and $p'_x$ is the corresponding marking of the place $P_x$.

**Definition 5.** A reachable state $M_{xi}$ is a marking that exists in the VG obtained by applying the PN state equation: $M_{xi} = M_0 + C \vec{\sigma}_{xi}$, $M_{xi}$ can easily be determined if p-invariants exist.

**Definition 6.** An event separation instance is represented by a couple $(M, t)$, where $M \in M_{(\vec{w},K)}$ is a legal state and $t$ is a forbidden state transition $\Omega = \{(M, t) | \exists M[t > M', M \in M_{(\vec{w},K)}', M' \in MF]\}$ (see Figure 2).

<figure><img src="image_6.png" /><figcaption>**Figure 2.** Marking/transition separation instance (MTSI) example.</figcaption></figure>
**Definition 7.** A state is said to be dangerous if it leads to the forbidden markings MF by firing uncontrollable transitions. Let MD be the set of dangerous states: $MD = \{M \in RG | \exists t \in T_u, \exists \sigma \in T_u^*, M[\sigma > M' M'[t > M'(M', t) \in \Omega]\}$.

**Definition 8.** Let $M_0$ be the initial marking of a given PN with its incidence matrix such as $M_0^t = (y_0, y_1 \dots y_n)$ where n is the number of places in the PN. The Linear System of Paths (LSP) is defined as follows:

$$C.\sigma = M_p - M_0 = \begin{pmatrix} p'_1 - y_1 \\ p'_2 - y_2 \\ \vdots \\ p'_n - y_n \end{pmatrix} \geq \begin{pmatrix} -y_1 \\ -y_2 \\ \vdots \\ -y_n \end{pmatrix} \quad (4)$$

The calculated paths will be denoted $P_s = \sum_i \sigma_i$.

**Remark 1.** If the system reaches a dangerous marking $M_j \in MD$, the uncontrollable transition $t_y \in T_u$ will be subtracted from the corresponding path $\sigma_j$ (i.e., $\sigma_i = \sigma_j - t_y$). This subtraction will affect the corresponding MTSI condition since the new marking $M_i$ obtained by crossing $\sigma_i$ is counted as a forbidden marking, i.e., $M_i \in MF$.

The aim of our proposed method is to determine the linear system of the TR defined by Equations (1)–(3). [2,3] demonstrated that a PN supervisor has a maximally permissive behavior if the legal states exist and the system behavior cannot be led outside the legal-states-zone. This hints that one should remove all illegal states (i.e., forbidden and dangerous markings) from the VG if one wants to obtain the desired behavior.

## 3.2. Calculation of the Linear System

In our previous work [28], we proposed two approaches that minimize the TR equations based on specific RG zones. Unfortunately, the technical obstacles of the TR persist in the convexity between the linear system equations.

**Theorem 1.** There is a control place which prohibits a state transition $M[t > M'$ if and only if the basic marking $m'$ (corresponding to the marking $M'$) is not a convex combination of all existing markings in VG (see Figure 3). In other words, the following relation is not true:

<figure><img src="image_7.png" /><figcaption>Figure 3. The virtual graph (VG).</figcaption></figure>

$\exists \lambda \geq 0 | \sum_{k=1}^{r} \lambda_k = 1 \text{ and } m' = \sum_{M_k \in VG} \lambda_k m_k, r$ is the number of markings in VG.
**Proof.** If a control place $P_c$ solving an MTSI condition exists, then its incidence vector checks the following system ($M' \in MF, t \in \Omega$):

$$ \left\{ \begin{array}{l} M_k(P_c) = M_0(P_c) + C(P_{c,\cdot}).\vec{\Gamma}_{M_k} \ge 0 \quad \forall k = 1..r \\ M'(P_c) = M_0(P_c) + C(P_{c,\cdot}).\vec{\Gamma}_M + C(P_{c,t}) < 0 \end{array} \right. $$

The above system is equivalent to the following relation: $C(P_{c,\cdot}).(\vec{\Gamma}_{M'} - \vec{\Gamma}_{M_k}) \le -1, \forall k = 1..r$.

$$ \Rightarrow \left( \begin{array}{c} (m' - m_1)^t \\ (m' - m_2)^t \\ \vdots \\ (m' - m_k)^t \end{array} \right) \le -I \quad (5) $$

$I$ is the unit vector of $\mathbb{R}^n$.

If there is no control place $P_c$ which prohibits the crossing of $t$ from $M$, then the above system would have no solution. However, according to a result in [28], the system can admit a solution if there is a convex combination between $m'$ and the basic markings validating the forbidden transition $t$. □

**Corollary 1.** There is a control place that forbids a state transition $M[t > M'$ if the marking $M'$ is not a convex combination of the markings of VG.

The control synthesis method using the new interpretation of TR is resumed in the flowchart below (see Figure 4). The main idea of the proposed policy is to determine all transition sequences (i.e., $P_s = \sum_i \sigma_i$) which connect the initial state $M_0$ to the other markings (i.e., ML, MF and MD). Then, one can resolve the linear system of the theory of regions to synthesize the PN controllers.

<figure><img src="image_8.png" /><figcaption>**Figure 4.** The proposed control synthesis method flowchart.</figcaption></figure>
## 4. Example

A flexible manufacturing system composed of three stations in UFR-MIM FRANCE and its PN model are presented in Figure 5a,b, respectively. In the first station ($P_1$), glass pieces are laser-engraved and stored in appropriate locations. Stations 2 and 3 modeled by $P_2 \& P_3$ pack the engraved pieces, respectively, in black and red boxes. The capacity of each station is modeled by $P_4$ and $P_5$ and is equal to three tokens. Transitions ($t_1, t_2$) and ($t_4, t_5$) represent, respectively, the events of entry and exit of the pallets through their annex conveyors. Otherwise, the pallets can continue their way to the main conveyor by crossing $t_3$. Note that only the transitions $t_1$ and $t_2$ are controllable.

<figure><img src="image_9.png" /><figcaption>Figure 5. UFR-MIM flexible manufacturing system. (a) PN model, (b) experimental environment.</figcaption></figure>

Since the used black boxes are cheaper than red ones, the constraint to respect is keeping the marking of $P_2$ plus the doubled marking of $P_3$ less than three tokens. This control specification can be formulated by the following GMEC:

$$M(P_2) + 2M(P_3) \leq 3$$

The t-invariants can be determined by resolving the following system: $C[x_{t1}x_{t2}x_{t3}x_{t4}x_{t5}]^t = 0$.

$$\begin{bmatrix} -1 & -1 & 0 & 1 & 1 \\ 1 & 0 & 0 & -1 & 0 \\ 0 & 1 & 0 & 0 & -1 \\ -1 & 0 & 0 & 1 & 0 \\ 0 & -1 & 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} x_{t1} \\ x_{t2} \\ x_{t3} \\ x_{t4} \\ x_{t5} \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \\ 0 \\ 0 \\ 0 \end{bmatrix}$$

$(X_t^1)^t = [10010]; (X_t^2)^t = [01001];$ therefore, the sequences corresponding to the cycle equations are: $\sigma_1 = (t_1t_4)$ and $\sigma_2 = (t_2t_5)$. The basic cycle equations can be detailed as follows:

$$C(P_{ci}, t_3) = 0,$$

$$C(P_{ci}, t_1) + C(P_{ci}, t_4) = 0,$$

$$C(P_{ci}, t_2) + C(P_{ci}, t_5) = 0.$$
According to our PN model $M_p = (p'_1 p'_2 p'_3 p'_4 p'_5)$. Thus, one can define the LSP in order to identify the set of paths $P_s = \sum_i \sigma_i$:

$$C.\sigma = M_p - M_0 = \begin{pmatrix} p'_1 - 4 \\ p'_2 - 0 \\ p'_3 - 0 \\ p'_4 - 3 \\ p'_5 - 3 \end{pmatrix} \ge \begin{pmatrix} -4 \\ 0 \\ 0 \\ -3 \\ -3 \end{pmatrix}$$

The detailed information of the calculated paths $P_s = \sum_i \sigma_i$ is listed in Table 1. Once all paths are determined, one can obtain the set of reachable markings $M_x$. The detailed information of $M_x$ is listed in Table 2.

<table><caption>**Table 1.** Information of paths.</caption><thead><tr><th>Sequence of Transitions</th><th>Information of Sequence (t<sub>1</sub>t<sub>2</sub>t<sub>3</sub>t<sub>4</sub>t<sub>5</sub>)</th><th>Sequence of Transitions</th><th>Information of Sequence (t<sub>1</sub>t<sub>2</sub>t<sub>3</sub>t<sub>4</sub>t<sub>5</sub>)</th></tr></thead><tbody><tr><td>σ<sub>1</sub></td><td>(1 0 0 0 0)</td><td>σ<sub>7</sub></td><td>(1 2 0 0 0)</td></tr><tr><td>σ<sub>2</sub></td><td>(0 1 0 0 0)</td><td>σ<sub>8</sub></td><td>(2 1 0 0 0)</td></tr><tr><td>σ<sub>3</sub></td><td>(0 2 0 0 0)</td><td>σ<sub>9</sub></td><td>(3 0 0 0 0)</td></tr><tr><td>σ<sub>4</sub></td><td>(1 1 0 0 0)</td><td>σ<sub>10</sub></td><td>(1 3 0 0 0)</td></tr><tr><td>σ<sub>5</sub></td><td>(2 0 0 0 0)</td><td>σ<sub>11</sub></td><td>(2 2 0 0 0)</td></tr><tr><td>σ<sub>6</sub></td><td>(0 3 0 0 0)</td><td>σ<sub>12</sub></td><td>(3 1 0 0 0)</td></tr></tbody></table>

<table><caption>**Table 2.** Information of reachable markings.</caption><thead><tr><th>Marking No.</th><th>Path</th><th>Information of Marking [p<sub>1</sub> p<sub>2</sub> p<sub>3</sub> p<sub>4</sub> p<sub>5</sub>]<sup>T</sup></th><th>Classification</th></tr></thead><tbody><tr><td>M<sub>x1</sub></td><td>σ<sub>1</sub></td><td>[3 1 0 3 2]<sup>T</sup></td><td>ML</td></tr><tr><td>M<sub>x2</sub></td><td>σ<sub>2</sub></td><td>[3 0 1 2 3]<sup>T</sup></td><td>ML</td></tr><tr><td>M<sub>x3</sub></td><td>σ<sub>3</sub></td><td>[2 0 2 1 3]<sup>T</sup></td><td>MF</td></tr><tr><td>M<sub>x4</sub></td><td>σ<sub>4</sub></td><td>[2 1 1 2 2]<sup>T</sup></td><td>ML</td></tr><tr><td>M<sub>x5</sub></td><td>σ<sub>5</sub></td><td>[2 2 0 3 1]<sup>T</sup></td><td>ML</td></tr><tr><td>M<sub>x6</sub></td><td>σ<sub>6</sub></td><td>[1 0 3 0 3]<sup>T</sup></td><td>MF</td></tr><tr><td>M<sub>x7</sub></td><td>σ<sub>7</sub></td><td>[1 1 2 1 2]<sup>T</sup></td><td>MF</td></tr><tr><td>M<sub>x8</sub></td><td>σ<sub>8</sub></td><td>[1 2 1 2 1]<sup>T</sup></td><td>MF</td></tr><tr><td>M<sub>x9</sub></td><td>σ<sub>9</sub></td><td>[1 3 0 3 0]<sup>T</sup></td><td>ML</td></tr><tr><td>M<sub>x10</sub></td><td>σ<sub>10</sub></td><td>[0 1 3 0 2]<sup>T</sup></td><td>MF</td></tr><tr><td>M<sub>x11</sub></td><td>σ<sub>11</sub></td><td>[0 2 2 1 1]<sup>T</sup></td><td>MF</td></tr><tr><td>M<sub>x12</sub></td><td>σ<sub>12</sub></td><td>[0 3 1 2 0]<sup>T</sup></td><td>MF</td></tr></tbody></table>

It is noticed that there are no dangerous markings MD. On the other hand, we should subtract the uncontrollable transition(s) from the corresponding path. Hence, the reachability conditions can be obtained as follows.

$$ 
\begin{align*}
M_0(P_{ci}) &\ge 0, \\
M_0(P_c) + C(P_{ci}, t_1) &\ge 0, \\
M_0(P_c) + C(P_{ci}, t_2) &\ge 0, \\
M_0(P_c) + C(P_{ci}, t_1) + C(P_{ci}, t_2) &\ge 0, \\
M_0(P_c) + 2C(P_{ci}, t_1) &\ge 0, \\
M_0(P_c) + 3C(P_{ci}, t_1) &\ge 0.
\end{align*} $$
The MTSI conditions can then be listed as follows:

$$
\begin{align*}
M_0(P_c) + 2C(P_{ci}, t_2) &< 0, \\
M_0(P_c) + 3C(P_{ci}, t_2) &< 0, \\
M_0(P_c) + C(P_{ci}, t_1) + 2C(P_{ci}, t_2) &< 0, \\
M_0(P_c) + 2C(P_{ci}, t_1) + C(P_{ci}, t_2) &< 0, \\
M_0(P_c) + C(P_{ci}, t_1) + 3C(P_{ci}, t_2) &< 0, \\
M_0(P_c) + 2C(P_{ci}, t_1) + 2C(P_{ci}, t_2) &< 0, \\
M_0(P_c) + 3C(P_{ci}, t_1) + C(P_{ci}, t_2) &< 0.
\end{align*}
$$

According to our new control policy, two control places $P_{c1}$ and $P_{c2}$ can then be located by removing redundant PN monitors when the linear system composed of reachability and MTSI conditions and cycle equations are solved. The controlled system net is obtained and shown in Table 3 and Figure 6.

<table><caption>**Table 3.** The control places for the PN.</caption><thead><tr><th>Additional Control Places</th><th>The Initial Marking M<sub>0</sub>(P<sub>ci</sub>)</th><th>The Incidence Vector C(P<sub>ci</sub>, ·)</th></tr></thead><tbody><tr><td>P<sub>c1</sub></td><td>3</td><td>(-1, -2, 0, 1, 2)</td></tr><tr><td>P<sub>c2</sub></td><td>1</td><td>(0, -1, 0, 0, 1)</td></tr></tbody></table>

<figure><img src="image_10.png" /><figcaption>**Figure 6.** The controlled PN model.</figcaption></figure>

**5. Comparison with Previous Approaches**

This section presents four tables to compare our work with previous control synthesis approaches. For convenience, the control policy of this work is called $R_3$, while our prior work [28] and Reference [29] are called $R_1$ and $R_2$, respectively. Moreover, the related studies [10,22] are called G and HP, respectively. First, we compared this work with our previous experimental results on supervisory control [28,29] in example 1 of a flexible manufacturing system (see Figure 5). Further, our method was confronted in example 2 with the method of Huang and Pan (HP) [22] based on the theory of regions and reduction approach. The experimental results of HP infer that the control policy seems to be the most effective method among existing deadlock prevention approaches, such as the works of Uzam and Zhou [20], and Park and Reveliotis [24]. Finally, it is shown in example 3 of Ghaffari et al. [10] that our control policy can more effectively design PN monitors through comparison to the classical approach of the TR in control synthesis used in G.
## 5.1. FMS Example 1

Table 4 lists the comparison results with our previous works $R_1$ and $R_2$ to design PN controllers for the flexible manufacturing system (FMS) example. One can observe that for the same number of PN monitors and MTSI conditions, one can calculate an optimal supervisor without a complete state enumeration and mixed integer programming problems, which is computationally intractable. Indeed, zero markings were generated in our method and two PN controllers were synthesized within 3560 ms, contrary to the previous approaches $R_1$ and $R_2$ that consume 7190 ms and 7213 ms, respectively, and together generate 13 markings in the reachability graph. Thus, one can remark that the reduction technology is involved in $R_3$ by dividing the computation time by 2. The controlled system net with the three methods was obtained and is shown in Table 5.

<table><caption>**Table 4.** Comparison results in example 1.</caption><thead><tr><th>Control Criteria</th><th>No. of PN Controllers</th><th>No. of Markings in the RG</th><th>Maximally Permissive</th><th>No. of MTSI</th><th>Computation Time (ms)</th><th>Approach</th></tr></thead><tbody><tr><td>$R_1$</td><td>2</td><td>13</td><td>Yes</td><td>7</td><td>7190</td><td>Minimal Cuts</td></tr><tr><td>$R_2$</td><td>2</td><td>13</td><td>Yes</td><td>7</td><td>7213</td><td>Canonic markings</td></tr><tr><td>$R_3$</td><td>2</td><td>0</td><td>Yes</td><td>7</td><td>3560</td><td>Without RG</td></tr></tbody></table>

<table><caption>**Table 5.** Petri net controllers of example 1.</caption><thead><tr><th>Method</th><th>Additional Control Places</th><th>Initial Marking $M_0(P_{ci})$</th><th>Incidence Vector $C(P_{ci}, .)$</th></tr></thead><tbody><tr><td rowspan="2">$R_1$</td><td>$P_{c1}$</td><td>1</td><td>(-1, -2, 0, 1, 2)</td></tr><tr><td>$P_{c2}$</td><td>1</td><td>(-2, 0, 0, 0, 0)</td></tr><tr><td rowspan="2">$R_2$</td><td>$P_{c1}$</td><td>1</td><td>(0, -2, 0, 0, 0)</td></tr><tr><td>$P_{c2}$</td><td>1</td><td>(-2, -2, 0, 0, 1)</td></tr><tr><td rowspan="2">$R_3$</td><td>$P_{c1}$</td><td>3</td><td>(-1, -2, 0, 1, 2)</td></tr><tr><td>$P_{c2}$</td><td>1</td><td>(0, -1, 0, 0, 1)</td></tr></tbody></table>

As a result, one can infer that our new control policy translated by $R_3$ can drastically reduce the encountered difficulties in solving the TR in control synthesis.

## 5.2. Huang and Pan Example 2

This PN example (see Figure 7) is taken from [22]. Based on Table 6, four MTSI conditions and 27 markings are necessary to be processed if *HP* is used. On the other side, our control policy also needs four MTSI conditions but does not generate any markings. It is obvious that three PN monitors are calculated to control this example with the *HP* approach against three, four and three control places for $R_1$, $R_2$, and $R_3$, respectively. The controlled system net was obtained with the four methods and is shown in Table 7. The main advantage of the $R_3$ algorithm is the gain of the computation time, which was decreased from 15,500 ms to 6700 ms. Indeed, without RG generation, one can design the same number of PN controllers using the theory of regions. Another important factor for the comparison of the four methods is not listed in Table 6; the *HP* approach does not consider uncontrollable transitions in the used PN models, which is a weakness in this work. As a result, one can conclude that our new control policy is the most efficient among *HP* method.
<figure><img src="image_11.png" /><figcaption>Figure 7. Huang and Pan example 2.</figcaption></figure>

<table><caption>**Table 6.** Comparison results of example 2.</caption><thead><tr><th>Control Criteria</th><th>No. of PN Controllers</th><th>No. of Markings in the RG</th><th>Maximally Permissive</th><th>No. of MTSI</th><th>Computation Time (ms)</th><th>Approach</th></tr></thead><tbody><tr><td>R<sub>1</sub></td><td>3</td><td>20</td><td>Yes</td><td>10</td><td>13,245</td><td>Minimal Cuts</td></tr><tr><td>R<sub>2</sub></td><td>4</td><td>20</td><td>Yes</td><td>10</td><td>13,400</td><td>Canonic markings</td></tr><tr><td>HP</td><td>3</td><td>27</td><td>Yes</td><td>4</td><td>15,500</td><td>RG based</td></tr><tr><td>R<sub>3</sub></td><td>3</td><td>0</td><td>Yes</td><td>4</td><td>6700</td><td>Without RG</td></tr></tbody></table>

<table><caption>**Table 7.** Petri net controllers of example 2.</caption><thead><tr><th>Method</th><th>Additional Control Places</th><th>Initial Marking M<sub>0</sub>(P<sub>ci</sub>)</th><th>Incidence Vector C(P<sub>ci</sub>)</th></tr></thead><tbody><tr><td rowspan="3">R<sub>1</sub></td><td>P<sub>c1</sub></td><td>0</td><td>(-2, 0, 0, 0, 0)</td></tr><tr><td>P<sub>c2</sub></td><td>0</td><td>(0, -2, 0, 0, 0)</td></tr><tr><td>P<sub>c3</sub></td><td>0</td><td>(0, 0, -2, 0, 0)</td></tr><tr><td rowspan="4">R<sub>2</sub></td><td>P<sub>c1</sub></td><td>1</td><td>(0, 0, 0, 0, -2, 0)</td></tr><tr><td>P<sub>c2</sub></td><td>1</td><td>(0, 0, 0, -2, 0, 0)</td></tr><tr><td>P<sub>c3</sub></td><td>1</td><td>(0, 0, 0, -2, -2, 0)</td></tr><tr><td>P<sub>c4</sub></td><td>1</td><td>(0, -2, -2, 0, 0, 0)</td></tr><tr><td rowspan="3">HP</td><td>P<sub>c1</sub></td><td>2</td><td>(0, -1, 1, 0, 1, -1)</td></tr><tr><td>P<sub>c2</sub></td><td>3</td><td>(-1, 1, -1, 0, 1, 0)</td></tr><tr><td>P<sub>c3</sub></td><td>2</td><td>(-1, 1, 0, 1, -1, 0)</td></tr><tr><td rowspan="3">R<sub>3</sub></td><td>P<sub>c1</sub></td><td>3</td><td>(0, -2, 2, 0, 2, -2)</td></tr><tr><td>P<sub>c2</sub></td><td>4</td><td>(-2, 2, -2, 0, 2, 0)</td></tr><tr><td>P<sub>c3</sub></td><td>3</td><td>(-2, 2, 0, 2, -2, 0)</td></tr></tbody></table>

### 5.3. Ghaffari et al. Example 3

The last PN example (see Figure 8) is taken from [10], which presents the forbidden state transition problem (FSTP) problem using the classical policy of the theory of regions to control a real flexible manufacturing system. The PN model considers the liveness requirement and uncontrollable transitions. Based on the experiment results in Table 8, 215 markings are needed to solve seven MTSI conditions if one uses the G approach in this example. In addition, the reduced technology is involved in $R_1$ and $R_3$. For both these control methods, we need to handle 120 or 0 markings which prove the big reduction of PN supervisor computation time decreasing from 29,150 ms to 14,450 ms and
9960 ms for $R_1$ and $R_3$, respectively. Moreover, one can remark in this example that for the same number of control places in G and $R_3$ methods, one can control the net system and satisfy the control specifications without needing to generate the graph/markings and with less calculation time for the controllers. The controlled system net of example 3 was obtained with three methods and is shown in Table 9. To summarize, our control policy $R_3$ is still the best computationally control algorithm among existing methods.

<figure><img src="image_12.png" /><figcaption>Figure 8. Ghaffari example 3.</figcaption></figure>

<table><caption>Table 8. Comparison results of example 3.</caption><thead><tr><th>Control Criteria</th><th>No. of PN Controllers</th><th>No. of Markings in the RG</th><th>Maximally Permissive</th><th>No. of MTSI</th><th>Computation Time (ms)</th><th>Approach</th></tr></thead><tbody><tr><td>$R_1$</td><td>4</td><td>120</td><td>Yes</td><td>12</td><td>14,450</td><td>Minimal Cuts</td></tr><tr><td>G</td><td>3</td><td>215</td><td>Yes</td><td>7</td><td>29,150</td><td>RG based</td></tr><tr><td>$R_3$</td><td>3</td><td>0</td><td>Yes</td><td>7</td><td>9960</td><td>Without RG</td></tr></tbody></table>

<table><caption>Table 9. Petri net controllers of example 3.</caption><thead><tr><th>Method</th><th>Additional Control Places</th><th>Initial Marking $M_0(P_{ci})$</th><th>Incidence Vector $C(P_{ci})$</th></tr></thead><tbody><tr><td rowspan="4">$R_1$</td><td>$P_{c1}$</td><td>3</td><td>(0, -2, 0, 0, 0, 0, 0, 0, 0)</td></tr><tr><td>$P_{c2}$</td><td>3</td><td>(0, 0, 0, 0, -2, 0, 0, 0, 0, 0)</td></tr><tr><td>$P_{c3}$</td><td>3</td><td>(0, 0, 0, 0, 0, 0, 0, 0, -2)</td></tr><tr><td>$P_{c4}$</td><td>2</td><td>(0, 0, 0, 0, 0, 0, 0, 0, -2, 0)</td></tr><tr><td rowspan="3">G</td><td>$P_{c1}$</td><td>2</td><td>(0, -1, 0, 0, 1, 0, 0, 0, 0, 1, -1)</td></tr><tr><td>$P_{c2}$</td><td>2</td><td>(0, 0, -1, 0, 1, 0, 0, 0, 1, -1, 0)</td></tr><tr><td>$P_{c3}$</td><td>3</td><td>(0, 0, 0, 0, -1, 1, 0, 0, 0, 1, -1)</td></tr><tr><td rowspan="3">$R_3$</td><td>$P_{c1}$</td><td>3</td><td>(0, -2, 0, 0, 2, 0, 0, 0, 0, 2, -2)</td></tr><tr><td>$P_{c2}$</td><td>3</td><td>(0, 0, -2, 0, 2, 0, 0, 0, 2, -2, 0)</td></tr><tr><td>$P_{c3}$</td><td>4</td><td>(0, 0, 0, 0, -2, 2, 0, 0, 0, 2, -2)</td></tr></tbody></table>

## 6. Conclusions and Perspectives

In this paper, a new control policy was proposed to design an optimal PN controller by avoiding generating the reachability graph. Indeed, based on structural properties of PNs and mathematical concepts, the controller was designed. Thus, the computing time of the supervisor was reduced,
and then one can control the system constraints in a timely manner. Consequently, the production and the security will be directly affected.

The proposed methodology was implemented in our flexible manufacturing system. The results analysis shows that our algebraic method using Petri nets is more effective than previous works based on the theory of regions. Indeed, for the same number of controllers, one can supervise the system under less computational burden. The steps of generation and analysis of the reachability graph are skipped in the control process, which allowed us to reduce the computation time using CPLEX software.

Moreover, the proposed approach always generates the minimal number of MTSIs, since the application of the theory of regions is confined on the calculated paths and not on the reachability graph. Therefore, it reflects a great reduction of the resolution complexity of the TR and prevents a possible combinatorial explosion of states when the complexity of the system increases.

Based on experimental results, it is self-evident to remark the considerable reduction of the computation cost of the TR. Thus, our new method can obtain an optimal maximally permissive supervisor for bounded Petri nets.

Hence, in the near future, how to obtain blocking states without calculating the reachability graph is to become an important issue in the control synthesis field. Our team is working on this project from the perspective of this model.

**Author Contributions:** The authors of this paper are specialists in the industrial engineering field and more precisely in the supervision of discrete event systems and preventive/corrective maintenance for systems. Conceptualization, S.R., S.T., and N.R.; Methodology, S.T.; Software, S.R.; Validation, S.R., S.T., and N.R.; Formal analysis, S.T.; Investigation, S.R.; Resources, N.R.; Data curation, N.R.; Writing—original draft preparation, S.R.; Writing—review and editing, S.R.; Visualization, S.T.; Supervision, N.R.; Project administration, N.R.; Funding acquisition, N.R.

**Funding:** This research received no external funding.

**Acknowledgments:** Our teamwork want to thank the entire MDPI team and the reviewers for reviewing our article entitled: Compute Optimization of Petri Net Controllers using the Algebraic Method. We would also like to thank everyone in our laboratory, LGIPM, who contributed in this work with their continued support and efforts.

**Conflicts of Interest:** The authors: Sadok Rezig, Sadok Turki, and Nidhal Rezg declare no conflict of interest.

## Abbreviations

<table><tr><td>DES</td><td>Discrete event systems</td></tr><tr><td>FMS</td><td>Flexible manufacturing system</td></tr><tr><td>FSTP</td><td>Forbidden state transition problem</td></tr><tr><td>GMEC</td><td>Generalized mutual exclusion constraint</td></tr><tr><td>LSP</td><td>Linear system of paths</td></tr><tr><td>MTSI</td><td>Marking/transition separation instance</td></tr><tr><td>PN</td><td>Petri net</td></tr><tr><td>RG</td><td>Reachability graph</td></tr><tr><td>TR</td><td>Theory of regions</td></tr><tr><td>VG</td><td>Virtual graph</td></tr></table>

## References

1. Murata, T. Petri nets: Properties, analysis and applications. Proc. IEEE **1989**, *77*, 541–580. [CrossRef]

2. Ramadge, P.J.; Wonham, W.M. Modular supervisory control of discrete event systems. In *Analysis and Optimization of Systems*; Springer: Berlin/Heidelberg, Germany, 1986; pp. 202–214.

3. Ramadge, P.J.; Wonham, W.M. Supervisory control of a class of discrete event processes. SIAM J. Control Optim. **1987**, *25*, 206–230. [CrossRef]

4. Uzam, M.; Wonham, W.M. A hybrid approach to supervisory control of discrete event systems coupling RW supervisors to Petri nets. Int. J. Adv. Manuf. Technol. **2006**, *28*, 747–760. [CrossRef]
5. Dideban, A.; Alla, H. Determination of minimal sets of control places for safe Petri nets. In Proceedings of the ACC07 American Control Conference, New York, NY, USA, 11–13 July 2007; pp. 4975–4980.

6. Dideban, A.; Alla, H. Reduction of constraints for controller synthesis based on safe Petri nets. Automatica **2008**, *44*, 1697–1706. [CrossRef]

7. Liao, H.; Wang, Y.; Cho, H.K.; Stanley, J.; Kelly, T.; Lafortune, S.; Reveliotis, S. Concurrency bugs in multithreaded software: Modeling and analysis using Petri nets. Discret. Event Dyn. Syst. **2013**, *23*, 157–195. [CrossRef]

8. Nazeem, A.; Reveliotis, S.; Wang, Y.; Lafortune, S. Designing compact and maximally permissive deadlock avoidance policies for complex resource allocation systems through classification theory: The linear case. IEEE Trans. Autom. Control **2011**, *56*, 1818–1833. [CrossRef]

9. Ghaffari, A.; Rezg, N.; Xie, X. Algebraic and geometric characterization of Petri net controllers using the theory of regions. In Proceedings of the Sixth International Workshop on Discrete Event Systems, Zaragoza, Spain, 2–4 October 2002; pp. 219–224.

10. Ghaffari, A.; Rezg, N.; Xie, X. Design of a live and maximally permissive Petri net controller using the theory of regions. IEEE Trans. Robot. Autom. **2003**, *19*, 137–141. [CrossRef]

11. Ghaffari, A.; Rezg, N.; Xie, X. Live and maximally permissive controller synthesis using theory of regions. In *Synthesis and Control of Discrete Event Systems*; Springer: New York, NY, USA, 2002; pp. 155–166.

12. Ghaffari, A.; Rezg, N.; Xie, X. Feedback control logic for forbidden-state problems of marked graphs: Application to a real manufacturing system. IEEE Trans. Autom. Control **2003**, *48*, 18–29. [CrossRef]

13. Ye, J.; Zhou, M.; Li, Z.; Al-Ahmari, A. Structural decomposition and decentralized control of Petri nets. IEEE Trans. Syst. Man Cybern. Syst. **2017**, *48*, 1360–1369. [CrossRef]

14. Balduzzi, F.; Giua, A.; Menga, G. First-order hybrid Petri nets: A model for optimization and control. IEEE Trans. Robot. Autom. **2000**, *16*, 382–399. [CrossRef]

15. Cavone, G.; Dotoli, M.; Seatzu, C. Management of intermodal freight terminals by first-order hybrid Petri nets. IEEE Robot. Autom. Lett. **2015**, *1*, 2–9. [CrossRef]

16. Zhou, M. (Ed.) *Petri Nets in Flexible and Agile Automation*; Springer Science & Business Media: New York, NY, USA, 2012; Volume 310.

17. Chen, Y.; Li, Z.; Khalgui, M.; Mosbahi, O. Design of a maximally permissive liveness-enforcing Petri net supervisor for flexible manufacturing systems. IEEE Trans. Autom. Sci. Eng. **2011**, *8*, 374–393. [CrossRef]

18. Zhao, M.; Uzam, M.; Hou, Y. A divide-and-conquer method for the synthesis of non-blocking supervisors for flexible manufacturing systems. In Proceedings of the 2014 IEEE International Conference on Automation Science and Engineering (CASE), Madison, WI, USA, 22 August 2014; pp. 455–460.

19. Uzam, M.; Li, Z.; Zhou, M. Identification and elimination of redundant control places in Petri net based liveness enforcing supervisors of FMS. Int. J. Adv. Manuf. Technol. **2007**, *35*, 150–168. [CrossRef]

20. Uzam, M.; Zhou, M. An improved iterative synthesis method for liveness enforcing supervisors of flexible manufacturing systems. Int. J. Prod. Res. **2006**, *44*, 1987–2030. [CrossRef]

21. Li, Z.; Zhao, M. On controllability of dependent siphons for deadlock prevention in generalized Petri nets. IEEE Trans. Syst. Man Cybern.-Part A Syst. Hum. **2008**, *38*, 369–384.

22. Huang, Y.S.; Pan, Y.L. An improved maximally permissive deadlock prevention policy based on the theory of regions and reduction approach. IET Control Theory Appl. **2011**, *5*, 1069–1078. [CrossRef]

23. Uzam, M.; Gelen, G. The real-time supervisory control of an experimental manufacturing system based on a hybrid method. Control Eng. Pract. **2009**, *17*, 1174–1189. [CrossRef]

24. Park, J.; Reveliotis, S.A. Deadlock avoidance in sequential resource allocation systems with multiple resource acquisitions and flexible routings. IEEE Trans. Autom. Control **2001**, *46*, 1572–1583. [CrossRef]

25. Rezig, S.; Achour, Z.; Rezg, N. Control synthesis based on reachability graph with minimal cuts: Application to a flexible manufacturing system. In Proceedings of the 2014 IEEE Emerging Technology and Factory Automation (ETFA), Barcelona, Spain, 16–19 September 2014; pp. 1–6.

26. Rezig, S.; Achour, Z.; Rezg, N.; Kammoun, M.A. Optimal control synthesis for a flexible manufacturing system based on minimal cuts. In Proceedings of the 2014 IEEE International Conference on Industrial Engineering and Engineering Management, Malaysia, 9–12 December 2014; pp. 254–258.

27. Rezig, S.; Achour, Z.; Rezg, N. Theory of Regions for Control Synthesis without Computing Reachability Graph. Appl. Sci. **2017**, *7*, 270. [CrossRef]
28. Rezig, S.; Achour, Z.; Rezg, N.; Kammoun, M.A. Supervisory control based on minimal cuts and Petri net sub-controllers coordination. *Int. J. Syst. Sci.* **2016**, *47*, 3425–3435. [CrossRef]

29. Rezig, S.; Achour, Z.; Rezg, N. Control Synthesis Based On Theory of Regions with Minimal Reachability Graph Knowledge. *IFAC-PapersOnLine* **2016**, *49*, 1383–1388. [CrossRef]

30. Giua, A.; DiCesare, F.; Silva, M. Generalized mutual exclusion contraints on nets with uncontrollable transitions. In Proceedings of the 1992 IEEE International Conference on Systems, Man and Cybernetics, Chicago, IL, USA, 18–21 October 1992; pp. 974–979.

<figure><img src="image_13.png" /></figure>

© 2019 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (http://creativecommons.org/licenses/by/4.0/).