# Optimal control of timed event graphs with resource sharing and output-reference update

Germano Schafaschek, Laurent Hardouin, Jörg Raisch

► To cite this version:

Germano Schafaschek, Laurent Hardouin, Jörg Raisch. Optimal control of timed event graphs with resource sharing and output-reference update. Automatisierungstechnik, 2020, 68 (7), pp.512-528. 10.1515/auto-2020-0051. hal-02961755

HAL Id: hal-02961755

https://univ-angers.hal.science/hal-02961755

Submitted on 8 Oct 2020

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

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

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

Distributed under a Creative Commons Attribution 4.0 International License
<figure><img src="image_2.png" /></figure>

# Methods

Germano Schafaschek*, Laurent Hardouin and Jörg Raisch

# Optimal control of timed event graphs with resource sharing and output-reference update

Optimalsteuerung zeitbehafte Synchronisationsgraphen mit Ressourcenkonkurrenz und Aktualisierung von Referenzsignalen

https://doi.org/10.1515/auto-2020-0051

Received April 8, 2020; accepted June 4, 2020

**Abstract:** Timed event graphs (TEGs) are a subclass of timed Petri nets that model synchronization and delay phenomena, but not conflict or choice. We consider a scenario where a number of TEGs share one or several resources and are subject to changes in their output-reference signals. Because of resource sharing, the resulting overall discrete event system is *not* a TEG. We propose a formal method to determine the optimal control input for such systems, where optimality is in the sense of the widely adopted just-in-time criterion. Our approach is based on a prespecified priority policy for the TEG components of the overall system. It builds on existing control theory for TEGs, which exploits the fact that, in a suitable mathematical framework (idempotent semirings such as the max-plus or the min-plus algebra), the temporal evolution of TEGs can be described by a set of linear time-invariant equations.

**Keywords:** timed event graphs, idempotent semirings, just-in-time control, min-plus algebra, resource sharing

**Zusammenfassung:** Zeitbehafte Synchronisationsgraphen (ZSGen) bilden eine spezielle Klasse zeitbehafte teter Petri-Netze. Sie können Synchronisations- und Verzögerungsphänomene modellieren, nicht aber Konflikte. Wir untersuchen ein Szenario, in dem sich mehrere ZSGen eine oder mehrere Ressourcen teilen und die Referenzsignale der ZSGen unvorhersehbaren Änderungen unterworfen sind. Da die beteiligten ZSGen um Ressourcen konkurren, ist das Gesamtsystem kein ZSG. Wir beschreiben

eine formale Vorgehensweise zur Bestimmung des im just-in-time Sinne optimalen Stellsignals für dieses Gesamtsystem. Unser Ansatz basiert auf einer vorab festgelegten Priorisierung der einzelnen ZSGen. Er baut auf der existierenden Regelungstheorie für ZSGen auf und nutzt die Tatsache, dass sich die zeitliche Entwicklung von ZSGen in einem geeigneten mathematischen Rahmen (idempotente Halbringe wie beispielsweise die max-plus- oder die min-plus-Algebra) durch lineare zeitinvariante Gleichungen beschreiben lässt.

**Schlagwörter:** Zeitbehafte Synchronisationsgraphen, idempotente Halbringe, min-plus-Algebra, just-in-time Regelung, Ressourcenkonkurrenz

This contribution is dedicated to Prof. Dr.-Ing. Dr. h.c. Michael Zeitz on the occasion of his 80th birthday.

# 1 Introduction

In this paper, we consider a scenario where several discrete event subsystems, each modeled by a timed event graph (TEG), share one or more resources and where the reference signals for the subsystems may change unexpectedly. TEGs are a subclass of timed Petri nets. They are characterized by the fact that each place has precisely one upstream and one downstream transition and all arcs have weight one. TEGs can model synchronization and delay phenomenon but not conflict, choice, or the sharing of resources. Therefore, the overall system class investigated in this contribution is more general than the subclass of TEGs. We argue that it models a wide range of application scenarios, e. g., in manufacturing or transportation. We aim at determining the optimal control input, where optimality is understood in the sense of the widely adopted just-in-time criterion. In particular, the aim is to fire all input transitions as late as possible while guaranteeing that the firing of output transitions is not later than specified by the respective reference signal. For example, in a manufacturing

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

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

<footnote>*Corresponding author: Germano Schafaschek, Fachgebiet Regelungssysteme, Technische Universität Berlin, Berlin, Germany, e-mail: schafaschek@control.tu-berlin.de</footnote>

<footnote>Laurent Hardouin, Laboratoire Angevin de Recherche en Ingénierie des Systèmes, Université d'Angers, Angers, France, e-mail: laurent.hardouin@univ-angers.fr</footnote>

<footnote>Jörg Raisch, Fachgebiet Regelungssysteme, Technische Universität Berlin, Berlin, Germany, e-mail: raisch@control.tu-berlin.de</footnote>
context, the firing of an input transition could correspond to the provisioning of raw material, while the firing of an output transition could model the completion of a workpiece. In general, a just-in-time policy aims at satisfying customer demands while minimizing internal stocks. We solve this optimal control problem for a fixed prioritization of subsystems, but allow updates of the reference signals.

It is a well-known fact that in a suitable mathematical framework, namely an idempotent semiring (or dioid) setting such as the max-plus or the min-plus algebra, the evolution of TEGs can be described by linear equations (see [3] for a thorough coverage). Based on such linear dioid models, an elaborate control theory has become available. Given an a-priori known reference signal, it mostly focuses on optimality in the sense of the just-in-time criterion and considers feedforward and (output or state) feedback control. For a tutorial introduction to this control framework, the reader may refer to [11].

In some applications, it may be necessary to update the reference for the system's output during run-time, for instance when customer demand is increased and a new production objective must be considered. In [12], a strategy has been presented to optimally update the input in face of such changes in the output-reference. In case the new reference encodes unachievable requirements, the authors show how to relax it such that optimal control for the relaxed reference leads to firing times of the output transitions that are as close as possible to (but possibly later than) the originally desired ones.

Systems of practical interest often involve limited resources that are shared among different subsystems. As examples, one can think of an automated manufacturing cell where the same tool/robot may be required in several steps of the production process, or of computational tasks competing for the use of a fixed number of processors. TEGs do not allow for concurrency or choice and hence are unfit to model such resource-sharing phenomena. Overcoming this limitation has motivated several efforts in the literature, with a predominant focus on modeling and analysis. In [7, 6], a modeling strategy for continuous timed Petri nets is proposed where conflict places are handled by the use of priority rules. In [8], constraints due to resource sharing are translated into additional inequalities in the system model. [1] models conflicting TEGs by max-plus time-varying equations; the models are restricted to safe conflict places. [5] relaxes the safety hypothesis on the conflict places and studies cycle time evaluation on conflicting TEGs with multiple shared resources. Works focusing on control of TEGs with resource sharing are less abundant. In [15], the authors show that concurrency can be

incorporated into switching max-plus linear systems models and apply model predictive control techniques to obtain the optimal switching sequence. In [13], the modeling and control of a number of TEGs that share resources is addressed. Obviously, because of resource sharing, the overall system is no longer a TEG. Under a prespecified priority policy, the authors show how to compute the optimal (just-in-time) input for each subsystem with respect to its individual output-reference.

In this paper, we propose a formal method to obtain the optimal control inputs in face of changes in the output-references for TEGs that share resources under a given priority policy, thus merging the results from [12] with those of [13]. This paper represents an extended version of a recent conference paper [14]. It extends the contributions of [14] in the following ways: the results are presented more didactically, with more detailed explanations of some crucial steps. Most significantly, we generalize the method to the case of an arbitrary number of shared resources (Section 5.3 is entirely new), whereas in [14] only the case of a single shared resource is explicitly covered; as a prerequisite thereto, we also formalize the extension of the results from [13], originally only presented for at most two shared resources, to the case of multiple shared resources — Section 4.3 originates here. The examples in this paper, although still simple, are more general and elucidative than those from [14]. We also enhance the presentation of preliminary concepts, providing a brief survey of the theoretical background and making the paper largely self-contained.

Prospective applications for the proposed approach include emergency call centers (as studied, e. g., in [2], which, in turn, is based on [7, 6]) where the arrival of high-priority calls may render it necessary to reschedule the answers to lower-priority ones, or manufacturing scenarios where changes in the demand of high-priority products will require a re-adjustment of resource allocations by processing steps related to lower-priority products.

We consider a set of TEGs operating under optimal schedules with respect to their individual output-references and to the priority policy; supposing the output-reference of one or more of the subsystems is updated during run-time, we show how to optimally update all their inputs so that their outputs are as close as possible to the corresponding new references and the priority policy is still observed. In case the performance limitation of the subsystems, combined with the limited availability of the resources, make it impossible to respect some of the new references, we also provide the optimal way to relax such references so that the ultimately obtained inputs lead to tracking them as closely as possible.
The examples presented along this paper serve solely the purpose of illustrating and helping to clarify the results. Due to space limitations and also to the fact that existing computational tools are not in pace with the state-of-the-art theoretical results proposed here, we do not present a more comprehensive example. The proposed method can, however, be applied to larger, more general systems of practical relevance.

The paper is organized as follows. Section 2 summarizes well-known facts on idempotent semirings. In Section 3, we adapt existing results on the control of TEGs with output-reference update to the idempotent semiring used in this paper. Section 4 provides an overview of previous results on modeling and control of TEGs with shared resources. The major purpose of these three sections is making the paper as self-contained as possible. In Section 5, the main contributions of the paper are presented; namely, we formulate and solve the problem of determining the optimal control inputs for TEGs with shared resources in face of changes in the output-references. Section 6 presents the conclusions and final remarks.

## 2 Preliminaries

In this section, we present a summary of some basic definitions and results on idempotent semirings and timed event graphs; for an exhaustive discussion, the reader may refer to [3]. We also touch on some topics from residuation theory and control of TEGs (see [4] and [11], respectively).

### 2.1 Idempotent semirings

An idempotent semiring (or dioid) $\mathcal{D}$ is a set endowed with two binary operations, denoted $\oplus$ (sum) and $\otimes$ (product), such that: $\oplus$ is associative, commutative, idempotent (i. e., $(\forall a \in \mathcal{D}) a \oplus a = a$), and has a neutral (zero) element, denoted $\varepsilon$; $\otimes$ is associative, distributes over $\oplus$, and has a neutral (unit) element, denoted $e$; the element $\varepsilon$ is absorbing for $\otimes$ (i. e., $(\forall a \in \mathcal{D}) a \otimes \varepsilon = \varepsilon$). As in conventional algebra, the product symbol $\otimes$ is often omitted. An order relation can be defined over $\mathcal{D}$ by

$$ (\forall a, b \in \mathcal{D}) a \leq b \Leftrightarrow a \oplus b = b. \qquad (1) $$

Note that $\varepsilon$ is the bottom element of $\mathcal{D}$, as $(\forall a \in \mathcal{D}) \varepsilon \leq a$.

An idempotent semiring $\mathcal{D}$ is complete if it is closed for infinite sums and if the product distributes over infinite sums. For a complete idempotent semiring, the top element is defined as $\top = \bigoplus_{x \in \mathcal{D}} x$, and the greatest lower

bound (or infimum) operation, denoted $\wedge$, by

$$ (\forall a, b \in \mathcal{D}) a \wedge b = \bigoplus_{x \leq a, x \leq b} x. $$

$\wedge$ is associative, commutative, and idempotent, and we have $a \oplus b = b \Leftrightarrow a \leq b \Leftrightarrow a \wedge b = a$.

**Example 1.** The set $\overline{\mathbb{Z}}^{\text{def}} = \mathbb{Z} \cup \{-\infty, +\infty\}$, with the minimum operation as $\oplus$ and conventional addition as $\otimes$, forms a complete idempotent semiring called min-plus algebra, denoted $\overline{\mathbb{Z}}_{\min}$, in which $\varepsilon = +\infty$, $e = 0$, and $\top = -\infty$. Note that in $\overline{\mathbb{Z}}_{\min}$ we have $2 \oplus 5 = 2$, so $5 \leq 2$; the order is reversed with respect to the conventional order over $\mathbb{Z}$.

$\diamond$

**Remark 2 ([3]).** The set of $n \times n$-matrices with entries in an idempotent semiring $\mathcal{D}$, endowed with sum and product operations defined by

$$ (A \oplus B)_{ij} = A_{ij} \oplus B_{ij}, $$

$$ (A \otimes B)_{ij} = \bigoplus_{k=1}^{n} (A_{ik} \otimes B_{kj}), $$

for all $i, j \in \{1, \dots, n\}$, forms a complete idempotent semiring, denoted $\mathcal{D}^{n \times n}$. Its unit element (or identity matrix) is the $n \times n$-matrix with entries equal to $e$ on the diagonal and $\varepsilon$ elsewhere; the zero (resp. top) element is the $n \times n$-matrix with all entries equal to $\varepsilon$ (resp. $\top$). The definition of order (1) implies, for any $A, B \in \mathcal{D}^{n \times n}$,

$$ A \leq B \Leftrightarrow (\forall i, j \in \{1, \dots, n\}) A_{ij} \leq B_{ij}. $$

It is possible to deal with nonsquare matrices in this context (including, in particular, row and column vectors) by suitably padding them with $\varepsilon$-rows or columns; this is done only implicitly, as it does not interfere with the relevant parts of the results of operations between matrices.

$\diamond$

A mapping $\Pi: \mathcal{D} \to \mathcal{C}$, with $\mathcal{D}$ and $\mathcal{C}$ two idempotent semirings, is isotone if $(\forall a, b \in \mathcal{D}) a \leq b \Rightarrow \Pi(a) \leq \Pi(b)$.

**Remark 3.** The composition of two isotone mappings is isotone.

$\diamond$

**Remark 4.** Let $\Pi$ be an isotone mapping over a complete idempotent semiring $\mathcal{D}$, and let $\mathcal{Y} = \{x \in \mathcal{D} | \Pi(x) = x\}$ be the set of fixed points of $\Pi$. $\bigwedge_{y \in \mathcal{Y}} y$ (resp. $\bigoplus_{y \in \mathcal{Y}} y$) is the least (resp. greatest) fixed point of $\Pi$.

