# Observable Feedback Control of discrete processes under time constraint: Application to Cluster Tools

Romain Jacob, Saïd Amari

► To cite this version:

Romain Jacob, Saïd Amari. Observable Feedback Control of discrete processes under time constraint: Application to Cluster Tools. 2015. hal-01274963

HAL Id: hal-01274963

https://hal.science/hal-01274963

Preprint submitted on 16 Feb 2016

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_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
To appear in the *International Journal of Computer Integrated Manufacturing*
Vol. 00, No. 00, Month 20XX, 1–19

Observable Feedback Control of discrete processes
under time constraint: Application to Cluster Tools

R. Jacob<sup>a*</sup> and S. Amari<sup>a</sup>

<sup>a</sup>LURPA, ENS Cachan, Univ Paris-Sud, Universit Paris-Saclay, F-94235 Cachan, France

(September 2015)

Practical control of timed behaviors in industrial applications is difficult. One of the few efficient modeling approaches to deal with time constraints on discrete-event systems (DES) is to use Timed Event Graph (TEG), a sub-class of Petri Nets. The dynamic behavior of these graphs is represented by a linear equations system over the Max-Plus algebra. Up to date, these models were assumed to be fully observable. In this paper, we demonstrate that if a TEG is strongly connected, one can derive a *valid and observable control*. In other words, the control law depends solely on the control itself and the system's output, considered to be the only observable events. We address the satisfaction of a set of constraints in the case of a single input model (i.e., having only one input transition) and we provide the procedure to derive an observable control law under feedback form. Finally, we apply our control method to a dual-armed cluster tool, a well-known industrial practical application.

**Keywords:** Output feedback control; Time event graph; Manufacturing control systems; Optimal Control; Dynamic production control; Semiconductor manufacture; Petri nets; Discrete event simulation

# 1. Introduction

This paper presents a control approach for temporal constraints which aims to be workable even though the controller has partial information over the occurrences of the system's events. The objective is to minimize the number of sensors needed to satisfy a given set of specifications, and thus cut down the costs. In the general case, our approach cannot be used if the system's model is not cyclic. However, a manufacturing plant model can easily be "made" cyclic by considering a maximal capacity for instance. We also need the system to be conflict-free, which is a much harder limitation to overcome. Further relaxation of this limitation is to be considered. However, giving that the system model satisfies those hypothesis, our approach provides a formal control strategy ensuring any set of temporal constraints (such as not burning parts in an oven) will be satisfied while preserving the throughput of the plant as much as possible.

It is common than a control problem involves some temporal constraints to satisfy. For example, consider a work-piece which processing includes chemical reactions. The stripping time of a piece by immersion in an acid bath is precise, or at least defined by a time interval (where it requires a minimum soak time but must not exceed a maximum time). Such temporal restrictions can take diverse forms (e.g., deadline, time intervals, validity duration, ...), which are encountered in a wide range of applications (e.g., semiconductor industry (Kim and Lee 2015), automotive industry (Martinez and Castagna 2003), thermal or chemical treatments (Kim and Lee 2003), rail transport (Wang et al. 2013), networked control systems (Diouri, Georges, and Rondeau 2007)).

Even complex industrial processes are efficiently modeled by Discrete-Event Systems (DES).
Especially, Petri nets have been extensively used, as they are very efficient to capture the sequential

<footnote>*Corresponding author. Email: rjacob@ens-cachan.fr</footnote>
behavior of complex dynamic systems. However, explicit consideration of time (synchronization, delay, ...) is still a challenging topic. A Timed Event Graph (TEG) is a specific Timed Petri net (Murata 1989) which is useful for modeling timed behavior. It captures the non-linearities of timed dynamics and expresses them into a linear equations system over the Max-Plus algebra (Baccelli et al. 1992).

Combined use of TEG and Max-Plus is a well-known approach in the literature, with applications to different kinds of time-related issues. Among others, it includes scheduling for large scale systems (Bonhomme 2013; Goverde 2007) and just-in-time control, which aims to delay the system's input as much as possible without increasing the overall cycle time (Houssin, Lahaye, and Boimond 2007; Lhommeau, Jaulin, and Hardouin 2012). The other way around, other works focus on satisfying time constraints with minimum delay. The control approach can be similar to supervision (Martinez and Castagna 2003; Houssin, Lahaye, and Boimond 2013) or performed by state-feedback, as for linear continuous systems (Maia, Hardouin, and Cury 2013; Maia, Andrade, and Hardouin 2011; Katz 2007). All these approaches aim to design a controller which guarantees that the system evolves without violating any of the time constraints, usually imposed on the system's states. Another method for the synthesis of such feedback control law was presented in Amari et al. (2012). It is defined as a Max-Plus linear inequality, causal, which corresponds to a state feedback from the system. Kim and Lee (2012, 2015) extend Amari et al. (2012) by relaxing some modeling hypothesis, for the specific setting of cluster tools. Even though they do address the control of temporal constraints, previous works suffer from a strong limitation. They consider the system to control as fully observable, which is never the case in practice. This paper generalizes Kim and Lee (2015) by relaxing the observability hypothesis.

The main contribution of this paper is the demonstration that **for any strongly connected system model**, one can derive **a valid controller** expressed under an **observable feedback form** (i.e., which depends solely on past control and output events) and **satisfies any set of time constraints**. Furthermore, we apply our method to the control of a cluster tool, a well-known industrial case of study from the literature (Wu and Zhou 2010; Kim and Lee 2012, 2015) and compare our control policy with previous results.

Section 2 presents useful background on Max-Plus, TEG, and the modeling of temporal con-
straints. Section 3 summarizes our modeling hypothesis and motivations. In Section 4 we introduce
some intermediate results before addressing the control derivation in Section 5. The practical ap-
plication of our approach is presented in Section 6, including comparison with previous results and
performances discussions. Finally, some conclusions and perspectives are drawn in Section 7.

## 2. Preliminaries

2.1. *Max-Plus Algebra*

A monoid is a set, say $\mathcal{D}$, endowed with an internal law, noted $\oplus$, which is associative and has a
neutral element, denoted $\varepsilon$. A semiring is a commutative monoid endowed with a second internal
law, denoted $\otimes$, which is associative, distributive with respect to the first law $\oplus$, has a neutral
element, denoted $e$, and admits $\varepsilon$ as absorbing element, i.e., $\forall a \in \mathcal{D}, a \otimes \varepsilon = \varepsilon \otimes a = \varepsilon$. A
dioid is a semiring with an idempotent internal law, i.e., $\forall a \in \mathcal{D}, a \oplus a = a$. The dioid is said
to be commutative if the second law $\otimes$ is commutative. Max-Plus algebra is defined as $(\mathbb{R} \cup
\{-\infty\}, \max, +)$. This semiring, denoted $\mathbb{R}_{\max}$, is a commutative dioid, the law $\oplus$ is the operator
max with neutral element $\varepsilon = -\infty$, and the second law $\otimes$ is the usual addition, with neutral
element $e = 0$.

We use the following notations

* $M(r; :)$ refers to the $r^{th}$ row of matrix $M$,
  $x(r)$ refers to the $r^{th}$ element of vector $x$,
* (+, ×) are the usual addition and multiplication,

* (⊕, ⊗) are the operator max and the usual addition,

* ⊗ is abbreviated by · (dot),

* $M^p$ is the $p^{th}$ power of matrix $M$ in $\mathbb{R}_{\max}$ (i.e., $M^2 = M \cdot M$).

For $(p, q) \in \mathbb{N}^2$, $(V, W) \in (\mathbb{R}_{\max}^{p \times q})^2$, $V \oplus W$ denotes the matrix with components $(V \oplus W)(i, j) = \max(V(i, j), W(i, j))$.

Given $n \in \mathbb{N}$, and matrices $(A, B) \in (\mathbb{R}_{\max}^{p \times n} \times \mathbb{R}_{\max}^{n \times q})$, $A \otimes B$ (or abbreviated $A \cdot B$) represents the result of matrices multiplication, defined by the formula

$$ (A \otimes B)(i, j) = \bigoplus_{k=1}^{n} (A(i, k) \otimes B(k, j)) = \max_{k \in [1..n]} (A(i, k) + B(k, j)) $$

The Kleene star of a square matrix $M \in \mathbb{R}_{\max}^{n \times n}$, written $M^*$, is defined as

$$ M^* = \bigoplus_{i \in \mathbb{N}} M^i $$

