SLDIs: cycle time analysis and applications]Switched max-plus linear-dual inequalities: cycle time analysis and applications

[1]Davide<EMAIL_ADDRESS>
2]Jan<EMAIL_ADDRESS>
1,3]Jörg<EMAIL_ADDRESS>
[1]Control Systems Group, Technische Universität Berlin, Germany

[2]Institute of Mathematics, Czech Academy of Sciences, Prague, Czech Republic

[3]Science of Intelligence, Research Cluster of Excellence, Berlin, Germany

P-time event graphs are discrete event systems suitable for modeling processes in which tasks must be executed in predefined time windows.
Their dynamics can be represented by max-plus linear-dual inequalities (LDIs), i.e., systems of linear dynamical inequalities in the primal and dual operations of the max-plus algebra.
We define a new class of models called switched LDIs (SLDIs), which allow to switch between different modes of operation, each corresponding to a set of LDIs, according to a sequence of modes called schedule.
In this paper, we focus on the analysis of SLDIs when the considered schedule is fixed and either periodic or intermittently periodic.
We show that SLDIs can model a wide range of applications including single-robot multi-product processing networks, in which every product has different processing requirements and corresponds to a specific mode of operation.
Based on the analysis of SLDIs, we propose algorithms to compute: i. minimum and maximum cycle times for these processes, improving the time complexity of other existing approaches; ii. a complete trajectory of the robot including start-up and shut-down transients.

§ INTRODUCTION

Illustration of a flow shop with 4 machines and jobs of two different types, labeled $\wA$ and $\wB$.

Time-window constraints arise in different settings.
Typical examples from manufacturing are the bakery and the semi-conductor industries, where some processes (e.g., yeast fermentation in the former case, metal deposition in the latter) must be executed under strict temporal constraints in order to obtain the desired quality of the final product <cit.>.
In transportation, time windows can be used to specify admissible pickup and delivery times for customers <cit.>.
From the pharmaceutical domain, high-throughput screening systems are another example where, due to chemical requirements, the time allowed to elapse between two operations is restricted by lower and/or upper bounds <cit.>.

P-time event graphs (P-TEGs) are event graphs[We recall that event graphs are Petri nets in which all arcs have unitary weight and all places have exactly one upstream and one downstream transition.] in which tokens are forced to sojourn in places in predefined time windows.
Given their ability to model time-window constraints, they have been applied to solve scheduling and control problems in various types of systems including bakeries, electroplating lines, and cluster tools <cit.>.
The signal describing firing times of transitions in P-TEGs evolves – non-deterministically – according to max-plus linear-dual inequalities (LDIs), i.e., dynamical inequalities that are linear in the primal operations and in the dual operations of the max-plus algebra (see (<ref>) in Section <ref>).

Since temporal upper bound constraints can be considered as specifications that a system driven exclusively by lower time bounds (i.e., a max-plus linear system) needs to satisfy, several authors have addressed the problem of limiting the sojourn time of tokens in places from a control point of view.
This resulted in a variety of techniques; we mention for instance <cit.>, in which the authors find sufficient conditions for the control of max-plus linear systems subject to constraints using, respectively, geometric control theory, max-plus spectral theory, residuation theory, and model predictive control.
Other sufficient conditions were discovered in <cit.>.
Note that, in its most general formulation, this control problem is still open, as no necessary and sufficient condition for its solution has been found.
The reason for this can be traced to the fact that a more fundamental problem, namely, checking the existence of solutions of LDIs, has not yet been fully understood.
On the other hand, the steady-state version of the problem was solved for a large class of instances in <cit.>, exploiting the results of <cit.>.

Moreover, the simple nature of the dynamics of P-TEGs has led to a number of theoretical results regarding the analysis of their cycle time <cit.>, which is defined as the temporal difference between the occurrence of two repetitions of the same event in the system, assuming events occur in a periodic manner (for a formal definition, see Section <ref>).

Such a simple characterization comes, however, at the cost of limited modeling power.
To illustrate this, consider the example of flow shops, which are manufacturing systems consisting of a sequence of machines of unitary capacity where all the jobs (i.e., parts to be processed) must visit all the machines in the same order (see Figure <ref>).
P-TEGs are the ideal tool for representing flow shops where all the jobs are identical.
Suppose instead that jobs of different types are present, each of which requires different processing times in machines, and that the entrance order of jobs is periodic and repeats every $V\in\nat$ jobs.
An example of periodic entrance order of period $V = 2$ for the flow shop of Figure <ref> is $\wA\wB\wA\wB\wA\wB\ldots$
In this case, P-TEGs can still be adopted to model the system (this is shown formally in Proposition <ref>), but:

* the number of transitions in the resulting P-TEGs increases (linearly) with $V$, which leads to a rather high computational complexity for the cycle time analysis where large values of $V$ are considered;

* for a different entrance order of jobs, a new P-TEG must be built.

Moreover, when the number of jobs to be processed is infinite[Considering infinitely many jobs to be processed is a typical assumption in the context of continuous production systems.] and the entrance order is not periodic, no P-TEG can model the manufacturing system.

With the aim of overcoming these limitations, in this paper we introduce a new class of dynamical systems called switched max-plus linear-dual inequalities (SLDIs).
SLDIs extend the modeling power of P-TEGs by allowing to switch among different modes of operation, each corresponding to a system of LDIs.
Let us take the example of the flow shop again.
By assigning a mode of operation to each job type, we can model the manufacturing system by SLDIs in which different job entrance orders simply correspond to different schedules, i.e., sequences of modes.

A first advantage of SLDIs is thus that, with a single dynamical system, one can represent all possible entrance orders of jobs in the flow shop, including non-periodic ones.

It is worth noting that this property is not exclusive to SLDIs, as also P-time Petri nets can be utilized to model flow shops under any job order <cit.>.
In fact, there exists a strong relation between the two models (which is briefly discussed in Section <ref>).
However, in contrast to P-time Petri nets, the dynamics of SLDIs possesses another appealing feature: a switched-linear formulation in the max-plus algebra.
By exploiting the abundance of existing results in this algebraic framework (see, e.g., <cit.>), in this paper we will derive low-complexity algorithms for the cycle time computation, considering two types of schedules: periodic and intermittently periodic schedules.
In the example of the flow shop, the first type of schedules corresponds to periodic arrivals of jobs of different types in the manufacturing system (as in schedule $\wA\wB\wA\wB\wA\wB\ldots$), whereas the second one is a generalization in which the entrance order of jobs alternates among periodic and non-periodic regimes.
An example of a schedule of the second type for the flow shop of Figure <ref> is $\wA\wA\wB\wA\wB\wA\wB\ldots\wA\wB\wB\wB\wA\wB\wA\wB\wA\ldots$, which consists of an initial transient $\wA$ followed by periodic regime $\wA\wB\wA\wB\ldots$, an intermediate transient $\wB$, and the final periodic subschedule $\wB\wA\wB\wA\ldots$[In this schedule example, different decompositions in periodic and transient regimes are possible. For more details on this, we refer to Section <ref>.]
In the cycle time analysis for this kind of schedules, one is interested in finding the cycle times that can be achieved in each periodic regime.
The motivation for studying intermittently periodic schedules is two-fold:

* they are ubiquitous in applications (as discussed in Section <ref>), and

* differently from systems described by only lower time-bounds, the cycle time analysis in this class of schedules can produce non-trivial results in the presence of time-window constraints.

Here, by "non-trivial" we mean that the cycle times of the periodic subschedules in an intermittently periodic schedule may be different from those obtained by studying the periodic subschedules independently.

The present article enhances and extends the recent conference paper <cit.> in several ways.
Besides simplifying the preliminaries in Section <ref> and adding a number of simple and illustrative examples, an important contribution of this extended paper is to systematically investigate the initial conditions of P-TEGs (in Section <ref>) and their relation to SLDIs.
Two types of initial conditions are presented, loose and strict, and it is proven that P-TEGs with strict initial conditions can be represented by SLDIs but not by pure LDIs (Section <ref>).
In Section <ref>, after formally presenting SLDIs, the cycle time analysis in periodic and intermittently periodic trajectories is discussed; intermittently periodic trajectories are introduced for the first time in this extended version.
In <cit.>, the correctness of the low-complexity method for computing the cycle time in SLDIs under periodic schedules was proven using tools from automata and regular languages theory; in this paper, the proof is entirely based on algebraic arguments.
Although the initial inspiration for the algorithm was drawn from analogies between multi-precedence graphs and automata theory, the new proof relies on more established results, which hopefully makes it less arduous to read.

In Section <ref>, the analysis of the case study considered in <cit.> has been deepened further.
The case study consists of a robotic job shop example derived from <cit.>, where parts of different type are required to visit a sequence of processing stations in different order, and are transported by a single robot.
The authors of <cit.> proved that the cycle time analysis in this class of systems can be performed in strongly polynomial time complexity $\pazocal{O}(V^4n^4)$, where $V$ is the period of the entrance order of different types of parts in the system, and $n$ is the number of processing stations.
In this paper, we show that the complexity can be reduced to $\pazocal{O}(Vn^3 + n^4)$ using SLDIs.
Computational tests show that the advantage is not only theoretical, but translates into a tangibly faster cycle time analysis.
This makes our algorithm an appealing optimization subroutine for the solution of (NP-hard) cyclic scheduling problems in which the goal is to find the optimal path of the robot.
Additionally, in this paper we show how to derive a complete (intermittently periodic) trajectory of the system, consisting of a start-up transient (where parts are initially introduced into the system), a periodic regime, and a shut-down transient (in which all parts are removed from the stations).

Finally, Section <ref> provides concluding remarks, comparisons with related classes of dynamical systems, and suggestions for future work.

§.§ Notation

The set of positive, respectively non-negative, integers is denoted by $\nat$, respectively $\nato$.
The set of non-negative real numbers is denoted by $\R_{\geq 0}$.
Moreover, $\Rmax \coloneqq \R \cup \{-\infty\}$, $\Rmin \coloneqq \R\cup\{\infty\}$, and $\Rbar \coloneqq \Rmax \cup \{\infty\}=\Rmin\cup\{-\infty\}$.
If $A\in\Rbar^{n\times n}$, we will use notation $A^\sharp$ to indicate $-A^\top$.
Given $a, b \in \mathbb{Z}$ with $b \geq a$, $\dint{a, b}$ denotes the discrete interval $\{a, a + 1, a + 2, \ldots, b\}$.

§ PRELIMINARIES

In this section, some basic concepts of max-plus algebra (Section <ref>) and precedence graphs (Section <ref>) are recalled; for a more detailed discussion of those topics, we refer to <cit.>.
Sections <ref> and <ref> present the non-positive circuit weight problem (introduced in <cit.>) and max-plus linear-dual inequalities.

§.§ Max-plus algebra

The max-plus algebra operates on the set of real numbers extended with $-\infty$ and $+\infty$, and is endowed with operations $\oplus$ (addition), $\otimes$ (multiplication), $\splus$ (dual addition), and $\stimes$ (dual multiplication), defined as follows: for all $a,b\in\Rbar$,

\[
\begin{array}{rclcrcl}
a \oplus b &=& \max(a,b), &\quad& a\otimes b &=&
\begin{dcases}
a+b & \mbox{if } a,b\neq -\infty,\\
-\infty & \mbox{otherwise,}
\end{dcases}\\
a \splus b &=& \min(a,b), &\quad& a\stimes b &=&
\begin{dcases}
a+b & \mbox{if } a,b\neq +\infty,\\
+\infty & \mbox{otherwise.}
\end{dcases}
\end{array}
\]

These operations can be extended to matrices; given $A,B\in\Rbar^{m\times n}$, $C\in\Rbar^{n\times p}$, for all $i\in\dint{1,m}$, $j\in\dint{1,n}$, $h\in\dint{1,p}$,

\[
\begin{array}{rclcrcl}
(A\oplus B)_{ij} &=& A_{ij}\oplus B_{ij}, &\quad& (A\otimes C)_{ih} &=& \displaystyle\bigoplus_{k=1}^n A_{ik}\otimes C_{kh},\\
(A\splus B)_{ij} &=& A_{ij}\splus B_{ij}, &\quad& (A\stimes C)_{ih} &=& \displaystyle\bigsplus_{k=1}^n A_{ik}\stimes C_{kh}.
\end{array}
\]

When the meaning is clear from the context, we will denote the max-plus multiplication between matrices $A$ and $C$, $A\otimes C$, simply by $A C$.
The symbols $\pazocal{E}$, $\pazocal{T}$, and $E_\otimes$ denote, respectively, the neutral element for $\oplus$, $\splus$, and $\otimes$, i.e., $\pazocal{E}_{ij} = -\infty$ and $\pazocal{T}_{ij} = +\infty$ for all $i,j$, and $E_\otimes$ is a square matrix with $(E_\otimes)_{ij} = 0$ if $i=j$ and $(E_\otimes)_{ij}=-\infty$ if $i\neq j$.
Given a square matrix $A$, its $r$th power is defined recursively by $A^0 = E_\otimes$ and, for all $r\geq 1$, $A^r = A^{r-1}\otimes A$.
Moreover, the Kleene star of a matrix $A\in\Rbar^{n\times n}$ is

\[
A^* = \bigoplus_{i = 0}^{+\infty} A^i.
\]

The partial order relation $\preceq$ between two matrices $A$ and $B$ of the same size is defined elementwise: $A\preceq B$ if and only if $A_{ij} \leq B_{ij}$ for all $i,j$.
Analogously to the standard algebra, we define the max-plus trace of matrix $A\in\Rbar^{n\times n}$ by $\tr(A) = \bigoplus_{i = 1}^n A_{ii}$.
The product and dual product between scalar $\lambda\in\Rbar$ and matrix $A\in\Rbar^{m\times n}$ are given by

\[
(\lambda \otimes A)_{ij} = \lambda \otimes A_{ij},\quad (\lambda \stimes A)_{ij} = \lambda \stimes A_{ij}.
\]

If $\lambda\notin\{-\infty,+\infty\}$, the two expressions coincide.

We will therefore simply write $\lambda A$ in place of $\lambda \otimes A$ or $\lambda \stimes A$ when $\lambda\in\R$.
When $\lambda\in\R$, we indicate by $\lambda^{-1}$ the element such that $\lambda^{-1}\otimes \lambda = \lambda \otimes \lambda^{-1} = 0$; thus, in the standard algebra, $\lambda^{-1}$ coincides with $-\lambda$.
When $\lambda\in\{-\infty,+\infty\}$, $\lambda$ does not have a multiplicative inverse; nevertheless, we will use symbol $\lambda^{-1}$ to denote $-\lambda$.

§.§ Precedence graphs

A directed graph is a pair $(\nodes,\arcs)$ where $\nodes$ is a finite set of nodes and $\arcs\subseteq\nodes\times\nodes$ is the set of arcs.
A weighted directed graph is a triplet $(\nodes,\arcs,w)$, where $(\nodes,\arcs)$ is a directed graph, and $w:\arcs\rightarrow\R$ is a function that associates a weight $w((i,j))$ to each arc $(i,j)\in\arcs$ of graph $(\nodes,\arcs)$.
A sequence of $r+1$ nodes $\rho=(i_1,i_2,\ldots,i_{r+1})$, $r\geq 0$, such that $(i_j,i_{j+1})\in\arcs$ for all $j\in\dint{1,r}$ is a path of length $r$; a path $\rho$ such that $i_1 = i_{r+1}$ is called a circuit.
The weight of a path is the sum (in conventional algebra) of the weights of the arcs composing it; conventionally, the weight of a path of length $r=0$, i.e., $\rho=(i_1)$, is equal to $0$.

The precedence graph associated with matrix $\MA\in\Rmax^{n\times n}$ is the weighted directed graph $\graph(A)=(\nodes,\arcs,w)$, where $\nodes=\dint{1,n}$, and there is an arc $(j,i)\in\arcs$ of weight $w((j,i))=A_{ij}$ if and only if $A_{ij}\neq -\infty$.

We say that $\graph(A)$ is a parametric precedence graph when elements of $A$ are functions of some real parameters $\lambda_1,\ldots,\lambda_p$, i.e., $A = A(\lambda_1,\ldots,\lambda_p)$.

There are important connections between the max-plus algebra and precedence graphs.
For instance, element $(i,j)$ of the $r$th max-plus power of a matrix $A\in\Rmax^{n\times n}$, $(A^r)_{ij}$, corresponds to the maximum weight of all paths in $\graph(A)$ of length $r$ from node $j$ to node $i$.
A direct consequence is that $(A^*)_{ij}$ is equal to the largest weight of all paths (of any length) from node $j$ to $i$.
Observe that a precedence graph $\graph(A)$ does not contain circuits with positive weight if and only if $\tr(A^*) = 0$; in presence of at least one circuit with positive weight, $\tr(A^*) = \infty$.
In the following, we indicate by $\nonegset$ the set of all precedence graphs that do not contain circuits with positive weight, i.e.,

\[
\nonegset = \{ \graph(A)\ | \ \tr(A^*) = 0 \}.
\]

The following proposition will be used later to verify the existence of, and compute, trajectories satisfying time-window constraints in (switched) max-plus linear-dual inequalities.
Let $A$ be an $n\times n$ matrix with elements in $\Rmax$.
Inequality $A\otimes x \preceq x$ admits a solution $x\in \R^n$ if and only if $\zor{\graph(A)}\in\nonegset$.
In this case, any column of $A^*$ solves the inequality, i.e., $A\otimes (A^*)_{\cdot,i} \preceq (A^*)_{\cdot,i}$ for all $i\in\dint{1,n}$.

The maximum circuit mean of precedence graph $\graph(A)$, denoted by $\mbox{mcm}(A)$, is the maximum weight-over-length ratio of all circuits of positive length in the graph; this value coincides with the largest max-plus eigenvalue (the max-plus spectral radius) of $A$, i.e., the largest $\lambda\in\Rmax$ such that $A\otimes x = \lambda x$ for some vector $x$ with elements from $\Rmax$.
For a matrix of dimension $n\times n$, the maximum circuit mean can be computed through the following formula (<cit.>):

