Switching Max-Plus-Linear Systems

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.

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.

Selected Related Publications

2023

Mohamadkhani, Alireza; Geilen, Marc; Voeten, Jeroen; Basten, Twan

Modeling and analysis of switching max-plus linear systems with discrete-event feedback Journal Article

In: Discrete Event Dynamic Systems, vol. 33, no. 3, pp. 341–372, 2023, ISSN: 0924-6703.

Abstract | Links | BibTeX

@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}

}

2018

Sanden, Bram

performance analysis and optimization of supervisory controllers PhD Thesis

Eindhoven University of Technology, 2018.

BibTeX

2017

Geilen, Marc; Falk, Joachim; Haubelt, Christian; Basten, Twan; Theelen, Bart; Stuijk, Sander

Performance Analysis of Weakly-Consistent Scenario-Aware Dataflow Graphs Journal Article

In: Journal of Signal Processing Systems, vol. 87, no. 1, pp. 157–175, 2017, ISSN: 1939-8115.

Links | BibTeX

2016

Sanden, Bram; Bastos, João; Voeten, Jeroen; Geilen, Marc; Reniers, Michel A.; Basten, Twan; Jacobs, Johan; Schiffelers, Ramon R. H.

Compositional specification of functionality and timing of manufacturing systems Proceedings Article

In: 2016 Forum on Specification and Design Languages, FDL 2016, Bremen, Germany, September 14-16, 2016, pp. 1–8, 2016.

Links | BibTeX

2010

Geilen, Marc; Stuijk, Sander

Worst-Case Performance Analysis of Synchronous Dataflow Scenarios Proceedings Article

In: Proceedings of the Eighth IEEE/ACM/IFIP International Conference on Hardware/Software Codesign and System Synthesis, pp. 125–134, Association for Computing Machinery, Scottsdale, Arizona, USA, 2010, ISBN: 9781605589053.

Links | BibTeX

Switching Max-Plus-Linear Systems

Max-Plus Linear Systems