Tropical Lexicographic Optimization: Synchronizing Timed Event Graphs

Abstract

Tropical Algebra is used to model the dynamics of Timed Event Graphs (TEG), a particular class of Timed Discrete-Event System (TDES) in which we are interested only in synchronization and delay phenomena. Whenever this TEG has control inputs, we can use them to control the synchronization of the system to achieve some objective. Thus, this paper formulates a framework based on tropical algebra and lexicographic optimization to synchronize a TEG when dealing with many synchronization objectives that are ranked in previous priority order. We call this kind of problem the Tropical Lexicographic Synchronization Optimization (TLSO). This work develops a solution to this problem, based on Tropical Fractional Linear Programming (TFLP) and lexicographic optimization concepts. In this way, the basics of tropical algebra are determined, including essential terms to this paper, such as left and right residuations, and the following stages of the solution to the TLSO problem are explained. Therefore, this work presents a general framework based on structured algebraic models with application to TEG synchronization. By synchronization, we mean balancing and organizing events chronologically in order to achieve the desired goal. So, we are dealing with concepts closely related to symmetry ones. An illustrative numerical example is presented, which demonstrates the implementation of the proposed algorithms. The acquired results confirm the efficiency of the proposed methodology. Codes used for implementing the algorithms are listed in the appendix section of the article.

1. Introduction

Timed Event Graphs (TEGs) are used to model a wide range of Timed Discrete-Event Systems (TDES), which is a class of dynamic systems in which the change of state is governed by events [1]. Examples of model applications include manufacturing systems, production chains, queues, and urban traffic systems [2].

A powerful tool for analysis of TEGs is the so-called Tropical Algebra, which is a kind of idempotent algebraic structure which can be a semiring or a semifield depending on the application. French researchers gave the denomination as a tribute to Brazilian mathematician Imre Simon, who had a considerable influence on the development of automata and semigroup theory [3].

There are many types of tropical algebras that have applications in areas such as mathematics, engineering, and computer science. Two important examples are the Min-Plus and Max-Plus algebra. Concerning Max-Plus algebra, several results were obtained for analysis and synthesis of TDES. Among them, we highlight remarkable developments in control synthesis for such systems in the last decades (e.g., [4,5,6,7,8,9]).

The methodology used in this work addresses the synchronization problem, giving priority to TEG transitions to be synchronized, as proposed by lexicographic optimization. Each stage of the general problem is treated as a subproblem, which is solved through Tropical Fractional Linear Programming (TFLP). This optimization employs the dual iterative method, which, in turn, uses the residency operation. The original contribution of this paper is a lexicographic formulation of a TFLP problem aimed at synchronizing multiple disconnected TEGs. As references for TFLP, the reader is invited to consult [10,11], and for lexicographic optimization, the reference is [12]. More precisely, the authors propose a framework to synchronize the firing times of the transition of a TEG, considering a priority list of the pair of transitions that must be synchronized. This framework models this problem as a Lexicographic variation of a TFLP [10,11]. The authors denote the problem as a Tropical Lexicographic Synchronization Optimization (TLSO). It is important to stress that this framework can be applied in a general context. Moreover, as far as the authors’ knowledge goes, there are few works regarding linear fractional programming applications, and the authors do not find researches that deal with the insertion of lexicographic optimization in this context. Therefore, this article contributes to a formulation that unites existing concepts and relates them with a numerical example. As an illustrative application, traffic light synchronization is used as an example. In particular, this paper refers to Egmund and Olsder [13], who introduce the basics of Max-Plus algebra to deal with synchronization between phases in the traffic light system, with the purpose to generate the green waves.

This work has a theoretical impact by proposing a framework capable of synchronizing a class of models—the timed event graphs. There are few applications of this concept, for instance, manufacturing [2,14], traffic light control [13], payoff games [10], and multiprocessed systems [15,16]. The remainder of the paper is organized as follows: In Section 2, we introduce the preliminary concepts, in which the elements of tropical algebra are defined. In Section 3, the Tropical Lexicographic Synchronization Optimization is discussed, and the used tools to solve it are explained. Section 4 deals with a numerical example, which is explained while developing a study case. Finally, in the Appendix Section, we provide the listed codes implemented in ScicosLab. Note that Scicolab is a free package for mathematical computing, similar to Matlab. It can be found in http://www.scicoslab.org. The software is very convenient to work with tropical algebra since it has many of the related functions native implemented. (Version 4.4) code for the algorithm.

2. Tropical Algebra

This work is heavily based on tropical algebra. Therefore, in this section, we introduce some concepts and definitions related to this algebra. For more details on academic background, consult a historical review of Max-Plus tropical algebra [2,17,18]. “Tropical algebra” is a generic name for a family of idempotent algebraic structures, which can be a semiring or a semifield depending on the application. A special example of tropical algebra is the so-called Max-Plus Algebra. It is a particular Tropical structure act on the set ${\mathbb{T}}_{max}=\mathbb{R}\cup \{-\infty \}$ with two operations, named $a\oplus b=max(a,b)$ and $a\otimes b=a+b$. Furthermore, let ${\mathbb{T}}_{max}^n$ and ${\mathbb{T}}_{max}^{n\times m}$ be the set of column vectors with n entries in $T_{max}$ and the set of matrices with n rows and m columns in $T_{max}$, respectively. From now on, we consider that “Max-Plus algebra” and “tropical algebra” can be used as synonyms, and this paper adopts the latter notation.