\[
\mbox{mcm}(A) = \bigoplus_{k=1}^n \tr(A^k)^{\frac{1}{k}},
\]

where $a^{\frac{1}{k}}$ (corresponding to $\frac{a}{k}$ in the standard algebra) is the $k$th max-plus root of $a\in\Rmax$; a more efficient algorithm that returns the same value in time complexity $\mathcal{O}(n\times m)$ in the worst case, where $m$ is the number of edges in $\graph(A)$, is due to Karp <cit.>.

We recall that it is possible to check whether $\graph(A)\in\nonegset$ and, when $\graph(A)\in\nonegset$, to compute $A^*$ in time $\pazocal{O}(n^3)$ in the worst case, using the Floyd-Warshall algorithm <cit.>.
In the case $\graph(A)\notin\nonegset$, computing $A^*$ is an NP-hard problem; fortunately, the algorithms presented in the next sections will never face this issue in practice.

§.§ The non-positive circuit weight problem

Given a parametric precedence graph $\graph(\MA)$, where $\MA = \MA(\lambda_1,\ldots,\lambda_p)$, the non-positive circuit weight problem (NCP) consists in characterizing the set $\solNCP{\MA} = \{(\lambda_1,\dots,\lambda_p)\in\R^p\ |\ \graph(\MA)\in\nonegset\}$ of all values of parameters $\lambda_1, \dots,\lambda_p$ for which $\graph(A)$ does not contain circuits with positive weight.
Specific classes of the NCP find applications in the analysis of periodic trajectories in max-plus dynamical systems.
An application example is shown in Section <ref>.

§.§.§ The PIC-NCP

When matrix $\MA$ has the form

\[
\MA(\lambda) = \lambda\MP \oplus \lambda^{-1}\MI \oplus \MC
\]

for arbitrary matrices $\MP,\MI,\MC\in\Rmax^{n\times n}$ (called proportional, inverse[In contrast with other notations, symbol $I$ in this paper does not indicate the identity matrix in the max-plus algebra, but an arbitrary matrix. The identity matrix is instead denoted by $E_{\otimes}$.], and constant matrix, respectively), then the problem is referred to as the proportional-inverse-constant-NCP.
In this case, $\solNCP{\lambda\MP\oplus\lambda^{-1}\MI\oplus\MC}=[\lambda_{\text{min}},\lambda_{\text{max}}]\cap\R$ is an interval, and its extreme points can be found either in weakly polynomial time using linear programming solvers such as the interior-point method, or in strongly polynomial time $\pazocal{O}(n^4)$ using Algorithm <ref> (<cit.>).
The functioning of the latter algorithm is briefly described in the following.

We remark that the PIC-NCP represents a generalization of the max-plus subeigenproblem (see <cit.>), i.e., the problem of finding a real $\lambda$ such that the inequality

\[
I \otimes x\leq \lambda x
\]

admits a solution $x\in\R^{n}$ for a given matrix $I\in\Rmax^{n\times n}$.
Indeed, the above inequality can be rewritten (by multiplying both sides by $\lambda^{-1}$) as

\[
\lambda^{-1}I \otimes x \leq x,
\]

and, from Proposition <ref>, admits a solution $x\in\R^n$ if and only if the precedence graph $\graph(\lambda^{-1}I)$ does not have circuits with positive weight; the PIC-NCP thus simplifies into the max-plus subeigenproblem when matrices $P$ and $C$ are $\mathcal{E}$.
We recall from <cit.> that the least solution of the subeigenproblem is the max-plus spectral radius of matrix $I$, i.e.,

\[
\solNCP{\lambda^{-1}I} = [\mbox{mcm}(I),+\infty) \cap \R.
\]

When matrices $P$ and $C$ are not $\mathcal{E}$, a more sophisticated approach is necessary to solve the PIC-NCP.
In particular, in Algorithm <ref> some pre-computations are first performed (lines 3-4) to simplify the problem into an equivalent PI-NCP (a PIC-NCP where matrix $C$ is $\mathcal{E}$) by redefining $P$ as $C^* \otimes P \otimes C^*$ and $I$ as $C^* \otimes I \otimes C^*$.
Then, through the for-loop of lines 5-7, a matrix $S$ is constructed such that, in every new iteration of the loop, the spectral radius of matrix $I\otimes S^*$ and the inverse of the spectral radius of matrix $P\otimes S^*$ approximate better and better $\lambda_{\textup{min}}$ and $\lambda_{\textup{max}}$, respectively.
It can be shown (see <cit.>) that after at most $\left \lfloor{\frac{n}{2}} \right \rfloor$ iterations, the two quantities converge to the desired values (line 10), i.e.,

\[
\solNCP{\lambda P \oplus \lambda^{-1}I \oplus C} = [\mbox{mcm}(I\otimes S^*),(\mbox{mcm}(P\otimes S^*))^{-1}] \cap \R.
\]

If some conditions on matrices $C$ and $S$ do not hold, the algorithm can be terminated prematurely as no $\lambda$ solving the PIC-NCP exists (lines 1-2 and 8-9).

$\MP,\MI,\MC\in \Rmax^{n\times n}$
$\Lambda_{\text{NCP}}(\lambda\MP\oplus \lambda^{-1}\MI\oplus \MC)$
$\graph(\MC)\notin \nonegset$

$\MP \leftarrow \MC^* \MP \MC^*$
$\MI \leftarrow \MC^* \MI \MC^*$
$S \leftarrow E_{\otimes}$
$k = 1$ $\left \lfloor{\frac{n}{2}} \right \rfloor$

$S\leftarrow \MP S^2 \MI \oplus \MI S^2 \MP \oplus E_{\otimes}$

$\graph(S)\notin \nonegset$

$[\mbox{mcm}(\MI S^*),(\mbox{mcm}(\MP S^*))^{-1}]\cap\R$
$\mathsf{Solve\_NCP}(\MP,\MI,\MC)$ (from <cit.>)

§.§.§ The MPIC-NCP

A natural generalization of the PIC-NCP is the multivariable PIC-NCP (MPIC-NCP), in which matrix $A$ takes the form

\[
A(\lambda_1,\dots,\lambda_q) = \bigoplus_{i=1}^q (\lambda_i P_i \oplus \lambda_i^{-1} I_i) \oplus C,
\]

for some matrices $P_i,I_i,C\in \Rmax^{n\times n}$ and parameters $\lambda_i\in\R$, for all $i\in\dint{1,q}$.

In this case, it can be shown that the problem becomes "trivially intractable" in $q$,[On the other hand, assuming that $q$ is fixed, the problem remains solvable in strongly polynomial time. The proof of this fact is out of the scope of the present article.] in the sense that the set $\solNCP{\MA}$ corresponds, in the worst case, to the solution of a system of $3^q-1$ (i.e., exponentially many) non-redundant linear inequalities (in the conventional sense) in variables $\lambda_1,\dots,\lambda_q$; in other words, $\solNCP{\MA}$ is a polytope with at most $3^q-1$ facets living in a $q$-dimensional space.
Consequently, it is unrealistic to expect to efficiently solve the MPIC-NCP, since the solution set $\solNCP{\MA}$ cannot be described in polynomial space.

Nevertheless, it is possible to verify the non-emptiness of $\solNCP{\MA}$ in (weakly) polynomial time from the following observation.
Proposition <ref> suggests that the parameters $\lambda_i$ such that $\graph(A)\in\nonegset$ are those for which the inequality

\[
\left(\bigoplus_{i=1}^q (\lambda_i P_i \oplus \lambda_i^{-1} I_i) \oplus C\right) \otimes x \preceq x
\]

admits a solution $x\in\R^{n}$.
We can rewrite the inequality above in the standard algebra as the system

