Analysing multiprogramming queues by generating functions

    Research output: Contribution to journalArticleAcademicpeer-review

    3 Citations (Scopus)
    142 Downloads (Pure)


    The generating function approach for analysing queueing systems has a long-standing tradition. One of the highlights is the seminal paper by Kingman [Ann. Math. Statist., 32(1961), pp. 1314–1323] on the shortest-queue problem, where the author shows that the equilibrium probabilities $p_{m,n} $ of the queue lengths can be written as an infinite sum of products of powers. The same approach is used by Hofri [Internal. J. Computer and Information Sci., 7 (1978), pp. 121–155] to prove that, for a multiprogramming model with two queues, the boundary probability $p_{0, j} $ can be expressed as an infinite sum of powers. This paper shows that the latter representation does not always hold, which implies that the multiprogramming problem is essentially more complicated than the shortest-queue problem. However, it appears that the generating function approach is very well suited to show when such a representation is available and when it is not.
    Original languageEnglish
    Pages (from-to)1123-1131
    Number of pages9
    JournalSIAM Journal on Applied Mathematics
    Issue number4
    Publication statusPublished - 1993


    Dive into the research topics of 'Analysing multiprogramming queues by generating functions'. Together they form a unique fingerprint.

    Cite this