This algebra can be extended to matrices and vectors. If $A=\left(A_{ij}\right)$, $B=\left(B_{ij}\right)$, and $C=\left(C_{ij}\right)$ are matrices of compatible sizes with entries in ${\mathbb{T}}_{max}$, we denote by $C=A\oplus B$ the tropical matrix sum, in which $C_{ij}=A_{ij}\oplus B_{ij}$. Furthermore, we define as $C=A\otimes B$ the tropical matrix product, in which ${\displaystyle C_{ij}=\underset{k}{⨁}{A}_{ik}\otimes B_{kj}}$. In later notations, we omit the symbol ⊗ and denote the tropical product by juxtaposition, so $A\otimes B=AB$. We use the symbol $\epsilon$ to denote $-\infty$. Let ${\epsilon }_{n\times m}$ be a matrix of $\epsilon$ with n rows and m columns. This article denotes the Max-Plus identity matrix of appropriate order, a matrix with 0 in the diagonal and $\epsilon$ outside, by $I{d}_{\mathbb{T}}$. For a square matrix A, we denote by $A^k$ the $k^{th}$ tropical power of A, defined recursively as $A^k=A{A}^{k-1}$ and $A^0=I{d}_{\mathbb{T}}$.

If A is a matrix (or a scalar) let $-A$ be the matrix (or the scalar) obtained by switching the sign of its entries. If a is a vector and b is a scalar $b\ne \epsilon$, let be $(-b)a$ (all the elements of a subtracted by b). Let $\rho \left(A\right)$ denote the spectral radius of A, i.e., the largest eigenvalue. In Tropical Algebra, the eigenvalue defines the cycle time in a TEG and is still active research topic, with recent results, such as involving nontrivial eigenvectors [19,20]. The symbol is because is the analog of a division in Max-Plus algebra. If $\rho \left(A\right)\le 0$, let $A^{*}$ denote the Kleene closure of A, i.e., ${\displaystyle \underset{i=0}{\overset{\infty }{⨁}}{A}^i}$. It is assumed from now on that the reader is familiar with the basics of this algebra, including concepts as Kleene closure [21].

Remark 1. 

Unless stated otherwise, all operations in this paper are done in tropical algebra. So it is essential to be careful with the symbol that we use for the operations.

An important operation in tropical algebra is the residuation. The residuation works as a kind of multiplicative inverse in the matrix tropical algebra. This work defines it below:

Definition 1. 

We define $\circ \backslash$, $\circ /$—the left and right residuation of the product, respectively—as (see more details in [22])

$$A\circ /B\equiv \begin{array}{c}maxX\\ XB\le A\end{array},$$

(1)

$$A\circ \backslash B\equiv \begin{array}{c}maxX\\ AX\le B\end{array}.$$

(2)

Note that the residuations are implicitly defined by multiobjective optimization problems, since we want to optimize all the entries of the matrix X of appropriate dimension subject to the constraint $XB\le A$ or $AX\le B$. Perhaps surprisingly, there is indeed a solution X, which is optimal in all its entries (the so-called utopical solution in optimization), and it is found by the residuations $A\circ /B$ and $A\circ \backslash B$.

For instance, consider problem (3) below:

$${\displaystyle \underset{X}{max}\left(\begin{array}{c}\hfill x_1\\ \hfill x_2\end{array}\right),}$$

(3)

subject to

$$\underset{A}{\underbrace{\left(\begin{array}{cc}\hfill 1& \hfill 2\\ \hfill 3& \hfill 4\end{array}\right)}}\underset{X}{\underbrace{\left(\begin{array}{c}\hfill x_1\\ \hfill x_2\end{array}\right)}}\le \underset{B}{\underbrace{\left(\begin{array}{c}\hfill 5\\ \hfill 6\end{array}\right)}}.$$

(4)

Note that this is of the form of (2). Thus, notice that the previous inequality can be rewritten as

$$\begin{array}{c}\hfill 1x_1\oplus 2x_2\le 5\\ \hfill 3x_1\oplus 4x_2\le 6\end{array}⟺\begin{array}{c}\hfill 1x_1\le 5,2x_2\le 5\\ \hfill 3x_1\le 6,4x_2\le 6\end{array}$$

(5)

Let $A\wedge B$ be the entrywise minimum between the matrices A and B. Consequently,

$$\begin{array}{c}\hfill x_1\le 4,x_2\le 3\\ \hfill x_1\le 3,x_2\le 2\end{array}⟺\begin{array}{c}\hfill x_1\le 4\wedge 3=3\\ \hfill x_2\le 3\wedge 2=2\end{array}.$$

(6)

Therefore, we have that

$$X=\left(\begin{array}{c}\hfill x_1\\ \hfill x_2\end{array}\right)\le \left(\begin{array}{c}\hfill 3\\ \hfill 2\end{array}\right).$$

(7)

Note that all the previous operations can be reversed. This implies that $X_{max}={\left(32\right)}^T$ is the maximum possible value for the matrix X, optimal in all its entries $x_1$ and $x_2$. This is exactly the (left) residuation: $X_{max}=A\circ \backslash B$.

The general formula for computing the left residuation is $A\circ \backslash B=-\left(A^T(-B)\right)$. Analogously, for the right residuation, $A\circ /B=-\left((-A)B^T\right)$. In both cases, in the internal tropical product, we consider that $-\epsilon +\epsilon =\epsilon$.

3. Tropical Lexicographic Synchronization Programming

In general, the purpose of this research is to synchronize the transitions of the TEGs, which describes the discrete event systems. In this section, we propose a framework for establishing synchronization among the transitions of a TEG, a model for TDES. This is applicable in, for instance, traffic light systems synchronization, as is discussed further in this paper. Note that this is only one of the various possible applications of this kind, in which it is desired to have synchronization among transitions.

3.1. Motivation