\[
\left\{
\begin{array}{ccl}
\displaystyle\max_{i\in\dint{1,q},j\in\dint{1,n}} \left( (P_i)_{1j} + \lambda_i + x_j, (I_i)_{1j}-\lambda_i + x_j, C_{1j} + x_j\right) &\leq& x_1 \\
\vdots&&\\
\displaystyle\max_{i\in\dint{1,q},j\in\dint{1,n}} \left( (P_i)_{nj} + \lambda_i + x_j, (I_i)_{nj}-\lambda_i + x_j, C_{nj} + x_j\right) &\leq& x_n ,
\end{array}
\right.
\]

which is equivalent to

\begin{equation}\label{eq:linear_inequalities}
\left\{
\begin{array}{rclcr}
(P_i)_{1j} + \lambda_i + x_j &\leq& x_1 &&\quad \forall i\in\dint{1,q},j\in\dint{1,n}\\
(I_i)_{1j}-\lambda_i + x_j &\leq& x_1 &&\quad \forall i\in\dint{1,q},j\in\dint{1,n}\\
C_{1j} + x_j &\leq& x_1 &&\quad \forall j\in\dint{1,n}\\
(P_i)_{nj} + \lambda_i + x_j &\leq& x_n &&\quad \forall i\in\dint{1,q},j\in\dint{1,n}\\
(I_i)_{nj}-\lambda_i + x_j &\leq& x_n &&\quad \forall i\in\dint{1,q},j\in\dint{1,n}\\
C_{nj} + x_j &\leq& x_n &&\quad \forall j\in\dint{1,n}.
\end{array}
\right.
\end{equation}

The system above consists of at most[The inequalities corresponding to $-\infty$-elements in matrices $P_i$, $I_i$, and $C$ are automatically satisfied and can be ignored.] $(2q+1)n^2$ linear inequalities in $n+q$ real unknowns $x_1,\dots,x_n,\lambda_1,\dots,\lambda_q$.
Therefore, the non-emptiness of its solution set can be checked in polynomial time using linear programming techniques.

§.§ Max-plus linear-dual inequalities

In the following, we define max-plus linear-dual inequalities (LDIs) from a purely formal point of view.
Their application to describe the dynamics of P-time event graphs is discussed in the next section.
Let $A^0,A^1\in\Rmax^{n\times n}$, $B^0,B^1\in\Rmin^{n\times n}$, and $K\in\nat\cup\{+\infty\}$.
LDIs are systems of $(\oplus,\otimes)$- and $(\splus,\stimes)$-linear dynamical inequalities in the dater function $x:\dint{1,K}\rightarrow\R^n$ of the form

\begin{equation}\label{eq:dynamics_LDIs}
\begin{array}{rrcl}
\forall k\in\dint{1,K}, &
A^0\otimes x(k) \preceq & x(k) & \preceq B^0\stimes x(k)\\
\forall k\in\dint{1,K-1}, &
\quad\quad A^1\otimes x(k) \preceq & x(k+1) & \preceq B^1\stimes x(k)
\end{array}
\end{equation}

A finite (when $K\in\nat$) or infinite (when $K=+\infty$) trajectory $\{x(k)\}_{k\in\dint{1,K}}$ of length $K$ is consistent if it satisfies (<ref>) for all $k$.
It is often useful in practice to restrict the focus on the simple class of $1$-periodic trajectories, which are those of the form $\{\lambda^{k-1}x(1)\}_{k\in\dint{1,K}}$; in the standard algebra, 1-periodic trajectories are those that satisfy: $\forall k\in\dint{1,K}$, $i\in\dint{1,n}$, $x_i(k) = (k-1)\times \lambda + x_i(1)$.
The number $\lambda$ is called period or cycle time of the 1-periodic trajectory.

In the following, we recall how to verify the existence of 1-periodic trajectories for given LDIs.
Substituting in (<ref>) the formula $x(k) = \lambda^{k-1} x(1)$, we obtain

\[
\begin{array}{rrcl}
\forall k\in\dint{1,K}, &
A^0\otimes \lambda^{k-1} x(1) \preceq & \lambda^{k-1} x(1) & \preceq B^0\stimes \lambda^{k-1} x(1)\\
\forall k\in\dint{1,K-1}, &
\quad\quad A^1\otimes \lambda^{k-1} x(1) \preceq & \lambda^k x(1) & \preceq B^1\stimes \lambda^{k-1} x(1)
\end{array}
\]

which, after multiplying left and right hand sides of the above inequalities by $(\lambda^{k-1})^{-1}$,[Recall that, in the standard algebra, this is equivalent to subtracting everywhere by $(k-1)\times \lambda$.] simplifies to

\begin{equation}\label{eq:aux}
\begin{array}{rcl}
A^0\otimes x(1) \preceq & x(1) & \preceq B^0\stimes x(1)\\
A^1\otimes x(1) \preceq & \lambda x(1) & \preceq B^1\stimes x(1)
\end{array}
\end{equation}

We recall the following result.

Let $x,y\in\R^n$, $A,B\in\Rmax^{n\times n}$.
Then[The reader familiar with residuation theory <cit.> may note that function $f_A^\sharp(y) = A^{\sharp}\stimes y$ coincides with the residual of the function "left multiplication by $A$" $f_A(x) = A\otimes x$ (i.e., $f_A^\sharp(y)$ is the greatest $x$ that satisfies $A\otimes x\leq y$).
In the max-plus context, function $f_A^\sharp$ is often called "left division by $A$" and denoted by $f_A^\sharp(y) = A \maxldiv y$ <cit.>.
Dually, function $g_B^\flat(x) = B^\sharp \otimes x$ coincides with the dual residual of the function "left dual multiplication by $B$" $g_B(y) = B \stimes y$ (i.e., $g_B^\flat(x)$ is the least $y$ that satisfies $x \leq B\stimes y$), and is sometimes denoted by $g_B^\flat(x) = B \minldiv x$ <cit.>.]

\[
x\preceq A^\sharp \stimes y \ \Leftrightarrow \ A\otimes x\preceq y,
\]

\[
\left\{
\begin{array}{l}
A\otimes x\preceq y\\
B\otimes x\preceq y
\end{array}
\right.
\quad
\Leftrightarrow
\quad
(A\oplus B) \otimes x\preceq y.
\]

Because of Proposition <ref> we can rewrite (<ref>) as

\[
(\lambda B^{1\sharp} \oplus \lambda^{-1} A^1 \oplus A^0\oplus B^{0\sharp}) \otimes x(1) \preceq x(1),
\]

which, from Proposition <ref>, admits solution $x(1)\in\R^n$ if and only if $\graph(\lambda B^{1\sharp} \oplus \lambda^{-1} A^1 \oplus A^0\oplus B^{0\sharp})\in\nonegset$.
Note that we obtained a PIC-NCP with matrices $P = B^{1\sharp}$, $I = A^1$, and $C = A^0 \oplus B^{0\sharp}$.
Therefore, a consistent $1$-periodic trajectory exists if and only if $\solNCP{\lambda B^{1\sharp} \oplus \lambda^{-1}A^1 \oplus A^0 \oplus B^{0\sharp}} = [\lambda_{\textup{min}},\lambda_{\textup{max}}]\cap \R$ is nonempty, where $\lambda_{\textup{min}}$ and $\lambda_{\textup{max}}$ can be found in time $\pazocal{O}(n^4)$ using Algorithm <ref>.

§ P-TIME EVENT GRAPHS

An ordinary (or unweighted) P-time Petri net (P-TPN) is a 5-tuple $(\places,\transitions,\arcs,m,\iota)$, where $(\places\cup\transitions,E)$ is a directed graph in which the set of nodes is partitioned into the set of places, $\places$, and the set of transitions, $\transitions$, the set of arcs, $\arcs$, is such that $\arcs\subseteq (\places\times \transitions)\cup(\transitions\times\places)$, $m:\places\rightarrow\nato$ is a map such that $m(p)$ represents the number of tokens initially residing in place $p\in\places$ (also called initial marking of $p$), and

\[
\iota:\places\rightarrow\{[\tau^-,\tau^+]\ |\ \tau^-\in\R_{\geq 0},\tau^+\in\R_{\geq 0}\cup\{\infty\},\tau^-\leq \tau^+\}
\]

is a map that associates to every place $p\in\places$ a time interval $\iota(p)=[\tau^-_p,\tau^+_p]$.

In the following, we briefly describe the dynamics of an ordinary P-TPN[Since the functioning of P-TPNs is here reported only to present P-time event graphs, we will not delve into the nuances of weak and strong semantics for P-TPNs.
For a thorough description of different types of semantics, we invite the reader to consult <cit.>.].
A transition $t$ is enabled when either it has no upstream places or each upstream place $p$ of $t$ contains at least one token which has resided in $p$ for a time between $\tau^-_{p}$ and $\tau^+_{p}$ (extremes included).
When transition $t$ is enabled, it may fire; its firing causes one token to be removed instantaneously from each of the upstream places of $t$, and one token to be added, again instantaneously, to each of the downstream places of $t$.
If a token sojourns more than $\tau^+_{p}$ time instants in a place $p$, then the token becomes dead.

A P-time event graph (P-TEG) is an ordinary P-TPN in which every place has exactly one upstream and one downstream transition.
Let $|\transitions|=n$ be the number of transitions in a P-TEG and let $x:\dint{1,K}\rightarrow\R^n$ be a dater function of length $K\in\nat\cup\{+\infty\}$, i.e., a function such that $x_i(k)$ represents the time at which transition $t_i$ fires for the $k$th time.
Since the $(k+1)$st firing of any transition cannot occur before the $k$th, we require the dater to be a non-decreasing function, i.e., $\forall i\in\dint{1,n}$, $x_i(k+1)\geq x_i(k)$.

The evolution of the marking in a P-TEG is entirely described by its corresponding dater trajectory $\{x(k)\}_{k\in\dint{1,K}}$, and if a non-decreasing dater trajectory exists for which no token death occurs, then it is said to be consistent for the P-TEG.

It is always possible to transform a P-TEG into an equivalent one whose places have at most $1$ initial token each <cit.>.
Therefore, in the following we will only focus on P-TEGs in which the initial marking $m(p)$ is either $0$ or $1$ for each place $p\in\places$.
Under this assumption, a consistent trajectory for a given P-TEG must satisfy LDIs as in (<ref>),

where matrices $A^0,A^1\in\Rmax^{n\times n}$, $B^0,B^1\in\Rmin^{n\times n}$ are called characteristic matrices of the P-TEG, and are defined as follows.
If there exists a place $p_{ij}$ with initial marking $\mu\in\{0,1\}$, upstream transition $t_j$ and downstream transition $t_i$, then $A^\mu_{ij}=\tau^-_{p_{ij}}$ and $B^\mu_{ij}=\tau^+_{p_{ij}}$; otherwise, $A^\mu_{ij} = -\infty$ and $B^\mu_{ij} = \infty$.

Before introducing some structural properties of P-TEGs, it is useful to clarify the role of initial conditions for these dynamical systems.

§.§ Initial conditions

Depending on the P-TEG's intended application, the restrictiveness of initial conditions may vary; in the following, we introduce two alternatives.

§.§.§ Loose initial conditions

Inequalities (<ref>) suggest that $x(1)$ can assume any value in $\R^n$, as long as it satisfies

\begin{equation}\label{eq:initial_conditions}
\begin{array}{c}
A^0\otimes x(1) \preceq x(1) \preceq B^0\stimes x(1)\\
A^1\otimes x(1) \preceq B^1\stimes x(1)
\end{array}
%	\begin{array}{rcr}
%		A^0\otimes x(1) \preceq & x(1) & \preceq B^0\stimes x(1)\\
%		A^1\otimes x(1) \preceq & \phantom{x(2)} & \phantom{\preceq } B^1\stimes x(1)
%	\end{array}
\end{equation}

Note that (<ref>) does not restrict the first firing time based on the arrival times of the initial tokens in the Petri net; the arrival times of initial tokens are, in fact, not even defined.
For this reason, we say that the initial conditions of a P-TEG are loose if no other restriction other than (<ref>) applies to $x(1)$.

P-TEGs with loose initial conditions evolve entirely according to LDIs, and are suitable to model manufacturing systems operating in periodic regime, after a transient period has passed (an example is given in Section <ref>).
Another scenario where loose initial conditions may be convenient is when the time-window constraints need to be fulfilled only after the occurrence of the first events, as shown in the following example.

[Heat treatment line]
This example is adapted from <cit.>.
Consider a simple heat treatment line, schematically represented in Figure <ref>, consisting of a furnace, which performs a heat treatment, and an autonomous guided vehicle that receives processed pieces and transports them to the next stage.
Both the furnace and the vehicle have unitary capacity, i.e., they can process and transport one piece at a time, respectively.
The heat treatment must last between 2 and 3 time units, and the autonomous vehicles takes (at least) 0.5 time units both to transport a processed piece to the next stage and to travel back to the furnace.
Customers' demand imposes that the time difference between subsequent unloadings of processed pieces from the autonomous guided vehicle must not exceed 4 time units; the specification needs to be met for all pieces after the first one.
Moreover, each piece must spend at least 6 time units in the processing line, from the moment it enters the furnace to the one it is removed from the vehicle, in order to synchronize with other processing stages.
Initially, the furnace is empty and the vehicle is waiting for a piece at the furnace.
The P-TEG in Figure <ref> models the described plant; a firing of transitions $t_1$, $t_2$, and $t_3$ represents, respectively, the arrival of an unprocessed piece in the furnace, the loading of a processed piece onto the autonomous guided vehicle, and the unloading of a piece from the vehicle.

Illustration of the heat treatment line of Example <ref>.

P-TEG representing the heat treatment line.

The characteristic matrices of the P-TEG are

\[
A^0 = \begin{bmatrix}
-\infty & -\infty & -\infty \\
2 & -\infty & -\infty \\
6 & 0.5 & -\infty
\end{bmatrix},\quad
A^1 = \begin{bmatrix}
-\infty & 0 & -\infty \\
-\infty & -\infty & 0.5 \\
-\infty & -\infty & 0
\end{bmatrix},
\]

\[
B^0 = \begin{bmatrix}
+\infty & +\infty & +\infty \\
3 & +\infty & +\infty \\
+\infty & +\infty & +\infty
\end{bmatrix},\quad
B^1 = \begin{bmatrix}
+\infty & +\infty & +\infty \\
+\infty & +\infty & +\infty \\
+\infty & +\infty & 4
\end{bmatrix}.
\]

It is possible to verify that

\[
x(1) = \begin{bmatrix}
\end{bmatrix},\quad \forall k\geq 1,\ x(k+1) = 3.5 x(k)
\]

is a consistent trajectory for the P-TEG under loose initial conditions.
Observe that the first firing time of transition $t_3$ does not violate the upper bound associated to place $p_{33}$ (i.e., the place that is upstream and downstream of transition $t_3$), even though $x_3(1) = 6 > 4 = B_{33}^1$.
Indeed, the sojourn time of the initial token in place $p_{33}$ does not restrict the dynamics of the P-TEG.
This is convenient from a practical point of view, as the constraint on the processing rate must be enforced only after the first piece leaves the plant.

§.§.§ Strict initial conditions

For the considered application, it may be necessary to impose further restrictions on the initial conditions.
Here we take into account the amount of time that initial tokens have resided in places prior to the initial time $t_0\in\R$; we call this value the time tag of the token[The concept of time tags is analogous to that of lag times, defined as in <cit.>.].
Time tags can be useful, for instance, in manufacturing, to specify that some machines have already been processing a part since time $t_0-\tau$, or in transportation, to indicate that a vehicle has left a station at time $t_0-\tau$, for $\tau\geq 0$.

Let $\rho$ be a function that associates a time tag to every place with an initial token in a P-TEG.
Formally, if there is a place $p_{ij}$ with marking $m(p_{ij}) = 1$, upstream transition $t_j$, and downstream transition $t_i$, then we denote $\rho(p_{ij}) = \rho_{ij}\in\R_{\geq 0}$, otherwise $\rho(p_{ij})$ is not defined.

Then, in addition to (<ref>), the first firing time of the transitions of the P-TEG must satisfy, for all $i,j\in\dint{1,n}$,

\[
A^1_{ij} + t_0 - \rho_{ij} \leq x_i(1) \leq B^1_{ij} + t_0 - \rho_{ij};
\]

for each $i,j$, the inequality specifies that the first firing time of transition $t_i$ must not violate the time-window constraint $[A^1_{ij},B^1_{ij}]$ associated with place $p_{ij}$, considering that the initial token of this place arrived at time $t_0 - \rho_{ij}$.
In the max-plus algebra, the latter inequalities can be expressed as

\begin{equation}\label{eq:time_tags}
\underline{\Delta} \otimes t_0\tilde{e} \leq x(1) \leq \overline{\Delta} \stimes t_0\tilde{e},
\end{equation}

\[
\underline{\Delta}_{ij} = \begin{dcases}
A^1_{ij} -\rho_{ij} & \mbox{if } A^1_{ij} \neq -\infty,\\
-\infty & \mbox{otherwise},
\end{dcases}
\quad
\overline{\Delta}_{ij} = \begin{dcases}
B^1_{ij} -\rho_{ij} & \mbox{if } B^1_{ij} \neq +\infty,\\
+\infty & \mbox{otherwise},
\end{dcases}
\]

\[
\tilde{e} = \begin{bmatrix}0\\0\\\vdots\\0\end{bmatrix}\in\R^n.
\]

Note that other possible definitions for $\underline{\Delta}$ and $\overline{\Delta}$, corresponding to different requirements for the first firings of transitions, may be considered.

In general, given any $\underline{\Delta}\in\Rmax^{n\times n}$, $\overline{\Delta}\in\Rmin^{n\times n}$ such that $(\underline{\Delta},\overline{\Delta}) \neq (\pazocal{E},\pazocal{T})$, inequality (<ref>) restricts the set of consistent trajectories for a P-TEG; hence, we say that the initial conditions of a P-TEG are strict if $x(1)$ is required to satisfy them for some $(\underline{\Delta},\overline{\Delta})\neq(\pazocal{E},\pazocal{T})$.
We will refer to consistent trajectories with either loose or strict initial conditions depending if they satisfy only (<ref>) or also (<ref>).
Note that, without loss of generality, we can assume that $t_0=0$, as P-TEGs (with either loose or strict initial conditions) are time-invariant systems, i.e., if $\{x(k)\}_{k\in\dint{1,K}}$ is a consistent trajectory, then $\{t_0 \otimes x(k)\}_{k\in\dint{1,K}}$ is consistent as well for any $t_0\in\R$.
In other words, the choice of the initial time $t_0$ does not affect the dynamics of P-TEGs.

[Heat treatment line, cont.]
Consider again the P-TEG of Figure <ref>.
It is not difficult to see that, if we assign a time tag to each initial token of the P-TEG, no consistent trajectory that satisfies strict initial conditions can be found; indeed, it is not possible to fire transition $t_3$ before time $4-\rho_{33}$, for any time tag $\rho_{33}\in \R_{\geq 0}$.
So, let us modify the configuration of the initial tokens as in Figure <ref>; time tags are indicated in the figure.

P-TEG representing the heat treatment line in another initial configuration.

The interpretation is that:

* a piece is inside the heat treatment line since time $t_0 - 3$, as $\rho_{31} = 3$,

* an autonomous guided vehicle is at the unloading location with a processed piece from time $t_0$, as $\rho_{32} = 0.5 = A^1_{32}$,

* the furnace has completed the last heat treatment at time $t_0 - 0.5$, as $\rho_{12} = 0.5$, and

* the first processed piece is required to leave the heat treatment plant before time $t_0 + 3$, as $\rho_{33} = 1$.

The characteristic matrices for this example are

\[
A^0 = \begin{bmatrix}
-\infty & -\infty & -\infty \\
2 & -\infty & 0.5 \\
-\infty & -\infty & -\infty
\end{bmatrix},\quad
A^1 = \begin{bmatrix}
-\infty & 0 & -\infty \\
-\infty & -\infty & -\infty \\
6 & 0.5 & 0
\end{bmatrix},
\]

\[
B^0 = \begin{bmatrix}
+\infty & +\infty & +\infty \\
3 & +\infty & +\infty \\
+\infty & +\infty & +\infty
\end{bmatrix},\quad
B^1 = \begin{bmatrix}
+\infty & +\infty & +\infty \\
+\infty & +\infty & +\infty \\
+\infty & +\infty & 4
\end{bmatrix},
\]

and the matrices $\underline{\Delta}$ and $\overline{\Delta}$ are

\[
\underline{\Delta} = \begin{bmatrix}
-\infty & -0.5 & -\infty \\
-\infty & -\infty & -\infty \\
3 & 0 & -1
\end{bmatrix},\quad
\overline{\Delta} = \begin{bmatrix}
+\infty & +\infty & +\infty \\
+\infty & +\infty & +\infty \\
+\infty & +\infty & 3
\end{bmatrix}.
\]

Assuming that $t_0 = 0$, the following is a consistent trajectory for the P-TEG under strict initial conditions:

\[
x(1) = \begin{bmatrix}
\end{bmatrix},\quad \forall k\geq 1,\ x(k+1) = 4 x(k).
\]

Despite their usefulness in applications, strict initial conditions present an additional complexity: the inequalities describing the dynamics of of P-TEGs with strict initial conditions are not (pure) LDIs.
This means that mathematical results in LDIs can be directly applied to P-TEGs with loose but not with strict initial conditions; this will be made evident in the following section.
In Section <ref>, we will see that the dynamics of P-TEGs with strict initial conditions falls in the category of switched LDIs.

§.§ Structural properties

In this section we recall the definition of some structural properties of P-TEGs.
These properties can be equivalently stated for P-TEGs under loose or strict initial conditions.

A P-TEG is said to be consistent if it admits a consistent, non-decreasing trajectory $\{x(k)\}_{k\in\nat}$ of infinite length.
The non-decreasingness of the dater trajectory, equivalent to having $x(k+1)\succeq x(k)$ for all $k\in\dint{1,K-1}$, is a natural requirement, as the $(k+1)$st firing of a transition cannot occur before the $k$th one; because of Proposition <ref>, to restrict the evolution of the dater trajectory such that this restriction is always satisfied, it is sufficient to modify the definition of matrix $A^1$ into $A^1 \oplus E_\otimes$.

We say that a trajectory $\{x(k)\}_{k\in\nat}$ is delay-bounded if there exists a positive real number $M$ such that, for all $i,j\in\dint{1,n}$ and for all $k\in\nat$, $x_i(k)-x_j(k)<M$; a P-TEG admitting a consistent delay-bounded trajectory of the dater function is said to be boundedly consistent.
Although in consistent P-TEGs it is possible to find a marking evolution such that no time-window constraint is violated, if the stronger property of bounded consistency does not hold, any consistent, infinite trajectory will accumulate unbounded delay between the firing times of two distinct transitions.
This phenomenon is usually not desirable in manufacturing systems represented by P-TEG, where the firings of transitions represent the start or end of processes, and the $k$th product entering the system is finished when all transitions fire for the $k$th time.
Indeed, in this context it implies that the total time the $k$th product spends in the manufacturing system increases without bounds with $k$.

Analogously to LDIs, in P-TEGs we say that dater trajectories of the form $\{\lambda^{k-1}x(1)\}_{k\in\dint{1,K}}$ are 1-periodic with period $\lambda\in\R_{\geq 0}$.
Clearly, in P-TEGs with loose initial conditions, 1-periodic trajectories can be found in time complexity $\pazocal{O}(n^4)$ using Algorithm <ref>, as their evolution satisfies LDIs.
To our knowledge, no algorithm that checks whether a P-TEG is consistent has been found until now; on the other hand, bounded consistency of P-TEGs with loose initial conditions can be verified in time $\pazocal{O}(n^4)$.
This fact comes from the following result.

A P-TEG with loose initial conditions is boundedly consistent if and only if it admits a consistent 1-periodic trajectory.

On the other hand, an analogous result for the case with strict initial conditions does not hold: boundedly consistent P-TEGs with strict initial conditions may admit no 1-periodic trajectory, as shown in the following example.

Example of boundedly consistent P-TEG with strict initial conditions that admits no 1-periodic trajectory.

Using an algorithm that will be presented in Section <ref>, it can be shown that the P-TEG with strict initial conditions in Figure <ref> admits no 1-periodic trajectory.
However, assuming that $t_0 = 0$, it admits the following delay-bounded (2-periodic) trajectory:

\[
x(1) = \begin{bmatrix}
\end{bmatrix},\quad x(2) = \begin{bmatrix}
\end{bmatrix}, \quad \forall k\geq 1,\ x(k+2) = 20 x(k).
\]

Therefore, it is boundedly consistent.

The following example illustrates the discussed properties in the case of P-TEGs with loose initial conditions.

Consider the P-TEG represented in <Ref>, in which time windows are parametrized with respect to label $\wZ$; in <Ref>, values of time windows are given for $\wZ\in\{\wA,\wB,\wC\}$.
The matrices characterizing the P-TEG labeled $\wZ$ are:

\[
A^0_\wZ =
\begin{bmatrix}
-\infty & -\infty \\
0 & -\infty
\end{bmatrix},\quad
A^1_\wZ =
\begin{bmatrix}
\alpha_\wZ & -\infty \\
-\infty & \beta_\wZ
\end{bmatrix},
\]

\[
B^0_\wZ =
\begin{bmatrix}
\infty & \infty \\
\infty & \infty
\end{bmatrix},\quad
B^1_\wZ =
\begin{bmatrix}
\alpha_\wZ & \infty \\
\infty & \beta_\wZ
\end{bmatrix}.
\]

We analyze structural properties of the P-TEGs under loose initial conditions.

figureExample of P-TEG.

$\wZ$     $\alpha_\wZ$     $\beta_\wZ$
$\wA$     2     1

$\wB$     1     2

$\wC$     1     1

tableParameters for the P-TEG of <Ref>.

Since lower and upper bounds for the sojourn times of the two places with an initial token coincide, once the vector of first firing times $x_\wZ(1)$ is chosen (such that the first inequality in (<ref>) is satisfied for $k=1$, i.e., $x_{\wZ,2}(1)\geq x_{\wZ,1}(1)$), the only infinite trajectory $\{x_\wZ(k)\}_{k\in\nat}$ that is a candidate to be consistent for the P-TEG labeled $\wZ$ is deterministically given by

\[
\forall k\in\nat,\quad x_\wZ(k+1) = \begin{bmatrix}\alpha_\wZ + x_{\wZ,1}(k)\\\beta_\wZ + x_{\wZ,2}(k)\end{bmatrix}.
\]

However, for the case $\wZ=\wA$ it is easy to see that, for any valid choice of the vector of first firing times, the candidate trajectory $\{x_\wA(k)\}_{k\in\nat}$ is not consistent (as for a sufficiently large $k$, $x_{\wA,2}(k) < x_{\wA,1}(k)$, i.e., the first inequality of (<ref>) is violated
For $\wZ=\wB$, candidate trajectories $\{x_\wB(k)\}_{k\in\nat}$, despite being consistent, are not delay-bounded and result in the infinite accumulation of tokens in the place between $t_1$ and $t_2$ for $k\rightarrow\infty$.
On the other hand, $\{x_\wC(k)\}_{k\in\nat}$ is consistent and delay-bounded (in fact, it is 1-periodic with period $1$).
Thus we can conclude that the P-TEG labeled $\wA$ is not consistent, the one labeled $\wB$ is consistent but not boundedly consistent, and the one labeled $\wC$ is boundedly consistent.
Of course, we would have reached the same conclusion regarding bounded consistency by using Theorem <ref>.

§ SWITCHED MAX-PLUS LINEAR-DUAL INEQUALITIES

This section introduces the class of dynamical systems called switched max-plus linear-dual inequalities (SLDIs), and demonstrates its usefulness by means of simple examples.
In Section <ref>, the relationship between SLDIs and P-TEGs with strict initial conditions is examined.
Methods to efficiently verify the existence of specific trajectories are then presented in Sections <ref> and <ref>.

§.§ Mathematical description

We start by defining switched LDIs (SLDIs) as the natural extension of LDIs in which matrices $A^0,A^1,B^0,B^1$ may be different for all $k$.

Formally, SLDIs are a 5-tuple $\pazocal{S}=(\Sigma,A^0,A^1,B^0,B^1)$, where $\Sigma=\{\wA_1,\ldots,\wA_m\}$ is a finite alphabet whose symbols are called modes, and $A^0,A^1:\Sigma \rightarrow \Rmax^{n\times n}$, $B^0,B^1:\Sigma\rightarrow \Rmin^{n\times n}$ are functions that associate a matrix to each mode of $\Sigma$; for the sake of simplicity, given a mode $\wZ\in\Sigma$, we will write $A^0_\wZ,A^1_\wZ,B^0_\wZ,B^1_\wZ$ in place of $A^0(\wZ),A^1(\wZ),B^0(\wZ),B^1(\wZ)$, respectively.
We denote by $\Sigma^*$ and $\Sigma^\omega$ the sets of finite and infinite concatenations of modes from $\Sigma$, respectively.
A schedule $w$ is an element of $\Sigma^* \cup \Sigma^\omega$, i.e., it is either a finite or an infinite sequence of modes $w = w_1w_2\ldots w_{K}$ with $w_k\in\Sigma$ for all $k\in\dint{1,K}$, where $K\in\nat\cup\{+\infty\}$ denotes the length of schedule $w$.

The dynamics of SLDIs $\pazocal{S}$ under schedule $w\in\Sigma^*\cup\Sigma^\omega$ is expressed by the following system of inequalities:

\begin{equation}\label{eq:dynamics}
\begin{array}{rrcl}
\mbox{for all } k\in\dint{1,K},&
A^0_{w_k}\otimes x(k) \preceq & x(k) & \preceq B^0_{w_k}\stimes x(k),\\
\mbox{for all } k\in\dint{1,K-1},&
\quad\quad A^1_{w_k}\otimes x(k) \preceq & x(k+1) & \preceq B^1_{w_k}\stimes x(k),
\end{array}
\end{equation}

where function $x:\dint{1,K}\rightarrow \R^n$ is called dater of $\pazocal{S}$ associated with schedule $w$.
Term $x_i(k)$ represents the occurrence time of event $i$ associated with mode[Strictly speaking, $x_i$ is the function that associates to sequence $w_1w_2\cdots w_k$ the time of the $k$th occurrence of event $i$ (in mode $w_k$). For notational simplicity, however, we prefer to write $x(k)$ in place of $x(w_1w_2\cdots w_k)$, relying on the fact that the meaning is clear from the context.] $w_{k}$.
Similar to P-TEGs, it is natural to assume the following non-decreasingness condition for the dater of SLDIs: for all $k,h\in\dint{1,K}$, $h>k$, such that $w_k = w_h$, $x(h) \succeq x(k)$.
The implication is that events occurring during a later execution of a mode cannot occur before events that took place during an earlier execution of that mode.
Note that this does not imply that $x(k)$ is non-decreasing over $k$; this stronger condition would indeed unnecessarily limit the modeling expressiveness of SLDIs, as illustrated by the dater trajectory in Example <ref> at page ex:starving_philosophers.

For convenience, given a finite sequence of modes $v=v_1v_2\ldots v_V\in\Sigma^*$ of length $V\in\nat$ and a number $K\in\nat$, in the remainder of the paper we will denote by $v^K\in\Sigma^*$ the sequence of length $V \cdot K$ formed by concatenating sequence $v$ with itself $K$ times, i.e.,

\[
v^1 = v,\quad \forall K\geq 2,\quad v^{K} = vv^{K-1};
%v^\omega = \underbrace{vvvv\ldots}_{\mbox{$K$ times}} = v_1v_2\ldots v_V v_1v_2\ldots v_V v_1 v_2 \ldots
\]

congruently, if $K = +\infty$, $v^K\in\Sigma^\omega$ denotes an infinite concatenation of sequence $v$.

We now show possible applications of SLDIs with two simple examples.

[Heat treatment line, cont.]
Consider again the heat treatment line of Example <ref>.
Now, suppose that two types of parts can be processed in the system: part $\wA$ and part $\wB$; in this example, a schedule $w\in\Sigma^*\cup\Sigma^\omega$ represents the entrance order of parts in the heat treatment line.
As illustrated in Figure <ref>, the two parts require different heating times; pieces of type $\wA$ must be heated in the furnace for a time between 2 and 3 time units (as in Example <ref>), whereas pieces of type $\wB$ between 3 and 4 time units.
Moreover, the processing rate requirement changes depending on the type $w_k\in\{\wA,\wB\}$ of the $k$th part entering the plant: the $(k+1)$st part must be unloaded from the autonomous guided vehicle at most 4 time units after the $k$th one if $w_k=\wA$, and at most 5 time units later if $w_k=\wB$.
As in Example <ref>, we consider loose initial conditions, i.e., we suppose that the processing rate requirement needs to hold for all pieces after the first one.

Illustration of the multi-product heat treatment line of Example <ref>.

P-TEG representing the heat treatment line if only parts of type $\wB$ were to be processed. The case where only parts of type $\wA$ are to be processed is shown in Figure <ref>.

This system can be modeled by SLDIs $\pazocal{S} = (\Sigma,A^0,A^1,B^0,B^1)$, where $\Sigma = \{\wA,\wB\}$,

\[
A^0_\wA = \begin{bmatrix}
-\infty & -\infty & -\infty \\
2 & -\infty & -\infty \\
6 & 0.5 & -\infty
\end{bmatrix},\quad
A^0_\wB = \begin{bmatrix}
-\infty & -\infty & -\infty \\
3 & -\infty & -\infty \\
6 & 0.5 & -\infty
\end{bmatrix},\quad
A^1_\wA = A^1_\wB =  \begin{bmatrix}
-\infty & 0 & -\infty \\
-\infty & -\infty & 0.5 \\
-\infty & -\infty & 0
\end{bmatrix},
\]

\[
B^0_\wA = \begin{bmatrix}
+\infty & +\infty & +\infty \\
3 & +\infty & +\infty \\
+\infty & +\infty & +\infty
\end{bmatrix},\quad
B^0_\wB = \begin{bmatrix}
+\infty & +\infty & +\infty \\
4 & +\infty & +\infty \\
+\infty & +\infty & +\infty
\end{bmatrix},
\]

\[
B^1_\wA = \begin{bmatrix}
+\infty & +\infty & +\infty \\
+\infty & +\infty & +\infty \\
+\infty & +\infty & 4
\end{bmatrix},\quad
B^1_\wB = \begin{bmatrix}
+\infty & +\infty & +\infty \\
+\infty & +\infty & +\infty \\
+\infty & +\infty & 5
\end{bmatrix}.
\]

Clearly, if $w = \wA\wA\wA\ldots = \wA^K$ is a concatenation of only mode $\wA$, the dynamics of the system can be described by the P-TEG of Figure <ref>; similarly, if $w = \wB^K$, then the SLDIs are equivalent to the dynamics of the P-TEG of Figure <ref>.

In this simple example, the following trajectory satisfies all the time-window constraints, for any schedule $w\in\{\wA,\wB\}^*\cup\{\wA,\wB\}^\omega$:

\[
x(1) =
\begin{bmatrix}
\end{bmatrix},\quad \forall k\geq 1,\ x(k+1) = \begin{dcases}
3.5 x(k) & \mbox{if } w_k = \wA,\\
4 x(k) & \mbox{if } w_k = \wB.
\end{dcases}
\]

The example shows that SLDIs are capable of modeling flow shops with time-window constraints, i.e., manufacturing systems where different jobs (in this case, parts) are processed in each machine (the furnace and the autonomous guided vehicle) of the system in the same order.

[Starving philosophers problem]
We present a variant of the famous dining philosophers problem, which we call the starving philosophers problem.
There are $p\in\nat$ philosophers sitting at a table eating spaghetti; on the table, there are $p$ chopsticks, and each philosopher $i\in\dint{1,p-1}$ needs both the $i$th and the $(i+1)$st chopstick to start eating, whereas the $p$th philosopher needs the $p$th and the $1$st chopstick.
The $i$th philosopher takes $c_{ij}$ time units to grab the $j$th chopstick and $e_i$ time units to eat; philosophers are allowed to grab two chopsticks at the same time and are not forced to stop eating after $e_i$ time units.
After eating, a philosopher instantaneously puts the chopsticks on the table, so that they can be used by other philosophers.
In our version of the problem, dining can take a "macabre" turn: if the $i$th philosopher does not eat for more than $s_i$ time units, s/he will starve.
The objective of the problem is to find a dining order such that no philosopher starves.

The problem is a metaphor for an issue encountered in concurrent programming, namely, resource starvation.
Consider $p$ critical processes (the philosophers) that need to access some shared resources (the chopsticks); for safety reasons, it might be desirable to prevent some processes from not receiving the requested resources for too long.
Thus, a scheduling plan should guarantee safe operation by granting each process the permission to access the resources at the right time.

Here we suppose that there are $p = 4$ philosophers at the table, and that the following periodic dining order is imposed: initially, the second and the fourth philosophers eat (they can do so concurrently, as they do not need to share chopsticks); after that, the first philosopher eats once while, in the meantime, the third philosopher eats twice in a row; finally, the eating order repeats from the beginning.

The order in which philosophers eat before repeating the periodic sequence is referred to as the dining cycle.

Since the considered dining order is periodic, it is possible to describe all trajectories that are valid for the system by means of a P-TEG (with time tags, if we suppose that the $i$th philosopher should start eating for the first time before time $t_0+s_i$ for all $i\in\dint{1,p}$).
The P-TEG for this example is shown in Figure <ref>, where a firing of transitions $t_{s,i}$ and $t_{f,i}$ represents that the $i$th philosopher has started and finished eating for the first time in a dining cycle, and a firing of transitions $t_{s,3}'$ and $t_{f,3}'$ indicate that the third philosopher has started and finished eating for the second time in a dining cycle, respectively.
Note that the dimension of the dater function for this problem increases not only with the number of philosophers, but also with the amount of times a philosopher eats in a dining cycle; furthermore, observe that P-TEGs can represent infinite eating orders only if they are periodic.

The same system can be represented more compactly by SLDIs.
Let $\Sigma = \{\winit,\wP_1,\wP_2,\wP_3,\wP_4\}$ be the alphabet associated with the SLDIs, where $\winit$ is the auxiliary initial mode, which will be used to impose strict initial conditions on the system (strict initial conditions are analyzed in more depth in Section <ref>), and $\wP_i$ corresponds to the $i$th philosopher.
A meaningful schedule for this system is any sequence $w\in\Sigma^{K}$ such that $w_1 = \winit$ and, for all $k\in\dint{2,K}$, $w_k = \wP_{i_k}$ for some $i_k\in\dint{1,p}$.
Whereas the first mode $w_1 = \winit$ does not have physical interpretation besides mathematically characterizing the initial conditions for the system, for all $k\in\dint{2,K}$, $w_k$ describes the eating order of philosophers.
The interpretation of schedule $w$ is as follows; consider $k\in\dint{2,K}$, $w_k = \wP_i$ and $w_{k+1} = \wP_j$:

* if the $i$th and $j$th philosophers require access to the same chopstick, then philosopher $i$ will eat once before philosopher $j$;

* otherwise, the $i$th and $j$th philosophers will eat independently of each other, i.e., philosopher $i$ will start (and finish) eating either before or after or at the same time as philosopher $j$.
In this case schedules $u w_k w_{k+1} v$ and $u w_{k+1} w_k v$ are representative of the same behavior of the system[In concurrent systems theory, one would say that $u w_k w_{k+1} v$ and $u w_{k+1} w_k v$ represent the same trace <cit.>.], for $u\in\Sigma^*$ and $v\in\Sigma^*\cup\Sigma^\omega$.

A possible schedule corresponding to the chosen dining order is then given by

\[
w = \winit \zor{(\wP_2\wP_4\wP_1\wP_3\wP_3)^{\frac{K-1}{5}}}.
\]

We will design $A^0,A^1,B^0,B^1$ such that any dater function $x(k)\in\R^{p+1} = \R^5$ satisfying (<ref>) assumes the following interpretation, from which the evolution of the system can be obtained: for all $k\in\dint{2,K}$, if $w_k = \wP_i$, then $x_i(k)$ and $x_5(k)$ represent, respectively, the time at which the $i$th philosopher starts and finishes eating; therefore, assuming $w_{k+1} = \wP_j$, if both the $i$th and the $j$th philosophers require access to the $h$th chopstick, then $x_i(k)+e_i+c_{jh} \leq x_j(k+1)$ (sequential behavior), otherwise, if they do not need to share chopsticks, $x_i(k)$ could also be greater than $x_j(k+1)$ (concurrent behavior).
For all philosophers $i\in\dint{1,4}$ such that $w_k\neq \wP_i$, $x_i(k)$ is an auxiliary variable that stores the time at which the $i$th philosopher will eat next.
For all $i\in\dint{1,5}$, element $x_i(1)$ will be assigned to the initial time $t_0$, in order to manage the initial conditions (for more details, see Section <ref>).

$\displaystyle x_4(k+1)$

For example, consider a value of $k\in\dint{2,K-1}$ such that $w_k = \wP_1$; with the above interpretation, in order to represent the dynamics of the system, the dater function must satisfy

x_1(k) + e_1 ≤        []$x_5(k)$

x_5(k) + max(c_11,c_12) ≤        x_1(k+1)      ≤x_5(k) + s_1

x_5(k) + c_22  ≤       x_2(k+1)

x_5(k) + c_41  ≤        x_4(k+1)

x_2(k)  ≤       x_2(k+1)      ≤x_2(k)

x_3(k)  ≤       x_3(k+1)      ≤x_3(k)

x_4(k)  ≤       x_4(k+1)      ≤x_4(k),

where (<ref>) imposes the time between starting and finishing eating for the 1st philosopher, (<ref>) is used to force the 1st philosopher to start eating again only after s/he has grabbed once more the 1st and 2nd chopsticks but before starving, (<ref>) and (<ref>) impose the 2nd and 4th philosophers to start eating only after grabbing the chopsticks left by the 1st philosopher,
and (<ref>–<ref>) are auxiliary constraints to impose that $x_i(k+1) = x_i(k)$ for all philosophers $i\in\dint{2,4}$.
Finally, for the initial condition, we want to impose that

\[
\begin{array}{rcl}
\max(c_{11},c_{12}) + t_0 \leq &x_1(2) & \leq s_1 + t_0\\
\max(c_{22},c_{23}) + t_0 \leq &x_2(2) & \leq s_2 + t_0\\
\max(c_{33},c_{34}) + t_0 \leq &x_3(2) & \leq s_3 + t_0\\
\max(c_{44},c_{41}) + t_0 \leq &x_4(2) & \leq s_4 + t_0\\
\end{array}
\]

to make sure that philosophers start eating for the first time after grabbing the chopsticks and before starving.

In order to get the above interpretation for the dater function, the matrices for the initial mode $\winit$ can be defined as

\[
(A^0_\winit)_{ij} = (B^0_\winit)_{ij} = 0\ \forall i,j, %\quad B^1_\winit = \pazocal{T},\quad A^1_\winit = E_\otimes,
\]

\[
A^1_\winit =
\begin{bsmallmatrix}
-\infty & c_{12} & -\infty & c_{11} & -\infty\\
c_{22} & -\infty & c_{23} & -\infty & -\infty\\
-\infty & c_{33} & -\infty & c_{34} & -\infty\\
c_{41} & -\infty & c_{44} & -\infty & -\infty\\
-\infty & -\infty & -\infty & -\infty & -\infty
\end{bsmallmatrix},\quad
B^1_\winit =
\begin{bsmallmatrix}
+\infty & +\infty & +\infty & +\infty & s_1 \\
+\infty & +\infty & +\infty & +\infty & s_2 \\
+\infty & +\infty & +\infty & +\infty & s_3 \\
+\infty & +\infty & +\infty & +\infty & s_4 \\
+\infty & +\infty & +\infty & +\infty & +\infty
\end{bsmallmatrix}.
\]

For mode $\wP_1$ we define

\[
A^0_{\wP_1} =
\begin{bsmallmatrix}
-\infty & -\infty & -\infty & -\infty & -\infty \\
-\infty & -\infty & -\infty & -\infty & -\infty \\
-\infty & -\infty & -\infty & -\infty & -\infty \\
-\infty & -\infty & -\infty & -\infty & -\infty \\
e_1 & -\infty & -\infty & -\infty & -\infty
\end{bsmallmatrix},\quad
A^1_{\wP_1} =
\begin{bsmallmatrix}
0 & -\infty & -\infty & -\infty & \max(c_{11},c_{12}) \\
-\infty & 0 & -\infty & -\infty & c_{22} \\
-\infty & -\infty & 0 & -\infty & -\infty \\
-\infty & -\infty & -\infty & 0 & c_{41} \\
-\infty & -\infty & -\infty & -\infty & -\infty
\end{bsmallmatrix}
\]

\[
B^0_{\wP_1} = \pazocal{T}, \quad
B^1_{\wP_1} =
\begin{bsmallmatrix}
+\infty & +\infty & +\infty & +\infty & s_1 \\
+\infty & 0 & +\infty & +\infty & +\infty \\
+\infty & +\infty & 0 & +\infty & +\infty \\
+\infty & +\infty & +\infty & 0 & +\infty \\
+\infty & +\infty & +\infty & +\infty & +\infty
\end{bsmallmatrix};
\]

for the sake of brevity, we leave it to the reader to derive the matrices for modes $\wP_2,\wP_3,\wP_4$.

P-TEG for the starving philosophers problem.
Tokens inside a place colored black, blue, and red represent, respectively, a philosopher eating, a philosopher waiting to eat, and a chopstick being grabbed.
The time tag associated to each place with initial token is $0$.
Note that a token in the place with upstream transition $t_{f,3}$ and downstream transition $t_{s,3}'$ indicates that the third philosopher is both grabbing the third and the fourth chopstick and waiting to eat, hence the double color of this place.

Gantt chart of a possible trajectory for the starving philosophers problem. Opaque bars indicate either that a chopstick is being grabbed or that a philosopher is eating; transparent bars represent chopsticks being used by a philosopher to eat. Different colors correspond to different philosophers. The dashed line indicates the period of the trajectory.

We consider the following numerical parameters:

\[
c_{11} = 2,\ c_{12} = 3,\ e_1 = 1,\ s_1 = 10,\ c_{22} = 1,\ c_{23} = 1,\ e_2 = 2,\ s_2 = 10,
\]

\[
c_{33} = 1,\ c_{34} = 1,\ e_3 = 1,\ s_3 = 15,\ c_{44} = 2,\ c_{41} = 3,\ e_4 = 1,\ s_4 = 12.
\]

The Gantt chart of Figure <ref> represents a valid trajectory for the P-TEG[Note that the trajectory is 1-periodic for the P-TEG.] of Figure <ref> and for the SLDIs defined above, supposing that the initial time $t_0$ is equal to $0$.

The first 5 elements of the dater trajectory for the SLDIs are:

\[
x(1) = \begin{bsmallmatrix}
\end{bsmallmatrix},\
x(2) = \begin{bsmallmatrix}
\end{bsmallmatrix},\
x(3) = \begin{bsmallmatrix}
\end{bsmallmatrix},\
x(4) = \begin{bsmallmatrix}
\end{bsmallmatrix},\
x(5) = \begin{bsmallmatrix}
\end{bsmallmatrix}.
%	x(6) = \begin{bsmallmatrix}
%		14\\9\\7\\10.5\\8
%	\end{bsmallmatrix}.
\]

It is worth noting that, differently from P-TEGs, the dater function of SLDIs does not need to be non-decreasing: for instance, in this example we have

\[
x_5(4) = 7.5 \geq 6 = x_5(5),
\]

as the time in which the first philosopher ($w_4 = \wP_1$) stops eating for the first time is after the time in which the third philosopher ($w_5 = \wP_3$) stops eating for the first time.

The three main advantages of using SLDIs instead of P-TEGs for this problem are the following:

* higher computational efficiency: the dater function for the SLDIs has smaller dimension compared to the P-TEG.
As we shall see, this corresponds to lower computational complexity for analyzing trajectories of the system;

* lower modeling effort: the P-TEG in Figure <ref> can only represent the dining order specified above; to analyze a different dining order, a new P-TEG needs to be provided.
On the other hand, for the SLDIs different dining orders simply correspond to different schedules $w$;

* larger modeling expressiveness: only SLDIs are able to represent dining orders that are not periodic (with a dater function of finite dimension).

When schedule $w$ is fixed, we can extend the definition of some properties of P-TEGs to SLDIs in a natural way.
For instance, if there exists a trajectory of the dater $\{x(k)\}_{k\in\dint{1,K}}$ that satisfies (<ref>), then the trajectory is consistent for the SLDIs under schedule $w$, and we say that $w$ is a consistent schedule for the SLDIs (or that the SLDIs are consistent under schedule $w$).
Note that, different from the simple case of Example <ref>, there are SLDIs for which not all schedules admit consistent trajectories.

The definitions of delay-bounded trajectory and bounded consistency are generalized to SLDIs in a similar fashion.

The interpretation of bounded consistency of a schedule $w$ is analogous to the one of P-TEGs; when a process consisting of several tasks (the start and end of which are represented by events) is modeled by SLDIs under a schedule $w$ that is not boundedly consistent, then either the execution of every possible sequence of tasks following $w$
will lead to the violation of some time window constraints (if $w$ is not even consistent), or we will certainly observe an infinite accumulation of delay between the start or end of some tasks (if the only consistent trajectories are not delay-bounded).

§.§ SLDIs and P-TEGs with strict initial conditions

As discussed in Subsection <ref>, the dynamics of P-TEGs with strict initial conditions are not pure LDIs.
In this subsection, we prove that they can be expressed by means of SLDIs under specific types of schedules, with the immediate consequence that any property of SLDIs also holds for P-TEGs with strict initial conditions.

We want to prove that inequalities

\begin{equation}\label{eq:dynamics_PTEGs_strict}
\begin{array}{rrcl}
& \underline{\Delta}\otimes t_0\tilde{e} \preceq & x(1) & \preceq \overline{\Delta} \stimes t_0\tilde{e},\\
\forall k\in\dint{1,K}, &
A^0\otimes x(k) \preceq & x(k) & \preceq B^0\stimes x(k),\\
\forall k\in\dint{1,K-1}, &
\quad\quad A^1\otimes x(k) \preceq & x(k+1) & \preceq B^1\stimes x(k)
\end{array}
\end{equation}

can be written as SLDIs.
For this aim, let us define an auxiliary variable $x(0)\in\R^n$.
Note that the first inequality of (<ref>) is equivalent to

\[
\begin{array}{rcl}
\mathbb{E}\otimes x(0) \preceq & x(0) & \preceq \mathbb{E} \stimes x(0),\\
\underline{\Delta}\otimes x(0) \preceq & x(1) & \preceq \overline{\Delta} \stimes x(0),
\end{array}
\]

where $\mathbb{E}_{ij} = 0$ for all $i,j\in\dint{1,n}$.
Indeed, the first of the latter inequalities can be rewritten as

\[
\forall i\in\dint{1,n},\quad \max(x_1(0),\ldots,x_n(0)) \preceq x_i(0) \preceq \min(x_1(0),\ldots,x_n(0)),
\]

which admits as solution all $x(0)$ that satisfy $x_i(0) = x_j(0)$ for all $i,j\in\dint{1,n}$; therefore, solutions can be parametrized in $t_0\in\R$ as $x(0) = t_0 \tilde{e}$.
Recalling that P-TEGs (as well as SLDIs) are time-invariant systems (see Subsection <ref>), this proves that (<ref>) is equivalent to SLDIs $\pazocal{S} = (\{\winit,\wA\},A^0,A^1,B^0,B^1)$ under schedule $w = \winit\wA\wA\wA\wA\ldots = \winit\wA^{K}$ (i.e., mode $\winit$ followed by a sequence of $K$ modes $\wA$), where

\[
A^0_{\winit} = B^0_{\winit}=\mathbb{E},\quad A^1_{\winit} = \underline{\Delta},\quad B^1_{\winit} = \overline{\Delta},
\]

\[
A^0_{\wA} = A^0,\quad A^1_{\wA} = A^1,\quad B^0_{\wA} =B^0, \quad B^1_{\wA} = B^1.
\]

The following result is an immediate consequence of this fact.

The P-TEG characterized by matrices $A^0,A^1,B^0,B^1$ under strict initial conditions determined by matrices $\underline{\Delta}$ and $\overline{\Delta}$ is (boundedly) consistent if and only if schedule $w = \winit\wA^{+\infty}$ is (boundedly) consistent for the SLDIs $\pazocal{S}$ defined as above.

Although Proposition <ref> alone does not answer the question about how to verify (bounded) consistency of P-TEGs with strict initial conditions[The question seems to be related to the topic of transience bounds in max-plus linear systems (see, e.g., <cit.>).], it suggests that any result regarding SLDIs under schedules of the form $w = \winit\wA^{K}$ holds automatically for P-TEGs with strict initial conditions.

In the following, we provide an example for the application of this fact.
Let us study the existence of 1-periodic trajectories for P-TEGs with strict initial conditions.
From the above discussion, such trajectories correspond to "ultimately" 1-periodic trajectories of the form

\[
x(1),x(2)\in\R^n,\quad \forall k\in\dint{1,K-1}\quad x(k+2) = \lambda^kx(2)
\]

for SLDIs $\pazocal{S} = (\{\winit,\wA\},A^0,A^1,B^0,B^1)$ under schedule $w = \winit\wA^K$.
We proceed with a strategy similar to the one seen in Subsection <ref>: substituting formula $x(k+2) = \lambda^{k}x(2)$ for all $k\in\dint{1,K-1}$ into (<ref>), we get

\[
\begin{array}{rrcl}
& A^0_{\winit}\otimes x(1) \preceq & x(1) & \preceq B^0_\winit \stimes x(1),\\
& A^1_{\winit}\otimes x(1) \preceq & x(2) & \preceq B^1_\winit \stimes x(1),\\
\forall k\in\dint{1,K}, &
A^0_\wA\otimes \lambda^{k-1} x(2) \preceq & \lambda^{k-1} x(2) & \preceq B^0_\wA\stimes \lambda^{k-1} x(2),\\
\forall k\in\dint{1,K-1}, &
\quad\quad A^1_\wA\otimes \lambda^{k-1} x(2) \preceq & \lambda^k x(2) & \preceq B^1_\wA\stimes \lambda^{k-1} x(2);
\end{array}
\]

multiplying by $\lambda^{-k+1}$ in the third and fourth inequalities, we obtain

\[
\begin{array}{rcl}
A^0_{\winit}\otimes x(1) \preceq & x(1) & \preceq B^0_\winit \stimes x(1),\\
A^1_{\winit}\otimes x(1) \preceq & x(2) & \preceq B^1_\winit \stimes x(1),\\
A^0_\wA\otimes  x(2) \preceq &  x(2) & \preceq B^0_\wA\stimes  x(2),\\
\quad\quad A^1_\wA\otimes  x(2) \preceq & \lambda x(2) & \preceq B^1_\wA\stimes x(2).
\end{array}
\]

By defining the extended dater vector $\tilde{x} = [x^\top (1)\ \ x^\top(2)]^\top$ and using Proposition <ref>, the inequalities can be rewritten in terms of $\tilde{x}$ as

\begin{equation}\label{eq:PIC-NCP_strict}
(\lambda P \oplus \lambda^{-1} I \oplus C)\otimes \tilde{x} \preceq\tilde{x},
\end{equation}

\[
P = \begin{bmatrix}
\pazocal{E} & \pazocal{E}\\
\pazocal{E} & B^{1\sharp}_{\wA}
\end{bmatrix},\quad
I = \begin{bmatrix}
\pazocal{E} & \pazocal{E}\\
\pazocal{E} & A^1_{\wA}
\end{bmatrix},\quad
C = \begin{bmatrix}
A_\winit^0\oplus B_\winit^{0\sharp} & B_\winit^{1\sharp}\\
A^1_\winit & A_\wA^0\oplus B_\wA^{0\sharp}
\end{bmatrix}.
\]

Clearly, (<ref>) defines a PIC-NCP, whose solution can be found in time $\pazocal{O}(n^4)$ using Algorithm <ref>.
The conclusion is that periods of consistent 1-periodic trajectories for P-TEGs under strict initial conditions can be obtained in the same strongly polynomial time complexity as for P-TEGs under loose initial conditions.

§.§ Analysis of periodic schedules

In this subsection, we analyze bounded consistency and cycle times of SLDIs when schedule $w\in\Sigma^*\cup\Sigma^\omega$ is periodic, i.e., when it can be written as $w = v^K$, $K\in\nat\cup\{+\infty\}$, and $v=v_1\cdots v_V\in\Sigma^*$ is a finite subschedule of length $V$.
We define $v$-periodic trajectories of period $\lambda\in\R_{\geq 0}$ for SLDIs under schedule $w=v^K$ as those dater trajectories that, for all $k\in\dint{1,K-1}$, $h\in\dint{1,V}$, satisfy

\[
x(Vk + h) = \lambda x(V(k-1) + h);
\]

$\solSLDI$ denotes the set of all periods (or cycle times) $\lambda$ for which there exists a consistent $v$-periodic trajectory.
Their relationship with 1-periodic trajectories in P-TEGs is illustrated in the following example.

Let us analyze the SLDIs $\pazocal{S}$, with $\Sigma=\{\wA,\wB,\wC\}$, and $A^0_\wZ,A^1_\wZ,B^0_\wZ,B^1_\wZ$ defined as in Example <ref>; now label $\wZ\in\Sigma$ is to be interpreted as a mode.
Thus, for each event $k$, the dynamics of the SLDIs may switch among those specified by the P-TEGs labeled $\wA$, $\wB$, and $\wC$.
We consider periodic schedules $(\wA\wC)^K$ and $(\wA\wB)^K$; observe that for $w=v^K$, with $v\in\{\wA\wC,\wA\wB\}$ (i.e., $v_1=\wA$ and $v_2=\wC$ or $v_2=\wB$), the SLDIs following $w$ can be written as:

\begin{equation}\label{eq:example_1}
\begin{array}{lrcl}
\forall k\in\dint{1,K},&A^0_{v_1}\otimes x(2(k-1)+1) \preceq & x(2(k-1)+1) & \preceq B^0_{v_1}\stimes x(2(k-1)+1),\\
\forall k\in\dint{1,K},&A^1_{v_1}\otimes x(2(k-1)+1) \preceq & x(2(k-1)+2) & \preceq B^1_{v_1}\stimes x(2(k-1)+1),\\
\forall k\in\dint{1,K},&A^0_{v_2}\otimes x(2(k-1)+2) \preceq & x(2(k-1)+2) & \preceq B^0_{v_2}\stimes x(2(k-1)+2),\\
\forall k\in\dint{1,K-1},&A^1_{v_2}\otimes x(2(k-1)+2) \preceq & x(2k+1) & \preceq B^1_{v_2}\stimes x(2(k-1)+2).
\end{array}
\end{equation}

By defining $\tilde{x}(k) = [x^\top(2(k-1)+1),x^\top(2(k-1)+2)]^\top$, the above set of inequalities can be rewritten as LDIs:

∀k∈1,K,      A^0_v
⊗x̃(k) ≼      x̃(k)       ≼B^0_v x̃(k)

∀k∈1,K-1,     A^1_v ⊗x̃(k) ≼x̃(k+1) ≼B^1_v x̃(k)

\[
A^0_v = \begin{bmatrix}
A^0_{v_1} & \pazocal{E} \\
A^1_{v_1} & A^0_{v_2}
\end{bmatrix}, \quad
A^1_v = \begin{bmatrix}
\pazocal{E} & A^1_{v_2} \\
\pazocal{E} & \pazocal{E}
\end{bmatrix},
\]

\[
B^0_v = \begin{bmatrix}
B^0_{v_1} & \pazocal{T} \\
B^1_{v_1} & B^0_{v_2}
\end{bmatrix},\quad
B^1_v = \begin{bmatrix}
\pazocal{T} & B^1_{v_2} \\
\pazocal{T} & \pazocal{T}
\end{bmatrix}.
\]

To see the equivalence of (<ref>) and (<ref>), observe that the second block of (<ref>) reads

\[
\begin{array}{rcl}
A_{v_1}^1 \otimes x(2(k-1)+1) \oplus \!\! & A_{v_2}^0 \otimes x(2(k-1)+2)  & \\ & \preceq x(2(k-1)+2) \preceq & \\ & B_{v_1}^1 \stimes x(2(k-1)+1) \splus & \!\! B_{v_2}^0 \stimes x(2(k-1)+1).
\end{array}
\]

From this transformation, we can easily conclude that $\pazocal{S}$ is boundedly consistent under $v^{+\infty}$ if and only if the LDIs with characteristic matrices $A^0_v,A^1_v,B^0_v,B^1_v$ are boundedly consistent, and that all consistent $v$-periodic trajectories of $\pazocal{S}$ coincide with consistent 1-periodic trajectories of the LDIs; hence, using Algorithm <ref> we obtain

\[
\solSLDI[\wA\wC] =
\solNCP{\lambda B^{1\sharp}_{\wA\wC}\oplus \lambda^{-1} A^1_{\wA\wC}\oplus A^0_{\wA\wC}\oplus B^{0\sharp}_{\wA\wC}} = \emptyset,
%\solPTEG[A^0_{\wA\wC}][A^1_{\wA\wC}][B^0_{\wA\wC}][B^1_{\wA\wC}] = \emptyset,
\]

\[
\solSLDI[\wA\wB] =
\solNCP{\lambda B^{1\sharp}_{\wA\wB} \oplus \lambda^{-1}A^1_{\wA\wB} \oplus A^0_{\wA\wB}\oplus B^{0\sharp}_{\wA\wB}} = [3,3].
%\solPTEG[A^0_{\wA\wB}][A^1_{\wA\wB}][B^0_{\wA\wB}][B^1_{\wA\wB}] = [3,3].
\]

It is worth noting that, although P-TEGs labeled $\wA$ and $\wB$ are not boundedly consistent, the SLDIs under schedule $(\wA\wB)^{+\infty}$ are.
Thus, in general it is not possible to infer bounded consistency of SLDIs under a fixed schedule $w$ solely based on the analysis of each mode appearing in $w$.

By generalizing the procedure shown in Example <ref>, we can derive the following proposition through some algebraic manipulations (to set up equivalent LDIs) and applying Theorem <ref> (for a formal proof, see Appendix <ref>).

SLDIs $\pazocal{S}$ are boundedly consistent under schedule $w=v^{+\infty}$ if and only if they admit a $v$-periodic trajectory.
Moreover, set $\solSLDI$ coincides with $\solPIC[\MP_v][\MI_v][\MC_v]$, where

\[
\lambda\MP_v \oplus \lambda^{-1}\MI_v \oplus \MC_v =
\begin{bmatrix}
C_1 & P_{1} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \cdots & \pazocal{E} & \lambda^{-1}I_{V}\\
I_{1} & C_{2} & P_{2} & \pazocal{E} & \pazocal{E} & \cdots & \pazocal{E} & \pazocal{E}\\
\pazocal{E} & I_{2} & C_{3} & P_{3} & \pazocal{E} & \cdots & \pazocal{E} & \pazocal{E}\\
\pazocal{E} & \pazocal{E} & I_{3} & C_{4} & P_{4} & \cdots & \pazocal{E} & \pazocal{E}\\
\pazocal{E} & \pazocal{E} & \pazocal{E} & I_{4} & C_{5} & \cdots & \pazocal{E} & \pazocal{E}\\
\vdots & \vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\
\pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \cdots & C_{{V-1}} & P_{{V-1}}\\
\lambda P_{V} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \cdots & I_{{V-1}} & C_{V}
\end{bmatrix} \in\Rmax^{Vn\times Vn},
\]

$P_h = B_{v_h}^{1\sharp}$, $I_h = A_{v_h}^1$, and $C_h = A_{v_h}^0\oplus B_{v_h}^{0\sharp}$ for all $h\in\dint{1,V}$.

Proposition <ref> directly provides an algorithm to compute the minimum and maximum cycle times of SLDIs under a fixed periodic schedule.
Indeed, these values come from solving the NCP for the parametric precedence graph $\graph(\lambda\MP_v\oplus\lambda^{-1}\MI_v\oplus\MC_v)$.
However, this approach results in a slow (although strongly polynomial time) algorithm when the length of subschedule $v$ is large; indeed, its time complexity is $\pazocal{O}((Vn)^4) = \pazocal{O}(V^4n^4)$, as the considered precedence graph has $Vn$ nodes.

To speed up the computation of $\solSLDI$, we may note the following fact: the longer subschedule $v$ is, the larger is the number of $-\infty$'s compared to real numbers in $\lambda\MP_v\oplus\lambda^{-1}\MI_v\oplus\MC_v$.
In other words, the matrix becomes sparser and sparser with larger values of $V$.
Moreover, the real entries of the matrix have a recognizable pattern.
The following theorem, proven in Appendix <ref>, exploits this observation, achieving time complexity $\pazocal{O}(Vn^3+n^4)$ for computing the set $\solSLDI$.
The resulting complexity is thus linear in the length of subschedule $v$.

Precedence graph $\graph(\lambda \MP_v \oplus \lambda^{-1}\MI_v \oplus \MC_v)$ does not contain circuits with positive weight if and only if the following conditions hold:

*  for all $h\in\dint{1,V}$, $\graph(C_{h})\in\nonegset$;

*  for all $h\in\dint{1,V-1}$, $\graph(\mathbb{C}^{P}_h)\in\nonegset$ and $\graph(\mathbb{C}^{I}_{h+1})\in\nonegset$, where

\[\def\arraystretch{1.5}
\begin{array}{ll}
\forall h\in\dint{1,V-1}, \quad & \mathbb{C}^{P}_h = \mathbb{P}_h(\mathbb{P}_{h+1}(\cdots(\mathbb{P}_{V-1}\mathbb{I}_{V-1})^*\cdots)^*\mathbb{I}_{h+1})^*\mathbb{I}_{h},\\
\forall h\in\dint{2,V}, &\mathbb{C}^{I}_h = \mathbb{I}_h(\mathbb{I}_{h-1}(\cdots(\mathbb{I}_{2}\mathbb{P}_{2})^*\cdots)^*\mathbb{P}_{h-1})^*\mathbb{P}_{h},\\
\forall h\in\dint{1,V},& \mathbb{P}_h = C_{h}^*P_{h}C_{{h+1}}^*, \quad\quad \mathbb{I}_h = C_{{h+1}}^*I_{h}C_{h}^*,\\
& C_{V+1} = C_1;
\end{array}
\]

*  $\lambda\in\solPIC[\mathbb{M}^P][\mathbb{M}^I][\mathbb{M}^C]$, where

\[\def\arraystretch{1.5}
\begin{array}{rcl}
\mathbb{M}^P &=& \mathbb{P}_1(\mathbb{C}^{P}_2)^*\mathbb{P}_{2}(\mathbb{C}^{P}_{3})^*\cdots(\mathbb{C}^{P}_{V-1})^*\mathbb{P}_{V-1} \mathbb{P}_V,\\
\mathbb{M}^I &=&\mathbb{I}_V(\mathbb{C}^{I}_{V-1})^*\mathbb{I}_{V-1}(\mathbb{C}^{I}_{V-2})^*\cdots(\mathbb{C}^{I}_{2})^*\mathbb{I}_2\mathbb{I}_1,\\
\mathbb{M}^C &=& \mathbb{C}^{P}_1\oplus \mathbb{C}^{I}_V.
\end{array}
\]

The time complexity is analyzed as follows.
Item <ref> from Theorem <ref> requires to check the existence of circuits with positive weight in $V$ precedence graphs consisting of $n$ nodes each; since each verification takes time $\pazocal{O}(n^3)$, all operations in item <ref> are computed in time $\pazocal{O}(Vn^3)$.
As for item <ref>, since $\mathbb{C}^P_h = \mathbb{P}_h(\mathbb{C}^P_{h+1})^* \mathbb{I}_h$ and $\mathbb{C}^I_h = \mathbb{I}_h (\mathbb{C}^I_{h-1})^* \mathbb{P}_h$, there are $\pazocal{O}(V)$ multiplications and Kleene star operations to be performed, each of which requires $\pazocal{O}(n^3)$ operations; the total computational time is thus $\pazocal{O}(Vn^3)$.
In item <ref>, $\mathbb{M}^P$, $\mathbb{M}^I$, and $\mathbb{M}^C$ can be obtained performing $\pazocal{O}(V)$ multiplications and Kleene star operations and $\pazocal{O}(1)$ additions on $n\times n$ matrices; finally, set $\solPIC[\mathbb{M}^P][\mathbb{M}^I][\mathbb{M}^C]$ is computable in time $\pazocal{O}(n^4)$ using Algorithm <ref>.

The formulas of Theorem <ref> generalize those found in <cit.> for the throughput evaluation in max-plus automata (or heap models).
The formula in <cit.> can indeed be recovered from Theorem <ref> considering the special case when $P_h = C_h = \pazocal{E}$ for all $h$, i.e., when no upper bound constraints or relations between $x_i(k)$ and $x_j(k)$ for all $i,j,k$ exist; in order to do so, observe that in this particular case Algorithm <ref> simplifies significantly, see <cit.>.

§.§ Analysis of intermittently periodic schedules

We conclude this section with the analysis of particular trajectories of SLDIs with intermittently periodic schedules, i.e., schedules that can be factorized in the form

\begin{equation}\label{eq:definition_intermittently_periodic_schedule}
w = u_0 v_1^{m_1} u_1 v_2^{m_2} u_2 \cdots v_q^{m_q}u_{q},
\end{equation}

* $u_0,\ldots,u_{q},v_1,\ldots,v_{q}$ are finite subschedules of lengths $U_0,\ldots,U_q\in\nato$ and $V_1,\ldots,V_{q}\in\nat$, respectively,

* $2\leq m_1,\ldots,m_{q-1}<+\infty$,

* $m_q$ is either an element of $\nat$ or $+\infty$; in the second case, $u_q$ is the empty string (of length $U_q=0$) and the schedule is called ultimately periodic.

We call $u_0,\ldots,u_q$ the transient subschedules and $v_1,\ldots,v_q$ the periodic subschedules of the schedule $w$.
Observe that the factorization of an intermittently periodic schedule into transient and periodic subschedules may be not unique; for example, schedule $w = \wA\wA\wB\wA\wB\wA$ can be factorized into $w = \wA (\wA\wB)^2 \wA$ ($u_0=\wA$, $v_1=\wA\wB$, $u_1 = \wA$, $m_1=2$), into $w = \wA \wA (\wB\wA)^2$ ($u_0 = \wA\wA$, $v_1 = \wB\wA$, $m_1 = 2$), or even into $w = (\wA)^2 (\wB\wA)^2$ ($U_0 = U_1 = U_2 = 0$, $v_1 = \wA$, $v_2 = \wB\wA$, $m_1=m_2=2$).
In the reminder of the paper, to unequivocally indicate the intended schedule factorization into periodic and transient subschedules, we adopt the practice of writing explicitly exponents $m_h$ that elevate periodic subschedules $v_h$, and of writing extensively transient subschedules $u_h$ (even when $u_h$ could be written as a concatenation of a sequence of modes).

The interpretation of intermittently periodic schedules in systems modeled by SLDIs is as follows: after the start-up of the system ($u_0$), a number of operations are executed cyclically ($v_1^{m_1}$), after which the system is re-initialized ($u_1$) before starting a new sequence of cyclical tasks ($v_2^{m_2}$), and so on; finally, after a finite number ($q$) of alternations between transient and cyclic working regimes, the system is either shut down ($u_q$) if $m_q\in\nat$ or works in periodic regime forever if $m_q = +\infty$.

In the reminder of the paper, we let $K_h = U_0+\sum_{j = 1}^{h} \left(m_jV_j+U_j\right)$ for all $h\in\dint{0,q}$.
The objective of this section is to show that trajectories with important practical relevance under intermittently periodic schedules can be efficiently analyzed in SLDIs.
Namely, we study the existence of intermittently periodic trajectories, that is, trajectories of the dater function $\{x(k)\}_{k\in\dint{1,K_q}}$ such that

\[
\zor{\{x(k)\}_{k\in\dint{K_{h-1}+1,K_{h-1} + m_{h}V_{h}}}}
\]

are $v_h$-periodic trajectories of period $\lambda_h$ for all $h\in\dint{1,q}$.
In other words, for all $h\in\dint{1,q}$, $j\in\dint{1,m_h-1}$, $k\in\dint{1,V_h}$, an intermittently periodic trajectory satisfies, for some $\lambda_h\in\mathbb{R}_{\geq 0}$,

\begin{equation}\label{eq:intermittently_periodic}
\zor{x\left(K_{h-1}+ j V_h + k\right) = \lambda_{h}x\left(K_{h-1}+(j-1)V_h+k\right).}
\end{equation}

Intermittently periodic trajectories in which $m_q = +\infty$ are referred to as ultimately periodic trajectories.

Intermittently periodic trajectories generalize $v$-periodic trajectories, as they are $v_h$-periodic in each sequence of cyclical tasks $v_h^{m_h}$.

Note that the definition of intermittently periodic trajectory depends on the specific factorization of schedule $w$ into transient ($u_h$) and periodic ($v_h$) subschedules.
For instance, let $w = \wA\wA\wB\wA\wB\wA$.
A trajectory $\{x(k)\}_{k\in\dint{1,6}}$ for schedule $w$ factorized as $\wA(\wA\wB)^2\wA$ is intermittently periodic if it satisfies, for some $\lambda_1\in\R_{\geq 0}$,

\[
\zor{x(4) = \lambda_1 x(2),\quad x(5) = \lambda_1 x(3).}
\]

Considering the factorization $w = \wA \wA (\wB\wA)^2$, the trajectory is intermittently periodic if, for some $\lambda_1\in\R_{\geq 0}$,

\[
\zor{x(5) = \lambda_1 x(3),\quad x(6) = \lambda_1 x(4).}
\]

According to factorization $w = (\wA)^2 (\wB\wA)^2$, instead, the trajectory is intermittently periodic if, for some $\lambda_1,\lambda_2 \in\R_{\geq 0}$,

\[
\zor{x(2) = \lambda_1 x(1),\quad x(5) = \lambda_2 x(3),\quad x(6) = \lambda_2 x(4).}
\]

Trajectories of this type appear frequently in applications.
Typical examples are batch manufacturing systems, where each batch is processed in a periodic workflow, but switching between different batches leads to pauses and irregular transients (see, e.g., <cit.>).
Urban railway systems also operate on a similar principle, with trains arriving at stations in a periodic manner during peak and off-peak hours, although the period may vary based on the time of day.

Moreover, note that, as shown in Subsection <ref>, $1$-periodic trajectories of P-TEGs with strict initial conditions correspond to a particular case of ultimately periodic trajectories of SLDIs, in which $q=1$ and $U_0 = 1$.

This example shows how to transform the periods of finding intermittently periodic trajectories into an MPIC-NCP.
We consider again the SLDIs of Example <ref> under the intermittently periodic schedule

\[
w = \wA (\wC)^{m_1} \wB
\]

for some $m_1\geq 2$.
The inequalities corresponding to schedule $w$ are: for all $k\in\dint{1,m_1}$,

\begin{equation}\label{eq:example_intermittently}
\begin{array}{rcl}
A_{\wA}^0\otimes x(1) \leq & x(1) & \leq B_{\wA}^0\stimes x(1)\\
A_{\wA}^1\otimes x(1) \leq & x(2) & \leq B_{\wA}^1\stimes x(1)\\
A_{\wC}^0\otimes x(k+1) \leq & x(k+1) & \leq B_{\wC}^0\stimes x(k+1)\\
A_{\wC}^1\otimes x(k+1) \leq & x(k+2) & \leq B_{\wC}^1\stimes x(k+1)\\
A_{\wB}^0\otimes x(m_1+2) \leq & x(m_1+2) & \leq B_{\wB}^0\stimes x(m_1+2).
\end{array}
\end{equation}

To analyze the existence of intermittently periodic trajectories, we substitute in (<ref>), for all $k\in\dint{1,m_1-1}$, $x(k+2) = \lambda_1^k x(2)$, obtaining: for all $k\in\dint{1,m_1}$,

\begin{equation}\label{eq:example_intermittently_trajectory}
\begin{array}{rcl}
A_{\wA}^0\otimes x(1) \leq & x(1) & \leq B_{\wA}^0\stimes x(1)\\
A_{\wA}^1\otimes x(1) \leq & x(2) & \leq B_{\wA}^1\stimes x(1)\\
A_{\wC}^0\otimes \cancel{\lambda_1^{k-1}} x(2) \leq & \cancel{\lambda_1^{k-1}} x(2) & \leq B_{\wC}^0\stimes \cancel{\lambda_1^{k-1}} x(2)\\
A_{\wC}^1\otimes \cancel{\lambda_1^{k-1}} x(2) \leq &\lambda_1^{\cancel{k}}  x(2) & \leq B_{\wC}^1\stimes\cancel{\lambda_1^{k-1}}  x(2)\\
A_{\wC}^1\otimes \lambda_1^{m_1-1} x(2) \leq & x(m_1+2) & \leq B_{\wC}^1\stimes\lambda_1^{m_1-1}  x(2)\\
A_{\wB}^0\otimes x(m_1+2) \leq & x(m_1+2) & \leq B_{\wB}^0\stimes x(m_1+2).
\end{array}
\end{equation}

It is possible to get rid of the term $\lambda_1^{m_1-1}$ in the penultimate inequalities by performing a change of variable.
Let $\xi:\dint{1,3}\rightarrow \R^2$ be defined by

\[
\xi(k) = \begin{dcases}
x(k) & \mbox{if } k\in\{1,2\},\\
\lambda_1^{-(m_1-1)} x(m_1+2) & \mbox{if } k=3.
\end{dcases}
\]

By substituting $\xi$ into (<ref>), we obtain

\[
\begin{array}{rcl}
A_{\wA}^0\otimes \xi(1) \leq & \xi(1) & \leq B_{\wA}^0\stimes \xi(1)\\
A_{\wA}^1\otimes \xi(1) \leq & \xi(2) & \leq B_{\wA}^1\stimes \xi(1)\\
A_{\wC}^0\otimes \xi(2) \leq & \xi(2) & \leq B_{\wC}^0\stimes \xi(2)\\
A_{\wC}^1\otimes \xi(2) \leq & \lambda_1 \xi(2) & \leq B_{\wC}^1\stimes\xi(2)\\
A_{\wC}^1\otimes \cancel{\lambda_1^{m_1-1}} \xi(2) \leq & \cancel{\lambda_1^{m_1-1}} \xi(3) & \leq B_{\wC}^1 \stimes \cancel{\lambda_1^{m_1-1}}  \xi(2)\\
A_{\wB}^0\otimes \cancel{\lambda_1^{m_1-1}}\xi(3) \leq &\cancel{\lambda_1^{m_1-1}} \xi(3) & \leq B_{\wB}^0\stimes\cancel{\lambda_1^{m_1-1}} \xi(3).
\end{array}
\]

Finally, by rewriting the inequalities in terms of the extended vector $[\xi^\top(1),\ \xi^{\top}(2),\ \xi^{\top}(3)]^\top$ and using Proposition <ref>, we can conclude that the set of $\lambda_1$'s for which the SLDIs admit an intermittent periodic trajectory under schedule $w$ coincides with the solution set $\solNCP{\lambda_1 P \oplus \lambda_1^{-1} I \oplus C}$ of the PIC-NCP defined by matrices

\[
P = \begin{bmatrix}
\mathcal{E} & \mathcal{E} & \mathcal{E} \\
\mathcal{E} & P_{\wC} & \mathcal{E} \\
\mathcal{E} & \mathcal{E} & \mathcal{E}
\end{bmatrix},\quad
I = \begin{bmatrix}
\mathcal{E} & \mathcal{E} & \mathcal{E} \\
\mathcal{E} & I_{\wC} & \mathcal{E} \\
\mathcal{E} & \mathcal{E} & \mathcal{E}
\end{bmatrix},\quad
C = \begin{bmatrix}
C_{\wA} & P_{\wA} & \mathcal{E} \\
I_{\wA} & C_{\wC} & P_{\wC} \\
\mathcal{E} & I_{\wC} & C_{\wB}
\end{bmatrix},
\]

where $P_\wZ = B_{\wZ}^{1\sharp}$, $I_\wZ = A^1_\wZ$, $C_\wZ = A^0_\wZ \oplus B^{0\sharp}_\wZ$ for all $\wZ\in\{\wA,\wB,\wC\}$.
Using Algorithm <ref> we can compute

\[
\solNCP{\lambda_1 P \oplus \lambda_1^{-1} I \oplus C} = [1,1].
\]

In this simple example, the set of admissible periods coincides with $\solSLDI[\wC]$; at a superficial glance one could think that this is a general fact, i.e., that for any intermittently periodic schedule of the form (<ref>), the set of valid periods $\lambda_h$ defined as in (<ref>) is simply $\solSLDI[v_h]$, for all $h\in\dint{1,q}$.
This is however not the case, as shown in the following example.

[starving philosophers problem, cont.]
We analyze the existence of intermittently and ultimately periodic trajectories for Example <ref> under schedule

\[
w = \winit (\wP_1\wP_1\wP_3\wP_2\wP_4)^{m_1} \wP_1\wP_3\wP_2\wP_4 (\wP_2\wP_4\wP_1\wP_3\wP_3)^{m_2},
\]

where $m_1\in\nat$ and $m_2 = +\infty$.

For the first $m_1$ dining cycles, schedule $w$ forces the first philosopher to eat twice in a row simultaneously with the third philosopher, who eats once, after which it is the turn of philosophers $2$ and $4$ to eat; the subsequent dining cycle is identical to the previous $m_1$ cycles except that the $1$st philosopher eats only once; thereafter the dining order is the one from Exercise <ref>.
Through computations analogous to those seen in the previous example, we can show that all periods $\lambda_1$ and $\lambda_2$ (corresponding to the two periodic subschedules $v_1=\wP_1\wP_1\wP_3\wP_2\wP_4$ and $v_2=\wP_2\wP_4\wP_1\wP_3\wP_3$ in $w$) of consistent intermittently periodic trajectories are those in $\solNCP{A(\lambda_1,\lambda_2)} = \solNCP{\lambda_1P_1 \oplus \lambda_1^{-1}I_1 \oplus \lambda_2 P_2 \oplus \lambda_2^{-1}I_2 \oplus C}$, where

\begin{equation}\label{eq:intermittent_periodic_matrix}
\scriptstyle A(\lambda_1,\lambda_2) =
\begin{bsmallmatrix}
\phantom{\lambda}\tikzmark{leftdot} C_\winit \tikzmark{rightdot}\phantom{\lambda} & P_\winit & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E}\\
I_\winit & \tikzmark{left} C_{\wP_1} & P_{\wP_1} & \pazocal{E} & \pazocal{E} & \lambda_1^{-1}I_{\wP_4} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E}\\
\pazocal{E} & I_{\wP_1} & C_{\wP_1} & P_{\wP_1} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E}& \pazocal{E} \\
\pazocal{E} & \pazocal{E} & I_{\wP_1} & C_{\wP_3} & P_{\wP_3} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E}& \pazocal{E} \\
\pazocal{E} & \pazocal{E} & \pazocal{E} & I_{\wP_3} & C_{\wP_2} & P_{\wP_2} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E}& \pazocal{E} \\
\pazocal{E} & \lambda_1P_{\wP_4} & \pazocal{E} & \pazocal{E} & I_{\wP_2} & C_{\wP_4} \tikzmark{right} & P_{\wP_4} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E}\\
\pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & I_{\wP_4} & \phantom{\lambda}\tikzmark{leftdot1} C_{\wP_1}\phantom{\lambda} & P_{\wP_1} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E}\\
\pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & I_{\wP_1} & C_{\wP_3} & P_{\wP_3} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E}\\
\pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & I_{\wP_3} & C_{\wP_2} & P_{\wP_2} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E}& \pazocal{E} \\
\pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & I_{\wP_2} &\phantom{\lambda} C_{\wP_4} \tikzmark{rightdot1}\phantom{\lambda} & P_{\wP_4} & \pazocal{E} & \pazocal{E} & \pazocal{E}& \pazocal{E} \\
\pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & I_{\wP_4} & \tikzmark{left1} C_{\wP_2} & P_{\wP_2} & \pazocal{E} & \pazocal{E} & \lambda_2^{-1}I_{\wP_3} \\
\pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & I_{\wP_2} & C_{\wP_4} & P_{\wP_4} & \pazocal{E} & \pazocal{E} \\
\pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & I_{\wP_4} & C_{\wP_1} & P_{\wP_1} & \pazocal{E} \\
\pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & I_{\wP_{1}} & C_{\wP_3} & P_{\wP_3} \\
\pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \lambda_2 P_{\wP_3} & \pazocal{E} & \pazocal{E} & I_{\wP_{3}} & C_{\wP_3} \tikzmark{right1}
\end{bsmallmatrix},
\end{equation}