$\diamond$

Algorithms exist which allow to compute the least and greatest fixed points of certain isotone mappings over complete idempotent semirings. In particular, the algorithm presented in [11] is applicable to the relevant mappings considered in this paper.
In a complete idempotent semiring $\mathcal{D}$, the Kleene star operator on $a \in \mathcal{D}$ is defined as $a^* = \bigoplus_{i \ge 0} a^i$, with $a^0 = e$ and $a^i = a^{i-1} \otimes a$ for $i > 0$.

**Remark 5.** The implicit equation $x = ax \oplus b$ over a complete idempotent semiring $\mathcal{D}$ admits $x = a^*b$ as least solution. This applies, in particular, to the case in which $x, b \in \mathcal{D}^n$ and $a \in \mathcal{D}^{n \times n}$ (see [3] and Remark 2). ◦

## 2.2 Semirings of formal power series

Let $s = \{s(t)\}_{t \in \bar{\mathbb{Z}}}$ be a sequence over $\bar{\mathbb{Z}}_{\min}$. The $\delta$-transform of $s$ is a formal power series in $\delta$ with coefficients in $\bar{\mathbb{Z}}_{\min}$ and exponents in $\bar{\mathbb{Z}}$, defined by

$$s = \bigoplus_{t \in \bar{\mathbb{Z}}} s(t) \delta^t.$$

We denote both the sequence and its $\delta$-transform by the same symbol, as no ambiguity will occur. Since

$$s \otimes \delta = \bigoplus_{t \in \bar{\mathbb{Z}}} s(t) \otimes \delta^{t+1} = \bigoplus_{t \in \bar{\mathbb{Z}}} s(t-1) \otimes \delta^t,$$

multiplication by $\delta$ can be seen as a backward shift operation.

**Definition 6.** The set of formal power series in $\delta$ with coefficients in $\bar{\mathbb{Z}}_{\min}$ and exponents in $\bar{\mathbb{Z}}$, with addition and multiplication defined by

$$s \oplus s' = \bigoplus_{t \in \bar{\mathbb{Z}}} (s(t) \oplus s'(t)) \delta^t, \\ s \otimes s' = \bigoplus_{t \in \bar{\mathbb{Z}}} \left( \bigoplus_{\tau \in \bar{\mathbb{Z}}} (s(\tau) \otimes s'(t-\tau)) \right) \delta^t,$$

is a complete idempotent semiring, denoted $\bar{\mathbb{Z}}_{\min}[\delta]$. Note that the order in $\bar{\mathbb{Z}}_{\min}[\delta]$ is induced by the order in $\bar{\mathbb{Z}}_{\min}$, i. e., $s \le s' \Leftrightarrow (\forall t \in \bar{\mathbb{Z}}) s(t) \le s'(t)$. ◦

In this paper we will use sequences to represent the number of firings of transitions in TEGs, so that each term $s(t)$ refers to the accumulated number of firings of a certain transition up to time $t$. Naturally, this interpretation carries over to the terms of a series $s$ corresponding to the $\delta$-transform of such a sequence. A series thus obtained is clearly nonincreasing (in the order of $\bar{\mathbb{Z}}_{\min}$, which, as pointed out before, is the reverse of the standard order of $\bar{\mathbb{Z}}$), meaning $s(t-1) \ge s(t)$ for all $t$. We will henceforth refer to such series as *counters*.

**Definition 7.** The set of counters (i. e., nonincreasing power series) in $\bar{\mathbb{Z}}_{\min}[\delta]$ is a complete idempotent semiring, named $\bar{\mathbb{Z}}_{\min, \delta}[\delta]$, with zero element $s_{\varepsilon}$ given by $s_{\varepsilon}(t) =$

$\varepsilon$ for all $t$, unit element $s_{\varepsilon}$ given by $s_{\varepsilon}(t) = e$ for $t \le 0$ and $s_{\varepsilon}(t) = \varepsilon$ for $t > 0$, and top element $s_{\top}$ given by $s_{\top}(t) = \top$ for all $t$. We will denote this semiring by $\Sigma$, for brevity. ◦

It is easy to see that $s_{\varepsilon}$, $s_{\varepsilon}$, respectively $s_{\top}$ are indeed the zero, unit, respectively top elements in $\Sigma$: $\forall s \in \Sigma$, $\forall t \in \bar{\mathbb{Z}}$,

$$(s \oplus s_{\varepsilon})(t) = s(t) \oplus s_{\varepsilon}(t) = s(t); \\ (s \otimes s_{\varepsilon})(t) = \bigoplus_{\tau \in \bar{\mathbb{Z}}} s(\tau) \otimes s_{\varepsilon}(t-\tau) \\ = \bigoplus_{\tau \ge t} s(\tau) \\ = s(t) \quad (\text{as s is nonincreasing}); \\ (s \oplus s_{\top})(t) = s(t) \oplus s_{\top}(t) = \top.$$

Counters can be represented compactly by omitting terms $s(t)\delta^t$ whenever $s(t) = s(t+1)$. For example, a counter $s$ with $s(t) = e$ for $t \le 3$, $s(t) = 1$ for $4 \le t \le 7$, $s(t) = 3$ for $8 \le t \le 12$, and $s(t) = 6$ for $t \ge 13$ can be written $s = e\delta^3 \oplus 1\delta^7 \oplus 3\delta^{12} \oplus 6\delta^{+\infty}$.

## 2.3 TEG models in idempotent semirings

A timed Petri net is a tuple $(P, T, A, w, h, v)$, where $P$ is a finite set of places (graphically represented by circles), $T$ a finite set of transitions (represented by bars), $A \subseteq (P \times T) \cup (T \times P)$ a set of arcs connecting places to transitions and transitions to places, $w$ a weight function assigning a positive integer weight to every arc, and $h$ a function assigning a nonnegative holding time to each place. In the following, holding times will be restricted to be integers. Furthermore, the function $v$ assigns to each place a non-negative integer number of tokens residing initially in this place. For any $p \in P$ and $t \in T$, if $(p, t) \in A$, we say that $p$ is an upstream place of $t$, and $t$ is a downstream transition of $p$; analogously, if $(t, p) \in A$, $t$ is said to be an upstream transition of $p$, and $p$ is a downstream place of $t$. The dynamics of a timed Petri net is governed by the following rules: (i) a transition $t$ can fire if all its upstream places $p$ contain at least $w((p, t))$ tokens that have resided there for at least $h(p)$ time units; (ii) if a transition $t$ fires, it removes $w((p, t))$ tokens from each of its upstream places $p$ and deposits $w((t, \tilde{p}))$ tokens in each of its downstream places $\tilde{p}$.

Timed event graphs (TEGs) are timed Petri nets in which each place has exactly one upstream and one downstream transition and all arcs have weight 1. In a TEG, we can distinguish input transitions (those that are not affected by the firing of other transitions), output transitions (those that do not affect the firing of other transitions), and
<figure><img src="image_5.png" /><figcaption>Figure 1: A SISO TEG, with input $u$ and output $y$.</figcaption></figure>

internal transitions (those that are neither input nor output transitions). In this paper, we will limit our discussion to SISO TEGs, i. e., TEGs with only one input and one output transition, which we denote respectively by $u$ and $y$; internal transitions are denoted by $x_i$. An example of a SISO TEG is shown in Fig. 1.

A TEG is said to be operating under the earliest firing rule if every internal and output transition fires as soon as it is enabled.

With each transition $x_i$, we associate a sequence $\{x_i(t)\}_{t \in \mathbb{Z}}$, for simplicity denoted by the same symbol, where $x_i(t)$ represents the accumulated number of firings of $x_i$ up to and including time $t$. Similarly, we associate sequences $\{u(t)\}_{t \in \mathbb{Z}}$ and $\{y(t)\}_{t \in \mathbb{Z}}$ with transitions $u$ and $y$, respectively. Considering the TEG from Fig. 1 operating under the earliest firing rule, in conventional algebra we have

$$x_1(t) = \min(u(t), x_2(t-2) + 2),$$

i. e., the number of firings of transition $x_1$ up to time $t$ is the minimum between the number of firings of transition $u$ up to time $t$ and the number of firings of transition $x_2$ up to time $t-2$ (because the place connecting $x_2$ to $x_1$ has holding time 2) plus 2 (as the place connecting $x_2$ to $x_1$ has initially 2 tokens).

In $\mathbb{Z}_{\min}$, the number of firings of transition $x_1$ can be conveniently rewritten as

$$(\forall t \in \mathbb{Z}) \ x_1(t) = u(t) \oplus 2x_2(t-2),$$

which, through the $\delta$-transform, can be expressed in $\Sigma$ as

$$x_1 = u \oplus 2\delta^2 x_2.$$

We can obtain similar relations for $x_2$ and $y$ and, defining the vector $x = [x_1^{\top} \ x_2^{\top}]$, write

$$x = \begin{bmatrix} \varepsilon & 2\delta^2 \\ e\delta^3 & \varepsilon \end{bmatrix} x \oplus \begin{bmatrix} e\delta^0 \\ \varepsilon \end{bmatrix} u,$$

$$y = [\varepsilon \ e\delta^0]^x.$$

In general, a TEG can be described by implicit equations over $\Sigma$ of the form

$$\begin{aligned} x &= Ax \oplus Bu, \\ y &= Cx. \end{aligned} \qquad (2)$$

From Remark 5, the least solution of (2) is given by

$$y = CA^*Bu, \qquad (3)$$

where $G = CA^*B$ is often called the transfer function of the system. For instance, for the system from Fig. 1 we obtain the (scalar) transfer function $G = e\delta^3(2\delta^5)^*$.

## 2.4 Residuation theory

Residuation theory provides, under certain conditions, greatest (resp. least) solutions to inequalities such as $f(x) \le b$ (resp. $f(x) \ge b$).

