Many systems have deterministic concurrent behavior. Tasks or operations are executed in fixed patterns and with fixed dependencies. Examples are software task graphs, or operations of a manufacturing system.
If we are interested in performance related questions about such systems, e.g., “what is the average throughput?”, or “What is the makespan or latency?”, then max-plus algebra is often a very suitable model to study such systems.
Max-Plus Linear Systems
Max-plus algebra [1, 2, 3, 4] is a linear algebra and therefore has strong analysis possibilities. It captures concurrency in a very different way than state-based models, which allow one to escape the state-space explosion problem in some cases. More about max-plus algebra on this page.
Switching Max-Plus-Linear Systems
A strong prerequisite to the use of plain max-plus-linear modeling is the requirement that systems behave deterministically, i.e., always execute the same operations in the same order.
Many systems in practice do not always behave deterministically. Some operations may or not be included in the task, may be interrupted by sporadic maintenance or startup-up actions.
This challenge may be addressed by considering switched max-plus-linear systems. These are systems that may switch between different max-plus-linear modes of operations.
The possible orders in which such modes can occur can restricted by a separate specification, typically using some form of automata.
See also
- Scenario Aware Data Flow is a dataflow model that is built on switching max-plus-linear systems. Individual scenarios can be captured by max-plus matrices and the changing between scenarios as switching between max-plus-linear modes.
- Activity Models are aimed at modelling logistic processes in flexible manufacturing systems. Activity model use switching max-plus-linear systems as their semantic model and it is supported by the LSAT tool.
- xCPS is a lab model of flexible manufacturing system and has been modeled as a switching max-plus-linear system using the activity modelling formalism.
Selected Related Publications
- F. Siyoum, M. Geilen, J. Eker, C. von Platen, and H. Corporaal, “Automated extraction of scenario sequences from disciplined dataflow networks,” in 2013 eleventh acm/ieee international conference on formal methods and models for codesign (memocode 2013), USA, 2013, pp. 47-56.
[Bibtex]@INPROCEEDINGS{SGEPC13, author={Siyoum, Firew and Geilen, Marc and Eker, Johan and von Platen, Carl and Corporaal, Henk}, booktitle={2013 Eleventh ACM/IEEE International Conference on Formal Methods and Models for Codesign (MEMOCODE 2013)}, title={Automated extraction of scenario sequences from disciplined dataflow networks}, year={2013}, volume={}, number={}, pages={47-56}, publisher = {IEEE Computer Society}, address = {USA}, numpages = {10}, } -
![[DOI]](https://computationalmodeling.info/wp/wp-content/plugins/papercite/img/external.png)
M. Geilen, J. Falk, C. Haubelt, T. Basten, B. Theelen, and S. Stuijk, “Performance analysis of weakly-consistent scenario-aware dataflow graphs,” Journal of signal processing systems, vol. 87, iss. 1, p. 157–175, 2017.
[Bibtex]@Article{GFHea16, author = {Geilen, Marc and Falk, Joachim and Haubelt, Christian and Basten, Twan and Theelen, Bart and Stuijk, Sander}, title = {Performance Analysis of Weakly-Consistent Scenario-Aware Dataflow Graphs}, journal = {Journal of Signal Processing Systems}, year = {2017}, volume = {87}, number = {1}, pages = {157--175}, issn = {1939-8115}, doi = {10.1007/s11265-016-1193-7}, url = {http://dx.doi.org/10.1007/s11265-016-1193-7}, } - 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, J. Bastos, J. Voeten, M. Geilen, M. A. Reniers, T. Basten, J. Jacobs, and R. R. H. Schiffelers, “Compositional specification of functionality and timing of manufacturing systems,” in 2016 forum on specification and design languages, FDL 2016, bremen, germany, september 14-16, 2016, 2016, p. 1–8.
[Bibtex]@InProceedings{SBVea16, author = {Bram van der Sanden and Jo{\~{a}}o Bastos and Jeroen Voeten and Marc Geilen and Michel A. Reniers and Twan Basten and Johan Jacobs and Ramon R. H. Schiffelers}, title = {Compositional specification of functionality and timing of manufacturing systems}, booktitle = {2016 Forum on Specification and Design Languages, {FDL} 2016, Bremen, Germany, September 14-16, 2016}, year = {2016}, pages = {1--8}, doi = {10.1109/FDL.2016.7880372}, timestamp = {Wed, 24 May 2017 08:31:17 +0200}, url = {https://doi.org/10.1109/FDL.2016.7880372}, } - 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}, }
References
[1] B. Heidergott, G. J. Olsder, and J. van der Woude, Max plus at work, Princeton university press, 2006.
[Bibtex]
[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},
}[2] T. J. J. van den Boom and B. De Schutter, “Modelling and control of discrete event systems using switching max-plus-linear systems,” Control engineering practice, vol. 14, iss. 10, p. 1199–1211, 2006.
[Bibtex]
T. J. J. van den Boom and B. De Schutter, “Modelling and control of discrete event systems using switching max-plus-linear systems,” Control engineering practice, vol. 14, iss. 10, p. 1199–1211, 2006. [Bibtex]
@Article{BD06,
author = {T.J.J. {van den Boom} and B. {De Schutter}},
title = {Modelling and control of discrete event systems using switching max-plus-linear systems},
journal = {Control Engineering Practice},
year = {2006},
volume = {14},
number = {10},
pages = {1199--1211},
month = oct,
doi = {10.1016/j.conengprac.2006.02.006},
}[3] S. Gaubert, “Performance evaluation of (max, +) automata,” Ieee trans. automatic control, vol. 40, iss. 12, pp. 2014-2025, 1995.
[Bibtex]
[Bibtex]
@Article{Gau95,
author = {S. Gaubert},
title = {Performance Evaluation of (max, +) automata},
journal = {IEEE Trans. Automatic Control},
year = {1995},
volume = {40},
number = {12},
pages = {2014-2025},
owner = {mgeilen},
timestamp = {2010.04.10},
}[4] F. Baccelli, G. Cohen, G. J. Olsder, and J.P.Quadrat, Synchronization and linearity, John wiley & sons, 1992.
[Bibtex]
[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},
}