Max-plus Algebraic Models

Max-plus algebra [1, 2] is a linear algebra to capture timing and performance of tasks and their dependencies. It has a wide variety of applications, from logistics, scheduling, cyber-physical systems to data processing and computational processes.

It works on the set \(\mathbb{R}\) of real numbers, extended with the special element \(-\infty\). It defines two operators:

$$x\oplus y = \max(x,y)$$

$$x\otimes y = x+y$$
\(\oplus\) typically captures dependencies and synchronization events, for example, a task that requires two other tasks to be complete, can start at time \(x \oplus y\) if \(x\) and \(y\) are the respective completion times of those tasks. The \(\otimes\) operator, on the other hand, typically captures durations or temporal constraints. For example, a task that starts at time \(x\) and takes \(y\) time units completes at time \(x\otimes y\).

With these operators, it defines a linear algebra that is often extended to a matrix-vector calculus similar to traditional linear algebra. One can then use this to capture max-plus-linear systems with common state-space equations.

$$\mathbf{x}(k+1) = \mathbf{A} \otimes \mathbf{x}(k) \oplus \mathbf{B} \otimes \mathbf{u}(k)$$

$$\mathbf{y}(k) = \mathbf{C} \otimes \mathbf{x}(k) \oplus \mathbf{D} \otimes \mathbf{u}(k)$$

A rich set of properties and analysis methods have been developed [1, 2] for this algebra.

For the interested reader, more details and exercises about max-plus algebra can also be found in the Lecture notes on Dataflow modeling and Max-Plus algebra used in the course Computational Modeling (5XIE0). And here are some related exam problems.

Using Max-Plus Algebra

We have used max-plus algebra to capture the behavior of Timed Data Flow models, where firing times of actors and production times of tokens can conveniently be expressed as max-plus-linear combinations of time stamps of input tokens and internal tokens of a dataflow graph. Most of the analysis algorithms for timed dataflow models are based on max-plus algebra.

We have also used max-plus algebraic models to capture logistic processes in cyber-physical systems. We use Activity Models to specify logistic systems. The semantics of activities is captured with max-plus matrices and activity models themselves as switching max-plus linear systems, using max-plus automata.

[3] describes a compositional semantics of max-plus linear systems, where state-space representations of components are composed to construct new state-space representations of the composites.

Tools

We have implemented max-plus algebra analysis algorithms in the C++ SDF3 open source tool set and also in the Python open source cmlib tool set.

Selected Related Publications

  • [DOI] M. Geilen and S. Stuijk, “Worst-case performance analysis of synchronous dataflow scenarios,” in Proceedings of the eighth ieee/acm/ifip international conference on hardware/software codesign and system synthesis, New York, NY, USA, 2010, p. 125–134.
    [Bibtex] 
    @InProceedings{GS10,
author = {Geilen, Marc and Stuijk, Sander},
title = {Worst-Case Performance Analysis of Synchronous Dataflow Scenarios},
year = {2010},
isbn = {9781605589053},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1878961.1878985},
doi = {10.1145/1878961.1878985},
booktitle = {Proceedings of the Eighth IEEE/ACM/IFIP International Conference on Hardware/Software Codesign and System Synthesis},
pages = {125–134},
numpages = {10},
location = {Scottsdale, Arizona, USA},
series = {CODES/ISSS '10}
}
  • B. van der Sanden, “Performance analysis and optimization of supervisory controllers,” PhD Thesis, 2018.
    [Bibtex] 
    @PhdThesis{San18,
author = {Bram van der Sanden},
title = {performance analysis and optimization of supervisory controllers},
school = {Eindhoven University of Technology},
year = {2018},
}
  • [DOI] T. Basten, J. Bastos, R. Medina, B. van der Sanden, M. C. W. Geilen, D. Goswami, M. A. Reniers, S. Stuijk, and J. P. M. Voeten, “Scenarios in the design of flexible manufacturing systems,” in System-scenario-based design principles and applications, Cham: Springer international publishing, 2020, p. 181–224.
    [Bibtex] 
    @Inbook{BBMea20,
author="Basten, Twan
and Bastos, Jo{\~a}o
and Medina, R{\'o}binson
and van der Sanden, Bram
and Geilen, Marc C. W.
and Goswami, Dip
and Reniers, Michel A.
and Stuijk, Sander
and Voeten, Jeroen P. M.",
title="Scenarios in the Design of Flexible Manufacturing Systems",
bookTitle="System-Scenario-based Design Principles and Applications",
year="2020",
publisher="Springer International Publishing",
address="Cham",
pages="181--224",
doi="10.1007/978-3-030-20343-6_9",
url="https://doi.org/10.1007/978-3-030-20343-6_9"
}
  • [DOI] M. C. W. Geilen, M. Skelin, R. J. van Kampenhout, H. A. Ara, T. Basten, S. Stuijk, and K. G. W. Goossens, “Scenarios in dataflow modeling and analysis,” in System-scenario-based design principles and applications, Cham: Springer international publishing, 2020, p. 145–180.
    [Bibtex] 
    @Inbook{GSKea20,
author="Geilen, Marc C. W.
and Skelin, Mladen
and van Kampenhout, J. Reinier
and Ara, Hadi Alizadeh
and Basten, Twan
and Stuijk, Sander
and Goossens, Kees G. W.",
title="Scenarios in Dataflow Modeling and Analysis",
bookTitle="System-Scenario-based Design Principles and Applications",
year="2020",
publisher="Springer International Publishing",
address="Cham",
pages="145--180",
isbn="978-3-030-20343-6",
doi="10.1007/978-3-030-20343-6_8",
url="https://doi.org/10.1007/978-3-030-20343-6_8"
}

References

[1] F. Baccelli, G. Cohen, G. J. Olsder, and J.P.Quadrat, Synchronization and linearity, John wiley & sons, 1992.
[Bibtex]
@Book{BCO92,
title = {Synchronization and Linearity},
publisher = {John Wiley \& Sons},
year = {1992},
author = {F. Baccelli and G. Cohen and G.J. Olsder and J.P.Quadrat},
owner = {mgeilen},
timestamp = {2009.04.22},
}
[2] B. Heidergott, G. J. Olsder, and J. van der Woude, Max plus at work, Princeton university press, 2006.
[Bibtex]
@Book{HOW06,
title = {Max Plus at Work},
publisher = {Princeton University Press},
year = {2006},
author = {Bernd Heidergott and Geert Jan Olsder and Jacob van der Woude},
owner = {mgeilen},
timestamp = {2009.07.06},
}
[3] [doi] H. Elahi, M. Geilen, and T. Basten, “A compositional model for multi-rate max-plus linear systems,” Ifac-papersonline, vol. 53, iss. 4, pp. 54-61, 2020.
[Bibtex]
@Article{EGB20,
author = {H. Elahi and M. Geilen and T. Basten},
journal = {IFAC-PapersOnLine},
title = {A Compositional Model for Multi-Rate Max-Plus Linear Systems},
year = {2020},
issn = {2405-8963},
note = {15th IFAC Workshop on Discrete Event Systems WODES 2020 — Rio de Janeiro, Brazil, 11-13 November 2020},
number = {4},
pages = {54-61},
volume = {53},
doi = {https://doi.org/10.1016/j.ifacol.2021.04.006},
keywords = {Discrete-event systems, Max-plus linear systems, Compositional models},
url = {https://www.sciencedirect.com/science/article/pii/S2405896321000306},
}