A tight bound on the throughput of queueing networks with blocking

Jean-Sébastien Tancrez, Philippe Chevalier and Pierre Semal

No 2008063, LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE)

Abstract: In this paper, we present a bounding methodology that allows to compute a tight lower bound on the cycle time of fork--join queueing networks with blocking and with general service time distributions. The methodology relies on two ideas. First, probability masses fitting (PMF) discretizes the service time distributions so that the evolution of the modified network can be modelled by a Markov chain. The PMF discretization is simple: the probability masses on regular intervals are computed and aggregated on a single value in the orresponding interval. Second, we take advantage of the concept of critical path, i.e. the sequence of jobs that covers a sample run. We show that the critical path can be computed with the discretized distributions and that the same sequence of jobs offers a lower bound on the original cycle time. The tightness of the bound is shown on computational experiments. Finally, we discuss the extension to split--and--merge networks and approximate estimations of the cycle time.

Keywords: queueing networks; blocking; throughput; bound; probability masses fitting; critical path. (search for similar items in EconPapers)
Date: 2008-11-01
References: Add references at CitEc
Citations:

Downloads: (external link)
https://sites.uclouvain.be/core/publications/coredp/coredp2008.html (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:cor:louvco:2008063

Access Statistics for this paper

More papers in LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE) Voie du Roman Pays 34, 1348 Louvain-la-Neuve (Belgium). Contact information at EDIRC.
Bibliographic data for series maintained by Alain GILLIS ().