$P_\wZ = B_\wZ^{1\sharp}$, $I_\wZ=A_\wZ^1$, and $C_\wZ = A_\wZ^0\oplus B_\wZ^{0\sharp}$ for all $\wZ\in\{\winit,\wP_1,\wP_2,\wP_3,\wP_4\}$.
Thus, the existence of intermittently periodic trajectories can be checked by solving an MPIC-NCP.
For instance, an intermittently periodic trajectory that minimizes the sum of periods $\lambda_1$ and $\lambda_2$ can be found by solving the following linear programming problem[The problem is written in the max-plus algebra for simplicity. To get the standard linear programming formulation, we refer to Section <ref> and recall that $\lambda_1\otimes \lambda_2$ coincides with $\lambda_1 + \lambda_2$.]:

\begin{equation}\label{eq:LP_philosophers}
\begin{array}{cl}
\displaystyle\min_{x\in\R^{75},(\lambda_1,\lambda_2)\in\R^2_{\geq 0}} \quad & \lambda_1 \otimes \lambda_2 \\
\mbox{subject to} \quad & A(\lambda_1,\lambda_2) \otimes x \preceq x.
\end{array}
\end{equation}

The constraints of the above problem can be expressed as 212 inequalities (with each inequality corresponding to an element of $A(\lambda_1,\lambda_2)$ different from $-\infty$) in 77 variables.
Clearly, the optimization problem can be solved efficiently by linear programming solvers such as interior point methods or the simplex method.