As an example of application of the proposed procedure, consider a traffic light system, in which the goal is to obtain synchronization between phases at adjacent crossings, which allows green waves, a sequence of green lights in continuous crossings.

A traffic light system can be modeled as a TEG [13]. Figure 1 illustrates a TEG example in which we have two subsystems, in which each one is related to a crossing. Each transition $x_i$ represents a change of phases in each crossing, in which a phase corresponds to a combination of enabled green lights. We also have transitions $u_i$, which represents the control of each phase. This means that we can delay the end of each phase.

A correct synchronization of the system allows the creation of green waves. The synchronization consists on having firing times $x_i$ as close as possible. Thus, the problem involves choosing the firing times $u_i$, which optimize the synchronization of the system, considering a priority order. Prioritization is necessary because it may not be possible to synchronize all the transitions $x_i$, it is the same as synchronizing the TEG. More details are seen in the next section.

Note that the application of traffic light control is only one of the possible applications. For instance, we could consider manufacture processing and other systems that need sharing and synchronization of resources. The generic framework used to solve these described problems is proposed in the next subsections.

3.2. Formulation of the Tropical Lexicographical Synchronization Problem

Consider the Tropical linear system below, in which we have the state $x\left[k\right]\in {\mathbb{T}}_{max}^n$ and input $u\left[k\right]\in {\mathbb{T}}_{max}^m$

$$x[k+1]=Ax\left[k\right]\oplus Bu[k+1].$$

(8)

We suppose that our policy for $u\left[k\right]$ is $u\left[k\right]={\lambda }^k\mu$, in which $\lambda$ is a scalar and $\mu$ is a constant vector of the same dimension as $u\left[k\right]$. With this same $\lambda$ and $\mu$ we can obtain a closed-loop controller $u\left[k\right]=Fx\left[k\right]$, see [23]. If $\lambda >\rho \left(A\right)$, it is known [8] that there are a finite K such that for all $k\ge K$, $x\left[k\right]={\lambda }^k\chi$ for a constant vector $\chi$ of same dimension as $x\left[k\right]$ that depends on $\mu$. Let ${M=\left((-\lambda )A\right)}^{*}B$. More precisely,

$$\chi \left(\mu \right)=M\mu .$$

(9)

For a fixed choice of $\lambda >\rho \left(A\right)$, we want to choose the vector $\mu$ such that the entries of $x\left[k\right]$ in steady-state ($k\ge K$) are as close as possible, i.e., they are synchronized. Unfortunately, it is not possible to have all the entries of $x\left[k\right]$ synchronized (i.e., equal), because we may not have enough freedom in $\mu$ to achieve such an objective. So, we need to prioritize the synchronizations. So, it is necessary to define some elements:

• Let P be the number of pairs of transitions of the TEG that we want to synchronize.
• Let $\mathcal{L}$ be the list of P pairs of indexes $\left(i\right(p),j(p\left)\right)$ of entries of $x\left[k\right]$ that we want to synchronize, ordered according to a decreasing defined priority. So, for instance, the pair of indexes $\left(i\right(1),j(1\left)\right)$ is more important to be synchronized than the pair of indexes $\left(i\right(2),j(2\left)\right)$. Furthermore, we assume that in a pair $\left(i\right(p),j(p\left)\right)$, $x_{i\left(p\right)}\left(k\right)\ge x_{j\left(p\right)}\left(k\right)$, i.e., we pre-specify a temporal order on the state in those indexes (the firing time $x_{i\left(p\right)}$ comes after the firing time $x_{j\left(p\right)}$, or, in the best case, at the same time).
• Let ${\delta }_p=x_{i\left(p\right)}\left(k\right)-x_{j\left(p\right)}\left(k\right)$. This is the synchronization index for the $p^{th}$ pair, which we want to minimize. Since the $x_n\left(k\right)$ represent the firing times of the transitions for the $k^{th}$ time, ${\delta }_p$ represents the delay between the $k^{th}$ firing time of transition $x_{j\left(p\right)}\left(k\right)$ and the $k^{th}$ firing time of transition $x_{i\left(p\right)}\left(k\right)$. (So, if ${\delta }_p$ equals to 0, the transitions happen simultaneously).

Note that, since $x_{i\left(p\right)}\left(k\right)\ge x_{j\left(p\right)}\left(k\right)$, this is always a non-negative number. Moreover, since $x\left[k\right]={\lambda }^k\chi \left(\mu \right)$ is in steady-state, one can see that ${\delta }_p={\chi }_{i\left(p\right)}\left(\mu \right)-{\chi }_{j\left(p\right)}\left(\mu \right)$, and therefore is independent on both k (that is why the symbol ${\delta }_p$ does not depend on k, although the definition seems to depend on k) and $\lambda$, depending only on $\chi$, which in turn depends on our decision variable $\mu$ according to (9).

We finally conclude that a higher priority pair has an utmost priority over a lower priority pair. This implies that we have a lexicographical optimization on the indexes ${\delta }_p$. Let $I_p^T$ and $J_p^T$ be the $i{\left(p\right)}^{th}$ and $j{\left(p\right)}^{th}$ row of the matrix M. Let $m_r$ be the $r^{th}$ row of M, respectively. Note that $x_p\left(k\right)={\lambda }^k{m}_p^T\mu$. So, our optimization problem is

(10)

It is possible that a pair of $\left(i\right(p),j(p\left)\right)$ cannot be synchronized, given the previous constraints. In Section 3.5, it is explained how this can be detected. In this case, we need to skip this pair and continue to the next one.

We define problems of this type as Tropical Lexicographic Synchronization Optimization (TLSO). Since the parameters of the problem are the matrix M, the list $\mathcal{L}$, and the scalar $\lambda >\rho \left(A\right)$, we can denote the problem by $TLSO(A,B,\mathcal{L},\lambda )$.

