Breaking the dimensionality curse in multi-server queues

Alexandre Brandwajn 1 Thomas Begin 2
2 DANTE - Dynamic Networks : Temporal and Structural Capture Approach
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme, IXXI - Institut Rhône-Alpin des systèmes complexes
Abstract : Ph/Ph/c and and Ph/Ph/c/N queues can be viewed as a common model of multi-server facilities. We propose a simple approximate solution for the equilibrium probabilities in such queues based on a reduced state description in order to circumvent the well-known and dreaded combinatorial growth of the number of states inherent in the classical state description. The number of equations to solve in our approach increases linearly with the number of servers and phases in the service time distribution. A simple fixed-point iteration is used to solve these equations. Our approach applies both to open models with unrestricted buffer size and to queues with finite-size buffers. The results of a large number of empirical studies indicate that the overall accuracy of the proposed approximation appears very good. For instance, the median relative error for the mean number in the queue over thousands of examples is below 0.1% and the relative error exceeds 5% in less than 1.5% of cases explored. The accuracy of the proposed approximation becomes particularly good for systems with more than 8 servers, and tends to become excellent as the number of servers increases.
Type de document :
Article dans une revue
Computers and Operations Research, Elsevier, 2016, 〈10.1016/j.cor.2016.04.011〉
Liste complète des métadonnées

Littérature citée [22 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01322249
Contributeur : Thomas Begin <>
Soumis le : jeudi 26 mai 2016 - 18:17:52
Dernière modification le : mardi 16 janvier 2018 - 16:29:48
Document(s) archivé(s) le : samedi 27 août 2016 - 11:05:23

Fichier

Revision.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Alexandre Brandwajn, Thomas Begin. Breaking the dimensionality curse in multi-server queues. Computers and Operations Research, Elsevier, 2016, 〈10.1016/j.cor.2016.04.011〉. 〈hal-01322249〉

Partager

Métriques

Consultations de la notice

150

Téléchargements de fichiers

59