Closed Loop Control Approaches for Conflicted Timed Event Graphs Subject to Constraints with Dioid Algebra

Abstract

In this chapter, we are going to tackle the control of a particular class of Discreet Event systems, which is the subclass of Conflicted Timed Event Graphs with the use of Dioid Algebra (Min, +). The main proposed approaches concern systems including sharing phenomena and are subject to various constraints such as time, capacity, and mixed constraints. For that, we establish a convenient switching policy according to a specific allocation order, and we compute suitable control laws that guarantee the proper system functioning while ensuring the respect of its constraints.

1. Introduction

For Discrete Event Systems, resource sharing could be a problem. Therefore, time and space compliance is crucial, and a loss of time and space results when the right control decision is not made, especially when various constraints exist. For this reason, the allocation of shared resources for Timed Event Graphs (TEGs) between several processes can be transformed into a switching system control problem that is modeled using the (Min, +) algebra. As this type of system could contain a finite number of states, then it belongs consequently to the class of Discrete Event Systems (DES), the object of our study.

This chapter book takes place among the investigations and the studies in order to establish control approaches for Discrete Event Systems [1, 2, 3, 4]. In several industrial processes, both time and capacity factors are critical conditions that affect the evolution of Discrete Events, especially when resource-sharing phenomenons arise, which urges us to define a suitable modeling adapted to their nature and following switching operational modes.

To do this, we have placed ourselves in relation to the works done with the use of the same tools in order to establish an adapted state of the art to our purposes. We have been able to improve some approaches by relaxing some limiting assumptions, and the new approaches established preserve the liveliness of Timed Event Graphs by avoiding dead loops without tokens [5, 6]. An effective switching policy is introduced to organize the access to the shared resource. Switching (Min, +) models are then adapted, computed, and used to solve the control problem under the existence of constraints. We have established an adapted control policy according to a sequence of active modes of competing graphs and defined according to an operating plan. For our case study, we were interested not only in mixed modes but also in conservative modes for which the same graph within a mode can exclusively appropriate the resource allocation.

Original (Min, +) control synthesis is detailed in the case of the existence of a single marking constraint on one of the CTEG’s places, which is after that generalized to the case of multiple marking constraints, and we have also dealt with the problem of possible mixed constraints of both time and capacity. The design of control laws that satisfy these requirements is therefore an important step, and sufficient conditions for the satisfaction of these constraints have been deduced.

2. Modeling of CTEGs

To model the sharing phenomenon between CTEGs, we first study the switching behavior of these systems. Their evolution is described by the succession of modes, which constitutes a switching sequence defining the resource allocation of a particular process, whereby the organization of modes within a sequence is already fixed by the production plan. In the following section, we give some basic definitions.

2.1 Definitions

A Conflicted Timed Event Graph is defined by $N\in {\mathrm{\mathbb{N}}}^{\ast }\backslash \left\{1\right\}$ Timed Event Graphs of type SISO.

A mode is a selection of a number of $N$ Timed Event Graphs competing to win the allocation of the shared resource.

A sequence, denoted by S, is a set of modes whose order is fixed according to a particular operational need.

Remark 3.1: In our study, the possession of the resource token can be considered by the same Timed Event Graph in a mode. This means that we are in a conservative mode. In the case where different Timed Event Graphs are in competition within the same mode, it is called a mixed mode.

2.2 Hypotheses

• $N$ defines the number of concurrent SISO Timed Event Graphs (users) such that $N>1$.

• Taking as $K$ the number of shared resources, in order to respect the competition criteria, we consider the following condition $K<N$.

• Since the periodic allocation of the shared conflict place depends on the order of the modes in the sequence, it results in a periodic Conflicted Timed Event Graph.

• The token in the conflict place is consumed only once by a single graph. In terms of Petri nets when this place is not marked, it means that there is only one active elementary circuit in possession of the resource.

• We consider a maximum transition firing speed rate.

• For each internal transition $t_i$ of the CTEG, a counter function noted ${\theta }_i$ is associated, and for each source transition noted $t_{u_i}$, a resource transition noted $u_i^k$ is associated, where K is the mode index.

2.3 (Min, +) switching model of a CTEG

Most of the works dealing with control of Petri nets, under marking constraints, have not taken into account the time parameter in the modeling phase or in the control synthesis phase. Despite the fundamental role of the time factor, a few studies have dealt with the control of SEDs modeled by timed Petri nets.

For the example of the TEG shown in Figure 1, we observe that three Timed Event Graphs (users) compete to win the resource allocation in one mode. Furthermore, we provide the rules for managing the switching between the different modes to validate the allocation of the shared resource. As defined earlier, a mode can contain a number of competing graphs. The activation logic of the transitions follows the order of the selected graphs, such that only the upstream and downstream transitions of the shared resource are concerned on the modeling step.

Figure 1.

Highlighting the conflict at the level of the shared resource ${\tilde{p}}_1$.

We highlight the modeling step of the GETC, especially at the shared resource level; see Figure 1. For this, we chose the operational mode $M_k\left(G_n{G}_{n+1}\right)$ where $k$ is the mode index. Thus, the activation of the mode systematically leads to the possession of the token by the first graph noted $G_n$ (respectively with its upstream and downstream transitions linked to the shared resource). After having been used for a certain time $\tau$, the resource will be available for the graph $G_{n+1}$, and the token will thus be distributed by the output transition $t_k$ to the input transition $t_i$ of this mode (the other arcs connected to the resource with other transitions will not be considered by the modeling step).

Referring to [7] and by analogy to TEGs, the modeling of GETC is based on the swap/switch between TEGs under the switching model approach.

Remark 1: Each defined mode is associated with a switching model (Min, +). The dynamic evolution equation corresponding to the activation of the mode is noted by $M_k$ in the sequence $S,$ and it is defined by the following equation:

$$x_x\left(t\right)=A_x.x\left(t-1\right)\oplus B_x{u}_x\left(t\right)$$E1

Where $x$ represents the index of the corresponding switching model (Min, +), we have:

$A_x\in {\mathbb{R}}_{\min }^{n\ast n}$ is the state matrix of the mode $k$.

$B_x\in {\mathbb{R}}_{\min }^{n\ast m}$ is the control matrix of the mode $k$.

$u_x$ is the control vector of the mode $k$.

$n$ is the number of all internal transitions, and $m$ is the number of source transitions.

Example: In Figure 2, the CTEG is composed of 3 Timed Event Graphs respectively given by: GET 1, GET 2, and GET 3. The resource allocation given by the sequence $S$ as follows:

Figure 2.

An example of three TEGs (TEG1, TEG2, and TEG3) sharing a conflict place ${\tilde{p}}_1$.

$$S=M_1{M}_2$$E2

Considering a maximum firing speed, the first mode $M_1$ is defined by $M_1\left(G_1{G}_3\right)$; the resource occupation of ${\tilde{p}}_1$ is interpreted by a token moving for the activation of the graph $G_1$ then the graph $G_3$. The counter functions associated with the source transitions $t_{u_1}$ and $t_{u_2}$ are respectively $u_1^1$ and $u_3^1$. ${\theta }_i$ indicates the counter function that corresponds to the CTEG transitions $t_i$, such that $i=1,\dots ,8.$

The modeling steps consist of determining the equations of the system constituted by counter functions associated to each transition.

To obtain the linear (Min, +) model and for more clarity sakes, it is recommended to make these changes; we replace “Min” by “$\oplus$” and “+” by “.”, and one obtains, consequently, the following system of (Min, +) linear equations:

$$\left\{\begin{array}{l}{\theta }_1\left(t\right)=e.u_1^1\left(t\right)\oplus 2.{\theta }_2\left(t-1\right)\\ {\theta }_2\left(t\right)=e.{\theta }_1\left(t-1\right)\\ {\theta }_3\left(t\right)=1.u_2^1\left(t\right)\\ {\theta }_4\left(t\right)=e.{\theta }_3\left(t-1\right)\oplus 1.{\theta }_8\left(t\right)\\ {\theta }_5\left(t\right)=1.{\theta }_4\left(t\right)\\ {\theta }_6\left(t\right)=e.u_3^1\left(t\right)\\ {\theta }_7\left(t\right)=e.{\theta }_6\left(t-1\right)\\ {\theta }_8\left(t\right)=1.{\theta }_7\left(t-1\right)\end{array}\right.$$E3

When the system switches the mode from $M_1$ to $M_2$, the model also changes. For the second mode $M_2\left(G_3{G}_2\right)$, we obtain the following system of (Min, +) equations:

$$\left\{\begin{array}{l}{\theta }_1\left(t\right)=e.u_1^2\left(t\right)\oplus 2.{\theta }_2\left(t-1\right)\\ {\theta }_2\left(t\right)=e.{\theta }_1\left(t-1\right)\\ {\theta }_3\left(t\right)=1.u_2^2\left(t\right)\\ {\theta }_4\left(t\right)=e.{\theta }_3\left(t-1\right)\oplus 1.{\theta }_8\left(t\right)\\ {\theta }_5\left(t\right)=1.{\theta }_4\left(t\right)\\ {\theta }_6\left(t\right)=e.u_3^2\left(t\right)\\ {\theta }_7\left(t\right)=e.{\theta }_6\left(t-1\right)\\ {\theta }_8\left(t\right)=1.{\theta }_7\left(t-1\right)\end{array}\right.$$E4

After determining the switching models (Min, +) corresponding to these modes, we provide the state space representations associated with each one as follows:

For $M_1\left(G_1{G}_3\right)$, we have:

$$x_1\left(t\right)=\left[\begin{array}{cccccccc}\epsilon & \epsilon & 2& \epsilon & \epsilon & \epsilon & \epsilon & \epsilon \\ e& \epsilon & \epsilon & \epsilon & \epsilon & \epsilon & \epsilon & \epsilon \\ \epsilon & 1& \epsilon & \epsilon & \epsilon & \epsilon & \epsilon & \epsilon \\ \epsilon & \epsilon & e& \epsilon & \epsilon & \epsilon & \epsilon & \epsilon \\ \epsilon & \epsilon & 2& \epsilon & \epsilon & \epsilon & \epsilon & \epsilon \\ \epsilon & \epsilon & \epsilon & \epsilon & \epsilon & \epsilon & \epsilon & \epsilon \\ \epsilon & \epsilon & \epsilon & \epsilon & \epsilon & \epsilon & \epsilon & \epsilon \\ \epsilon & \epsilon & \epsilon & \epsilon & \epsilon & e& \epsilon & \epsilon \end{array}\right].x\left(t-1\right)\oplus \left[\begin{array}{ccc}e& \epsilon & \epsilon \\ \epsilon & \epsilon & \epsilon \\ \epsilon & 1& \epsilon \\ \epsilon & \epsilon & \epsilon \\ \epsilon & \epsilon & \epsilon \\ \epsilon & \epsilon & e\\ \epsilon & \epsilon & \epsilon \\ \epsilon & \epsilon & \epsilon \end{array}\right].u\left(t\right)$$E5

And for the second mode $M_2\left({\mathrm{G}}_2{\mathrm{G}}_3\right),$ the following state space equation is achieved:

$$x_2\left(t\right)=\left[\begin{array}{cccccccc}\epsilon & 2& \epsilon & \epsilon & \epsilon & \epsilon & \epsilon & \epsilon \\ e& \epsilon & \epsilon & \epsilon & \epsilon & \epsilon & \epsilon & \epsilon \\ \epsilon & \epsilon & \epsilon & \epsilon & \epsilon & \epsilon & \epsilon & \epsilon \\ \epsilon & \epsilon & e& \epsilon & \epsilon & \epsilon & 2& \epsilon \\ \epsilon & \epsilon & 1& \epsilon & \epsilon & \epsilon & \epsilon & \epsilon \\ \epsilon & \epsilon & \epsilon & \epsilon & \epsilon & \epsilon & \epsilon & \epsilon \\ \epsilon & \epsilon & \epsilon & \epsilon & \epsilon & e& \epsilon & \epsilon \\ \epsilon & \epsilon & \epsilon & \epsilon & \epsilon & \epsilon & 1& \epsilon \end{array}\right].x\left(t-1\right)\oplus \left[\begin{array}{ccc}e& \epsilon & \epsilon \\ \epsilon & \epsilon & \epsilon \\ \epsilon & \epsilon & \epsilon \\ \epsilon & \epsilon & \epsilon \\ \epsilon & \epsilon & \epsilon \\ \epsilon & \epsilon & \epsilon \\ \epsilon & 1& \epsilon \\ \epsilon & \epsilon & \epsilon \end{array}\right]u\left(t\right)$$E6

3. Formulation of the control problem

Space constraints are crucial factors that are often considered in the context of the Petri net formalism. Our main objective is to find efficient controllers to optimize this constraint by limiting the number of tokens in certain places and that is depending on the system needs. These places could be assimilated to stations in transportation networks or to limited stock areas in industrial contexts. The marking constraints are expressed by linear inequalities.

In the same context, among some recent contributions, we can mention [8], where the authors addressed the control design problem to synthesize a causal control feedback that serves to satisfy the capacity constraints in a single place as well as in a sequence of places. In this sense, they tried to establish relaxed adaptive assumptions by assuming that each linear marking constraint only affects a single place or places located on the same path within the TEG.

Through this section, we will give some hypotheses in order to solve the problem of undesirable situations related to capacity constraints (whatever the place) for a large and complex case of Timed Petri nets, which is Conflicting Timed Event Graphs. To do so, it is necessary to explain some interesting concepts.

In the following sections, after introducing the marking constraint, we will proceed first by the control synthesis formulation for the case of a single constraint before extending to the case of multiple constraints.

3.1 Marking constraint

An accessible marking vector represents the dynamical behavior of Petri nets. Forbidden states are markings that can be determined, but they are at the same time still forbidden by specifications imposed to the system.

Since capacity is not only a cost-of-space issue but also a price issue, we spend a lot of time finding control law that respects this critical constraint.

For a TEG modeled through the DES class, we assume that a place $p_{\mathit{ij}}$ is exposed to a capacity constraint. Thus, regardless of context necessity, there is a finite number of tokens that must not be exceeded.

For the place $p_{\mathit{ij}}$, $M_{\mathit{ij}}\left(t\right)$ denotes the marking of this place until $t$ time, which is expressed by the following inequality:

$$M_{\mathit{ij}}\left(t\right)=x_j\left(t\right)-x_i\left(t\right)+M_{\mathit{ij}0}$$E7

Where $x_i\left(t\right)$ and $x_j\left(t\right)$ are, respectively, the counter functions of the input and output transitions related to this place. The first counter function $x_i\left(t\right)$ represents the number of transitions firing from the transition start time $t_j$ to $t$ time. Thus, $x_j\left(t\right)$ defines the sum of input tokens, and $x_i\left(t\right)$ defines the sum of output tokens.

In the case of marking constraint, the final marking of this place from an initial marking $M_{\mathit{ij}0}$ must not exceed a certain threshold noted $b$. Eq. (7) can thus be reduced through (Min, +) algebra to the following inequality, which represents the marking constraint that we seek to satisfy:

$$x_j\left(t\right)\le \left(b-M_{\mathit{ij}0}\right).x_i\left(t\right)$$E8

Given the explicit equation of state representation: $x\left(t\right)=A.x\left(t-1\right)\oplus B.u\left(t\right)$ such that we have $A={\widehat{A}}_0^{\ast }.{\widehat{A}}_1$ and $B={\widehat{A}}_0^{\ast }.\widehat{B}$, its equivalent equation is given by the following equation:

$$x\left(t\right)=A^{\tau }.x\left(t-\tau \right)\oplus \left[\underset{k=0}{\overset{\tau -1}{\oplus }}{A}^k.B.u\left(t-k\right)\right],\text{Such}\mathrm{as}\tau \ge 1$$E9

If we substitute $\tau =\varphi$ in Eq. (9), we could establish the following explicit expression:

$$x_i\left(t\right)=\left[\underset{r=1}{\overset{n}{\oplus }}{\left(A^{\varphi }\right)}_{\mathit{ir}}{x}_r\left(t-\varphi \right)\right]\oplus \left[\underset{k=0}{\overset{\varphi -1}{\oplus }}{\left(A^k.B\right)}_i.u\left(t-k\right)\right],\varphi \ge 1,\text{and}A\in {\overline{\mathbb{R}}}_{\min }^{n\times n}$$E10

Where $n$ represents the number of internal transitions of CTEG, and ${\left(A^{\varphi }\right)}_{\mathit{ir}}$ denotes the $i^{\mathit{th}}$ components of the matrix.

For each path in CTEG the selected mode, we define by ${\tau }_{{\alpha }_n}$ the sum of all delays for each TEG connecting the source transition to the upstream transition of the constrained place. We denote by $n$ the graph number.

$$x_{j_n}\left(t\right)\le {\left(A^{{\tau }_{{\alpha }_n}}B\right)}_{j_n}{u}_x\left(t-{\tau }_{{\alpha }_n}\right),\forall N\in {\mathrm{\mathbb{N}}}^{\ast }\backslash \left\{1\right\}$$E11

By replacing the two Eqs. (10) and (11) in Eq. (9), we obtain the following expression:

$${\left(A^{{\tau }_{{\alpha }_n}}B\right)}_{j_n}{u}_x\left(t-{\tau }_{{\alpha }_n}\right)\le \left(b-M_{\mathit{ij}0}\right).\left[\underset{r=1}{\overset{n}{\oplus }}{\left(A^{\varphi }\right)}_{i_{n}r}{x}_r\left(t-\varphi \right)\right]\oplus \left[\underset{k=0}{\overset{\varphi -1}{\oplus }}{\left(A^k.B\right)}_{i_n}.u\left(t-k\right)\right]$$E12

We see that the satisfaction of the above inequality induces the simultaneous satisfaction of the following two inequalities:

$${\left(A^{{\tau }_{{\alpha }_n}}B\right)}_{j_n}{u}_x\left(t-{\tau }_{{\alpha }_n}\right)\le \left(b-M_{\mathit{ij}0}\right)\left[\underset{k=0}{\overset{\varphi -1}{\oplus }}{\left(A^k.B\right)}_{i_n}.u\left(t-k\right)\right]$$E13

$${\left(A^{{\tau }_{{\alpha }_n}}B\right)}_{j_n}{u}_x\left(t-{\tau }_{{\alpha }_n}\right)\le \left(b-M_{\mathit{ij}0}\right)\left[\underset{r=1}{\overset{n}{\oplus }}{\left(A^{\varphi }\right)}_{i_{n}r}{x}_r\left(t-\varphi \right)\right]$$E14

These inequalities could also be formulated as follows:

$${\left(A^{{\tau }_{{\alpha }_n}}B\right)}_{j_n}{u}_x\left(t-{\tau }_{{\alpha }_n}\right)\le \left(b-M_{\mathit{ij}0}\right)\left[\underset{k=0}{\overset{\varphi -1}{\oplus }}{\left(A^k.B\right)}_{i_n}.u\left(t-k\right)\right]$$E15

$$u_x\left(t-{\tau }_{{\alpha }_n}\right)\le \left(b-M_{\mathit{ij}0}-{\left(A^{{\tau }_{{\alpha }_n}}B\right)}_{j_n}\right)\left[\underset{r=1}{\overset{n}{\oplus }}{\left(A^{\varphi }\right)}_{i_{n}r}{x}_r\left(t-\varphi \right)\right]$$E16

3.2 Control synthesis in the case of a single marking constraint

In this section, we address the problem resolution of control of CTEGs, having a safe shared resource for which we will start with the case of a single marking constraint.

Theorem 1: A CTEG consisting of $N$ TEGs, whose evolution is given by the explicit equation of state representation (1), sharing a safe resource noted ${\tilde{p}}_1$ and subject to a single capacity constraint of the form (8), admits a control law $u\left(t\right)$ of the form:

$$u\left(t\right)=\underset{1}{\overset{n}{\oplus }}F.x\left(t-1\right)$$E17

Like:

$F=\left(b-M_{\mathit{ij}0}-{\left(A^{{\tau }_{{\alpha }_n}}B\right)}_{j_n}\right).A^{\varphi }$ such that $\varphi ={\tau }_{{\alpha }_n}+1$; $F\ge e$.

If the following $N$ conditions are true:

$${\left(A^{{\tau }_{{\alpha }_n}}B\right)}_{j_n}\le \left(b-M_{\mathit{ij}0}\right).{\left(A^k.B\right)}_{i_n}k=0,\dots ,{\tau }_{{\alpha }_n}$$E18

Proof is provided in [9].

3.3 Control synthesis for the case of multiple marking constraints

In this section, we deal with a more complex case, where multiple users are competing to win the resource allocation. In addition to this complexity criterion that could be cumulated especially with the presence of multiple marking constraints. Therefore, we admit that for a CTEG, multiple constraints could emerge for each $n$ SISO TEG. We assume that there are $Z$ capacity constraints applied to some places belonging to the Timed Event Graph of $n$ index, and they are noted $p_{s_n}.$ For each constrained place, we note respectively the following notations: $M_{{\mathit{sn}}_0}$ is the initial marking, $t_{\mathit{zn}}$ and $t_{z\text{'}n}$ are the delays, and they are corresponding to the input and output transitions of the place $p_{s_n}$. $x_{\mathit{zn}}{x}_{z\text{'}n}$ are the counter functions corresponding to these transitions. We denote by ${\alpha }_{s_n}$ the path connecting the control transition to the input transition of the constrained place. ${\tau }_{{\alpha }_{s_n}}$ is the sum of the delays through this path.

We denote the expression of marking constraints by the following inequality:

$$x_{\mathit{zn}}\left(t\right)\le \left(b_n-M_{{\mathit{sn}}_0}\right).x_{z\text{'}n}\left(t\right)\text{with}{b}_n\in \mathrm{\mathbb{N}}$$E19

Theorem 2: A CTEG consists of $N$ TEGs, whose evolution is given by Eq. (1), sharing a safe resource noted as ${\tilde{p}}_1$. It is object of multiple capacity constraints of the form (19), and it admits a global control law of the form:

$$u\left(t\right)=\underset{z=1}{\overset{Z}{\oplus }}{u}_z\left(t\right)$$E20

Having for the z constraint a control law denoted as $u_z\left(t\right)=F_z.x\left(t-1\right)$ such that $F_z=\left(b-M_{\mathit{ij}0}-{\left(A^{{\tau }_{{\alpha }_n}}B\right)}_{j_n}\right).A^{{\tau }_{{\alpha }_n}+1}\left({z_n}^{\text{'}},:\right)$ is the feedback that ensures each constraint of the form (19), if the conditions of the form (18) are verified for each index $z^{\text{'}}n$ and $\mathit{zn}$ of the constrained place $p_{s_n}$, with ${\varphi }_s={\tau }_{\alpha s_n}+1$ for $s=1,\dots ,S.$

Proof is provided in [9].

3.4 Closed-loop control with the (Min, +) algebra of timed Petri nets subject to mixed constraints

3.4.1 Time constraints

Temporal constraints are common restrictions for Discrete Event Systems, and their consideration during the control synthesis stage is a current problem that has motivated many researchers [1, 2, 3, 5, 10, 11, 12, 13, 14, 15, 16, 17, 18].

In this section, we are interested in the satisfaction of these constraints, more particularly in the critical time, especially in the case of tasks where the allocated time must be limited by a maximum bound ${\tau }_{\mathit{ij}}^{\max }$. Given a place denoted by $p_{\mathit{ij}}$, ${\tau }_{\mathit{ij}}^{\min }$ represents the minimal stay time of the token in this place. This is the time that is already taken in advance by the linear model. Since ${\tau }_{\mathit{ij}}^{\min }={\tau }_{\mathit{ij}}$, then ${\tau }_{\mathit{ij}}^{\max }$ is the additional time condition that we look to satisfy.

Referring to [19], the expression for the time constraint is derived. It is represented by the following inequality:

$$x_i\left(t\right)\ge m_{\mathit{ij}0}{x}_j\left(t-{\tau }_{\mathit{ij}}^{\max }\right)$$E21

3.4.2 Marking constraints

Petri net feature marking assigns a nonnegative integer number to the places that refers to number of existing tokens. It also defines the dynamic behavior of a given system that varies according to certain transition firing rules. The tokens are interpreted as available resources such as material storage capacity in storage areas, memory capacity in network communication systems, and products to be processed and that are occupying an industrial production line. In the literature, several attempts have been carried out for the synthesis of a control satisfying the marking constraints of different kinds and for particular Petri nets [4, 8, 20, 21, 22, 23]. However, each of these approaches suffers from a particular limitation.

We assume that the place illustrated in Figure 3 is subject to a mixed constraint. Let $m_{\mathit{ij}0}$ be its initial marking. $x_j\left(t\right)$ and $x_i\left(t\right)$ are, respectively, the counter functions associated with the transitions $t_j$ and $t_i$ until $t$ time. $m_{\mathit{ij}}$ is the marking available in the place $p_{\mathit{ij}}$ until $t$ time like $m_{\mathit{ij}}\in \left[e,b\right]$, which is equivalent to:

Figure 3.

Mixed constraints on the place $p_{\mathit{ij}}$.

$$m_{\mathit{ij}}\left(t\right)=x_j\left(t\right)-x_i\left(t\right)+m_{\mathit{ij}0}$$E22

According to [8], the marking is bounded as follows $m_{\mathit{ij}}\left(t\right)\le b$, and subsequently, we could get the following inequality:

$$x_j\left(t\right)-x_i\left(t\right)+m_{\mathit{ij}0}\le b$$E23

and that could be transformed to its equivalent inequality (Min, +) as follows:

$$x_j\left(t\right)\le \left(b-m_{\mathit{ij}0}\right).x_i\left(t\right)$$E24

4. Control formulation for TEGs with mixed constraints

In this section, we focus on the synthesis of appropriate control laws in the presence of mixed constraints on the places of the Timed Event Graphs. We start with the case of a single mixed constraint, and then, we generalize to the case of multiple constraints.

Considering the Eq. (9), we proceed by substituting the parameter $\tau$ by $\varphi$, and we the following equation:

$$x_i\left(t\right)=\left[\underset{r=1}{\overset{N}{\oplus }}{\left(A^{\varphi }\right)}_{\mathit{ir}}{x}_r\left(t-\varphi \right)\right]\oplus \left[\underset{k=0}{\overset{\varphi -1}{\oplus }}{\left(A^k.B\right)}_i.u\left(t-k\right)\right];\varphi \ge 1$$E25

With $A\in {\overline{\mathbb{R}}}_{\min }^{n\times n}$ and $B\in {\overline{\mathbb{R}}}_{\min }^{n\times m}$, like $n$ denotes the number of internal transitions, and $m$ is the number of resource transitions.

The matrix given by ${\left(A^{\varphi }\right)}_{\mathit{ir}}$ denotes the $r^{\mathit{th}}$ components of the $i$ row of the matrix $A^{\varphi }.$

To be more precise, we will opt for the notation $\varphi ={\varphi }_x$ in the case of the time constraint and the notation $\varphi ={\varphi }_y$ when it comes to the capacity constraint.

Let $\alpha$ be the path bounded by the source transition and the transition upstream of the mixed constrained place.

We define by ${\tau }_{\alpha }$ and $m_{\alpha }$ successively the sum of all delays and the sum of markings existing along this path.

$x_j\left(t\right)$ represents the counter function of the transition upstream of the constrained place, and $u_x\left(t\right)$ represents the counter function of the source transition. As a result, we give the following inequality:

$$x_j\left(t\right)\le m_{\alpha }.u_x\left(t-{\tau }_{\alpha }\right)$$E26

Remark 2: We admit that $u_x\left(t\right)$ represents the control that guarantees the time constraint case and $u_y\left(t\right)$ the control that guarantees the marking constraint.

4.1 Control synthesis of the TEG subject to a mixed constraint

TEGs are a major class within the Discrete Event Systems paradigm. This type of system seems to be more sensitive when the general process is exposed to mixed time and capacity constraints. We reserve this section for the introduction of the control synthesis in the case of existence of mixed constraints in the TEG.

Theorem 4.1: A TEG whose dynamics is given by the explicit equation of state representation, subject to time and capacity constraints on the place $p_{\mathit{ij}}$ of the form (21) and (24) respectively. It admits a control law of the form $u\left(t\right)$:

$$u\left(t\right)=min\left(F_x{x}_r\left(t-1\right),F_y{x}_r\left(t-1\right)\right)=\left(u_x\left(t\right)\oplus u_y\left(t\right)\right)=F_x{x}_r\left(t-1\right)\oplus F_y{x}_r\left(t-1\right)$$E27

With $F_x=\left[\underset{r=1}{\overset{N}{\oplus }}{\left(A^{{\varphi }_x}\right)}_{\mathit{ir}}-m_{\mathit{ij}}.m_{\alpha }\right]$ such like ${\varphi }_x={\tau }_{\alpha }+{\tau }_{\mathit{ij}}^{\max }+1$ and

$F_y=\left[\underset{r=1}{\overset{N}{\oplus }}{A}^{{\varphi }_y}.\left(\left(b-m_{\mathit{ij}}\right)-m_{\alpha }\right)\right]$ such like ${\varphi }_y={\tau }_{\alpha }+1$

This is also equivalent to:

$$\begin{array}{l}u\left(t\right)=min\left(\left[\underset{r=1}{\overset{N}{\oplus }}{\left(A^{{\varphi }_x}\right)}_{\mathit{ir}}-m_{\mathit{ij}}.m_{\alpha }\right].x_r\left(t-1\right),\left[\underset{r=1}{\overset{N}{\oplus }}\left(A^{{\varphi }_y}\right).{\left(\left(b-m_{\mathit{ij}}\right)-m_{\alpha }\right)}_{\mathit{ir}}\right].x_r\left(t-1\right)\right)\\ =\left[\underset{r=1}{\overset{N}{\oplus }}{\left(A^{{\varphi }_x}\right)}_{\mathit{ir}}-m_{\mathit{ij}}.m_{\alpha }\right].x_r\left(t-1\right)\oplus \left[\underset{r=1}{\overset{N}{\oplus }}\left(A^{{\varphi }_y}\right).{\left(\left(b-m_{\mathit{ij}}\right)-m_{\alpha }\right)}_{\mathit{ir}}\right].x_r\left(t-1\right)\end{array}$$

If the following conditions are true:

$$F_y\ge 0;F_x\ge 0\mathrm{et}{m}_{\alpha }\le \left(b-m_{\mathit{ij}}\right).{\left(A^k.B\right)}_i\text{Pour}k=0\mathrm{à}{\tau }_{\alpha }$$E28

Proof of this theorem is found [24].

4.2 Control synthesis of the GET subject to multiple mixed constraints

TEG might also be more sensitive when the same system is the subject of the presence of multiple mixed constraints. In this regard, since we have dealt with the case of control laws that satisfy a single mixed constraint, it seems important to deal with a more generalized problem that is multiple places subject to mixed constraints:

Let $P_s$ be the places subject to multiple mixed constraints with $s=1,\dots ,S.$ These places are respectively delimited by the transitions $t_z$, $t_{z^{\text{'}}}$, which are respectively associated to the counter functions $x_z$ and $x_{z^{\text{'}}}.$ We denote by ${\lambda }_z$ the cumulative delay from the control transition $t_u$ to the input transition of the constrained place $P_s.$. For each place $P_s$, we define by $m_z$ the initial marking. ${\tau }_z^{\max }$ is the maximum delay, and $b_z\in {\mathrm{\mathbb{N}}}^{\ast }$ is the upper bound of the marking to be respected.

Consequently, the time constraints and the capacity constraints are given by:

$$x_{z\text{'}}\left(t\right)\le m_z{x}_z\left(t-{\tau }_z^{\max }\right)$$E29

$$x_z\left(t\right)\le \left(b-M_s\right)x_{z\text{'}n}\left(t\right)$$E30

Theorem 3: For a TEG whose evolution is described by the explicit equation of the state representation (1), it is subject to Z mixed constraints on the places of the form (29) and (30), admitting a general control law of the form:

$$U\left(t\right)=\underset{z=1}{\overset{Z}{\oplus }}{u}_z\left(t\right)$$E31

With:

$$u\left(t\right)=F.x\left(t-1\right)=min\left(F_x.F_y\right)x_r\left(t-1\right)=\left(F_x\oplus F_y\right)x_r\left(t-1\right)$$

Like $F_x=\left[\underset{r=1}{\overset{N}{\oplus }}{\left(A^{{\varphi }_x}\right)}_{\mathit{ir}}-m_{\mathit{ij}}.m_{\alpha }\right]$ et $F_y=\left[\underset{r=1}{\overset{N}{\oplus }}{\left(A^{{\varphi }_y}\right)}_{\mathit{ir}}.\left(\left(b-m_{\mathit{ij}}\right)-m_{\alpha }\right)\right]$ are the feedbacks that ensure the mixed constraints of the form (29) and (30), they are verified for each index $z^{\text{'}}$ and $z$ of the constrained place $p_s$, with:

$${\varphi }_{x_s}={\tau }_{\alpha }+{\tau }_{\mathit{ij}}^{\max }+1\mathrm{et}{\varphi }_{y_s}={\tau }_{\alpha }+1\text{for each}s=1,\dots ,S.$$

Proof of this theorem could be found in [24].

Considering that time and capacity constraints are two crucial factors for the successful and efficient conduction of these systems, we address the control problem for Conflicted Timed Event Graphs under mixed constraints. To this end, we build on the approaches introduced in [2, 8] to provide an adapted formulation of (Min, +) switching model policy.

4.3 Control of CTEGs subject to a mixed constraint with a single shared resource

Although many processes with nonpermissive standards, such as time and capacity criteria, are almost sensitive, they are found to be effective when these standards are met under proper system conduction.

At this level, we focus on the formulation of the control approach in the case of CTEGs exposed to a mixed time and capacity constraint. CTEGs are similar to competing users sharing a single resource among themselves. The solution of this problem is based on finding control laws with appropriate feedbacks that guarantee the mixed constraints applied on specific places of the CTEG.

Assuming that $p_{\mathit{ij}}$ is the place subject to both a capacity and a time constraint, specifically located on the $n$^th Timed Event Graph of the CTEG.

We first consider that this place is disposed to a temporal constraint presented by the interval: $$\left[{\tau }_{\mathit{ij}}^{\min }{\tau }_{\mathit{ij}}^{\max }\right].$$

$x_{j_n}\left(t\right)$ and $x_{i_n}\left(t\right)$ represent the counter functions of transitions $t_j$ and $t_i$ respectively, such that the firing number of these transitions is fixed until $t$ time.

In the context of CTEG topic, the expression of the time constraint is expressed with reference to the n index of the TEG where it exists. It is given by the following linear inequality:

$$x_{i_n}\left(t\right)\ge m_{\mathit{ij}}{x}_{j_n}\left(t-{\tau }_{\mathit{ij}}^{\max }\right)$$E32

This same place may also be subject to marking constraint, which is given by the following inequality:

$$x_{j_n}\left(t\right)\le \left(b-m_{\mathit{ij}}\right)x_{i_n}\left(t\right)$$E33

Remark 3: In addition to the assumptions mentioned above, it is preferable to assume that each constrained place is accessible thanks to the index that determines its location in the Conflict Time Event Graph.

Remark 4: We assume that a control of the form $u\left(t\right)=F.x\left(t-1\right)$ is always a well-posed control law with delays and is preferred over a static control of the form $u\left(t\right)=F.x\left(t\right),$ such as $F\in {\overline{\mathbb{R}}}_{\min }^{m\times N}$. On the other hand, implicit control laws due to implicit loops for the controlled CTEG can lead to closed-loop blocking.

We provide in the following the equivalent equation to the explicit equation of state representation already given in (1).

$$x_x\left(t\right)=A^{\tau }.x\left(t-\tau \right)\oplus \left[\underset{k=0}{\overset{\tau -1}{\oplus }}{A}^k.B.u\left(t-k\right)\right],\text{with}\tau \ge 1$$E34

By proceeding to the substitution $\tau =\varphi$, like $\varphi \ge 1$, one can achieve:

$$x_{i_n}\left(t\right)=\left[\underset{r=1}{\overset{N^{\text{'}}}{\oplus }}{\left(A^{\varphi }\right)}_{\mathit{ir}}{x}_r\left(t-\varphi \right)\right]\oplus \left[\underset{k=0}{\overset{\varphi -1}{\oplus }}{\left(A^k.B\right)}_i.u\left(t-k\right)\right]$$E35

Given the matrices $A\in {\overline{\mathbb{R}}}_{\min }^{N\text{'}\times N\text{'}}$ and $B\in {\overline{\mathbb{R}}}_{\min }^{N\text{'}\times m}$, such that $N^{\text{'}}$ represents the number of internal transitions of the Conflicted Timed Event Graph. The notation given by ${\left(A^{\varphi }\right)}_{\mathit{ir}}$ denotes the i^th component of the matrix $A^{\varphi }$ with $r$ varying from 1 to $N^{\text{'}}$.

For clarity purposes, $u\left(t-k\right)$ in Eq. (35) will be noted as $u_x\left(t-k\right)$ when we inspect for a control synthesis in the time constraint case and as $u_y\left(t-k\right)$ in the capacity constraint case, with ${\alpha }_n$ denoting the path bounded by the source transition and the upstream transition of the mixed constrained place.

For each path of the Conflict Timed Event Graphs in the chosen mode, we define respectively by ${\tau }_{{\alpha }_n}$ and $m_{{\alpha }_n}$ the sum of all delays and the sum of the markings for each Timed Event Graph connecting the source transition to the upstream transition of the constrained place. Let $t_{j_n}$ be its upstream transition of this place and $x_{j_n}$ be its counter function. As a result, we obtain the following inequation:

$$x_{j_n}\left(t\right)\le m_{{\alpha }_n}.u_x\left(t-{\tau }_{{\alpha }_n}\right)$$E36

In the case of a single shared resource, we begin by introducing Theorem 4 below in which we detail the control approach synthesis in the case of a single mixed constraint.

Theorem 4: A CTEG composed of $N$ Timed Events Graph, whose evolution is given by the explicit equation of state representation, shares a safe resource denoted $\tilde{p}$. Let $p_{\mathit{ij}}$ be the place subject to time and capacity constraints of the form (32) and (33) respectively. This CTEG admits a control law of the form $u_n\left(t\right)$:

$$u_n\left(t\right)=min\left(F_x{x}_r\left(t-1\right),F_y{x}_r\left(t-1\right)\right)=\left(u_x\left(t\right)\oplus u_y\left(t\right)\right)=F_x{x}_r\left(t-1\right)\oplus F_y{x}_r\left(t-1\right)$$E37

Like:

$F_x=\left[\underset{r=1}{\overset{N}{\oplus }}{\left(A^{{\varphi }_x}\right)}_{\mathit{ir}}-m_{\mathit{ij}}.m_{{\alpha }_n}\right];$, we have ${\varphi }_x={\tau }_{{\alpha }_n}+{\tau }_{\mathit{ij}}^{\max }+1$

$F_y=\left[\underset{r=1}{\overset{N}{\oplus }}{A}^{{\varphi }_y}.\left(\left(b-m_{\mathit{ij}}\right)-m_{{\alpha }_n}\right)\right]$; ${\varphi }_y={\tau }_{{\alpha }_n}+1$

The above control is also equivalent to

$$\begin{array}{l}{u}_n\left(t\right)=min\left(\left[\underset{r=1}{\overset{N}{\oplus }}{\left(A^{{\varphi }_x}\right)}_{\mathit{ir}}-m_{\mathit{ij}}.m_{{\alpha }_n}\right].x_r\left(t-1\right),\left[\underset{r=1}{\overset{N}{\oplus }}\left(A^{{\varphi }_y}\right).{\left(\left(b-m_{\mathit{ij}}\right)-m_{{\alpha }_n}\right)}_{\mathit{ir}}\right]x_r\left(t-1\right)\right)\\ =\left[\underset{r=1}{\overset{N}{\oplus }}{\left(A^{{\varphi }_x}\right)}_{\mathit{ir}}-m_{\mathit{ij}}.m_{{\alpha }_n}\right].x_r\left(t-1\right)\oplus \left[\underset{r=1}{\overset{N}{\oplus }}\left(A^{{\varphi }_y}\right).{\left(\left(b-m_{\mathit{ij}}\right)-m_{{\alpha }_n}\right)}_{\mathit{ir}}\right]x_r\left(t-1\right)\end{array}$$

The above control law exists if the following conditions are true:

$$F_x\ge 0,F_y\ge 0\text{and}{m}_{{\alpha }_n}\le \left(b-m_{\mathit{ij}}\right).{\left(A^k.B\right)}_{i_n}\text{for each}k=0,\dots ,{\tau }_{{\alpha }_n}$$E38

Proof is found in [25].

4.4 Control of a CTEG with multiple mixed constraints

Switching systems represent a frequently encountered problem, especially in the context of real-time applications whose performance is very sensitive to the time factor and to the availability of the shared resource. In this case, the implementation of control laws that guarantee the respect of these conditions is required. It represents the motivation behind the study of this problem that deserves to be meticulously analyzed.

The following inequalities (39) and (40) define the expressions for the time and capacity constraints.

$$x_{z\text{'}}\left(t\right)\ge m_z{x}_z\left(t-{\tau }_z^{\max }\right)$$E39

$$x_{\mathit{zn}}\left(t\right)\le \left(b_n-M_{\mathit{sn}}\right)x_{z\text{'}n}\left(t\right)$$E40

This section will be reserved to extend the previous case for the control of a CTEG in the case of the existence of multiple mixed constraints.

Theorem 5: For a CTEG constituted of $N$ Timed Event Graphs, whose evolution is described by the explicit equation of state representation (1), shares a safe resource denoted $\tilde{p}$. Then, $P_s$ are the places subject to z mixed constraints of the form (39) and (40). This CTEG admits a general control law of the form:

$$U\left(t\right)=\underset{z=1}{\overset{Z}{\oplus }}{u}_z\left(t\right)$$E41

Like $u_z\left(t\right)=F.x_r\left(t-1\right)=min\left(F_x{x}_r\left(t-1\right),F_Y{x}_r\left(t-1\right)\right)=\left(F_x\oplus F_Y\right).x_r\left(t-1\right)$ such as $F_x=\left[\underset{r=1}{\overset{N}{\oplus }}{\left(A^{{\varphi }_x}\right)}_{\mathit{ir}}-m_{\mathit{ij}}.m_{{\alpha }_n}\right]$ and $F_y=\left[\underset{r=1}{\overset{N}{\oplus }}{\left(A^{{\varphi }_y}\right)}_{\mathit{ir}}.\left(\left(b-m_{\mathit{ij}}\right)-m_{{\alpha }_n}\right)\right]$ are the feedbacks that guarantee the mixed constraints of respectively the form (39) and (40). They are verified for each index ${z^{\text{'}}}_n$ and $z_n$ of the constrained place $p_{s_n},$ having ${\varphi }_{x_s}={\tau }_{{\alpha }_n}+{\tau }_{\mathit{ij}}^{\max }+1$ and ${\varphi }_{y_s}={\tau }_{{\alpha }_n}+1$, for each $s=1,..,S.$ if the following conditions are true:

$$F_x\ge 0,F_y\ge 0\text{and}{m}_{{\alpha }_n}\le \left(b-m_{\mathit{ij}}\right).{\left(A^k.B\right)}_{i_n}\text{for each}k=0,\dots ,{\lambda }_z$$E42

The demonstration of this theorem with an application case could be found in [25].

4.5 Generalization to the case of multiple shared resources

Multiple shared resources can be the object of multiple switches between the Timed Event Graphs constituting the CTEGs and performed according to the needs and specifications of the application. While multiple mixed constraints may also be involved, we move to a generalization for a control approach previously given in Section 4.4 that focuses on the existence of multiple users sharing multiple safe places while being a cause of the presence of multiple mixed constraints.

Remark 4: We note that at the modeling level, the mobilization of several shared resources is visible through the switching (Min, +) model within the sequence.

Theorem 6: For a CTEG consisting of $N$ Timed Event Graphs, whose evolution is given by the explicit equation of state space representation (1), sharing multiple safe resources noted ${\tilde{p}}_l$ with $l=1,\dots ,L$, $\forall l\in \mathrm{\mathbb{N}}$, it is subject to multiple mixed constraints given by the inequalities (39) and (40) respectively, admitting a global control law of the form:

$$U\left(t\right)=\underset{z=1}{\overset{Z}{\oplus }}{u}_z\left(t\right)$$E43

Having for $z$ existing constraints on the places $p_{s_n},$ the control law in this case is noted $u_z\left(t\right)=min\left(u_x\left(t\right),u_y\left(t\right)\right)$, where $u_x\left(t\right)=\underset{r=1}{\overset{N}{\oplus }}{A}^{{\varphi }_x}\left(z_n^{\text{'}},:\right).x_r\left(t-1\right)-m_{z\text{'}z}.m_{{\alpha }_n}$ and $u_y\left(t\right)=\underset{r=1}{\overset{N}{\oplus }}{A}^{{\varphi }_y}\left(z_n^{\text{'}},:\right).x_r\left(t-1\right).(\left(b_n-m_{\mathit{iz}\text{'}z}\right)-m_{{\alpha }_n}$ guarantee the existing constraints of the form (32) and (33), if and only if the conditions of the form (42) are verified for each index ${z^{\text{'}}}_n$ and $z_n$ of the constrained places noted by $p_{s_n}.$ having ${\varphi }_{x_s}={\tau }_{{\alpha }_n}+{\tau }_{\mathit{ij}}^{\max }+1$ and ${\varphi }_{y_s}={\tau }_{{\alpha }_n}+1$, for $s=1,\dots ,S.$

The proof is provided in [25] and an application case of a crossing railway sections is given.

5. Conclusion

Conflicted Timed Event Graphs turn out to be a rich class in the Discrete Event Systems paradigm with wide range of industrial applications. Based on their functionally critical nature where multiple users compete to win resource allocation, this type of systems seems to be more sensitive when the overall process is exposed to mixed time and capacity constraints. A wide investigation in this subject with multiple application cases referring to manufacturing applications and transport systems could be found in [26]. To this end, we detailed the switching model approach using the (Min, +) Dioid algebra. The conservative and mixed cases for resource allocation between graphs are considered beforehand. These contributions solve both sharing-resource-allocation problems, while the problem of the existence of capacity- and time-related marking constraints in places seems to be a source of complication for this type of system. Sufficient conditions are given for the existence of control laws.

Conflict of interest

The authors declare no conflict of interest.