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 ^[3][4] 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.

^[5] 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++ SDF³ open source tool set and also in the Python open source cmlib tool set.

References

1. F. Baccelli and G. Cohen and G. J. Olsder and J.P.Quadrat (1992): Synchronization and Linearity. John Wiley & Sons, 1992.
2. Bernd Heidergott and Geert Jan Olsder and Jacob Woude (2006): Max Plus at Work. Princeton University Press, 2006.
3. F. Baccelli and G. Cohen and G. J. Olsder and J.P.Quadrat (1992): Synchronization and Linearity. John Wiley & Sons, 1992.
4. Bernd Heidergott and Geert Jan Olsder and Jacob Woude (2006): Max Plus at Work. Princeton University Press, 2006.
5. H. Elahi and M. Geilen and T. Basten (2020): A Compositional Model for Multi-Rate Max-Plus Linear Systems. In: IFAC-PapersOnLine, vol. 53, no. 4, pp. 54-61, 2020, ISSN: 2405-8963, (15th IFAC Workshop on Discrete Event Systems WODES 2020 — Rio de Janeiro, Brazil, 11-13 November 2020).

Selected Related Publications

@article{MGVB23,

title = {Modeling and analysis of switching max-plus linear systems with discrete-event feedback},

author = {Alireza Mohamadkhani and Marc Geilen and Jeroen Voeten and Twan Basten},

url = {https://doi.org/10.1007/s10626-023-00382-y},

doi = {10.1007/s10626-023-00382-y},

issn = {0924-6703},

year  = {2023},

date = {2023-08-01},

urldate = {2023-08-01},

journal = {Discrete Event Dynamic Systems},

volume = {33},

number = {3},

pages = {341–372},

publisher = {Kluwer Academic Publishers},

address = {USA},

abstract = {Switching max-plus linear system (SMPLS) models are an apt formalism for performance analysis of discrete-event systems. SMPLS analysis is more scalable than analysis through other formalisms such as timed automata, because SMPLS abstract pieces of determinate concurrent system behavior into atomic modes with fixed timing. We consider discrete-event systems that are decomposed into a plant and a Supervisory Controller (SC) that controls the plant. The SC needs to react to events, concerning e.g. the successful completion or failure of an action, to determine the future behavior of the system, for example, to initiate a retrial of the action. To specify and analyze such system behavior and the impact of feedback on timing properties, we introduce an extension to SMPLS with discrete-event feedback. In this extension, we model the plant behavior with system modes and capture the timing of discrete-event feedback emission from plant to SC in the mode matrices. Furthermore, we use I/O automata to capture how the SC responds to discrete-event feedback with corresponding mode sequences of the SMPLS. We define the semantics of SMPLS with events using new state-space equations that are akin to classical SMPLS with dynamic state-vector sizes. To analyze the extended models, we formulate a transformation from SMPLS with events to classical SMPLS with equivalent semantics and properties such that performance properties can be analyzed using existing techniques. Our approach enables the specification of discrete-event feedback from the plant to the SC and its performance analysis. We demonstrate our approach by specifying and analyzing the makespan of a flexible manufacturing system.},

keywords = {},

pubstate = {published},

tppubtype = {article}

}

@article{SGRB22,

title = {Partial-Order Reduction for Supervisory Controller Synthesis},

author = {Bram Sanden and Marc Geilen and Michel Reniers and Twan Basten},

doi = {10.1109/TAC.2021.3129161},

year  = {2022},

date = {2022-01-01},

urldate = {2022-01-01},

journal = {IEEE Transactions on Automatic Control},

volume = {67},

number = {2},

pages = {870-885},

keywords = {},

pubstate = {published},

tppubtype = {article}

}

@inproceedings{SBSV21,

title = {LSAT: Specification and Analysis of Product Logistics in Flexible Manufacturing Systems},

author = {Bram Sanden and Yuri Blankenstein and Ramon Schiffelers and Jeroen Voeten},

doi = {10.1109/CASE49439.2021.9551412},

year  = {2021},

date = {2021-01-01},

urldate = {2021-01-01},

booktitle = {2021 IEEE 17th International Conference on Automation Science and Engineering (CASE)},

pages = {1-8},

keywords = {},

pubstate = {published},

tppubtype = {inproceedings}

}

@inbook{GSKea20,

title = {Scenarios in Dataflow Modeling and Analysis},

author = {Marc C. W. Geilen and Mladen Skelin and J. Reinier Kampenhout and Hadi Alizadeh Ara and Twan Basten and Sander Stuijk and Kees G. W. Goossens},

url = {https://doi.org/10.1007/978-3-030-20343-6_8},

doi = {10.1007/978-3-030-20343-6_8},

isbn = {978-3-030-20343-6},

year  = {2020},

date = {2020-01-01},

urldate = {2020-01-01},

booktitle = {System-Scenario-based Design Principles and Applications},

pages = {145–180},

publisher = {Springer International Publishing},

address = {Cham},

keywords = {},

pubstate = {published},

tppubtype = {inbook}

}

@inbook{BBMea20,

title = {Scenarios in the Design of Flexible Manufacturing Systems},

author = {Twan Basten and João Bastos and Róbinson Medina and Bram Sanden and Marc C. W. Geilen and Dip Goswami and Michel A. Reniers and Sander Stuijk and Jeroen P. M. Voeten},

url = {https://doi.org/10.1007/978-3-030-20343-6_9},

doi = {10.1007/978-3-030-20343-6_9},

year  = {2020},

date = {2020-01-01},

urldate = {2020-01-01},

booktitle = {System-Scenario-based Design Principles and Applications},

pages = {181–224},

publisher = {Springer International Publishing},

address = {Cham},

keywords = {},

pubstate = {published},

tppubtype = {inbook}

}

@phdthesis{San18,

title = {performance analysis and optimization of supervisory controllers},

author = {Bram Sanden},

year  = {2018},

date = {2018-01-01},

urldate = {2018-01-01},

school = {Eindhoven University of Technology},

keywords = {},

pubstate = {published},

tppubtype = {phdthesis}

}

@inproceedings{SBVea16,

title = {Compositional specification of functionality and timing of manufacturing systems},

author = {Bram Sanden and João Bastos and Jeroen Voeten and Marc Geilen and Michel A. Reniers and Twan Basten and Johan Jacobs and Ramon R. H. Schiffelers},

url = {https://doi.org/10.1109/FDL.2016.7880372},

doi = {10.1109/FDL.2016.7880372},

year  = {2016},

date = {2016-01-01},

urldate = {2016-01-01},

booktitle = {2016 Forum on Specification and Design Languages, FDL 2016, Bremen, Germany, September 14-16, 2016},

pages = {1–8},

keywords = {},

pubstate = {published},

tppubtype = {inproceedings}

}

@inproceedings{GFHea14,

title = {Performance analysis of weakly-consistent scenario-aware dataflow graphs},

author = {Marc Geilen and Joachim Falk and Christian Haubelt and Twan Basten and Bart Theelen and Sander Stuijk},

doi = {10.1109/ACSSC.2014.7094470},

year  = {2014},

date = {2014-01-01},

urldate = {2014-01-01},

booktitle = {2014 48th Asilomar Conference on Signals, Systems and Computers},

pages = {393-397},

keywords = {},

pubstate = {published},

tppubtype = {inproceedings}

}

@inproceedings{YGBSC12,

title = {Playing games with scenario- and resource-aware SDF graphs through policy iteration},

author = {Yang Yang and Marc Geilen and Twan Basten and Sander Stuijk and Henk Corporaal},

doi = {10.1109/DATE.2012.6176462},

year  = {2012},

date = {2012-01-01},

urldate = {2012-01-01},

booktitle = {2012 Design, Automation & Test in Europe Conference & Exhibition (DATE)},

pages = {194-199},

keywords = {},

pubstate = {published},

tppubtype = {inproceedings}

}

@inproceedings{GS10,

title = {Worst-Case Performance Analysis of Synchronous Dataflow Scenarios},

author = {Marc Geilen and Sander Stuijk},

url = {https://doi.org/10.1145/1878961.1878985},

doi = {10.1145/1878961.1878985},

isbn = {9781605589053},

year  = {2010},

date = {2010-01-01},

urldate = {2010-01-01},

booktitle = {Proceedings of the Eighth IEEE/ACM/IFIP International Conference on Hardware/Software Codesign and System Synthesis},

pages = {125–134},

publisher = {Association for Computing Machinery},

address = {Scottsdale, Arizona, USA},

series = {CODES/ISSS '10},

keywords = {},

pubstate = {published},

tppubtype = {inproceedings}

}

@book{HOW06,

title = {Max Plus at Work},

author = {Bernd Heidergott and Geert Jan Olsder and Jacob Woude},

year  = {2006},

date = {2006-01-01},

urldate = {2006-01-01},

publisher = {Princeton University Press},

keywords = {},

pubstate = {published},

tppubtype = {book}

}

@inproceedings{CTCea98,

title = {Numerical computation of spectral elements in max-plus algebra},

author = {J. Cochet-Terrasson and G. Cohen and S. Gaubert and M. M. Gettrick and J. -P. Quadrat},

year  = {1998},

date = {1998-07-01},

urldate = {1998-07-01},

booktitle = {Proc.~of the IFAC Conference on System Structure and Control},

address = {Nantes},

keywords = {},

pubstate = {published},

tppubtype = {inproceedings}

}

@article{Gau95,

title = {Performance Evaluation of (max, +) automata},

author = {S. Gaubert},

year  = {1995},

date = {1995-01-01},

urldate = {1995-01-01},

journal = {IEEE Trans. Automatic Control},

volume = {40},

number = {12},

pages = {2014-2025},

keywords = {},

pubstate = {published},

tppubtype = {article}

}