However, since the number of optimization variables and constraints increases (linearly) with the length of subschedules $u_0,\ldots,u_q$ and $v_1,\ldots,v_q$, this method can be impractical for larger problems.
This becomes especially evident when considering hard scheduling problems such as the following one: find the schedule $w$, from a prescribed set of intermittently periodic schedules, which admits the intermittently periodic trajectory with minimal performance index $\bigotimes_{i=1}^q \lambda_i$.
The intrinsic NP-hardness of the problem requires the use of enumeration methods for its exact solution, and relying on standard solutions approaches for problems like (<ref>) to evaluate the performance index can result in a slow optimization procedure.
Therefore, it is natural to ask whether an alternative, less expensive technique to solve problems of the form (<ref>) exploiting the structure of the matrix in (<ref>) exists, similarly to what seen in Theorem <ref> for periodic schedules; an affirmative answer to this question will be provided in Theorem <ref>.

Returning to (<ref>), its solution reveals that the optimal value of $\lambda_1 \otimes \lambda_2$ is $19$, corresponding to $\lambda_1 = 11$ and $\lambda_2 = 8$.
The Gantt chart of Figure <ref> shows a trajectory corresponding to a solution of the optimization problem, for $m_1 = 2$.

Before concluding the example note that, for the SLDIs $\pazocal{S}$ modeling the starving philosophers problem, $\solSLDI[\wP_2\wP_4\wP_1\wP_3\wP_3] = [7.5,16]$ (the lower bound is the period of the trajectory shown in the Gantt chart of Figure <ref>) whereas the value of $\lambda_2$ solving (<ref>) is $8> 7.5$.
This shows a remarkable fact that is exclusive to systems with upper bound constraints: the cycle times valid in intermittently periodic trajectories may be different from those obtained by considering periodic subschedules independently.
The reason for this phenomenon has to be searched in the structure of the precedence graph of matrix $A(\lambda_1,\lambda_2)$ (schematically illustrated in Figure <ref> on page fi:intermittent_graph).
Here the critical circuit (i.e., the circuit with largest weight) can be generated from arcs connecting portions of the graphs related to different regimes (periodic or transient) of the schedule.