where $M^0$ equals the unit matrix, with entries equal to $e$ on the diagonal, and $\varepsilon$ elsewhere.

**Definition 1** (Similar vectors). Two vectors $(u, v) \in (\mathbb{R}_{\max}^n)^2$ are similar if they share the same zero-elements regarding to the law $\otimes$, i.e.,

$$ \forall r \in [1..n], (u(r) = \varepsilon \Leftrightarrow v(r) = \varepsilon) $$

**Remark 1.** In some references, similar vectors (or matrices) are said to have same support (Baccelli et al. 1992).

**Proposition 1.** Similarity is distributive over the law $\otimes$. Given three vectors $(u, v, w) \in (\mathbb{R}_{\max}^n)^3$,

$$ (u, v) \text{ similar} \Rightarrow (u \cdot w, v \cdot w) \text{ similar} $$

*Proof.*

$$ \begin{align*} u \cdot w = \varepsilon &\Leftrightarrow \bigoplus_{r=1}^{n} u(r) \cdot w(r) = \varepsilon \\ &\Leftrightarrow [\forall r \in [1..n], u(r) \neq \varepsilon \Rightarrow w(r) = \varepsilon] \end{align*} $$

Since $(u, v)$ are similar,

$$ \begin{align*} &\Leftrightarrow [\forall r \in [1..n], v(r) \neq \varepsilon \Rightarrow w(r) = \varepsilon] \\ &\Leftrightarrow v \cdot w = \varepsilon \end{align*} $$

□

## 2.2. TEG and Linear Max-Plus Models

An event graph is an ordinary Petri net where each place has exactly one upstream and one downstream transition. It is also referred to as a decision free Petri net, as one token never enable more than one transition at a time. A timed event graph (TEG) is an event graph with extra delays associated to places (holding times) or transitions (firing times).

We distinguish transitions having at least one upstream place $(t_1...t_n)$ and those having none $(t_{u_1}...t_{u_q})$ also called source transitions. The former are referred to as standard transitions, while the latter are said to be input transitions, which can be fired following any arbitrary non-decreasing sequence of epochs.
We further introduce the following notations and definitions

* $p_{ij}$ denotes the place linking $t_j$ to $t_i$ when it exists,

* A **path** is an oriented alternating sequence of transitions and places successively connected by an arc,

* The **token number** of a path is the sum of tokens in all places along the path,

* The **delay** of a path is the sum of holding and firing time of all places and transitions along the path,

* Given two transitions $t_i$ and $t_j$ and a token number $m_{ij}$, several $m_{ij}$-token paths connecting $t_j$ to $t_i$ exist in general.

$t_j \xrightarrow{m_{ij}, \tau_{ij}} t_i$ denotes the maximal of such paths, i.e., the $m_{ij}$-token path with maximum delay $\tau_{ij}$,

* A **primal path** contains exactly one token in the first place along the path,

* An **empty path** contains no token,

* A **circuit** around $t_i$ is a path connecting $t_i$ to itself,

* An **elementary path** does not contain any transition more than once,

* An **event** is the firing of a transition. A **control** (resp. **output**) **event** refers to the firing of one of the system's input (resp. output) transitions,

* An event is said **observable** if the occurrence of the associated firing can be detected and used by the controller. Control events are considered observable,

* A transition which firing is observable is called an **output transition**. Thus output events are observable by definition.

A Petri net is said to be **live** for an initial marking if all transitions can always be enabled by a future marking (Baccelli et al. 1992). A Petri net not live is said to be **deadlocked**. An event graph containing only standard transitions is said to be **autonomous**. A nonautonomous event graph is said to be live if its autonomous subgraph (i.e., pruned of input transitions) is live.

**Theorem 1** (from (Baccelli et al. 1992)). An autonomous event graph is live if and only if every circuit contains at least one token with respect to the initial marking.

**Definition 2** (Valid control). If a live autonomous system remains live after the implementation of the control law, the control is said to be valid.

$\leftrightarrow$ A valid control does not deadlocked a system.

**Definition 3** (Observable feedback control). A control law is said to be observable if it depends on controls' and outputs' events, associated to non-negative delays.

The state variable $x_i(k)$ of a TEG is the epoch when standard transition $t_i$ fires for the $k^{th}$ time. We call $x(k) = (x_i(k))$ the system's **state vector**. The **input vector** $u(k)$ is defined likewise. The dynamic behavior of a TEG in Max-Plus is described by the evolution equation

$$x(k) = \bigoplus_{m \ge 0} (A_m \cdot x(k-m) \oplus B_m \cdot u(k-m)) \quad (1)$$

where $A_m(i, j) = \begin{cases} \tau & \text{if } p_{ij} \text{ exists, contains } m \text{ tokens, and has holding time } \tau \\ \varepsilon & \text{otherwise.} \end{cases}$

$B_m$ is defined likewise for places between input and standard transitions.

It yields $(A_m, B_m) \in \mathbb{R}_{\max}^{n \times n} \times \mathbb{R}_{\max}^{n \times q}$.
<figure><img src="image_2.png" /><figcaption>Figure 1. Example of TEG; (a) a general model and (b) its extension</figcaption></figure>

**Example 1.** Consider the TEG in Fig. 1(a). The firing epochs of $t_1$ are defined by the following equation

$$x_1(k) = \max(2 + u_1(k - 1), 5 + u_2(k - 1), 3 + x_2(k - 2))$$

which rewrites into linear form in Max-Plus

$$x_1(k) = 2 \cdot u_1(k - 1) \oplus 5 \cdot u_2(k - 1) \oplus 3 \cdot x_2(k - 2)$$

Setting $x(k) = [x_1(k), x_2(k)]'$ and $u(k) = [u_1(k), u_2(k)]'$, the full TEG behavior is expressed by

$$x(k) = \underbrace{\begin{pmatrix} \cdot & \cdot \\ 2 & \cdot \end{pmatrix}}_{A_0} x(k) \oplus \underbrace{\begin{pmatrix} \cdot & 3 \\ \cdot & \cdot \end{pmatrix}}_{A_2} x(k - 2) \oplus \underbrace{\begin{pmatrix} 2 & 5 \\ \cdot & \cdot \end{pmatrix}}_{B_1} u(k - 1)$$

We will further assume that places connecting input to standard transitions contain no token. It yields $B_k = \varepsilon$ for all $k > 0$. This is no restriction as one can add an extra place between such transitions, such that the first place is empty and the second contains tokens. Moreover, as for regular linear systems, the initial recurrence (1) can be transformed into an equivalent recurrence of order 1 by extending the state vector. This consists in expanding all places with marking $m > 1$ into $m$ places with marking equal to 1. Hence, for each of such places, $(m - 1)$ intermediate transitions are added and the resulting extended state vector $\hat{x}(k)$ belongs to $\mathbb{R}_{\max}^N$ with $N = n + (m - 1)$. Fig. 1 is a simple example of both model extensions. It follows,

$$\hat{x}(k) = \hat{A}_0 \cdot \hat{x}(k) \oplus \hat{A}_1 \cdot \hat{x}(k - 1) \oplus \hat{B}_0 \cdot u(k)$$

The $\widehat{\cdot}$ notation will be further omitted for the sake of readability.

Furthermore, it is shown that if the event graph is live, $A_0^*$ reduces to $\bigoplus_{i=1}^n A_0^i$ (Baccelli et al. 1992). Hence one can derive the **standard state-space equation**,

$$x(k) = A \cdot x(k - 1) \oplus B \cdot u(k) \qquad (2)$$

where $A = A_0^* \cdot A_1$ and $B = A_0^* \cdot B_0$. See Baccelli et al. (1992) for details.

Finally, for any integer $\phi$ such that $1 \le \phi \le k$, by doing $\phi$ substitutions in (2), we obtain