3.3. Lexicographic Optimization Problem

In a general form, a Lexicographic Optimization Problem consists of solving $lex{min}_{\mu }$$f_i\left(\mu \right)$, $i=1,2,...,p$, subject to a constraint $g\left(\mu \right)\le 0$. Note that the objective functions $f_i\left(\mu \right)$ are ordered so an index i has more priority than index $i+1$. One procedure to solve this kind of problem consists of solving a sequence of traditional optimization problems for $j=1$ to $j=p$:

$$\begin{array}{c}{\displaystyle \underset{\mu }{min}{f}_j\left(\mu \right)}\\ \mathrm{subject}\mathrm{to}:g\left(\mu \right)\le 0,\\ f_i\left(\mu \right)=f_i^{*},i=1,2,...,j-1\end{array}$$

(11)

in which $f_i^{*}$ is the optimal value of $f_i\left(\mu \right)$ in the previous problem [12].

3.4. Tropical Fractional Linear Programming

We want to solve a TLSO, which is a Lexicographic Optimization Problem. We use the strategy explained in Section 3.3, which reduces lexicographic optimization problems into a sequence of traditional optimization problems. In our case, the particular traditional optimization problems are TFLP. The general form of a TFLP problem is

(12)

in which w, $\alpha$, f, $\beta$, R, r, S, s are parameters. This kind of problem has been studied in [10,11], and algorithms have been proposed to solve them. The algorithm proposed in [11], in particular, relies on the ability to solve a particular case of TFLP. This particular case is called Max-Type Tropical Linear Problem (Max TLP):

$$\begin{array}{c}{\displaystyle \underset{\upsilon }{max}{g}^T\upsilon ,}\\ \mathrm{subject}\mathrm{to}:E\upsilon \oplus e=D\upsilon \oplus d.\end{array}$$

(13)

In order to guarantee that the solution $\upsilon$ for this problem is finite, the constraint of (13) must generate a set, which is upper bounded; in better words, there must exist a finite vector ${\upsilon }_{max}$ such that $\upsilon \le {\upsilon }_{max}$. From now on, we assume that this is true.

An algorithm to solve this problem is called Dual Method [11]. This is an iterative method that works with the following recursion:

$$\upsilon [k+1]=E\circ \backslash \left(D\upsilon \right[k]\oplus d)\wedge D\circ \backslash \left(D\upsilon \right[k]\oplus e)\wedge \upsilon \left[k\right],$$

(14)

with the initial condition $\upsilon \left(0\right)={\upsilon }_{max}$. In each iteration k, the following conditions must be tested:

$$\begin{array}{c}e\le D\upsilon \left[k\right]\oplus d,and\hfill \\ d\le E\upsilon \left[k\right]\oplus e.\hfill \end{array}$$

(15)

If these conditions are not true, the algorithm halts, and we can conclude that the feasible set of (13) is empty. Otherwise, when the algorithm converges (new $\upsilon$ equal to a previous $\upsilon$), it is able to find the optimal solution for the optimization problem. Note that the algorithm is independent of g. It turns out that, indeed, the solution $\mu$ is independent of these elements (see [11]). Any solution $\upsilon$ which is optimal for a vector $g_1$ is also optimal for any other $g_2$. More generally, any objective function $f\left(\upsilon \right)$ which is nondecreasing implies the same behavior. This happens because the algorithm in (14) will find a solution $\upsilon$ inside the feasible set of (13) that is maximal in any entry of $\upsilon$ [24].

When using the discussed Tropical Dual method by solving (14), we can solve the TFLP problems by converting Max-Type TFLP into Max-Type TLP problem according to Figure 2 through Charnes–Cooper conversion [25]. The complete TFLP problem is defined in (12). It is straightforward to adapt the Charnes–Cooper transformation to the tropical setting [11]. Set

(16)

Then, by dividing (in tropical algebra) both sides of the affine equation on (12) by $f^T\mu \oplus \beta$, it can be rewritten as

$$\begin{array}{c}{\displaystyle \underset{\theta ,\widehat{\theta }}{max}{w}^T\theta \oplus \alpha \widehat{\theta },}\\ \mathrm{subject}\mathrm{to}:\\ R\theta \oplus r\widehat{\theta }=S\theta \oplus s\widehat{\theta };\\ f^T\theta \oplus \beta \widehat{\theta }=0\end{array}$$

(17)

in which the additional equation $f^T\theta \oplus \beta \widehat{\theta }=0$ condenses (16).

Define the vector

$$\upsilon =\left[\begin{array}{c}\theta \\ \widehat{\theta }\end{array}\right].$$

(18)

Let n and m be the number of rows and columns of R, respectively. With this definition, we can rewrite (17) as

$$\begin{array}{c}{\displaystyle \underset{\upsilon }{max}\underset{g^T}{\underbrace{\left[w^T\alpha \right]}}\upsilon ,}\\ \mathrm{subject}\mathrm{to}:\\ \underset{E}{\underbrace{\left[\begin{array}{cc}R& r\\ f^T& \beta \end{array}\right]}}\upsilon \oplus \underset{e}{\underbrace{\left[\begin{array}{c}{\epsilon }_{n\times 1}\\ \epsilon \end{array}\right]}}=\underset{D}{\underbrace{\left[\begin{array}{cc}S& s\\ {\epsilon }_{1\times m}& \epsilon \end{array}\right]}}\upsilon \oplus \underset{d}{\underbrace{\left[\begin{array}{c}{\epsilon }_{n\times 1}\\ 0\end{array}\right]}}.\end{array}$$

(19)