Gantt chart representing an intermittently periodic trajectory for the starving philosophers problem.

The latter two examples suggested the following proposition, which is proven in Appendix <ref>.

The set of periods $(\lambda_1,\ldots,\lambda_q)\in\R_{\geq 0}^q$ of intermittently periodic trajectories that are consistent for a given intermittently periodic schedule coincides with $\solNCP{\bigoplus_{h=1}^q (\lambda_h P_h\oplus \lambda_h^{-1} I_h)\oplus C}$, where $P_h,I_h,C$ are appropriately defined square matrices with $(U_0+\sum_{h=1}^q V_h + U_h)n$ rows and columns.

Similarly to Theorem <ref>, it is possible to reduce the complexity of the problem by leveraging the sparsity and modularity of matrix $\bigoplus_{h=1}^q (\lambda_h P_h\oplus \lambda_h^{-1} I_h)\oplus C$.
With the term modularity, we mean the recognizable block structure of the matrix; for an illustrative example see the dashed and dotted blocks in matrix $A(\lambda_1,\lambda_2)$ of (<ref>).
The main result, which is based on an extensive application of Theorem <ref>, is stated below.
Details of this result and its proof is provided for the particular case of Example <ref> in Appendix <ref>.

The MPIC-NCP of Proposition <ref> can be transformed into an equivalent one where the precedence graph to be studied has $qn$ nodes (instead of $(U_0+\sum_{h=1}^q V_h + U_h)n$).
The reduction requires $\pazocal{O}\left(\left(U_0+\sum_{h=1}^q V_h + U_h\right)n^3\right)$ operations.