**Definition 8.** An isotone mapping $f: \mathcal{D} \to \mathcal{C}$, with $\mathcal{D}$ and $\mathcal{C}$ complete idempotent semirings, is said to be residuated if for all $y \in \mathcal{C}$ there exists a greatest solution to the inequality $f(x) \le y$. This greatest solution is denoted $f^{\#}(y)$, and the mapping $f^{\#}: \mathcal{C} \to \mathcal{D}$, $y \mapsto \bigoplus\{x \in \mathcal{D} | f(x) \le y\}$, is called the residual of $f$.

Mapping $f$ is said to be dually residuated if for all $y \in \mathcal{C}$ there exists a least solution to the inequality $f(x) \ge y$. This least solution is denoted $f^{\flat}(y)$, and the mapping $f^{\flat}: \mathcal{C} \to \mathcal{D}$, $y \mapsto \bigwedge\{x \in \mathcal{D} | f(x) \ge y\}$, is called the dual residual of $f$. ◇

Note that, if equality $f(x) = y$ is solvable, $f^{\#}(y)$ and $f^{\flat}(y)$ yield its greatest and least solutions, respectively.

**Theorem 9 ([4]).** Mapping $f$ as in Def. 8 is residuated if and only if there exists a unique isotone mapping $f^{\#}: \mathcal{C} \to \mathcal{D}$ such that $f \circ f^{\#} \le \mathrm{Id}_{\mathcal{C}}$ and $f^{\#} \circ f \ge \mathrm{Id}_{\mathcal{D}}$, where $\mathrm{Id}_{\mathcal{C}}$ and $\mathrm{Id}_{\mathcal{D}}$ are the identity mappings on $\mathcal{C}$ and $\mathcal{D}$, respectively. ◇

**Remark 10.** For $a \in \mathcal{D}$, mapping $L_a: \mathcal{D} \to \mathcal{D}$, $x \mapsto a \otimes x$, is residuated; its residual is denoted by $L_a^{\#}(y) = a \flat y$ ("left division by $a$"). More generally, for $A \in \mathcal{D}^{n \times m}$, mapping $L_A: \mathcal{D}^{m \times p} \to \mathcal{D}^{n \times p}$, $X \mapsto A \otimes X$, is residuated; $L_A^{\#}(Y) = A \flat Y \in \mathcal{D}^{m \times p}$ can be computed as follows: for all $1 \le i \le m$ and $1 \le j \le p$,

$$(A \flat Y)_{ij} = \bigwedge_{k=1}^{n} A_{ki} \flat Y_{kj}$$

(see [3] and Remark 2). ◇

**Theorem 11 ([4]).** Mapping $f$ as in Def. 8 is dually residuated if and only if $f(\top) = \top$ and $(\forall A \subseteq \mathcal{D}) f(\bigwedge_{x \in A} x) = \bigwedge_{x \in A} f(x)$. ◇

<footnote n="1">1 Note that, for any idempotent semiring $\mathcal{X}$, the order $\leq$ on $\mathcal{X}$ induces an order, for simplicity also denoted $\leq$, on the set of mappings over $\mathcal{X}$: for any such mappings $\Theta_1, \Theta_2$, one has $\Theta_1 \leq \Theta_2 \iff (\forall x \in \mathcal{X}) \Theta_1(x) \leq \Theta_2(x)$.</footnote>
## 2.5 Optimal control of TEGs

Assume that a TEG to be controlled is modeled by equations (2) and that an output-reference $z \in \Sigma$ is given. Under the just-in-time paradigm, we aim at firing the input transition $u$ the least possible number of times while guaranteeing that the output transition $y$ fires, by each time instant, at least as many times as specified by $z$. In other words, we seek the greatest $u$ (in the order of $\Sigma$) such that $y = G \otimes u \le z$. Based on (3) and Remark 10, the solution is directly obtained by

$$u_{\text{opt}} = G \setminus z. \quad (4)$$

**Example 12.** For the TEG from Fig. 1, suppose it is required that transition $y$ fires once at time $t = 43$, twice at $t = 47$, and three times at $t = 55$, meaning the accumulated number of firings of $y$ should be $e (= 0)$ for $t \le 42$, $1$ for $43 \le t \le 46$, $3$ for $47 \le t \le 54$, and $6$ for $t \ge 55$. This is represented by the output-reference $z = e\delta^{42} \oplus 1\delta^{46} \oplus 3\delta^{54} \oplus 6\delta^{+\infty}$. Applying (4), we get $u_{\text{opt}} = e\delta^{38} \oplus 1\delta^{41} \oplus 2\delta^{43} \oplus 3\delta^{46} \oplus 4\delta^{51} \oplus 6\delta^{+\infty}$, and the corresponding optimal output is $y_{\text{opt}} = G \otimes u_{\text{opt}} = e\delta^{41} \oplus 1\delta^{44} \oplus 2\delta^{46} \oplus 3\delta^{49} \oplus 4\delta^{54} \oplus 6\delta^{+\infty}$. One can verify that $y_{\text{opt}} \le z$. These computations can be performed with the aid of the C++ toolbox introduced in [9]. We interpret the place with holding time 3 between $x_1$ and $x_2$, initially empty, as the operation of the system, and the bottom place with holding time 2 between $x_2$ and $x_1$, with two initial tokens, as a double-capacity resource. Under this interpretation, the firings of transitions $x_1$ and $x_2$ represent resource-allocation and resource-release events, respectively. This paves the way for the examples of Sections 4 and 5, where the resource will be shared with other (sub)systems. The optimal schedule obtained above can be displayed in a chart as shown in Fig. 2, where each row corresponds to one instance of the resource. ◇

# 3 Optimal control of TEGs with output-reference update

The material of this section is a dual version, adapted to the point of view of counters, of the results from [12].

In practice, it may be necessary to update the reference for the output of a system during run-time, for instance when customer demand is increased and a new production objective must be taken into account. For a system like the one from Example 12, let reference $z$ be updated to a new one, $z'$, at time $T$. The problem at hand is to find the input $u'_{\text{opt}}$ which optimally tracks $z'$ without, however,

<figure><img src="image_6.png" /><figcaption>**Figure 2:** Optimal schedule obtained in Example 12; the gray bars represent the operation of the system, and the dashed bars are the delays imposed by the resource.</figcaption></figure>

changing the inputs given up to time $T$. Define the mapping $r_T: \Sigma \to \Sigma$,

$$[r_T(u)](t) = \begin{cases} u(t), & \text{if } t \le T; \\ \varepsilon, & \text{if } t > T. \end{cases} \quad (5)$$

Our objective can then be restated as follows: find the greatest element $u'_{\text{opt}}$ of the set

$$\mathcal{F} = \{u \in \Sigma | G \otimes u \le z' \text{ and } r_T(u) = r_T(u_{\text{opt}})\},$$

where $u_{\text{opt}}$ is the optimal input with respect to reference $z$, computed as in (4). The following theorem provides, given that certain conditions are met, a way to compute this greatest element.

**Theorem 13** ([12]). Let $\mathcal{D}$ and $\mathcal{C}$ be complete idempotent semirings, $f_1, f_2: \mathcal{D} \to \mathcal{C}$ residuated mappings, and $c_1, c_2 \in \mathcal{C}$. If the set

$$S = \{x \in \mathcal{D} | f_1(x) \le c_1 \text{ and } f_2(x) = c_2\}$$

is nonempty, we have $\bigoplus_{x \in S} x = f_1^{\#}(c_1) \wedge f_2^{\#}(c_2)$. ◇

An obvious correspondence between $\mathcal{F}$ and $\mathcal{S}$ can be established by taking $\mathcal{D}$ and $\mathcal{C}$ both as $\Sigma$, $f_1$ as $L_G$ (which is well known to be residuated — see Remark 10), $c_1$ as $z'$, $f_2$ as $r_T$, and $c_2$ as $r_T(u_{\text{opt}})$.

**Remark 14.** Mapping $r_T$ as defined in (5) is residuated, with

$$[r_T^{\#}(u)](t) = \begin{cases} u(t), & \text{if } t \le T; \\ u(T), & \text{if } t > T. \end{cases}$$

In fact, $r_T^{\#}$ is clearly isotone and we have $r_T \circ r_T^{\#} = r_T \le \text{Id}_{\Sigma}$ and $r_T^{\#} \circ r_T = r_T^{\#} \ge \text{Id}_{\Sigma}$, so the conditions from Theorem 9 are fulfilled. ◇

Hence, as long as set $\mathcal{F}$ is nonempty, Theorem 13 provides the desired solution

$$u'_{\text{opt}} = G \setminus z' \wedge r_T^{\#}(u_{\text{opt}}). \quad (6)$$

In order to check for nonemptiness of $\mathcal{F}$, let us consider the set

$$\tilde{\mathcal{F}} = \{u \in \Sigma | r_T(u) = r_T(u_{\text{opt}})\},$$
<figure><img src="image_7.png" /><figcaption>**Figure 3:** Updated optimal schedule obtained in Example 15; the gray bars represent the operation of the system, whereas the dashed bars are the delays imposed by the resource.</figcaption></figure>

<figure><img src="image_8.png" /><figcaption>**Figure 4:** Updated optimal schedule obtained in Example 17; the gray bars represent the operation of the system, whereas the dashed bars are the delays imposed by the resource.</figcaption></figure>

i. e., the set of counters that up to and including time $T$ are identical to $u_{opt}$. Consider now

$$ \underline{u} \stackrel{\text{def}}{=} \bigwedge_{u \in \mathcal{F}} u = r_T(u_{opt}). $$

Since $r_T \circ r_T = r_T$ and therefore $r_T(\underline{u}) = r_T(r_T(u_{opt})) = r_T(u_{opt})$, $\underline{u} \in \mathcal{F}$. Isotony of $L_G$ thus implies

$$ \mathcal{F} \neq \emptyset \Leftrightarrow G \otimes \underline{u} \leq z'. \quad (7) $$

**Example 15.** For the system from Example 12 (Fig. 1) operating according to the optimal input obtained for output-reference $z$, suppose that at time $T = 40$ a new demand is received: three firings of $y$ are now required at $t = 54$ (instead of at $t = 55$). This translates to $z' = e\delta^{42} \oplus 1\delta^{46} \oplus 3\delta^{53} \oplus 6\delta^{+\infty}$. In order to determine whether $\mathcal{F} \neq \emptyset$, following (7) we check if $G \otimes \underline{u} \leq z'$. We have $\underline{u} = r_T(u_{opt}) = e\delta^{38} \oplus 1\delta^{40} \oplus e\delta^{+\infty}$, so $G \otimes \underline{u} = e\delta^{41} \oplus 1\delta^{43} \oplus 2\delta^{46} \oplus 3\delta^{48} \oplus 4\delta^{51} \oplus 5\delta^{53} \oplus 6\delta^{56} \oplus 7\delta^{58} \oplus \dots = (e\delta^{41} \oplus 1\delta^{43})(2\delta^5)^* \leq z'$, implying $\mathcal{F} \neq \emptyset$. From Theorem 13 (and recalling that $r_T^\# \circ r_T = r_T^\#$), we then have $u'_{opt} = G \setminus z' \wedge r_T^\#(u_{opt}) = e\delta^{38} \oplus 1\delta^{40} \oplus 2\delta^{43} \oplus 3\delta^{45} \oplus 4\delta^{50} \oplus 6\delta^{+\infty}$, and hence $y'_{opt} = e\delta^{41} \oplus 1\delta^{43} \oplus 2\delta^{46} \oplus 3\delta^{48} \oplus 4\delta^{53} \oplus 6\delta^{+\infty}$. The updated optimal schedule is shown in Fig. 3, to be interpreted as explained in Example 12. ◦

In case $G \otimes \underline{u} \neq z'$ (and hence $\mathcal{F} = \emptyset$), this means the past inputs make it impossible for the system to respect $z'$. Intuitively, having implemented a just-in-time policy $u_{opt}$ for a reference $z$ up to time $T$ may make it impossible to satisfy a more demanding new reference $z'$. Since the condition $r_T(u) = r_T(u_{opt})$ cannot be relaxed, in order to have a solution we must then increase $z'$; more precisely, we wish to find the least counter $z'' \geq z'$ such that

$$ \mathcal{F}_{z''} = \{u \in \Sigma \mid G \otimes u \leq z'' \text{ and } r_T(u) = r_T(u_{opt})\} $$

is not empty. The following result provides the answer.

**Proposition 16.** The least counter $z'' \geq z'$ such that $\mathcal{F}_{z''} \neq \emptyset$ is $z'' = z' \oplus (G \otimes \underline{u})$.

*Proof.* Since $G \otimes \underline{u} \leq z' \oplus (G \otimes \underline{u}) = z''$, we have $\underline{u} \in \mathcal{F}_{z''}$, therefore $\mathcal{F}_{z''} \neq \emptyset$. Take now an arbitrary $\tilde{z}'' \geq z'$ such that $\mathcal{F}_{\tilde{z}''} \neq \emptyset$, and take any $v \in \mathcal{F}_{\tilde{z}''}$. Clearly $v \in \mathcal{F}$ and hence

$\underline{u} \leq v$; as $L_G$ is isotone, we have $G \otimes \underline{u} \leq G \otimes v \leq \tilde{z}''$, implying $z'' = z' \oplus (G \otimes \underline{u}) \leq z' \oplus \tilde{z}'' = \tilde{z}''$. □

A correspondence between $\mathcal{F}_{z''}$ and $\mathcal{S}$ can be established analogously to that between $\mathcal{F}$ and $\mathcal{S}$, only taking $c_1$ as $z''$ (instead of $z'$). Applying Theorem 13 and recalling that $r_T^\# \circ r_T = r_T^\#$, we obtain

$$ u'_{\text{opt}} = G \setminus (z' \oplus (G \otimes \underline{u})) \wedge r_T^\#(u_{\text{opt}}). \quad (8) $$

Note that in case $\mathcal{F} \neq \emptyset$ we have $z'' = z' \oplus (G \otimes \underline{u}) = z'$ and therefore recover solution (6).

**Example 17.** Consider, once more, the system from Example 12 (Fig. 1) operating according to the optimal input obtained for output-reference $z$, and suppose the same new output-reference $z'$ as in Example 15 is received, only now at time $T = 42$ instead of at time 40. We again use (7) to check whether set $\mathcal{F}$ is empty; in this case, we obtain $\underline{u} = e\delta^{38} \oplus 1\delta^{41} \oplus 2\delta^{42} \oplus e\delta^{+\infty}$ and hence $G \otimes \underline{u} = e\delta^{41} \oplus 1\delta^{44} \oplus 2\delta^{46} \oplus 3\delta^{49} \oplus 4\delta^{51} \oplus 5\delta^{54} \oplus 6\delta^{56} \oplus 7\delta^{59} \oplus \dots = (e\delta^{41} \oplus 1\delta^{44})(2\delta^5)^* \neq z'$, implying $\mathcal{F} = \emptyset$. So, we seek the least $z'' \geq z'$ such that $\mathcal{F}_{z''} \neq \emptyset$; according to Proposition 16, we get $z'' = z' \oplus (G \otimes \underline{u}) = e\delta^{42} \oplus 1\delta^{46} \oplus 3\delta^{53} \oplus 5\delta^{54} \oplus 6\delta^{+\infty}$, which is the reference we shall effectively track. Then, from (8) we have $u'_{opt} = e\delta^{38} \oplus 1\delta^{41} \oplus 2\delta^{43} \oplus 3\delta^{46} \oplus 4\delta^{50} \oplus 5\delta^{51} \oplus 6\delta^{+\infty}$, and hence $y'_{opt} = e\delta^{41} \oplus 1\delta^{44} \oplus 2\delta^{46} \oplus 3\delta^{49} \oplus 4\delta^{53} \oplus 5\delta^{54} \oplus 6\delta^{+\infty}$. The updated optimal schedule is shown in Fig. 4, to be interpreted as explained in Example 12. ◦

# 4 Modeling and optimal control of TEGs with resource sharing

We now turn our attention to systems in which a number of TEGs share one or multiple resources. We first focus on the simple case of a single shared resource (Sections 4.1 and 4.2); the discussion is based on [13], where the authors also present the more general case of two shared resources. Here, we take it one step further and explicitly generalize the approach to the case of arbitrarily many shared resources (Section 4.3).
<figure><img src="image_9.png" /><figcaption>Figure 5: A number of TEGs with a single shared resource.</figcaption></figure>

## 4.1 Modeling of TEGs with one shared resource

Consider a system consisting of TEGs $S^1, \dots, S^K$ sharing a resource (with arbitrary capacity), as illustrated in Fig. 5. $H^k$ represents the internal dynamics of $S^k$. $\beta$ may, in general, be a TEG (or, in simple cases, just a single place) describing the capacity of the resource as well as the minimal delay between release and allocation events. Clearly, the overall system is no longer a TEG, as there are places with several upstream and/or several downstream transitions. For simplicity, let us assume that input transitions $(u^k)$ are connected to resource-allocation transitions $(x_A^k)$ via a single place with zero delay and no initial tokens, the same being true for the connection between resource-release transitions $(x_R^k)$ and output transitions $(y^k)$. These assumptions will be dropped in Section 4.3.

It is not possible to model systems exhibiting resource-sharing phenomena by linear equations such as (2). Considering a system like the one from Fig. 5, in order to express the relationship among counters $x_A^k$ and $x_R^k$, $k \in \{1, \dots, K\}$, the *Hadamard product* of series is introduced ([10]).

**Definition 18.** The Hadamard product of $s_1, s_2 \in \Sigma$, written $s_1 \odot s_2$, is the counter defined as follows:

$$ (\forall t \in \overline{\mathbb{Z}}) (s_1 \odot s_2)(t) = s_1(t) \otimes s_2(t). $$

This operation is commutative, distributes over $\oplus$ and $\wedge$, has neutral element $e\delta^{+\infty}$, and $s_\epsilon$ is absorbing for it (i. e., $(\forall s \in \Sigma) s \odot s_\epsilon = s_\epsilon$).

Consider a join structure (i. e., a place with two or more incoming transitions) as shown in Fig. 6. At any time instant $t$, the accumulated number of firings of $\gamma$, in conventional algebra, cannot exceed that of $\lambda_1$ and $\lambda_2$ combined, which translates to $\lambda_1 \odot \lambda_2 \le \gamma$. Similarly, for a fork

<figure><img src="image_10.png" /><figcaption>Figure 6: A join and a fork structure.</figcaption></figure>

structure (i. e., a place with two or more outgoing transitions) such as the one shown in Fig. 6, the accumulated number of firings of $\gamma_1$ and $\gamma_2$ combined — again, in conventional algebra — can never exceed that of $\lambda$, meaning $\lambda \le \gamma_1 \odot \gamma_2$.

Generalizing these ideas allows us to write, for the system from Fig. 5,

$$ x_R^1 \odot \dots \odot x_R^K \le \alpha_1 \quad \text{and} \quad \alpha_2 \le x_A^1 \odot \dots \odot x_A^K $$

which, combined with $\beta \otimes \alpha_1 \le \alpha_2$, leads to

$$ \beta \otimes \left( \bigodot_{k=1}^{K} x_R^k \right) \le \bigodot_{k=1}^{K} x_A^k. \qquad (9) $$

## 4.2 Optimal control of TEGs with one shared resource

For a system like the one from Fig. 5, competition for the resource is, in general, going to make it impossible for all subsystems to concurrently follow a just-in-time schedule with respect to their individual output-references. One way to settle the dispute is introducing a priority policy among the subsystems. We henceforth assume, without loss of generality, that subsystem $S^k$ has higher priority than $S^{k+1}$, for all $k \in \{1, \dots, K-1\}$. The priority policy is based on a simple rule: for each $k \in \{2, \dots, K\}$ and for all $j \in \{1, \dots, k-1\}$, $S^k$ cannot interfere with the performance of $S^j$.

Let the input-output behavior of each $S^k$, ignoring all other subsystems, be described by $y^k = G^k \otimes u^k$ — which, according to the assumptions made above, is equivalent to $x_R^k = G^k \otimes x_A^k$ — and assume that corresponding references $z^k$ are given. The subsystem with highest priority, $S^1$, is free to use the resource at will; therefore, we can effectively neglect all other subsystems and simply compute its optimal input by $u_{\text{opt}}^1 = x_{A_{\text{opt}}}^1 = G^1 \odot z^1$ (cf. Section 2.5). For $S^2$, we must compute the optimal input under the restriction that the optimal behavior of $S^1$ is unchanged; based on (9), this means we must respect

$$ \beta \otimes (x_{R_{\text{opt}}}^1 \odot x_R^2) \le x_{A_{\text{opt}}}^1 \odot x_A^2. \qquad (10) $$
<figure><img src="image_11.png" /><figcaption>Figure 7: Optimal schedules obtained in Example 20; the gray, black, and crosshatched bars represent the operation of $S^1$, $S^2$, and $S^3$, respectively, whereas the dashed bars are the delays imposed by the resource.</figcaption></figure>

In fact, we want to determine the greatest $x_A^2$ — and thus also the corresponding $u^2$ — satisfying both $G^2 \otimes u^2 \le z^2$ and (10); seeing that (10) implies

$$x_{R_{\text{opt}}}^1 \odot x_R^2 \le \beta \psi (x_{A_{\text{opt}}}^1 \odot x_A^2), \quad (11)$$

the following result comes in handy.

**Proposition 19 ([10]).** For any $a \in \Sigma$, the mapping $\Pi_a : \Sigma \to \Sigma$, $x \mapsto a \odot x$, is residuated. For any $b \in \Sigma$, $\Pi_a^\#(b)$, denoted $b \odot^\# a$, is the greatest $x \in \Sigma$ such that $a \odot x \le b$. ◦

From Proposition 19, inequality (11) leads to

$$x_R^2 \le (\beta \psi (x_{A_{\text{opt}}}^1 \odot x_A^2)) \odot^\# x_{R_{\text{opt}}}^1; \quad (12)$$

writing $x_R^2 = G^2 \otimes x_A^2$ and combining (12) with $G^2 \otimes x_A^2 \le z^2$ yields

$$G^2 \otimes x_A^2 \le [(\beta \psi (x_{A_{\text{opt}}}^1 \odot x_A^2)) \odot^\# x_{R_{\text{opt}}}^1] \wedge z^2,$$

which, in turn, implies

$$x_A^2 \le G^2 \psi [(\beta \psi (x_{A_{\text{opt}}}^1 \odot x_A^2)) \odot^\# x_{R_{\text{opt}}}^1] \wedge G^2 \psi z^2. \quad (13)$$

Since for any $s_1, s_2 \in \Sigma$ it holds that $s_1 \le s_2 \Leftrightarrow s_1 = s_1 \wedge s_2$, one can see that (13) is equivalent to

$$x_A^2 = G^2 \psi [(\beta \psi (x_{A_{\text{opt}}}^1 \odot x_A^2)) \odot^\# x_{R_{\text{opt}}}^1] \wedge G^2 \psi z^2 \wedge x_A^2. \quad (14)$$

The greatest $x_A^2$ satisfying (14), $x_{A_{\text{opt}}}^2$, is the greatest fixed point (provided it exists) of the mapping $\Phi^2 : \Sigma \to \Sigma$,

$$\Phi^2(x_A^2) = G^2 \psi [(\beta \psi (x_{A_{\text{opt}}}^1 \odot x_A^2)) \odot^\# x_{R_{\text{opt}}}^1] \wedge G^2 \psi z^2 \wedge x_A^2. \quad (15)$$

Notice that $\Phi^2$ consists in a succession of order-preserving operations (Hadamard product $\odot$ and its residual $\odot^\#$, left-division $\psi$, and infimum $\wedge$), which, in turn, can be seen as the composition of corresponding isotone mappings (for instance, following the notation of Proposition 19, $s_1 \oplus s_2$ corresponds to $\Pi_{s_1}(s_2)$, and similarly for the other operations). Therefore, according to Remark 3 $\Phi^2$ is also isotope; Remark 4 then ensures the existence of its greatest fixed point, which yields the desired optimal solution $x_{A_{\text{opt}}}^2 (= u_{\text{opt}}^2)$.

<figure><img src="image_12.png" /><figcaption>Figure 8: Three TEGs sharing a resource with capacity 2.</figcaption></figure>

Using the same procedure, we obtain, for each $k$,

$$x_A^k \le G^k \psi [(\beta \psi ((\bigcirc_{i=1}^{k-1} x_{A_{\text{opt}}}^i) \odot x_A^k)) \odot^\# (\bigcirc_{i=1}^{k-1} x_{R_{\text{opt}}}^i)] \wedge G^k \psi z^k$$

and, defining a mapping $\Phi^k$ by analogy with (15), its greatest fixed point provides $x_{A_{\text{opt}}}^k$ and, therefore, also $u_{\text{opt}}^k$.

**Example 20.** Consider the system from Fig. 8, where subsystems $S^1$, $S^2$, and $S^3$ share a resource with capacity 2. $S^1$, including the resource and ignoring $S^2$ and $S^3$, is the system from Example 12, whose transfer function is $G^1 = e\delta^3(2\delta^5)^*$ (cf. Section 2.3). For $S^2$ and $S^3$, we obtain $G^2 = e\delta^5(2\delta^7)^*$ and $G^3 = e\delta^2(2\delta^4)^*$, respectively. In this example, $\beta = 2\delta^2$. The references $z^1 = e\delta^{42} \oplus 1\delta^{46} \oplus 3\delta^{55} \oplus 6\delta^{+\infty}$, $z^2 = e\delta^{39} \oplus 1\delta^{50} \oplus 2\delta^{54} \oplus 3\delta^{+\infty}$, and $z^3 = e\delta^{52} \oplus 3\delta^{+\infty}$ are given. As $S^1$ has the highest priority, we can simply compute $u_{\text{opt}}^1 = x_{A_{\text{opt}}}^1 = G^1 \psi z^1 = e\delta^{38} \oplus 1\delta^{42} \oplus 2\delta^{43} \oplus 3\delta^{47} \oplus 4\delta^{52} \oplus 6\delta^{+\infty}$ and $y_{\text{opt}}^1 = G^1 \otimes u_{\text{opt}}^1 = e\delta^{41} \oplus 1\delta^{45} \oplus 2\delta^{46} \oplus 3\delta^{50} \oplus 4\delta^{55} \oplus 6\delta^{+\infty}$. Next, we determine $x_{A_{\text{opt}}}^2$ by following the procedure described in this section. Computing the greatest fixed point of $\Phi^2$ as in (15), we get $x_{A_{\text{opt}}}^2 = e\delta^{28} \oplus 1\delta^{31} \oplus 2\delta^{35} \oplus 3\delta^{+\infty} (= u_{\text{opt}}^2)$ and $x_{R_{\text{opt}}}^2 = e\delta^{33} \oplus 1\delta^{36} \oplus 2\delta^{40} \oplus 3\delta^{+\infty} (= y_{\text{opt}}^2)$. Finally, the greatest fixed point of

$$\Phi^3(x_A^3) = G^3 \psi [(\beta \psi (x_{A_{\text{opt}}}^1 \odot x_{A_{\text{opt}}}^2 \odot x_A^3)) \odot^\# (x_{R_{\text{opt}}}^1 \odot x_{R_{\text{opt}}}^2)] \wedge G^3 \psi z^3 \wedge x_A^3$$

yields $x_{A_{\text{opt}}}^3 = e\delta^{24} \oplus 1\delta^{27} \oplus 2\delta^{48} \oplus 3\delta^{+\infty} (= u_{\text{opt}}^3)$, and so $x_{R_{\text{opt}}}^3 = e\delta^{26} \oplus 1\delta^{29} \oplus 2\delta^{50} \oplus 3\delta^{+\infty} (= y_{\text{opt}}^3)$. These optimal schedules are shown in Fig. 7. Because the availability of
<figure><img src="image_13.png" /><figcaption>Figure 9: A number of TEGs with multiple shared resources.</figcaption></figure>

the resource for $S^2$ is subject to the operation of $S^1$, the fir-
ings of $y^2$ have to be considerably earlier than required by
$z^2$; this is, however, the latest they can be so as to respect
$z^2$ without interfering with $S^1$. A similar effect can be ob-
served in $y^3$ due to the limitations imposed by the opera-
tions of $S^1$ and $S^2$.
$\diamond$

4.3 Modeling and optimal control of TEGs
with multiple shared resources

Consider, as before, a system comprising *K* TEGs $S^1, \dots, S^K$, but now suppose they share *L* resources, as shown in Fig. 9. Similarly to Section 4.1, each $\beta^\ell$, $\ell \in \{1, \dots, L\}$, is a TEG (or possibly just a place) describing the capacity as well as the minimal delay between release and allocation events of resource $\ell$. We denote by $x_A^{k\ell}$ (resp. $x_R^{k\ell}$) the transition — and associated counter — representing the allocation (resp. release) of resource $\ell$ by subsystem $S^k$. Accordingly, $H^{k\ell}$ denotes the internal dynamics of $S^k$ between $x_A^{k\ell}$ and $x_R^{k\ell}$. As opposed to Section 4.1, here we consider that there may be also some dynamics between input transitions ($u^k$) and resource-allocation transitions for the first resource ($x_A^{k1}$), modeled by TEGs (or, again, simply single places) called $P^{k1}$, as well as between resource-release transitions for the last resource ($x_R^{kL}$) and output transitions ($y^k$), called $P^{k(L+1)}$. The TEG (or single place) describing the dynamics between the release of resource $\ell-1$ and the allocation of resource $\ell$ by $S^k$ (i. e., between $x_R^{k(\ell-1)}$ and $x_A^{k\ell}$) is denoted $P^{k\ell}$.

Through the same reasoning as applied in Section 4.1, it is straightforward to conclude that, for each $\ell \in \{1, \dots, L\}$, the relationship among counters $x_A^{k\ell}$ and $x_R^{k\ell}$ must respect

$$
\beta^{\ell} \otimes (\bigcirc_{k=1}^{K} x_{R}^{k\ell}) \leq \bigcirc_{k=1}^{K} x_{A}^{k\ell}. \qquad (16)
$$

The optimal (just-in-time) schedule for the usage of the re-
sources is sought under the same priority policy as in Sec-

tion 4.2. Let the input-output behavior of each $S^k$, consid-
ering the resources and ignoring all other subsystems, be
described as usual by $y^k = G^k \otimes u^k$, and let us again as-
sume corresponding references $z^k$ to be given. For $S^1$, we
can simply compute the optimal input by $u_{\text{opt}}^1 = G^1 \oslash z^1$.
Based on $u_{\text{opt}}^1$, we can obtain the optimal firing sched-
ules for the remaining transitions of $S^1$. For instance, we
have $x_{A_{\text{opt}}}^{11} = P^{11} \otimes u_{\text{opt}}^1$ and $x_{R_{\text{opt}}}^{11} = H^{11} \otimes x_{A_{\text{opt}}}^{11}$. In general,
for each $\ell \in \{2, \dots, L\}$ we can then successively compute
$x_{A_{\text{opt}}}^{1\ell} = P^{1\ell} \otimes x_{R_{\text{opt}}}^{1(\ell-1)}$ and $x_{R_{\text{opt}}}^{1\ell} = H^{1\ell} \otimes x_{A_{\text{opt}}}^{1\ell}$.

In order to determine the optimal input $u_{\text{opt}}^2$ for $S^2$ — i. e., the greatest $u^2$ such that $G^2 \otimes u^2 \le z^2$ — while guaranteeing no interference with the optimal behavior of $S^1$, based on (16) we must have, for each $\ell \in \{1, \dots, L\}$,

$$
\beta^{\ell} \otimes (x_{R_{\text{opt}}}^{1\ell} \odot x_{R}^{2\ell}) \leq x_{A_{\text{opt}}}^{1\ell} \odot x_{A}^{2\ell}. \quad (17)
$$

Notice that, for a just-in-time input $u^2$ computed so that
(17) holds for $\ell = 1$, it follows that $x_A^{2\ell} = P^{2\ell} \otimes u^2$, and hence
$x_R^{2\ell} = H^{2\ell} \otimes x_A^{2\ell} = H^{2\ell} \otimes P^{2\ell} \otimes u^2$. In fact, the optimal input we
seek is such that (17) holds for every $\ell$ and, furthermore,
such that a just-in-time behavior is enforced throughout
the system, implying $x_A^{2\ell} = P^{2\ell} \otimes x_R^{2(\ell-1)}$ for all $\ell \in \{2, \dots, L\}$.
This means we can express any $x_A^{2\ell}$ in terms of $u^2$; defining
the terms

$$
\mathcal{P}^{2\ell} = \begin{cases} P^{21}, & \text{if } \ell = 1, \\ P^{2\ell} \otimes H^{2(\ell-1)} \otimes \mathcal{P}^{2(\ell-1)}, & \text{if } 2 \le \ell \le L, \end{cases}
$$

we have $x_A^{2\ell} = \mathcal{P}^{2\ell} \otimes u^2$, and hence $x_R^{2\ell} = H^{2\ell} \otimes x_A^{2\ell} = H^{2\ell} \otimes \mathcal{P}^{2\ell} \otimes u^2$. Then, we can rewrite (17) as

$$
\beta^{\ell} \otimes (x_{R_{\text{opt}}}^{1\ell} \odot (H^{2\ell} \otimes \mathcal{P}^{2\ell} \otimes u^2)) \leq x_{A_{\text{opt}}}^{1\ell} \odot (\mathcal{P}^{2\ell} \otimes u^2),
$$

which, proceeding similarly to Section 4.2, leads to

$$
u^2 \leq (H^{2\ell} \otimes \mathcal{P}^{2\ell}) \oslash [(\beta^\ell \oslash (x_{A_{\text{opt}}}^{1\ell} \odot (\mathcal{P}^{2\ell} \otimes u^2))) \circ^\sharp x_{R_{\text{opt}}}^{1\ell}].
$$

Define, for each $\ell \in \{1, \dots, L\}$, the mapping $\Phi^{2\ell} : \Sigma \rightarrow \Sigma$,

$$
\Phi^{2\ell}(u^2) = (H^{2\ell} \otimes \mathcal{P}^{2\ell}) \oslash [(\beta^\ell \oslash (x_{A_{\text{opt}}}^{1\ell} \odot (\mathcal{P}^{2\ell} \otimes u^2))) \circ^\sharp x_{R_{\text{opt}}}^{1\ell}]. \quad (18)
$$
We seek the greatest $u^2$ such that $u^2 \le G^2 \mathfrak{V} z^2$ and $(\forall \ell \in \{1, \dots, L\}) \ u^2 \le \Phi^{2\ell}(u^2)$. This amounts to looking for the greatest fixed point of the (isotone) mapping $\bar{\Phi}^2: \Sigma \to \Sigma$,

$$ \bar{\Phi}^2(u^2) = u^2 \wedge G^2 \mathfrak{V} z^2 \wedge \bigwedge_{\ell=1}^{L} \Phi^{2\ell}(u^2). $$

The same arguments presented above can be applied to determine $u_{\text{opt}}^k$ for an arbitrary $k \in \{1, \dots, K\}$. Defining

$$ P^{k\ell} = \begin{cases} P^{k1}, & \text{if } \ell = 1, \\ P^{k\ell} \otimes H^{k(\ell-1)} \otimes P^{k(\ell-1)}, & \text{if } 2 \le \ell \le L, \end{cases} \quad (19) $$

and expressing each $x_A^{k\ell}$ and $x_R^{k\ell}$ in terms of $u^k$, from (16) we obtain, for each $\ell \in \{1, \dots, L\}$,

$$ \beta^{\ell} \otimes \left( \left( \bigotimes_{i=1}^{k-1} x_{R_{\text{opt}}}^{i\ell} \right) \circ (H^{k\ell} \otimes P^{k\ell} \otimes u^k) \right) \le \left( \bigotimes_{i=1}^{k-1} x_{A_{\text{opt}}}^{i\ell} \right) \circ (P^{k\ell} \otimes u^k). $$

Then, proceeding as before and defining the mapping $\Phi^{k\ell}: \Sigma \to \Sigma$,

$$ \Phi^{k\ell}(u^k) = (H^{k\ell} \otimes P^{k\ell}) \mathfrak{V} \left[ \left( \beta^{\ell} \mathfrak{V} \left( \left( \bigotimes_{i=1}^{k-1} x_{A_{\text{opt}}}^{i\ell} \right) \circ (P^{k\ell} \otimes u^k) \right) \right) \circ^{\sharp} \left( \bigotimes_{i=1}^{k-1} x_{R_{\text{opt}}}^{i\ell} \right) \right] $$

for each $\ell \in \{1, \dots, L\}$, the greatest $u^k$ such that $u^k \le G^k \mathfrak{V} z^k$ and $u^k \le \Phi^{k\ell}(u^k)$ for all $\ell \in \{1, \dots, L\}$ is given by the greatest fixed point of $\bar{\Phi}^k: \Sigma \to \Sigma$,

$$ \bar{\Phi}^k(u^k) = u^k \wedge G^k \mathfrak{V} z^k \wedge \bigwedge_{\ell=1}^{L} \Phi^{k\ell}(u^k). $$

## 4.4 Supplementary remarks

**Proposition 21 (Adapted from [10]).** Let $\tilde{\Sigma} = \{s \in \Sigma | (\forall t \in \bar{\mathbb{Z}}) s(t) \notin \{\varepsilon, \tau\}\}$. For any $a \in \bar{\Sigma}$, the mapping $\Pi_a: \Sigma \to \Sigma$, $x \mapsto a \odot x$, is dually residuated. For any $b \in \Sigma$, $\Pi_a^b(b)$, denoted $b \odot^b a$, is the least $x \in \Sigma$ such that $a \odot x \ge b$.

*Proof.* For an arbitrary $a \in \bar{\Sigma}$, we have $(\forall t \in \bar{\mathbb{Z}}) a(t) \otimes \tau = \tau$, therefore $\Pi_a(s_\tau) = a \odot s_\tau = s_\tau$. Moreover, since $\odot$ distributes over $\wedge$ (cf. Def. 18), for any $A \subseteq \Sigma$ it holds that $\Pi_a(\bigwedge_{x \in A} x) = a \odot (\bigwedge_{x \in A} x) = \bigwedge_{x \in A} (a \odot x) = \bigwedge_{x \in A} \Pi_a(x)$. The result then follows from Theorem 11. $\square$

**Remark 22 ([10]).** Given two counters $x_1, x_2 \in \Sigma$, the series $s \in \bar{\mathbb{Z}}_{\min}[\delta]$ defined by $(\forall t \in \bar{\mathbb{Z}}) s(t) = x_1(t) - x_2(t)$ is not necessarily a counter; $x_1 \odot^\sharp x_2$ is the greatest counter less than or equal to $s$ (in the order of $\bar{\mathbb{Z}}_{\min}[\delta]$). Similarly, provided $x_2 \in \bar{\Sigma}$ (cf. Proposition 21), $x_1 \odot^b x_2$ is the least counter greater than or equal to $s$. ◦

Note that, in Proposition 21, the restriction of $a$ to the subset $\bar{\Sigma}$ is necessary for $\Pi_a$ to meet the conditions of Theorem 11. In fact, if $a(\tau) = \varepsilon$ for some $\tau \in \bar{\mathbb{Z}}$, $(a \odot s_\tau)(\tau) = \varepsilon \otimes \tau = \varepsilon$, so $a \odot s_\tau \neq s_\tau$. If $a(\rho) = \tau$ for some $\rho \in \bar{\mathbb{Z}}$, one can show that $(\exists A \subseteq \Sigma) \Pi_a(\bigwedge_{x \in A} x) \neq \bigwedge_{x \in A} \Pi_a(x)$. Taking, for instance, $A = \bar{\Sigma}$, as $\bigwedge_{x \in \bar{\Sigma}} x = s_\varepsilon$ we have $\Pi_a(\bigwedge_{x \in \bar{\Sigma}} x) = a \odot (\bigwedge_{x \in \bar{\Sigma}} x) = s_\varepsilon$; on the other hand, for any $x \in \bar{\Sigma}$ we have $x(\rho) \neq \varepsilon$ and hence $(a \odot x)(\rho) = \tau \otimes x(\rho) = \tau$, showing that $(\bigwedge_{x \in \bar{\Sigma}} \Pi_a(x))(\rho) = (\bigwedge_{x \in \bar{\Sigma}} (a \odot x))(\rho) = \tau$.

**Remark 23.** Since we take a term like $\eta \delta^\tau$ to mean that a transition has accumulated $\eta$ firings by time $\tau$, it is reasonable to assume that the counters $u, x_i$, and $y$ (cf. Section 2.3) are elements of $\bar{\Sigma}$. Note, additionally, that for any finite subset $B \subseteq \bar{\Sigma}$ one has $\otimes_{s \in B} s \in \bar{\Sigma}$ and $\odot_{s \in B} s \in \bar{\Sigma}$. ◦

# 5 Optimal control of TEGs with resource sharing and output-reference update

In this section, as the main contribution of this paper, we incorporate the ideas discussed in Section 3 to the class of systems studied in Section 4 by showing how to determine the optimal (just-in-time) control inputs in face of changes in the output-references for TEGs that share resources under a given priority policy. We again emphasize that, in this setting, the overall system is not a TEG.

This section is structured similarly to Section 4, starting with the simple case of a single shared resource (Sections 5.1 and 5.2) and then generalizing to the case of multiple resources (Section 5.3).

## 5.1 Problem formulation: the case of a single shared resource

Consider the system from Fig. 5 and assume every subsystem $S^k$ is operating optimally with respect to its own output-reference $z^k$, according to the priority-based strategy introduced in Section 4.1. Now, suppose that at time $T$ each $S^k$ has its reference $z^k$ updated to $z^{k'}$ (with the possibility that $z^{k'} = z^k$ for some of them). Analogously to Section 3, we seek, for each $k$, the input $u_{\text{opt}}^{k'}$ which leads the corresponding output to optimally track $z^{k'}$ while preserving the input $u_{\text{opt}}^k$ up to time $T$. The crucial difference is that now the priority scheme must be observed and, furthermore, the past resource allocations by subsystems with lower priority must also be respected. Such allocations are relevant — despite having occurred before time $T$ — be-
cause the respective resource releases may take place after $T$, thus influencing the availability of the resource in the meantime.

For the purpose of the discussion to follow, let us fix an arbitrary $k \in \{1, \dots, K\}$. When updating the input of $S^k$, we require minimal interference from lower-priority subsystems (i. e., all $S^j$ with $j \in \{k+1, \dots, K\}$). This means that we have to respect past resource allocations in these subsystems, but may ignore future ones. Recall that $x_A^j(t)$ is the accumulated number of firings originally scheduled for $x_A^j$ up to time $t$. Respecting the past means that the firings which have already occurred by time $T$ (when the new references are received) cannot be revoked. On the other hand, the prospective firings that have not taken place by time $T$ can still be postponed and hence, from the point of view of $S^k$, ignored. In other words, for the sake of determining $u_{\text{opt}}^{k'} = x_{A_{\text{opt}}}^{k'}$ with minimal interference from $S^j$, we preserve the terms $x_A^j(t) = x_{A_{\text{opt}}}^j(t)$ for $t \le T$ and neglect all new firings by making $x_A^j(t) = x_{A_{\text{opt}}}^j(t)$ for $t > T$. Recalling Remark 14, this is precisely captured by the counter $r_T^\#(x_{A_{\text{opt}}}^j)$.

In sum, (i) we must compute $x_{A_{\text{opt}}}^{k'}$ in decreasing order of priority, i. e., start from $k=1$ and proceed up to $k=K$; (ii) when calculating $x_{A_{\text{opt}}}^{k'}$ for $k > 1$, we must consider $x_{A_{\text{opt}}}^{i'}$ for every $i \in \{1, \dots, k-1\}$; (iii) when calculating $x_{A_{\text{opt}}}^{k'}$ for $k < K$, we must consider $r_T^\#(x_{A_{\text{opt}}}^j)$ for every $j \in \{k+1, \dots, K\}$.
It will be convenient to define the following terms:

$$ \mathcal{H}_A^k = \bigcirc_{i=1}^{k-1} x_{A_{\text{opt}}}^{i'} , \quad \mathcal{H}_R^k = \bigcirc_{i=1}^{k-1} (G^i \otimes x_{A_{\text{opt}}}^{i'}), \\ \mathcal{L}_A^k = \bigcirc_{j=k+1}^{K} r_T^\#(x_{A_{\text{opt}}}^j), \quad \mathcal{L}_R^k = \bigcirc_{j=k+1}^{K} (G^j \otimes r_T^\#(x_{A_{\text{opt}}}^j)). $$

$\mathcal{H}_A^k$ combines the counters $x_{A_{\text{opt}}}^{i'}$ of all subsystems $S^i$ with priority higher than that of $S^k$, referring to the already-updated optimal schedules of resource-allocation transitions $x_A^j$ with respect to the corresponding updated references $z^{i'}$; accordingly, $\mathcal{H}_R^k$ combines the counters $x_{R_{\text{opt}}}^{i'} = G^i \otimes x_{A_{\text{opt}}}^{i'}$ representing the respective resource-release events. In a similar way, $\mathcal{L}_A^k$ combines the counters $r_T^\#(x_{A_{\text{opt}}}^j)$ of all subsystems $S^i$ with priority lower than that of $S^k$, representing the past firings (up to time $T$) of resource-allocation transitions $x_A^j$ and neglecting their firings after time $T$, whereas $\mathcal{L}_R^k$ gathers the respective resource-release events by combining the counters $G^j \otimes r_T^\#(x_{A_{\text{opt}}}^j)$; it should be emphasized that, even though we only consider the resource allocations by $S^j$ up to time $T$, the respective resource-release events may take place after $T$, so in general one may have $G^j \otimes r_T^\#(x_{A_{\text{opt}}}^j) \neq r_T^\#(x_{R_{\text{opt}}}^j)$.

Thus, based on (9) and on the foregoing discussion, in order to update $u^k = x_A^k$ without compromising the performance of higher-priority subsystems and, at the same time, ensuring minimal interference of lower-priority subsystems while taking into account their past resource allocations, we must respect

$$ \beta \otimes (\mathcal{H}_R^k \odot (G^k \otimes x_A^k) \odot \mathcal{L}_R^k) \leq \mathcal{H}_A^k \odot x_A^k \odot \mathcal{L}_A^k, \quad (*) $$

where it is understood that for $k=1$ (resp. $k=K$), the degenerate terms $\mathcal{H}_A^1$ and $\mathcal{H}_R^1$ (resp. $\mathcal{L}_A^K$ and $\mathcal{L}_R^K$) are to be neglected.

The problem of determining the new optimal input $u_{\text{opt}}^{k'} (= x_{A_{\text{opt}}}^{k'})$ with respect to a reference $z^{k'}$ given at time $T$ can be formulated as follows: find the greatest element of the set

$$ \mathcal{F}^k = \{x_A^k \in \Sigma \mid G^k \otimes x_A^k \leq z^{k'} \text{ and } (*) \text{ and} \\ r_T(x_A^k) = r_T(x_{A_{\text{opt}}}^k)\}. \quad (20) $$

**Remark 24.** It should be clear that, for any $k \in \{1, \dots, K\}$, if $z^{i'} = z^i$ for all $i \in \{1, \dots, k\}$, then $x_{A_{\text{opt}}}^{i'} = x_{A_{\text{opt}}}^i$ for all $i \in \{1, \dots, k\}$. Nonetheless, if $z^{i'} \neq z^i$ for some $i < k$, in general it may be that $x_{A_{\text{opt}}}^{k'} \neq x_{A_{\text{opt}}}^k$ even if $z^{k'} = z^k$ (see Example 28). ◦

## 5.2 Optimal update of the inputs: the case of a single shared resource

We set out to look for the greatest element of set $\mathcal{F}^k$ (defined as in (20)) by proposing a slight generalization of Theorem 13.

**Proposition 25.** Let $\mathcal{D}$ and $\mathcal{C}$ be complete idempotent semirings, $f_1, f_2 : \mathcal{D} \to \mathcal{C}$ residuated mappings, $\psi : \mathcal{D} \to \mathcal{C}$, and $c \in \mathcal{C}$. Consider the set

$$ S_{\psi}^{\text{def}} = \{x \in \mathcal{D} \mid f_1(x) \leq \psi(x) \text{ and } f_2(x) = c\} $$

and the isotone mapping $\Omega : \mathcal{D} \to \mathcal{D}$,

$$ \Omega(x) = x \wedge f_1^\#(\psi(x)) \wedge f_2^\#(c). $$

If $S_{\psi} \neq \emptyset$, we have $\bigoplus_{x \in S_{\psi}} x = \bigoplus \{x \in \mathcal{D} \mid \Omega(x) = x\}$.

*Proof.* Define the set

$$ \bar{S}_{\psi} = \{x \in \mathcal{D} \mid f_1(x) \leq \psi(x) \text{ and } f_2(x) \leq c\} $$

and denote $\chi = \bigoplus_{x \in S_{\psi}} x$ and $\bar{\chi} = \bigoplus_{x \in \bar{S}_{\psi}} x$. Note that

$$ \begin{align*} f_1(x) &\leq \psi(x) \text{ and } f_2(x) \leq c \\ \Leftrightarrow x &\leq f_1^\#(\psi(x)) \text{ and } x \leq f_2^\#(c) \quad (\text{see Def. 8}) \\ \Leftrightarrow x &\leq f_1^\#(\psi(x)) \wedge f_2^\#(c) \\ \Leftrightarrow x &= x \wedge f_1^\#(\psi(x)) \wedge f_2^\#(c) = \Omega(x). \end{align*} $$
So, we can rewrite $\tilde{S}_{\psi}$ as $\tilde{S}_{\psi} = \{x \in \mathcal{D} | x = \Omega(x)\}$, clearly implying $\bar{\chi} = \bigoplus \{x \in \mathcal{D} | \Omega(x) = x\}$. Then, it also follows from Remark 4 that $\bar{\chi} \in \tilde{S}_{\psi}$.

Now, assume $S_{\psi} \neq \emptyset$. As $S_{\psi} \subseteq \tilde{S}_{\psi}$, this implies $(\exists \bar{x} \in \tilde{S}_{\psi}) f_2(\bar{x}) = c$. Taking such an $\bar{x}$, we have $\bar{x} \leq \bar{\chi}$ and so $c = f_2(\bar{x}) \leq f_2(\bar{x})$ (as $f_2$ is isotone). But we saw above that $\bar{\chi} \in \tilde{S}_{\psi}$, meaning $f_2(\bar{x}) \leq c$, so $f_2(\bar{x}) = c$. Therefore, $\bar{\chi} \in S_{\psi}$ and hence $\bar{\chi} \leq \chi$. On the other hand, $S_{\psi} \subseteq \tilde{S}_{\psi}$ implies $\chi \leq \bar{\chi}$, showing that $\bar{\chi} = \chi$. $\square$

Now, let us once more fix an arbitrary $k \in \{1, \dots, K\}$, and assume $x_{A_{opt}}^{i'}$ has been determined for each (if any) $i \in \{1, \dots, k-1\}$. Seeing that $(\star)$ is equivalent to

$$G^k \otimes x_A^k \leq (\beta \mathfrak{h}(\mathcal{H}_A^k \odot x_A^k \odot \mathcal{L}_A^k)) \odot^\flat (\mathcal{H}_R^k \odot \mathcal{L}_R^k),$$

by defining the mapping $\Psi^k : \Sigma \to \Sigma$,

$$\Psi^k(x) = z^{k'} \wedge [(\beta \mathfrak{h}(\mathcal{H}_A^k \odot x \odot \mathcal{L}_A^k)) \odot^\flat (\mathcal{H}_R^k \odot \mathcal{L}_R^k)]$$

we can write

$$\mathcal{F}^k = \{x \in \Sigma | G^k \otimes x \leq \Psi^k(x) \text{ and } r_T(x) = r_T(x_{A_{opt}}^k)\}.$$

This reveals a correspondence between set $\mathcal{F}^k$ and set $S_{\psi}$ from Proposition 25: take $\mathcal{D}$ and $\mathcal{C}$ both as $\Sigma$, $f_1$ as $L_{G^k}$, $\psi$ as $\Psi^k$, $f_2$ as $r_T$, and $c$ as $r_T(x_{A_{opt}}^k)$. So, as long as $\mathcal{F}^k \neq \emptyset$, the conditions from the proposition are met and, recalling that $r_T^\# \circ r_T = r_T^\#$, the optimal update of $x_A^k$ is the greatest fixed point of the (isotone) mapping $\Gamma^k : \Sigma \to \Sigma$,

$$\Gamma^k(x) = x \wedge G^k \mathfrak{h} \Psi^k(x) \wedge r_T^\#(x_{A_{opt}}^k). \quad (21)$$

Next, we must investigate when $\mathcal{F}^k$ is nonempty. To that end, considering the set

$$\bar{\mathcal{F}}^k = \{x_A^k \in \Sigma | (\star) \text{ and } r_T(x_A^k) = r_T(x_{A_{opt}}^k)\},$$

we want to show that

$$\underline{x}_A^k \stackrel{\text{def}}{=} \bigwedge_{x \in \bar{\mathcal{F}}^k} x \in \bar{\mathcal{F}}^k, \quad (22)$$

i. e., that there exists a (unique) least counter, which we will denote by $\underline{x}_A^k$, satisfying both $(\star)$ and $r_T(x_A^k) = r_T(x_{A_{opt}}^k)$. Define the mapping $\mathcal{Y}^k : \Sigma \to \Sigma$,

$$\mathcal{Y}^k(x) = [(\beta \otimes (\mathcal{H}_R^k \odot (G^k \otimes x) \odot \mathcal{L}_R^k)) \odot^\flat (\mathcal{H}_A^k \odot \mathcal{L}_A^k)] \oplus r_T(x_{A_{opt}}^k) \oplus x.$$

Note that, from Proposition 21 and Remark 23, the mapping $\Pi_{(\mathcal{H}_A^k \odot \mathcal{L}_A^k)}$ is dually residuated, so $\mathcal{Y}^k$ is well defined. Since $x \geq r_T(x)$ for any $x \in \Sigma$, for any element $\bar{x}_A^k$ of $\bar{\mathcal{F}}^k$ it

follows that $\bar{x}_A^k \geq r_T(\bar{x}_A^k) = r_T(x_{A_{opt}}^k)$. As, in addition, $(\star)$ is equivalent to

$$(\beta \otimes (\mathcal{H}_R^k \odot (G^k \otimes x_A^k) \odot \mathcal{L}_R^k)) \odot^\flat (\mathcal{H}_A^k \odot \mathcal{L}_A^k) \leq x_A^k,$$

one can see that $\mathcal{Y}^k(\bar{x}_A^k) = \bar{x}_A^k$, i. e., every element of $\bar{\mathcal{F}}^k$ is a fixed point of $\mathcal{Y}^k$; in short, $\bar{\mathcal{F}}^k \subseteq \{x \in \Sigma | \mathcal{Y}^k(x) = x\}$. Hence, denoting

$$\bigwedge_{\mathcal{Y}^k} \stackrel{\text{def}}{=} \bigwedge \{x \in \Sigma | \mathcal{Y}^k(x) = x\}$$

(which, according to Remark 4, is the least fixed point of $\mathcal{Y}^k$), we have

$$\underline{x}_A^k \geq \bigwedge_{\mathcal{Y}^k} . \quad (23)$$

To prove the converse inequality, we proceed to show that $\bigwedge_{\mathcal{Y}^k}$ is an element of $\bar{\mathcal{F}}^k$.

**Proposition 26.** $\bigwedge_{\mathcal{Y}^k} \stackrel{\text{def}}{=} \bigwedge \{x \in \Sigma | \mathcal{Y}^k(x) = x\} \in \bar{\mathcal{F}}^k$.

*Proof.* Any $x_A^k \in \Sigma$ such that $\mathcal{Y}^k(x_A^k) = x_A^k$ satisfies

$$(\beta \otimes (\mathcal{H}_R^k \odot (G^k \otimes x_A^k) \odot \mathcal{L}_R^k)) \odot^\flat (\mathcal{H}_A^k \odot \mathcal{L}_A^k) \leq x_A^k$$

and, by consequence (cf. Def. 8), also satisfies $(\star)$. According to Remark 4, $\bigwedge_{\mathcal{Y}^k}$ is a fixed point of $\mathcal{Y}^k$, therefore $(\star)$ holds for $x_A^k = \bigwedge_{\mathcal{Y}^k}$ and it suffices to prove that $r_T(\bigwedge_{\mathcal{Y}^k}) = r_T(x_{A_{opt}}^k)$.

$\bigwedge_{\mathcal{Y}^k}$ being a fixed point of $\mathcal{Y}^k$ implies $\bigwedge_{\mathcal{Y}^k} \geq r_T(x_{A_{opt}}^k)$, so $r_T(\bigwedge_{\mathcal{Y}^k}) \geq r_T(r_T(x_{A_{opt}}^k)) = r_T(x_{A_{opt}}^k)$.

Moreover, $r_T^\#(x_{A_{opt}}^k)$ is a fixed point of $\mathcal{Y}^k$, as can be seen from the following argument. Since we assume $x_{A_{opt}}^{i'}$ to be given for each $i \in \{1, \dots, k-1\}$, according to $(\star)$ we know $x_{A_{opt}}^{(k-1)'}$ fulfills

$$\beta \otimes (\mathcal{H}_R^{(k-1)} \odot (G^{(k-1)} \otimes x_{A_{opt}}^{(k-1)'} \odot \mathcal{L}_R^{(k-1)}) \leq \mathcal{H}_A^{(k-1)} \odot x_{A_{opt}}^{(k-1)'} \odot \mathcal{L}_A^{(k-1)}. \quad (24)$$

But note that

$$\mathcal{H}_R^{(k-1)} \odot (G^{(k-1)} \otimes x_{A_{opt}}^{(k-1)'} ) = \mathcal{H}_R^k,$$

$$\mathcal{L}_R^{(k-1)} = (G^k \otimes r_T^\#(x_{A_{opt}}^k)) \odot \mathcal{L}_R^k,$$

$$\mathcal{H}_A^{(k-1)} \odot x_{A_{opt}}^{(k-1)'} = \mathcal{H}_A^k, \quad \text{and}$$

$$\mathcal{L}_A^{(k-1)} = r_T^\#(x_{A_{opt}}^k) \odot \mathcal{L}_A^k,$$

so (24) is equivalent to

$$\beta \otimes (\mathcal{H}_R^k \odot (G^k \otimes r_T^\#(x_{A_{opt}}^k)) \odot \mathcal{L}_R^k) \leq (\mathcal{H}_A^k \odot r_T^\#(x_{A_{opt}}^k)) \odot \mathcal{L}_A^k$$

which, in turn, implies

$$(\beta \otimes (\mathcal{H}_R^k \odot (G^k \otimes r_T^\#(x_{A_{opt}}^k)) \odot \mathcal{L}_R^k)) \odot^\flat (\mathcal{H}_A^k \odot \mathcal{L}_A^k) \leq r_T^\#(x_{A_{opt}}^k).$$
This, together with the fact that $r_T^\#(x_{A_{opt}}^k) \ge r_T(x_{A_{opt}}^k)$, implies $\mathcal{Y}^k(r_T^\#(x_{A_{opt}}^k)) = r_T^\#(x_{A_{opt}}^k)$. Hence, $\bigwedge_{\mathcal{Y}^k} \le r_T^\#(x_{A_{opt}}^k)$ and, as $r_T$ is isotone and $r_T \circ r_T^\# = r_T$, we have $r_T(\bigwedge_{\mathcal{Y}^k}) \le r_T(r_T^\#(x_{A_{opt}}^k)) = r_T(x_{A_{opt}}^k)$, which concludes the proof. □

A direct consequence of Proposition 26 is that $\underline{x}_A^k \le \bigwedge_{\mathcal{Y}^k}$, which, combined with (23), implies

$$ \underline{x}_A^k = \bigwedge_{\mathcal{Y}^k}, \qquad (25) $$

thus proving that (22) holds. Isotony of $L_{G^k}$ then implies

$$ \mathcal{F}^k \neq \emptyset \Leftrightarrow G^k \otimes \underline{x}_A^k \le z^{k'}. \qquad (26) $$

In case $G^k \otimes \underline{x}_A^k \neq z^{k'}$ (and hence, according to (26), $\mathcal{F}^k = \emptyset$), this means the past inputs of $S^k$ itself, combined with the (updated) operation of higher-priority subsystems and with the past inputs of lower-priority ones, make it impossible for $S^k$ to respect $z^{k'}$. As $(\cdot)$ and $r_T(x_A^k) = r_T(x_{A_{opt}}^k)$ are irrevocable, we will then seek the least way to relax $z^{k'}$ (i. e., look for the least counter $z^{k''} \ge z^{k'}$) such that the set

$$ \mathcal{F}_{z^{k''}}^k = \{x_A^k \in \Sigma | G^k \otimes x_A^k \le z^{k''} \text{ and } (\cdot) \text{ and} \\ r_T(x_A^k) = r_T(x_{A_{opt}}^k)\} $$

is nonempty. The solution is given by the following result.

**Proposition 27.** The least counter $z^{k''} \ge z^{k'}$ such that $\mathcal{F}_{z^{k''}}^k \neq \emptyset$ is $z^{k''} = z^{k'} \oplus (G^k \otimes \underline{x}_A^k)$.

*Proof.* Taking $z^{k''} = z^{k'} \oplus (G^k \otimes \underline{x}_A^k)$, it can be readily checked that $\underline{x}_A^k \in \mathcal{F}_{z^{k''}}^k$, therefore $\mathcal{F}_{z^{k''}}^k \neq \emptyset$; the proof then proceeds by direct analogy with that of Proposition 16. □

Following the same reasoning as before, we define the mapping $\Psi_{z^{k''}}^k : \Sigma \to \Sigma$,

$$ \Psi_{z^{k''}}^k(x) = z^{k''} \wedge [(\beta \upharpoonright (\mathcal{H}_A^k \otimes x \otimes \mathcal{L}_A^k)) \circ^\# (\mathcal{H}_R^k \circ \mathcal{L}_R^k)], $$

with $z^{k''} = z^{k'} \oplus (G^k \otimes \underline{x}_A^k)$. Since we know from Proposition 27 that $\mathcal{F}_{z^{k''}}^k \neq \emptyset$, we can again apply Proposition 25 — only now taking $\Psi$ as $\Psi_{z^{k''}}^k$ instead of $\Psi^k$ — to finally conclude that $x_{A_{opt}}^{k'}$ is the greatest fixed point of the (isotone) mapping $\Gamma_{z^{k''}}^k : \Sigma \to \Sigma$,

$$ \Gamma_{z^{k''}}^k(x) = x \wedge G^k \upharpoonright \Psi_{z^{k''}}^k(x) \wedge r_T^\#(x_{A_{opt}}^k). \qquad (27) $$

**Example 28.** Consider the system from Example 20 (Fig. 8), with $S^1$, $S^2$, and $S^3$ operating under the obtained optimal schedules with respect to references $z^1$, $z^2$, and $z^3$, respectively. Now, suppose new references $z^{1'} = e\delta^{36} \oplus 16^{46} \oplus 36^{54} \oplus 56^{55} \oplus 6\delta^{+\infty}$, $z^{2'} = z^2$, and $z^{3'} = z^3$ are received at time $T = 27$. Observing the pri-

ority policy, we start by updating the input of $S^1$. Recall that, for $k = 1$, the terms $\mathcal{H}_A^1$ and $\mathcal{H}_R^1$ are not well defined and hence are disregarded in $(\cdot)$. For the relevant terms, we have $\mathcal{L}_A^1 = r_T^\#(x_{A_{opt}}^2) \circ r_T^\#(x_{A_{opt}}^3) = e\delta^{24} \oplus 16^{+\infty}$ and $\mathcal{L}_R^1 = (G^2 \otimes r_T^\#(x_{A_{opt}}^2)) \circ (G^3 \otimes r_T^\#(x_{A_{opt}}^3)) = e\delta^{26} \oplus 16^{+\infty}$. Note that $\mathcal{L}_A^1$ refers to all allocations of the resource by $S^2$ and $S^3$ up to time $T = 27$ — in this case, just one allocation (by $S^3$) at $t = 25$ — and $\mathcal{L}_R^1$ represents the corresponding resource releases. These two terms combined inform that one instance of the resource is occupied from $t = 25$ until $t = 27$; inequality $(\cdot)$ accordingly imposes a hard condition on $x_A^1$. The second hard condition is to preserve the past inputs of $S^1$ itself, meaning $r_T(x_A^1) = r_T(x_{A_{opt}}^1)$. For this example, $r_T(x_{A_{opt}}^1) = e\delta^{27} \oplus \varepsilon\delta^{+\infty}$, so the restriction is simply that there can be no firing of $x_A^1$ (and hence nor of $u^1$) before or at time $T = 27$. Defining $\mathcal{F}^1$ as in (20), through (26) one can check that $\mathcal{F}^1 \neq \emptyset$; then, we can directly look for the greatest fixed point of $\Gamma^1$ (defined as in (21)), which is $x_{A_{opt}}^{1'} = e\delta^{33} \oplus 16^{42} \oplus 2\delta^{43} \oplus 3\delta^{47} \oplus 4\delta^{51} \oplus 56^{52} \oplus 6\delta^{+\infty} (= u_{opt}^{1'})$. Then, $x_{R_{opt}}^{1'} = e\delta^{36} \oplus 16^{45} \oplus 2\delta^{46} \oplus 3\delta^{50} \oplus 4\delta^{54} \oplus 56^{55} \oplus 6\delta^{+\infty} (= y_{opt}^{1'})$.

We now proceed to update $x_A^2$. We have $\mathcal{H}_A^2 = x_{A_{opt}}^{1'}$, $\mathcal{H}_R^2 = x_{R_{opt}}^{1'}$, $\mathcal{L}_A^2 = r_T^\#(x_{A_{opt}}^3) = e\delta^{24} \oplus 16^{+\infty}$, and $\mathcal{L}_R^2 = G^3 \otimes r_T^\#(x_{A_{opt}}^3) = e\delta^{26} \oplus 16^{+\infty}$. Moreover, $r_T(x_{A_{opt}}^2) = e\delta^{27} \oplus \varepsilon\delta^{+\infty}$. We then verify that $\mathcal{F}^2 = \emptyset$, so we look for the least $z^{2''} \ge z^{2'}$ such that $\mathcal{F}_{z^{2''}}^2 \neq \emptyset$. According to Proposition 27, we obtain $z^{2''} = e\delta^{39} \oplus 16^{50} \oplus 2\delta^{61} \oplus 3\delta^{+\infty}$. Computing the greatest fixed point of $\Gamma_{z^{2''}}^2$ then yields $x_{A_{opt}}^{2'} = e\delta^{29} \oplus 16^{36} \oplus 2\delta^{56} \oplus 3\delta^{+\infty} (= u_{opt}^{2'})$ and $x_{R_{opt}}^{2'} = e\delta^{34} \oplus 16^{41} \oplus 2\delta^{61} \oplus 3\delta^{+\infty} (= y_{opt}^{2'})$. Notice that $x_{A_{opt}}^{2'} \neq x_{R_{opt}}^{2'}$ even though $z^{2'} = z^2$ (cf. Remark 24).

Finally, for $S^3$ we get $\mathcal{H}_A^3 = x_{A_{opt}}^{1'} \circ x_{A_{opt}}^{2'} = e\delta^{29} \oplus 16^{33} \oplus 2\delta^{36} \oplus 36^{42} \oplus 4\delta^{43} \oplus 5\delta^{47} \oplus 6\delta^{51} \oplus 7\delta^{52} \oplus 8\delta^{56} \oplus 9\delta^{+\infty}$ and $\mathcal{H}_R^3 = x_{R_{opt}}^{1'} \circ x_{R_{opt}}^{2'} = e\delta^{34} \oplus 16^{36} \oplus 2\delta^{41} \oplus 36^{45} \oplus 4\delta^{46} \oplus 56^{50} \oplus 6\delta^{54} \oplus 7\delta^{55} \oplus 8\delta^{61} \oplus 9\delta^{+\infty}$. Recall that, for $k = K = 3$, the terms $\mathcal{L}_A^3$ and $\mathcal{L}_R^3$ are not well defined and hence are disregarded in $(\cdot)$. With $r_T(x_{A_{opt}}^3) = e\delta^{24} \oplus 16^{27} \oplus \varepsilon\delta^{+\infty}$, we have $\mathcal{F}^3 \neq \emptyset$, so we compute the greatest fixed point of $\Gamma^3$ and obtain $x_{A_{opt}}^{3'} = e\delta^{24} \oplus 16^{29} \oplus 2\delta^{38} \oplus 3\delta^{+\infty} (= u_{opt}^{3'})$. Then, $x_{R_{opt}}^{3'} = e\delta^{26} \oplus 16^{31} \oplus 2\delta^{40} \oplus 3\delta^{+\infty} (= y_{opt}^{3'})$.

The updated optimal schedules are shown in Fig. 10. ◇

## 5.3 Extension to the case of multiple shared resources

Consider the system from Fig. 9, with every subsystem $S^k$ following the optimal schedule with respect to output-reference $z^k$, obtained according to Section 4.3. Suppose
<figure><img src="image_14.png" /><figcaption>**Figure 10:** Updated optimal schedules obtained in Example 28; the gray, black, and crosshatched bars represent the operation of $S^1$, $S^2$, and $S^3$, respectively, whereas the dashed bars are the delays imposed by the resource.</figcaption></figure>

that each reference $z^k$ is updated to $z^{k'}$ at time $T$ (with perhaps $z^{k'} = z^k$ for some of them). In this section we seek, for each $k$, the optimal input $u_{\text{opt}}^{k'}$ which preserves $u_{\text{opt}}^k$ up to time $T$ and results in the output $y_{\text{opt}}^{k'}$ that tracks $z^{k'}$ as closely as possible, without interfering with the operation of higher-priority subsystems and while respecting the past resource allocations of every resource by lower-priority subsystems.

As usual, we base the following discussion on a fixed but arbitrary $k \in \{1, \dots, K\}$. Let us denote the counter representing the updated optimal firing schedule for the resource-allocation transition $x_A^{k\ell}$ by $x_{A_{\text{opt}}}^{k\ell'}$. Arguing as in Section 5.1, the task at hand can be summarized as follows: (i) we must compute $u_{\text{opt}}^{k'}$ in decreasing order of priority; (ii) when calculating $u_{\text{opt}}^{k'}$ for $k > 1$, we must consider $x_{A_{\text{opt}}}^{i\ell'}$ for every $i \in \{1, \dots, k-1\}$ and for all $\ell \in \{1, \dots, L\}$; (iii) when calculating $u_{\text{opt}}^{k'}$ for $k < K$, we must consider $r_T^{\sharp}(x_{A_{\text{opt}}}^{j\ell'})$ for every $j \in \{k+1, \dots, K\}$ and for all $\ell \in \{1, \dots, L\}$.

Still along the lines of Section 5.1, define the terms

$$ \mathcal{H}_A^{k\ell} = \bigodot_{i=1}^{k-1} x_{A_{\text{opt}}}^{i\ell'}, \quad \mathcal{H}_R^{k\ell} = \bigodot_{i=1}^{k-1} x_{R_{\text{opt}}}^{i\ell'}, \\ \mathcal{L}_A^{k\ell} = \bigodot_{j=k+1}^{K} r_T^{\sharp}(x_{A_{\text{opt}}}^{j\ell}), \quad \mathcal{L}_R^{k\ell} = \bigodot_{j=k+1}^{K} (H^{j\ell} \otimes r_T^{\sharp}(x_{A_{\text{opt}}}^{j\ell})), $$

which can be explained as in the referred section, only now for each resource $\ell$. We aim at updating $u^k$ without compromising the performance of higher-priority subsystems and, at the same time, ensuring minimal interference from lower-priority subsystems while taking into account their past allocations of all resources. Based on (16), we must consequently respect, for every $\ell \in \{1, \dots, L\}$,

$$ \beta \otimes (\mathcal{H}_R^{k\ell} \odot x_R^{k\ell} \odot \mathcal{L}_R^{k\ell}) \le \mathcal{H}_A^{k\ell} \odot x_A^{k\ell} \odot \mathcal{L}_A^{k\ell}, \quad (\star\star) $$

where it is understood that for $k=1$ (resp. $k=K$), the degenerate terms $\mathcal{H}_A^{1\ell}$ and $\mathcal{H}_R^{1\ell}$ (resp. $\mathcal{L}_A^{K\ell}$ and $\mathcal{L}_R^{K\ell}$) are to be neglected.

We can then formulate the problem of optimally updating the input $u_{\text{opt}}^{k'}$ with respect to a reference $z^{k'}$ given at time $T$ as follows: find the greatest element of the set

$$ \mathcal{M}^k = \{u^k \in \Sigma | \begin{array}{l} G^k \otimes u^k \le z^{k'} \text{ and } r_T(u^k) = r_T(u_{\text{opt}}^k) \\ \text{and } (\star\star) \text{ holds for all } \ell \in \{1, \dots, L\}. \end{array} \} $$

Recall from Section 4.3 that we can write $x_A^{k\ell} = \mathcal{P}^{k\ell} \otimes u^k$ and $x_R^{k\ell} = H^{k\ell} \otimes \mathcal{P}^{k\ell} \otimes u^k$, with $\mathcal{P}^{k\ell}$ defined as in (19). Applying this to $(\star\star)$ gives

$$ \beta \otimes (\mathcal{H}_R^{k\ell} \odot (H^{k\ell} \otimes \mathcal{P}^{k\ell} \otimes u^k) \odot \mathcal{L}_R^{k\ell}) \le \mathcal{H}_A^{k\ell} \odot (\mathcal{P}^{k\ell} \otimes u^k) \odot \mathcal{L}_A^{k\ell}, \quad (28) $$

which is equivalent to

$$ u^k \le (H^{k\ell} \otimes \mathcal{P}^{k\ell}) \mathcal{v} \left[ (\beta^\ell \mathcal{v} (\mathcal{H}_A^{k\ell} \odot (\mathcal{P}^{k\ell} \otimes u^k) \odot \mathcal{L}_A^{k\ell})) \odot^\sharp (\mathcal{H}_R^{k\ell} \odot \mathcal{L}_R^{k\ell}) \right]. $$

Define the mappings $\Psi^{k\ell} : \Sigma \to \Sigma$,

$$ \Psi^{k\ell}(x) = (H^{k\ell} \otimes \mathcal{P}^{k\ell}) \mathcal{v} \left[ (\beta^\ell \mathcal{v} (\mathcal{H}_A^{k\ell} \odot (\mathcal{P}^{k\ell} \otimes x) \odot \mathcal{L}_A^{k\ell})) \odot^\sharp (\mathcal{H}_R^{k\ell} \odot \mathcal{L}_R^{k\ell}) \right], \\ \ell \in \{1, \dots, L\}, \text{ and } \bar{\Psi}^k : \Sigma \to \Sigma, $$

$$ \bar{\Psi}^k(x) = G^k \mathcal{v} z^{k'} \wedge \bigwedge_{\ell=1}^{L} \Psi^{k\ell}(x). $$

We can then rewrite $\mathcal{M}^k$ as

$$ \mathcal{M}^k = \{x \in \Sigma | x \le \bar{\Psi}^k(x) \text{ and } r_T(x) = r_T(u_{\text{opt}}^k)\}. $$

Note that $x \le \bar{\Psi}^k(x)$ is equivalent to $\text{Id}_\Sigma(x) \le \bar{\Psi}^k(x)$, where $\text{Id}_\Sigma$ is the identity mapping on $\Sigma$. It is trivial to verify that $\text{Id}_\Sigma$ is residuated and that $\text{Id}_\Sigma^\sharp = \text{Id}_\Sigma$. Therefore, there exists a correspondence between $\mathcal{M}^k$ and $S_\psi$ from Proposition 25: take $\mathcal{D}$ and $\mathcal{C}$ both as $\Sigma$, $f_1$ as $\text{Id}_\Sigma$, $\psi$ as $\bar{\Psi}^k$, $f_2$ as $r_T$, and $c$ as $r_T(u_{\text{opt}}^k)$. Provided $\mathcal{M}^k \ne \emptyset$, the proposition entails that $u_{\text{opt}}^{k'}$ can be determined by computing the greatest fixed point of the (isotone) mapping $\Lambda^k : \Sigma \to \Sigma$,

$$ \Lambda^k(x) = x \wedge \bar{\Psi}^k(x) \wedge r_T^{\sharp}(u_{\text{opt}}^k). $$

In order to check whether $\mathcal{M}^k$ is nonempty, consider the set

$$ \bar{\mathcal{M}}^k = \{u^k \in \Sigma | (\star\star) \text{ holds for all } \ell \in \{1, \dots, L\} \text{ and} \\ r_T(u^k) = r_T(u_{\text{opt}}^k)\}. $$

We want to show that

$$ \underline{u}^k \stackrel{\text{def}}{=} \bigwedge_{x \in \bar{\mathcal{M}}^k} x \in \bar{\mathcal{M}}^k, $$
i. e., that there exists a (unique) least counter $\underline{u}^k$ satisfying
(**) for all $\ell \in \{1, \dots, L\}$ and $r_T(\underline{u}^k) = r_T(u_{\text{opt}}^k)$. Define, for
each $\ell \in \{1, \dots, L\}$, the mapping $\bar{Y}^{\ell k} : \Sigma \to \Sigma$,

$$
\bar{Y}^{k\ell}(x) = \mathcal{P}^{k\ell} \cap [(\beta \otimes (\mathcal{H}_R^{k\ell} \circ (H^{k\ell} \otimes \mathcal{P}^{k\ell} \otimes x) \circ \mathcal{L}_R^{k\ell})) \circ^b (\mathcal{H}_A^{k\ell} \circ \mathcal{L}_A^{k\ell})],
$$

and also the mapping $\bar{\mathcal{Y}}^k : \Sigma \to \Sigma$,

$$
\bar{\mathcal{Y}}^k(x) = x \oplus r_T(u_{\text{opt}}^k) \oplus \bigoplus_{\ell=1}^{L} \mathcal{Y}^{k\ell}(x).
$$

Since (**) is equivalent to (28) which, in turn, is equivalent to

$$
\mathcal{P}^{k\ell} \cap [(\beta \otimes (\mathcal{H}_R^{k\ell} \circ (H^{k\ell} \otimes \mathcal{P}^{k\ell} \otimes \underline{u}^k) \circ \mathcal{L}_R^{k\ell})) \circ^b (\mathcal{H}_A^{k\ell} \circ \mathcal{L}_A^{k\ell})] \le \underline{u}^k,
$$

one can see that for any element $\bar{u}^k$ of $\overline{\mathcal{M}}^k$ we have
$\bar{Y}^{k\ell}(\bar{u}^k) \le \bar{u}^k$ for all $\ell$. As $\bar{u}^k \ge r_T(\bar{u}^k) = r_T(u_{\text{opt}}^k)$, it actually
holds that $\bar{Y}^k(\bar{u}^k) = \bar{u}^k$, implying $\overline{\mathcal{M}}^k \subseteq \{x \in \Sigma | \bar{Y}^k(x) = x\}$.
Hence, denoting

$$
\bigwedge \bar{\mathcal{Y}}^k \stackrel{\text{def}}{=} \bigwedge \{x \in \Sigma \mid \bar{\mathcal{Y}}^k(x) = x\}
$$

we have

$$
\underline{u}^k \geq \bigwedge \bar{\mathcal{Y}}^k .
$$

By arguments parallel to those put forth in Section 5.2, it
can be shown that the converse inequality also holds, so
we have

$$
\underline{u}^k = \bigwedge \bar{Y}^k .
$$

Analogously to (26), this leads to the conclusion that

$$
\mathcal{M}^k \neq \emptyset \Leftrightarrow G^k \otimes \underline{u}^k \leq z^{k'}.
$$

In case $G^k \otimes \underline{u}^k \neq z^{k'}$, we look for the least counter $z^{k''} \geq z^{k'}$
such that the set

$$
\mathcal{M}_{z^{k''}}^{k} = \{\underline{u}^{k} \in \Sigma \mid G^{k} \otimes \underline{u}^{k} \leq z^{k''} \text{ and } r_{T}(\underline{u}^{k}) = r_{T}(\underline{u}_{\text{opt}}^{k}) \\
\text{ and } (**)} \text{ holds for all } \ell \in \{1, \dots, L\} \}.
$$

is nonempty. A straightforward adaptation of Proposition 27 gives the solution $z^{k''} = z^{k'} \oplus (G^k \otimes \underline{u}^k)$.

Following the same reasoning as before, we define the
mapping $\bar{\Psi}_{z^{k''}} : \Sigma \to \Sigma$,

$$
\bar{\Psi}_{z^{k''}}^{k}(x) = G^{k} \cap z^{k''} \wedge \bigwedge_{\ell=1}^{L} \Psi^{k\ell}(x),
$$

with $z^{k''} = z^{k'} \oplus (G^k \otimes \underline{u}^k)$. We can then once more apply
Proposition 25, only now taking $\psi$ as $\bar{\Psi}_{z^{k''}}^k$ instead of $\bar{\Psi}^k$,
which leads to the conclusion that $u_{\text{opt}}^{k'}$ is the greatest fixed
point of the (isotone) mapping $\Lambda_{z^{k''}}^k : \Sigma \to \Sigma$,

$$
\Lambda_{z^{k''}}^{k}(x) = x \wedge \bar{\Psi}_{z^{k''}}^{k}(x) \wedge r_{T}^{\#}(u_{\text{opt}}^{k}).
$$

6 Conclusion

This paper solves the problem of ensuring that a number
of TEGs competing for the use of shared resources operate
optimally (in a just-in-time sense) even in face of changes
in their output-references. The proposed method assumes
a prespecified priority policy on the component TEGs, and
the optimal inputs are computed under the rule that the
operation of lower-priority subsystems cannot interfere
with the performance of higher-priority ones. However,
when higher-priority subsystems recompute their inputs
after a change in the reference signal occurs, they need
of course to respect past resource allocations by lower-
priority subsystems. We also study the case in which the
limited availability of the resources renders it impossible
to respect the updated output-reference for one or more of
the subsystems. In this case, we show how to relax such
references in an optimal way so that the ultimately ob-
tained inputs lead to tracking them as closely as possible.
The results are illustrated through simple examples. Ex-
ploiting the generality of the method and applying it to a
larger, more realistic case study is a subject for future work.

**Funding:** Financial support from Deutsche Forschungs-ge-
meinschaft (DFG) via grant RA 516/14-1 is gratefully ac-
knowledged.

**References**

1. B. Addad, S. Amari and J.-J. Lesage. Networked conflicting timed event graphs representation in (max,+) algebra. *Discrete Event Dynamic Systems*, 22(4):429–449, 2012.

2. X. Allamigeon, V. Bœuf and S. Gaubert. Performance evaluation of an emergency call center: tropical polynomial systems applied to timed petri nets. In *Formal Modeling and Analysis of Timed Systems (FORMATS 2015)*, Springer, 2015.

3. F. Baccelli, G. Cohen, G. J. Olsder and J.-P. Quadrat. *Synchronization and Linearity: an Algebra for Discrete Event Systems*. Wiley, 1992.

4. T. Blyth and M. Janowitz. *Residuation Theory*. Pergamon press,
1972.

5. W. M. Boussahel, S. Amari and R. Kara. Analytic evaluation of the cycle time on networked conflicting timed event graphs in the (max,+) algebra. *Discrete Event Dynamic Systems*, 26(4):561–581, 2016.

6. G. Cohen, S. Gaubert and J. P. Quadrat. Asymptotic throughput of continuous timed petri nets. In *34th IEEE Conference on Decision and Control (CDC)*, New Orleans, LA, USA, 1995.

7. G. Cohen, S. Gaubert and J. P. Quadrat. Algebraic system analysis of timed petri nets. In *Idempotency*, J. Gunawardena Ed. Collection of the Isaac Newton Institute, pages 145–170, 1998.
8. A Corrêa, A. Abbas-Turki, R. Bouyekhf and A. El Moudni. A dioid model for invariant resource sharing problems. *IEEE Transactions on Systems, Man, and Cybernetics*, 39(4):770-781, 2009.

9. B. Cottenceau, L. Hardouin and J. Trunk. A C++ toolbox to handle series for event-variant/time-variant (max,+)$\cdot$ systems. In *15th International Workshop on Discrete Event Systems (WODES'20) — to appear*.

10. L. Hardouin, B. Cottenceau, S. Lagrange and E. Le Corronc. Performance analysis of linear systems over semiring with additive inputs. In *9th International Workshop on Discrete Event Systems (WODES)*, Göteborg, Sweden, 2008.

11. L. Hardouin, B. Cottenceau, Y. Shang and J. Raisch. Control and state estimation for max-plus linear systems. *Foundations and Trends in Systems and Control*, 6(1):1-116, 2018.

12. E. Menguy, J.-L. Boimond, L. Hardouin and J.-L. Ferrier. Just-in-time control of timed event graphs: update of reference input, presence of uncontrollable input. *IEEE Transactions on Automatic Control*, 45(11):2155-2159, 2000.

13. S. Moradi, L. Hardouin and J. Raisch. Optimal control of a class of timed discrete event systems with shared resources, an approach based on the hadamard product of series in dioids. In *56th IEEE Conference on Decision and Control (CDC)*, Melbourne, Australia, 2017.

14. G. Schafaschek, S. Moradi, L. Hardouin and J. Raisch. Optimal control of timed event graphs with resource sharing and output-reference update. In *15th International Workshop on Discrete Event Systems (WODES'20) — to appear*.

15. T. J. J. van den Boom and B. De Schutter. Modelling and control of discrete event systems using switching max-plus-linear systems. *Control Engineering Practice*, 14(10):1199-1211, 2006.

## Bionotes

<figure><img src="image_15.png" /><figcaption>Germano Schafaschek</figcaption></figure>

Fachgebiet Regelungssysteme, Technische Universität Berlin, Berlin, Germany
**schafaschek@control.tu-berlin.de**

Germano Schafaschek studied Control and Automation Engineering at the Federal University of Santa Catarina (UFSC), Florianópolis, Brazil. He received a Master's degree in Automation Systems Engineering from the same university. Since 2016, he has been a teaching and research assistant at the Control Systems Group (Fachgebiet Regelungssysteme) of TU Berlin, Germany, where he also pursues his PhD in a joint (cotutelle) program with the University of Angers, France. His current research is mainly focused on modeling and control of timed discrete-event systems in tropical algebras. He is also interested in the theory of formal languages and automata, Petri nets theory, and supervisory control theory for timed and untimed discrete-event systems.

<figure><img src="image_16.png" /><figcaption>Laurent Hardouin</figcaption></figure>

Laboratoire Angevin de Recherche en Ingénierie des Systèmes, Université d'Angers, Angers, France
**laurent.hardouin@univ-angers.fr**

Laurent Hardouin received the degrees of Master and Ph.D. in Acoustic and Control from the University of Poitiers, France, in 1990 and 1993, respectively. He received the Habilitation Diriger des Recherches from the University of Angers, France, in 2004. He is currently Full Professor of Polytech Angers at the University of Angers, France. He specializes in discrete-event systems, max-plus algebra, and interval analysis with applications to computer networks, manufacturing systems, transportation systems, and robotics.

<figure><img src="image_17.png" /><figcaption>Jörg Raisch</figcaption></figure>

Fachgebiet Regelungssysteme, Technische Universität Berlin, Berlin, Germany
**raisch@control.tu-berlin.de**

Jörg Raisch studied Engineering Cybernetics at Stuttgart University and Control Systems at UMIST, Manchester, UK. He received a PhD and a Habilitation degree, both from Stuttgart University. He holds the chair for Control Systems in the EECS Department at TU Berlin, and he is also an external scientific member of the Max Planck Institute for Dynamics of Complex Technical Systems. His main research interests are hybrid and hierarchical control, distributed cooperative control, and control of timed discrete event systems in tropical algebras, with applications in chemical, medical, and power systems engineering. He was on the editorial boards of the European Journal of Control, the IEEE Transactions on Control Systems Technology, and Automatica. He serves on the editorial boards of Discrete Event Dynamic Systems and Foundations and Trends in Systems and Control. He is chair of IFAC Technical Committee 1.3 (Discrete Event and Hybrid Systems).