Remember that ${\epsilon }_{n\times 1}$ is a vector of $\epsilon$ with n rows and one column, and ${\epsilon }_{1\times m}$ is a vector of $\epsilon$ with one row and m columns.

This problem is a Max-type TLP as (13) and can be solved by Algorithm 1. The program’s code in the Scicoslab language is listed in Appendix A.1. Once $\theta$ and $\widehat{\theta }$ are obtained, in order to return to the original variable, one needs to revert (16).

(20)

Algorithm 1: Tropical Dual Function: TDual Algorithm

The TFLP method is implemented by the function $\mathtt{TFLP}(w,\alpha ,f,\beta ,R,r,S,s)$, in which w, $\alpha$, f, $\beta$, R, r, S, and s are parameters and it returns $\mu$ and $\delta$, in which $\delta$ is the value of the optimal objective function, according to the implementation listed in Algorithm 2. The program’s code in the Scicoslab language is listed in Appendix A.2.

Algorithm 2: Tropical Fractional Linear Programming: TFLP

3.5. Tropical Lexicographic Synchronization Programming

We solve the TLSO (10) using the general strategy proposed in Section 3.3. This implies solving a sequence of TFLPs (12), as discussed in Section 3.4. In this subsection, we describe this procedure in more detail.

First, note that the constraints in problem (10) can be rewritten as

(21)

Remember that we have a list $\mathcal{L}$ of pairs $\left(i\right(p),j(p\left)\right)$

$$\mathcal{L}=\left\{\right(i\left(1\right),j\left(1\right));(i\left(2\right),j\left(2\right))...(i\left(P\right),j\left(P\right)\left)\right\}$$

(22)

ordered by a decreasing priority and also that $x_{i\left(p\right)}\left(k\right)\ge x_{j\left(p\right)}\left(k\right)$. So, according to the procedure described in Section 3.3, the first problem that we need to solve is

(23)

a TFLP (as in (12)) which can be solved using the procedure described in Section 3.4. After this TFLP is solved, we obtain a solution ${\mu }_1^{*}$, and then we compute the first ${\delta }_1$ as

(24)

Now, the next step is to create the second problem in the sequence. We need to change the objective function to $I_2^T\mu -J_2^T\mu$ and also to add two new constraints:

$$(I_2^T\oplus J_2^T)\mu =I_2^T\mu .$$

(25)

(26)

The second problem, in addition to the previous constraints and the change of objective function, is augmented by two new constraints, one to synchronize the new pair and another constraint to guarantee the previous result ${\delta }_1$

(27)

$$\begin{array}{ccc}& & I_1^T\mu ={\delta }_1{J}_1^T\mu \hfill \\ & & (I_1^T\oplus J_1^T)\mu =I_1^T\mu .\hfill \end{array}$$

(28)

From the third problem on, up to $p=P$, we have two more constraints for each new pair:

(29)

$$\begin{array}{c}\hfill \left.(I_p^T\oplus J_p^T)\mu =I_p^T\mu \right\}p=P\\ \hfill \\ \hfill \left.\begin{array}{c}\hfill I_{p-1}^T\mu ={\delta }_{p-1}{J}_{p-1}^T\mu \\ \hfill (I_{p-1}^T\oplus J_{p-1}^T)\mu =I_{p-1}^T\mu \end{array}\right\}p=P-1\end{array}$$

(30)

$$\dots$$

$$\begin{array}{c}\hfill \left.\begin{array}{c}\hfill I_2^T\mu ={\delta }_2{J}_2^T\mu \\ \hfill (I_2^T\oplus J_2^T)\mu =I_2^T\mu \end{array}\right\}p=2\\ \hfill \\ \hfill \left.\begin{array}{c}\hfill I_1^T\mu ={\delta }_1{J}_1^T\mu \\ \hfill (I_1^T\oplus J_1^T)\mu =I_1^T\mu \end{array}\right\}p=1.\end{array}$$

(31)

If the $p^{th}$ pair cannot be synchronized, that is, if the Algorithm 2 returns $\mu$ equal to empty, the pair is deleted from the list $\mathcal{L}$, the size P of the list $\mathcal{L}$ is updated, and the iteration p is not increased.

The implementation of the TLSO is given by the function TLSO(A,B,L,lambda) in Algorithm 3. The program’s code in the Scicoslab language is listed in Appendix A.3, in which the parameters A and B are Max-Plus matrices. In ScicosLab the Max-Plus denomination is used instead of Tropical. L is the priority pairs list $\mathcal{L}$ represented by a matrix with P rows and two columns, and $\lambda$ is a scalar that is related to the period. The function TSLP returns the optimal ${\mu }^{*}$.

It is important to stress that the TLSO is tropical homogeneous—that means, if $\mu$ is a solution, so is $\alpha \mu$ with $\alpha$, a scalar. Therefore, we can shift the vector $\mu$ that we obtain after we solve the problem, so that all its elements are non-negative.

A numerical example is developed in Section 4 to clarify the TLSO method.

Algorithm 3: Tropical Lexicographic Synchronization Optimization: TLSO

4. Numerical Example

In this section, we develop a numerical example. We work with the TEG illustrated in Figure 1. As mentioned in the motivation Section 3.1, the illustrated TEG can model a traffic light system, which has two subsystems that refers to crossings. For more about the traffic light modeling with TEGs, see [13,26].

We suppose that the state equations are known and is given as follows:

$$\begin{array}{ccc}& & x_1(k+1)=10.6x_4\left(k\right)\hfill \\ & & x_2(k+1)=38.6x_1(k+1)\hfill \\ & & x_3(k+1)=12x_2(k+1)\hfill \\ & & x_4(k+1)=20.8x_3(k+1)\hfill \\ & & x_5(k+1)=20.8x_8\left(k\right)\hfill \\ & & x_6(k+1)=15.7x_5(k+1)\hfill \\ & & x_7(k+1)=12x_6(k+1)\hfill \\ & & x_8(k+1)=25.9x_7(k+1)\hfill \end{array}$$