Observe that performing the reduction takes a number of operations that is linear in the sum of the lengths of subschedules $u_0,\ldots,u_q$ and $v_1,\ldots,v_q$.
As no linear programming solver with linear worst-case complexity has ever been found, the advantage of the reduction becomes more prominent with longer subschedules.

[starving philosophers problem, cont.]

Let $A(\lambda_1,\lambda_2)$ be as in (<ref>).
Applying Theorem <ref> as explained in Appendix <ref>, it can be shown that $\graph(A(\lambda_1,\lambda_2))\in\nonegset$ if and only if $\graph(\widetilde{A}(\lambda_1,\lambda_2))\in\nonegset$, where

\[
\widetilde{A}(\lambda_1,\lambda_2) = \lambda_1 P_1 \oplus \lambda_1^{-1}I_1 \oplus \lambda_2 P_2 \oplus \lambda_2^{-1} I_2 \oplus C,
\]

and $P_1,I_1,P_2,I_2,C$ are matrices of dimension $10\times 10$ with coefficients in $\Rmax$.

In particular, the linear programming problem in (<ref>) has the same optimal value as the following one:

\begin{equation}\label{eq:LP_philosophers_improved}
\begin{array}{cl}
\displaystyle\min_{x\in\R^{10},(\lambda_1,\lambda_2)\in\R^2_{\geq 0}} \quad & \lambda_1 \otimes \lambda_2 \\
\mbox{subject to} \quad & \widetilde{A}(\lambda_1,\lambda_2) \otimes x \preceq x.
\end{array}
\end{equation}

It can be verified that the constraints of the above problem can be expressed as 146 inequalities in 12 variables.
Hence, compared with the constraints in (<ref>), we have a $31\%$ reduction in the number of inequalities and $84\%$ reduction in the number of variables.

§ PRACTICALLY MOTIVATED EXAMPLE

The example we present is a multi-product processing network taken from <cit.>.
Examples of such networks are electroplating lines and cluster tools.
Consider a manufacturing system consisting of 5 processing stations $S_1,\ldots,S_5$ and a robot of capacity one.
The system can treat two types of parts, part $\wA$, which requires to be processed on $S_1$, $S_3$, and $S_5$ (in this order), and part $\wB$, which must follow route $S_2$, $S_1$, $S_4$, $S_5$.
The task of the robot is to transport parts of type $\wA$ and $\wB$ from an input storage $S_0$ to their first processing stations, between the processing stations (in the right order), and finally from the last processing station to an output storage $S_6$.
The time the robot needs to travel from $S_i$ to $S_j$ is $\tau_{ij}$ when it is not carrying any part, and $\tau_{ij}^\wZ$ when it is carrying part $\wZ\in\{\wA,\wB\}$.
Moreover, the processing time for part $\wZ$ in station $S_i$ must be within the interval $\iota_i^\wZ=[L_{i}^\wZ,R_{i}^\wZ]\subset \R_{\geq 0}$.

We consider the following parameters for the processing network: $\tau_{ij} = |i-j|$, $\tau_{ij}^\wA = \tau_{ij}+1$, $\tau_{ij}^\wB=\tau_{ij}+2$, $\iota_1^\wA=[10,15]$, $\iota_3^\wA=[40,140]$, $\iota_5^\wA=[20,30]$, $\iota_2^\wB=[50,150]$, $\iota_1^\wB=[10,20]$, $\iota_4^\wB=[30,150]$, $\iota_5^\wB=[20,30]$.

§.§ Cycle time analysis

A classical scheduling problem in this kind of processing networks is to find a periodic robot operation sequence that minimizes the cycle time and avoids time-window constraints violations; in the literature, this is referred to as the single-robot (or hoist) cyclic scheduling problem <cit.>.
Such an optimization problem, which is strongly NP-hard, can be divided into two subproblems:

*  the cycle time minimization, given a fixed sequence of robot operations,

*  the search for the optimal robot operations sequence.

In this section we focus on <ref>, which is polynomial-time solvable: clearly, an efficient algorithm for <ref> can be used as subroutine in search procedures to solve the more general scheduling problem (<ref>+<ref>).

To find the cycle time for a given robot operation sequence, we will firstly assume, as is standard in robotic cyclic scheduling problems <cit.>, that the system is already treating parts in a periodic manner from the initial time; the application of Theorem <ref> will then provide the possible periods of such treatment plans.
In particular, we suppose that initially station $S_3$ is processing a part of type $\wA$, and $S_2$, $S_4$ are processing parts of type $\wB$.
Of course, this assumption is not met by real systems at start-up time (when all stations are empty), and will thus be relaxed in the next section.

We denote by $S_i\xrightarrow{\wZ} S_j$ robot operation "unload a part of type $\wZ$ from $S_i$, transport it to and load it into $S_j$" and by $\rightarrow S_j$ operation "travel from the current location to $S_j$ and wait if necessary".
A schedule for this process is a sequence of modes $w\in\{\wA,\wB\}^\omega$, where mode $\wA$ represents the sequence of operations

\[
\rightarrow S_3, S_3\xrightarrow{\wA} S_5,\rightarrow S_0,S_0 \xrightarrow{\wA} S_1,\rightarrow S_5,S_5 \xrightarrow{\wA} S_6,\rightarrow S_1,S_1 \xrightarrow{\wA} S_3
\]

and mode $\wB$ represents

\[
\rightarrow S_4, S_4\! \xrightarrow{\wB} S_5, \rightarrow S_2, S_2\! \xrightarrow{\wB} S_1, \rightarrow S_5, S_5\! \xrightarrow{\wB} S_6, \rightarrow S_0, S_0\! \xrightarrow{\wB} S_2, \rightarrow S_1, S_1\! \xrightarrow{\wB} S_4.
\]

Initially, the robot is positioned at $S_3$ if $w_1=\wA$ or at $S_4$ if $w_1=\wB$.

[$\mbox{P-TEG}_\wA$ for parts of type $\wA$.]

[$\mbox{P-TEG}_\wB$ for parts of type $\wB$.]

P-TEGs modeling the processing network considering only types of one part.
A token in a place colored red and black, respectively blue, represents a part being processed in a station and the robot moving with, respectively without carrying a part.