$$x(k) = A^{\phi} \cdot x(k - \phi) \oplus \left[ \bigoplus_{k'=0}^{\phi-1} A^{k'} \cdot B \cdot u(k - k') \right] \qquad (3)$$

**Remark 2.** Graph interpretation of A and B is illustrated in Fig. 2. Matrices' coefficients represent the maximal delay along some paths, depending on the matrix under consideration. For instance, $A(i, j) = (A_0^* \cdot A_1)(i, j)$, thus $A(i, j)$ is the maximal delay of paths connecting $t_j$ to $t_i$, primal (because of $A_1$) and then going through an arbitrary number of empty places (from $A_0^*$). It equals $\varepsilon$ if no such path exists.

$A^k$ contains delays of "longer" paths (i.e., with more tokens) as $k$ increases. Hence, $A^k$ will tend to "grow" with $k$.
<figure><img src="image_3.png" /></figure>

<figure><img src="image_4.png" /><figcaption>Figure 2. Graph interpretation of A and B matrices</figcaption></figure>

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

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

Note that these paths do not need to be elementary (i.e., they can pass through the same transition several times).

Example 2. Back to Example 1, consider the extended TEG represented in Fig. 1(b). Its dynamics are expressed by the following standard form

$$x(k) = \underbrace{\begin{pmatrix} \dots & 2 & 5 & 3 \\ \dots & 4 & 7 & 5 \\ \dots & \dots & \dots & \dots \\ \dots & \dots & \dots & \dots \\ \dots & \dots & \dots & \dots \end{pmatrix}}_{A} \oplus x(k-1) \oplus \underbrace{\begin{pmatrix} \dots \\ \dots \\ 0 & \dots \\ \dots & 0 \\ \dots \end{pmatrix}}_{B} u(k)$$

**Remark 3.** One should remember that the state variables ($x_i$) represent firings of transitions. Hence, when we refer to state-feedback, the state is the set of last firing epochs of the system's transitions. This differs from the notion of state in the Petri net formalism, which is usually the marking of the net.

## 2.3. Model of cyclic processes

In many real life applications, automated systems we aim to control are cyclic. When we model these systems by means of a graph, the resulting graph is said to be **strongly connected**.

**Definition 4 (Strongly connected graph).** A graph is said to be strongly connected if for any pair of nodes i and j, there exists an oriented path from i to j.

**Proposition 2.** If an event graph is strongly connected, then, for any pair of transitions ($t_i, t_j$), there exists $m_{ij} \in \mathbb{N}$ such that a path $t_j \xrightarrow{m_{ij}, \tau_{ij}} t_i$ exists.

*Proof.* Existence of paths between $t_j$ and $t_i$ is direct from Def. 4. Then, for any possible token number $m_{ij}$, there exists at least one with maximal delay $\tau_{ij}$. □

**Remark 4.** If the event graph is live, the token number of every circuit is at least 1 (Thm. 1). Thus, adding strong connectivity, one can note that for any $k \in \mathbb{N}$ and any pair of transitions, there always exists a (possibly non-elementary) $k'$-token path, $k' \ge k$, connecting these two transitions.

**Definition 5 (Cycle time (Baccelli et al. 1992)).** Given a live TEG under standard form (2), its cycle time $\lambda$ is the maximal cycle mean of the state matrix A. It computes

$$\lambda = \bigoplus_{j=1}^{n} (\text{trace}(A^j))^{1/j} \qquad (4)$$
<figure><img src="image_7.png" /></figure>

<figure><img src="image_8.png" /><figcaption>Figure 3. (a) Example of temporal constraint and (b) its extension</figcaption></figure>

where (.)¹/ⱼ represents in Max-Plus the division by j in the conventional sense.

## 2.4. Temporal constraints

Strict time constraints are frequent in industry. It is crucial to model them efficiently to be able to ensure they are satisfied during the process. In a TEG, holding time represents the minimal time a token has to sojourn in a place. If one wants to account for a maximal duration, another constraint has to be added.

An approach to solve this modeling problem was suggested in (Amari et al. 2012). The sojourn time of tokens in place $p_{ij}$ is minimized by the holding time $\tau_{ij}$. In addition, it must not exceed another time delay, denoted $\tau_{ij}^{max}$. Hence, a time interval $[\tau_{ij}, \tau_{ij}^{max}]$ can be associated with the place $p_{ij}$ subject to a strict time constraint. This additional temporal constraint is expressed by the following Max-Plus inequality

$$x_i(k) \le \tau_{ij}^{max} \cdot x_j(k - m_{ij}) \quad (5)$$

This is illustrated in Fig. 3.

## 3. Model description and motivations

In the remaining of this paper, we consider a nonautonomous TEG with a single input transition $t_u$ and N standard transitions, live, with no 0-delay circuit, and such that its autonomous subgraph is strongly connected. The dynamics of this TEG are described by the standard form equation

$$(2): x(k) = A \cdot x(k-1) \oplus B \cdot u(k).$$

It yields A and B belong to $\mathbb{R}_{\max}^{N \times N}$ and $\mathbb{R}_{\max}^{N \times 1}$ respectively.

We are interested in modeling manufacturing systems, in which holding times represent length of processes and thus are non-negative. We set firing times of transitions to 0 and we consider the following evolution rules for our TEG

(a) transitions fire as soon as they are enabled,

(b) a token starts enabling the downstream transition as soon as it has completed its place's holding time,

(c) we consider the following (compatible – refer to Baccelli et al. (1992)) initial conditions

$$x(k) = \begin{cases} e & \text{if } k = 0 \\ \varepsilon & \text{if } k < 0 \end{cases}$$

Assuming firing epochs of the input sequence $u(k)$ can be arbitrary defined, we aim to derive such a sequence (later referred to as **the control**) valid (i.e., which does not deadlocked the system), under observable feedback form (i.e., expressed by means of non-negative delays and past observable events), such that preset temporal constraints (the kind of (5)) are satisfied.
## 4. Intermediate results

This Section introduces Lemma 1, which justifies that, under Section 3's assumptions, the firing epochs of any standard transition can be overestimated using solely the input sequence and previous firings of any other standard transition. We start with three intermediate propositions, which are prerequisites for the demonstration of the Lemma. All proofs are provided in Appendix A.

**Proposition 3.** For any $(i, j) \in [1..N]^2$, if there exists a path $t_j \xrightarrow{m_{ij}, \tau_{ij}} t_i$,

$$ \forall p \in \mathbb{N}^*, A^{p+m_{ij}}(i, :) \geq \tau_{ij} \cdot A^p(j, :) $$

**Proposition 4.** For any $(i, j) \in [1..N]^2$ such as there exist a path $t_j \xrightarrow{m_{ij}, \tau_{ij}} t_i$ and a circuit $t_i \xrightarrow{m_{ii}, \tau_{ii}} t_i$, and for any $\nu \in \mathbb{R}$,

$$ \exists q_0 \in \mathbb{N}, \forall q \geq q_0, \forall p \in \mathbb{N}^*, $$

$$ \nu \cdot A^{p+m_{ij}+q \times m_{ii}}(i, :) \geq A^p(j, :) $$

**Proposition 5.** For any $(i, j) \in [1..N]^2$ such as there exist paths $t_j \xrightarrow{m_{ij}, \tau_{ij}} t_i$ and $t_i \xrightarrow{m_{ji}, \tau_{ji}} t_j$, there exists $p_0 \in \mathbb{N}$ such that,

$$ 5.1: \forall p \geq p_0, \forall q \in \mathbb{N}, \quad (A^{p+q \times m_{ii}}(i, :), A^p(i, :)) \text{ similar,} $$

$$ 5.2: \forall p \geq p_0 + m_{ji}, \quad (A^{p+m_{ij}}(i, :), A^p(j, :)) \text{ similar,} $$

$$ 5.3: \forall p \geq p_0 + m_{ji}, \forall q \in \mathbb{N}, \quad (A^{p+q \times m_{ii}+m_{ij}}(i, :), A^p(j, :)) \text{ similar,} \\ \text{where } m_{ii} = m_{ij} + m_{ji}. $$

**Lemma 1.** For any $(i, j) \in [1..N]^2$ such as there exist paths $t_j \xrightarrow{m_{ij}, \tau_{ij}} t_i$ and $t_i \xrightarrow{m_{ji}, \tau_{ji}} t_j$, and for any $\nu \in \mathbb{R}$, there exist $\delta \in \mathbb{R}^+$, $(p_0, q_0) \in \mathbb{N}^2$, and $(\mu_0, .., \mu_{p+q-1}) \in \mathbb{R}_{\max}^{p+q}$ such that,

$$ \forall p \geq p_0, \forall q \geq q_0, $$

$$ \nu \cdot x_i(k) \leq \delta \cdot x_j(k-q) \oplus \left[ \bigoplus_{k'=0}^{p+q-1} (\mu_{k'} \cdot u(k-k')) \right] $$

**Remark 5.** Lemma 1 is the core theoretical result of this paper. Given any (even negative) delay $\nu$ and state $x_i$, it guarantees we can find an **observable upper bound**, that is an expression depending solely on past control events $u(k)$ and any other transition's events $x_j(k)$, associated with a non-negative delay ($\delta$) on $x_j$.

In the next section, we will set the system's output $y$ as $x_j$ and use the Lemma to derive a valid and observable control law.

## 5. Observable feedback control

We consider a TEG under assumptions of Section 3. Lets take one of its standard transitions as output, which firing epochs are referred to as $y(k)$.

### 5.1. Demonstration of observable controlability

**Theorem 2.** Consider a live TEG with no 0-delay circuit which autonomous subgraph is strongly connected (Section 3 hypothesis), with a single place $p_{ij}$ (containing $m_{ij}$ tokens) subjects to a
temporal constraint of form (5). Given that, (i) There exists an empty path $t_u \xrightarrow{0,B(j)} t_j$, (ii) $\forall k', 0 \le k' < m_{ij}$, $(A^{k'} \cdot B)(i) = \varepsilon$, (iii) $(A^{m_{ij}} \cdot B)(i) \le \tau_{ij}^{max} \cdot B(j)$,

it is sufficient to set

$$u(k) \geq C = (-B(j)) \cdot (-\tau_{ij}^{max}) \cdot x_i(k + m_{ij}) \quad (6)$$

to obtain a control which guarantees to satisfy the constraint for all $k \ge m_{ij}$.

Furthermore, one can always derive an upper-bound of $C$ of the following form, such as it defines a valid and observable feedback control,

$$C \le \delta \cdot y(k + m_{ij} - q) \oplus \left[ \bigoplus_{k'=1}^{p+q} (\mu_{k'+m_{ij}}^{+} \cdot u(k - k')) \right] \quad (7)$$

where $(p, q) \in \mathbb{N}^2$ with $q \ge 0 \oplus (1 + m_{ij} - m_{yu})$, $m_{yu}$ is the smallest token number of paths $t_u \to t_y$, coefficients $p, q, \delta$ and $(\mu_{k'}^+)$ are returned by Alg. 1.

**Proof.** The time constraint to satisfy is expressed by (5) : $x_i(k) \le \tau_{ij}^{max} \cdot x_j(k - m_{ij})$.

Existence of an empty path $t_u \xrightarrow{0,B(j)} t_j$ is equivalent to $B(j) \ne \varepsilon$ (refer to Rem.2). Therefore, $C$ is well-defined in $\mathbb{R}_{\max}$.

$$ \begin{array}{l} (2) : x_j(k) = A(j, :) \cdot x(k-1) \oplus B(j) \cdot u(k) \\ \qquad \Rightarrow x_j(k) \ge B(j) \cdot u(k) \\ u(k) \ge C \\ \qquad \Rightarrow x_j(k) \ge B(j) \cdot (-B(j)) \cdot (-\tau_{ij}^{max}) \cdot x_i(k + m_{ij}) \\ \qquad \Rightarrow x_j(k) \ge (-\tau_{ij}^{max}) \cdot x_i(k + m_{ij}) \\ \qquad \Rightarrow \forall k \ge m_{ij}, \mathbf{x}_i(k) \le \tau_{ij}^{max} \cdot \mathbf{x}_j(k - m_{ij}) \end{array} $$

Moreover, $u(k)$ must respect the state equations system, especially, for any $\phi \in \mathbb{N}$:

$$ \begin{array}{l} (3) \quad \Rightarrow x_i(k) = A^{\phi}(i, :) \cdot x(k - \phi) \oplus \left[ \bigoplus_{k'=0}^{\phi-1} (A^{k'} \cdot B)(i) \cdot u(k - k') \right] \\ \qquad \Rightarrow \forall k' \in \mathbb{N}, x_i(k) \ge \nu_{k'} \cdot x_i(k + m_{ij} - k') \\ \qquad \text{where } \nu_{k'} = (A^{k'} \cdot B)(i) \cdot (-B(j)) \cdot (-\tau_{ij}^{max}) \end{array} \quad (*) $$

Note that $x_i(k)$ is a non decreasing sequence. Hence $x_i(k) \le x_i(k + p)$ for any $p \ge 0$. Therefore, we can assure that (*) will be satisfied if

$$ \forall k' < m_{ij}, \nu_{k'} = \varepsilon \Leftrightarrow (ii) : \forall k' < m_{ij}, (A^{k'} \cdot B)(i) = \varepsilon $$

$$ \text{and } 0 \ge (A^{m_{ij}} \cdot B)(i) \cdot (-B(j)) \cdot (-\tau_{ij}^{max}) \Leftrightarrow (iii) : (A^{m_{ij}} \cdot B)(i) \le \tau_{ij}^{max} \cdot B(j) $$

Note that the two conditions are sufficient but the second is also necessary ($\ast$) cannot be true if (iii) does not hold).

Moreover, under the Theorem's assumptions, we can apply Lemma 1,
$$ \exists \delta \in \mathbb{R}^{+}, \exists (p_0, q_0) \in \mathbb{N}^2, \forall p \ge p_0, \forall q \ge q_0, \\ (-B(j)) \cdot (-\tau_{ij}^{\max}) \cdot x_i(k) \le \delta \cdot y(k-q) \oplus \left[ \bigoplus_{k'=0}^{p+q-1} (\mu_{k'} \cdot u(k-k')) \right] $$

$$ \text{where } \mu_{k'} = (-B(j)) \cdot (-\tau_{ij}^{\max}) \cdot (A^{k'} \cdot B)(i) $$

$$ \Rightarrow C \le \delta \cdot y(k + m_{ij} - q) \oplus \left[ \bigoplus_{k'=0}^{p+q-1} (\mu_{k'} \cdot u(k + m_{ij} - k')) \right] = C' $$

Furthermore, if (i) and (ii) are satisfied, $\mu_{k'} = \varepsilon$ for $0 \le k' \le m_{ij}$, therefore,

$$ C' = \delta \cdot y(k + m_{ij} - q) \oplus \left[ \bigoplus_{k'=m_{ij}+1}^{p+q-1} (\mu_{k'} \cdot u(k + m_{ij} - k')) \right] \\ = \delta \cdot y(k + m_{ij} - q) \oplus \left[ \bigoplus_{k'=1}^{p+q-1-m_{ij}} (\mu_{k'+m_{ij}} \cdot u(k - k')) \right] $$

Lets set $\mu_{k'}^+ = \begin{cases} \mu_{k'} & \text{if } \mu_{k'} > 0, \\ \varepsilon & \text{otherwise.} \end{cases}$

$\forall k' \ge 0, \mu \le 0 \Rightarrow u(k) \ge \mu \cdot u(k-k')$ by definition. Thus, if one defines $C'^+$ as $C'$ with $\mu_{k'}$ replaced by $\mu_{k'}^+$, it follows

$$ \begin{align*} u(k) \ge C'^+ &\Leftrightarrow u(k) \ge C' \\ &\Rightarrow u(k) \ge C \\ &\Rightarrow u(k) \text{ satisfies the constraint.} \end{align*} $$

Finally, $u(k) \ge C'^+$ implies $u(k) \ge \delta \cdot y(k + m_{ij} - q)$. Therefore, implementing this control results in adding a path $t_y \xrightarrow{(q-m_{ij}), \delta} t_u$. According to Thm. 1, for the controlled system to remain live, we ultimately need to satisfy

$$ \begin{align*} m_{yu} + m_{uy} \ge 1 &\Rightarrow m_{yu} + (q - m_{ij}) \ge 1 \\ &\Rightarrow q \ge 1 + m_{ij} - m_{yu} \end{align*} $$

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

**Remark 6.** This method easily extends to multiple constraints, in the exact same fashion as in (Amari et al. 2012) and (Kim and Lee 2015). For each constraint, one derives a suitable control $u_s(k)$. All constraints will be satisfied by $u(k) \ge \bigoplus u_s(k)$.

**Remark 7.** Note that, even though demonstrated starting from the standard form (2), Theorem 2 is not restricted to constraint places with zero or one token.

Consider the example of Fig. 3(b). After expansion, the temporal constraint reads $x_i(k) \le \tau_{ij}^{\max} \cdot x_{j'}(k-1)$.

But since $x_{j'}(k) = x_j(k-1)$, it is equivalent to $x_i(k) \le \tau_{ij}^{\max} \cdot x_j(k-2)$, from which our method can be applied.

## 5.2. Algorithmic procedure for the control derivation

Coefficients from control's definition of Theorem 2 are computed by Algorithm 1. It takes as input the state equations system (matrices A and B), the input and output transitions of the constrained place (i and j) and its token number ($m_{ij}$), the constraint value ($\tau_{ij}^{\max}$), the output transition of the system (y), and the smallest token number of paths $t_u \to t_y$ ($m_{yu}$). It returns all coefficients defining a valid and observable feedback control lower-bound which satisfies the constraint (p, q, $\delta$ and ($\mu_{k'}^+$)) when sufficient conditions are satisfied, and a failure otherwise. Theorem 2 guarantees that the procedure terminates.

# 6. Observable control of cluster tools

Semiconductor manufacturing industry is a good example of practical need for precise temporal control of processing. A commonly used technology is low pressure chemical vapor deposition (LPCVD), which as a strict time limit on maximum acceptable wafer delays. Pushed by opti-
**Algorithm 1** deriveControlCoef

Require: A, B, i, j, m<sub>ij</sub>, τ<sub>ij</sub><sup>max</sup>, y, m<sub>yu</sub>

%Tests for sufficient conditions

if B(j) = ε or (A<sup>m<sub>ij</sub></sup> · B)(i) > τ<sub>ij</sub><sup>max</sup> · B(j) then
print Failure ;
return

end if

for k' ∈ [0..m<sub>ij</sub> − 1] do

if (A<sup>k'</sup> · B)(i) ≠ ε then
print Failure ;
return

end if

end for

%Initialization and tests definition

p := 1 ; q := max( 0, 1 + m<sub>ij</sub> − m<sub>yu</sub> ) ;

ν = − B(j) − τ<sub>ij</sub><sup>max</sup> ;

majorationTest = (ν · A<sup>p+q</sup>(i, :) ≥ A<sup>p</sup>(y, :)) ;

similarityTest = (A<sup>p+q</sup>(i, :), A<sup>p</sup>(y, :)) similar ;

while majorationTest is false do

q := q + 1 ;

end while%q = q<sub>0</sub> from Prop. 4 has been reached.

while similarityTest is false do

p := p + 1 ;

end while%p = p<sub>0</sub> from Prop. 5.3 has been reached.

%Compute the remaining coefficients

δ := max<sub>r∈[1..N]</sub> (ν · A<sup>p+q</sup>(i, r) − A<sup>p</sup>(y, r)) ;
A<sup>p</sup>(y,r)≠ε

for k' ∈ [m<sub>ij</sub> + 1..p + q − 1] do

μ<sub>k'</sub> := (A<sup>k'</sup> · B)(i) − B(j) − τ<sub>ij</sub><sup>max</sup> ;

μ<sub>k'</sub><sup>+</sup> := max (μ<sub>k'</sub>, 0)

end for

return (p, q, δ, (μ<sub>k'</sub><sup>+</sup>))

mization concerns over the past 20 years, there has been a lot of work done oriented toward this
type of industry, from process design and performance evaluation (Srinivasan 1998), to optimized
scheduling (Kim and Lee 2008; Wu and Zhou 2010; Jung and Lee 2012; Jung, Kim, and Lee 2015;
Wu et al. 2013), multirobot cluster tools (Zuberek 2001), and control (Kim and Lee 2012, 2015).

In this section, we present the model of a cluster-tool we use as a case of study and show how to
use our method in practice, plus an evaluation of the control performance. Final discussion includes
a comparison with previous results from the literature.
<figure><img src="image_10.png" /><figcaption>Figure 4. Modeling of a dual-armed cluster tool performing a swap sequence</figcaption></figure>

**6.1. Presentation of the system**

We introduce thereafter the TEG model of a radial dual-armed cluster tool, which description is mostly taken from Kim and Lee (2015). We present how to apply our method to derive a valid and observable feedback control ensuring the satisfaction of wafer residency time constraints.

A cluster tool, as illustrated in Fig. 4(a), consists of several single wafer processing chambers which are also called process modules (PMs), a wafer handling robot, and loadlocks (LLs) for loading and unloading of wafer cassettes in a closed environment. Cluster tools are widely used for various semiconductor manufacturing processes including etching, sputtering, chemical vapor deposition and so on. PMs and LLs are mostly radially arranged around a robot. A robot performs loading and unloading a wafer at a PM or a LL through radial moves. The swap sequence (illustrated in Fig. 4(b)) is a well-known simple robot task sequence for dual-armed cluster tools. It is known to be optimal for most practical cases. It repeats a swap operation at each PM in order of wafer flow. The swap operation unloads a wafer from a PM into the empty arm, rotate the robot arms, and unloads the wafer on the other arm into the PM. This sequence can be modeled by the TEG of Fig. 4(c).
As mentioned in Section 2, firing of transition $t_i$ triggers the beginning of actions associated to the downstream place(s). Note that in this model, there are two process tasks to perform. Nominal duration of $PM_1$ is 100 time units while $PM_2$ takes 240 times units, but can be processed on two modules, hence the two tokens in the lower-side loop. In order to derive the standard state equation (2), this place (in grey on Fig. 4(c)) has been decomposed into two places containing 1 token each, in the fashion of Fig. 1.

Processing task $PM_1$ is subject to a time constraint, i.e., a wafer must not stay longer than 110 time units in $PM_1$. We assume the firing of transition $t_6$ (starting $PM_1$) is a controllable event, which is represented by the input transition $t_u$ connected to $t_6$ on Fig. 4(c). It follows that the dynamics of this TEG are expressed by the following state-space equation

$$x(k) = A.x(k-1) \oplus B.u(k)$$

$$ \text{where } A = \begin{pmatrix} \dots & \dots & \dots & \dots & 5 \\ \dots & \dots & \dots & \dots & 10 \\ \dots & \dots & \dots & \dots & 100 \\ \dots & \dots & \dots & \dots & 105 \\ \dots & \dots & \dots & \dots & 110 \\ \dots & \dots & \dots & \dots & 115 \\ \dots & \dots & \dots & \dots & 120 \\ \dots & \dots & \dots & \dots & 125 \\ \dots & \dots & \dots & \dots & 130 \\ \dots & \dots & \dots & \dots & 135 \\ \dots & \dots & \dots & \dots & 140 \\ \dots & \dots & \dots & \dots & 145 \\ \dots & \dots & \dots & \dots & 10 \end{pmatrix}, B = \begin{pmatrix} \dots \\ \dots \\ \dots \\ \dots \\ \dots \\ \dots \\ \dots \\ \dots \\ \dots \\ \dots \end{pmatrix} \text{ and } \varepsilon \text{ is replaced by a . for the sake of readability.} $$

## 6.2. Observable control of the system

We consider the unloading of a processed part in one of the loadlocks LL as the system's output. Hence, we will consider $y = x_{12}$, that is to say firing of $t_i$ ($i \neq 12$) are considered to be unobservable events.

**Remark 8.** Note that the choice of $x_{12}$ is arbitrary. Our approach can be applied with any of the system's events, as long as Theorem 1's conditions are satisfied.

$PM_1$'s time constraint is expressed by the following inequality

$$x_3(k) \leq \tau_{36}^{\max} \cdot x_6(k-1) = 110 \cdot x_6(k-1) \quad (8)$$

The system's model satisfies hypothesis of Theorem 2. It is live with no 0-delay circuit and its autonomous subgraph is strongly connected. Furthermore,

(i) there exists an empty path $t_u \xrightarrow{0,B(j)} t_j$,

(ii) $(B)(3) = \varepsilon$,

(iii) $(A \cdot B)(3) = 100 \leq 110 + 0 = \tau_{36}^{\max} \cdot B(6)$.

It follows that constraint (8) is satisfied by

$$u(k) \geq C = -(B(6) + \tau_{36}^{\max}) \cdot x_3(k+1) = -110 \cdot x_3(k+1)$$
<figure><img src="image_11.png" /><figcaption>Figure 5. Observable feedback controlled TEG</figcaption></figure>

Applying Algorithm 1 to $\mathcal{C}$ returns $p = 2$, $q = 2$, $\delta = 100$, and $\mu_{k'}^{+} = [105, 220]'$, hence

$$u(k) \geq 100 \cdot y(k-1) \oplus 105 \cdot u(k-1) \oplus 205 \cdot u(k-2)$$

satisfies constraint (8). Implementation of this control law is represented on Fig. 5.

One can note that this control law is valid (controlled system is still live – see Theorem 1) and causal (delays are non-negative).

### 6.3. Discussions on control performance and optimality

To evaluate control performance in our setting, the natural parameter to consider is the system's cycle time (i.e., the inverse of the throughput). An **optimal control** could be defined as a control which does not increase the cycle time of the uncontrolled system.

Let $\lambda$ and $\tilde{\lambda}$ be the cycle times of the uncontrolled and controlled systems respectively. Applying relation (4) to our control returns

$$\lambda = 127.5 \text{ time units, and}$$

$$\tilde{\lambda} = 130 \text{ time units} > \lambda$$

Thus, our control might not be optimal, as it affects the system's cycle time.

In our work, as in previous approaches from the literature, we derive sufficient conditions for controlability of temporal constraints the kind of (5). There are no proof (at least so far) that such control strategies are minimally restrictive. This could be true if sufficient conditions from Theorem 2 are also necessary. This remains an open question.

Although this was only partially presented in this paper, we have implemented our control method in simulation and tested it on several manufacturing scenarios from the literature (Atto, Martinez, and Amari 2011; Kim and Lee 2015). As one can expect, compared to the full-observability case, our control approach tends to increase more the cycle time of the controlled system. This is natural as we have some extra restrictions on the information available. It is the price one has to pay to control under partial observability.

Note that it is not always the case. The cycle time will increase depending on the system's architecture, the constraints values, and the choice of the state variable set as output.
**Remark 9.** For instance, in our example, one can derive an observable control law which is also optimal (i.e., which does not increase the system's cycle time) by considering $x_5$ as the system's output. The resulting control law is then

$$u(k) = 105 \cdot u(k-1) \oplus 220 \cdot u(k-2) \oplus 335 \cdot u(k-3) \oplus 135 \cdot y(k-1)$$

which preserves $\tilde{\lambda} = 127.5$ time units.

However, up to this point in our research, there is no proof this can always be achieved.

## 6.4. Comparison with previous approaches

On Fig. 5, we also represent the control law derived in Kim and Lee (2015), showed in grey. Compared to our approach, this control uses as input firings of transitions $t_{12}$ but also $t_6$ and $t_{10}$. Until the present contribution, the control dependence with these events could not be handled. If only one of such events is unobservable, we could not guarantee the controllability of the system. In introduction, we claimed our control method to be an extension of this of Kim and Lee (2015). Indeed, while stated otherwise, their approach consists simply in expressing (6) (refer to Thm. 2) into feedback form. This is done easily by using relation (3) with $\phi = m_{ij} + 1$,

$$x_i(k + m_{ij}) = (A^{m_{ij}+1})(i, :), x(k-1) \oplus \left[ \bigoplus_{k'=0}^{m_{ij}} A^{k'} \cdot B \cdot u(k + m_{ij} - k') \right]$$

Under hypothesis (ii) and (iii) of Thm. 2, terms in $u$ simplify and we get

$$u(k) \ge ((A^{m_{ij}+1})(i, :), (-B(j)) \cdot (-\tau_{ij}^{max})) \cdot x(k-1)$$

The problem here is that such expression uses possibly all state variables in its definition, while some of them might not be observable. Therefore, our approach consists in pushing further the order of $\phi$. We showed that, if one looks "far enough" in the past, firing epochs of any state variable of interest ($x_i$ in this setting) can be over-estimated by previous firings of any other state variable (e.g., the output $y$) and some positive delays. This is Lemma 1's result.

Theorem 2 shows how to use this result to derive a valid and observable feedback control, which can be further implemented on the system.

## 7. Conclusions

Max-Plus models are useful to capture time dependencies of discrete-event systems. In the literature, several approaches address the control of such models, especially in cases of strict time constraints (e.g., Amari et al. (2012); Atto, Martinez, and Amari (2011); Maia, Hardouin, and Cury (2013); Kim and Lee (2015)). It was demonstrated that one can derive a control sequence $u(k)$ which ensures such constraints are met. However, in these works, all events are assumed to be observable, which means all transitions firing epochs can be used to feed the control. This is a strong limitation in practice.

In this paper, we relax that hypothesis. In other word, we tackle the **synthesis of a controller under partial observability**. We demonstrate that for any strongly connected TEG, one can **always derive a valid and observable feedback control** (i.e., depending on output and the control events only), ensuring a given set of temporal constraints will be satisfied. The procedure to derive such a control law is provided. Furthermore, we use the practical example of a dual-armed cluster tool to demonstrate the use of our method and discuss its performance.
As a final contribution related to this work, we are currently developing a plug-in for the TINA (TIme petri Net Analyzer) software tool (Berthomieu, Ribet, and Vernadat 2004). Taking the TEG to control as input (under textual or graphic form), it returns the control policy, adds it to the model and evaluates the cycle time of the controlled system. This tool is also interesting because of another (already existing) plug-in performing LTL model-checking on Time and Timed Petri nets. For example, it allows one to verify the controller we have derived does indeed verify our constraints.

To push further our synthesis approach, it would be interesting to further investigate **conditions for an optimal control**, that is, whether or not one can derive an observable feedback control which will not increase the system's cycle time, or at least no more that a fully-observable control does. Other perspectives include the more general study of necessary conditions for contolability, the satisfaction of time constraints on paths instead of places, relaxing the empty-path hypothesis ((i) in Thm. 2), or the efficient control of systems using multiple inputs (i.e., multiple control transitions). Finally, the fundamental limitation of our approach is the inability (or at least inefficiency) of TEGs for handling conflicts. It would be interesting to consider extensions of such control approaches to sets of TEGs with conflicts, in the fashion of Addad, Amari, and Lesage (2010).

## References

Addad, Boussad, Saïd Amari, and Jean-Jacques Lesage. 2010. "Analytic calculus of response time in networked automation systems." *Automation Science and Engineering, IEEE Transactions on* 7 (4): 858-869.

Amari, Saïd, Isabel Demongodin, Jean Jacques Loiseau, and Claude Martinez. 2012. "Max-plus control design for temporal constraints meeting in timed event graphs." *Automatic Control, IEEE Transactions on* 57 (2): 462-467.

Atto, Abdourrahmane M, Claude Martinez, and Said Amari. 2011. "Control of discrete event systems with respect to strict duration: Supervision of an industrial manufacturing plant." *Computers & Industrial Engineering* 61 (4): 1149-1159.

Baccelli, François, Guy Cohen, Geert Jan Olsder, and Jean-Pierre Quadrat. 1992. *Synchronization and linearity: an algebra for discrete event systems*. John Wiley & Sons Ltd.

Berthomieu, Bernard, P-O Ribet, and François Vernadat. 2004. "The tool TINA-construction of abstract state spaces for Petri nets and time Petri nets." *International Journal of Production Research* 42 (14): 2741-2756.

Bonhomme, Patrice. 2013. "Scheduling and control of real-time systems based on a token player approach." *Discrete Event Dynamic Systems* 23 (2): 197-209.

Diouri, Idriss, J-P Georges, and Eric Rondeau. 2007. "Accommodation of delays for networked control systems using classification of service." In *Networking, Sensing and Control, 2007 IEEE International Conference on*, 410-415. IEEE.

Goverde, Rob MP. 2007. "Railway timetable stability analysis using max-plus system theory." *Transportation Research Part B: Methodological* 41 (2): 179-201.

Houssin, Laurent, Sébastien Lahaye, and Jean-Louis Boimond. 2007. "Just in time control of constrained (max,+)-linear systems." *Discrete Event Dynamic Systems* 17 (2): 159-178.

Houssin, Laurent, Sébastien Lahaye, and Jean-Louis Boimond. 2013. "Control of (max,+)-linear systems minimizing delays." *Discrete Event Dynamic Systems* 23 (3): 261-276.

Jung, Chihyun, Hyun-Jung Kim, and Tae-Eog Lee. 2015. "A branch and bound algorithm for cyclic scheduling of timed Petri nets." *Automation Science and Engineering, IEEE Transactions on* 12 (1): 309-323.

Jung, Chihyun, and Tae-Eog Lee. 2012. "An efficient mixed integer programming model based on timed Petri nets for diverse complex cluster tool scheduling problems." *Semiconductor Manufacturing, IEEE Transactions on* 25 (2): 186-199.

Katz, Ricardo David. 2007. "Max-plus (A, B)-invariant spaces and control of timed discrete-event systems." *Automatic Control, IEEE Transactions on* 52 (2): 229-241.

Kim, Chulhan, and Tae-Eog Lee. 2012. "Feedback control design for cluster tools with wafer residency time constraints." In *Systems, Man, and Cybernetics (SMC), 2012 IEEE International Conference on,*
3063–3068. IEEE.

Kim, C., and T.-E. Lee. 2015. "Feedback Control of Cluster Tools for Regulating Wafer Delays." Automation Science and Engineering, IEEE Transactions on PP (99): 1–11.

Kim, Ja-Hee, and Tae-Eog Lee. 2003. "Schedule stabilization and robust timing control for time-constrained cluster tools." In Robotics and Automation, 2003. Proceedings. ICRA '03. IEEE International Conference on, Vol. 1Vol. 1, 1039–1044. IEEE.

Kim, Ja-Hee, and Tae-Eog Lee. 2008. "Schedulability analysis of time-constrained cluster tools with bounded time variation by an extended Petri net." Automation Science and Engineering, IEEE Transactions on 5 (3): 490–503.

Lhommeau, Mehdi, Luc Jaulin, and Laurent Hardouin. 2012. "A non-linear set-membership approach for the control of Discrete Event Systems." In Workshop on Discrete Event Systems-WODES, xx. https://hal-ensta-bretagne.archives-ouvertes.fr/hal-00746053/.

Maia, Carlos Andrey, CR Andrade, and Laurent Hardouin. 2011. "On the control of max-plus linear system subject to state restriction." Automatica 47 (5): 988–992.

Maia, Carlos Andrey, Laurent Hardouin, and José ER Cury. 2013. "Some results on the feedback control of max-plus linear systems under state constrains." In Decision and Control (CDC), 2013 IEEE 52nd Annual Conference on, 6992–6997. IEEE.

Martinez, Claude, and Pierre Castagna. 2003. "Sizing of an industrial plant under tight time constraints using two complementary approaches:(max,+)$\overline{\epsilon}$ algebra and computer simulation." Simulation Modelling Practice and Theory 11 (1): 75–88.

Murata, Tadao. 1989. "Petri nets: Properties, analysis and applications." Proceedings of the IEEE 77 (4): 541–580.

Srinivasan, RS. 1998. "Modeling and performance analysis of cluster tools using Petri nets." Semiconductor Manufacturing, IEEE Transactions on 11 (3): 394–403.

Wang, Yihui, Bart De Schutter, Ton JJ van den Boom, and Bin Ning. 2013. "Optimal trajectory planning for trains–A pseudospectral method and a mixed integer linear programming approach." Transportation Research Part C: Emerging Technologies 29: 97–114.

Wu, NaiQi, and MengChu Zhou. 2010. "A closed-form solution for schedulability and optimal schedul-
ing of dual-arm cluster tools with wafer residency time constraint based on steady schedule analysis."
*Automation Science and Engineering, IEEE Transactions on* 7 (2): 303–315.

Wu, NaiQi, MengChu Zhou, Feng Chu, and Chengbin Chu. 2013. “A Petri-net-based scheduling strategy for dual-arm cluster tools with wafer revisiting.” *Systems, Man, and Cybernetics: Systems, IEEE Transactions on* 43 (5): 1182–1194.

Zuberek, WM. 2001. "Timed Petri net models of multi-robot cluster tools." In Systems, Man, and Cybernetics (SMC), 2001 IEEE International Conference on, Vol. 4Vol. 4, 2729–2734. http://web.cs.mun.ca/~wlodek/pdf/01-SMC-1.pdf.

**Appendix A. Proofs of Section 4 properties and lemma**

*Proof of Prop. 3.*

$$
\begin{align*}
& \text{For any } r \in [1..N], A^p(j,r) = \tau_{jr} \neq \varepsilon \\
& \quad \Rightarrow \exists \text{ a primal path } t_r \xrightarrow{p,\tau_{jr}} t_j \tag*{\{Rem. 2\}}
\end{align*}
$$

$$
\exists t_j \xrightarrow{m_{ij}, \tau_{ij}} t_i
\begin{align*}
& \Rightarrow \exists t_r \xrightarrow{p, \tau_{jr}} t_j \xrightarrow{m_{ij}, \tau_{ij}} t_i \\
& \Rightarrow \exists t_r \xrightarrow{p+m_{ij}, \tau_{ij} \cdot \tau_{jr}} t_i, \text{ which is primal (but not necessarily unique),} \\
& \Rightarrow A^{p+m_{ij}}(i,r) \ge \tau_{ij} \cdot \tau_{jr} = \tau_{ij} \cdot A^p(j,r) \tag*{\{Rem. 2\}}
\end{align*}
$$

{Rem. 2}

Else, if $A^p(j,r) = \varepsilon$, the result trivially holds. In any case, property holds true for any $r$, thus it
holds for all. $\square$

*Proof of Prop. 4.*

There exists a circuit $t_i \xrightarrow{m_{ii}, \tau_{ii}} t_i$, therefore,
$$ \forall p \in \mathbb{N}^*, A^{p+m_{ii}}(i, :) \geq \tau_{ii} \cdot A^p(i, :) \qquad \{\text{Prop. 3}\} $$

One can recursively set $p := p + m_{ii}$ and easily show that

$$ \Rightarrow \forall p \in \mathbb{N}^*, \forall q \in \mathbb{N}, A^{p+q \times m_{ii}}(i, :) \geq (q \times \tau_{ii}) \cdot A^p(i, :) $$

One can further set $p := p + m_{ij}$,

$$ \Rightarrow \forall p \in \mathbb{N}^*, \forall q \in \mathbb{N}, A^{p+m_{ij}+q \times m_{ii}}(i, :) \geq (q \times \tau_{ii}) \cdot A^{p+m_{ij}}(i, :) $$

Plus:

$$ \exists t_j \xrightarrow{m_{ij}, \tau_{ij}} t_i \qquad \begin{aligned} & \Rightarrow \forall p \in \mathbb{N}^*, A^{p+m_{ij}}(i, :) \geq \tau_{ij} \cdot A^p(j, :) \\ & \Rightarrow \forall p \in \mathbb{N}^*, \forall q \in \mathbb{N}, A^{p+m_{ij}+q \times m_{ii}}(i, :) \geq (q \times \tau_{ii} + m_{ij}) \cdot A^p(j, :) \end{aligned} \qquad \{\text{Prop. 3}\} $$

As we assumed no 0-delay circuits, $\tau_{ii} > 0$, therefore,

$$ \begin{aligned} & \forall \nu \in \mathbb{R}, \exists q_0 \in \mathbb{N}, \nu + (q_0 \times \tau_{ii} + m_{ij}) \geq 0 \\ & \Rightarrow \forall q \geq q_0, \nu \cdot A^{p+m_{ij}+q \times m_{ii}}(i, :) \geq (\nu + q \times \tau_{ii} + m_{ij}) \cdot A^p(j, :) \\ & \Rightarrow \forall \nu \in \mathbb{R}, \forall q \geq q_0, \forall p \in \mathbb{N}^*, \nu \cdot A^{p+m_{ij}+q \times m_{ii}}(i, :) \geq A^p(j, :) \end{aligned} \qquad \square $$

**Proof of Prop. 5.**

Existence of both $t_j \xrightarrow{m_{ij}, \tau_{ij}} t_i$ and $t_i \xrightarrow{m_{ji}, \tau_{ji}} t_j$ implies there exists at least one circuit $t_i \xrightarrow{m_{ii}, \tau_{ii}} t_j$ where $m_{ii} = m_{ij} + m_{ji}$. For any of such circuit, let $(\eta_i^q)_{q \in \mathbb{N}}$ be the sequel counting the number of $\varepsilon$-element in $A^{q \times m_{ii}}(i, :)$.

$$ \begin{aligned} & \forall p \in \mathbb{N}^*, A^{p+m_{ii}}(i, :) \geq \tau_{ii} \cdot A^p(i, :) \qquad \{\text{Prop. 3}\} \\ & \Rightarrow A^{p+m_{ii}}(i, :) \geq A^p(i, :) \qquad \{\text{non-negative delays}\} \\ & \Rightarrow A^{(q+1) \times m_{ii}}(i, :) \geq A^{q \times m_{ii}}(i, :) \qquad \{p := q \times m_{ii}\} \\ & \Rightarrow \forall r \in [1..N], \left[ (A^{(q+1) \times m_{ii}}(i,r) = \varepsilon \Rightarrow A^{q \times m_{ii}}(i,r) = \varepsilon) \right] \\ & \Rightarrow \eta_{q+1}^i \leq \eta_q^i \\ & \Rightarrow (\eta_q^i)_{q \in \mathbb{N}} \text{ is decreasing, plus it is minimized by 0,} \\ & \Rightarrow (\eta_q^i)_{q \in \mathbb{N}} \text{ converges. Since it takes only discrete values, the sequel reaches its limit at a given step } l \geq 0. \\ & \Rightarrow \exists l \in \mathbb{N}, \forall q \in \mathbb{N}, \eta_{l+q}^i = \eta_l^i \\ & \Rightarrow [A^{(l+q) \times m_{ii}}(i,r) = \varepsilon \Leftrightarrow A^{l \times m_{ii}}(i,r) = \varepsilon] \end{aligned} $$

One can set $p_0 := l \times m_{ii}$,

$$ \Rightarrow \exists p_0 \in \mathbb{N}, \forall q \in \mathbb{N}, \quad [A^{q \times m_{ii}+p_0}(i, :) = \varepsilon \Leftrightarrow A^{p_0}(i, :) = \varepsilon] \qquad (A1) $$

which concludes proof of 5.1 by use of Prop. 1.

Furthermore, as there exist both $t_i \xrightarrow{m_{ij}, \tau_{ij}} t_j$ and $t_j \xrightarrow{m_{ji}, \tau_{ji}} t_i$ paths,

$$ \forall p \in \mathbb{N}^*, \left\{ \begin{array}{l} A^{p+m_{ij}}(i, :) \geq A^p(j, :) \\ A^{p+m_{ji}}(j, :) \geq A^p(i, :) \end{array} \right. \qquad \{\text{Prop. 3}\} \\ \Rightarrow \forall p \in \mathbb{N}^*, A^{p+m_{ij}+m_{ji}}(i, :) \geq A^{p+m_{ji}}(j, :) \geq A^p(i, :) \\ \Rightarrow \forall p \in \mathbb{N}^*, A^{p+m_{ii}}(i, :) \geq A^{p+m_{ii}}(j, :) \geq A^p(i, :) $$

One can set $p := p_0 = l \times m_{ii}$,

$$ \Rightarrow A^{(l+1) \times m_{ii}}(i, :) \geq A^{l \times m_{ii}+m_{ji}}(j, :) \geq A^{l \times m_{ii}}(i, :) $$

Thus, for any $r \in [1..N]$:

$$ \begin{array}{l} \textcircled{1} \Rightarrow \left[ \begin{array}{lcl} A^{(l+1) \times m_{ii}}(i,r) = \varepsilon & \Rightarrow & A^{l \times m_{ii}+m_{ji}}(j,r) = \varepsilon \\ A^{l \times m_{ii}+m_{ji}}(j,r) = \varepsilon & \Rightarrow & A^{l \times m_{ii}}(i,r) = \varepsilon \end{array} \right] \\ \textcircled{2} \Rightarrow \left[ \begin{array}{lcl} \Leftrightarrow & A^{p_0}(i,r) & = \varepsilon \\ (A1):q=1 \Leftrightarrow & A^{m_{ii}+p_0}(i,r) & = \varepsilon \\ \Leftrightarrow & A^{(l+1) \times m_{ii}}(i,r) & = \varepsilon \end{array} \right] \end{array} $$
$$ \Rightarrow [A^{(l+1) \times m_{ii}}(i, :) = \varepsilon \Leftrightarrow A^{l \times m_{ii}+m_{ji}}(j, :) = \varepsilon] $$

$$ \Rightarrow [A^{p_0+m_{ij}+m_{ji}}(i, :) = \varepsilon \Leftrightarrow A^{p_0+m_{ji}}(j, :) = \varepsilon] $$

One can set $\tilde{p}_0 := p_0 + m_{ji}$,

$$ \Rightarrow [A^{\tilde{p}_0+m_{ij}}(i, :) = \varepsilon \Leftrightarrow A^{\tilde{p}_0}(j, :) = \varepsilon] $$

Using Prop. 1, we deduce that,

$$ \Rightarrow \forall p \ge \tilde{p}_0, (A^{p+m_{ij}}(i, :), A^p(j, :)) \text{ similar, which concludes 5.2's proof.} $$

Finally, 5.1 holds for all $p \ge p_0$, so it holds in particular for all $p \ge \tilde{p}_0$. Therefore, for all $q \in \mathbb{N}$ and $p \ge \tilde{p}_0$,

$(A^{p+q \times m_{ii}}(i, :), A^p(i, :))$ similar,

$$ \text{Prop. 1} \Rightarrow (A^{p+q \times m_{ii}+m_{ij}}(i, :), A^{p+m_{ij}}(i, :)) \text{ similar,} $$

$$ 5.2 \Rightarrow (A^{p+q \times m_{ii}+m_{ij}}(i, :), A^p(j, :)) \text{ similar, which proves 5.3.} \quad \square $$

**Proof of Lemma. 1.**

Existence of both $t_j \xrightarrow{m_{ij}, \tau_{ij}} t_i$ and $t_i \xrightarrow{m_{ji}, \tau_{ji}} t_j$ implies there exists at least one circuit $t_i \xrightarrow{m_{ii}, \tau_{ii}} t_i$. Then, from Lemma's hypothesis, Prop. 4 and 5 provide,

$$ \forall \nu \in \mathbb{R}, \exists (p_0, q_0) \in \mathbb{N}^2, \forall p \ge p_0, \forall q \ge q_0, $$

$$ (i) : \nu \cdot A^{p+m_{ij}+q \times m_{ii}}(i, :) \ge A^p(j, :) $$

Right-hand side's terms are contained in the left-hand side's.

$$ (ii) : (A^{p+m_{ij}+q \times m_{ii}}(i, :), A^p(j, :)) \text{ similar} $$

Both vectors have the same support (i.e., the same non-$\varepsilon$ elements).

$$ \text{Let set } Q := m_{ij} + q \times m_{ii} \text{ and define, } \delta := \max_{\substack{r \in [1..N] \\ A^p(j,r) \ne \varepsilon}} (\nu \cdot A^{p+Q}(i,r) - A^p(j,r)). $$

Note that we need to be careful in $\delta$ definition as $(-\varepsilon) = +\infty$ does not belong to $\mathbb{R}_{\max}$, hence the rejection of $r$ such that $A^p(j, r) = \varepsilon$.

$$ (i) \Rightarrow \delta \ge 0 $$

$$ \Rightarrow \forall r \in [1..N], A^p(j,r) \ne \varepsilon, \quad \nu \cdot A^{p+Q}(i,r) \le \delta \cdot A^p(j,r) $$

$$ (ii) \Rightarrow (iii) : \nu \cdot A^{p+Q}(i, :) \le \delta \cdot A^p(j, :) $$

(3) with $\phi := p$ gives

$$ \begin{align*} x_j(k) &= A^p(j, :) \cdot x(k-p) & \oplus \left[ \bigoplus_{k'=0}^{p-1} (A^{k'} \cdot B)(j) \cdot u(k-k') \right] \\ \Rightarrow x_j(k-Q) &= A^p(j, :) \cdot x(k-(p+Q)) & \oplus \left[ \bigoplus_{k'=0}^{p-1} (A^{k'} \cdot B)(j) \cdot u(k-Q-k') \right] \\ \Rightarrow (iv) : x_j(k-Q) &\ge A^p(j, :) \cdot x(k-(p+Q)) \end{align*} $$

Similarly, for any $\nu \in \mathbb{R}$, (3) with $\phi := p+Q$ gives

$$ \begin{align*} \nu \cdot x_i(k) &= \nu \cdot A^{p+Q}(i, :) \cdot x(k-(p+Q)) \oplus \left[ \bigoplus_{k'=0}^{p+Q-1} \nu \cdot (A^{k'} \cdot B)(i) \cdot u(k-k') \right] \\ \stackrel{(iii)}{\Rightarrow} \nu \cdot x_i(k) &\le \delta \cdot A^p(j, :) \cdot x(k-(p+Q)) \oplus \left[ \bigoplus_{k'=0}^{p+Q-1} \nu \cdot (A^{k'} \cdot B)(i) \cdot u(k-k') \right] \\ \stackrel{(iv)}{\Rightarrow} \nu \cdot x_i(k) &\le \delta \cdot x_j(k-Q) \oplus \left[ \bigoplus_{k'=0}^{p+Q-1} \nu \cdot (A^{k'} \cdot B)(i) \cdot u(k-k') \right] \end{align*} $$

which concludes the proof by setting $\mu_{k'} = \nu \cdot (A^{k'} \cdot B)(i)$. $\square$

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