(32)

We also suppose that the list $\mathcal{L}$ of pairs that have a connection is known and is given as follows:

$$\mathcal{L}=\left\{\right(3,7),(4,8),(4,7\left)\right)\}.$$

(33)

With these equations, we can write in state-space form $x[k+1]=Ax\left[k\right]\oplus Bu[k+1]$ once we define the matrices:

$$A_0=\left[\begin{array}{cc}{A}_0^1& {\epsilon }_{4\times 4}\\ {\epsilon }_{4\times 4}& A_0^2\end{array}\right],A_1=\left[\begin{array}{cc}{A}_1^1& {\epsilon }_{4\times 4}\\ {\epsilon }_{4\times 4}& A_1^2\end{array}\right],$$

(34)

in which,

$$A_0^1=\left[\begin{array}{cccc}\hfill \epsilon & \hfill \epsilon & \hfill \epsilon & \hfill \epsilon \\ \hfill 38.6& \hfill \epsilon & \hfill \epsilon & \hfill \epsilon \\ \hfill \epsilon & \hfill 12& \hfill \epsilon & \hfill \epsilon \\ \hfill \epsilon & \hfill \epsilon & \hfill 20.8& \hfill \epsilon \end{array}\right],$$

(35)

$$A_0^2=\left[\begin{array}{cccc}\hfill \epsilon & \hfill \epsilon & \hfill \epsilon & \hfill \epsilon \\ \hfill 15.7& \hfill \epsilon & \hfill \epsilon & \hfill \epsilon \\ \hfill \epsilon & \hfill 12& \hfill \epsilon & \hfill \epsilon \\ \hfill \epsilon & \hfill \epsilon & \hfill 25.9& \hfill \epsilon \end{array}\right],$$

(36)

$$A_1^1=\left[\begin{array}{cccc}\hfill \epsilon & \hfill \epsilon & \hfill \epsilon & \hfill 10.6\\ \hfill \epsilon & \hfill \epsilon & \hfill \epsilon & \hfill \epsilon \\ \hfill \epsilon & \hfill \epsilon & \hfill \epsilon & \hfill \epsilon \\ \hfill \epsilon & \hfill \epsilon & \hfill \epsilon & \hfill \epsilon \end{array}\right],$$

(37)

$$A_1^2=\left[\begin{array}{cccc}\hfill \epsilon & \hfill \epsilon & \hfill \epsilon & \hfill 20.8\\ \hfill \epsilon & \hfill \epsilon & \hfill \epsilon & \hfill \epsilon \\ \hfill \epsilon & \hfill \epsilon & \hfill \epsilon & \hfill \epsilon \\ \hfill \epsilon & \hfill \epsilon & \hfill \epsilon & \hfill \epsilon \end{array}\right].$$

(38)

The matrices $A_0$ and $A_1$ have relation with the times $x[k+1]$ (next state) and $x\left[k\right]$ (current state), respectively. We execute the operation Kleene closure (see [21]) and obtain the matrix $A=A_0^{*}{A}_1$:

$$A=\left[\begin{array}{cc}{A}^1& {\epsilon }_{4\times 4}\\ {\epsilon }_{4\times 4}& A^2\end{array}\right],$$

(39)

in which,

$$A^1=\left[\begin{array}{cccc}\hfill \epsilon & \hfill \epsilon & \hfill \epsilon & \hfill 10.6\\ \hfill \epsilon & \hfill \epsilon & \hfill \epsilon & \hfill 49.2\\ \hfill \epsilon & \hfill \epsilon & \hfill \epsilon & \hfill 61.2\\ \hfill \epsilon & \hfill \epsilon & \hfill \epsilon & \hfill 82\end{array}\right],$$

(40)

$$A^2=\left[\begin{array}{cccc}\hfill \epsilon & \hfill \epsilon & \hfill \epsilon & \hfill 20.8\\ \hfill \epsilon & \hfill \epsilon & \hfill \epsilon & \hfill 36.5\\ \hfill \epsilon & \hfill \epsilon & \hfill \epsilon & \hfill 48.5\\ \hfill \epsilon & \hfill \epsilon & \hfill \epsilon & \hfill 74.4\end{array}\right].$$

(41)

The matrix B is associated to control transition, thus, we obtain the matrix $B=A_0^{*}$, as 

$$B=\left[\begin{array}{cc}{B}^1& {\epsilon }_{4\times 4}\\ {\epsilon }_{4\times 4}& B^2\end{array}\right],$$

(42)

in which,

$$B^1=\left[\begin{array}{cccc}\hfill 0& \hfill \epsilon & \hfill \epsilon & \hfill \epsilon \\ \hfill 38.6& \hfill 0& \hfill \epsilon & \hfill \epsilon \\ \hfill 50.6& \hfill 12& \hfill 0& \hfill \epsilon \\ \hfill 71.4& \hfill 32.8& \hfill 20.8& \hfill 0\end{array}\right],$$

(43)

$$B^2=\left[\begin{array}{cccc}\hfill 0& \hfill \epsilon & \hfill \epsilon & \hfill \epsilon \\ \hfill 15.7& \hfill 0& \hfill \epsilon & \hfill \epsilon \\ \hfill 27.7& \hfill 12& \hfill 0& \hfill \epsilon \\ \hfill 53.6& \hfill 37.9& \hfill 25.9& \hfill 0\end{array}\right].$$

