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