Let us first model the processing network when only part $\wA$, respectively, $\wB$ is considered.
In this way, we obtain two P-TEGs, $\mbox{P-TEG}_\wA$ and $\mbox{P-TEG}_\wB$ (shown in Figure <ref>), each of which represents the behavior of the system when processing only parts of one type.
Using Algorithm <ref>, we can find that the cycle times of the network when processing only parts of type $\wA$, $\wB$ are all values in $[73,+\infty[$, and $[72,192]$, respectively.
Now, from the obtained P-TEGs, we can model the processing network in the case where both part-types are considered as SLDIs $\pazocal{S}=(\{\wA,\wB\},A^0,A^1,B^0,B^1)$.
To do so, we must define matrices $A^0_\wZ,A^1_\wZ,B^0_\wZ,B^1_\wZ\in\Rmax^{n\times n}$ for $\wZ\in\{\wA,\wB\}$ appropriately: we start by adding in $\mbox{P-TEG}_\wA$ (respectively, $\mbox{P-TEG}_\wB$) the missing transitions from $\mbox{P-TEG}_\wB$ (respectively, $\mbox{P-TEG}_\wA$) – the obtained P-TEGs have both $n = 12$ transitions (in  general, $n=2+2\ \times$ number of processing stations).
For each new transition $t_i$ of $\mbox{P-TEG}_\wZ$, we define $(\MA^1_{\wZ})_{ii}=(\MB^1_{\wZ})_{ii} = 0$; this is done to store in auxiliary variables $x_i(k)$ the last entrance and exit times of parts in stations that are not used in mode $\wZ$.
Moreover, to model the transportation of the robot from $S_3$ to $S_4$ (respectively, from $S_4$ to $S_3$) after each switching of mode from $\wA$ to $\wB$ (respectively, from $\wB$ to $\wA$), we set $(\MA^1_\wA)_{4out,3in}=\tau_{34}$ (respectively, $(\MA^1_\wB)_{3out,4in}=\tau_{43}$).
The other elements of $\MA^0_\wZ,\MA^1_\wZ,\MB^0_\wZ,\MB^1_\wZ$ are taken from the characteristic matrices of $\mbox{P-TEG}_\wZ$, for $\wZ\in\{\wA,\wB\}$.

This modeling procedure results in the following matrices for mode $\wA$:

\[
A^0_\wA \oplus B^{0\sharp}_\wA =
\begin{bNiceMatrix}[small,r,first-row,last-col=13]
0 & 1in & 1out & 2in & 2out & 3in & 3out & 4in & 4out & 5in & 5out & 6 & \\
-\infty & -\infty & -\infty & -\infty & -\infty & -\infty & -\infty & -\infty & -\infty &    5 & -\infty & -\infty & 0\\
2 &  -\infty & -15 & -\infty & -\infty & -\infty & -\infty & -\infty & -\infty & -\infty & -\infty & -\infty & 1in\\
-\infty &  10 & -\infty & -\infty & -\infty & -\infty & -\infty & -\infty & -\infty & -\infty & -\infty &    5 & 1out\\
-\infty & -\infty & -\infty & -\infty & -\infty & -\infty & -\infty & -\infty & -\infty & -\infty & -\infty & -\infty & 2in \\
-\infty & -\infty & -\infty & -\infty & -\infty & -\infty & -\infty & -\infty & -\infty & -\infty & -\infty & -\infty & 2out \\
-\infty & -\infty &    3 & -\infty & -\infty & -\infty & -\infty & -\infty & -\infty & -\infty & -\infty & -\infty & 3in \\
-\infty & -\infty & -\infty & -\infty & -\infty & -\infty & -\infty & -\infty & -\infty & -\infty & -\infty & -\infty & 3out\\
-\infty & -\infty & -\infty & -\infty & -\infty & -\infty & -\infty & -\infty & -\infty & -\infty & -\infty & -\infty & 4in\\
-\infty & -\infty & -\infty & -\infty & -\infty & -\infty & -\infty & -\infty & -\infty & -\infty & -\infty & -\infty & 4out \\
-\infty & -\infty & -\infty & -\infty & -\infty & -\infty &    3 & -\infty & -\infty & -\infty & -30 & -\infty & 5in\\
-\infty &    4 & -\infty & -\infty & -\infty & -\infty & -\infty & -\infty & -\infty &   20 & -\infty & -\infty & 5out\\
-\infty & -\infty & -\infty & -\infty & -\infty & -\infty & -\infty & -\infty & -\infty & -\infty &   2  & -\infty & 6
\end{bNiceMatrix},
\]

\[
A^1_\wA =
\begin{bNiceMatrix}[small,r,first-row,last-col=13]
0 & 1in & 1out & 2in & 2out & 3in & 3out & 4in & 4out & 5in & 5out & 6 & \\
-\infty & -\infty & -\infty & -\infty & -\infty & -\infty & -\infty & -\infty & -\infty & -\infty & -\infty & -\infty & 0\\
-\infty & -\infty & -\infty & -\infty & -\infty & -\infty & -\infty & -\infty & -\infty & -\infty & -\infty & -\infty & 1in\\
-\infty & -\infty & -\infty & -\infty & -\infty & -\infty & -\infty & -\infty & -\infty & -\infty & -\infty & -\infty & 1out\\
-\infty & -\infty & -\infty &    0 & -\infty & -\infty & -\infty & -\infty & -\infty & -\infty & -\infty & -\infty & 2in\\
-\infty & -\infty & -\infty & -\infty &    0 & -\infty & -\infty & -\infty & -\infty & -\infty & -\infty & -\infty & 2out\\
-\infty & -\infty & -\infty & -\infty & -\infty & -\infty & -\infty & -\infty & -\infty & -\infty & -\infty & -\infty & 3in\\
-\infty & -\infty & -\infty & -\infty & -\infty &   40 & -\infty & -\infty & -\infty & -\infty & -\infty & -\infty & 3out\\
-\infty & -\infty & -\infty & -\infty & -\infty & -\infty & -\infty &    0 & -\infty & -\infty & -\infty & -\infty & 4in\\
-\infty & -\infty & -\infty & -\infty & -\infty &    1 & -\infty & -\infty &    0 & -\infty & -\infty & -\infty & 4out\\
-\infty & -\infty & -\infty & -\infty & -\infty & -\infty & -\infty & -\infty & -\infty & -\infty & -\infty & -\infty & 5in\\
-\infty & -\infty & -\infty & -\infty & -\infty & -\infty & -\infty & -\infty & -\infty & -\infty & -\infty & -\infty & 5out\\
-\infty & -\infty & -\infty & -\infty & -\infty & -\infty & -\infty & -\infty & -\infty & -\infty & -\infty & -\infty & 6
\end{bNiceMatrix},
\]

\[
B^{1\sharp}_\wA =
\begin{bNiceMatrix}[small,r,first-row,last-col=13]
0 & 1in & 1out & 2in & 2out & 3in & 3out & 4in & 4out & 5in & 5out & 6 & \\
-\infty &  -\infty &  -\infty &  -\infty &  -\infty &  -\infty &  -\infty &  -\infty &  -\infty &  -\infty &  -\infty &  -\infty & 0\\
-\infty &  -\infty &  -\infty &  -\infty &  -\infty &  -\infty &  -\infty &  -\infty &  -\infty &  -\infty &  -\infty &  -\infty & 1in\\
-\infty &  -\infty &  -\infty &  -\infty &  -\infty &  -\infty &  -\infty &  -\infty &  -\infty &  -\infty &  -\infty &  -\infty & 1out\\
-\infty &  -\infty &  -\infty &    0 &  -\infty &  -\infty &  -\infty &  -\infty &  -\infty &  -\infty &  -\infty &  -\infty & 2in\\
-\infty &  -\infty &  -\infty &  -\infty &    0 &  -\infty &  -\infty &  -\infty &  -\infty &  -\infty &  -\infty &  -\infty & 2out\\
-\infty &  -\infty &  -\infty &  -\infty &  -\infty &  -\infty &  -140 &  -\infty &  -\infty &  -\infty &  -\infty &  -\infty & 3in\\
-\infty &  -\infty &  -\infty &  -\infty &  -\infty & -\infty &  -\infty &  -\infty &  -\infty &  -\infty &  -\infty &  -\infty & 3out\\
-\infty &  -\infty &  -\infty &  -\infty &  -\infty &  -\infty &  -\infty &    0 &  -\infty &  -\infty &  -\infty &  -\infty & 4in\\
-\infty &  -\infty &  -\infty &  -\infty &  -\infty &  -\infty &  -\infty &  -\infty &    0 &  -\infty &  -\infty &  -\infty & 4out\\
-\infty &  -\infty &  -\infty &  -\infty &  -\infty &  -\infty &  -\infty &  -\infty &  -\infty &  -\infty &  -\infty &  -\infty & 5in\\
-\infty &  -\infty &  -\infty &  -\infty &  -\infty &  -\infty &  -\infty &  -\infty &  -\infty &  -\infty &  -\infty &  -\infty & 5out\\
-\infty &  -\infty &  -\infty &  -\infty &  -\infty &  -\infty &  -\infty &  -\infty &  -\infty &  -\infty &  -\infty &  -\infty & 6
\end{bNiceMatrix}
\]

The modeling effort required to define $\pazocal{S}$ is repaid by the possibility to use Theorem <ref> for computing the minimum and maximum cycle times corresponding to a schedule $w=v^K$, for $K\in\nat\cup\{+\infty\}$.
For instance, we get $\solSLDI[\wB\wA] = [77,192]$.
This means that, using schedule $(\wB\wA)^\omega$, the time between subsequent completions of a product of the same type is at least $72$ and at most $192$ time units.

To appreciate the advantage of using the algorithm derived from Theorem <ref>, in Figure <ref> we compare the computational time to obtain $\solSLDI$ with increasing subschedule length $V$ using Theorem <ref> and other methods; specifically, we also consider the algorithm derived from Proposition <ref> directly, the algorithm developed in <cit.>, and a linear programming solver.
The implementations were made on Matlab R2019a, and for solving the linear programs we used CPLEX's dual simplex method; the tests were executed on a PC with an Intel i7 processor at 2.20Ghz.
From the results, we can see that the most time-consuming approach is the one using Proposition <ref> directly, while the algorithm from Theorem <ref> achieves the fastest computation.
The advantage becomes more evident with larger subschedule lengths: for instance, when $V = 300$, the dual simplex method takes $11.0\cdot 10^{-2}$ seconds to solve the problem, whereas the algorithm derived from Theorem <ref> only $1.25 \cdot 10^{-2}$ seconds.
Such computational time reduction may have considerable impact for the solution of cyclic scheduling problems.

Time to compute $\solSLDI$ for increasing values of $V$ using different methods.

§.§ Considering start-up and shut-down transients

At the start-up, the system cannot follow the periodic trajectories found in the previous section as all stations are initially empty.
Moreover, the periodic workflow must be interrupted for the system shut-down, at the end of which all stations are left empty.
In the following, we also suppose that the initial position of the robot coincides with the location of the input storage $S_0$.

To represent the complete dynamics of the processing network, from the start-up to the shut-down, we introduce additional modes of operations modeling the initial and final transients.
In particular, we add three modes for the start-up: $\winit_{\wB_1}$ corresponds to the sequence of operations

\[
S_0 \xrightarrow{\wB} S_2, \rightarrow S_2, S_2 \xrightarrow{\wB} S_1, \rightarrow S_0,
\]

mode $\winit_{\wB_2}$ corresponds to

\[
S_0 \xrightarrow{\wB} S_2, \rightarrow S_1, S_1 \xrightarrow{\wB} S_4, \rightarrow S_0,
\]

and mode $\winit_{\wA}$ is associated to

\[
S_0 \xrightarrow{\wA} S_1, \rightarrow S_1, S_1 \xrightarrow{\wA} S_3.
\]

The subschedule $\winit_{\wB_1}\winit_{\wB_2}\winit_{\wA}$ represents the initial transient of the processing network, consisting of the transportation inside the system of the first two parts of type $\wB$ and the first part of type $\wA$; thus, at the end of the sequence of operations corresponding to $\winit_{\wB_1}\winit_{\wB_2}\winit_{\wA}$, a part of type $\wB$ is in station $S_2$, another part of the same type is in $S_4$, and a part of type $\wA$ is in $S_3$.
Similarly, three modes are added for the shut-down: mode $\wfin_{\wB_1}$ corresponds to

\[
\rightarrow S_4, S_4 \xrightarrow{\wB} S_5, \rightarrow S_2, S_2 \xrightarrow{\wB} S_1, \rightarrow S_5, S_5 \xrightarrow{\wB} S_6, \rightarrow S_1, S_1 \xrightarrow{\wB} S_4,
\]

mode $\wfin_{\wA}$ is associated to

\[
\rightarrow S_3, S_3 \xrightarrow{\wA} S_5, \rightarrow S_5, S_5 \xrightarrow{\wA} S_6,
\]

and mode $\wfin_{\wB_2}$ corresponds to

\[
\rightarrow S_4, S_4 \xrightarrow{\wB} S_5, \rightarrow S_5, S_5 \xrightarrow{\wB} S_6.
\]

Similarly to modes $\wA$ and $\wB$, we can derive matrices $A^0_\wZ$, $A^1_\wZ$, $B^0_\wZ$, and $B^1_\wZ$ for the additional modes $\winit_{\wB_1},\winit_{\wB_2},\winit_\wA,\wfin_{\wB_1},\wfin_\wA,\wfin_{\wB_2}$.

An example of complete schedule for the processing network is the intermittently periodic schedule

\[
w = \winit_{\wB_1}\winit_{\wB_2}\winit_\wA (\wB \wA)^{m} \wfin_{\wB_1} \wfin_\wA \wfin_{\wB_2},
\]

where $m\in\nat$ is the number of repetitions of subschedule $\wB \wA$.
To find the admissible periods $\lambda$ of an intermittently periodic trajectory following schedule $w$, we solve the PIC-NCP on matrix

\[
\lambda P \oplus \lambda^{-1} I \oplus C = \begin{bsmallmatrix}
C_{\winit_{\wB_1}} & P_{\winit_{\wB_1}} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} \\
I_{\winit_{\wB_1}} & C_{\winit_{\wB_2}} & P_{\winit_{\wB_2}} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} \\
\pazocal{E} & I_{\winit_{\wB_2}} & C_{\winit_{\wA}} & P_{\winit_{\wA}} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} \\
\pazocal{E} & \pazocal{E} & I_{\winit_{\wA}} & C_{\wB} & P_\wB\oplus \lambda^{-1}I_\wA & \pazocal{E} & \pazocal{E}  & \pazocal{E} \\
\pazocal{E} & \pazocal{E} & \pazocal{E} & I_\wB\oplus \lambda P_{\wA} & C_\wA & P_\wA & \pazocal{E}  & \pazocal{E} \\
\pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & I_{\wA} & C_{\wfin_{\wB_1}} & P_{\wfin_{\wB_1}} & \pazocal{E} \\
\pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & I_{\wfin_{\wB_1}} & C_{\wfin_{\wA}} & P_{\wfin_\wA} \\
\pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & I_{\wfin_{\wA}} & C_{\wfin_{\wB_2}}
\end{bsmallmatrix}
\]

using Theorem <ref>; the outcome is that the valid periods are those in interval $[77,192]$.
Finally, a consistent intermittently periodic trajectory can be obtained from any column of $(\lambda P \oplus \lambda^{-1} I \oplus C)^*$ for $\lambda\in [77,192]$ (see Proposition <ref>).
For instance, the trajectory displayed in Figure <ref> is derived through some simple manipulations from the first column of matrix $A=(77 P \oplus 77^{-1} I \oplus C)^*$; in particular, we consider $w = \winit_{\wB_1}\winit_{\wB_2}\winit_\wA \wB \wA \wB \wA \wfin_{\wB_1} \wfin_\wA \wfin_{\wB_2}$ (i.e., $m = 2)$ and impose:

\[
\forall k\in\dint{1,5},\ x(k) = A_{\dint{12\times (k-1),12\times k},1},\quad x(6) = 77 x(4),\ x(7) = 77 x(5),
\]

\[ \forall h\in\dint{8,10},\ x(h) = 77 A_{\dint{12\times (h-3),12\times (h-2)},1},
\]

where $A_{\dint{i,j},1}$ indicates the vector containing elements $i,i+1,\ldots,j$ of the first column of matrix $A$.

Intermittently periodic trajectory for the multi-product processing network. In this trajectory, 3 parts of type $\wA$ and 4 of type $\wB$ are processed.

§ FINAL REMARKS

A number of results regarding the cycle time analysis in systems with time-window constraints have been presented.
Because of the generality of SLDIs, the formulas in Theorem <ref> and the complexity-reduction technique of Theorem <ref> are applicable to a wide range of cyclic scheduling problems.
However, plenty of problems of theoretical and practical relevance regarding SLDIs remain open, such as the decidability and complexity of verifying the existence of a schedule $w$ under which the SLDIs is boundedly consistent, or the development of feedback-control techniques for this class of systems.

In the following, we draw comparisons between SLDIs and other related dynamical systems to provide a broader context for this new class of systems and to outline possible research directions inspired from previous work.

SLDIs have strong connections with several other dynamical systems, with interval weighted automata being the most closely related in terms of modeling expressiveness <cit.>.

Interval weighted automata represent the natural extension of max-plus automata to the case of time-window constraints, which force the dater function to satisfy inequalities of the form

\begin{equation}\label{eq:IWA}A^1_{w_k} \otimes x(k) \leq x(k+1) \leq B^1_{w_k} \stimes x(k).\end{equation}

Expanding the seminal work <cit.> of Gaubert and Mairesse, in <cit.> it was shown that safe P-time Petri nets, in which the number of tokens per place cannot exceed 1, are a subclass of interval weighted automata.
Comparing (<ref>) with (<ref>), it is not difficult to see that SLDIs are an even larger class of systems compared to interval weighted automata, implying that also SLDIs can represent the dynamics of safe P-time Petri nets.

If from (<ref>) we eliminate the upper bound constraints (by defining $B_{w_k}^1=\mathcal{T}$) and take the least consistent trajectory of the dater function (by substituting the left "$\leq$" sign in (<ref>) by "$=$"), we get the dynamics of a max-plus automaton <cit.>:

\begin{equation}\label{eq:MPA}
A^1_{w_k} \otimes x(k) = x(k+1).
\end{equation}

This shows that the behavior of any max-plus automaton corresponds to the "fastest" trajectory of specific switched max-plus linear-dual inequalities, in which $A^0_{w_k} = \pazocal{E}$ and $B^0_{w_k} = B^1_{w_k} = \mathcal{T}$.
From this relationship one can observe that the algorithm derived in this paper for the cycle time computation in periodic schedules (Theorem <ref>) generalizes <cit.>, which gives a simple formula for the cycle time of safe job shops (without upper bound constraints).
The involvement of more complex formulas featured in Theorem <ref> has to be attributed to the greater number of circuits in the precedence graph when accounting for upper-bound constraints (see Figure <ref>; the case considered in <cit.> corresponds to the same type of graphs but without arcs labeled $P_i$, $\lambda P_i$, and $C_i$).

In <cit.>, van den Boom and De Schutter extended the capabilities of max-plus automata by introducing an input signal $u(k)\in\R^m$ and an input-state matrix $D_{w_k}\in\Rmax^{n\times m}$ to (<ref>); the resulting dynamical system is referred to as a switching max-plus linear system:

\begin{equation}\label{eq:switching_max_plus}
A^1_{w_k} \otimes x(k) \oplus D_{w_k} \otimes u(k+1) = x(k+1).
\end{equation}

Now the system is not anymore forced to evolve according to the fastest possible trajectory represented by (<ref>), but it is possible to construct a controller that, by selecting the appropriate input signal, can delay the occurrence of events with the aim of regulating the behavior of the system.
This feature makes switching max-plus linear systems, in a certain sense, more similar to SLDIs.
We explain this in more detail in the following.
Take a switching max-plus linear system and assume that the input signal is able to delay "directly" the occurrence of each event.
Mathematically, this corresponds to having $D_{w_k} = E_{\otimes}\in\Rmax^{n\times n}$ for all $k$.
Then, recalling that $\oplus$ in (<ref>) is the elementwise maximization, by taking $u(k+1)$ sufficiently large (in particular, $A^1_{w_k}\otimes x(k)\leq u(k+1)$), $x(k+1)$ and $u(k+1)$ coincide, and (<ref>) simplifies to

\[
A^1_{w_k} \otimes x(k) \oplus x(k+1) = x(k+1),
\]

which is equivalent to

\[
A^1_{w_k} \otimes x(k) \leq x(k+1).
\]

In this way, we have recovered a portion of the inequalities that appear in SLDIs.
Thus, observe that:

* on the one hand, unlike SLDIs, switching max-plus linear systems are not able to represent upper-bound constraints,

* on the other hand, only systems where all events are directly controllable (i.e., delayable) can be modeled by SLDIs, whereas this does not need to be the case for switching max-plus linear systems.

It follows that the modeling expressiveness of switching max-plus linear systems and SLDIs is not comparable.
The generalization of the results of the present paper to switching dynamical systems driven by time-window constraints and where the assumption of direct controllability of all events is relaxed is left as future work.