(44)

The cycle time of the system can be obtained by calculating the eigenvalue, which results $\lambda =82s$. Once the data ($A,B,\mathcal{L},\lambda$) is ready, as a result we get the synchronizing vector $\mu$ from the algorithm TLSO (Algorithm 3, listed code Appendix A.3).

Obtaining matrix M: The TLSO algorithm uses the parameters $\lambda$, A, and B to calculate the matrix ${M=\left((-\lambda )A\right)}^{*}B$, as 

$$M=\left[\begin{array}{cc}{M}^1& {\epsilon }_{4\times 4}\\ {\epsilon }_{4\times 4}& M^2\end{array},\right]$$

(45)

in which,

$$M^1=\left[\begin{array}{cccc}\hfill 0& \hfill -38.6& \hfill -50.6& \hfill -71.4\\ \hfill 38.6& \hfill 0& \hfill -12& \hfill -32.8\\ \hfill 50.6& \hfill 12& \hfill 0& \hfill -20.8\\ \hfill 71.4& \hfill 32.8& \hfill 20.8& \hfill 0\end{array}\right],$$

(46)

$$M^2=\left[\begin{array}{cccc}\hfill 0& \hfill -23.3& \hfill -35.3& \hfill -61.2\\ \hfill 15.7& \hfill 0& \hfill -19.6& \hfill -45.5\\ \hfill 27.7& \hfill 12& \hfill 0& \hfill -33.5\\ \hfill 53.6& \hfill 37.9& \hfill 25.9& \hfill 0\end{array}\right].$$

(47)

Step one: The algorithm TLSO starts the search by finding an optimal synchronized vector $\mu$ by solving the first optimization problem for the first pair of indexes from the list $\mathcal{L}$.

In the first iteration ($p=1$), the pair (3,7) from the list $\mathcal{L}$ is used, we have $i_p=7$ and $j_p=3$. In this way, $I_1$ (48) is the 7th line and $J_1$ (49) is the 3rd line of the matrix M:

$$I_1^T=\left[\begin{array}{cccccccc}\hfill \epsilon & \hfill \epsilon & \hfill \epsilon & \hfill \epsilon & \hfill 27.7& \hfill 12& \hfill 0& \hfill -33.5\end{array}\right]$$

(48)

$$J_1^T=\left[\begin{array}{cccccccc}\hfill 50.6& \hfill 12& \hfill 0& \hfill -20.8& \hfill \epsilon & \hfill \epsilon & \hfill \epsilon & \hfill \epsilon \end{array}\right].$$

(49)

In order to solve the first TFLP problem (see Section 3.4), we use $w=I_1$, $\alpha =0$, $f=J_1$, $\beta =\epsilon$, $R=I_1\oplus J_1$, $r=\epsilon$, $S=I_1$, and $s=\epsilon$.

The lexicographic algorithm calls the function TFLP (Algorithm 2) for these defined variables (w, $\alpha$, f, $\beta$, R, r, S, s). The function returns the variables ${\mu }_1^{*}$:

$${\mu }_1^{*T}=\left[\begin{array}{cccccccc}\hfill -50.6& \hfill -12& \hfill 0& \hfill 20.8& \hfill -27.7& \hfill -12& \hfill 0& \hfill 33.5\end{array}\right]$$

(50)

and ${\delta }_1=0$ (perfect synchronization between the transitions $x_7$ and $x_3$). In that way, we have the first vector ${\mu }_1^{*}$.

Second step: At the second iteration ($p=2$) the pair $(3,8)$ is used, we have $i\left(2\right)=3$ and $j\left(2\right)=8$, being $I_2$ and $J_2$:

$$I_2^T=\left[\begin{array}{cccccccc}\hfill \epsilon & \hfill \epsilon & \hfill \epsilon & \hfill \epsilon & \hfill 53.6& \hfill 37.9& \hfill 25.9& \hfill 0\end{array}\right],$$

(51)

$$J_2^T=\left[\begin{array}{cccccccc}\hfill 71.4& \hfill 32.8& \hfill 20.8& \hfill 0& \hfill \epsilon & \hfill \epsilon & \hfill \epsilon & \hfill \epsilon \end{array}\right].$$

(52)

From (28), we compute the R (53) and S (54) variables in the second iteration ($p=2$):

$$R=\left[\begin{array}{cccccccc}\hfill \epsilon & \hfill \epsilon & \hfill \epsilon & \hfill \epsilon & \hfill 53.6& \hfill 37.9& \hfill 25.9& \hfill 0\\ \hfill 50.6& \hfill 12& \hfill 0& \hfill \mathrm{-20.8}& \hfill \mathrm{\epsilon }& \hfill \mathrm{\epsilon }& \hfill \mathrm{\epsilon }& \hfill \mathrm{\epsilon }\\ \hfill \mathrm{\epsilon }& \hfill \mathrm{\epsilon }& \hfill \mathrm{\epsilon }& \hfill \mathrm{\epsilon }& \hfill 27.7& \hfill 12& \hfill 0& \hfill \mathrm{-33.5}\end{array}\right],$$

(53)

$$S=\left[\begin{array}{cccccccc}\hfill 71.4& \hfill 32.8& \hfill 20.8& \hfill 0& \hfill 53.6& \hfill 37.9& \hfill 25.9& \hfill 0\\ \hfill \mathrm{\epsilon }& \hfill \mathrm{\epsilon }& \hfill \mathrm{\epsilon }& \hfill \mathrm{\epsilon }& \hfill 27.7& \hfill 12& \hfill 0& \hfill \mathrm{-33.5}\\ \hfill 50.6& \hfill 12& \hfill 0& \hfill \mathrm{-20.8}& \hfill 27.7& \hfill 12& \hfill 0& \hfill \mathrm{-33.5}\end{array}\right].$$

