A characterisation of (max, +)-linear queueing systems

B.F. Heidergott

Research output: Contribution to journalArticleAcademicpeer-review

19 Citations (Scopus)
1 Downloads (Pure)


The (max,+)-algebra has been successfully applied to many areas of queueing theory, like stability analysis and ergodic theory. These results are mainly based on two ingredients: (1) a (max,+)-linear model of the time dynamic of the system under consideration, and (2) the time-invariance of the structure of the (max,+)-model. Unfortunately, (max,+)-linearity is a purely algebraic concept and it is by no means immediate if a queueing network admits a (max,+)-linear representation satisfying (1) and (2). In this paper we derive the condition a queueing network must meet if it is to have a (max,+)-linear representation. In particular, we study (max,+)-linear systems with time-invariant transition structures. For this class of systems, we find a surprisingly simple necessary and sufficient condition for (max,+)-linearity, based on the flow of customers through the network.
Original languageEnglish
Pages (from-to)237-262
JournalQueueing Systems: Theory and Applications
Issue number1-4
Publication statusPublished - 2000


Dive into the research topics of 'A characterisation of (max, +)-linear queueing systems'. Together they form a unique fingerprint.

Cite this