(54)

The second iteration returns from the function TFLP the result of ${\mu }_2^{*T}$:

$${\mu }_2^{*T}=\left[\begin{array}{cccccccc}\hfill -76.5& \hfill -37.9& \hfill -25.9& \hfill -5.1& \hfill -53.6& \hfill -37.9& \hfill -25.9& \hfill 0\end{array}\right]$$

(55)

and ${\delta }_2=5.1$, which is the best synchronization possible in this case for this index pair.

Third step: At the third iteration ($p=3$), we have the pair $(4,7)$, in which we compute $I_3$ and $J_3$ correspondent to stages $i\left(3\right)=4$ and $j\left(3\right)=7$:

$$I_3^T=\left[\begin{array}{cccccccc}\hfill \epsilon & \hfill \epsilon & \hfill \epsilon & \hfill \epsilon & \hfill 27.7& \hfill 12& \hfill 0& \hfill -33.5\end{array}\right],$$

(56)

$$J_3^T=\left[\begin{array}{cccccccc}\hfill 71.4& \hfill 32.8& \hfill 20.8& \hfill 0& \hfill \epsilon & \hfill \epsilon & \hfill \epsilon & \hfill \epsilon \end{array}\right].$$

(57)

Once $I_3$ (56) and $J_3$ (57) are defined, we compute R and S as

$$R^T=\left[\begin{array}{ccccc}\hfill \epsilon & \hfill 76.5& \hfill \epsilon & \hfill 50.6& \hfill \epsilon \\ \hfill \epsilon & \hfill 37.9& \hfill \epsilon & \hfill 12& \hfill \epsilon \\ \hfill \epsilon & \hfill 25.9& \hfill \epsilon & \hfill 0& \hfill \epsilon \\ \hfill \epsilon & \hfill 5.1& \hfill \epsilon & \hfill -20.8& \hfill \epsilon \\ \hfill 27.7& \hfill \epsilon & \hfill 53.6& \hfill \epsilon & \hfill 27.7\\ \hfill 12& \hfill \epsilon & \hfill 37.9& \hfill \epsilon & \hfill 12\\ \hfill 0& \hfill \epsilon & \hfill 25.9& \hfill \epsilon & \hfill 0\\ \hfill -33.5& \hfill \epsilon & \hfill 0& \hfill \epsilon & \hfill -33.5\end{array}\right],$$

(58)

$$S^T=\left[\begin{array}{ccccc}\hfill 71.4& \hfill \epsilon & \hfill 71.4& \hfill \epsilon & \hfill 50.6\\ \hfill 32.8& \hfill \epsilon & \hfill 32.8& \hfill \epsilon & \hfill 12\\ \hfill 20.8& \hfill \epsilon & \hfill 20.8& \hfill \epsilon & \hfill 0\\ \hfill 0& \hfill \epsilon & \hfill 0& \hfill \epsilon & \hfill -20.8\\ \hfill 27.7& \hfill 53.6& \hfill 53.6& \hfill 27.7& \hfill 27.7\\ \hfill 12& \hfill 37.9& \hfill 37.9& \hfill 12& \hfill 12\\ \hfill 0& \hfill 25.9& \hfill 25.9& \hfill 0& \hfill 0\\ \hfill -33.5& \hfill 0& \hfill 0& \hfill -33.5& \hfill -33.5\end{array}\right].$$

(59)

Using these parameters R (58) and S (59), the third problem is solved, and the variable $\mu$ returns empty, which indicates that the algorithm does not converge and the synchronization is not possible. Therefore, we have to skip this phase and keep the last vector ${\mu }^{*}={\mu }_2^{*}$. Since there are no more pairs to synchronize, the algorithm is over.

As we explained in Section 3.5, we can shift the vector $\mu$ in a way that we have only non-negative values. Thus, we use $\mu =\lambda {\mu }_2^{*}$, obtaining

$${\mu }^T=\left[\begin{array}{cccccccc}\hfill 5.5& \hfill 44.1& \hfill 56.1& \hfill 76.9& \hfill 29.4& \hfill 44.1& \hfill 56.1& \hfill 82\end{array}\right].$$

(60)

The proposed example in this section clarifies the implementation of the lexicographic algorithm for synchronization among stages according to the previously defined list. In the first iteration, there is the perfect synchronization (${\delta }_1=0$). In the second iteration, the synchronization is possible with delay (${\delta }_2=5.1$). Lastly, in the third iteration, it is not possible to synchronize ($\mu$ is empty).

5. Conclusions

In this work, we propose the TLSO (Tropical Lexicographic Synchronization Optimization) framework. This framework is based on TFLP (Tropical Fractional Linear Programming), which allows the formulation and solution of problems in which it is desirable to synchronize transitions of TEGs. As far as the authors’ knowledge goes, there are few practical TLFP applications in the literature. Thus, this article’s contribution is the formalization and utilization of TFLP for modeling of synchronization problems, in which we develop a numerical example of traffic light synchronization. It is important to note that if synchronization is not feasible, the method will handle it.

The research gap served by this work is the lexicographic proposition together with models resolved by TFLP for synchronization of TEGs subject to delays. The framework proposed in this research is limited to the characteristics resulting from the time events graph model, which applies to systems subjected to synchronization and delay phenomena. The study does not apply to systems where there is a dispute over resources of another nature. As future work, we propose the formulation for broader models, represented by more general TDES. Another possibility for future work is to consider an approach for closed-loop systems. The proposed lexicographic method is also suitable for other systems, such as manufacturing systems, and others in which synchronization and resource sharing are desired.